oj.uz

Submission #403503

# Submission time Handle Problem Language Result Execution time Memory
403503 2021-05-13T08:51:15 Z zaneyu None (KOI17_shell) C++14
46 / 100
 1946 ms 153540 KB 
/*input
3

1 0 0 
1 1 0
0 0 0

D 1 1

D 2 1

D 2 2
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define pb push_back
#define ALL(x) x.begin(),x.end()
const int maxn=1500+5;
int dp[maxn][maxn];
int arr[maxn][maxn];
int n;
vector<int> v[maxn*maxn];
ll ans=0;
void calc2(){
    REP1(i,n){
        REP1(j,n){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];
            ans+=dp[i][j];

            if(dp[i][j]==dp[i-1][j]+arr[i][j]){
                //cout<<(i-1)*(n+1)+j<<' '<<i*(n+1)+j<<'\n';
                v[(i-1)*(n+1)+j].pb(i*(n+1)+j);
            }
            if(dp[i][j]==dp[i][j-1]+arr[i][j]){
                v[i*(n+1)+j-1].pb(i*(n+1)+j);
            }
        }
    }
    cout<<ans<<'\n';
}
bool vis[maxn*maxn];
int vs[maxn*maxn];
int ptr=0;
inline void dfs(int u){
    vis[u]=1;
    vs[ptr++]=u;
    for(int x:v[u]){
        if(!vis[x]){
            int i=x/(n+1),j=x%(n+1);
            int pv=dp[i][j];
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];
            if(dp[i][j]!=pv){
                dfs(x);
            }
            ans+=dp[i][j]-pv;
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    REP1(i,n) REP1(j,n) cin>>arr[i][j];
    if(n<=100){
        calc2();
        REP(i,n){
            char c;
            int x,y;
            cin>>c>>x>>y;
            if(c=='U') arr[x][y]++;
            else arr[x][y]--;
            ans=0;
            calc2();
        }
        return 0;
    }
    calc2();

    REP(i,n){
        char c;
        int x,y;
        cin>>c>>x>>y;
        if(c=='U') arr[x][y]++;
        else arr[x][y]--;
        dp[x][y]--,ans--;
        dfs(x*(n+1)+y);
        REP(asd,ptr){
            int z=vs[asd];
            int i=z/(n+1),j=z%(n+1);
            if(find(ALL(v[i*(n+1)+j-1]),z)!=v[i*(n+1)+j-1].end()) v[i*(n+1)+j-1].erase(find(ALL(v[i*(n+1)+j-1]),z));
            if(find(ALL(v[(i-1)*(n+1)+j]),z)!=v[(i-1)*(n+1)+j].end()) v[(i-1)*(n+1)+j].erase(find(ALL(v[(i-1)*(n+1)+j]),z));
            if(dp[i][j]==dp[i-1][j]+arr[i][j]){
                v[(i-1)*(n+1)+j].pb(z);
            }
            if(dp[i][j]==dp[i][j-1]+arr[i][j]){
                v[i*(n+1)+j-1].pb(z);
            }
            vis[z]=0;
        }
        ptr=0;
        /*REP1(i,(n+1)*(n+1)){
            for(auto x:v[i]) cout<<i<<' '<<x<<'\n';
        }
        REP1(i,n){
            REP1(j,n) cout<<dp[i][j]<<' ';
            cout<<'\n';
        }*/
        cout<<ans<<'\n';
    }
}
/*
107
3 4 11 
7 9 17 
12 15 25 
103
2 3 10 
7 9 16 
12 15 24 
98
2 3 10 
7 8 16 
12 15 24 
97
[Finished in 2.5s]
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 59684 KB Output is correct
2 Correct 49 ms 59716 KB Output is correct
3 Correct 51 ms 59856 KB Output is correct
4 Correct 51 ms 59736 KB Output is correct
5 Correct 50 ms 59716 KB Output is correct
6 Correct 49 ms 59716 KB Output is correct
7 Correct 56 ms 62140 KB Output is correct
8 Correct 55 ms 62248 KB Output is correct
9 Correct 92 ms 62188 KB Output is correct
10 Correct 50 ms 59768 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 143428 KB Output is correct
2 Correct 574 ms 143424 KB Output is correct
3 Correct 1946 ms 153540 KB Output is correct
4 Correct 454 ms 143348 KB Output is correct
5 Correct 451 ms 143480 KB Output is correct
6 Correct 575 ms 143536 KB Output is correct
7 Correct 565 ms 143444 KB Output is correct
8 Correct 457 ms 143444 KB Output is correct
9 Correct 418 ms 143300 KB Output is correct
10 Correct 420 ms 143272 KB Output is correct

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 59684 KB Output is correct
2 Correct 49 ms 59716 KB Output is correct
3 Correct 51 ms 59856 KB Output is correct
4 Correct 51 ms 59736 KB Output is correct
5 Correct 50 ms 59716 KB Output is correct
6 Correct 49 ms 59716 KB Output is correct
7 Correct 56 ms 62140 KB Output is correct
8 Correct 55 ms 62248 KB Output is correct
9 Correct 92 ms 62188 KB Output is correct
10 Correct 582 ms 143428 KB Output is correct
11 Correct 574 ms 143424 KB Output is correct
12 Correct 1946 ms 153540 KB Output is correct
13 Correct 454 ms 143348 KB Output is correct
14 Correct 451 ms 143480 KB Output is correct
15 Correct 575 ms 143536 KB Output is correct
16 Correct 565 ms 143444 KB Output is correct
17 Correct 457 ms 143444 KB Output is correct
18 Correct 418 ms 143300 KB Output is correct
19 Correct 420 ms 143272 KB Output is correct
20 Correct 50 ms 59768 KB Output is correct
21 Incorrect 495 ms 128244 KB Output isn't correct
22 Halted 0 ms 0 KB -