Submission #835204

#	Time	Username	Problem	Language	Result	Execution time	Memory
835204		SamAnd	Catfish Farm (IOI22_fish)	C++17	100 / 100	120 ms	36460 KiB

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]);
        }
        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);
        }

        for (int j = 0; j < sz(v[i]); ++j)
            dp0[i][j] = max(dp0[i][j], dp1[i][j]);
    }

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

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16