oj.uz

Submission #1042279

# Submission time Handle Problem Language Result Execution time Memory
1042279 2024-08-02T19:06:15 Z VMaksimoski008 Catfish Farm (IOI22_fish) C++17
64 / 100
 309 ms 506964 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll pref[3005][3005], dp[3005][3005][2], pmx1[3005][3005], smx1[3005][3005], pmx2[3005][3005], smx2[3005][3005];
 
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    int mask = 0, mx = 0, mx2 = 0;
    for(int i=0; i<M; i++) mask |= (1 << (X[i] % 2));
    for(int i=0; i<M; i++) mx = max(mx, Y[i]);
    for(int i=0; i<M; i++) mx2 = max(mx, X[i]);
 
    if(mask == 1) {
        ll ans = 0;
        for(int &x : W) ans += x;
        return ans;
    }

    if(mx == 0) {
        vector<ll> val(N+5), dp(N+5);
        for(int i=0; i<M; i++) val[X[i]] = W[i];
 
        ll ans = 0;
        vector<ll> MX(N+5); MX[0] = val[1];
        for(int i=1; i<N; i++) {
            dp[i] = max(dp[i-1], val[i-1]);
            if(i >= 3) dp[i] = max(dp[i], MX[i-3] + val[i-1]);
            if(i >= 2) dp[i] = max(dp[i], dp[i-2] + val[i-1]);
            MX[i] = max(MX[i-1], dp[i] + val[i+1]);
        }
 
        for(int i=0; i<N; i++) ans = max(ans, dp[i] + val[i+1]);
        return ans;
    }

    for(int i=0; i<M; i++) pref[X[i]+1][Y[i]+1] += W[i];
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) pref[i][j] += pref[i][j-1];
    for(int i=1; i<=N; i++)
        for(int j=0; j<=N; j++) pmx1[i][j] = smx1[i][j] = pmx2[i][j] = smx2[i][j] = -1e18;

    // if(mx2 <= 1) {
    //     if(N == 2) return max(pref[1][2], pref[2][2]);
    //     ll ans = 0;
    //     for(int i=1; i<=N; i++) ans = max(ans, pref[1][i] + pref[2][N] - pref[2][i]);
    //     return max({ pref[1][N], pref[2][N], ans });
    // }

    pmx1[1][0] = dp[1][0][1] - pref[1][0];
    smx1[1][N] = max(dp[1][N][0], dp[1][N][1]) + pref[2][N];
    for(int i=1; i<=N; i++) pmx1[1][i] = max(pmx1[1][i-1], dp[1][i][1] - pref[1][i]);
    for(int i=N-1; i>=0; i--) smx1[1][i] = max(smx1[1][i+1], max(dp[1][i][0], dp[1][i][1]) + pref[2][i]);
    for(int i=1; i<=N; i++) pmx2[1][i] = max(pmx2[1][i-1], max(dp[1][i][0], dp[1][i][1]));
    for(int i=N-1; i>=0; i--) smx2[1][i] = max(smx2[i][i+1], max(dp[1][i][0], dp[1][i][1]));

    for(int i=2; i<=N; i++) {
        for(int j=0; j<=N; j++) {
            dp[i][j][0] = max(dp[i][j][0], smx1[i-1][j] - pref[i][j]);
            dp[i][j][1] = max({ dp[i][j][1], pmx1[i-1][j] + pref[i-1][j] });
            if(i >= 3) dp[i][j][0] = max({ dp[i][j][0], pmx2[i-2][j] + pref[i-1][j], smx2[i-2][j] + pref[i-1][j] });
            if(i >= 3) dp[i][j][1] = max({ dp[i][j][1], pmx2[i-2][j] + pref[i-1][j], smx2[i-2][j] + pref[i-1][j] });

            if(j) pmx1[i][j] = pmx1[i][j-1];
            if(j) pmx2[i][j] = pmx2[i][j-1];
            pmx1[i][j] = max(pmx1[i][j], dp[i][j][1] - pref[i][j]);
            pmx2[i][j] = max(pmx2[i][j], max(dp[i][j][0], dp[i][j][1]));
        }

        smx1[i][N] = max(dp[i][N][0], dp[i][N][1]) + pref[i+1][N];
        for(int j=N-1; j>=0; j--) smx1[i][j] = max(smx1[i][j+1], max(dp[i][j][0], dp[i][j][1]) + pref[i+1][j]);
        smx2[i][N] = max(dp[i][N][0], dp[i][N][1]);
        for(int j=N-1; j>=0; j--) smx2[i][j] = max(smx2[i][j+1], max(dp[i][j][0], dp[i][j][1]));
    }

    ll ans = 0;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++) ans = max({ ans, dp[i][j][0] + pref[i+1][j], dp[i][j][1] + pref[i+1][j] });
    return ans;
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:9:27: warning: variable 'mx2' set but not used [-Wunused-but-set-variable]
    9 |     int mask = 0, mx = 0, mx2 = 0;
      |                           ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2140 KB Output is correct
2 Correct 14 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 45 ms 7300 KB Output is correct
6 Correct 46 ms 7252 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Runtime error 222 ms 153908 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 9 ms 3676 KB Output is correct
4 Correct 7 ms 3452 KB Output is correct
5 Correct 17 ms 4968 KB Output is correct
6 Correct 13 ms 4956 KB Output is correct
7 Correct 15 ms 4956 KB Output is correct
8 Correct 17 ms 4960 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 10704 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 2408 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 6 ms 19288 KB Output is correct
11 Correct 3 ms 14400 KB Output is correct
12 Correct 7 ms 20828 KB Output is correct
13 Correct 2 ms 15196 KB Output is correct
14 Correct 6 ms 22620 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 10704 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 2408 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 6 ms 19288 KB Output is correct
11 Correct 3 ms 14400 KB Output is correct
12 Correct 7 ms 20828 KB Output is correct
13 Correct 2 ms 15196 KB Output is correct
14 Correct 6 ms 22620 KB Output is correct
15 Correct 5 ms 24412 KB Output is correct
16 Correct 2 ms 13660 KB Output is correct
17 Correct 15 ms 26456 KB Output is correct
18 Correct 16 ms 24412 KB Output is correct
19 Correct 14 ms 24396 KB Output is correct
20 Correct 13 ms 24412 KB Output is correct
21 Correct 15 ms 26460 KB Output is correct
22 Correct 20 ms 28244 KB Output is correct
23 Correct 8 ms 22876 KB Output is correct
24 Correct 10 ms 23680 KB Output is correct
25 Correct 6 ms 24540 KB Output is correct
26 Correct 8 ms 22876 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 10704 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 2408 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 6 ms 19288 KB Output is correct
11 Correct 3 ms 14400 KB Output is correct
12 Correct 7 ms 20828 KB Output is correct
13 Correct 2 ms 15196 KB Output is correct
14 Correct 6 ms 22620 KB Output is correct
15 Correct 5 ms 24412 KB Output is correct
16 Correct 2 ms 13660 KB Output is correct
17 Correct 15 ms 26456 KB Output is correct
18 Correct 16 ms 24412 KB Output is correct
19 Correct 14 ms 24396 KB Output is correct
20 Correct 13 ms 24412 KB Output is correct
21 Correct 15 ms 26460 KB Output is correct
22 Correct 20 ms 28244 KB Output is correct
23 Correct 8 ms 22876 KB Output is correct
24 Correct 10 ms 23680 KB Output is correct
25 Correct 6 ms 24540 KB Output is correct
26 Correct 8 ms 22876 KB Output is correct
27 Correct 236 ms 494676 KB Output is correct
28 Correct 58 ms 67224 KB Output is correct
29 Correct 292 ms 506936 KB Output is correct
30 Correct 288 ms 506964 KB Output is correct
31 Correct 300 ms 506960 KB Output is correct
32 Correct 66 ms 50544 KB Output is correct
33 Correct 305 ms 506864 KB Output is correct
34 Correct 309 ms 506960 KB Output is correct
35 Correct 265 ms 499024 KB Output is correct
36 Correct 287 ms 506964 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 9 ms 3676 KB Output is correct
4 Correct 7 ms 3452 KB Output is correct
5 Correct 17 ms 4968 KB Output is correct
6 Correct 13 ms 4956 KB Output is correct
7 Correct 15 ms 4956 KB Output is correct
8 Correct 17 ms 4960 KB Output is correct
9 Runtime error 20 ms 5216 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2140 KB Output is correct
2 Correct 14 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 45 ms 7300 KB Output is correct
6 Correct 46 ms 7252 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Runtime error 222 ms 153908 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -