Submission #1110986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110986		jerzyk	Catfish Farm (IOI22_fish)	C++17	100 / 100	400 ms	229276 KiB

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;
        ll 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)
    {
        ll ma = -I, mb = -I;
        for(int j = 0; j < (int)dpv[l - 2].size(); ++j)
        {
            ma = max(ma, dp[l - 2][0][j] - sr[l - 2][j]);
            mb = max(mb, dp[l - 2][0][j]);
        }
        ll m1 = -I;
        int j1 = -1;
        for(int i = 0; i < (int)dpv[l].size(); ++i)
        {
            dp[l][0][i] = max(ma + sl[l][i], mb);
            dp[l][1][i] = dp[l][0][i];
            while(j1 < (int)dpv[l - 1].size() - 1 && dpv[l - 1][j1 + 1] <= dpv[l][i])
            {
                ++j1;
                m1 = max(m1, dp[l - 1][1][j1] - as[l - 1][j1]);
            }
            dp[l][1][i] = max(dp[l][1][i], m1 + sl[l][i]);
        }
        m1 = -I;
        j1 = (int)dpv[l - 1].size();
        for(int i = (int)dpv[l].size() - 1; i >= 0; --i)
        {
            while(j1 > 0 && dpv[l - 1][j1 - 1] >= dpv[l][i])
            {
                --j1;
                m1 = max(m1, dp[l - 1][0][j1]);
            }
            dp[l][0][i] = max(dp[l][0][i], m1 - as[l][i]);
            dp[l][0][i] = max(dp[l][0][i], dp[l][1][i]) + sr[l][i];
        }
    }
}

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: 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