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 |
|
|
|
|
|
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 |