oj.uz

Submission #771643

# Submission time Handle Problem Language Result Execution time Memory
771643 2023-07-03T07:43:08 Z Magikarp4000 Catfish Farm (IOI22_fish) C++17
100 / 100
 559 ms 247440 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
#define int long long

const int MAXN = 3e5+10;
int n,m;
vector<PII> p[MAXN], v[MAXN], v2[MAXN];
vector<int> v1[MAXN];
vector<PII> dp[MAXN], dp1[MAXN], dp2[MAXN], dp3[MAXN];
int dp4[MAXN], dp5[MAXN];
US<int> vis1[MAXN];

void init() {
    FOR(i,1,n+1) {
        US<int> vis, vis2;
        FORX(u,v[i]) v2[i].PB(u);
        FORX(u,v[i+1]) {
            if (!vis2.count(u.F)) {
                vis2.insert(u.F);
                v1[i].PB(u.F);
            }
        }
        FORX(u,v[i-1]) {
            if (!vis2.count(u.F)) {
                vis2.insert(u.F);
                v1[i].PB(u.F);
            }
        }
    }
    FOR(i,1,n+1) {
        sort(ALL(v[i]));
        sort(ALL(v1[i]));
        sort(ALL(v2[i]));
    }
    FOR(i,1,n+1) {
        int cur = 0LL;
        FORX(u,v2[i]) {
            p[i].PB({u.F,cur+u.S});
            cur += u.S;
        }
    }
    dp[1].PB({0LL,0LL});
    dp1[1].PB({0LL,0LL});
    dp2[1].PB({0LL,0LL});
    int ma3 = 0LL;
    int vn = v1[1].size();
    int idx = p[2].size()-1;
    FORR(pos,vn-1,-1) {
        int j = v1[1][pos];
        while (idx > 0 && p[2][idx].F > j) idx--;
        ma3 = max(ma3, p[2][idx].S);
        dp3[1].PB({j,ma3});
    }
    reverse(ALL(dp3[1]));
}

long long max_weights(int32_t N, int32_t M, std::vector<int32_t> X, std::vector<int32_t> Y, std::vector<int32_t> W) {
    n = N; m = M;
    FOR(i,0,m) {
        if (!vis1[i+1].count(Y[i]+1)) {
            vis1[i+1].insert(Y[i]+1);
            v[X[i]+1].PB({Y[i]+1,W[i]});
        }
    }
    FOR(i,0,n+2) {
        v[i].PB({0LL,0LL});
        if (!vis1[i].count(n)) {
            vis1[i].insert(n);
            v[i].PB({n,0LL});
        }
    }
    init();
    FOR(i,2,n+1) {
        int vn = v1[i].size();
        int idx = 0, idx1 = 0, idx2 = 0, idx3 = dp3[i-1].size()-1;
        int pn = p[i].size(), p1n = p[i-1].size(), dp2n = dp2[i-1].size();
        int ma2 = 0LL;
        FOR(pos,0,vn) {
            int j = v1[i][pos];
            while (idx < pn-1 && p[i][idx+1].F <= j) idx++;
            while (idx1 < p1n-1 && p[i-1][idx1+1].F <= j) idx1++;
            while (idx2 < dp2n-1 && dp2[i-1][idx2+1].F <= j) idx2++;
            while (idx3 > 0 && dp3[i-1][idx3-1].F >= j) idx3--;
            int zero = max(dp4[i-1], dp5[i-1]+p[i-1][idx1].S);
            dp[i].PB({j, max(zero, dp2[i-1][idx2].S + p[i-1][idx1].S)});
            dp1[i].PB({j, max(zero, dp3[i-1][idx3].S - p[i][idx].S)});
            ma2 = max(ma2, dp[i][pos].S - p[i][idx].S);
            dp2[i].PB({j,ma2});
            dp4[i] = max(dp4[i], max(dp[i-1][idx2].S, dp1[i-1][idx2].S) + p[i][idx].S);
            dp5[i] = max(dp5[i], max(dp[i-1][idx2].S, dp1[i-1][idx2].S));
        }
        if (i == n) break;
        int ma3 = 0LL;
        idx = p[i+1].size()-1;
        FORR(pos,vn-1,-1) {
            int j = v1[i][pos];
            while (idx > 0 && p[i+1][idx].F > j) idx--;
            ma3 = max(ma3, max(dp[i][pos].S, dp1[i][pos].S) + p[i+1][idx].S);
            dp3[i].PB({j,ma3});
        }
        reverse(ALL(dp3[i]));
    }
    int res = -LLINF;
    FORX(u,dp[n]) res = max(res, u.S);
    FORX(u,dp1[n]) res = max(res, u.S);
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 133440 KB Output is correct
2 Correct 218 ms 142508 KB Output is correct
3 Correct 146 ms 124680 KB Output is correct
4 Correct 142 ms 124716 KB Output is correct
5 Correct 438 ms 225620 KB Output is correct
6 Correct 489 ms 245200 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 73096 KB Output is correct
2 Correct 268 ms 157252 KB Output is correct
3 Correct 347 ms 173280 KB Output is correct
4 Correct 188 ms 133428 KB Output is correct
5 Correct 213 ms 142428 KB Output is correct
6 Correct 34 ms 73044 KB Output is correct
7 Correct 35 ms 73036 KB Output is correct
8 Correct 33 ms 73080 KB Output is correct
9 Correct 33 ms 73120 KB Output is correct
10 Correct 139 ms 124684 KB Output is correct
11 Correct 143 ms 124864 KB Output is correct
12 Correct 198 ms 135428 KB Output is correct
13 Correct 227 ms 144756 KB Output is correct
14 Correct 200 ms 134768 KB Output is correct
15 Correct 227 ms 141884 KB Output is correct
16 Correct 193 ms 134568 KB Output is correct
17 Correct 228 ms 141960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 124680 KB Output is correct
2 Correct 144 ms 124684 KB Output is correct
3 Correct 174 ms 135736 KB Output is correct
4 Correct 178 ms 135872 KB Output is correct
5 Correct 225 ms 153700 KB Output is correct
6 Correct 215 ms 153728 KB Output is correct
7 Correct 226 ms 153764 KB Output is correct
8 Correct 216 ms 153704 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73120 KB Output is correct
2 Correct 37 ms 73036 KB Output is correct
3 Correct 35 ms 73076 KB Output is correct
4 Correct 35 ms 73044 KB Output is correct
5 Correct 39 ms 73136 KB Output is correct
6 Correct 36 ms 72976 KB Output is correct
7 Correct 35 ms 73084 KB Output is correct
8 Correct 34 ms 73048 KB Output is correct
9 Correct 36 ms 73272 KB Output is correct
10 Correct 36 ms 74052 KB Output is correct
11 Correct 37 ms 73484 KB Output is correct
12 Correct 37 ms 73640 KB Output is correct
13 Correct 35 ms 73172 KB Output is correct
14 Correct 40 ms 73684 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73120 KB Output is correct
2 Correct 37 ms 73036 KB Output is correct
3 Correct 35 ms 73076 KB Output is correct
4 Correct 35 ms 73044 KB Output is correct
5 Correct 39 ms 73136 KB Output is correct
6 Correct 36 ms 72976 KB Output is correct
7 Correct 35 ms 73084 KB Output is correct
8 Correct 34 ms 73048 KB Output is correct
9 Correct 36 ms 73272 KB Output is correct
10 Correct 36 ms 74052 KB Output is correct
11 Correct 37 ms 73484 KB Output is correct
12 Correct 37 ms 73640 KB Output is correct
13 Correct 35 ms 73172 KB Output is correct
14 Correct 40 ms 73684 KB Output is correct
15 Correct 35 ms 73280 KB Output is correct
16 Correct 37 ms 73940 KB Output is correct
17 Correct 73 ms 89796 KB Output is correct
18 Correct 72 ms 90664 KB Output is correct
19 Correct 72 ms 90568 KB Output is correct
20 Correct 71 ms 89624 KB Output is correct
21 Correct 76 ms 89512 KB Output is correct
22 Correct 104 ms 105992 KB Output is correct
23 Correct 45 ms 76932 KB Output is correct
24 Correct 63 ms 85232 KB Output is correct
25 Correct 37 ms 73732 KB Output is correct
26 Correct 44 ms 76364 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73120 KB Output is correct
2 Correct 37 ms 73036 KB Output is correct
3 Correct 35 ms 73076 KB Output is correct
4 Correct 35 ms 73044 KB Output is correct
5 Correct 39 ms 73136 KB Output is correct
6 Correct 36 ms 72976 KB Output is correct
7 Correct 35 ms 73084 KB Output is correct
8 Correct 34 ms 73048 KB Output is correct
9 Correct 36 ms 73272 KB Output is correct
10 Correct 36 ms 74052 KB Output is correct
11 Correct 37 ms 73484 KB Output is correct
12 Correct 37 ms 73640 KB Output is correct
13 Correct 35 ms 73172 KB Output is correct
14 Correct 40 ms 73684 KB Output is correct
15 Correct 35 ms 73280 KB Output is correct
16 Correct 37 ms 73940 KB Output is correct
17 Correct 73 ms 89796 KB Output is correct
18 Correct 72 ms 90664 KB Output is correct
19 Correct 72 ms 90568 KB Output is correct
20 Correct 71 ms 89624 KB Output is correct
21 Correct 76 ms 89512 KB Output is correct
22 Correct 104 ms 105992 KB Output is correct
23 Correct 45 ms 76932 KB Output is correct
24 Correct 63 ms 85232 KB Output is correct
25 Correct 37 ms 73732 KB Output is correct
26 Correct 44 ms 76364 KB Output is correct
27 Correct 40 ms 75476 KB Output is correct
28 Correct 211 ms 148724 KB Output is correct
29 Correct 318 ms 176972 KB Output is correct
30 Correct 327 ms 195176 KB Output is correct
31 Correct 332 ms 195172 KB Output is correct
32 Correct 268 ms 177360 KB Output is correct
33 Correct 357 ms 195148 KB Output is correct
34 Correct 330 ms 195156 KB Output is correct
35 Correct 153 ms 122600 KB Output is correct
36 Correct 312 ms 189012 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 124680 KB Output is correct
2 Correct 144 ms 124684 KB Output is correct
3 Correct 174 ms 135736 KB Output is correct
4 Correct 178 ms 135872 KB Output is correct
5 Correct 225 ms 153700 KB Output is correct
6 Correct 215 ms 153728 KB Output is correct
7 Correct 226 ms 153764 KB Output is correct
8 Correct 216 ms 153704 KB Output is correct
9 Correct 232 ms 153644 KB Output is correct
10 Correct 165 ms 122408 KB Output is correct
11 Correct 329 ms 171596 KB Output is correct
12 Correct 38 ms 73120 KB Output is correct
13 Correct 37 ms 73128 KB Output is correct
14 Correct 35 ms 73044 KB Output is correct
15 Correct 36 ms 73008 KB Output is correct
16 Correct 37 ms 73016 KB Output is correct
17 Correct 36 ms 72988 KB Output is correct
18 Correct 140 ms 124668 KB Output is correct
19 Correct 143 ms 124724 KB Output is correct
20 Correct 142 ms 124756 KB Output is correct
21 Correct 146 ms 124788 KB Output is correct
22 Correct 265 ms 158372 KB Output is correct
23 Correct 362 ms 196356 KB Output is correct
24 Correct 394 ms 199884 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 133440 KB Output is correct
2 Correct 218 ms 142508 KB Output is correct
3 Correct 146 ms 124680 KB Output is correct
4 Correct 142 ms 124716 KB Output is correct
5 Correct 438 ms 225620 KB Output is correct
6 Correct 489 ms 245200 KB Output is correct
7 Correct 34 ms 73096 KB Output is correct
8 Correct 268 ms 157252 KB Output is correct
9 Correct 347 ms 173280 KB Output is correct
10 Correct 188 ms 133428 KB Output is correct
11 Correct 213 ms 142428 KB Output is correct
12 Correct 34 ms 73044 KB Output is correct
13 Correct 35 ms 73036 KB Output is correct
14 Correct 33 ms 73080 KB Output is correct
15 Correct 33 ms 73120 KB Output is correct
16 Correct 139 ms 124684 KB Output is correct
17 Correct 143 ms 124864 KB Output is correct
18 Correct 198 ms 135428 KB Output is correct
19 Correct 227 ms 144756 KB Output is correct
20 Correct 200 ms 134768 KB Output is correct
21 Correct 227 ms 141884 KB Output is correct
22 Correct 193 ms 134568 KB Output is correct
23 Correct 228 ms 141960 KB Output is correct
24 Correct 138 ms 124680 KB Output is correct
25 Correct 144 ms 124684 KB Output is correct
26 Correct 174 ms 135736 KB Output is correct
27 Correct 178 ms 135872 KB Output is correct
28 Correct 225 ms 153700 KB Output is correct
29 Correct 215 ms 153728 KB Output is correct
30 Correct 226 ms 153764 KB Output is correct
31 Correct 216 ms 153704 KB Output is correct
32 Correct 36 ms 73120 KB Output is correct
33 Correct 37 ms 73036 KB Output is correct
34 Correct 35 ms 73076 KB Output is correct
35 Correct 35 ms 73044 KB Output is correct
36 Correct 39 ms 73136 KB Output is correct
37 Correct 36 ms 72976 KB Output is correct
38 Correct 35 ms 73084 KB Output is correct
39 Correct 34 ms 73048 KB Output is correct
40 Correct 36 ms 73272 KB Output is correct
41 Correct 36 ms 74052 KB Output is correct
42 Correct 37 ms 73484 KB Output is correct
43 Correct 37 ms 73640 KB Output is correct
44 Correct 35 ms 73172 KB Output is correct
45 Correct 40 ms 73684 KB Output is correct
46 Correct 35 ms 73280 KB Output is correct
47 Correct 37 ms 73940 KB Output is correct
48 Correct 73 ms 89796 KB Output is correct
49 Correct 72 ms 90664 KB Output is correct
50 Correct 72 ms 90568 KB Output is correct
51 Correct 71 ms 89624 KB Output is correct
52 Correct 76 ms 89512 KB Output is correct
53 Correct 104 ms 105992 KB Output is correct
54 Correct 45 ms 76932 KB Output is correct
55 Correct 63 ms 85232 KB Output is correct
56 Correct 37 ms 73732 KB Output is correct
57 Correct 44 ms 76364 KB Output is correct
58 Correct 40 ms 75476 KB Output is correct
59 Correct 211 ms 148724 KB Output is correct
60 Correct 318 ms 176972 KB Output is correct
61 Correct 327 ms 195176 KB Output is correct
62 Correct 332 ms 195172 KB Output is correct
63 Correct 268 ms 177360 KB Output is correct
64 Correct 357 ms 195148 KB Output is correct
65 Correct 330 ms 195156 KB Output is correct
66 Correct 153 ms 122600 KB Output is correct
67 Correct 312 ms 189012 KB Output is correct
68 Correct 232 ms 153644 KB Output is correct
69 Correct 165 ms 122408 KB Output is correct
70 Correct 329 ms 171596 KB Output is correct
71 Correct 38 ms 73120 KB Output is correct
72 Correct 37 ms 73128 KB Output is correct
73 Correct 35 ms 73044 KB Output is correct
74 Correct 36 ms 73008 KB Output is correct
75 Correct 37 ms 73016 KB Output is correct
76 Correct 36 ms 72988 KB Output is correct
77 Correct 140 ms 124668 KB Output is correct
78 Correct 143 ms 124724 KB Output is correct
79 Correct 142 ms 124756 KB Output is correct
80 Correct 146 ms 124788 KB Output is correct
81 Correct 265 ms 158372 KB Output is correct
82 Correct 362 ms 196356 KB Output is correct
83 Correct 394 ms 199884 KB Output is correct
84 Correct 432 ms 215560 KB Output is correct
85 Correct 424 ms 220856 KB Output is correct
86 Correct 559 ms 242560 KB Output is correct
87 Correct 556 ms 247172 KB Output is correct
88 Correct 36 ms 73044 KB Output is correct
89 Correct 559 ms 247440 KB Output is correct
90 Correct 497 ms 237768 KB Output is correct
91 Correct 458 ms 224592 KB Output is correct