oj.uz

Submission #1022814

# Submission time Handle Problem Language Result Execution time Memory
1022814 2024-07-14T05:34:22 Z vjudge1 Catfish Farm (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;
}

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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -