Submission #1053079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053079		hirayuu_oj	Catfish Farm (IOI22_fish)	C++17	18 / 100	140 ms	69204 KiB

fish

#include "fish.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll INF=1LL<<60;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<pair<int,ll>>> fish(N);
    rep(i,M) {
        fish[X[i]].emplace_back(Y[i],W[i]);
    }
    rep(i,N) {
        fish[i].emplace_back(N,0);
    }
    vector<vector<int>> pos(N);
    vector<vector<ll>> cum_lf(N);
    vector<vector<ll>> cum_ri(N);
    vector<vector<ll>> cum_hr(N);
    vector<vector<ll>> updp(N);
    vector<vector<ll>> dndp(N);
    vector<int> sz(N);
    rep(i,N) {
        sort(all(fish[i]));
        sz[i]=fish[i].size();
        updp[i].resize(sz[i],-INF);
        dndp[i].resize(sz[i],-INF);
        if(i!=0) {
            ll cum=0;
            int cnt=0;
            for(auto &[y,_]:fish[i]){
                while(fish[i-1][cnt].first<y){
                    cum+=fish[i-1][cnt].second;
                    cnt++;
                }
                cum_lf[i].emplace_back(cum);
            }
        }
        if(i!=N-1){
            ll cum=0;
            int cnt=0;
            for(auto &[y,_]:fish[i]){
                while(fish[i+1][cnt].first<y){
                    cum+=fish[i+1][cnt].second;
                    cnt++;
                }
                cum_ri[i].emplace_back(cum);
            }
        }
        cum_hr[i].emplace_back(0);
        for(auto &[_,w]:fish[i]) {
            cum_hr[i].emplace_back(cum_hr[i].back()+w);
        }
    }
    rep(i,sz[0]) {
        updp[0][i]=0;
        dndp[0][i]=0;
    }
    rng(i,1,N) {
        int cnt=0;
        ll mx=-INF;
        rep(j,sz[i]) {
            while(cnt<sz[i-1]&&fish[i-1][cnt].first<=fish[i][j].first) {
                mx=max(mx,updp[i-1][cnt]-cum_hr[i-1][cnt]);
                cnt++;
            }
            updp[i][j]=mx+cum_lf[i][j];
        }
        cnt=sz[i-1]-1;
        mx=-INF;
        rrep(j,sz[i]) {
            while(cnt>=0&&fish[i-1][cnt].first>=fish[i][j].first) {
                mx=max(mx,dndp[i-1][cnt]+cum_ri[i-1][cnt]);
                cnt--;
            }
            dndp[i][j]=mx-cum_hr[i][j];
        }
        if(i>=2) {
            cnt=0;
            mx=-INF;
            ll mxa=-INF;
            rep(j,sz[i-2]) {
                mx=max(mx,dndp[i-2][j]);
                mxa=max(mxa,dndp[i-2][j]+cum_ri[i-2][cnt]);
            }
            rep(j,sz[i]) {
                updp[i][j]=max(updp[i][j],mxa);
                updp[i][j]=max(updp[i][j],mx+cum_lf[i][j]);
            }
        }
        rep(j,sz[i]) {
            dndp[i][j]=max(dndp[i][j],updp[i][j]);
        }
    }
    ll ans=-INF;
    for(ll i:dndp.back())ans=max(ans,i);
    return ans;
}

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