oj.uz

Submission #1042315

# Submission time Handle Problem Language Result Execution time Memory
1042315 2024-08-02T20:36:27 Z VMaksimoski008 Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 117072 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
 
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for(int i=0; i<M; i++) X[i]++, Y[i]++;
    map<int, int> mp[N+5];
    for(int i=0; i<M; i++) mp[X[i]][Y[i]] = W[i];
    ll ans = 0;

    vector<pair<int, int> > vec[N+5];
    vector<int> pos[N+5], SZ(N+5);
    for(int i=1; i<=N; i++) vec[i].push_back({ 0, 0 });
    for(int i=0; i<M; i++) vec[X[i]].push_back({ Y[i], W[i] });

    for(int i=1; i<=N; i++) {
        set<int> st;
        for(int j=-1; j<=1; j++) for(auto &x : vec[i-j]) st.insert(x.first);
        for(auto &x : st) pos[i].push_back(x);
        sort(vec[i].begin(), vec[i].end());
    }

    vector<vector<ll> > pref(N+5), pmx1(N+5);
    vector<vector<vector<ll> > > dp(N+5);
    for(int i=1; i<=N; i++) {
        SZ[i] = pos[i].size() - 1;
        pref[i].resize(SZ[i] + 5);
        pmx1[i].resize(SZ[i] + 5);
        dp[i].resize(SZ[i] + 5, vector<ll>(2));
        
        if(i == 1) {
            pmx1[i][0] = dp[i][0][1] - pref[i][0];
            for(int j=1; j<=SZ[i]; j++) pmx1[i][j] = max(pmx1[i][j-1], dp[i][j][1] - pref[i][j]);
        }

        for(int j=1; j<=SZ[i]; j++) pref[i][j] = pref[i][j-1] + mp[i][pos[i][j]];
    }

    for(int i=2; i<=N; i++) {
        for(int j=0; j<=SZ[i]; j++) {
            int p = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i][j]) - pos[i-1].begin() - 1;
            dp[i][j][1] = max(dp[i][j][1], pmx1[i-1][p] + pref[i-1][p]);
            for(int k=0; k<=SZ[i-1]; k++) {
                // if(pos[i][j] >= pos[i-1][k]) {
                    // int p = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i][j]) - pos[i-1].begin() - 1;
                //     dp[i][j][1] = max(dp[i][j][1], dp[i-1][k][1] + pref[i-1][p] - pref[i-1][k]);
                // }

                if(pos[i][j] <= pos[i-1][k]) {
                    int p = upper_bound(pos[i].begin(), pos[i].end(), pos[i-1][k]) - pos[i].begin() - 1;
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][k][0], dp[i-1][k][1]) + pref[i][p] - pref[i][j]);
                }
            }

            if(i < 3) continue;
            for(int k=0; k<=SZ[i-2]; k++) {
                int p1 = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i][j]) - pos[i-1].begin() - 1;
                int p2 = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i-2][k]) - pos[i-1].begin() - 1;
                dp[i][j][0] = max(dp[i][j][0], max(dp[i-2][k][0], dp[i-2][k][1]) + max((p1 > -1 ? pref[i-1][p1] : 0), (p2 > -1 ? pref[i-1][p2] : 0)));
                dp[i][j][1] = max(dp[i][j][1], max(dp[i-2][k][0], dp[i-2][k][1]) + max((p1 > -1 ? pref[i-1][p1] : 0), (p2 > -1 ? pref[i-1][p2] : 0)));
            }
        }

        pmx1[i][0] = dp[i][0][1] - pref[i][0];
        for(int j=1; j<=SZ[i]; j++) {
            pmx1[i][j] = max(pmx1[i][j-1], dp[i][j][1] - pref[i][j]);
        }
    }

    for(int i=1; i<=N; i++) {
        for(int j=0; j<=SZ[i]; j++) {
            if(pref[i+1].empty() || j == 0) ans = max({ ans, dp[i][j][0], dp[i][j][1] });
            else {
                int p = upper_bound(pos[i+1].begin(), pos[i+1].end(), pos[i][j]) - pos[i+1].begin() - 1;
                ans = max(ans, max(dp[i][j][0], dp[i][j][1]) + pref[i+1][p]);
            }
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 77100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1082 ms 91580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 60876 KB Output is correct
2 Correct 70 ms 61068 KB Output is correct
3 Correct 114 ms 64456 KB Output is correct
4 Correct 93 ms 68176 KB Output is correct
5 Correct 125 ms 77392 KB Output is correct
6 Correct 119 ms 77392 KB Output is correct
7 Correct 122 ms 77400 KB Output is correct
8 Correct 129 ms 77392 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 648 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 600 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 648 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 8 ms 896 KB Output is correct
17 Correct 576 ms 9640 KB Output is correct
18 Correct 556 ms 8540 KB Output is correct
19 Correct 332 ms 8936 KB Output is correct
20 Correct 287 ms 7772 KB Output is correct
21 Correct 257 ms 7764 KB Output is correct
22 Correct 965 ms 15108 KB Output is correct
23 Correct 71 ms 3928 KB Output is correct
24 Correct 462 ms 9816 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 58 ms 3420 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 648 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 8 ms 896 KB Output is correct
17 Correct 576 ms 9640 KB Output is correct
18 Correct 556 ms 8540 KB Output is correct
19 Correct 332 ms 8936 KB Output is correct
20 Correct 287 ms 7772 KB Output is correct
21 Correct 257 ms 7764 KB Output is correct
22 Correct 965 ms 15108 KB Output is correct
23 Correct 71 ms 3928 KB Output is correct
24 Correct 462 ms 9816 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 58 ms 3420 KB Output is correct
27 Correct 5 ms 3416 KB Output is correct
28 Execution timed out 1099 ms 45704 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 60876 KB Output is correct
2 Correct 70 ms 61068 KB Output is correct
3 Correct 114 ms 64456 KB Output is correct
4 Correct 93 ms 68176 KB Output is correct
5 Correct 125 ms 77392 KB Output is correct
6 Correct 119 ms 77392 KB Output is correct
7 Correct 122 ms 77400 KB Output is correct
8 Correct 129 ms 77392 KB Output is correct
9 Correct 192 ms 100940 KB Output is correct
10 Correct 97 ms 45648 KB Output is correct
11 Correct 201 ms 91216 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 63 ms 60972 KB Output is correct
19 Correct 83 ms 61008 KB Output is correct
20 Correct 67 ms 61008 KB Output is correct
21 Correct 67 ms 60888 KB Output is correct
22 Correct 231 ms 100692 KB Output is correct
23 Correct 303 ms 114664 KB Output is correct
24 Correct 290 ms 117072 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 77100 KB Time limit exceeded
2 Halted 0 ms 0 KB -