답안 #1022834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022834	2024-07-14T06:00:13 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++){
                int r=lb(all(y[i]),make_pair(can[i][j]+1,0ll))-y[i].begin();
                ll sum=0;
                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]);
                        while(r<sz(y[i])&&y[i][r].F<=mx){
                            sum+=W[y[i][r].S];
                            r++;
                        }
                        nxt+=sum;
                    }
                    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	53 ms	37060 KB	Output is correct
2	Correct	62 ms	40128 KB	Output is correct
3	Correct	22 ms	28624 KB	Output is correct
4	Correct	22 ms	28500 KB	Output is correct
5	Execution timed out	1064 ms	90032 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	907 ms	2097152 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	28620 KB	Output is correct
2	Correct	23 ms	28508 KB	Output is correct
3	Correct	59 ms	37624 KB	Output is correct
4	Correct	43 ms	35132 KB	Output is correct
5	Correct	93 ms	46504 KB	Output is correct
6	Correct	82 ms	45900 KB	Output is correct
7	Correct	77 ms	46552 KB	Output is correct
8	Correct	89 ms	46368 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	19036 KB	Output is correct
2	Correct	11 ms	19036 KB	Output is correct
3	Correct	11 ms	19144 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	19180 KB	Output is correct
7	Correct	8 ms	19036 KB	Output is correct
8	Correct	8 ms	19116 KB	Output is correct
9	Correct	11 ms	19288 KB	Output is correct
10	Correct	10 ms	19548 KB	Output is correct
11	Correct	13 ms	19292 KB	Output is correct
12	Correct	9 ms	19288 KB	Output is correct
13	Correct	9 ms	19036 KB	Output is correct
14	Correct	9 ms	19288 KB	Output is correct

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	19036 KB	Output is correct
2	Correct	11 ms	19036 KB	Output is correct
3	Correct	11 ms	19144 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	19180 KB	Output is correct
7	Correct	8 ms	19036 KB	Output is correct
8	Correct	8 ms	19116 KB	Output is correct
9	Correct	11 ms	19288 KB	Output is correct
10	Correct	10 ms	19548 KB	Output is correct
11	Correct	13 ms	19292 KB	Output is correct
12	Correct	9 ms	19288 KB	Output is correct
13	Correct	9 ms	19036 KB	Output is correct
14	Correct	9 ms	19288 KB	Output is correct
15	Correct	9 ms	19292 KB	Output is correct
16	Correct	41 ms	20828 KB	Output is correct
17	Execution timed out	1080 ms	149076 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	19036 KB	Output is correct
2	Correct	11 ms	19036 KB	Output is correct
3	Correct	11 ms	19144 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	19180 KB	Output is correct
7	Correct	8 ms	19036 KB	Output is correct
8	Correct	8 ms	19116 KB	Output is correct
9	Correct	11 ms	19288 KB	Output is correct
10	Correct	10 ms	19548 KB	Output is correct
11	Correct	13 ms	19292 KB	Output is correct
12	Correct	9 ms	19288 KB	Output is correct
13	Correct	9 ms	19036 KB	Output is correct
14	Correct	9 ms	19288 KB	Output is correct
15	Correct	9 ms	19292 KB	Output is correct
16	Correct	41 ms	20828 KB	Output is correct
17	Execution timed out	1080 ms	149076 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	28620 KB	Output is correct
2	Correct	23 ms	28508 KB	Output is correct
3	Correct	59 ms	37624 KB	Output is correct
4	Correct	43 ms	35132 KB	Output is correct
5	Correct	93 ms	46504 KB	Output is correct
6	Correct	82 ms	45900 KB	Output is correct
7	Correct	77 ms	46552 KB	Output is correct
8	Correct	89 ms	46368 KB	Output is correct
9	Correct	91 ms	51028 KB	Output is correct
10	Correct	64 ms	39760 KB	Output is correct
11	Correct	142 ms	60428 KB	Output is correct
12	Correct	9 ms	19036 KB	Output is correct
13	Correct	8 ms	19036 KB	Output is correct
14	Correct	8 ms	19148 KB	Output is correct
15	Correct	8 ms	19032 KB	Output is correct
16	Correct	8 ms	19032 KB	Output is correct
17	Correct	9 ms	19160 KB	Output is correct
18	Correct	22 ms	28620 KB	Output is correct
19	Correct	23 ms	28604 KB	Output is correct
20	Correct	22 ms	28616 KB	Output is correct
21	Correct	24 ms	28508 KB	Output is correct
22	Correct	87 ms	51944 KB	Output is correct
23	Correct	155 ms	74428 KB	Output is correct
24	Correct	159 ms	78164 KB	Output is correct

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	37060 KB	Output is correct
2	Correct	62 ms	40128 KB	Output is correct
3	Correct	22 ms	28624 KB	Output is correct
4	Correct	22 ms	28500 KB	Output is correct
5	Execution timed out	1064 ms	90032 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

답안 #1022834

Compilation message