oj.uz

답안 #403569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403569 2021-05-13T09:38:23 Z tqbfjotld 조개 줍기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -