Submission #1214847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214847		Nelt	Catfish Farm (IOI22_fish)	C++17	0 / 100	1095 ms	32068 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(0, 0));
    dp[1][1].push_back(make_pair(n, 0));
    from0[1].push_back(make_pair(0, 0));
    for (ll i = 2; i <= n; i++)
    {
        states.clear();
        for (auto j : fish[i])
            if (j.first != -1)
            states.push_back(j.first);
        for (auto j : fish[i - 1])
            if (j.first != -1)
            states.push_back(j.first);
        states.push_back(0);
        states.push_back(n);
        sort(states.begin(), states.end());
        for (ll x : states)
        {
            dp[i][1].push_back(make_pair(x, -inf));
            for (auto j : dp[i - 1][1])
                if (j.first <= x)
                {
                    ll l = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(j.first, inf)) - 1 - fish[i].begin();
                    ll r = upper_bound(fish[i].begin(), fish[i].end(), make_pair(x, inf)) - 1 - fish[i].begin();
                    dp[i][1].back().second = max(dp[i][1].back().second, j.second + fish[i][r].second - fish[i][l].second);
                }
            for (auto j : from0[i - 1])
            {
                ll pos = upper_bound(fish[i - 1].begin(), fish[i - 1].end(), make_pair(x, inf)) - fish[i - 1].begin() - 1;
                dp[i][1].back().second = max(dp[i][1].back().second, j.first + max(0ll, fish[i - 1][pos].second - j.second));
            }
            dp[i][0].push_back(dp[i][1].back());
            for (auto j : dp[i - 1][0])
                if (j.first >= x)
                {
                    ll l = upper_bound(fish[i].begin(), fish[i].end(), make_pair(x, inf)) - fish[i].begin() - 1;
                    ll r = upper_bound(fish[i].begin(), fish[i].end(), make_pair(j.first, inf)) - fish[i].begin() - 1;
                    dp[i][0].back().second = max(dp[i][0].back().second, j.second + fish[i][r].second - fish[i][l].second);
                }
        }
        for (auto j : dp[i - 1][i == 1])
        {
            ll pos = upper_bound(fish[i].begin(), fish[i].end(), make_pair(j.first, inf)) - fish[i - 1].begin() - 1;
            from0[i].push_back(make_pair(j.second + fish[i - 1][pos].second, fish[i - 1][pos].second));
        }
    }
    ll ans = 0;
    for (auto i : dp[n][0]) ans = max(ans, i.second);
    if (n == 1) assert(ans == 0);
    return ans;
}

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