Submission #1110977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1110977	2024-11-11T08:25:28 Z	jerzyk	Catfish Farm (IOI22_fish)	C++17	23 / 100	1000 ms	213576 KB

fish

#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, 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)
    {
        for(int i = 0; i < (int)dpv[l].size(); ++i)
        {
            for(int j = 0; j < (int)dpv[l - 2].size(); ++j)
            {
                if(dpv[l - 2][j] <= dpv[l][i])
                    dp[l][0][i] = max(dp[l][0][i], dp[l - 2][0][j] - sr[l - 2][j] + sl[l][i]);
                else
                    dp[l][0][i] = max(dp[l][0][i], dp[l - 2][0][j]);
            }
            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
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	157 ms	190972 KB	1st lines differ - on the 1st token, expected: '40313272768926', found: '2147442400'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	164592 KB	Output is correct
2	Execution timed out	1074 ms	201516 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	131 ms	186680 KB	Output is correct
2	Correct	125 ms	186716 KB	Output is correct
3	Correct	159 ms	186516 KB	Output is correct
4	Correct	151 ms	188720 KB	Output is correct
5	Correct	201 ms	192260 KB	Output is correct
6	Correct	213 ms	191408 KB	Output is correct
7	Correct	202 ms	192176 KB	Output is correct
8	Correct	205 ms	192072 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	164680 KB	Output is correct
2	Correct	107 ms	164680 KB	Output is correct
3	Correct	97 ms	164680 KB	Output is correct
4	Correct	115 ms	164708 KB	Output is correct
5	Correct	102 ms	164680 KB	Output is correct
6	Correct	95 ms	164680 KB	Output is correct
7	Correct	94 ms	164680 KB	Output is correct
8	Correct	101 ms	164748 KB	Output is correct
9	Incorrect	97 ms	164868 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '164774621996'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	164680 KB	Output is correct
2	Correct	107 ms	164680 KB	Output is correct
3	Correct	97 ms	164680 KB	Output is correct
4	Correct	115 ms	164708 KB	Output is correct
5	Correct	102 ms	164680 KB	Output is correct
6	Correct	95 ms	164680 KB	Output is correct
7	Correct	94 ms	164680 KB	Output is correct
8	Correct	101 ms	164748 KB	Output is correct
9	Incorrect	97 ms	164868 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '164774621996'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	164680 KB	Output is correct
2	Correct	107 ms	164680 KB	Output is correct
3	Correct	97 ms	164680 KB	Output is correct
4	Correct	115 ms	164708 KB	Output is correct
5	Correct	102 ms	164680 KB	Output is correct
6	Correct	95 ms	164680 KB	Output is correct
7	Correct	94 ms	164680 KB	Output is correct
8	Correct	101 ms	164748 KB	Output is correct
9	Incorrect	97 ms	164868 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '164774621996'
10	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	131 ms	186680 KB	Output is correct
2	Correct	125 ms	186716 KB	Output is correct
3	Correct	159 ms	186516 KB	Output is correct
4	Correct	151 ms	188720 KB	Output is correct
5	Correct	201 ms	192260 KB	Output is correct
6	Correct	213 ms	191408 KB	Output is correct
7	Correct	202 ms	192176 KB	Output is correct
8	Correct	205 ms	192072 KB	Output is correct
9	Correct	231 ms	193356 KB	Output is correct
10	Correct	169 ms	184136 KB	Output is correct
11	Correct	278 ms	203592 KB	Output is correct
12	Correct	115 ms	164680 KB	Output is correct
13	Correct	101 ms	164680 KB	Output is correct
14	Correct	103 ms	164800 KB	Output is correct
15	Correct	101 ms	164804 KB	Output is correct
16	Correct	97 ms	164680 KB	Output is correct
17	Correct	102 ms	164620 KB	Output is correct
18	Correct	139 ms	186648 KB	Output is correct
19	Correct	140 ms	186680 KB	Output is correct
20	Correct	134 ms	186492 KB	Output is correct
21	Correct	151 ms	186660 KB	Output is correct
22	Correct	227 ms	196936 KB	Output is correct
23	Correct	290 ms	211016 KB	Output is correct
24	Correct	313 ms	213576 KB	Output is correct

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	157 ms	190972 KB	1st lines differ - on the 1st token, expected: '40313272768926', found: '2147442400'
2	Halted	0 ms	0 KB	-

Submission #1110977

Compilation message