oj.uz

Submission #991878

# Submission time Handle Problem Language Result Execution time Memory
991878 2024-06-03T10:15:51 Z thinknoexit Catfish Farm (IOI22_fish) C++17
15 / 100
 909 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] });
                sum += a[i - 1][j];
                dp[0][i][j] = max(dp[0][i][j], mx + sum);
            }
            mx = 0;
            for (int j = c;j >= 0;j--) {
                mx = max({ mx, dp[0][i - 2][j] + sum, dp[1][i - 2][j] + sum });
                sum -= a[i - 1][j];
                dp[0][i][j] = max(dp[0][i][j], mx);
            }
        }
        // (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 10232 KB Output is correct
2 Correct 21 ms 11732 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Runtime error 909 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 0 ms 344 KB Output is correct
2 Correct 33 ms 14576 KB Output is correct
3 Correct 50 ms 16740 KB Output is correct
4 Correct 18 ms 10236 KB Output is correct
5 Correct 21 ms 11616 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 4 ms 9428 KB Output is correct
12 Correct 19 ms 12828 KB Output is correct
13 Correct 24 ms 14540 KB Output is correct
14 Correct 21 ms 12796 KB Output is correct
15 Correct 22 ms 14292 KB Output is correct
16 Correct 20 ms 12884 KB Output is correct
17 Correct 22 ms 14292 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 23 ms 22136 KB Output is correct
3 Correct 29 ms 21080 KB Output is correct
4 Correct 27 ms 20824 KB Output is correct
5 Correct 41 ms 24660 KB Output is correct
6 Correct 36 ms 24664 KB Output is correct
7 Correct 38 ms 24656 KB Output is correct
8 Correct 38 ms 24652 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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 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 1 ms 348 KB Output is correct
2 Correct 23 ms 22136 KB Output is correct
3 Correct 29 ms 21080 KB Output is correct
4 Correct 27 ms 20824 KB Output is correct
5 Correct 41 ms 24660 KB Output is correct
6 Correct 36 ms 24664 KB Output is correct
7 Correct 38 ms 24656 KB Output is correct
8 Correct 38 ms 24652 KB Output is correct
9 Runtime error 887 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 10232 KB Output is correct
2 Correct 21 ms 11732 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Runtime error 909 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -