oj.uz

Submission #834735

# Submission time Handle Problem Language Result Execution time Memory
834735 2023-08-22T18:02:39 Z tengiz05 Catfish Farm (IOI22_fish) C++17
52 / 100
 737 ms 436988 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]);
        }
        if (i >= 2) {
            best = -inf;
            for (int j = n; j >= 0; j--) {
                chmax(best, dp[i - 2][j][1] + pre[i - 1][j]);
                chmax(dp[i][j][0], best);
            }
            best = -inf;
            for (int j = 0; j <= n; j++) {
                chmax(best, dp[i - 2][j][1]);
                chmax(dp[i][j][0], best + pre[i - 1][j]);
            }
        }
        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 721 ms 433052 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 141280 KB Output is correct
2 Runtime error 734 ms 436988 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 737 ms 429156 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 44 ms 141268 KB Output is correct
2 Correct 43 ms 141300 KB Output is correct
3 Correct 44 ms 141260 KB Output is correct
4 Correct 44 ms 141260 KB Output is correct
5 Correct 45 ms 141292 KB Output is correct
6 Correct 43 ms 141260 KB Output is correct
7 Correct 45 ms 141268 KB Output is correct
8 Correct 45 ms 141256 KB Output is correct
9 Correct 45 ms 142036 KB Output is correct
10 Correct 45 ms 143180 KB Output is correct
11 Correct 44 ms 142016 KB Output is correct
12 Correct 53 ms 143128 KB Output is correct
13 Correct 44 ms 141524 KB Output is correct
14 Correct 46 ms 143180 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 141268 KB Output is correct
2 Correct 43 ms 141300 KB Output is correct
3 Correct 44 ms 141260 KB Output is correct
4 Correct 44 ms 141260 KB Output is correct
5 Correct 45 ms 141292 KB Output is correct
6 Correct 43 ms 141260 KB Output is correct
7 Correct 45 ms 141268 KB Output is correct
8 Correct 45 ms 141256 KB Output is correct
9 Correct 45 ms 142036 KB Output is correct
10 Correct 45 ms 143180 KB Output is correct
11 Correct 44 ms 142016 KB Output is correct
12 Correct 53 ms 143128 KB Output is correct
13 Correct 44 ms 141524 KB Output is correct
14 Correct 46 ms 143180 KB Output is correct
15 Correct 45 ms 143180 KB Output is correct
16 Correct 45 ms 141644 KB Output is correct
17 Correct 55 ms 144204 KB Output is correct
18 Correct 56 ms 144204 KB Output is correct
19 Correct 56 ms 144204 KB Output is correct
20 Correct 55 ms 144168 KB Output is correct
21 Correct 53 ms 144144 KB Output is correct
22 Correct 64 ms 145228 KB Output is correct
23 Correct 47 ms 143364 KB Output is correct
24 Correct 53 ms 143880 KB Output is correct
25 Correct 49 ms 143168 KB Output is correct
26 Correct 48 ms 143308 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 141268 KB Output is correct
2 Correct 43 ms 141300 KB Output is correct
3 Correct 44 ms 141260 KB Output is correct
4 Correct 44 ms 141260 KB Output is correct
5 Correct 45 ms 141292 KB Output is correct
6 Correct 43 ms 141260 KB Output is correct
7 Correct 45 ms 141268 KB Output is correct
8 Correct 45 ms 141256 KB Output is correct
9 Correct 45 ms 142036 KB Output is correct
10 Correct 45 ms 143180 KB Output is correct
11 Correct 44 ms 142016 KB Output is correct
12 Correct 53 ms 143128 KB Output is correct
13 Correct 44 ms 141524 KB Output is correct
14 Correct 46 ms 143180 KB Output is correct
15 Correct 45 ms 143180 KB Output is correct
16 Correct 45 ms 141644 KB Output is correct
17 Correct 55 ms 144204 KB Output is correct
18 Correct 56 ms 144204 KB Output is correct
19 Correct 56 ms 144204 KB Output is correct
20 Correct 55 ms 144168 KB Output is correct
21 Correct 53 ms 144144 KB Output is correct
22 Correct 64 ms 145228 KB Output is correct
23 Correct 47 ms 143364 KB Output is correct
24 Correct 53 ms 143880 KB Output is correct
25 Correct 49 ms 143168 KB Output is correct
26 Correct 48 ms 143308 KB Output is correct
27 Correct 128 ms 211788 KB Output is correct
28 Correct 97 ms 157444 KB Output is correct
29 Correct 194 ms 224388 KB Output is correct
30 Correct 195 ms 224304 KB Output is correct
31 Correct 196 ms 224416 KB Output is correct
32 Correct 110 ms 157916 KB Output is correct
33 Correct 189 ms 224332 KB Output is correct
34 Correct 194 ms 224460 KB Output is correct
35 Correct 153 ms 216412 KB Output is correct
36 Correct 195 ms 224348 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 737 ms 429156 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 721 ms 433052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -