답안 #1022814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022814	2024-07-14T05:34:22 Z	vjudge1	메기 농장 (IOI22_fish)	C++17	37 / 100	1000 ms	2097152 KB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define lb lower_bound
#define ub upper_bound

const int MAX=2e5+10;

vector<pair<ll,ll>> y[MAX];
vector<ll> p[MAX];
vector<vector<ll>> dp[MAX];
vector<ll> can[MAX];

ll getSum(int x,ll l,ll r){
    if(l>r)return 0;
    int L=lb(all(y[x]),make_pair(l,0ll))-y[x].begin();
    int R=ub(all(y[x]),make_pair(r+1,0ll))-y[x].begin()-1;
    if(L<=R){
        if(L==0)return p[x][R];
        return p[x][R]-p[x][L-1];
    }
    return 0;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
    for(int i=0;i<M;i++){
        X[i]++;
        Y[i]++;
        y[X[i]].pb({Y[i],i});
    }
    for(int i=1;i<=N;i++){
        if(y[i].empty())continue;
        sort(all(y[i]));
        p[i].pb(W[y[i][0].S]);
        for(int j=1;j<sz(y[i]);j++){
            p[i].pb(p[i].back()+W[y[i][j].S]);
        }
    }
    // cout<<y[5][0].F<<"\n";
    can[0].pb(0);
    can[N+1].pb(0);
    for(int i=1;i<=N;i++){
        can[i].pb(0);
        if(i>0){
            for(auto [x,b]:y[i-1])can[i].pb(x);
        }
        if(i+1<=N){
            for(auto [x,b]:y[i+1])can[i].pb(x);
        }
        sort(all(can[i]));
        can[i].erase(unique(all(can[i])),can[i].end());
    }
    // cout<<can[4].back()<<"\n";
    for(int i=1;i<=N+1;i++){
        dp[i].resize(sz(can[i]));
        for(int j=0;j<sz(dp[i]);j++){
            dp[i][j].resize(sz(can[i-1]));
            for(int k=0;k<sz(can[i-1]);k++){
                dp[i][j][k]=0;
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<sz(can[i]);j++){
            for(int k=0;k<sz(can[i-1]);k++){
                // cout<<i<<" "<<can[i-1][k]<<" "<<can[i][j]<<" "<<dp[i][j][k]<<"\n";
                for(int f=0;f<sz(can[i+1]);f++){
                    ll nxt=dp[i][j][k];
                    {
                        int mx=max(can[i+1][f],can[i-1][k]);
                        // cout<<"!! "<<i<<" "<<can[i][j]+1<<" "<<mx<<" "<<getSum(i,can[i][j]+1,mx)<<"\n";
                        nxt+=getSum(i,can[i][j]+1,mx);
                    }
                    dp[i+1][f][j]=max(dp[i+1][f][j],nxt);
                }
            }
        }
    }
    ll ans=0;
    for(int j=0;j<sz(can[N]);j++)ans=max(ans,dp[N+1][0][j]);
    return ans;
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	38336 KB	Output is correct
2	Correct	75 ms	42180 KB	Output is correct
3	Correct	22 ms	28436 KB	Output is correct
4	Correct	25 ms	28568 KB	Output is correct
5	Execution timed out	1055 ms	91308 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	19036 KB	Output is correct
2	Runtime error	846 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	28504 KB	Output is correct
2	Correct	26 ms	28504 KB	Output is correct
3	Correct	45 ms	37608 KB	Output is correct
4	Correct	58 ms	35148 KB	Output is correct
5	Correct	67 ms	46620 KB	Output is correct
6	Correct	65 ms	45908 KB	Output is correct
7	Correct	67 ms	46416 KB	Output is correct
8	Correct	68 ms	46552 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	19032 KB	Output is correct
2	Correct	9 ms	19036 KB	Output is correct
3	Correct	9 ms	19036 KB	Output is correct
4	Correct	9 ms	19036 KB	Output is correct
5	Correct	9 ms	19036 KB	Output is correct
6	Correct	9 ms	19036 KB	Output is correct
7	Correct	9 ms	19032 KB	Output is correct
8	Correct	9 ms	19032 KB	Output is correct
9	Correct	9 ms	19332 KB	Output is correct
10	Correct	10 ms	19548 KB	Output is correct
11	Correct	9 ms	19292 KB	Output is correct
12	Correct	10 ms	19420 KB	Output is correct
13	Correct	8 ms	19036 KB	Output is correct
14	Correct	9 ms	19292 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	19032 KB	Output is correct
2	Correct	9 ms	19036 KB	Output is correct
3	Correct	9 ms	19036 KB	Output is correct
4	Correct	9 ms	19036 KB	Output is correct
5	Correct	9 ms	19036 KB	Output is correct
6	Correct	9 ms	19036 KB	Output is correct
7	Correct	9 ms	19032 KB	Output is correct
8	Correct	9 ms	19032 KB	Output is correct
9	Correct	9 ms	19332 KB	Output is correct
10	Correct	10 ms	19548 KB	Output is correct
11	Correct	9 ms	19292 KB	Output is correct
12	Correct	10 ms	19420 KB	Output is correct
13	Correct	8 ms	19036 KB	Output is correct
14	Correct	9 ms	19292 KB	Output is correct
15	Correct	9 ms	19292 KB	Output is correct
16	Correct	159 ms	20996 KB	Output is correct
17	Execution timed out	1055 ms	149072 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	19032 KB	Output is correct
2	Correct	9 ms	19036 KB	Output is correct
3	Correct	9 ms	19036 KB	Output is correct
4	Correct	9 ms	19036 KB	Output is correct
5	Correct	9 ms	19036 KB	Output is correct
6	Correct	9 ms	19036 KB	Output is correct
7	Correct	9 ms	19032 KB	Output is correct
8	Correct	9 ms	19032 KB	Output is correct
9	Correct	9 ms	19332 KB	Output is correct
10	Correct	10 ms	19548 KB	Output is correct
11	Correct	9 ms	19292 KB	Output is correct
12	Correct	10 ms	19420 KB	Output is correct
13	Correct	8 ms	19036 KB	Output is correct
14	Correct	9 ms	19292 KB	Output is correct
15	Correct	9 ms	19292 KB	Output is correct
16	Correct	159 ms	20996 KB	Output is correct
17	Execution timed out	1055 ms	149072 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	28504 KB	Output is correct
2	Correct	26 ms	28504 KB	Output is correct
3	Correct	45 ms	37608 KB	Output is correct
4	Correct	58 ms	35148 KB	Output is correct
5	Correct	67 ms	46620 KB	Output is correct
6	Correct	65 ms	45908 KB	Output is correct
7	Correct	67 ms	46416 KB	Output is correct
8	Correct	68 ms	46552 KB	Output is correct
9	Correct	83 ms	50952 KB	Output is correct
10	Correct	61 ms	39852 KB	Output is correct
11	Correct	117 ms	60500 KB	Output is correct
12	Correct	9 ms	19032 KB	Output is correct
13	Correct	8 ms	19032 KB	Output is correct
14	Correct	9 ms	19024 KB	Output is correct
15	Correct	10 ms	19036 KB	Output is correct
16	Correct	8 ms	19036 KB	Output is correct
17	Correct	10 ms	19228 KB	Output is correct
18	Correct	24 ms	28508 KB	Output is correct
19	Correct	21 ms	28508 KB	Output is correct
20	Correct	22 ms	28508 KB	Output is correct
21	Correct	21 ms	28508 KB	Output is correct
22	Correct	99 ms	51936 KB	Output is correct
23	Correct	175 ms	74540 KB	Output is correct
24	Correct	189 ms	78264 KB	Output is correct

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	38336 KB	Output is correct
2	Correct	75 ms	42180 KB	Output is correct
3	Correct	22 ms	28436 KB	Output is correct
4	Correct	25 ms	28568 KB	Output is correct
5	Execution timed out	1055 ms	91308 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

답안 #1022814

Compilation message