oj.uz

Submission #1110985

# Submission time Handle Problem Language Result Execution time Memory
1110985 2024-11-11T08:44:00 Z jerzyk Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 225680 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]);
            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 115 ms 190972 KB Output is correct
2 Correct 130 ms 195256 KB Output is correct
3 Correct 95 ms 186720 KB Output is correct
4 Correct 96 ms 186588 KB Output is correct
5 Correct 258 ms 225588 KB Output is correct
6 Correct 357 ms 225680 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 164564 KB Output is correct
2 Execution timed out 1063 ms 201512 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 186696 KB Output is correct
2 Correct 96 ms 186696 KB Output is correct
3 Correct 137 ms 186396 KB Output is correct
4 Correct 158 ms 187988 KB Output is correct
5 Correct 170 ms 190516 KB Output is correct
6 Correct 174 ms 190536 KB Output is correct
7 Correct 170 ms 190536 KB Output is correct
8 Correct 188 ms 190536 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164680 KB Output is correct
2 Correct 65 ms 164680 KB Output is correct
3 Correct 71 ms 164680 KB Output is correct
4 Correct 68 ms 164680 KB Output is correct
5 Correct 83 ms 164680 KB Output is correct
6 Correct 85 ms 164680 KB Output is correct
7 Correct 93 ms 164692 KB Output is correct
8 Correct 72 ms 164772 KB Output is correct
9 Correct 77 ms 164680 KB Output is correct
10 Correct 77 ms 164936 KB Output is correct
11 Correct 74 ms 164680 KB Output is correct
12 Correct 73 ms 164904 KB Output is correct
13 Correct 85 ms 164804 KB Output is correct
14 Correct 71 ms 164936 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164680 KB Output is correct
2 Correct 65 ms 164680 KB Output is correct
3 Correct 71 ms 164680 KB Output is correct
4 Correct 68 ms 164680 KB Output is correct
5 Correct 83 ms 164680 KB Output is correct
6 Correct 85 ms 164680 KB Output is correct
7 Correct 93 ms 164692 KB Output is correct
8 Correct 72 ms 164772 KB Output is correct
9 Correct 77 ms 164680 KB Output is correct
10 Correct 77 ms 164936 KB Output is correct
11 Correct 74 ms 164680 KB Output is correct
12 Correct 73 ms 164904 KB Output is correct
13 Correct 85 ms 164804 KB Output is correct
14 Correct 71 ms 164936 KB Output is correct
15 Correct 75 ms 164716 KB Output is correct
16 Correct 74 ms 165068 KB Output is correct
17 Correct 103 ms 169564 KB Output is correct
18 Correct 116 ms 170188 KB Output is correct
19 Correct 95 ms 170052 KB Output is correct
20 Correct 101 ms 169844 KB Output is correct
21 Correct 92 ms 169716 KB Output is correct
22 Correct 120 ms 174772 KB Output is correct
23 Correct 83 ms 165984 KB Output is correct
24 Correct 87 ms 168520 KB Output is correct
25 Correct 73 ms 164936 KB Output is correct
26 Correct 77 ms 165960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164680 KB Output is correct
2 Correct 65 ms 164680 KB Output is correct
3 Correct 71 ms 164680 KB Output is correct
4 Correct 68 ms 164680 KB Output is correct
5 Correct 83 ms 164680 KB Output is correct
6 Correct 85 ms 164680 KB Output is correct
7 Correct 93 ms 164692 KB Output is correct
8 Correct 72 ms 164772 KB Output is correct
9 Correct 77 ms 164680 KB Output is correct
10 Correct 77 ms 164936 KB Output is correct
11 Correct 74 ms 164680 KB Output is correct
12 Correct 73 ms 164904 KB Output is correct
13 Correct 85 ms 164804 KB Output is correct
14 Correct 71 ms 164936 KB Output is correct
15 Correct 75 ms 164716 KB Output is correct
16 Correct 74 ms 165068 KB Output is correct
17 Correct 103 ms 169564 KB Output is correct
18 Correct 116 ms 170188 KB Output is correct
19 Correct 95 ms 170052 KB Output is correct
20 Correct 101 ms 169844 KB Output is correct
21 Correct 92 ms 169716 KB Output is correct
22 Correct 120 ms 174772 KB Output is correct
23 Correct 83 ms 165984 KB Output is correct
24 Correct 87 ms 168520 KB Output is correct
25 Correct 73 ms 164936 KB Output is correct
26 Correct 77 ms 165960 KB Output is correct
27 Correct 67 ms 165448 KB Output is correct
28 Correct 296 ms 189248 KB Output is correct
29 Execution timed out 1055 ms 201016 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 186696 KB Output is correct
2 Correct 96 ms 186696 KB Output is correct
3 Correct 137 ms 186396 KB Output is correct
4 Correct 158 ms 187988 KB Output is correct
5 Correct 170 ms 190516 KB Output is correct
6 Correct 174 ms 190536 KB Output is correct
7 Correct 170 ms 190536 KB Output is correct
8 Correct 188 ms 190536 KB Output is correct
9 Correct 174 ms 192072 KB Output is correct
10 Correct 144 ms 182348 KB Output is correct
11 Correct 226 ms 200264 KB Output is correct
12 Correct 66 ms 164680 KB Output is correct
13 Correct 72 ms 164680 KB Output is correct
14 Correct 65 ms 164680 KB Output is correct
15 Correct 71 ms 164712 KB Output is correct
16 Correct 77 ms 164680 KB Output is correct
17 Correct 84 ms 164688 KB Output is correct
18 Correct 112 ms 186604 KB Output is correct
19 Correct 115 ms 186704 KB Output is correct
20 Correct 116 ms 186712 KB Output is correct
21 Correct 123 ms 186696 KB Output is correct
22 Correct 191 ms 194888 KB Output is correct
23 Correct 289 ms 209520 KB Output is correct
24 Correct 263 ms 213044 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 190972 KB Output is correct
2 Correct 130 ms 195256 KB Output is correct
3 Correct 95 ms 186720 KB Output is correct
4 Correct 96 ms 186588 KB Output is correct
5 Correct 258 ms 225588 KB Output is correct
6 Correct 357 ms 225680 KB Output is correct
7 Correct 55 ms 164564 KB Output is correct
8 Execution timed out 1063 ms 201512 KB Time limit exceeded
9 Halted 0 ms 0 KB -