oj.uz

답안 #1022842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022842 2024-07-14T06:07:13 Z vjudge1 메기 농장 (IOI22_fish) C++17
37 / 100
 1000 ms 2097152 KB 
#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;
}

vector<vector<ll>> sumF[MAX];
vector<vector<ll>> sumB[MAX];

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=0;i<N;i++){
        sumF[i].resize(sz(can[i]));
        for(int j=0;j<sz(can[i]);j++){
            sumF[i][j].resize(sz(can[i+1]));
            for(int k=0;k<sz(can[i+1]);k++){
                sumF[i][j][k]=getSum(i+1,can[i+1][k]+1,can[i][j]);
            }
        }
    }
    for(int i=1;i<=N+1;i++){
        sumB[i].resize(sz(can[i]));
        for(int j=0;j<sz(can[i]);j++){
            sumB[i][j].resize(sz(can[i-1]));
            for(int k=0;k<sz(can[i-1]);k++){
                sumB[i][j][k]=getSum(i-1,can[i-1][k]+1,can[i][j]);
            }
        }
    }
    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++){
                for(int f=0;f<sz(can[i+1]);f++){
                    ll nxt=dp[i][j][k];
                    {

                        nxt+=max(sumF[i-1][k][j],sumB[i+1][f][j]);
                    }
                    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 90 ms 67776 KB Output is correct
2 Correct 115 ms 76240 KB Output is correct
3 Correct 46 ms 50408 KB Output is correct
4 Correct 47 ms 50260 KB Output is correct
5 Execution timed out 1079 ms 186072 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 50488 KB Output is correct
2 Correct 56 ms 50348 KB Output is correct
3 Correct 78 ms 64592 KB Output is correct
4 Correct 72 ms 61520 KB Output is correct
5 Correct 109 ms 79440 KB Output is correct
6 Correct 106 ms 79284 KB Output is correct
7 Correct 108 ms 79440 KB Output is correct
8 Correct 110 ms 79292 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 13 ms 28468 KB Output is correct
3 Correct 13 ms 28520 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 13 ms 28508 KB Output is correct
6 Correct 13 ms 28508 KB Output is correct
7 Correct 12 ms 28624 KB Output is correct
8 Correct 13 ms 28508 KB Output is correct
9 Correct 13 ms 28764 KB Output is correct
10 Correct 15 ms 29532 KB Output is correct
11 Correct 14 ms 29020 KB Output is correct
12 Correct 14 ms 29272 KB Output is correct
13 Correct 13 ms 28508 KB Output is correct
14 Correct 14 ms 29020 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 13 ms 28468 KB Output is correct
3 Correct 13 ms 28520 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 13 ms 28508 KB Output is correct
6 Correct 13 ms 28508 KB Output is correct
7 Correct 12 ms 28624 KB Output is correct
8 Correct 13 ms 28508 KB Output is correct
9 Correct 13 ms 28764 KB Output is correct
10 Correct 15 ms 29532 KB Output is correct
11 Correct 14 ms 29020 KB Output is correct
12 Correct 14 ms 29272 KB Output is correct
13 Correct 13 ms 28508 KB Output is correct
14 Correct 14 ms 29020 KB Output is correct
15 Correct 14 ms 28764 KB Output is correct
16 Correct 43 ms 33372 KB Output is correct
17 Execution timed out 1109 ms 410196 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 13 ms 28468 KB Output is correct
3 Correct 13 ms 28520 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 13 ms 28508 KB Output is correct
6 Correct 13 ms 28508 KB Output is correct
7 Correct 12 ms 28624 KB Output is correct
8 Correct 13 ms 28508 KB Output is correct
9 Correct 13 ms 28764 KB Output is correct
10 Correct 15 ms 29532 KB Output is correct
11 Correct 14 ms 29020 KB Output is correct
12 Correct 14 ms 29272 KB Output is correct
13 Correct 13 ms 28508 KB Output is correct
14 Correct 14 ms 29020 KB Output is correct
15 Correct 14 ms 28764 KB Output is correct
16 Correct 43 ms 33372 KB Output is correct
17 Execution timed out 1109 ms 410196 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 50488 KB Output is correct
2 Correct 56 ms 50348 KB Output is correct
3 Correct 78 ms 64592 KB Output is correct
4 Correct 72 ms 61520 KB Output is correct
5 Correct 109 ms 79440 KB Output is correct
6 Correct 106 ms 79284 KB Output is correct
7 Correct 108 ms 79440 KB Output is correct
8 Correct 110 ms 79292 KB Output is correct
9 Correct 134 ms 93476 KB Output is correct
10 Correct 86 ms 64500 KB Output is correct
11 Correct 183 ms 100692 KB Output is correct
12 Correct 17 ms 28508 KB Output is correct
13 Correct 14 ms 28592 KB Output is correct
14 Correct 14 ms 28504 KB Output is correct
15 Correct 13 ms 28508 KB Output is correct
16 Correct 14 ms 28600 KB Output is correct
17 Correct 14 ms 28504 KB Output is correct
18 Correct 45 ms 50516 KB Output is correct
19 Correct 45 ms 50516 KB Output is correct
20 Correct 44 ms 50488 KB Output is correct
21 Correct 44 ms 50512 KB Output is correct
22 Correct 142 ms 97364 KB Output is correct
23 Correct 230 ms 143188 KB Output is correct
24 Correct 242 ms 152400 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 67776 KB Output is correct
2 Correct 115 ms 76240 KB Output is correct
3 Correct 46 ms 50408 KB Output is correct
4 Correct 47 ms 50260 KB Output is correct
5 Execution timed out 1079 ms 186072 KB Time limit exceeded
6 Halted 0 ms 0 KB -