oj.uz

Submission #834732

# Submission time Handle Problem Language Result Execution time Memory
834732 2023-08-22T17:56:55 Z tengiz05 Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 436924 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 3000;
constexpr i64 inf = 1E18;

i64 dp[N + 1][N + 1][2];
i64 pre[N + 1][N + 1];

void chmax(i64 &a, i64 b) {
    if (a < b) {
        a = b;
    }
}

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    for (int i = 0; i < m; i++) {
        pre[X[i]][Y[i] + 1] += W[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pre[i][j + 1] += pre[i][j];
        }
    }
    
    memset(dp, 190, sizeof dp);
    
    for (int i = 0; i <= n; i++) {
        dp[0][i][0] = dp[0][i][1] = 0;
    }
    for (int i = 1; i < n; i++) {
        i64 best = -inf;
        for (int k = 0; k <= n; k++) {
            chmax(best, dp[i - 1][k][0] - pre[i - 1][k]);
            chmax(dp[i][k][0], best + pre[i - 1][k]);
        }
        best = -inf;
        for (int k = n; k >= 0; k--) {
            chmax(best, dp[i - 1][k][1] + pre[i][k]);
            chmax(dp[i][k][1], best - pre[i][k]);
        }
        for (int j = 0; j <= n; j++) {
            if (i >= 2) {
                for (int k = 0; k <= n; k++) {
                    chmax(dp[i][k][0], dp[i - 2][j][1] + pre[i - 1][max(j, k)]);
                }
            }
        }
        for (int j = 0; j <= n; j++) {
            chmax(dp[i][j][1], dp[i][j][0]);
        }
        if (i + 1 < n)
            chmax(dp[i + 1][0][0], dp[i][0][1]);
    }
    
    i64 ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, dp[n - 1][i][1]);
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 719 ms 433044 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 141244 KB Output is correct
2 Runtime error 731 ms 436924 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 736 ms 429216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 141196 KB Output is correct
2 Correct 46 ms 141300 KB Output is correct
3 Correct 46 ms 141264 KB Output is correct
4 Correct 46 ms 141260 KB Output is correct
5 Correct 45 ms 141260 KB Output is correct
6 Correct 45 ms 141260 KB Output is correct
7 Correct 45 ms 141268 KB Output is correct
8 Correct 50 ms 141260 KB Output is correct
9 Correct 50 ms 142028 KB Output is correct
10 Correct 72 ms 143188 KB Output is correct
11 Correct 53 ms 142036 KB Output is correct
12 Correct 73 ms 143092 KB Output is correct
13 Correct 45 ms 141520 KB Output is correct
14 Correct 73 ms 143212 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 141196 KB Output is correct
2 Correct 46 ms 141300 KB Output is correct
3 Correct 46 ms 141264 KB Output is correct
4 Correct 46 ms 141260 KB Output is correct
5 Correct 45 ms 141260 KB Output is correct
6 Correct 45 ms 141260 KB Output is correct
7 Correct 45 ms 141268 KB Output is correct
8 Correct 50 ms 141260 KB Output is correct
9 Correct 50 ms 142028 KB Output is correct
10 Correct 72 ms 143188 KB Output is correct
11 Correct 53 ms 142036 KB Output is correct
12 Correct 73 ms 143092 KB Output is correct
13 Correct 45 ms 141520 KB Output is correct
14 Correct 73 ms 143212 KB Output is correct
15 Correct 73 ms 143188 KB Output is correct
16 Correct 46 ms 141644 KB Output is correct
17 Correct 81 ms 144172 KB Output is correct
18 Correct 82 ms 144204 KB Output is correct
19 Correct 84 ms 144204 KB Output is correct
20 Correct 81 ms 144204 KB Output is correct
21 Correct 81 ms 144252 KB Output is correct
22 Correct 91 ms 145292 KB Output is correct
23 Correct 75 ms 143392 KB Output is correct
24 Correct 80 ms 143856 KB Output is correct
25 Correct 72 ms 143084 KB Output is correct
26 Correct 81 ms 143308 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 141196 KB Output is correct
2 Correct 46 ms 141300 KB Output is correct
3 Correct 46 ms 141264 KB Output is correct
4 Correct 46 ms 141260 KB Output is correct
5 Correct 45 ms 141260 KB Output is correct
6 Correct 45 ms 141260 KB Output is correct
7 Correct 45 ms 141268 KB Output is correct
8 Correct 50 ms 141260 KB Output is correct
9 Correct 50 ms 142028 KB Output is correct
10 Correct 72 ms 143188 KB Output is correct
11 Correct 53 ms 142036 KB Output is correct
12 Correct 73 ms 143092 KB Output is correct
13 Correct 45 ms 141520 KB Output is correct
14 Correct 73 ms 143212 KB Output is correct
15 Correct 73 ms 143188 KB Output is correct
16 Correct 46 ms 141644 KB Output is correct
17 Correct 81 ms 144172 KB Output is correct
18 Correct 82 ms 144204 KB Output is correct
19 Correct 84 ms 144204 KB Output is correct
20 Correct 81 ms 144204 KB Output is correct
21 Correct 81 ms 144252 KB Output is correct
22 Correct 91 ms 145292 KB Output is correct
23 Correct 75 ms 143392 KB Output is correct
24 Correct 80 ms 143856 KB Output is correct
25 Correct 72 ms 143084 KB Output is correct
26 Correct 81 ms 143308 KB Output is correct
27 Execution timed out 1042 ms 211688 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 736 ms 429216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 719 ms 433044 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -