Submission #863456

#	Time	Username	Problem	Language	Result	Execution time	Memory
863456		neki	Catfish Farm (IOI22_fish)	C++17	100 / 100	541 ms	77668 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"

#define ll long long
#define vc vector
 
using namespace std;
 
ll max_weights(int N, int M, vc<int> X, vc<int> Y, vc<int> W) {
    vc<ll> ind(M); for(ll i=0;i<M;++i) ind[i]=i;
    sort(ind.begin(),ind.end(),[&](ll a,ll b){return Y[a]<Y[b];});
    
    vc<vc<pair<ll, ll>>> f(N);
    vc<vc<ll>> rel(N, vc<ll>(1, -1)), dpm(N, vc<ll>(1, 0)), dpv(N, vc<ll>(1, 0)), dpn(N, vc<ll>(1, 0));
    for(auto i: ind){
        f[X[i]].emplace_back(Y[i], W[i]);
        if(X[i]-1>=0) rel[X[i]-1].push_back(Y[i]),dpn[X[i]-1].push_back(0),dpm[X[i]-1].push_back(0),dpv[X[i]-1].push_back(0);
        if(X[i]+1<N) rel[X[i]+1].push_back(Y[i]),dpn[X[i]+1].push_back(0),dpm[X[i]+1].push_back(0),dpv[X[i]+1].push_back(0);
    }
    
    for(ll i=0;i<N;++i){
        if(i-2>=0){
            for(ll j=0, prej=0, c=0, pp=0, mm=0;j<(ll)rel[i].size();++j){
                while(pp<(ll)rel[i-2].size()&&rel[i-2][pp]<=rel[i][j])mm=max(mm, max(dpv[i-2][pp], dpm[i-2][pp])),++pp;
                while(prej<(ll)f[i-1].size()&&f[i-1][prej].first<=rel[i][j])c+=f[i-1][prej++].second;
                dpv[i][j]=max(dpv[i][j],mm+c);
                dpm[i][j]=max(dpm[i][j],mm+c);
            }
            for(ll j=(ll)rel[i].size()-1, pp=(ll)rel[i-2].size(), mm=0;j>=0;--j){
                while(pp-1>=0&&rel[i-2][pp-1]>=rel[i][j])mm=max(mm, dpn[i-2][--pp]);
                dpv[i][j]=max(dpv[i][j],mm);
                dpm[i][j]=max(dpm[i][j],mm);
            }
        }
        if(i-1>=0){
            for(ll j=0, prej=0, pf=0, mm=0;j<(ll)rel[i].size();++j){
                while(1){
                    if(prej<(ll)rel[i-1].size()&&rel[i-1][prej]<=rel[i][j]&&(!(pf<(ll)f[i-1].size()) || rel[i-1][prej]<f[i-1][pf].first))mm=max(mm, dpm[i-1][prej++]);
                    else if(pf<(ll)f[i-1].size()&&f[i-1][pf].first<=rel[i][j])mm+=f[i-1][pf++].second;
                    else break;
                }
                dpm[i][j]=max(dpm[i][j], mm);
            }
            
            ll mm=0;
            for(auto v: dpn[i-1])mm=max(mm, v);
            for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
                while(nas<(ll)f[i].size()&&f[i][nas].first<=rel[i][j])c+=f[i][nas++].second;
                dpv[i][j]=max({dpv[i][j],dpm[i][j], mm-c});
            }
        }
        if(i+1<N){
            for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
                while(nas<(ll)f[i+1].size()&&f[i+1][nas].first<=rel[i][j])c+=f[i+1][nas++].second;
                dpn[i][j]=max(dpn[i][j],max(dpv[i][j], dpm[i][j])+c);
            }
        }
    }
    ll ans=0;
    for(ll i=0;i<N;++i){
        for(ll j=0;j<(ll)rel[i].size();++j)ans=max({ans, dpn[i][j], dpv[i][j], dpm[i][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