Submission #3900718
Source Code Expand
#include<bits/stdc++.h> #define MAX_N 100001 #define INF_INT 2147483647 #define INF_LL 9223372036854775807 #define REP(i,n) for(int i=0;i<(int)(n);i++) using namespace std; typedef long long int ll; typedef pair<ll,ll> P; ll bpow(ll,ll,ll); const ll MOD = 1000000007; ll dp[200001] = {0}; int main() { ll N,M,f[200002],res=0,n=0,tr=1,back[200002],lo[200002],sum[200002]={0}; cin >> N >> M; REP(i,N)cin >> f[i+1]; REP(i,N+1){ dp[i] = 0; back[i] = 0; lo[i] = 0; sum[i] = 0; } REP(i,N){ back[i+1] = lo[f[i+1]]; lo[f[i+1]] = i+1; } dp[0] = 1; sum[0] = 1; int ind=0; for(int i=0;i<N;i++){ if(ind < back[i+1]){ ind = back[i+1]; } dp[i+1] = (MOD+sum[i] - (ind == 0 ? 0 : sum[ind-1]))%MOD; sum[i+1] = (sum[i] + dp[i+1])%MOD; } cout << dp[N] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - サプリメント |
User | makss |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 874 Byte |
Status | AC |
Exec Time | 33 ms |
Memory | 7296 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample01.txt, subtask0-sample02.txt |
Subtask1 | subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 | subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample01.txt | AC | 3 ms | 5632 KB |
subtask0-sample02.txt | AC | 2 ms | 4736 KB |
subtask1-01.txt | AC | 3 ms | 4736 KB |
subtask1-02.txt | AC | 3 ms | 4992 KB |
subtask1-03.txt | AC | 3 ms | 5888 KB |
subtask1-04.txt | AC | 4 ms | 5888 KB |
subtask1-05.txt | AC | 3 ms | 4992 KB |
subtask1-06.txt | AC | 3 ms | 4736 KB |
subtask1-07.txt | AC | 4 ms | 5632 KB |
subtask1-08.txt | AC | 4 ms | 6016 KB |
subtask1-09.txt | AC | 4 ms | 4992 KB |
subtask1-10.txt | AC | 4 ms | 5888 KB |
subtask1-11.txt | AC | 3 ms | 5120 KB |
subtask1-12.txt | AC | 4 ms | 6016 KB |
subtask1-13.txt | AC | 4 ms | 5248 KB |
subtask1-14.txt | AC | 4 ms | 4736 KB |
subtask1-15.txt | AC | 4 ms | 4608 KB |
subtask1-16.txt | AC | 4 ms | 4992 KB |
subtask1-17.txt | AC | 4 ms | 4992 KB |
subtask1-18.txt | AC | 4 ms | 5888 KB |
subtask1-19.txt | AC | 4 ms | 4736 KB |
subtask1-20.txt | AC | 3 ms | 4608 KB |
subtask2-01.txt | AC | 8 ms | 4992 KB |
subtask2-02.txt | AC | 13 ms | 6528 KB |
subtask2-03.txt | AC | 20 ms | 6144 KB |
subtask2-04.txt | AC | 26 ms | 7040 KB |
subtask2-05.txt | AC | 20 ms | 6784 KB |
subtask2-06.txt | AC | 20 ms | 7040 KB |
subtask2-07.txt | AC | 20 ms | 6912 KB |
subtask2-08.txt | AC | 27 ms | 7296 KB |
subtask2-09.txt | AC | 29 ms | 7296 KB |
subtask2-10.txt | AC | 32 ms | 7296 KB |
subtask2-11.txt | AC | 33 ms | 7168 KB |
subtask2-12.txt | AC | 32 ms | 7296 KB |
subtask2-13.txt | AC | 32 ms | 7296 KB |
subtask2-14.txt | AC | 28 ms | 7168 KB |
subtask2-15.txt | AC | 32 ms | 7296 KB |
subtask2-16.txt | AC | 26 ms | 7168 KB |
subtask2-17.txt | AC | 32 ms | 7168 KB |
subtask2-18.txt | AC | 32 ms | 6528 KB |
subtask2-19.txt | AC | 28 ms | 7296 KB |
subtask2-20.txt | AC | 32 ms | 6528 KB |