oj.uz

답안 #1022844

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022844 2024-07-14T06:12:28 Z vjudge1 메기 농장 (IOI22_fish) C++17
37 / 100
 1000 ms 2097152 KB 
#include "fish.h"
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

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());
    }
    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 99 ms 69316 KB Output is correct
2 Correct 107 ms 76484 KB Output is correct
3 Correct 44 ms 50524 KB Output is correct
4 Correct 44 ms 50512 KB Output is correct
5 Execution timed out 1080 ms 188492 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 50512 KB Output is correct
2 Correct 45 ms 50508 KB Output is correct
3 Correct 80 ms 65360 KB Output is correct
4 Correct 71 ms 62264 KB Output is correct
5 Correct 112 ms 80976 KB Output is correct
6 Correct 127 ms 80464 KB Output is correct
7 Correct 108 ms 80980 KB Output is correct
8 Correct 108 ms 80980 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 13 ms 28588 KB Output is correct
3 Correct 14 ms 28624 KB Output is correct
4 Correct 13 ms 28508 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 14 ms 28528 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 13 ms 28508 KB Output is correct
9 Correct 14 ms 28780 KB Output is correct
10 Correct 20 ms 29532 KB Output is correct
11 Correct 14 ms 28864 KB Output is correct
12 Correct 15 ms 29276 KB Output is correct
13 Correct 13 ms 28700 KB Output is correct
14 Correct 15 ms 29020 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 13 ms 28588 KB Output is correct
3 Correct 14 ms 28624 KB Output is correct
4 Correct 13 ms 28508 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 14 ms 28528 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 13 ms 28508 KB Output is correct
9 Correct 14 ms 28780 KB Output is correct
10 Correct 20 ms 29532 KB Output is correct
11 Correct 14 ms 28864 KB Output is correct
12 Correct 15 ms 29276 KB Output is correct
13 Correct 13 ms 28700 KB Output is correct
14 Correct 15 ms 29020 KB Output is correct
15 Correct 17 ms 28764 KB Output is correct
16 Correct 40 ms 33364 KB Output is correct
17 Execution timed out 1064 ms 410960 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 13 ms 28588 KB Output is correct
3 Correct 14 ms 28624 KB Output is correct
4 Correct 13 ms 28508 KB Output is correct
5 Correct 14 ms 28508 KB Output is correct
6 Correct 14 ms 28528 KB Output is correct
7 Correct 13 ms 28508 KB Output is correct
8 Correct 13 ms 28508 KB Output is correct
9 Correct 14 ms 28780 KB Output is correct
10 Correct 20 ms 29532 KB Output is correct
11 Correct 14 ms 28864 KB Output is correct
12 Correct 15 ms 29276 KB Output is correct
13 Correct 13 ms 28700 KB Output is correct
14 Correct 15 ms 29020 KB Output is correct
15 Correct 17 ms 28764 KB Output is correct
16 Correct 40 ms 33364 KB Output is correct
17 Execution timed out 1064 ms 410960 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 50512 KB Output is correct
2 Correct 45 ms 50508 KB Output is correct
3 Correct 80 ms 65360 KB Output is correct
4 Correct 71 ms 62264 KB Output is correct
5 Correct 112 ms 80976 KB Output is correct
6 Correct 127 ms 80464 KB Output is correct
7 Correct 108 ms 80980 KB Output is correct
8 Correct 108 ms 80980 KB Output is correct
9 Correct 130 ms 94800 KB Output is correct
10 Correct 91 ms 66388 KB Output is correct
11 Correct 179 ms 104276 KB Output is correct
12 Correct 14 ms 28508 KB Output is correct
13 Correct 13 ms 28376 KB Output is correct
14 Correct 14 ms 28504 KB Output is correct
15 Correct 14 ms 28508 KB Output is correct
16 Correct 14 ms 28428 KB Output is correct
17 Correct 13 ms 28568 KB Output is correct
18 Correct 47 ms 50316 KB Output is correct
19 Correct 46 ms 50516 KB Output is correct
20 Correct 45 ms 50356 KB Output is correct
21 Correct 62 ms 50512 KB Output is correct
22 Correct 146 ms 99408 KB Output is correct
23 Correct 232 ms 146772 KB Output is correct
24 Correct 243 ms 156496 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 69316 KB Output is correct
2 Correct 107 ms 76484 KB Output is correct
3 Correct 44 ms 50524 KB Output is correct
4 Correct 44 ms 50512 KB Output is correct
5 Execution timed out 1080 ms 188492 KB Time limit exceeded
6 Halted 0 ms 0 KB -