oj.uz

Submission #1110981

# Submission time Handle Problem Language Result Execution time Memory
1110981 2024-11-11T08:34:46 Z jerzyk Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 232264 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]);
        }
        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];
            for(int j = 0; j < (int)dpv[l - 1].size(); ++j)
            {
                if(dpv[l - 1][j] <= dpv[l][i])
                    dp[l][1][i] = max(dp[l][1][i], dp[l - 1][1][j] + sl[l][i] - as[l - 1][j]);
                if(dpv[l - 1][j] >= dpv[l][i])
                    dp[l][0][i] = max(dp[l][0][i], dp[l - 1][0][j] - as[l][i]);
            }
            dp[l][0][i] = max(dp[l][0][i], dp[l][1][i]) + sr[l][i];
            //cerr << l << " " << i << " " << dp[l][0][i] << " " << dp[l][1][i] << "\n";
        }
    }
}

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 183 ms 190968 KB Output is correct
2 Correct 193 ms 195256 KB Output is correct
3 Correct 147 ms 186696 KB Output is correct
4 Correct 144 ms 186700 KB Output is correct
5 Correct 305 ms 225500 KB Output is correct
6 Correct 426 ms 232264 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 164680 KB Output is correct
2 Execution timed out 1071 ms 201508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 186508 KB Output is correct
2 Correct 165 ms 186700 KB Output is correct
3 Correct 167 ms 187208 KB Output is correct
4 Correct 171 ms 187976 KB Output is correct
5 Correct 205 ms 190536 KB Output is correct
6 Correct 214 ms 190432 KB Output is correct
7 Correct 214 ms 190640 KB Output is correct
8 Correct 217 ms 190452 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 164660 KB Output is correct
2 Correct 104 ms 164668 KB Output is correct
3 Correct 113 ms 164592 KB Output is correct
4 Correct 102 ms 164724 KB Output is correct
5 Correct 99 ms 164712 KB Output is correct
6 Correct 99 ms 164680 KB Output is correct
7 Correct 104 ms 164600 KB Output is correct
8 Correct 124 ms 164692 KB Output is correct
9 Correct 106 ms 164680 KB Output is correct
10 Correct 115 ms 165084 KB Output is correct
11 Correct 109 ms 164680 KB Output is correct
12 Correct 118 ms 164936 KB Output is correct
13 Correct 101 ms 164680 KB Output is correct
14 Correct 107 ms 164936 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 164660 KB Output is correct
2 Correct 104 ms 164668 KB Output is correct
3 Correct 113 ms 164592 KB Output is correct
4 Correct 102 ms 164724 KB Output is correct
5 Correct 99 ms 164712 KB Output is correct
6 Correct 99 ms 164680 KB Output is correct
7 Correct 104 ms 164600 KB Output is correct
8 Correct 124 ms 164692 KB Output is correct
9 Correct 106 ms 164680 KB Output is correct
10 Correct 115 ms 165084 KB Output is correct
11 Correct 109 ms 164680 KB Output is correct
12 Correct 118 ms 164936 KB Output is correct
13 Correct 101 ms 164680 KB Output is correct
14 Correct 107 ms 164936 KB Output is correct
15 Correct 120 ms 164680 KB Output is correct
16 Correct 108 ms 164976 KB Output is correct
17 Correct 154 ms 170056 KB Output is correct
18 Correct 152 ms 170208 KB Output is correct
19 Correct 130 ms 170056 KB Output is correct
20 Correct 130 ms 169800 KB Output is correct
21 Correct 129 ms 169800 KB Output is correct
22 Correct 174 ms 174672 KB Output is correct
23 Correct 105 ms 166216 KB Output is correct
24 Correct 138 ms 168668 KB Output is correct
25 Correct 104 ms 164936 KB Output is correct
26 Correct 110 ms 165960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 164660 KB Output is correct
2 Correct 104 ms 164668 KB Output is correct
3 Correct 113 ms 164592 KB Output is correct
4 Correct 102 ms 164724 KB Output is correct
5 Correct 99 ms 164712 KB Output is correct
6 Correct 99 ms 164680 KB Output is correct
7 Correct 104 ms 164600 KB Output is correct
8 Correct 124 ms 164692 KB Output is correct
9 Correct 106 ms 164680 KB Output is correct
10 Correct 115 ms 165084 KB Output is correct
11 Correct 109 ms 164680 KB Output is correct
12 Correct 118 ms 164936 KB Output is correct
13 Correct 101 ms 164680 KB Output is correct
14 Correct 107 ms 164936 KB Output is correct
15 Correct 120 ms 164680 KB Output is correct
16 Correct 108 ms 164976 KB Output is correct
17 Correct 154 ms 170056 KB Output is correct
18 Correct 152 ms 170208 KB Output is correct
19 Correct 130 ms 170056 KB Output is correct
20 Correct 130 ms 169800 KB Output is correct
21 Correct 129 ms 169800 KB Output is correct
22 Correct 174 ms 174672 KB Output is correct
23 Correct 105 ms 166216 KB Output is correct
24 Correct 138 ms 168668 KB Output is correct
25 Correct 104 ms 164936 KB Output is correct
26 Correct 110 ms 165960 KB Output is correct
27 Correct 107 ms 165448 KB Output is correct
28 Correct 387 ms 189084 KB Output is correct
29 Execution timed out 1079 ms 200776 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 186508 KB Output is correct
2 Correct 165 ms 186700 KB Output is correct
3 Correct 167 ms 187208 KB Output is correct
4 Correct 171 ms 187976 KB Output is correct
5 Correct 205 ms 190536 KB Output is correct
6 Correct 214 ms 190432 KB Output is correct
7 Correct 214 ms 190640 KB Output is correct
8 Correct 217 ms 190452 KB Output is correct
9 Correct 217 ms 193100 KB Output is correct
10 Correct 220 ms 182512 KB Output is correct
11 Correct 299 ms 200268 KB Output is correct
12 Correct 109 ms 164692 KB Output is correct
13 Correct 117 ms 164776 KB Output is correct
14 Correct 104 ms 164660 KB Output is correct
15 Correct 112 ms 164772 KB Output is correct
16 Correct 107 ms 164680 KB Output is correct
17 Correct 105 ms 164728 KB Output is correct
18 Correct 155 ms 186664 KB Output is correct
19 Correct 143 ms 186696 KB Output is correct
20 Correct 145 ms 186696 KB Output is correct
21 Correct 140 ms 186696 KB Output is correct
22 Correct 228 ms 195656 KB Output is correct
23 Correct 285 ms 207300 KB Output is correct
24 Correct 313 ms 209632 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 190968 KB Output is correct
2 Correct 193 ms 195256 KB Output is correct
3 Correct 147 ms 186696 KB Output is correct
4 Correct 144 ms 186700 KB Output is correct
5 Correct 305 ms 225500 KB Output is correct
6 Correct 426 ms 232264 KB Output is correct
7 Correct 104 ms 164680 KB Output is correct
8 Execution timed out 1071 ms 201508 KB Time limit exceeded
9 Halted 0 ms 0 KB -