oj.uz

Submission #834726

# Submission time Handle Problem Language Result Execution time Memory
834726 2023-08-22T17:49:32 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;

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++) {
        for (int j = 0; j <= n; j++) {
            for (int k = j; k <= n; k++) {
                chmax(dp[i][k][0], dp[i - 1][j][0] + pre[i - 1][k] - pre[i - 1][j]);
            }
            for (int k = j; k >= 0; k--) {
                chmax(dp[i][k][1], dp[i - 1][j][1] + pre[i][j] - pre[i][k]);
            }
            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 732 ms 433004 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 44 ms 141252 KB Output is correct
2 Runtime error 725 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 744 ms 429116 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 45 ms 141204 KB Output is correct
2 Correct 43 ms 141240 KB Output is correct
3 Correct 45 ms 141184 KB Output is correct
4 Correct 45 ms 141212 KB Output is correct
5 Correct 46 ms 141172 KB Output is correct
6 Correct 44 ms 141176 KB Output is correct
7 Correct 45 ms 141260 KB Output is correct
8 Correct 45 ms 141264 KB Output is correct
9 Correct 50 ms 141984 KB Output is correct
10 Correct 101 ms 143276 KB Output is correct
11 Correct 54 ms 142028 KB Output is correct
12 Correct 98 ms 143176 KB Output is correct
13 Correct 45 ms 141524 KB Output is correct
14 Correct 98 ms 143200 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 141204 KB Output is correct
2 Correct 43 ms 141240 KB Output is correct
3 Correct 45 ms 141184 KB Output is correct
4 Correct 45 ms 141212 KB Output is correct
5 Correct 46 ms 141172 KB Output is correct
6 Correct 44 ms 141176 KB Output is correct
7 Correct 45 ms 141260 KB Output is correct
8 Correct 45 ms 141264 KB Output is correct
9 Correct 50 ms 141984 KB Output is correct
10 Correct 101 ms 143276 KB Output is correct
11 Correct 54 ms 142028 KB Output is correct
12 Correct 98 ms 143176 KB Output is correct
13 Correct 45 ms 141524 KB Output is correct
14 Correct 98 ms 143200 KB Output is correct
15 Correct 93 ms 143160 KB Output is correct
16 Correct 46 ms 141644 KB Output is correct
17 Correct 105 ms 145040 KB Output is correct
18 Correct 118 ms 144920 KB Output is correct
19 Correct 109 ms 144960 KB Output is correct
20 Correct 103 ms 145000 KB Output is correct
21 Correct 103 ms 144900 KB Output is correct
22 Correct 115 ms 146748 KB Output is correct
23 Correct 98 ms 143532 KB Output is correct
24 Correct 111 ms 144484 KB Output is correct
25 Correct 95 ms 143228 KB Output is correct
26 Correct 95 ms 143420 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 141204 KB Output is correct
2 Correct 43 ms 141240 KB Output is correct
3 Correct 45 ms 141184 KB Output is correct
4 Correct 45 ms 141212 KB Output is correct
5 Correct 46 ms 141172 KB Output is correct
6 Correct 44 ms 141176 KB Output is correct
7 Correct 45 ms 141260 KB Output is correct
8 Correct 45 ms 141264 KB Output is correct
9 Correct 50 ms 141984 KB Output is correct
10 Correct 101 ms 143276 KB Output is correct
11 Correct 54 ms 142028 KB Output is correct
12 Correct 98 ms 143176 KB Output is correct
13 Correct 45 ms 141524 KB Output is correct
14 Correct 98 ms 143200 KB Output is correct
15 Correct 93 ms 143160 KB Output is correct
16 Correct 46 ms 141644 KB Output is correct
17 Correct 105 ms 145040 KB Output is correct
18 Correct 118 ms 144920 KB Output is correct
19 Correct 109 ms 144960 KB Output is correct
20 Correct 103 ms 145000 KB Output is correct
21 Correct 103 ms 144900 KB Output is correct
22 Correct 115 ms 146748 KB Output is correct
23 Correct 98 ms 143532 KB Output is correct
24 Correct 111 ms 144484 KB Output is correct
25 Correct 95 ms 143228 KB Output is correct
26 Correct 95 ms 143420 KB Output is correct
27 Execution timed out 1096 ms 211792 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 744 ms 429116 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 732 ms 433004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -