Submission #728654

# Submission time Handle Problem Language Result Execution time Memory
728654 2023-04-22T19:14:04 Z Urvuk3 Catfish Farm (IOI22_fish) C++17
9 / 100
319 ms 36472 KB
#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) { cerr<<"["<<#x<<"]=["; _PRINT(x); }

vector<vector<int>> ind;
vector<vector<pair<int,ll>>> fish;
vector<vector<ll>> dp[2];
map<int,ll> pref;

ll Sum(int l,int r){
    ll prefr=prev(pref.upper_bound(r))->se;
    ll prefl=prev(pref.upper_bound(l-1))->se;
    return prefr-prefl;
}

void MaxSelf(ll& x,ll y){
    x=max(x,y);
}

long long max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
    ind.resize(N); fish.resize(N);
    dp[0].resize(N); dp[1].resize(N);
    for(int i=0;i<M;i++){
        if(X[i]) ind[X[i]-1].pb(Y[i]+1);
        if(X[i]+1<N) ind[X[i]+1].pb(Y[i]+1);
        fish[X[i]].pb({Y[i],W[i]});
    }
    for(int x=0;x<N;x++){
        ind[x].pb(0); ind[x].pb(N);
        sort(all(ind[x]));
        sort(all(fish[x]));
        ind[x].resize(unique(all(ind[x]))-ind[x].begin());
        dp[0][x].resize(sz(ind[x]));
        dp[1][x].resize(sz(ind[x]));
    }
    for(int x=1;x<N;x++){
        pref.clear(); pref[-1]=0;
        for(int i=0;i<sz(fish[x-1]);i++){
            int y=fish[x-1][i].fi;
            int w=fish[x-1][i].se;
            pref[y]=pref.upper_bound(y-1)->se+w;
        }
        if(x>1){
            int i1=sz(ind[x-2])-1;
            ll suf_max=-LINF;
            for(int i=sz(ind[x])-1;i>=0;i--){
                while(i1>=0 && ind[x-2][i1]>ind[x][i]){
                    ll m=max(dp[0][x-2][i1],dp[1][x-2][i1]);
                    MaxSelf(suf_max,m+Sum(0,ind[x-2][i1]-1));
                    i1--;
                }
                MaxSelf(dp[1][x][i],suf_max);
            }

            i1=0;
            ll pref_max=-LINF;
            for(int i=0;i<sz(ind[x]);i++){
                while(i1<sz(ind[x-2]) && ind[x-2][i1]<=ind[x][i]){
                    ll m=max(dp[0][x-2][i1],dp[1][x-2][i1]);
                    MaxSelf(pref_max,m);
                    i1++;
                }
                MaxSelf(dp[1][x][i],pref_max+Sum(0,ind[x][i]-1));
            }

            i1=1;
            pref_max=-LINF;
            for(int i=0;i<sz(ind[x]);i++){
                if(i>0) pref_max+=Sum(ind[x][i-1],ind[x][i]-1);
                while(i1<sz(ind[x-1]) && ind[x-1][i1]<=ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(pref_max,m+Sum(ind[x-1][i1],ind[x][i]-1));
                    i1++;
                }
                MaxSelf(dp[1][x][i],pref_max);
            }

            pref.clear(); pref[-1]=0;
            for(int i=0;i<sz(fish[x]);i++){
                int y=fish[x][i].fi;
                int w=fish[x][i].se;
                pref[y]=pref.upper_bound(y-1)->se+w;
            }

            i1=sz(ind[x-1])-1;
            suf_max=-LINF;
            for(int i=sz(ind[x])-1;i>=0;i--){
                if(i<sz(ind[x])-1) suf_max+=Sum(ind[x][i],ind[x][i+1]-1);
                while(i1>=0 && ind[x-1][i1]>ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(suf_max,m+Sum(ind[x][i],ind[x-1][i1]-1));
                    i1--;
                }
                MaxSelf(dp[0][x][i],suf_max);
            }
        }
        else if(x==1){
            int i1=0;
            ll pref_max=-LINF;
            for(int i=0;i<sz(ind[x]);i++){
                if(i>0) pref_max+=Sum(ind[x][i-1],ind[x][i]-1);
                while(i1<sz(ind[x-1]) && ind[x-1][i1]<=ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(pref_max,m+Sum(ind[x-1][i1],ind[x][i]-1));
                    i1++;
                }
                MaxSelf(dp[1][x][i],pref_max);
            }

            pref.clear(); pref[-1]=0;
            for(int i=0;i<sz(fish[x]);i++){
                int y=fish[x][i].fi;
                int w=fish[x][i].se;
                pref[y]=pref.upper_bound(y-1)->se+w;
            }

            i1=sz(ind[x-1])-1;
            ll suf_max=-LINF;
            for(int i=sz(ind[x])-1;i>=0;i--){
                if(i<sz(ind[x])-1) suf_max+=Sum(ind[x][i],ind[x][i+1]-1);
                while(i1>=0 && ind[x-1][i1]>ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(suf_max,m+Sum(ind[x][i],ind[x-1][i1]-1));
                    i1--;
                }
                MaxSelf(dp[0][x][i],suf_max);
            }
        }
    }
    ll res=0;
    for(int i=0;i<sz(ind[N-1]);i++){
        ll m=max(dp[0][N-1][i],dp[1][N-1][i]);
        MaxSelf(res,m);
    }
    return res;
}
# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 28428 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '999990243'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Incorrect 319 ms 36472 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '1999943696'
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 46 ms 19024 KB Output is correct
2 Correct 42 ms 18976 KB Output is correct
3 Correct 84 ms 20968 KB Output is correct
4 Correct 73 ms 21564 KB Output is correct
5 Correct 135 ms 26188 KB Output is correct
6 Correct 133 ms 25568 KB Output is correct
7 Correct 138 ms 26116 KB Output is correct
8 Correct 149 ms 26056 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '84310811791'
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '84310811791'
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '84310811791'
10 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 46 ms 19024 KB Output is correct
2 Correct 42 ms 18976 KB Output is correct
3 Correct 84 ms 20968 KB Output is correct
4 Correct 73 ms 21564 KB Output is correct
5 Correct 135 ms 26188 KB Output is correct
6 Correct 133 ms 25568 KB Output is correct
7 Correct 138 ms 26116 KB Output is correct
8 Correct 149 ms 26056 KB Output is correct
9 Correct 156 ms 29004 KB Output is correct
10 Incorrect 120 ms 19136 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '23772043885836'
11 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 28428 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '999990243'
2 Halted 0 ms 0 KB -