Submission #838240

#	Time	Username	Problem	Language	Result	Execution time	Memory
838240		JakobZorz	Catfish Farm (IOI22_fish)	C++17	100 / 100	376 ms	259024 KiB

fish

#include"fish.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
typedef long long ll;
 
int n;
vector<pair<int,int>>fish[100001];
vector<ll>sum_down[100001];
vector<ll>sum_right_pos[100001];
vector<ll>sum_left_pos[100001];
vector<ll>next_right[100001];
vector<ll>next_left[100001];
int h[100001];
ll full_sum[100001];

vector<ll>slope_down_dp[1000001];
vector<ll>slope_down_dp_max[1000001];
vector<ll>slope_up_dp[1000001];
vector<ll>slope_up_dp_max[1000001];
vector<ll>dp_max1[1000001];
vector<ll>dp_max2[1000001];
vector<ll>gap_dp[1000001];
ll full_dp[1000001];
 
ll get_sum_right(int x,int y){
    if(x==n-1)
        return 0;
    return sum_down[x+1][sum_right_pos[x][y]];
}
 
ll get_sum_left(int x,int y){
    if(x==0)
        return 0;
    return sum_down[x-1][sum_left_pos[x][y]];
}
 
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
    n=N+1;
    for(int i=0;i<M;i++){
        fish[X[i]+1].push_back({Y[i],W[i]});
        full_sum[X[i]+1]+=W[i];
    }
    
    for(int i=0;i<n;i++)
        sort(fish[i].begin(),fish[i].end());
    
    for(int i=0;i<n;i++)
        fish[i].push_back({n+1,0});
    
    for(int i=0;i<n;i++)
        h[i]=(int)fish[i].size();
    
    for(int i=0;i<n;i++){
        sum_down[i].resize(h[i]);
        for(int j=1;j<h[i];j++){
            sum_down[i][j]=sum_down[i][j-1]+fish[i][j-1].second;
        }
    }
    
    for(int i=0;i<n;i++){
        slope_down_dp[i].resize(h[i]);
        slope_down_dp_max[i].resize(h[i]+1);
        slope_up_dp[i].resize(h[i]);
        slope_up_dp_max[i].resize(h[i]+1);
        gap_dp[i].resize(h[i]);
        dp_max1[i].resize(h[i]+1);
        dp_max2[i].resize(h[i]+1);
    }
    
    
    sum_right_pos[n-1].resize(h[n-1]);
    for(int i=0;i<n-1;i++){
        sum_right_pos[i].resize(h[i]);
        next_right[i].resize(h[i]);
        int i2=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i+1]-1&&fish[i][i1].first>fish[i+1][i2].first){
                i2++;
            }
            sum_right_pos[i][i1]=i2;
        }
        
        i2=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i+1]&&fish[i][i1].first>=fish[i+1][i2].first)
                i2++;
            next_right[i][i1]=i2;
        }
    }
    
    sum_left_pos[0].resize(h[0]);
    for(int i=1;i<n;i++){
        sum_left_pos[i].resize(h[i]);
        next_left[i].resize(h[i]);
        int i2=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i-1]-1&&fish[i][i1].first>fish[i-1][i2].first){
                i2++;
            }
            sum_left_pos[i][i1]=i2;
        }
        
        i2=0;
        for(int i1=0;i1<h[i];i1++){
            while(i2<h[i-1]&&fish[i][i1].first>=fish[i-1][i2].first)
                i2++;
            next_left[i][i1]=i2;
        }
    }
    
    for(int y=0;y<h[n-1];y++){
        slope_up_dp[n-1][y]=get_sum_left(n-1,y);
        gap_dp[n-1][y]=sum_down[n-1][y];
    }
    
    for(int x=n-2;x>=0;x--){
        slope_down_dp_max[x+1][0]=-1e17;
        for(int y=1;y<=h[x+1];y++){
            slope_down_dp_max[x+1][y]=max(slope_down_dp_max[x+1][y-1],slope_down_dp[x+1][y-1]);
        }
        
        slope_up_dp_max[x+1][h[x+1]]=-1e17;
        for(int y=h[x+1]-1;y>=0;y--){
            slope_up_dp_max[x+1][y]=max(slope_up_dp_max[x+1][y+1],slope_up_dp[x+1][y]);
        }
        
        dp_max1[x+1][0]=-1e17;
        for(int y=1;y<=h[x+1];y++){
            dp_max1[x+1][y]=max(dp_max1[x+1][y-1],slope_up_dp[x+1][y-1]-get_sum_left(x+1,y-1));
        }
        
        dp_max2[x+1][h[x+1]]=-1e17;
        for(int y=h[x+1]-1;y>=0;y--){
            dp_max2[x+1][y]=max(dp_max2[x+1][y+1],slope_up_dp[x+1][y]+get_sum_left(x+1,y)-get_sum_left(x+1,y));
        }
        
        for(int y=0;y<h[x];y++){
            //slope down
            {
                ll res=slope_down_dp_max[x+1][next_right[x][y]];
                
                res+=-sum_down[x][y]+get_sum_right(x,y);
                
                ll res2=gap_dp[x+1][sum_right_pos[x][y]]-sum_down[x][y];
                
                slope_down_dp[x][y]=max(res,res2);
            }
            
            // slope up
            {
                ll res=slope_up_dp_max[x+1][next_right[x][y]]-sum_down[x][y]+get_sum_left(x,y);
                
                ll res2=full_dp[x+1]+full_sum[x]-sum_down[x][y]+get_sum_left(x,y);
                
                slope_up_dp[x][y]=max(res,res2);
            }
            
            // gap
            {
                ll res=full_dp[x+1]+full_sum[x];
                res=max(res,gap_dp[x+1][0]+sum_down[x][y]);
                
                int l=-1,r=h[x+1];
                while(l<r-1){
                    int m=(l+r)/2;
                    if(get_sum_left(x+1,m)>sum_down[x][y]){
                        r=m;
                    }else{
                        l=m;
                    }
                }
                
                int y_point=r;
                
                res=max(res,dp_max1[x+1][y_point]+sum_down[x][y]);
                /*for(int y2=0;y2<y_point;y2++){
                    ll res2=slope_up_dp[x+1][y2]-get_sum_left(x+1,y2);
                    res=max(res,res2);
                }*/
                
                res=max(res,dp_max2[x+1][y_point]);
                /*for(int y2=y_point;y2<h[x+1];y2++){
                    ll res2=slope_up_dp[x+1][y2]+get_sum_left(x+1,y2)-get_sum_left(x+1,y2);
                    res=max(res,res2);
                }*/
                
                gap_dp[x][y]=res;
            }
        }
        
        // full
        {
            ll res=gap_dp[x+1][h[x+1]-1];
            
            res=max(res,full_dp[x+1]);
            
            for(int y2=0;y2<h[x+1];y2++){
                ll res2=slope_down_dp[x+1][y2]+full_sum[x+1];
                res=max(res,res2);
            }
            
            full_dp[x]=res;
        }
    }
    
    return gap_dp[0][0];
}

• 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