oj.uz

Submission #725674

# Submission time Handle Problem Language Result Execution time Memory
725674 2023-04-17T20:49:50 Z Urvuk3 Catfish Farm (IOI22_fish) C++17
0 / 100
 296 ms 36416 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 i=0;i<N;i++){
        ind[i].pb(0);
        ind[i].pb(N);
        sort(all(ind[i]));
        ind.resize(unique(all(ind))-ind.begin());
        dp[0][i].resize(sz(ind[i]));
        dp[1][i].resize(sz(ind[i]));
    }
    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;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 28392 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '13695610151'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 296 ms 36416 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '26306777200'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 19024 KB Output is correct
2 Correct 38 ms 19004 KB Output is correct
3 Runtime error 232 ms 28584 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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: '102829397891'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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: '102829397891'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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: '102829397891'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 19024 KB Output is correct
2 Correct 38 ms 19004 KB Output is correct
3 Runtime error 232 ms 28584 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 28392 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '13695610151'
2 Halted 0 ms 0 KB -