oj.uz

Submission #1033024

# Submission time Handle Problem Language Result Execution time Memory
1033024 2024-07-24T12:03:58 Z vjudge1 Catfish Farm (IOI22_fish) C++17
32 / 100
 399 ms 305504 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
#define mem(a,i) memset(a,i,sizeof(a))

const int MAX=2e5+10;

int n;
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];
vector<vector<ll>> w;

struct t300{

    ll dp[3010][3010][2];

    ll getP(int i,int l,int r){
        if(l>r||i==0)return 0;
        return p[i][r]-p[i][l-1];
    }

    ll solve300(){
        for(int i=1;i<=n;i++){
            p[i].resize(n+10);
            p[i][0]=0;
            for(int j=1;j<=n;j++){
                p[i][j]=p[i][j-1]+w[i][j];
            }
        }
        mem(dp,0);
        for(int i=2;i<=n;i++){
            {
                ll mx=0;
                for(int j=n;j>=0;j--){
                    mx=max(mx,max(dp[i-1][j][0],dp[i-1][j][1])+p[i][j]);
                    dp[i][j][0]=mx-p[i][j];
                }

            }
            {
                ll mx=0;
                for(int j=0;j<=n;j++){
                    mx=max(mx,dp[i-1][j][1]-p[i-1][j]);
                    dp[i][j][1]=mx+p[i-1][j];
                }
                
            }
            // for(int j=0;j<=n;j++){
            //     {
            //         for(int f=0;f<=j;f++){
            //             dp[i][j][1]=max(dp[i][j][1],dp[i-1][f][1]+getP(i-1,f+1,j));
            //         }
            //         dp[i][j][1]=max(dp[i][j][1],dp[i-1][0][0]);
            //     }
            // }
        }
        ll ans=0;
        for(int j=0;j<=n;j++)ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
        return ans;
    }
};


long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
    // assert(N<=300);
    n=N;
    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);
        }
        ll sum=0;
        for(int i=0;i<M;i++){
            if(X[i]%2==0)sum+=W[i];
        }
        ll 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]);
        }
    }
    if(N<=3000){
        w.resize(N+10);
        for(int i=1;i<=n;i++){
            w[i].resize(n+10);
            for(int j=1;j<=n;j++){
                w[i][j]=0;
            }
            for(auto [pos,num]:y[i])w[i][pos]=W[num];
        }
        t300 FFF;
        return FFF.solve300();
    }
    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 117 ms 182472 KB Output is correct
