oj.uz

Submission #883174

# Submission time Handle Problem Language Result Execution time Memory
883174 2023-12-04T17:13:48 Z DAleksa Abduction 2 (JOI17_abduction2) C++17
27 / 100
 443 ms 303720 KB 
#include <bits/stdc++.h>

using namespace std;

struct node {
    int v;
    int w;
};

const int N = 2010;
int n, m, q;
int a[N], b[N];

int f(int i, int j) { return (i - 1) * N + (j - 1); }
vector<node> g[N * N];
const int END = N * N - 1;
int dp[N * N];
bool mark[N * N];
int L[N][N], R[N][N], U[N][N], D[N][N];

void dfs(int u) {
    mark[u] = true;
    for(node v : g[u]) {
        if(!mark[v.v]) dfs(v.v);
        dp[u] = max(dp[u], dp[v.v] + v.w);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) {
        int lst = 0;
        for(int j = 1; j <= m; j++) {
            L[i][j] = lst;
            if(a[i] < b[j]) lst = j;
        }
        lst = m + 1;
        for(int j = m; j >= 1; j--) {
            R[i][j] = lst;
            if(a[i] < b[j]) lst = j;
        }
    }
    for(int j = 1; j <= m; j++) {
        int lst = 0;
        for(int i = 1; i <= n; i++) {
            U[i][j] = lst;
            if(a[i] > b[j]) lst = i;
        }
        lst = n + 1;
        for(int i = n; i >= 1; i--) {
            D[i][j] = lst;
            if(a[i] > b[j]) lst = i;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i] < b[j]) {
                if(U[i][j] != 0) g[f(i, j)].push_back({f(U[i][j], j), i - U[i][j]});
                else g[f(i, j)].push_back({END, i - 1});
                if(D[i][j] != n + 1) g[f(i, j)].push_back({f(D[i][j], j), D[i][j] - i});
                else g[f(i, j)].push_back({END, n - i});
            } else {
                if(L[i][j] != 0) g[f(i, j)].push_back({f(i, L[i][j]), j - L[i][j]});
                else g[f(i, j)].push_back({END, j - 1});
                if(R[i][j] != m + 1) g[f(i, j)].push_back({f(i, R[i][j]), R[i][j] - j});
                else g[f(i, j)].push_back({END, m - j});
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mark[f(i, j)]) continue;
            dfs(f(i, j));
        }
    }
//    for(int i = 1; i <= n; i++) {
//        for(int j = 1; j <= m; j++) {
//            cout << i << " " << j << ": " << dp[f(i, j)] << "\n";
//        }
//    }
    while(q--) {
        int x, y;
        cin >> x >> y;
        int ans = 0;
        ans = max(ans, (L[x][y] == 0 ? -1 : dp[f(x, L[x][y])]) + y - L[x][y]);
        ans = max(ans, (R[x][y] == m + 1 ? -1 : dp[f(x, R[x][y])]) + R[x][y] - y);
        ans = max(ans, (U[x][y] == 0 ? -1 : dp[f(U[x][y], y)]) + x - U[x][y]);
        ans = max(ans, (D[x][y] == n + 1 ? -1 : dp[f(D[x][y], y)]) + D[x][y] - x);
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 102236 KB Output is correct
2 Correct 23 ms 102468 KB Output is correct
3 Correct 22 ms 102236 KB Output is correct
4 Correct 25 ms 102236 KB Output is correct
5 Correct 21 ms 102228 KB Output is correct
6 Correct 24 ms 102340 KB Output is correct
7 Correct 23 ms 102236 KB Output is correct
8 Correct 21 ms 102324 KB Output is correct
9 Correct 21 ms 102240 KB Output is correct
10 Correct 21 ms 102236 KB Output is correct
11 Correct 22 ms 102236 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 102236 KB Output is correct
2 Correct 23 ms 102468 KB Output is correct
3 Correct 22 ms 102236 KB Output is correct
4 Correct 25 ms 102236 KB Output is correct
5 Correct 21 ms 102228 KB Output is correct
6 Correct 24 ms 102340 KB Output is correct
7 Correct 23 ms 102236 KB Output is correct
8 Correct 21 ms 102324 KB Output is correct
9 Correct 21 ms 102240 KB Output is correct
10 Correct 21 ms 102236 KB Output is correct
11 Correct 22 ms 102236 KB Output is correct
12 Correct 441 ms 303416 KB Output is correct
13 Correct 411 ms 303444 KB Output is correct
14 Correct 410 ms 303444 KB Output is correct
15 Correct 410 ms 303400 KB Output is correct
16 Correct 424 ms 303720 KB Output is correct
17 Correct 375 ms 303684 KB Output is correct
18 Correct 368 ms 303692 KB Output is correct
19 Correct 394 ms 303600 KB Output is correct
20 Correct 385 ms 299604 KB Output is correct
21 Correct 387 ms 301176 KB Output is correct
22 Correct 391 ms 303604 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 102236 KB Output is correct
2 Correct 23 ms 102468 KB Output is correct
3 Correct 22 ms 102236 KB Output is correct
4 Correct 25 ms 102236 KB Output is correct
5 Correct 21 ms 102228 KB Output is correct
6 Correct 24 ms 102340 KB Output is correct
7 Correct 23 ms 102236 KB Output is correct
8 Correct 21 ms 102324 KB Output is correct
9 Correct 21 ms 102240 KB Output is correct
10 Correct 21 ms 102236 KB Output is correct
11 Correct 22 ms 102236 KB Output is correct
12 Correct 441 ms 303416 KB Output is correct
13 Correct 411 ms 303444 KB Output is correct
14 Correct 410 ms 303444 KB Output is correct
15 Correct 410 ms 303400 KB Output is correct
16 Correct 424 ms 303720 KB Output is correct
17 Correct 375 ms 303684 KB Output is correct
18 Correct 368 ms 303692 KB Output is correct
19 Correct 394 ms 303600 KB Output is correct
20 Correct 385 ms 299604 KB Output is correct
21 Correct 387 ms 301176 KB Output is correct
22 Correct 391 ms 303604 KB Output is correct
23 Runtime error 105 ms 194468 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 303380 KB Output is correct
2 Correct 415 ms 303460 KB Output is correct
3 Correct 419 ms 303364 KB Output is correct
4 Correct 407 ms 303408 KB Output is correct
5 Correct 443 ms 303604 KB Output is correct
6 Correct 370 ms 303484 KB Output is correct
7 Correct 368 ms 303700 KB Output is correct
8 Correct 382 ms 303524 KB Output is correct
9 Correct 392 ms 301276 KB Output is correct
10 Correct 394 ms 302912 KB Output is correct
11 Correct 392 ms 303560 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 102236 KB Output is correct
2 Correct 23 ms 102468 KB Output is correct
3 Correct 22 ms 102236 KB Output is correct
4 Correct 25 ms 102236 KB Output is correct
5 Correct 21 ms 102228 KB Output is correct
6 Correct 24 ms 102340 KB Output is correct
7 Correct 23 ms 102236 KB Output is correct
8 Correct 21 ms 102324 KB Output is correct
9 Correct 21 ms 102240 KB Output is correct
10 Correct 21 ms 102236 KB Output is correct
11 Correct 22 ms 102236 KB Output is correct
12 Correct 441 ms 303416 KB Output is correct
13 Correct 411 ms 303444 KB Output is correct
14 Correct 410 ms 303444 KB Output is correct
15 Correct 410 ms 303400 KB Output is correct
16 Correct 424 ms 303720 KB Output is correct
17 Correct 375 ms 303684 KB Output is correct
18 Correct 368 ms 303692 KB Output is correct
19 Correct 394 ms 303600 KB Output is correct
20 Correct 385 ms 299604 KB Output is correct
21 Correct 387 ms 301176 KB Output is correct
22 Correct 391 ms 303604 KB Output is correct
23 Runtime error 105 ms 194468 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -