Submission #1067391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067391		hotboy2703	Catfish Farm (IOI22_fish)	C++17	100 / 100	181 ms	31988 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
#define fi first
#define se second
#define pll pair <ll,ll>
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL<<(i)) 
ll n,m;
const ll MAXN = 1e5+100;
vector <pll> all[MAXN];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n=N,m=M;
    ll bot1,bot2,top;
    bot1 = bot2 = top = 0;
    map <ll,ll> mp1,mp2;
    ll sum1=0,sum2=0;
    mp1[0] = mp2[0] = 0;
    for (ll i = 0;i < m;i ++){
        all[X[i]].push_back(MP(Y[i],W[i]));
    }

    for (ll i = 0;i < n;i ++)sort(all[i].begin(),all[i].end());
    for (ll i = 1;i < n;i ++){
        // cout<<i<<endl;
        while ((*mp1.begin()).se<bot2){
            ll x = (*mp1.begin()).se;
            sum1 -= x;
            mp1.erase(mp1.begin());
            if (!mp1.empty()){
                (*mp1.begin()).se += x;
                sum1 += x;
            }
            else break;
        }
        if (!mp1.empty())(*mp1.begin()).se -= bot2;
        else sum1 = bot2;
        mp1[-1] = bot2;
        for (auto x:all[i-1]){
            mp1[x.fi] -= x.se;
            sum1 -= x.se;
            auto cur = mp1.find(x.fi);
            while ((*cur).se < 0){
                ll z = (*cur).se;
                cur = mp1.erase(cur);
                sum1 -= z;
                if (cur==mp1.end())break;
                (*cur).se+=z;
                sum1 += z;
            }
        }
        // cout<<i<<endl;
        for (auto x:all[i-1]){
            mp1[x.fi] += x.se;
            sum1 += x.se;
        }

        mp1.erase(mp1.begin());
        mp1[0] += bot2;

        mp2[n-1] = top - sum2;
        sum2 = top;
        auto sus = [&](auto tmp){
            while ((*tmp).se > 0){
                if (tmp==mp2.begin())break;
                auto pre = prev(tmp);
                (*pre).se += (*tmp).se;
                mp2.erase(tmp);
                tmp = pre;
            }
        };
        sus(mp2.find(n-1));
        for (auto x:all[i]){
            mp2[x.fi]+=x.se;
            sus(mp2.find(x.fi));
        }
        // cout<<"OK"<<endl;
        // return 0;
        ll nw_bot1 = mp2[0];
        for (auto x:all[i]){
            mp2[x.fi]-=x.se;
        }
        sum2 -= mp2[n-1];
        mp2.erase(mp2.find(n-1));
        top = max({top,bot1,sum1});
        bot2 = bot1;
        bot1 = nw_bot1;
        // cout<<endl;
        // cout<<bot1<<' '<<bot2<<' '<<top<<endl;
        // cout<<"MP1\n";
        // for (auto x:mp1)cout<<x.fi<<' '<<x.se<<'\n';
        // cout<<"MP2\n";
        // for (auto x:mp2)cout<<x.fi<<' '<<x.se<<'\n';
    }
    return max({bot1,bot2,top});
}

• 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