oj.uz

Submission #991829

# Submission time Handle Problem Language Result Execution time Memory
991829 2024-06-03T08:24:01 Z thinknoexit Catfish Farm (IOI22_fish) C++17
50 / 100
 1000 ms 224304 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
map<int, int> a[100100];
/*
0 -> Increasing
1 -> Decreasing
2 -> No Poles
*/
map<int, map<int, ll>> dp[3];
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++) {
        a[X[i] + 1][Y[i] + 1] = W[i];
        r = max(r, X[i] + 1);
        c = max(c, Y[i] + 1);
    }
    c++;
    r = min(n, r + 1);
    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[2][i - 1][j] });
            dp[0][i][j] = mx;
        }
        mx = 0;
        for (int j = c;j >= 0;j--) {
            mx = max(mx, dp[2][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] });
        }
        // (2)
        mx = 0;
        for (int j = 0;j <= c;j++) {
            mx += a[i][j];
            dp[2][i][j] = max(dp[0][i - 1][j], dp[1][i - 1][j]) + mx;
        }
    }
    ll ans = 0;
    for (int i = 1;i <= r;i++) {
        for (int j = 0;j <= c;j++) {
            ans = max(ans, dp[0][i][j]);
            ans = max(ans, dp[1][i][j]);
            ans = max(ans, dp[2][i][j]);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 49236 KB Output is correct
2 Correct 364 ms 56080 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 311 ms 51924 KB Output is correct
5 Execution timed out 1075 ms 153400 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 538 ms 72288 KB Output is correct
3 Correct 730 ms 83640 KB Output is correct
4 Correct 248 ms 50620 KB Output is correct
5 Correct 363 ms 56144 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 5140 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 273 ms 51940 KB Output is correct
12 Correct 540 ms 71764 KB Output is correct
13 Correct 634 ms 79444 KB Output is correct
14 Correct 490 ms 71764 KB Output is correct
15 Correct 634 ms 79404 KB Output is correct
16 Correct 507 ms 71644 KB Output is correct
17 Correct 545 ms 79140 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 533 ms 103604 KB Output is correct
3 Correct 356 ms 94992 KB Output is correct
4 Correct 388 ms 95316 KB Output is correct
5 Correct 629 ms 107780 KB Output is correct
6 Correct 678 ms 107016 KB Output is correct
7 Correct 629 ms 107540 KB Output is correct
8 Correct 641 ms 107500 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4968 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 5 ms 5980 KB Output is correct
11 Correct 4 ms 5468 KB Output is correct
12 Correct 4 ms 5724 KB Output is correct
13 Correct 1 ms 5212 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4968 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 5 ms 5980 KB Output is correct
11 Correct 4 ms 5468 KB Output is correct
12 Correct 4 ms 5724 KB Output is correct
13 Correct 1 ms 5212 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 114 ms 26192 KB Output is correct
16 Correct 7 ms 6492 KB Output is correct
17 Correct 135 ms 27432 KB Output is correct
18 Correct 130 ms 27376 KB Output is correct
19 Correct 126 ms 27356 KB Output is correct
20 Correct 135 ms 27432 KB Output is correct
21 Correct 68 ms 16720 KB Output is correct
22 Correct 183 ms 28500 KB Output is correct
23 Correct 115 ms 26452 KB Output is correct
24 Correct 128 ms 26964 KB Output is correct
25 Correct 9 ms 6488 KB Output is correct
26 Correct 116 ms 26640 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4968 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 5 ms 5980 KB Output is correct
11 Correct 4 ms 5468 KB Output is correct
12 Correct 4 ms 5724 KB Output is correct
13 Correct 1 ms 5212 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 114 ms 26192 KB Output is correct
16 Correct 7 ms 6492 KB Output is correct
17 Correct 135 ms 27432 KB Output is correct
18 Correct 130 ms 27376 KB Output is correct
19 Correct 126 ms 27356 KB Output is correct
20 Correct 135 ms 27432 KB Output is correct
21 Correct 68 ms 16720 KB Output is correct
22 Correct 183 ms 28500 KB Output is correct
23 Correct 115 ms 26452 KB Output is correct
24 Correct 128 ms 26964 KB Output is correct
25 Correct 9 ms 6488 KB Output is correct
26 Correct 116 ms 26640 KB Output is correct
27 Execution timed out 1066 ms 224304 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 533 ms 103604 KB Output is correct
3 Correct 356 ms 94992 KB Output is correct
4 Correct 388 ms 95316 KB Output is correct
5 Correct 629 ms 107780 KB Output is correct
6 Correct 678 ms 107016 KB Output is correct
7 Correct 629 ms 107540 KB Output is correct
8 Correct 641 ms 107500 KB Output is correct
9 Execution timed out 1075 ms 151688 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 49236 KB Output is correct
2 Correct 364 ms 56080 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 311 ms 51924 KB Output is correct
5 Execution timed out 1075 ms 153400 KB Time limit exceeded
6 Halted 0 ms 0 KB -