답안 #863451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863451	2023-10-20T11:33:37 Z	neki	메기 농장 (IOI22_fish)	C++17	18 / 100	413 ms	74876 KB

fish

#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 mm=0;
            for(auto v: dpn[i-1]) mm=max(mm, v);

            ll c=0; for(auto v: f[i])c+=v.second;
            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], dpm[i][j], mm-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
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	29224 KB	Output is correct
2	Correct	59 ms	32664 KB	Output is correct
3	Correct	23 ms	24664 KB	Output is correct
4	Correct	24 ms	24668 KB	Output is correct
5	Correct	150 ms	63100 KB	Output is correct
6	Correct	413 ms	74876 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	85 ms	40304 KB	Output is correct
3	Correct	104 ms	44072 KB	Output is correct
4	Correct	55 ms	29224 KB	Output is correct
5	Correct	59 ms	32552 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	23 ms	24668 KB	Output is correct
11	Correct	25 ms	24668 KB	Output is correct
12	Correct	55 ms	31192 KB	Output is correct
13	Correct	64 ms	35756 KB	Output is correct
14	Correct	52 ms	31696 KB	Output is correct
15	Correct	57 ms	34724 KB	Output is correct
16	Correct	65 ms	32056 KB	Output is correct
17	Correct	57 ms	35240 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	24668 KB	Output is correct
2	Correct	26 ms	24668 KB	Output is correct
3	Correct	96 ms	30036 KB	Output is correct
4	Correct	70 ms	29548 KB	Output is correct
5	Correct	229 ms	38996 KB	Output is correct
6	Correct	208 ms	38988 KB	Output is correct
7	Correct	211 ms	38992 KB	Output is correct
8	Correct	210 ms	38992 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 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	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Incorrect	2 ms	860 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '799682693947'
11	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 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	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Incorrect	2 ms	860 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '799682693947'
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 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	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Incorrect	2 ms	860 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '799682693947'
11	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	24668 KB	Output is correct
2	Correct	26 ms	24668 KB	Output is correct
3	Correct	96 ms	30036 KB	Output is correct
4	Correct	70 ms	29548 KB	Output is correct
5	Correct	229 ms	38996 KB	Output is correct
6	Correct	208 ms	38988 KB	Output is correct
7	Correct	211 ms	38992 KB	Output is correct
8	Correct	210 ms	38992 KB	Output is correct
9	Correct	95 ms	37204 KB	Output is correct
10	Correct	158 ms	30284 KB	Output is correct
11	Correct	399 ms	58948 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	24 ms	24668 KB	Output is correct
19	Correct	24 ms	24572 KB	Output is correct
20	Correct	24 ms	24668 KB	Output is correct
21	Correct	23 ms	24668 KB	Output is correct
22	Incorrect	249 ms	39080 KB	1st lines differ - on the 1st token, expected: '45561826463480', found: '44672515017346'
23	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	29224 KB	Output is correct
2	Correct	59 ms	32664 KB	Output is correct
3	Correct	23 ms	24664 KB	Output is correct
4	Correct	24 ms	24668 KB	Output is correct
5	Correct	150 ms	63100 KB	Output is correct
6	Correct	413 ms	74876 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	85 ms	40304 KB	Output is correct
9	Correct	104 ms	44072 KB	Output is correct
10	Correct	55 ms	29224 KB	Output is correct
11	Correct	59 ms	32552 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	23 ms	24668 KB	Output is correct
17	Correct	25 ms	24668 KB	Output is correct
18	Correct	55 ms	31192 KB	Output is correct
19	Correct	64 ms	35756 KB	Output is correct
20	Correct	52 ms	31696 KB	Output is correct
21	Correct	57 ms	34724 KB	Output is correct
22	Correct	65 ms	32056 KB	Output is correct
23	Correct	57 ms	35240 KB	Output is correct
24	Correct	25 ms	24668 KB	Output is correct
25	Correct	26 ms	24668 KB	Output is correct
26	Correct	96 ms	30036 KB	Output is correct
27	Correct	70 ms	29548 KB	Output is correct
28	Correct	229 ms	38996 KB	Output is correct
29	Correct	208 ms	38988 KB	Output is correct
30	Correct	211 ms	38992 KB	Output is correct
31	Correct	210 ms	38992 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	0 ms	344 KB	Output is correct
34	Correct	0 ms	344 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	344 KB	Output is correct
40	Correct	1 ms	604 KB	Output is correct
41	Incorrect	2 ms	860 KB	1st lines differ - on the 1st token, expected: '799839985182', found: '799682693947'
42	Halted	0 ms	0 KB	-

답안 #863451

Compilation message