oj.uz

Submission #403569

# Submission time Handle Problem Language Result Execution time Memory
403569 2021-05-13T09:38:23 Z tqbfjotld None (KOI17_shell) C++14
12 / 100
 2000 ms 169520 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 = 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]--;
        vis.clear();
        decr(a,b);
        printf("%lld\n",curans);
    }
}

Compilation message

shell.cpp: In function 'void decr(long long int, long long int)':
shell.cpp:16:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   16 |     if (vis.size()==t) return;
      |         ~~~~~~~~~~^~~
shell.cpp: At global scope:
shell.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main(){
      | ^~~~
shell.cpp: In function 'int main()':
shell.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
shell.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |                 scanf("%lld",&vals[x][y]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~
shell.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |             scanf(" %c%lld%lld",&c,&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%lld",&vals[x][y]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
shell.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         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 9 ms 1272 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 7 ms 1272 KB Output is correct
8 Correct 7 ms 1228 KB Output is correct
9 Correct 7 ms 1228 KB Output is correct
10 Correct 7 ms 1228 KB Output is correct

Subtask #2
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 37004 KB Output is correct
2 Correct 565 ms 39380 KB Output is correct
3 Execution timed out 2041 ms 169520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1228 KB Output is correct
2 Correct 9 ms 1272 KB Output is correct
3 Correct 7 ms 1228 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 7 ms 1272 KB Output is correct
8 Correct 7 ms 1228 KB Output is correct
9 Correct 7 ms 1228 KB Output is correct
10 Correct 524 ms 37004 KB Output is correct
11 Correct 565 ms 39380 KB Output is correct
12 Execution timed out 2041 ms 169520 KB Time limit exceeded
13 Halted 0 ms 0 KB -