Submission #1214053


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

int d1[2505][10005]; // [i+1, i]
int d2[2505][10005]; // [i, i]
int n, k, x, a[2505];

int main(){
	for(int i=0; i<=2500; i++){
		int s[10005] = {};
		if(i > 0){
			for(int j=1; j<=10000; j++) s[j] = (s[j-1] + d1[i-1][j]) % mod;
		}
		for(int j=1; j<=10000; j++){
			if(j <= 2 * i + 1) d2[i][j]++;
			d2[i][j] += s[j-1] - s[max(0, j-2*i-1)] + mod;
			d2[i][j] %= mod;
		}
		for(int j=1; j<=10000; j++) s[j] = (s[j-1] + d2[i][j]) % mod;
		for(int j=1; j<=10000; j++){
			if(j <= 2 * i + 2) d1[i][j]++;
			d1[i][j] += s[j-1] - s[max(0, j-2*i-3)] + mod;
			d1[i][j] %= mod;
		}
	}
	cin >> n >> k >> x;
	for(int i=0; i<k; i++) cin >> a[i];
	lint ret = 1;
	for(int i=1; i<k; i++){
		if(x - i < 0) ret = 0;
		else ret *= d1[x-i][a[i] - a[i-1]];
		ret %= mod;
	}
	cout << ret << endl;
}

Submission Info

Submission Time
Task E - Enormous Atcoder Railroad
User koosaga
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 967 Byte
Status AC
Exec Time 469 ms
Memory 195968 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4 Subtask5
Score / Max Score 120 / 120 90 / 90 260 / 260 160 / 160 370 / 370
Status
AC × 3
AC × 6
AC × 9
AC × 12
AC × 15
Set Name Test Cases
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt
Subtask3 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt
Subtask4 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt
Subtask5 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub5_in1.txt, sub5_in2.txt, sub5_in3.txt
Case Name Status Exec Time Memory
sub1_in1.txt AC 468 ms 195968 KB
sub1_in2.txt AC 468 ms 195968 KB
sub1_in3.txt AC 468 ms 195968 KB
sub2_in1.txt AC 468 ms 195968 KB
sub2_in2.txt AC 468 ms 195968 KB
sub2_in3.txt AC 468 ms 195968 KB
sub3_in1.txt AC 468 ms 195968 KB
sub3_in2.txt AC 468 ms 195968 KB
sub3_in3.txt AC 468 ms 195968 KB
sub4_in1.txt AC 468 ms 195968 KB
sub4_in2.txt AC 468 ms 195968 KB
sub4_in3.txt AC 468 ms 195968 KB
sub5_in1.txt AC 469 ms 195968 KB
sub5_in2.txt AC 469 ms 195968 KB
sub5_in3.txt AC 469 ms 195968 KB