oj.uz

Submission #403574

# Submission time Handle Problem Language Result Execution time Memory
403574 2021-05-13T09:40:48 Z tqbfjotld None (KOI17_shell) C++14
46 / 100
 1033 ms 103752 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int vals[1505][1505];
int val2[1505][1505];
int num[1505][1505];

vector<pair<int,int> > vis;
bool vis2[1505][1505];
int curans = 0;
int n;

void decr(int x, int y){
    if (vis2[x][y]) return;
    vis.push_back({x,y});
    vis2[x][y] = true;
    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 = 1; x<=n; x++){
        for (int y = 1; y<=n; y++){
            scanf("%lld",&vals[x][y]);
        }
    }
    for (int x = 1; x<=n; x++){
        for (int y = 1; y<=n; y++){
            if (x==1){
                if (y==1) val2[x][y] = vals[x][y];
                else val2[x][y] = vals[x][y]+val2[x][y-1];
            }
            else if (y==1){
                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]--;
        for (auto y : vis){
            vis2[y.first][y.second] = false;
        }
        vis.clear();
        decr(a,b);
        printf("%lld\n",curans);
    }
}

Compilation message

shell.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~
shell.cpp: In function 'int main()':
shell.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
shell.cpp:37:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |                 scanf("%lld",&vals[x][y]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~
shell.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf(" %c%lld%lld",&c,&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |             scanf("%lld",&vals[x][y]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
shell.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf(" %c%lld%lld",&c,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1228 KB Output is correct
2 Correct 7 ms 1268 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 7 ms 1260 KB Output is correct
7 Correct 7 ms 1228 KB Output is correct
8 Correct 8 ms 1228 KB Output is correct
9 Correct 8 ms 1228 KB Output is correct
10 Correct 7 ms 1228 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 36860 KB Output is correct
2 Correct 255 ms 36732 KB Output is correct
3 Correct 1033 ms 103752 KB Output is correct
4 Correct 218 ms 38564 KB Output is correct
5 Correct 218 ms 38520 KB Output is correct
6 Correct 262 ms 39004 KB Output is correct
7 Correct 308 ms 39108 KB Output is correct
8 Correct 216 ms 38356 KB Output is correct
9 Correct 217 ms 38596 KB Output is correct
10 Correct 216 ms 38488 KB Output is correct

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1228 KB Output is correct
2 Correct 7 ms 1268 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Correct 8 ms 1260 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 7 ms 1260 KB Output is correct
7 Correct 7 ms 1228 KB Output is correct
8 Correct 8 ms 1228 KB Output is correct
9 Correct 8 ms 1228 KB Output is correct
10 Correct 256 ms 36860 KB Output is correct
11 Correct 255 ms 36732 KB Output is correct
12 Correct 1033 ms 103752 KB Output is correct
13 Correct 218 ms 38564 KB Output is correct
14 Correct 218 ms 38520 KB Output is correct
15 Correct 262 ms 39004 KB Output is correct
16 Correct 308 ms 39108 KB Output is correct
17 Correct 216 ms 38356 KB Output is correct
18 Correct 217 ms 38596 KB Output is correct
19 Correct 216 ms 38488 KB Output is correct
20 Correct 7 ms 1228 KB Output is correct
21 Incorrect 272 ms 43980 KB Output isn't correct
22 Halted 0 ms 0 KB -