oj.uz

Submission #282214

# Submission time Handle Problem Language Result Execution time Memory
282214 2020-08-24T06:55:09 Z 반딧불(#5757) Abduction 2 (JOI17_abduction2) C++17
27 / 100
 345 ms 126328 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, q;
int arr1[2002], arr2[2002];
ll DP[2002][2002][4];

/// ����: 0: up, 1: right, 2: down, 3: left
ll getAns(int x, int y, int d){
    if(DP[x][y][d] != -1) return DP[x][y][d];
    switch(d){
    case 0: /// ���� ����. tree1���� ���� �۾��� �ʿ��ϴ�.
        if(x==1){
            DP[x][y][d] = 0;
            break;
        }
        if(arr2[y] < arr1[x-1]) DP[x][y][d] = max(getAns(x-1, y, 1), getAns(x-1, y, 3)) + 1;
        else DP[x][y][d] = getAns(x-1, y, d) + 1;
        break;
    case 1: /// ������.
        if(y==m){
            DP[x][y][d] = 0;
            break;
        }
        if(arr1[x] < arr2[y+1]) DP[x][y][d] = max(getAns(x, y+1, 0), getAns(x, y+1, 2)) + 1;
        else DP[x][y][d] = getAns(x, y+1, d) + 1;
        break;
    case 2: /// �Ʒ���.
        if(x==n){
            DP[x][y][d] = 0;
            break;
        }
        if(arr2[y] < arr1[x+1]) DP[x][y][d] = max(getAns(x+1, y, 1), getAns(x+1, y, 3)) + 1;
        else DP[x][y][d] = getAns(x+1, y, d) + 1;
        break;
    case 3:
        if(y==1){
            DP[x][y][d] = 0;
            break;
        }
        if(arr1[x] < arr2[y-1]) DP[x][y][d] = max(getAns(x, y-1, 0), getAns(x, y-1, 2)) + 1;
        else DP[x][y][d] = getAns(x, y-1, d) + 1;
        break;
    }
    return DP[x][y][d];
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr1[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%d", &arr2[i]);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int d=0; d<4; d++){
                DP[i][j][d] = -1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int d=0; d<4; d++){
                getAns(i, j, d);
            }
        }
    }

    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        ll ans = 0;
        for(int d=0; d<4; d++){
            ans = max(ans, getAns(x, y, d));
        }
        printf("%lld\n", ans);
    }
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         scanf("%d", &arr1[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         scanf("%d", &arr2[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 290 ms 125944 KB Output is correct
13 Correct 294 ms 126072 KB Output is correct
14 Correct 290 ms 125944 KB Output is correct
15 Correct 301 ms 125944 KB Output is correct
16 Correct 291 ms 125944 KB Output is correct
17 Correct 293 ms 126152 KB Output is correct
18 Correct 297 ms 126072 KB Output is correct
19 Correct 314 ms 126328 KB Output is correct
20 Correct 305 ms 122360 KB Output is correct
21 Correct 312 ms 126204 KB Output is correct
22 Correct 322 ms 126276 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 290 ms 125944 KB Output is correct
13 Correct 294 ms 126072 KB Output is correct
14 Correct 290 ms 125944 KB Output is correct
15 Correct 301 ms 125944 KB Output is correct
16 Correct 291 ms 125944 KB Output is correct
17 Correct 293 ms 126152 KB Output is correct
18 Correct 297 ms 126072 KB Output is correct
19 Correct 314 ms 126328 KB Output is correct
20 Correct 305 ms 122360 KB Output is correct
21 Correct 312 ms 126204 KB Output is correct
22 Correct 322 ms 126276 KB Output is correct
23 Execution timed out 2 ms 384 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 125944 KB Output is correct
2 Correct 308 ms 125944 KB Output is correct
3 Correct 304 ms 125944 KB Output is correct
4 Correct 300 ms 125944 KB Output is correct
5 Correct 292 ms 125944 KB Output is correct
6 Correct 294 ms 126072 KB Output is correct
7 Correct 288 ms 126072 KB Output is correct
8 Correct 308 ms 126200 KB Output is correct
9 Correct 309 ms 124240 KB Output is correct
10 Correct 321 ms 126200 KB Output is correct
11 Correct 345 ms 126200 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 290 ms 125944 KB Output is correct
13 Correct 294 ms 126072 KB Output is correct
14 Correct 290 ms 125944 KB Output is correct
15 Correct 301 ms 125944 KB Output is correct
16 Correct 291 ms 125944 KB Output is correct
17 Correct 293 ms 126152 KB Output is correct
18 Correct 297 ms 126072 KB Output is correct
19 Correct 314 ms 126328 KB Output is correct
20 Correct 305 ms 122360 KB Output is correct
21 Correct 312 ms 126204 KB Output is correct
22 Correct 322 ms 126276 KB Output is correct
23 Execution timed out 2 ms 384 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -