oj.uz

Submission #1022848

# Submission time Handle Problem Language Result Execution time Memory
1022848 2024-07-14T06:16:55 Z vjudge1 Catfish Farm (IOI22_fish) C++17
12 / 100
 167 ms 103836 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) {
    // 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});
        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){
        ll f=0,f1=0;
        for(int i=0;i<M;i++){
            if(X[i]%2)f+=W[i];
            else f+=W[i-1];
        }
        return max(f,f1);
    }
    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 31 ms 33892 KB Output is correct
2 Correct 34 ms 34500 KB Output is correct
3 Correct 13 ms 28508 KB Output is correct
4 Correct 14 ms 28544 KB Output is correct
5 Correct 79 ms 45784 KB Output is correct
6 Correct 94 ms 48720 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Incorrect 51 ms 37760 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80847304374467'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 56 ms 50464 KB Output is correct
3 Correct 80 ms 65356 KB Output is correct
4 Correct 72 ms 62156 KB Output is correct
5 Correct 111 ms 80976 KB Output is correct
6 Correct 116 ms 80244 KB Output is correct
7 Correct 112 ms 80980 KB Output is correct
8 Correct 110 ms 80840 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 13 ms 28532 KB Output is correct
4 Incorrect 17 ms 28508 KB 1st lines differ - on the 1st token, expected: '5050', found: '10100'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 13 ms 28532 KB Output is correct
4 Incorrect 17 ms 28508 KB 1st lines differ - on the 1st token, expected: '5050', found: '10100'
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28504 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 13 ms 28532 KB Output is correct
4 Incorrect 17 ms 28508 KB 1st lines differ - on the 1st token, expected: '5050', found: '10100'
5 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28508 KB Output is correct
2 Correct 56 ms 50464 KB Output is correct
3 Correct 80 ms 65356 KB Output is correct
4 Correct 72 ms 62156 KB Output is correct
5 Correct 111 ms 80976 KB Output is correct
6 Correct 116 ms 80244 KB Output is correct
7 Correct 112 ms 80980 KB Output is correct
8 Correct 110 ms 80840 KB Output is correct
9 Correct 131 ms 94760 KB Output is correct
10 Correct 93 ms 66132 KB Output is correct
11 Correct 167 ms 103836 KB Output is correct
12 Correct 16 ms 28508 KB Output is correct
13 Incorrect 18 ms 28508 KB 1st lines differ - on the 1st token, expected: '5050', found: '10100'
14 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33892 KB Output is correct
2 Correct 34 ms 34500 KB Output is correct
3 Correct 13 ms 28508 KB Output is correct
4 Correct 14 ms 28544 KB Output is correct
5 Correct 79 ms 45784 KB Output is correct
6 Correct 94 ms 48720 KB Output is correct
7 Correct 14 ms 28508 KB Output is correct
8 Incorrect 51 ms 37760 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80847304374467'
9 Halted 0 ms 0 KB -