oj.uz

Submission #1079372

# Submission time Handle Problem Language Result Execution time Memory
1079372 2024-08-28T13:34:26 Z ArthuroWich Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int pref[3005][3005];
int query(int j, int i1, int i2) {
    if (i1 > i2) {
        return 0;
    }
    return pref[i2][j]-pref[i1-1][j];
}
int max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) {
    int n = N, m = M, yn;
    yn = N;
    vector<vector<int>> c(yn+1, vector<int>(n+1, 0));
    vector<vector<vector<int>>> dp(yn+1, vector<vector<int>>(n+1, vector<int>(2, 0))); // 0 is increasing, 1 is decreasing, increasing can go to decreasing, decreasing cant go to increasing if next to eachother
    for (int i = 0; i < m; i++) {
        c[Y[i]+1][X[i]] = W[i];
        pref[Y[i]+1][X[i]] = W[i];
    }
    for (int j = 0; j < n; j++) {
        for (int i = 1; i <= yn; i++) {
            pref[i][j] += pref[i-1][j];
        }
    }
    for (int j = 1; j < n; j++) {
        int v = 0;
        dp[0][j][0] = max(dp[0][j][0], dp[0][j-1][0]);
        for (int i = 1; i <= yn; i++) {
            v += c[i][j];
            dp[0][j][0] = max(dp[0][j][0], dp[i][j-1][0]+v);
            dp[0][j][0] = max(dp[0][j][0], dp[i][j-1][1]+v);
        }
        for (int i = 1; i <= yn; i++) {
            for (int a = i; a <= yn; a++) {
                v = query(j, i+1, a);
                dp[i][j][1] = max(dp[i][j][1], dp[a][j-1][0]+v);
                dp[i][j][1] = max(dp[i][j][1], dp[a][j-1][1]+v);
            } 
            for (int a = 1; a <= i; a++) {
                v = query(j-1, a+1, i);
                dp[i][j][0] = max(dp[i][j][0], dp[a][j-1][0]+v);
            } 
        }
        if (j == 1) {
            v = 0;
            for (int i = 1; i <= yn; i++) {
                v += c[i][j-1];
                dp[i][j][0] = max(dp[i][j][0], dp[0][j-1][0]+v);
                dp[i][j][1] = max(dp[i][j][1], dp[0][j-1][0]+v);
            }
        }
        if (j-2 >= 0) {
            v = 0;
            for (int i = 1; i <= yn; i++) {
                v += c[i][j-1];
                dp[i][j][0] = max(dp[i][j][0], dp[0][j-2][0]+v);
                dp[i][j][1] = max(dp[i][j][1], dp[0][j-2][0]+v);
            }
            for (int i = 1; i <= yn; i++) {
                v = 0;
                for (int h = 1; h <= i; h++) {
                    v += c[h][j-1];
                }
                for (int h = 1; h <= i; h++) {
                    dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][0]+v);
                    dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][1]+v);
                    dp[i][j][1] = max(dp[i][j][1], dp[h][j-2][0]+v);
                    dp[i][j][1] = max(dp[i][j][1], dp[h][j-2][1]+v);
                }
                for (int h = i+1; h < yn; h++) {
                    v += c[h][j-1];
                    dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][0]+v);
                    dp[i][j][0] = max(dp[i][j][0], dp[h][j-2][1]+v);
                    dp[i][j][1] = max(dp[i][j][1], dp[h][j-2][0]+v);
                    dp[i][j][1] = max(dp[i][j][1], dp[h][j-2][1]+v);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= yn; i++) {
        ans = max(ans, dp[i][n-1][0]);
        ans = max(ans, dp[i][n-1][1]);
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 913 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 916 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 867 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 25 ms 2652 KB Output is correct
10 Correct 207 ms 8136 KB Output is correct
11 Correct 26 ms 2652 KB Output is correct
12 Correct 209 ms 8080 KB Output is correct
13 Correct 3 ms 1112 KB Output is correct
14 Correct 225 ms 8028 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 25 ms 2652 KB Output is correct
10 Correct 207 ms 8136 KB Output is correct
11 Correct 26 ms 2652 KB Output is correct
12 Correct 209 ms 8080 KB Output is correct
13 Correct 3 ms 1112 KB Output is correct
14 Correct 225 ms 8028 KB Output is correct
15 Correct 209 ms 8028 KB Output is correct
16 Correct 3 ms 1112 KB Output is correct
17 Correct 249 ms 9900 KB Output is correct
18 Correct 214 ms 9668 KB Output is correct
19 Correct 218 ms 9820 KB Output is correct
20 Correct 210 ms 9820 KB Output is correct
21 Correct 238 ms 9840 KB Output is correct
22 Correct 251 ms 11676 KB Output is correct
23 Correct 207 ms 8280 KB Output is correct
24 Correct 208 ms 9048 KB Output is correct
25 Correct 203 ms 8028 KB Output is correct
26 Correct 204 ms 8284 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 25 ms 2652 KB Output is correct
10 Correct 207 ms 8136 KB Output is correct
11 Correct 26 ms 2652 KB Output is correct
12 Correct 209 ms 8080 KB Output is correct
13 Correct 3 ms 1112 KB Output is correct
14 Correct 225 ms 8028 KB Output is correct
15 Correct 209 ms 8028 KB Output is correct
16 Correct 3 ms 1112 KB Output is correct
17 Correct 249 ms 9900 KB Output is correct
18 Correct 214 ms 9668 KB Output is correct
19 Correct 218 ms 9820 KB Output is correct
20 Correct 210 ms 9820 KB Output is correct
21 Correct 238 ms 9840 KB Output is correct
22 Correct 251 ms 11676 KB Output is correct
23 Correct 207 ms 8280 KB Output is correct
24 Correct 208 ms 9048 KB Output is correct
25 Correct 203 ms 8028 KB Output is correct
26 Correct 204 ms 8284 KB Output is correct
27 Execution timed out 1094 ms 635224 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 867 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 913 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -