Submission #1214871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214871		Nelt	메기 농장 (IOI22_fish)	C++17	100 / 100	460 ms	120080 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const ll inf = 2e18;
long long max_weights(int n, int m, vector<int> X, vector<int> Y,
                      vector<int> W)
{
    vector<pair<ll, ll>> fish[n + 1];
    for (ll i = 0; i < m; i++)
        fish[X[i] + 1].push_back(make_pair(Y[i] + 1, W[i]));
    for (ll i = 1; i <= n; i++)
    {
        sort(fish[i].begin(), fish[i].end());
        fish[i].insert(fish[i].begin(), make_pair(-1, 0));
        for (ll j = 1; j < fish[i].size(); j++)
            fish[i][j].second += fish[i][j - 1].second;
    }
    vector<pair<ll, ll>> dp[n + 1][2];
    vector<pair<ll, ll>> from0[n + 1];
    vector<ll> states;
    for (auto j : fish[1])
        if (j.first != -1)
            dp[1][1].push_back(make_pair(j.first, 0)), dp[1][0].push_back(make_pair(j.first, 0));
    dp[1][1].push_back(make_pair(n, 0));
    dp[1][0].push_back(make_pair(n, 0));
    from0[1].push_back(make_pair(0, 0));
    vector<pair<ll, ll>> pre, suf;
    for (ll i = 2; i <= n; i++)
    {
        states.clear();
        for (auto j : fish[i])
            if (j.first != -1)
                states.push_back(j.first), states.push_back(j.first - 1);
        for (auto j : fish[i - 1])
            if (j.first != -1)
                states.push_back(j.first), states.push_back(j.first - 1);
        states.push_back(0);
        states.push_back(n);
        sort(states.begin(), states.end());
        states.resize(unique(states.begin(), states.end()) - states.begin());
        pre.clear();
        pre.push_back(make_pair(-1, -inf));
        for (auto j : dp[i - 1][1])
        {
            ll l = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(j.first, inf)) - 1 - fish[i - 1].begin();
            pre.push_back(make_pair(j.first, max(pre.back().second, j.second - fish[i - 1][l].second)));
        }
        suf.clear();
        suf.push_back(make_pair(n + 1, -inf));
        for (ll j = (ll)dp[i - 1][0].size() - 1; j >= 0; j--)
        {
            ll r = upper_bound(fish[i].begin(), fish[i].end(), make_pair(dp[i - 1][0][j].first, inf)) - fish[i].begin() - 1;
            suf.push_back(make_pair(dp[i - 1][0][j].first, max(suf.back().second, dp[i - 1][0][j].second + fish[i][r].second)));
        }
        reverse(suf.begin(), suf.end());
        ll mx = -inf, mx1 = -inf;
        for (auto j : from0[i - 1])
            mx = max(mx, j.second - j.first), mx1 = max(mx1, j.second);
        for (ll x : states)
        {
            dp[i][1].push_back(make_pair(x, -inf));
            ll r = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - 1 - fish[i - 1].begin();
            ll pos = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - fish[i - 1].begin() - 1;
            ll l = upper_bound(fish[i].begin(), fish[i].end(), make_pair(x, inf)) - fish[i].begin() - 1;
            dp[i][1].back().second = max(dp[i][1].back().second, (--upper_bound(pre.begin(), pre.end(), make_pair(x, inf)))->second + fish[i - 1][r].second);
            dp[i][1].back().second = max(dp[i][1].back().second, fish[i - 1][pos].second + mx);
            dp[i][1].back().second = max(dp[i][1].back().second, mx1);
            dp[i][0].push_back(dp[i][1].back());
            dp[i][0].back().second = max(dp[i][0].back().second, (lower_bound(suf.begin(), suf.end(), make_pair(x, inf)))->second - fish[i][l].second);
        }
        assert(dp[i][1].size() == dp[i][0].size());
        for (ll j = 0; j < dp[i - 1][0].size(); j++)
        {
            ll pos = upper_bound(fish[i].begin(), fish[i].end(), make_pair(dp[i - 1][0][j].first, inf)) - fish[i].begin() - 1;
            from0[i].push_back(make_pair(fish[i][pos].second, max(dp[i - 1][0][j].second, dp[i - 1][1][j].second) + fish[i][pos].second));
        }
    }
    ll ans = 0;
    for (auto i : dp[n][0]) ans = max(ans, i.second);
    for (auto i : dp[n][1]) ans = max(ans, i.second);
    if (n == 1) assert(ans == 0);
    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