Submission #1515614
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int md = 1e9 + 7; const int maxn = 1e6 + 7; int dp[maxn]; int suf[maxn]; int ss[maxn]; int main() { fill(dp,dp+maxn,0); fill(suf,suf+maxn,0); fill(ss,ss+maxn,0); int n; cin>>n; if (n == 1) { cout<<1<<endl; return 0; } dp[n] = suf[n] = ss[n] = n-1; int n2 = ((long long)(n-1) * (n-1))%( (long long) md); for (int j = n-1; j >= 1; j--) { if (j == 1) dp[j] = (n + suf[2])%md; else dp[j] = n-1; dp[j] = (dp[j] + n2 + ss[j+3])%md; suf[j] = (suf[j+1] + dp[j])%md; ss[j] = (ss[j+1] + suf[j])%md; } cout<<dp[1]<<endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Infinite Sequence |
User | mbrc |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 626 Byte |
Status | WA |
Exec Time | 12 ms |
Memory | 11904 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt |
All | 0_000.txt, 0_001.txt, max_1000000.txt, max_999745.txt, max_999880.txt, max_999999.txt, min_1.txt, rnd_14.txt, rnd_22.txt, rnd_25002.txt, rnd_2956.txt, rnd_3.txt, rnd_380467.txt, rnd_407774.txt, rnd_52228.txt, rnd_68.txt, rnd_804783.txt, rnd_85984.txt, rnd_894324.txt, rnd_93.txt, rnd_963981.txt, rnd_968416.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 5 ms | 11904 KB |
0_001.txt | AC | 9 ms | 11904 KB |
max_1000000.txt | WA | 11 ms | 11904 KB |
max_999745.txt | AC | 11 ms | 11904 KB |
max_999880.txt | WA | 12 ms | 11904 KB |
max_999999.txt | WA | 12 ms | 11904 KB |
min_1.txt | AC | 5 ms | 11904 KB |
rnd_14.txt | AC | 5 ms | 11904 KB |
rnd_22.txt | AC | 5 ms | 11904 KB |
rnd_25002.txt | AC | 5 ms | 11904 KB |
rnd_2956.txt | AC | 5 ms | 11904 KB |
rnd_3.txt | AC | 5 ms | 11904 KB |
rnd_380467.txt | AC | 7 ms | 11904 KB |
rnd_407774.txt | AC | 8 ms | 11904 KB |
rnd_52228.txt | AC | 5 ms | 11904 KB |
rnd_68.txt | AC | 5 ms | 11904 KB |
rnd_804783.txt | AC | 11 ms | 11904 KB |
rnd_85984.txt | AC | 5 ms | 11904 KB |
rnd_894324.txt | AC | 11 ms | 11904 KB |
rnd_93.txt | AC | 5 ms | 11904 KB |
rnd_963981.txt | AC | 11 ms | 11904 KB |
rnd_968416.txt | AC | 12 ms | 11904 KB |