Submission #1053038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053038		hirayuu_oj	Catfish Farm (IOI22_fish)	C++17	18 / 100	145 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;
const 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,fish[0].size()) {
        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;
            rep(j,sz[i]) {
                while(cnt<sz[i-2]&&fish[i-2][cnt].first<=fish[i][j].first) {
                    mx=max(mx,dndp[i-2][cnt]);
                    cnt++;
                }
                updp[i][j]=max(updp[i][j],mx+cum_lf[i][j]);
            }
            cnt=sz[i-2]-1;
            mx=-INF;
            rrep(j,sz[i]) {
                while(0<=cnt&&fish[i-2][cnt].first>=fish[i][j].first) {
                    mx=max(mx,dndp[i-2][cnt]+cum_ri[i-2][cnt]);
                    cnt--;
                }
                updp[i][j]=max(updp[i][j],mx);
            }
        }
        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;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:6:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
fish.cpp:61:5: note: in expansion of macro 'rep'
   61 |     rep(i,fish[0].size()) {
      |     ^~~

• 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