oj.uz

Submission #1110986

# Submission time Handle Problem Language Result Execution time Memory
1110986 2024-11-11T08:47:19 Z jerzyk Catfish Farm (IOI22_fish) C++17
100 / 100
 400 ms 229276 KB 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
vector<pair<int, ll>> cat[N];
vector<int> dpv[N];
vector<ll> dp[N][2], sl[N], as[N], sr[N];

void CntS(int n)
{
    for(int l = 0; l <= n; ++l)
    {
        int j1 = 0, j2 = 0, j3 = 0;
        ll s1 = 0, s2 = 0, s3 = 0;
        //cerr << l << " " << dpv[l].size() << " " << as[l].size() << "\n";
        for(int i = 1; i < (int)dpv[l].size(); ++i)
        {
            while(l > 0 && j1 < (int)cat[l - 1].size() - 1 && cat[l - 1][j1 + 1].st <= dpv[l][i])
            {
                ++j1;
                s1 += cat[l - 1][j1].nd;
            }
            while(j2 < (int)cat[l].size() - 1 && cat[l][j2 + 1].st <= dpv[l][i])
            {
                ++j2;
                s2 += cat[l][j2].nd;
            }
            while(j3 < (int)cat[l + 1].size() - 1 && cat[l + 1][j3 + 1].st <= dpv[l][i])
            {
                ++j3;
                s3 += cat[l + 1][j3].nd;
            }
            //cerr << i << " ";
            sl[l][i] = s1; as[l][i] = s2; sr[l][i] = s3;
        }
    }
}

void Do1()
{
    for(int i = 1; i < (int)dpv[1].size(); ++i)
    {
        dp[1][0][i] = sr[1][i];
        //dp[1][2][i] = sr[1][i];
    }
}

void CntDP(int n)
{
    Do1();
    for(int l = 2; l <= n; ++l)
    {
        ll ma = -I, mb = -I;
        for(int j = 0; j < (int)dpv[l - 2].size(); ++j)
        {
            ma = max(ma, dp[l - 2][0][j] - sr[l - 2][j]);
            mb = max(mb, dp[l - 2][0][j]);
        }
        ll m1 = -I;
        int j1 = -1;
        for(int i = 0; i < (int)dpv[l].size(); ++i)
        {
            dp[l][0][i] = max(ma + sl[l][i], mb);
            dp[l][1][i] = dp[l][0][i];
            while(j1 < (int)dpv[l - 1].size() - 1 && dpv[l - 1][j1 + 1] <= dpv[l][i])
            {
                ++j1;
                m1 = max(m1, dp[l - 1][1][j1] - as[l - 1][j1]);
            }
            dp[l][1][i] = max(dp[l][1][i], m1 + sl[l][i]);
        }
        m1 = -I;
        j1 = (int)dpv[l - 1].size();
        for(int i = (int)dpv[l].size() - 1; i >= 0; --i)
        {
            while(j1 > 0 && dpv[l - 1][j1 - 1] >= dpv[l][i])
            {
                --j1;
                m1 = max(m1, dp[l - 1][0][j1]);
            }
            dp[l][0][i] = max(dp[l][0][i], m1 - as[l][i]);
            dp[l][0][i] = max(dp[l][0][i], dp[l][1][i]) + sr[l][i];
        }
    }
}

