Submission #835202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
835202	2023-08-23T10:18:01 Z	SamAnd	Catfish Farm (IOI22_fish)	C++17	9 / 100	115 ms	37596 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, m;
vector<pair<int, int> > v[N];
vector<ll> dp0[N], dp1[N];

long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW)
{
    n = NN;
    m = MM;
    for (int i = 0; i < m; ++i)
    {
        v[XX[i] + 1].push_back(m_p(YY[i], WW[i]));
    }
    v[0].push_back(m_p(0, 0));
    for (int i = 1; i <= n; ++i)
    {
        sort(all(v[i]));
        v[i].push_back(m_p(n, 0));
    }

    dp0[0].push_back(0);
    dp1[0].push_back(0);
    for (int i = 1; i <= n; ++i)
    {
        ll maxu = 0;
        for (int j = 0; j < sz(v[i - 1]); ++j)
        {
            maxu = max(maxu, dp0[i - 1][j]);
            maxu = max(maxu, dp1[i - 1][j]);
        }
        dp0[i].assign(sz(v[i]), maxu);
        dp1[i].assign(sz(v[i]), maxu);

        vector<ll> p;
        p.assign(sz(v[i]), 0);
        p[0] = v[i][0].se;
        for (int j = 1; j < sz(v[i]); ++j)
            p[j] = p[j - 1] + v[i][j].se;

        int k = sz(v[i - 1]) - 1;
        maxu = 0;
        for (int j = sz(v[i]) - 1; j >= 0; --j)
        {
            while (k >= 0 && v[i - 1][k].fi > v[i][j].fi)
            {
                maxu = max(maxu, p[j] + dp0[i - 1][k]);
                --k;
            }
            if (j)
                dp0[i][j] = max(dp0[i][j], maxu - p[j - 1]);
            else
                dp0[i][j] = max(dp0[i][j], maxu);
        }

        k = 0;
        maxu = 0;
        ll pp = 0;
        for (int j = 0; j < sz(v[i]); ++j)
        {
            while (k < sz(v[i - 1]) && v[i - 1][k].fi < v[i][j].fi)
            {
                maxu = max(maxu, dp1[i - 1][k] - pp);
                pp += v[i - 1][k].se;
                ++k;
            }
            dp1[i][j] = max(dp1[i][j], pp + maxu);
        }
    }

    ll ans = 0;
    for (int j = 0; j < sz(v[n]); ++j)
    {
        ans = max(ans, dp0[n][j]);
        ans = max(ans, dp1[n][j]);
    }
    return ans;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	20916 KB	Output is correct
2	Correct	48 ms	23060 KB	Output is correct
3	Correct	17 ms	16664 KB	Output is correct
4	Correct	16 ms	16636 KB	Output is correct
5	Correct	112 ms	37596 KB	Output is correct
6	Correct	115 ms	37044 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7252 KB	Output is correct
2	Correct	65 ms	26196 KB	Output is correct
3	Correct	79 ms	29604 KB	Output is correct
4	Correct	40 ms	20932 KB	Output is correct
5	Correct	48 ms	23112 KB	Output is correct
6	Correct	4 ms	7308 KB	Output is correct
7	Correct	3 ms	7340 KB	Output is correct
8	Correct	3 ms	7348 KB	Output is correct
9	Correct	4 ms	7252 KB	Output is correct
10	Correct	16 ms	16632 KB	Output is correct
11	Correct	16 ms	16640 KB	Output is correct
12	Correct	41 ms	20960 KB	Output is correct
13	Correct	47 ms	23084 KB	Output is correct
14	Correct	41 ms	20980 KB	Output is correct
15	Correct	45 ms	22516 KB	Output is correct
16	Correct	43 ms	21008 KB	Output is correct
17	Correct	46 ms	22492 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	16724 KB	Output is correct
2	Correct	17 ms	16744 KB	Output is correct
3	Incorrect	30 ms	17876 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '19227425297844'
4	Halted	0 ms	0 KB	-

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7252 KB	Output is correct
2	Correct	3 ms	7252 KB	Output is correct
3	Correct	3 ms	7252 KB	Output is correct
4	Correct	3 ms	7252 KB	Output is correct
5	Correct	3 ms	7252 KB	Output is correct
6	Correct	3 ms	7252 KB	Output is correct
7	Correct	3 ms	7252 KB	Output is correct
8	Correct	3 ms	7252 KB	Output is correct
9	Incorrect	3 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '180180661865'
10	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7252 KB	Output is correct
2	Correct	3 ms	7252 KB	Output is correct
3	Correct	3 ms	7252 KB	Output is correct
4	Correct	3 ms	7252 KB	Output is correct
5	Correct	3 ms	7252 KB	Output is correct
6	Correct	3 ms	7252 KB	Output is correct
7	Correct	3 ms	7252 KB	Output is correct
8	Correct	3 ms	7252 KB	Output is correct
9	Incorrect	3 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '180180661865'
10	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7252 KB	Output is correct
2	Correct	3 ms	7252 KB	Output is correct
3	Correct	3 ms	7252 KB	Output is correct
4	Correct	3 ms	7252 KB	Output is correct
5	Correct	3 ms	7252 KB	Output is correct
6	Correct	3 ms	7252 KB	Output is correct
7	Correct	3 ms	7252 KB	Output is correct
8	Correct	3 ms	7252 KB	Output is correct
9	Incorrect	3 ms	7380 KB	1st lines differ - on the 1st token, expected: '216624184325', found: '180180661865'
10	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	16724 KB	Output is correct
2	Correct	17 ms	16744 KB	Output is correct
3	Incorrect	30 ms	17876 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '19227425297844'
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	20916 KB	Output is correct
2	Correct	48 ms	23060 KB	Output is correct
3	Correct	17 ms	16664 KB	Output is correct
4	Correct	16 ms	16636 KB	Output is correct
5	Correct	112 ms	37596 KB	Output is correct
6	Correct	115 ms	37044 KB	Output is correct
7	Correct	3 ms	7252 KB	Output is correct
8	Correct	65 ms	26196 KB	Output is correct
9	Correct	79 ms	29604 KB	Output is correct
10	Correct	40 ms	20932 KB	Output is correct
11	Correct	48 ms	23112 KB	Output is correct
12	Correct	4 ms	7308 KB	Output is correct
13	Correct	3 ms	7340 KB	Output is correct
14	Correct	3 ms	7348 KB	Output is correct
15	Correct	4 ms	7252 KB	Output is correct
16	Correct	16 ms	16632 KB	Output is correct
17	Correct	16 ms	16640 KB	Output is correct
18	Correct	41 ms	20960 KB	Output is correct
19	Correct	47 ms	23084 KB	Output is correct
20	Correct	41 ms	20980 KB	Output is correct
21	Correct	45 ms	22516 KB	Output is correct
22	Correct	43 ms	21008 KB	Output is correct
23	Correct	46 ms	22492 KB	Output is correct
24	Correct	15 ms	16724 KB	Output is correct
25	Correct	17 ms	16744 KB	Output is correct
26	Incorrect	30 ms	17876 KB	1st lines differ - on the 1st token, expected: '21261825233649', found: '19227425297844'
27	Halted	0 ms	0 KB	-

Submission #835202

Compilation message