# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
403561 | 2021-05-13T09:32:17 Z | tqbfjotld | None (KOI17_shell) | C++14 | 296 ms | 39284 KB |
#include <bits/stdc++.h> using namespace std; #define int long long int vals[1505][1505]; int val2[1505][1505]; int num[1505][1505]; set<pair<int,int> > vis; int curans = 0; int n; void decr(int x, int y){ int t=vis.size(); vis.insert({x,y}); if (vis.size()==t) return; val2[x][y]--; curans --; if (x!=n){ if (vals[x+1][y]+max(val2[x][y],y!=1?val2[x+1][y-1]:0)<val2[x+1][y]){ decr(x+1,y); } } if (y!=n){ if (vals[x][y+1]+max(val2[x][y],x!=1?val2[x-1][y+1]:0)<val2[x][y+1]){ decr(x,y+1); } } } main(){ scanf("%lld",&n); if (n<=100){ for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ scanf("%lld",&vals[x][y]); } } for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ if (x==0){ if (y==0) val2[x][y] = vals[x][y]; else val2[x][y] = vals[x][y]+val2[x][y-1]; } else if (y==0){ val2[x][y] = vals[x][y]+val2[x-1][y]; } else{ val2[x][y] = vals[x][y]+max(val2[x-1][y],val2[x][y-1]); } } } for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ curans += val2[x][y]; } } printf("%lld\n",curans); for (int x = 0; x<n; x++){ char c; int a,b; scanf(" %c%lld%lld",&c,&a,&b); if (c=='U'){ vals[a-1][b-1]++; } else{ vals[a-1][b-1]--; } for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ if (x==0){ if (y==0) val2[x][y] = vals[x][y]; else val2[x][y] = vals[x][y]+val2[x][y-1]; } else if (y==0){ val2[x][y] = vals[x][y]+val2[x-1][y]; } else{ val2[x][y] = vals[x][y]+max(val2[x-1][y],val2[x][y-1]); } } } int curans = 0; for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ curans += val2[x][y]; } } printf("%lld\n",curans); } return 0; } for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ scanf("%lld",&vals[x][y]); } } int curans = 0; for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ if (x==0){ if (y==0) val2[x][y] = vals[x][y]; else val2[x][y] = vals[x][y]+val2[x][y-1]; } else if (y==0){ val2[x][y] = vals[x][y]+val2[x-1][y]; } else{ val2[x][y] = vals[x][y]+max(val2[x-1][y],val2[x][y-1]); } curans += val2[x][y]; } } printf("%lld\n",curans); for(int x = 0; x<n; x++){ char c; int a,b; scanf(" %c%lld%lld",&c,&a,&b); vals[a][b]--; vis.clear(); decr(a,b); printf("%lld\n",curans); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1228 KB | Output is correct |
2 | Correct | 8 ms | 1312 KB | Output is correct |
3 | Correct | 7 ms | 1268 KB | Output is correct |
4 | Correct | 7 ms | 1228 KB | Output is correct |
5 | Correct | 7 ms | 1228 KB | Output is correct |
6 | Correct | 9 ms | 1312 KB | Output is correct |
7 | Correct | 8 ms | 1228 KB | Output is correct |
8 | Correct | 8 ms | 1228 KB | Output is correct |
9 | Correct | 7 ms | 1228 KB | Output is correct |
10 | Correct | 7 ms | 1228 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 296 ms | 39284 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1228 KB | Output is correct |
2 | Correct | 8 ms | 1312 KB | Output is correct |
3 | Correct | 7 ms | 1268 KB | Output is correct |
4 | Correct | 7 ms | 1228 KB | Output is correct |
5 | Correct | 7 ms | 1228 KB | Output is correct |
6 | Correct | 9 ms | 1312 KB | Output is correct |
7 | Correct | 8 ms | 1228 KB | Output is correct |
8 | Correct | 8 ms | 1228 KB | Output is correct |
9 | Correct | 7 ms | 1228 KB | Output is correct |
10 | Incorrect | 296 ms | 39284 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |