oj.uz

Submission #991871

# Submission time Handle Problem Language Result Execution time Memory
991871 2024-06-03T10:03:05 Z thinknoexit Catfish Farm (IOI22_fish) C++17
15 / 100
 939 ms 2097152 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
int n, m;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N, m = M;
    int r = 0, c = 0;
    for (int i = 0;i < m;i++) {
        r = max(r, X[i] + 1);
        c = max(c, Y[i] + 1);
    }
    c++;
    r = min(n, r + 1);
    vector<vector<int>> a(r + 1, vector<int>(c + 1, 0));
    vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(r + 1, vector<ll>(c + 1, 0ll)));
    for (int i = 0;i < m;i++) {
        a[X[i] + 1][Y[i] + 1] = W[i];
    }
    ll mx;
    for (int i = 2;i <= r;i++) {
        // (0)
        mx = 0;
        for (int j = 0;j <= c;j++) {
            mx = max(mx + a[i - 1][j], dp[0][i - 1][j]);
            dp[0][i][j] = mx;
        }
        if (i >= 3) { // i - 2
            ll sum = 0;
            mx = 0;
            for (int j = 0;j <= c;j++) {
                mx = max({ mx, dp[0][i - 2][j], dp[1][i - 2][j] }) + a[i - 1][j];
                sum += a[i - 1][j];
                dp[0][i][j] = max(dp[0][i][j], mx);
            }
            mx = 0;
            for (int j = c;j >= 0;j--) {
                mx = max({ mx, max(dp[0][i - 2][j], dp[1][i - 2][j]) + sum });
                dp[0][i][j] = max(dp[0][i][j], mx);
                sum -= a[i - 1][j];
            }
        }
        // (1)
        mx = 0;
        for (int j = c;j >= 0;j--) {
            dp[1][i][j] = mx;
            mx = max({ mx + a[i][j], dp[0][i - 1][j], dp[1][i - 1][j] });
        }
    }
    ll ans = 0;
    for (int i = 1;i <= r;i++) {
        for (int j = 0;j <= c;j++) {
            ans = max({ ans, dp[0][i][j], dp[1][i][j] });
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10236 KB Output is correct
2 Correct 21 ms 11728 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 9428 KB Output is correct
5 Runtime error 939 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 34 ms 16156 KB Output is correct
3 Correct 44 ms 20268 KB Output is correct
4 Correct 18 ms 11648 KB Output is correct
5 Correct 23 ms 13360 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 9264 KB Output is correct
12 Correct 22 ms 14332 KB Output is correct
13 Correct 24 ms 16280 KB Output is correct
14 Correct 21 ms 14320 KB Output is correct
15 Correct 24 ms 15828 KB Output is correct
16 Correct 26 ms 14320 KB Output is correct
17 Correct 23 ms 15816 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 21 ms 22364 KB Output is correct
3 Correct 27 ms 22056 KB Output is correct
4 Correct 28 ms 21596 KB Output is correct
5 Correct 44 ms 26288 KB Output is correct
6 Correct 48 ms 25496 KB Output is correct
7 Correct 41 ms 26104 KB Output is correct
8 Correct 45 ms 26196 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 21 ms 22364 KB Output is correct
3 Correct 27 ms 22056 KB Output is correct
4 Correct 28 ms 21596 KB Output is correct
5 Correct 44 ms 26288 KB Output is correct
6 Correct 48 ms 25496 KB Output is correct
7 Correct 41 ms 26104 KB Output is correct
8 Correct 45 ms 26196 KB Output is correct
9 Runtime error 853 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10236 KB Output is correct
2 Correct 21 ms 11728 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 9428 KB Output is correct
5 Runtime error 939 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -