oj.uz

Submission #1042324

# Submission time Handle Problem Language Result Execution time Memory
1042324 2024-08-02T21:07:06 Z VMaksimoski008 Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 214452 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);
    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);
        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;
            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]);
        }

        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 200 ms 97376 KB Output is correct
2 Correct 229 ms 112840 KB Output is correct
3 Correct 114 ms 82080 KB Output is correct
4 Correct 98 ms 82156 KB Output is correct
5 Execution timed out 1032 ms 214452 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 82040 KB Output is correct
2 Correct 102 ms 81988 KB Output is correct
3 Correct 128 ms 81828 KB Output is correct
4 Correct 118 ms 87888 KB Output is correct
5 Correct 145 ms 95296 KB Output is correct
6 Correct 176 ms 95316 KB Output is correct
7 Correct 148 ms 95304 KB Output is correct
8 Correct 150 ms 95444 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 344 KB Output is correct
3 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Correct 2 ms 864 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 860 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 344 KB Output is correct
3 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Correct 2 ms 864 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 7 ms 956 KB Output is correct
17 Correct 520 ms 10176 KB Output is correct
18 Correct 445 ms 9156 KB Output is correct
19 Correct 277 ms 9424 KB Output is correct
20 Correct 251 ms 8284 KB Output is correct
21 Correct 233 ms 8136 KB Output is correct
22 Correct 805 ms 15700 KB Output is correct
23 Correct 64 ms 4184 KB Output is correct
24 Correct 398 ms 9876 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 49 ms 3664 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 344 KB Output is correct
3 Correct 1 ms 344 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 608 KB Output is correct
12 Correct 2 ms 864 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 7 ms 956 KB Output is correct
17 Correct 520 ms 10176 KB Output is correct
18 Correct 445 ms 9156 KB Output is correct
19 Correct 277 ms 9424 KB Output is correct
20 Correct 251 ms 8284 KB Output is correct
21 Correct 233 ms 8136 KB Output is correct
22 Correct 805 ms 15700 KB Output is correct
23 Correct 64 ms 4184 KB Output is correct
24 Correct 398 ms 9876 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 49 ms 3664 KB Output is correct
27 Correct 5 ms 3928 KB Output is correct
28 Execution timed out 1099 ms 44116 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 82040 KB Output is correct
2 Correct 102 ms 81988 KB Output is correct
3 Correct 128 ms 81828 KB Output is correct
4 Correct 118 ms 87888 KB Output is correct
5 Correct 145 ms 95296 KB Output is correct
6 Correct 176 ms 95316 KB Output is correct
7 Correct 148 ms 95304 KB Output is correct
8 Correct 150 ms 95444 KB Output is correct
9 Correct 227 ms 120564 KB Output is correct
10 Correct 102 ms 57164 KB Output is correct
11 Correct 223 ms 114000 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 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 114 ms 82180 KB Output is correct
19 Correct 104 ms 82220 KB Output is correct
20 Correct 95 ms 82004 KB Output is correct
21 Correct 100 ms 82000 KB Output is correct
22 Correct 291 ms 122368 KB Output is correct
23 Correct 354 ms 136952 KB Output is correct
24 Correct 356 ms 139344 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 97376 KB Output is correct
2 Correct 229 ms 112840 KB Output is correct
3 Correct 114 ms 82080 KB Output is correct
4 Correct 98 ms 82156 KB Output is correct
5 Execution timed out 1032 ms 214452 KB Time limit exceeded
6 Halted 0 ms 0 KB -