oj.uz

Submission #1023108

# Submission time Handle Problem Language Result Execution time Memory
1023108 2024-07-14T09:46:45 Z vjudge1 Catfish Farm (IOI22_fish) C++17
84 / 100
 970 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
#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];
                    dp[i][j][1]=max(dp[i][j][1],dp[i-1][0][0]);
                }
                
            }
            // 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 108 ms 181956 KB Output is correct
2 Correct 105 ms 182980 KB Output is correct
3 Correct 85 ms 174932 KB Output is correct
4 Correct 79 ms 175104 KB Output is correct
5 Correct 157 ms 195112 KB Output is correct
6 Correct 183 ms 197716 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 174928 KB Output is correct
2 Correct 132 ms 185640 KB Output is correct
3 Correct 146 ms 188088 KB Output is correct
4 Correct 116 ms 181960 KB Output is correct
5 Correct 119 ms 183028 KB Output is correct
6 Correct 87 ms 174928 KB Output is correct
7 Correct 87 ms 174928 KB Output is correct
8 Correct 85 ms 174932 KB Output is correct
9 Correct 87 ms 174944 KB Output is correct
10 Correct 88 ms 174932 KB Output is correct
11 Correct 89 ms 174932 KB Output is correct
12 Correct 108 ms 181960 KB Output is correct
13 Correct 116 ms 182976 KB Output is correct
14 Correct 107 ms 181668 KB Output is correct
15 Correct 127 ms 181124 KB Output is correct
16 Correct 109 ms 181816 KB Output is correct
17 Correct 115 ms 182464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 175084 KB Output is correct
2 Correct 120 ms 196944 KB Output is correct
3 Correct 151 ms 211532 KB Output is correct
4 Correct 142 ms 208328 KB Output is correct
5 Correct 188 ms 226632 KB Output is correct
6 Correct 193 ms 226612 KB Output is correct
7 Correct 179 ms 226664 KB Output is correct
8 Correct 183 ms 226756 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 175184 KB Output is correct
2 Correct 92 ms 174928 KB Output is correct
3 Correct 89 ms 174992 KB Output is correct
4 Correct 87 ms 174888 KB Output is correct
5 Correct 85 ms 174928 KB Output is correct
6 Correct 85 ms 174972 KB Output is correct
7 Correct 87 ms 174928 KB Output is correct
8 Correct 91 ms 174932 KB Output is correct
9 Correct 94 ms 175424 KB Output is correct
10 Correct 99 ms 176724 KB Output is correct
11 Correct 93 ms 175440 KB Output is correct
12 Correct 95 ms 176716 KB Output is correct
13 Correct 89 ms 175188 KB Output is correct
14 Correct 92 ms 176660 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 175184 KB Output is correct
2 Correct 92 ms 174928 KB Output is correct
3 Correct 89 ms 174992 KB Output is correct
4 Correct 87 ms 174888 KB Output is correct
5 Correct 85 ms 174928 KB Output is correct
6 Correct 85 ms 174972 KB Output is correct
7 Correct 87 ms 174928 KB Output is correct
8 Correct 91 ms 174932 KB Output is correct
9 Correct 94 ms 175424 KB Output is correct
10 Correct 99 ms 176724 KB Output is correct
11 Correct 93 ms 175440 KB Output is correct
12 Correct 95 ms 176716 KB Output is correct
13 Correct 89 ms 175188 KB Output is correct
14 Correct 92 ms 176660 KB Output is correct
15 Correct 93 ms 176468 KB Output is correct
16 Correct 92 ms 175236 KB Output is correct
17 Correct 104 ms 179796 KB Output is correct
18 Correct 103 ms 180492 KB Output is correct
19 Correct 111 ms 180052 KB Output is correct
20 Correct 110 ms 180052 KB Output is correct
21 Correct 104 ms 180048 KB Output is correct
22 Correct 118 ms 183632 KB Output is correct
23 Correct 92 ms 177256 KB Output is correct
24 Correct 114 ms 178812 KB Output is correct
25 Correct 95 ms 176584 KB Output is correct
26 Correct 97 ms 177236 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 175184 KB Output is correct
2 Correct 92 ms 174928 KB Output is correct
3 Correct 89 ms 174992 KB Output is correct
4 Correct 87 ms 174888 KB Output is correct
5 Correct 85 ms 174928 KB Output is correct
6 Correct 85 ms 174972 KB Output is correct
7 Correct 87 ms 174928 KB Output is correct
8 Correct 91 ms 174932 KB Output is correct
9 Correct 94 ms 175424 KB Output is correct
10 Correct 99 ms 176724 KB Output is correct
11 Correct 93 ms 175440 KB Output is correct
12 Correct 95 ms 176716 KB Output is correct
13 Correct 89 ms 175188 KB Output is correct
14 Correct 92 ms 176660 KB Output is correct
15 Correct 93 ms 176468 KB Output is correct
16 Correct 92 ms 175236 KB Output is correct
17 Correct 104 ms 179796 KB Output is correct
18 Correct 103 ms 180492 KB Output is correct
19 Correct 111 ms 180052 KB Output is correct
20 Correct 110 ms 180052 KB Output is correct
21 Correct 104 ms 180048 KB Output is correct
22 Correct 118 ms 183632 KB Output is correct
23 Correct 92 ms 177256 KB Output is correct
24 Correct 114 ms 178812 KB Output is correct
25 Correct 95 ms 176584 KB Output is correct
26 Correct 97 ms 177236 KB Output is correct
27 Correct 186 ms 316756 KB Output is correct
28 Correct 150 ms 198656 KB Output is correct
29 Correct 286 ms 339788 KB Output is correct
30 Correct 279 ms 339144 KB Output is correct
31 Correct 262 ms 339028 KB Output is correct
32 Correct 174 ms 205904 KB Output is correct
33 Correct 254 ms 339028 KB Output is correct
34 Correct 257 ms 339164 KB Output is correct
35 Correct 203 ms 325716 KB Output is correct
36 Correct 254 ms 341072 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 175084 KB Output is correct
2 Correct 120 ms 196944 KB Output is correct
3 Correct 151 ms 211532 KB Output is correct
4 Correct 142 ms 208328 KB Output is correct
5 Correct 188 ms 226632 KB Output is correct
6 Correct 193 ms 226612 KB Output is correct
7 Correct 179 ms 226664 KB Output is correct
8 Correct 183 ms 226756 KB Output is correct
9 Correct 234 ms 243132 KB Output is correct
10 Correct 171 ms 211880 KB Output is correct
11 Correct 237 ms 248892 KB Output is correct
12 Correct 85 ms 175088 KB Output is correct
13 Correct 98 ms 174932 KB Output is correct
14 Correct 84 ms 174936 KB Output is correct
15 Correct 85 ms 175128 KB Output is correct
16 Correct 85 ms 174928 KB Output is correct
17 Correct 91 ms 174932 KB Output is correct
18 Correct 89 ms 175020 KB Output is correct
19 Correct 87 ms 174932 KB Output is correct
20 Correct 124 ms 196948 KB Output is correct
21 Correct 127 ms 196808 KB Output is correct
22 Correct 222 ms 245872 KB Output is correct
23 Correct 301 ms 291376 KB Output is correct
24 Correct 303 ms 301652 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 181956 KB Output is correct
2 Correct 105 ms 182980 KB Output is correct
3 Correct 85 ms 174932 KB Output is correct
4 Correct 79 ms 175104 KB Output is correct
5 Correct 157 ms 195112 KB Output is correct
6 Correct 183 ms 197716 KB Output is correct
7 Correct 86 ms 174928 KB Output is correct
8 Correct 132 ms 185640 KB Output is correct
9 Correct 146 ms 188088 KB Output is correct
10 Correct 116 ms 181960 KB Output is correct
11 Correct 119 ms 183028 KB Output is correct
12 Correct 87 ms 174928 KB Output is correct
13 Correct 87 ms 174928 KB Output is correct
14 Correct 85 ms 174932 KB Output is correct
15 Correct 87 ms 174944 KB Output is correct
16 Correct 88 ms 174932 KB Output is correct
17 Correct 89 ms 174932 KB Output is correct
18 Correct 108 ms 181960 KB Output is correct
19 Correct 116 ms 182976 KB Output is correct
20 Correct 107 ms 181668 KB Output is correct
21 Correct 127 ms 181124 KB Output is correct
22 Correct 109 ms 181816 KB Output is correct
23 Correct 115 ms 182464 KB Output is correct
24 Correct 87 ms 175084 KB Output is correct
25 Correct 120 ms 196944 KB Output is correct
26 Correct 151 ms 211532 KB Output is correct
27 Correct 142 ms 208328 KB Output is correct
28 Correct 188 ms 226632 KB Output is correct
29 Correct 193 ms 226612 KB Output is correct
30 Correct 179 ms 226664 KB Output is correct
31 Correct 183 ms 226756 KB Output is correct
32 Correct 96 ms 175184 KB Output is correct
33 Correct 92 ms 174928 KB Output is correct
34 Correct 89 ms 174992 KB Output is correct
35 Correct 87 ms 174888 KB Output is correct
36 Correct 85 ms 174928 KB Output is correct
37 Correct 85 ms 174972 KB Output is correct
38 Correct 87 ms 174928 KB Output is correct
39 Correct 91 ms 174932 KB Output is correct
40 Correct 94 ms 175424 KB Output is correct
41 Correct 99 ms 176724 KB Output is correct
42 Correct 93 ms 175440 KB Output is correct
43 Correct 95 ms 176716 KB Output is correct
44 Correct 89 ms 175188 KB Output is correct
45 Correct 92 ms 176660 KB Output is correct
46 Correct 93 ms 176468 KB Output is correct
47 Correct 92 ms 175236 KB Output is correct
48 Correct 104 ms 179796 KB Output is correct
49 Correct 103 ms 180492 KB Output is correct
50 Correct 111 ms 180052 KB Output is correct
51 Correct 110 ms 180052 KB Output is correct
52 Correct 104 ms 180048 KB Output is correct
53 Correct 118 ms 183632 KB Output is correct
54 Correct 92 ms 177256 KB Output is correct
55 Correct 114 ms 178812 KB Output is correct
56 Correct 95 ms 176584 KB Output is correct
57 Correct 97 ms 177236 KB Output is correct
58 Correct 186 ms 316756 KB Output is correct
59 Correct 150 ms 198656 KB Output is correct
60 Correct 286 ms 339788 KB Output is correct
61 Correct 279 ms 339144 KB Output is correct
62 Correct 262 ms 339028 KB Output is correct
63 Correct 174 ms 205904 KB Output is correct
64 Correct 254 ms 339028 KB Output is correct
65 Correct 257 ms 339164 KB Output is correct
66 Correct 203 ms 325716 KB Output is correct
67 Correct 254 ms 341072 KB Output is correct
68 Correct 234 ms 243132 KB Output is correct
69 Correct 171 ms 211880 KB Output is correct
70 Correct 237 ms 248892 KB Output is correct
71 Correct 85 ms 175088 KB Output is correct
72 Correct 98 ms 174932 KB Output is correct
73 Correct 84 ms 174936 KB Output is correct
74 Correct 85 ms 175128 KB Output is correct
75 Correct 85 ms 174928 KB Output is correct
76 Correct 91 ms 174932 KB Output is correct
77 Correct 89 ms 175020 KB Output is correct
78 Correct 87 ms 174932 KB Output is correct
79 Correct 124 ms 196948 KB Output is correct
80 Correct 127 ms 196808 KB Output is correct
81 Correct 222 ms 245872 KB Output is correct
82 Correct 301 ms 291376 KB Output is correct
83 Correct 303 ms 301652 KB Output is correct
84 Runtime error 970 ms 2097152 KB Execution killed with signal 9
85 Halted 0 ms 0 KB -