# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
901670 | 2024-01-09T22:25:59 Z | alexander707070 | Misspelling (JOI22_misspelling) | C++14 | 4000 ms | 8408 KB |
#include<bits/stdc++.h> #define MAXN 20007 using namespace std; const int mod=1e9+7; int n,m,a,b,ans; int dp[MAXN][30]; int es[MAXN],es2[MAXN]; bool bad[MAXN],bad2[MAXN]; int pt,pt2; int sum[30],sum2[30]; void calc_dp(){ pt=pt2=n+1; for(int pos=n;pos>=1;pos--){ for(int f=pos+1;f<=es[pos];f++){ for(int letter=0;letter<26;letter++){ if(!bad[f])sum[letter]-=dp[f][letter]; sum[letter]+=mod; sum[letter]%=mod; } bad[f]=true; } for(int f=pos+1;f<=es2[pos];f++){ for(int letter=0;letter<26;letter++){ if(!bad2[f])sum2[letter]-=dp[f][letter]; sum2[letter]+=mod; sum2[letter]%=mod; } bad2[f]=true; } if(es[pos]>=pos+1)pt=pos+1; if(es2[pos]>=pos+1)pt2=pos+1; for(int letter=0;letter<26;letter++){ dp[pos][letter]=1; for(int nxtletter=0;nxtletter<26;nxtletter++){ if(nxtletter==letter)continue; if(nxtletter<letter)dp[pos][letter]+=sum[nxtletter]; if(nxtletter>letter)dp[pos][letter]+=sum2[nxtletter]; dp[pos][letter]%=mod; } } for(int letter=0;letter<26;letter++){ sum[letter]+=dp[pos][letter]; sum[letter]%=mod; sum2[letter]+=dp[pos][letter]; sum2[letter]%=mod; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a>>b; if(a<b){ es[a]=max(es[a],b); }else{ es2[b]=max(es2[b],a); } } calc_dp(); for(int i=0;i<26;i++){ ans+=dp[1][i]; ans%=mod; } cout<<ans<<"\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 0 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 1 ms | 2392 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 0 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 1 ms | 2392 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 2 ms | 2392 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 2 ms | 2396 KB | Output is correct |
22 | Correct | 3 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
2 | Correct | 0 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2392 KB | Output is correct |
4 | Correct | 0 ms | 2396 KB | Output is correct |
5 | Runtime error | 59 ms | 4692 KB | Execution killed with signal 11 |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 0 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 1 ms | 2392 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 2 ms | 2392 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 2 ms | 2396 KB | Output is correct |
22 | Correct | 3 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
26 | Correct | 45 ms | 2900 KB | Output is correct |
27 | Correct | 1762 ms | 3136 KB | Output is correct |
28 | Correct | 1785 ms | 2976 KB | Output is correct |
29 | Correct | 2100 ms | 3012 KB | Output is correct |
30 | Correct | 2050 ms | 3584 KB | Output is correct |
31 | Correct | 3003 ms | 8408 KB | Output is correct |
32 | Correct | 49 ms | 3152 KB | Output is correct |
33 | Correct | 46 ms | 2996 KB | Output is correct |
34 | Correct | 3682 ms | 3016 KB | Output is correct |
35 | Execution timed out | 4042 ms | 7248 KB | Time limit exceeded |
36 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2396 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 1 ms | 2396 KB | Output is correct |
6 | Correct | 1 ms | 2396 KB | Output is correct |
7 | Correct | 0 ms | 2396 KB | Output is correct |
8 | Correct | 0 ms | 2396 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 0 ms | 2396 KB | Output is correct |
12 | Correct | 1 ms | 2392 KB | Output is correct |
13 | Correct | 1 ms | 2396 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |
16 | Correct | 1 ms | 2396 KB | Output is correct |
17 | Correct | 1 ms | 2396 KB | Output is correct |
18 | Correct | 2 ms | 2392 KB | Output is correct |
19 | Correct | 1 ms | 2396 KB | Output is correct |
20 | Correct | 1 ms | 2396 KB | Output is correct |
21 | Correct | 2 ms | 2396 KB | Output is correct |
22 | Correct | 3 ms | 2396 KB | Output is correct |
23 | Correct | 1 ms | 2396 KB | Output is correct |
24 | Correct | 1 ms | 2396 KB | Output is correct |
25 | Correct | 1 ms | 2396 KB | Output is correct |
26 | Correct | 1 ms | 2396 KB | Output is correct |
27 | Correct | 0 ms | 2396 KB | Output is correct |
28 | Correct | 1 ms | 2392 KB | Output is correct |
29 | Correct | 0 ms | 2396 KB | Output is correct |
30 | Runtime error | 59 ms | 4692 KB | Execution killed with signal 11 |
31 | Halted | 0 ms | 0 KB | - |