oj.uz

Submission #1110983

# Submission time Handle Problem Language Result Execution time Memory
1110983 2024-11-11T08:38:24 Z jerzyk Catfish Farm (IOI22_fish) C++17
47 / 100
 1000 ms 229104 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, 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][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 130 ms 192508 KB Output is correct
2 Correct 135 ms 195768 KB Output is correct
3 Correct 95 ms 186584 KB Output is correct
4 Correct 99 ms 186696 KB Output is correct
5 Correct 253 ms 228708 KB Output is correct
6 Correct 325 ms 229104 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 164832 KB Output is correct
2 Execution timed out 1038 ms 203548 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 186696 KB Output is correct
2 Correct 117 ms 186580 KB Output is correct
3 Correct 151 ms 187212 KB Output is correct
4 Correct 144 ms 188652 KB Output is correct
5 Correct 200 ms 192072 KB Output is correct
6 Correct 219 ms 191260 KB Output is correct
7 Correct 221 ms 191488 KB Output is correct
8 Correct 189 ms 191560 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 164680 KB Output is correct
2 Correct 74 ms 164624 KB Output is correct
3 Correct 84 ms 164680 KB Output is correct
4 Correct 77 ms 164680 KB Output is correct
5 Correct 71 ms 164624 KB Output is correct
6 Correct 77 ms 164720 KB Output is correct
7 Correct 74 ms 164684 KB Output is correct
8 Correct 73 ms 164592 KB Output is correct
9 Correct 71 ms 164816 KB Output is correct
10 Correct 75 ms 164940 KB Output is correct
11 Correct 73 ms 164936 KB Output is correct
12 Correct 73 ms 165020 KB Output is correct
13 Correct 86 ms 164696 KB Output is correct
14 Correct 80 ms 164856 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 164680 KB Output is correct
2 Correct 74 ms 164624 KB Output is correct
3 Correct 84 ms 164680 KB Output is correct
4 Correct 77 ms 164680 KB Output is correct
5 Correct 71 ms 164624 KB Output is correct
6 Correct 77 ms 164720 KB Output is correct
7 Correct 74 ms 164684 KB Output is correct
8 Correct 73 ms 164592 KB Output is correct
9 Correct 71 ms 164816 KB Output is correct
10 Correct 75 ms 164940 KB Output is correct
11 Correct 73 ms 164936 KB Output is correct
12 Correct 73 ms 165020 KB Output is correct
13 Correct 86 ms 164696 KB Output is correct
14 Correct 80 ms 164856 KB Output is correct
15 Correct 76 ms 164680 KB Output is correct
16 Correct 73 ms 164936 KB Output is correct
17 Correct 110 ms 170316 KB Output is correct
18 Correct 113 ms 170568 KB Output is correct
19 Correct 107 ms 170920 KB Output is correct
20 Correct 113 ms 170240 KB Output is correct
21 Correct 107 ms 170312 KB Output is correct
22 Correct 163 ms 175688 KB Output is correct
23 Correct 84 ms 166216 KB Output is correct
24 Correct 105 ms 169148 KB Output is correct
25 Correct 72 ms 164952 KB Output is correct
26 Correct 79 ms 165960 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 164680 KB Output is correct
2 Correct 74 ms 164624 KB Output is correct
3 Correct 84 ms 164680 KB Output is correct
4 Correct 77 ms 164680 KB Output is correct
5 Correct 71 ms 164624 KB Output is correct
6 Correct 77 ms 164720 KB Output is correct
7 Correct 74 ms 164684 KB Output is correct
8 Correct 73 ms 164592 KB Output is correct
9 Correct 71 ms 164816 KB Output is correct
10 Correct 75 ms 164940 KB Output is correct
11 Correct 73 ms 164936 KB Output is correct
12 Correct 73 ms 165020 KB Output is correct
13 Correct 86 ms 164696 KB Output is correct
14 Correct 80 ms 164856 KB Output is correct
15 Correct 76 ms 164680 KB Output is correct
16 Correct 73 ms 164936 KB Output is correct
17 Correct 110 ms 170316 KB Output is correct
18 Correct 113 ms 170568 KB Output is correct
19 Correct 107 ms 170920 KB Output is correct
20 Correct 113 ms 170240 KB Output is correct
21 Correct 107 ms 170312 KB Output is correct
22 Correct 163 ms 175688 KB Output is correct
23 Correct 84 ms 166216 KB Output is correct
24 Correct 105 ms 169148 KB Output is correct
25 Correct 72 ms 164952 KB Output is correct
26 Correct 79 ms 165960 KB Output is correct
27 Correct 81 ms 165448 KB Output is correct
28 Correct 337 ms 192376 KB Output is correct
29 Execution timed out 1067 ms 205432 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 186696 KB Output is correct
2 Correct 117 ms 186580 KB Output is correct
3 Correct 151 ms 187212 KB Output is correct
4 Correct 144 ms 188652 KB Output is correct
5 Correct 200 ms 192072 KB Output is correct
6 Correct 219 ms 191260 KB Output is correct
7 Correct 221 ms 191488 KB Output is correct
8 Correct 189 ms 191560 KB Output is correct
9 Correct 185 ms 193352 KB Output is correct
10 Correct 160 ms 183880 KB Output is correct
11 Correct 257 ms 203268 KB Output is correct
12 Correct 72 ms 164680 KB Output is correct
13 Correct 73 ms 164680 KB Output is correct
14 Correct 74 ms 164680 KB Output is correct
15 Correct 78 ms 164680 KB Output is correct
16 Correct 86 ms 164652 KB Output is correct
17 Correct 72 ms 164684 KB Output is correct
18 Correct 120 ms 186696 KB Output is correct
19 Correct 116 ms 186596 KB Output is correct
20 Correct 120 ms 186552 KB Output is correct
21 Correct 134 ms 186696 KB Output is correct
22 Incorrect 214 ms 196628 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 130 ms 192508 KB Output is correct
2 Correct 135 ms 195768 KB Output is correct
3 Correct 95 ms 186584 KB Output is correct
4 Correct 99 ms 186696 KB Output is correct
5 Correct 253 ms 228708 KB Output is correct
6 Correct 325 ms 229104 KB Output is correct
7 Correct 64 ms 164832 KB Output is correct
8 Execution timed out 1038 ms 203548 KB Time limit exceeded
9 Halted 0 ms 0 KB -