oj.uz

Submission #1022847

# Submission time Handle Problem Language Result Execution time Memory
1022847 2024-07-14T06:16:26 Z vjudge1 Catfish Farm (IOI22_fish) C++17
12 / 100
 174 ms 104284 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){
        int 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 33 ms 33992 KB Output is correct
2 Correct 36 ms 34760 KB Output is correct
3 Correct 15 ms 28508 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 78 ms 47016 KB Output is correct
6 Correct 102 ms 50004 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 28504 KB Output is correct
2 Incorrect 49 ms 38364 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 45 ms 50452 KB Output is correct
3 Correct 77 ms 65364 KB Output is correct
4 Correct 71 ms 62372 KB Output is correct
5 Correct 112 ms 80976 KB Output is correct
6 Correct 109 ms 80208 KB Output is correct
7 Correct 110 ms 80832 KB Output is correct
8 Correct 113 ms 81036 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Incorrect 15 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 14 ms 28508 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Incorrect 15 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 14 ms 28508 KB Output is correct
2 Correct 13 ms 28508 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Incorrect 15 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 14 ms 28508 KB Output is correct
2 Correct 45 ms 50452 KB Output is correct
3 Correct 77 ms 65364 KB Output is correct
4 Correct 71 ms 62372 KB Output is correct
5 Correct 112 ms 80976 KB Output is correct
6 Correct 109 ms 80208 KB Output is correct
7 Correct 110 ms 80832 KB Output is correct
8 Correct 113 ms 81036 KB Output is correct
9 Correct 131 ms 94804 KB Output is correct
10 Correct 89 ms 66324 KB Output is correct
11 Correct 174 ms 104284 KB Output is correct
12 Correct 15 ms 28504 KB Output is correct
13 Incorrect 17 ms 28532 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 33 ms 33992 KB Output is correct
2 Correct 36 ms 34760 KB Output is correct
3 Correct 15 ms 28508 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 78 ms 47016 KB Output is correct
6 Correct 102 ms 50004 KB Output is correct
7 Correct 13 ms 28504 KB Output is correct
8 Incorrect 49 ms 38364 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '0'
9 Halted 0 ms 0 KB -