oj.uz

Submission #863427

# Submission time Handle Problem Language Result Execution time Memory
863427 2023-10-20T08:50:43 Z neki Catfish Farm (IOI22_fish) C++17
0 / 100
 159 ms 63100 KB 
#include <bits/stdc++.h>
#include "fish.h"

#define ll long long
#define vc vector
 
using namespace std;
 
ll max_weights(int N, int M, vc<int> X, vc<int> Y, vc<int> W) {
    vc<ll> ind(M); for(ll i=0;i<M;++i) ind[i]=i;
    sort(ind.begin(),ind.end(),[&](ll a,ll b){return Y[a]<Y[b];});
    
    vc<vc<pair<ll, ll>>> f(N);
    vc<vc<ll>> rel(N, vc<ll>(1, -1)), dpm(N, vc<ll>(1, 0)), dpv(N, vc<ll>(1, 0)), dpn(N, vc<ll>(1, 0));
    for(auto i: ind){
        f[X[i]].emplace_back(Y[i], W[i]);
        if(X[i]-1>=0) rel[X[i]-1].push_back(Y[i]),dpn[X[i]-1].push_back(0),dpm[X[i]-1].push_back(0),dpv[X[i]-1].push_back(0);
        if(X[i]+1<N) rel[X[i]+1].push_back(Y[i]),dpn[X[i]+1].push_back(0),dpm[X[i]+1].push_back(0),dpv[X[i]+1].push_back(0);
    }
    
    for(ll i=0;i<N;++i){
        if(i-2>=0){
            for(ll j=0, prej=0, c=0, pp=0, mm=0;j<(ll)rel[i].size();++j){
                while(pp<(ll)rel[i-2].size()&&rel[i-2][pp]<=rel[i][j])mm=max(mm, max(dpv[i-2][pp], dpm[i-2][pp])),++pp;
                while(prej<(ll)f[i-1].size()&&f[i-1][prej].first<=rel[i][j])c+=f[i-1][prej++].second;
                dpv[i][j]=max(dpv[i][j],mm+c);
                dpm[i][j]=max(dpm[i][j],mm+c);
            }
            for(ll j=(ll)rel[i].size()-1, pp=(ll)rel[i-2].size(), mm=0;j>=0;--j){
                while(pp-1>=0&&rel[i-2][pp-1]>=rel[i][j])mm=max(mm, dpn[i-2][--pp]);
                dpv[i][j]=max(dpv[i][j],mm);
                dpm[i][j]=max(dpm[i][j],mm);
            }
        }
        if(i-1>=0){
            for(ll j=0, prej=0, pf=0, mm=0;j<(ll)rel[i].size();++j){
                while(1){
                    if(prej<(ll)rel[i-1].size()&&rel[i-1][prej]<=rel[i][j]&&(!(pf<(ll)f[i-1].size()) || rel[i-1][prej]<f[i-1][pf].first))mm=max(mm, dpm[i-1][prej++]);
                    else if(pf<(ll)f[i-1].size()&&f[i-1][pf].first<=rel[i][j])mm+=f[i-1][pf++].second;
                    else break;
                }
                dpm[i][j]=max(dpm[i][j], mm);
            }
            ll c=0; for(auto v: f[i])c+=v.second;
            vc<ll> pr=dpv[i-1];
            for(ll j=0, nas=0, c=0;j<(ll)rel[i-1].size();++j){
                while(nas<(ll)f[i].size()&&f[i][nas].first<=rel[i-1][j])c+=f[i][nas++].second;
                pr[j]+=c;
            }
            for(ll j=(ll)pr.size()-2;j>=0;--j)pr[j]=max(pr[j],pr[j+1]);

            for(ll j=(ll)rel[i].size()-1, prej=(ll)rel[i-1].size(), pf=(ll)f[i].size()-1;j>=0;--j){
                while(pf>=0&&rel[i][j]<f[i][pf].first)c-=f[i][pf--].second;
                while(prej-1>=0&&rel[i-1][prej]>=rel[i][j])--prej;
                if(prej<(ll)rel[i-1].size()) dpv[i][j]=max(dpv[i][j], pr[prej]-c);
            }

            for(ll j=0, pf=0, c=0;j<(ll)rel[i].size();++j){
                while(pf<(ll)f[i-1].size()&&f[i-1][pf].first<=rel[i][j])c+=f[i-1][pf++].second;
                dpv[i][j]=max(dpv[i][j], max(dpv[i-1][0], dpm[i-1][0])+c);
                dpm[i][j]=max(dpm[i][j], max(dpv[i-1][0], dpm[i-1][0])+c);
            }
        }
        if(i+1<N){
            for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
                while(nas<(ll)f[i+1].size()&&f[i+1][nas].first<=rel[i][j])c+=f[i+1][nas++].second;
                dpn[i][j]=max(dpn[i][j],max(dpv[i][j], dpm[i][j])+c);
            }
        }
    }
    ll ans=0;
    for(ll i=0;i<N;++i){
        for(ll j=0;j<(ll)rel[i].size();++j)ans=max({ans, dpn[i][j], dpv[i][j], dpm[i][j]});
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29248 KB Output is correct
2 Correct 60 ms 33172 KB Output is correct
3 Correct 26 ms 24664 KB Output is correct
4 Correct 31 ms 24680 KB Output is correct
5 Incorrect 159 ms 63100 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '299628921470958'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24664 KB Output is correct
2 Correct 25 ms 24668 KB Output is correct
3 Incorrect 128 ms 30012 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '32717839057000'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 604 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '326664473535'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 604 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '326664473535'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 604 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '326664473535'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24664 KB Output is correct
2 Correct 25 ms 24668 KB Output is correct
3 Incorrect 128 ms 30012 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '32717839057000'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29248 KB Output is correct
2 Correct 60 ms 33172 KB Output is correct
3 Correct 26 ms 24664 KB Output is correct
4 Correct 31 ms 24680 KB Output is correct
5 Incorrect 159 ms 63100 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '299628921470958'
6 Halted 0 ms 0 KB -