oj.uz

Submission #1022851

# Submission time Handle Problem Language Result Execution time Memory
1022851 2024-07-14T06:21:30 Z vjudge1 Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 416280 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];
vector<pair<int,int>> vec[MAX];

long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
    // assert(N<=300);
    int MX=0;
    bool sub=1;
    for(int i=0;i<M;i++){
        X[i]++;
        Y[i]++;
        y[X[i]].pb({Y[i],i});
        vec[Y[i]].pb({X[i],W[i]});
        sub&=(X[i]%2==1);
        MX=max(MX,X[i]);
    }
    if(sub){
        ll ans=0;
        for(int i=0;i<M;i++)ans+=W[i];
        return ans;
    }
    if(MX<=2){
        if(N==2){
            ll f=0,f1=0;
            for(int i=0;i<M;i++){
                if(X[i]%2)f+=W[i];
                else f1+=W[i];
            }
            return max(f,f1);
        }
        int sum=0;
        for(int i=0;i<M;i++){
            if(X[i]%2==0)sum+=W[i];
        }
        int ans=sum;
        for(int i=1;i<=N;i++){
            for(auto [x,w]:vec[i]){
                if(x%2==1)sum+=w;
                else sum-=w;
            }
            ans=max(ans,sum);
        }
        return ans;
    }
    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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 40652 KB Output is correct
2 Correct 42 ms 42028 KB Output is correct
3 Correct 15 ms 33112 KB Output is correct
4 Correct 14 ms 33320 KB Output is correct
5 Correct 108 ms 56228 KB Output is correct
6 Correct 120 ms 58960 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33112 KB Output is correct
2 Incorrect 60 ms 45624 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '2147468759'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33112 KB Output is correct
2 Correct 51 ms 55136 KB Output is correct
3 Correct 83 ms 70492 KB Output is correct
4 Correct 74 ms 67264 KB Output is correct
5 Correct 115 ms 86428 KB Output is correct
6 Correct 108 ms 85704 KB Output is correct
7 Correct 120 ms 86468 KB Output is correct
8 Correct 116 ms 86304 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33116 KB Output is correct
2 Correct 16 ms 33116 KB Output is correct
3 Correct 16 ms 33116 KB Output is correct
4 Correct 15 ms 33244 KB Output is correct
5 Correct 14 ms 33116 KB Output is correct
6 Correct 16 ms 33148 KB Output is correct
7 Correct 16 ms 33252 KB Output is correct
8 Correct 19 ms 33116 KB Output is correct
9 Correct 17 ms 33372 KB Output is correct
10 Correct 19 ms 34200 KB Output is correct
11 Correct 16 ms 33636 KB Output is correct
12 Correct 18 ms 33884 KB Output is correct
13 Correct 16 ms 33220 KB Output is correct
14 Correct 17 ms 33628 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33116 KB Output is correct
2 Correct 16 ms 33116 KB Output is correct
3 Correct 16 ms 33116 KB Output is correct
4 Correct 15 ms 33244 KB Output is correct
5 Correct 14 ms 33116 KB Output is correct
6 Correct 16 ms 33148 KB Output is correct
7 Correct 16 ms 33252 KB Output is correct
8 Correct 19 ms 33116 KB Output is correct
9 Correct 17 ms 33372 KB Output is correct
10 Correct 19 ms 34200 KB Output is correct
11 Correct 16 ms 33636 KB Output is correct
12 Correct 18 ms 33884 KB Output is correct
13 Correct 16 ms 33220 KB Output is correct
14 Correct 17 ms 33628 KB Output is correct
15 Correct 15 ms 33484 KB Output is correct
16 Correct 41 ms 38328 KB Output is correct
17 Execution timed out 1087 ms 416280 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33116 KB Output is correct
2 Correct 16 ms 33116 KB Output is correct
3 Correct 16 ms 33116 KB Output is correct
4 Correct 15 ms 33244 KB Output is correct
5 Correct 14 ms 33116 KB Output is correct
6 Correct 16 ms 33148 KB Output is correct
7 Correct 16 ms 33252 KB Output is correct
8 Correct 19 ms 33116 KB Output is correct
9 Correct 17 ms 33372 KB Output is correct
10 Correct 19 ms 34200 KB Output is correct
11 Correct 16 ms 33636 KB Output is correct
12 Correct 18 ms 33884 KB Output is correct
13 Correct 16 ms 33220 KB Output is correct
14 Correct 17 ms 33628 KB Output is correct
15 Correct 15 ms 33484 KB Output is correct
16 Correct 41 ms 38328 KB Output is correct
17 Execution timed out 1087 ms 416280 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33112 KB Output is correct
2 Correct 51 ms 55136 KB Output is correct
3 Correct 83 ms 70492 KB Output is correct
4 Correct 74 ms 67264 KB Output is correct
5 Correct 115 ms 86428 KB Output is correct
6 Correct 108 ms 85704 KB Output is correct
7 Correct 120 ms 86468 KB Output is correct
8 Correct 116 ms 86304 KB Output is correct
9 Correct 147 ms 102740 KB Output is correct
10 Correct 95 ms 71900 KB Output is correct
11 Correct 181 ms 110648 KB Output is correct
12 Correct 18 ms 33624 KB Output is correct
13 Correct 16 ms 33312 KB Output is correct
14 Correct 15 ms 33216 KB Output is correct
15 Correct 17 ms 33316 KB Output is correct
16 Correct 16 ms 33116 KB Output is correct
17 Correct 16 ms 33312 KB Output is correct
18 Correct 15 ms 33116 KB Output is correct
19 Correct 15 ms 33120 KB Output is correct
20 Correct 47 ms 55124 KB Output is correct
21 Correct 46 ms 55120 KB Output is correct
22 Correct 162 ms 106320 KB Output is correct
23 Correct 230 ms 152884 KB Output is correct
24 Correct 312 ms 163752 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 40652 KB Output is correct
2 Correct 42 ms 42028 KB Output is correct
3 Correct 15 ms 33112 KB Output is correct
4 Correct 14 ms 33320 KB Output is correct
5 Correct 108 ms 56228 KB Output is correct
6 Correct 120 ms 58960 KB Output is correct
7 Correct 15 ms 33112 KB Output is correct
8 Incorrect 60 ms 45624 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '2147468759'
9 Halted 0 ms 0 KB -