long long max_weights(int _N, int _M, vector<int> X, vector<int> Y, vector<int> W)
{
    int n = _N, m = _M;
    for(int i = 0; i < m; ++i)
        {X[i] += 1; Y[i] += 1;}
    for(int i = 0; i <= n + 1; ++i)
    {
        dpv[i].pb(0);
        cat[i].pb(make_pair(0, 0LL));
    }
    for(int i = 0; i < m; ++i)
    {
        cat[X[i]].pb(make_pair(Y[i], W[i]));
        if(X[i] > 1)
            dpv[X[i] - 1].pb(Y[i]);
        if(X[i] < N)
            dpv[X[i] + 1].pb(Y[i]);
    }
    for(int l = 0; l <= n; ++l)
    {
        sort(cat[l].begin(), cat[l].end());
        sort(dpv[l].begin(), dpv[l].end());
        vector<int> nw;
        for(int i = 0; i < (int)dpv[l].size(); ++i)
            if(i == 0 || dpv[l][i] != dpv[l][i - 1])
                nw.pb(dpv[l][i]);
        dpv[l] = nw;
        for(int i = 0; i < (int)dpv[l].size(); ++i)
            dp[l][0].pb(0LL);
        dp[l][1] = dp[l][0];
        sl[l] = dp[l][0]; as[l] = dp[l][0]; sr[l] = dp[l][0];
    }
    CntS(n);
    CntDP(n);
    //cerr << "XD\n";
    ll ans = 0LL;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < (int)dpv[i].size(); ++j)
            ans = max(ans, dp[i][0][j]);
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 191124 KB Output is correct
2 Correct 144 ms 194860 KB Output is correct
3 Correct 99 ms 186696 KB Output is correct
4 Correct 114 ms 186612 KB Output is correct
5 Correct 265 ms 225428 KB Output is correct
6 Correct 400 ms 225644 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 164680 KB Output is correct
2 Correct 180 ms 203044 KB Output is correct
3 Correct 202 ms 211004 KB Output is correct
4 Correct 149 ms 192376 KB Output is correct
5 Correct 175 ms 196628 KB Output is correct
6 Correct 76 ms 164684 KB Output is correct
7 Correct 85 ms 164680 KB Output is correct
8 Correct 84 ms 164680 KB Output is correct
9 Correct 77 ms 164688 KB Output is correct
10 Correct 131 ms 186696 KB Output is correct
11 Correct 142 ms 186696 KB Output is correct
12 Correct 159 ms 196904 KB Output is correct
13 Correct 171 ms 200776 KB Output is correct
14 Correct 176 ms 194248 KB Output is correct
15 Correct 179 ms 197568 KB Output is correct
16 Correct 150 ms 194332 KB Output is correct
17 Correct 152 ms 197696 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 186696 KB Output is correct
2 Correct 114 ms 186788 KB Output is correct
3 Correct 144 ms 186444 KB Output is correct
4 Correct 131 ms 187976 KB Output is correct
5 Correct 187 ms 190540 KB Output is correct
6 Correct 171 ms 190460 KB Output is correct
7 Correct 172 ms 190536 KB Output is correct
8 Correct 195 ms 190536 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164576 KB Output is correct
2 Correct 75 ms 164680 KB Output is correct
3 Correct 81 ms 164712 KB Output is correct
4 Correct 89 ms 164760 KB Output is correct
5 Correct 85 ms 164680 KB Output is correct
6 Correct 93 ms 164680 KB Output is correct
7 Correct 79 ms 164680 KB Output is correct
8 Correct 78 ms 164628 KB Output is correct
9 Correct 80 ms 164680 KB Output is correct
10 Correct 76 ms 164936 KB Output is correct
11 Correct 75 ms 164680 KB Output is correct
12 Correct 77 ms 164872 KB Output is correct
13 Correct 91 ms 164764 KB Output is correct
14 Correct 78 ms 164776 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164576 KB Output is correct
2 Correct 75 ms 164680 KB Output is correct
3 Correct 81 ms 164712 KB Output is correct
4 Correct 89 ms 164760 KB Output is correct
5 Correct 85 ms 164680 KB Output is correct
6 Correct 93 ms 164680 KB Output is correct
7 Correct 79 ms 164680 KB Output is correct
8 Correct 78 ms 164628 KB Output is correct
9 Correct 80 ms 164680 KB Output is correct
10 Correct 76 ms 164936 KB Output is correct
11 Correct 75 ms 164680 KB Output is correct
12 Correct 77 ms 164872 KB Output is correct
13 Correct 91 ms 164764 KB Output is correct
14 Correct 78 ms 164776 KB Output is correct
15 Correct 70 ms 164696 KB Output is correct
16 Correct 67 ms 164936 KB Output is correct
17 Correct 94 ms 169720 KB Output is correct
18 Correct 118 ms 170228 KB Output is correct
19 Correct 99 ms 170056 KB Output is correct
20 Correct 95 ms 169832 KB Output is correct
21 Correct 99 ms 169800 KB Output is correct
22 Correct 113 ms 174580 KB Output is correct
23 Correct 88 ms 165960 KB Output is correct
24 Correct 92 ms 168520 KB Output is correct
25 Correct 78 ms 164916 KB Output is correct
26 Correct 80 ms 165864 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 164576 KB Output is correct
2 Correct 75 ms 164680 KB Output is correct
3 Correct 81 ms 164712 KB Output is correct
4 Correct 89 ms 164760 KB Output is correct
5 Correct 85 ms 164680 KB Output is correct
6 Correct 93 ms 164680 KB Output is correct
7 Correct 79 ms 164680 KB Output is correct
8 Correct 78 ms 164628 KB Output is correct
9 Correct 80 ms 164680 KB Output is correct
10 Correct 76 ms 164936 KB Output is correct
11 Correct 75 ms 164680 KB Output is correct
12 Correct 77 ms 164872 KB Output is correct
13 Correct 91 ms 164764 KB Output is correct
14 Correct 78 ms 164776 KB Output is correct
15 Correct 70 ms 164696 KB Output is correct
16 Correct 67 ms 164936 KB Output is correct
17 Correct 94 ms 169720 KB Output is correct
18 Correct 118 ms 170228 KB Output is correct
19 Correct 99 ms 170056 KB Output is correct
20 Correct 95 ms 169832 KB Output is correct
21 Correct 99 ms 169800 KB Output is correct
22 Correct 113 ms 174580 KB Output is correct
23 Correct 88 ms 165960 KB Output is correct
24 Correct 92 ms 168520 KB Output is correct
25 Correct 78 ms 164916 KB Output is correct
26 Correct 80 ms 165864 KB Output is correct
27 Correct 82 ms 165560 KB Output is correct
28 Correct 164 ms 189140 KB Output is correct
29 Correct 213 ms 200776 KB Output is correct
30 Correct 220 ms 211564 KB Output is correct
31 Correct 213 ms 211596 KB Output is correct
32 Correct 189 ms 202828 KB Output is correct
33 Correct 239 ms 211784 KB Output is correct
34 Correct 229 ms 211784 KB Output is correct
35 Correct 136 ms 182600 KB Output is correct
36 Correct 230 ms 211156 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 186696 KB Output is correct
2 Correct 114 ms 186788 KB Output is correct
3 Correct 144 ms 186444 KB Output is correct
4 Correct 131 ms 187976 KB Output is correct
5 Correct 187 ms 190540 KB Output is correct
6 Correct 171 ms 190460 KB Output is correct
7 Correct 172 ms 190536 KB Output is correct
8 Correct 195 ms 190536 KB Output is correct
9 Correct 178 ms 192052 KB Output is correct
10 Correct 165 ms 182532 KB Output is correct
11 Correct 241 ms 200264 KB Output is correct
12 Correct 91 ms 164680 KB Output is correct
13 Correct 83 ms 164752 KB Output is correct
14 Correct 89 ms 164720 KB Output is correct
15 Correct 78 ms 164680 KB Output is correct
16 Correct 83 ms 164680 KB Output is correct
17 Correct 89 ms 164680 KB Output is correct
18 Correct 117 ms 186632 KB Output is correct
19 Correct 118 ms 186696 KB Output is correct
20 Correct 128 ms 186684 KB Output is correct
21 Correct 110 ms 186496 KB Output is correct
22 Correct 190 ms 194888 KB Output is correct
23 Correct 284 ms 207348 KB Output is correct
24 Correct 248 ms 209608 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 191124 KB Output is correct
2 Correct 144 ms 194860 KB Output is correct
3 Correct 99 ms 186696 KB Output is correct
4 Correct 114 ms 186612 KB Output is correct
5 Correct 265 ms 225428 KB Output is correct
6 Correct 400 ms 225644 KB Output is correct
7 Correct 72 ms 164680 KB Output is correct
8 Correct 180 ms 203044 KB Output is correct
9 Correct 202 ms 211004 KB Output is correct
10 Correct 149 ms 192376 KB Output is correct
11 Correct 175 ms 196628 KB Output is correct
12 Correct 76 ms 164684 KB Output is correct
13 Correct 85 ms 164680 KB Output is correct
14 Correct 84 ms 164680 KB Output is correct
15 Correct 77 ms 164688 KB Output is correct
16 Correct 131 ms 186696 KB Output is correct
17 Correct 142 ms 186696 KB Output is correct
18 Correct 159 ms 196904 KB Output is correct
19 Correct 171 ms 200776 KB Output is correct
20 Correct 176 ms 194248 KB Output is correct
21 Correct 179 ms 197568 KB Output is correct
22 Correct 150 ms 194332 KB Output is correct
23 Correct 152 ms 197696 KB Output is correct
24 Correct 115 ms 186696 KB Output is correct
25 Correct 114 ms 186788 KB Output is correct
26 Correct 144 ms 186444 KB Output is correct
27 Correct 131 ms 187976 KB Output is correct
28 Correct 187 ms 190540 KB Output is correct
29 Correct 171 ms 190460 KB Output is correct
30 Correct 172 ms 190536 KB Output is correct
31 Correct 195 ms 190536 KB Output is correct
32 Correct 83 ms 164576 KB Output is correct
33 Correct 75 ms 164680 KB Output is correct
34 Correct 81 ms 164712 KB Output is correct
35 Correct 89 ms 164760 KB Output is correct
36 Correct 85 ms 164680 KB Output is correct
37 Correct 93 ms 164680 KB Output is correct
38 Correct 79 ms 164680 KB Output is correct
39 Correct 78 ms 164628 KB Output is correct
40 Correct 80 ms 164680 KB Output is correct
41 Correct 76 ms 164936 KB Output is correct
42 Correct 75 ms 164680 KB Output is correct
43 Correct 77 ms 164872 KB Output is correct
44 Correct 91 ms 164764 KB Output is correct
45 Correct 78 ms 164776 KB Output is correct
46 Correct 70 ms 164696 KB Output is correct
47 Correct 67 ms 164936 KB Output is correct
48 Correct 94 ms 169720 KB Output is correct
49 Correct 118 ms 170228 KB Output is correct
50 Correct 99 ms 170056 KB Output is correct
51 Correct 95 ms 169832 KB Output is correct
52 Correct 99 ms 169800 KB Output is correct
53 Correct 113 ms 174580 KB Output is correct
54 Correct 88 ms 165960 KB Output is correct
55 Correct 92 ms 168520 KB Output is correct
56 Correct 78 ms 164916 KB Output is correct
57 Correct 80 ms 165864 KB Output is correct
58 Correct 82 ms 165560 KB Output is correct
59 Correct 164 ms 189140 KB Output is correct
60 Correct 213 ms 200776 KB Output is correct
61 Correct 220 ms 211564 KB Output is correct
62 Correct 213 ms 211596 KB Output is correct
63 Correct 189 ms 202828 KB Output is correct
64 Correct 239 ms 211784 KB Output is correct
65 Correct 229 ms 211784 KB Output is correct
66 Correct 136 ms 182600 KB Output is correct
67 Correct 230 ms 211156 KB Output is correct
68 Correct 178 ms 192052 KB Output is correct
69 Correct 165 ms 182532 KB Output is correct
70 Correct 241 ms 200264 KB Output is correct
71 Correct 91 ms 164680 KB Output is correct
72 Correct 83 ms 164752 KB Output is correct
73 Correct 89 ms 164720 KB Output is correct
74 Correct 78 ms 164680 KB Output is correct
75 Correct 83 ms 164680 KB Output is correct
76 Correct 89 ms 164680 KB Output is correct
77 Correct 117 ms 186632 KB Output is correct
78 Correct 118 ms 186696 KB Output is correct
79 Correct 128 ms 186684 KB Output is correct
80 Correct 110 ms 186496 KB Output is correct
81 Correct 190 ms 194888 KB Output is correct
82 Correct 284 ms 207348 KB Output is correct
83 Correct 248 ms 209608 KB Output is correct
84 Correct 295 ms 227668 KB Output is correct
85 Correct 283 ms 229148 KB Output is correct
86 Correct 373 ms 227236 KB Output is correct
87 Correct 394 ms 229276 KB Output is correct
88 Correct 87 ms 164680 KB Output is correct
89 Correct 398 ms 229024 KB Output is correct
90 Correct 324 ms 227912 KB Output is correct
91 Correct 281 ms 223560 KB Output is correct