oj.uz

Submission #1110984

# Submission time Handle Problem Language Result Execution time Memory
1110984 2024-11-11T08:42:47 Z jerzyk Catfish Farm (IOI22_fish) C++17
47 / 100
 1000 ms 226196 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 = 0;
        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[j1 + 1] <= dpv[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 133 ms 191172 KB Output is correct
2 Correct 137 ms 194812 KB Output is correct
3 Correct 96 ms 186696 KB Output is correct
4 Correct 99 ms 186700 KB Output is correct
5 Correct 298 ms 226196 KB Output is correct
6 Correct 360 ms 225584 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 164588 KB Output is correct
2 Execution timed out 1062 ms 201324 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 186952 KB Output is correct
2 Correct 105 ms 186696 KB Output is correct
3 Correct 134 ms 186440 KB Output is correct
4 Correct 160 ms 187976 KB Output is correct
5 Correct 172 ms 190540 KB Output is correct
6 Correct 181 ms 190536 KB Output is correct
7 Correct 187 ms 190564 KB Output is correct
8 Correct 174 ms 190536 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164716 KB Output is correct
2 Correct 74 ms 164596 KB Output is correct
3 Correct 74 ms 164732 KB Output is correct
4 Correct 71 ms 164680 KB Output is correct
5 Correct 73 ms 164684 KB Output is correct
6 Correct 67 ms 164680 KB Output is correct
7 Correct 73 ms 164680 KB Output is correct
8 Correct 69 ms 164680 KB Output is correct
9 Correct 65 ms 164680 KB Output is correct
10 Correct 65 ms 164948 KB Output is correct
11 Correct 65 ms 164688 KB Output is correct
12 Correct 67 ms 164936 KB Output is correct
13 Correct 62 ms 164680 KB Output is correct
14 Correct 74 ms 164936 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164716 KB Output is correct
2 Correct 74 ms 164596 KB Output is correct
3 Correct 74 ms 164732 KB Output is correct
4 Correct 71 ms 164680 KB Output is correct
5 Correct 73 ms 164684 KB Output is correct
6 Correct 67 ms 164680 KB Output is correct
7 Correct 73 ms 164680 KB Output is correct
8 Correct 69 ms 164680 KB Output is correct
9 Correct 65 ms 164680 KB Output is correct
10 Correct 65 ms 164948 KB Output is correct
11 Correct 65 ms 164688 KB Output is correct
12 Correct 67 ms 164936 KB Output is correct
13 Correct 62 ms 164680 KB Output is correct
14 Correct 74 ms 164936 KB Output is correct
15 Correct 65 ms 164788 KB Output is correct
16 Correct 68 ms 165020 KB Output is correct
17 Correct 93 ms 169552 KB Output is correct
18 Correct 90 ms 170140 KB Output is correct
19 Correct 97 ms 170056 KB Output is correct
20 Correct 97 ms 169704 KB Output is correct
21 Correct 110 ms 169800 KB Output is correct
22 Correct 137 ms 174664 KB Output is correct
23 Correct 77 ms 165968 KB Output is correct
24 Correct 95 ms 168480 KB Output is correct
25 Correct 74 ms 164936 KB Output is correct
26 Correct 81 ms 165960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164716 KB Output is correct
2 Correct 74 ms 164596 KB Output is correct
3 Correct 74 ms 164732 KB Output is correct
4 Correct 71 ms 164680 KB Output is correct
5 Correct 73 ms 164684 KB Output is correct
6 Correct 67 ms 164680 KB Output is correct
7 Correct 73 ms 164680 KB Output is correct
8 Correct 69 ms 164680 KB Output is correct
9 Correct 65 ms 164680 KB Output is correct
10 Correct 65 ms 164948 KB Output is correct
11 Correct 65 ms 164688 KB Output is correct
12 Correct 67 ms 164936 KB Output is correct
13 Correct 62 ms 164680 KB Output is correct
14 Correct 74 ms 164936 KB Output is correct
15 Correct 65 ms 164788 KB Output is correct
16 Correct 68 ms 165020 KB Output is correct
17 Correct 93 ms 169552 KB Output is correct
18 Correct 90 ms 170140 KB Output is correct
19 Correct 97 ms 170056 KB Output is correct
20 Correct 97 ms 169704 KB Output is correct
21 Correct 110 ms 169800 KB Output is correct
22 Correct 137 ms 174664 KB Output is correct
23 Correct 77 ms 165968 KB Output is correct
24 Correct 95 ms 168480 KB Output is correct
25 Correct 74 ms 164936 KB Output is correct
26 Correct 81 ms 165960 KB Output is correct
27 Correct 79 ms 165448 KB Output is correct
28 Correct 370 ms 189264 KB Output is correct
29 Execution timed out 1076 ms 200816 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 186952 KB Output is correct
2 Correct 105 ms 186696 KB Output is correct
3 Correct 134 ms 186440 KB Output is correct
4 Correct 160 ms 187976 KB Output is correct
5 Correct 172 ms 190540 KB Output is correct
6 Correct 181 ms 190536 KB Output is correct
7 Correct 187 ms 190564 KB Output is correct
8 Correct 174 ms 190536 KB Output is correct
9 Correct 242 ms 192072 KB Output is correct
10 Correct 151 ms 182304 KB Output is correct
11 Correct 267 ms 200100 KB Output is correct
12 Correct 68 ms 164684 KB Output is correct
13 Correct 66 ms 164684 KB Output is correct
14 Correct 78 ms 164680 KB Output is correct
15 Correct 72 ms 164680 KB Output is correct
16 Correct 77 ms 164680 KB Output is correct
17 Correct 81 ms 164716 KB Output is correct
18 Correct 116 ms 186696 KB Output is correct
19 Correct 119 ms 186732 KB Output is correct
20 Correct 146 ms 186688 KB Output is correct
21 Correct 139 ms 186696 KB Output is correct
22 Incorrect 195 ms 194888 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45458155758023'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 191172 KB Output is correct
2 Correct 137 ms 194812 KB Output is correct
3 Correct 96 ms 186696 KB Output is correct
4 Correct 99 ms 186700 KB Output is correct
5 Correct 298 ms 226196 KB Output is correct
6 Correct 360 ms 225584 KB Output is correct
7 Correct 67 ms 164588 KB Output is correct
8 Execution timed out 1062 ms 201324 KB Time limit exceeded
9 Halted 0 ms 0 KB -