2 Correct 117 ms 183744 KB Output is correct
3 Correct 98 ms 174936 KB Output is correct
4 Correct 105 ms 174968 KB Output is correct
5 Correct 194 ms 198328 KB Output is correct
6 Correct 196 ms 200792 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 175136 KB Output is correct
2 Correct 134 ms 187452 KB Output is correct
3 Correct 136 ms 189436 KB Output is correct
4 Correct 117 ms 182468 KB Output is correct
5 Correct 119 ms 183928 KB Output is correct
6 Correct 85 ms 174904 KB Output is correct
7 Correct 109 ms 174928 KB Output is correct
8 Correct 101 ms 174932 KB Output is correct
9 Correct 107 ms 175188 KB Output is correct
10 Correct 105 ms 175084 KB Output is correct
11 Correct 86 ms 174932 KB Output is correct
12 Correct 115 ms 182528 KB Output is correct
13 Correct 121 ms 183792 KB Output is correct
14 Correct 127 ms 182172 KB Output is correct
15 Correct 126 ms 181816 KB Output is correct
16 Correct 147 ms 182200 KB Output is correct
17 Correct 140 ms 182976 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 174936 KB Output is correct
2 Correct 152 ms 196952 KB Output is correct
3 Correct 161 ms 212428 KB Output is correct
4 Correct 147 ms 208956 KB Output is correct
5 Correct 208 ms 228220 KB Output is correct
6 Correct 216 ms 227784 KB Output is correct
7 Correct 185 ms 228264 KB Output is correct
8 Correct 189 ms 228296 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 175048 KB Output is correct
2 Correct 90 ms 175128 KB Output is correct
3 Correct 92 ms 174932 KB Output is correct
4 Correct 94 ms 174932 KB Output is correct
5 Correct 109 ms 174900 KB Output is correct
6 Correct 86 ms 174900 KB Output is correct
7 Correct 92 ms 175104 KB Output is correct
8 Correct 84 ms 174928 KB Output is correct
9 Incorrect 102 ms 175480 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 175048 KB Output is correct
2 Correct 90 ms 175128 KB Output is correct
3 Correct 92 ms 174932 KB Output is correct
4 Correct 94 ms 174932 KB Output is correct
5 Correct 109 ms 174900 KB Output is correct
6 Correct 86 ms 174900 KB Output is correct
7 Correct 92 ms 175104 KB Output is correct
8 Correct 84 ms 174928 KB Output is correct
9 Incorrect 102 ms 175480 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 175048 KB Output is correct
2 Correct 90 ms 175128 KB Output is correct
3 Correct 92 ms 174932 KB Output is correct
4 Correct 94 ms 174932 KB Output is correct
5 Correct 109 ms 174900 KB Output is correct
6 Correct 86 ms 174900 KB Output is correct
7 Correct 92 ms 175104 KB Output is correct
8 Correct 84 ms 174928 KB Output is correct
9 Incorrect 102 ms 175480 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 174936 KB Output is correct
2 Correct 152 ms 196952 KB Output is correct
3 Correct 161 ms 212428 KB Output is correct
4 Correct 147 ms 208956 KB Output is correct
5 Correct 208 ms 228220 KB Output is correct
6 Correct 216 ms 227784 KB Output is correct
7 Correct 185 ms 228264 KB Output is correct
8 Correct 189 ms 228296 KB Output is correct
9 Correct 238 ms 244560 KB Output is correct
10 Correct 166 ms 213588 KB Output is correct
11 Correct 299 ms 252220 KB Output is correct
12 Correct 89 ms 175004 KB Output is correct
13 Correct 95 ms 174932 KB Output is correct
14 Correct 132 ms 175048 KB Output is correct
15 Correct 88 ms 175132 KB Output is correct
16 Correct 88 ms 174932 KB Output is correct
17 Correct 94 ms 174928 KB Output is correct
18 Correct 82 ms 175096 KB Output is correct
19 Correct 120 ms 175112 KB Output is correct
20 Correct 160 ms 196944 KB Output is correct
21 Correct 113 ms 196948 KB Output is correct
22 Correct 291 ms 248164 KB Output is correct
23 Correct 372 ms 294944 KB Output is correct
24 Correct 399 ms 305504 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 182472 KB Output is correct
2 Correct 117 ms 183744 KB Output is correct
3 Correct 98 ms 174936 KB Output is correct
4 Correct 105 ms 174968 KB Output is correct
5 Correct 194 ms 198328 KB Output is correct
6 Correct 196 ms 200792 KB Output is correct
7 Correct 105 ms 175136 KB Output is correct
8 Correct 134 ms 187452 KB Output is correct
9 Correct 136 ms 189436 KB Output is correct
10 Correct 117 ms 182468 KB Output is correct
11 Correct 119 ms 183928 KB Output is correct
12 Correct 85 ms 174904 KB Output is correct
13 Correct 109 ms 174928 KB Output is correct
14 Correct 101 ms 174932 KB Output is correct
15 Correct 107 ms 175188 KB Output is correct
16 Correct 105 ms 175084 KB Output is correct
17 Correct 86 ms 174932 KB Output is correct
18 Correct 115 ms 182528 KB Output is correct
19 Correct 121 ms 183792 KB Output is correct
20 Correct 127 ms 182172 KB Output is correct
21 Correct 126 ms 181816 KB Output is correct
22 Correct 147 ms 182200 KB Output is correct
23 Correct 140 ms 182976 KB Output is correct
24 Correct 86 ms 174936 KB Output is correct
25 Correct 152 ms 196952 KB Output is correct
26 Correct 161 ms 212428 KB Output is correct
27 Correct 147 ms 208956 KB Output is correct
28 Correct 208 ms 228220 KB Output is correct
29 Correct 216 ms 227784 KB Output is correct
30 Correct 185 ms 228264 KB Output is correct
31 Correct 189 ms 228296 KB Output is correct
32 Correct 85 ms 175048 KB Output is correct
33 Correct 90 ms 175128 KB Output is correct
34 Correct 92 ms 174932 KB Output is correct
35 Correct 94 ms 174932 KB Output is correct
36 Correct 109 ms 174900 KB Output is correct
37 Correct 86 ms 174900 KB Output is correct
38 Correct 92 ms 175104 KB Output is correct
39 Correct 84 ms 174928 KB Output is correct
40 Incorrect 102 ms 175480 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
41 Halted 0 ms 0 KB -