oj.uz

Submission #172319

# Submission time Handle Problem Language Result Execution time Memory
172319 2020-01-01T07:44:08 Z ho94949 Abduction 2 (JOI17_abduction2) C++17
27 / 100
 199 ms 65028 KB 
#include<bits/stdc++.h>
using namespace std;

enum {UP, LEFT, DOWN, RIGHT};
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int MAXN = 2020;
int H, W, Q;
int A[MAXN], B[MAXN];
int dp[MAXN][MAXN][4];
bool ins(int x, int y){ return 0<=x&&x<H&&0<=y&&y<W; }
int solve(int x, int y, int d)
{
    if(dp[x][y][d] != -1) return dp[x][y][d];
    
    int nx = x+dx[d], ny = y+dy[d];
    if(!ins(nx, ny)) return dp[x][y][d] = 0;

    if(d==UP||d==DOWN)
    {
        if(A[nx]<B[ny]) return dp[x][y][d] = 1+solve(nx, ny, d);
        else return dp[x][y][d] = 1+max(solve(nx, ny, LEFT), solve(nx, ny, RIGHT));
    }
    else
    {
        if(B[ny]<A[nx]) return dp[x][y][d] = 1+solve(nx, ny, d);
        else return dp[x][y][d] = 1+max(solve(nx, ny, UP), solve(nx, ny, DOWN));
    }
}
int main()
{
    memset(dp, -1, sizeof dp);
    scanf("%d%d%d", &H, &W, &Q);
    for(int i=0; i<H; ++i)
        scanf("%d", A+i);
    for(int i=0; i<W; ++i)
        scanf("%d", B+i);
    while(Q--)
    {
        int S, T; scanf("%d%d", &S, &T); --S; --T;
        int ans = 0;
        for(int d=0; d<4; ++d)
            ans = max(ans, solve(S, T, d));
        printf("%d\n", ans);
    }
}

Compilation message

abduction2.cpp: In function 'int main()':
abduction2.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &H, &W, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
         ~~~~~^~~~~~~~~~~
abduction2.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", B+i);
         ~~~~~^~~~~~~~~~~
abduction2.cpp:40:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int S, T; scanf("%d%d", &S, &T); --S; --T;
                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 64376 KB Output is correct
2 Correct 55 ms 64376 KB Output is correct
3 Correct 55 ms 64248 KB Output is correct
4 Correct 63 ms 64248 KB Output is correct
5 Correct 55 ms 64220 KB Output is correct
6 Correct 56 ms 64248 KB Output is correct
7 Correct 56 ms 64248 KB Output is correct
8 Correct 56 ms 64248 KB Output is correct
9 Correct 55 ms 64248 KB Output is correct
10 Correct 55 ms 64248 KB Output is correct
11 Correct 55 ms 64248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 64376 KB Output is correct
2 Correct 55 ms 64376 KB Output is correct
3 Correct 55 ms 64248 KB Output is correct
4 Correct 63 ms 64248 KB Output is correct
5 Correct 55 ms 64220 KB Output is correct
6 Correct 56 ms 64248 KB Output is correct
7 Correct 56 ms 64248 KB Output is correct
8 Correct 56 ms 64248 KB Output is correct
9 Correct 55 ms 64248 KB Output is correct
10 Correct 55 ms 64248 KB Output is correct
11 Correct 55 ms 64248 KB Output is correct
12 Correct 56 ms 64356 KB Output is correct
13 Correct 56 ms 64476 KB Output is correct
14 Correct 57 ms 64376 KB Output is correct
15 Correct 58 ms 64428 KB Output is correct
16 Correct 56 ms 64328 KB Output is correct
17 Correct 62 ms 64512 KB Output is correct
18 Correct 67 ms 64436 KB Output is correct
19 Correct 123 ms 64888 KB Output is correct
20 Correct 138 ms 64888 KB Output is correct
21 Correct 128 ms 64888 KB Output is correct
22 Correct 188 ms 64988 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 64376 KB Output is correct
2 Correct 55 ms 64376 KB Output is correct
3 Correct 55 ms 64248 KB Output is correct
4 Correct 63 ms 64248 KB Output is correct
5 Correct 55 ms 64220 KB Output is correct
6 Correct 56 ms 64248 KB Output is correct
7 Correct 56 ms 64248 KB Output is correct
8 Correct 56 ms 64248 KB Output is correct
9 Correct 55 ms 64248 KB Output is correct
10 Correct 55 ms 64248 KB Output is correct
11 Correct 55 ms 64248 KB Output is correct
12 Correct 56 ms 64356 KB Output is correct
13 Correct 56 ms 64476 KB Output is correct
14 Correct 57 ms 64376 KB Output is correct
15 Correct 58 ms 64428 KB Output is correct
16 Correct 56 ms 64328 KB Output is correct
17 Correct 62 ms 64512 KB Output is correct
18 Correct 67 ms 64436 KB Output is correct
19 Correct 123 ms 64888 KB Output is correct
20 Correct 138 ms 64888 KB Output is correct
21 Correct 128 ms 64888 KB Output is correct
22 Correct 188 ms 64988 KB Output is correct
23 Execution timed out 56 ms 64612 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 60 ms 64376 KB Output is correct
2 Correct 59 ms 64780 KB Output is correct
3 Correct 60 ms 64476 KB Output is correct
4 Correct 59 ms 64504 KB Output is correct
5 Correct 61 ms 64512 KB Output is correct
6 Correct 112 ms 64504 KB Output is correct
7 Correct 112 ms 64504 KB Output is correct
8 Correct 156 ms 64888 KB Output is correct
9 Correct 151 ms 64888 KB Output is correct
10 Correct 154 ms 65028 KB Output is correct
11 Correct 199 ms 64988 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 64376 KB Output is correct
2 Correct 55 ms 64376 KB Output is correct
3 Correct 55 ms 64248 KB Output is correct
4 Correct 63 ms 64248 KB Output is correct
5 Correct 55 ms 64220 KB Output is correct
6 Correct 56 ms 64248 KB Output is correct
7 Correct 56 ms 64248 KB Output is correct
8 Correct 56 ms 64248 KB Output is correct
9 Correct 55 ms 64248 KB Output is correct
10 Correct 55 ms 64248 KB Output is correct
11 Correct 55 ms 64248 KB Output is correct
12 Correct 56 ms 64356 KB Output is correct
13 Correct 56 ms 64476 KB Output is correct
14 Correct 57 ms 64376 KB Output is correct
15 Correct 58 ms 64428 KB Output is correct
16 Correct 56 ms 64328 KB Output is correct
17 Correct 62 ms 64512 KB Output is correct
18 Correct 67 ms 64436 KB Output is correct
19 Correct 123 ms 64888 KB Output is correct
20 Correct 138 ms 64888 KB Output is correct
21 Correct 128 ms 64888 KB Output is correct
22 Correct 188 ms 64988 KB Output is correct
23 Execution timed out 56 ms 64612 KB Time limit exceeded (wall clock)
24 Halted 0 ms 0 KB -