oj.uz

Submission #1042325

# Submission time Handle Problem Language Result Execution time Memory
1042325 2024-08-02T21:13:06 Z VMaksimoski008 Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 245764 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), smx1(N+5), pmx2(N+5), smx2(N+5);
    vector<vector<vector<ll> > > dp(N+5);
    for(int i=N; i>=1; i--) {
        SZ[i] = pos[i].size() - 1;
        pref[i].resize(SZ[i] + 10);
        pmx1[i].resize(SZ[i] + 10);
        smx1[i].resize(SZ[i] + 10);
        pmx2[i].resize(SZ[i] + 10);
        smx2[i].resize(SZ[i] + 10);
        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=SZ[i]; j>=0; j--) {
                int p = upper_bound(pos[i+1].begin(), pos[i+1].end(), pos[i][j]) - pos[i+1].begin() - 1;
                smx1[i][j] = pref[i+1][p];
            }

            for(int j=SZ[i]-1; j>=0; j--) smx1[i][j] = max(smx1[i][j], smx1[i][j+1]);
        }

        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++) {
        int ptr = 0;
        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]);
            while(ptr + 1 <= SZ[i-1] && pos[i-1][ptr] < pos[i][j]) ptr++;
            if(pos[i-1][ptr] >= pos[i][j]) dp[i][j][0] = max(dp[i][j][0], smx1[i-1][ptr] - pref[i][j]);

            if(i < 3) continue;
            int pa = upper_bound(pos[i-2].begin(), pos[i-2].end(), pos[i][j]) - pos[i-2].begin() - 1;
            int pb = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i][j]) - pos[i-1].begin() - 1;
            dp[i][j][0] = max(dp[i][j][0], pmx2[i-2][pa] + pref[i-1][pb]);
            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][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];
        pmx2[i][0] = max(dp[i][0][0], dp[i][0][1]);
        for(int j=1; j<=SZ[i]; j++) {
            pmx1[i][j] = max(pmx1[i][j-1], dp[i][j][1] - pref[i][j]);
            pmx2[i][j] = max(pmx2[i][j-1], max(dp[i][j][0], dp[i][j][1]));
        }

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

        for(int j=SZ[i]-1; j>=0; j--) smx1[i][j] = max(smx1[i][j], smx1[i][j+1]);
    }

    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 Correct 274 ms 120960 KB Output is correct
2 Correct 253 ms 137664 KB Output is correct
3 Correct 124 ms 105556 KB Output is correct
4 Correct 118 ms 105708 KB Output is correct
5 Execution timed out 1088 ms 245764 KB Time limit exceeded
6 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 Execution timed out 1091 ms 137916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 105552 KB Output is correct
2 Correct 119 ms 105632 KB Output is correct
3 Correct 157 ms 102736 KB Output is correct
4 Correct 161 ms 111440 KB Output is correct
5 Correct 170 ms 118868 KB Output is correct
6 Correct 170 ms 119128 KB Output is correct
7 Correct 168 ms 118988 KB Output is correct
8 Correct 173 ms 118868 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 2 ms 1116 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 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 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 0 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 2 ms 1116 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 504 ms 11196 KB Output is correct
18 Correct 438 ms 9820 KB Output is correct
19 Correct 277 ms 10168 KB Output is correct
20 Correct 225 ms 9176 KB Output is correct
21 Correct 223 ms 9040 KB Output is correct
22 Correct 832 ms 17352 KB Output is correct
23 Correct 63 ms 4440 KB Output is correct
24 Correct 366 ms 10840 KB Output is correct
25 Correct 2 ms 1112 KB Output is correct
26 Correct 48 ms 3928 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 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 0 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 2 ms 1116 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 7 ms 860 KB Output is correct
17 Correct 504 ms 11196 KB Output is correct
18 Correct 438 ms 9820 KB Output is correct
19 Correct 277 ms 10168 KB Output is correct
20 Correct 225 ms 9176 KB Output is correct
21 Correct 223 ms 9040 KB Output is correct
22 Correct 832 ms 17352 KB Output is correct
23 Correct 63 ms 4440 KB Output is correct
24 Correct 366 ms 10840 KB Output is correct
25 Correct 2 ms 1112 KB Output is correct
26 Correct 48 ms 3928 KB Output is correct
27 Correct 6 ms 4696 KB Output is correct
28 Execution timed out 1046 ms 48724 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 105552 KB Output is correct
2 Correct 119 ms 105632 KB Output is correct
3 Correct 157 ms 102736 KB Output is correct
4 Correct 161 ms 111440 KB Output is correct
5 Correct 170 ms 118868 KB Output is correct
6 Correct 170 ms 119128 KB Output is correct
7 Correct 168 ms 118988 KB Output is correct
8 Correct 173 ms 118868 KB Output is correct
9 Correct 274 ms 147172 KB Output is correct
10 Correct 128 ms 70560 KB Output is correct
11 Correct 275 ms 140624 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 145 ms 105680 KB Output is correct
19 Correct 126 ms 105556 KB Output is correct
20 Correct 128 ms 105552 KB Output is correct
21 Correct 125 ms 105556 KB Output is correct
22 Correct 343 ms 149844 KB Output is correct
23 Correct 460 ms 165608 KB Output is correct
24 Correct 425 ms 168548 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 120960 KB Output is correct
2 Correct 253 ms 137664 KB Output is correct
3 Correct 124 ms 105556 KB Output is correct
4 Correct 118 ms 105708 KB Output is correct
5 Execution timed out 1088 ms 245764 KB Time limit exceeded
6 Halted 0 ms 0 KB -