Submission #1238990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238990		AlperenT_	Catfish Farm (IOI22_fish)	C++20	100 / 100	197 ms	137632 KiB

fish

#include "fish.h"
#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const ll maxn = 6e5 + 10 , inf = 1e18+ 10 , mod = 998244353;
vector <int> vec[maxn]  ;
vector <ll> mx2[maxn] , pmx[maxn] , smx[maxn] , smx2[maxn]  ;
vector <pair<int,ll > >  sf[maxn] ;
ll dp[maxn][2] ; 
int n ;
long long max_weights(int N, int m, std::vector<int> X, std::vector<int> Y,std::vector<int> W){
    n = N ; 
    rep(i , 0, m-1){
        vec[X[i]].pb(Y[i]);
        sf[X[i]].pb({Y[i] , W[i]}); 
    }
    rep(i , 0 ,n-1){
        vec[i].pb(n) ;
        sf[i].pb({n ,0}) ;
    }
    rep(i , 0 ,n-1){
        sort(all(vec[i])) ;
        sort(all(sf[i])) ;
        per(j , sz(sf[i])-2 , 0){
            sf[i][j].S += sf[i][j+1].S; 
        }
    }
    int sm = 0 ;
    rep(i , 0 ,n-1){
        if(i!=0)
        rep(j , 0 ,sz(vec[i])-1){
            int id = sm + j; 
            int xx = lower_bound(all(vec[i-1]) , vec[i][j]) - vec[i-1].begin() ;
            int xx2 = lower_bound(all(vec[i-1]) , vec[i][j]+1) - vec[i-1].begin();
            ll mx ;
            if(xx2)mx = max(pmx[i-1][xx2-1] , -sf[i-1][xx].S + mx2[i-1][xx2-1]);
            else mx = -inf ;
            if(xx2 < sz(smx[i-1])){
                dp[id][0] = max(dp[id][0] , smx[i-1][xx2]);
                dp[id][1] = max(dp[id][1] , smx2[i-1][xx2] + sf[i][j].S) ;
            }
            rep(k2 , 0 ,sz(vec[i-1])-1){
                int k = sm - sz(vec[i-1]) + k2 ;
                if(vec[i-1][k2] <= vec[i][j]){
           //         mx = max({mx , dp[k][1]  , dp[k][0] + sf[i-1][k2].S -  sf[i-1][xx].S} );  
                }else{
                //    dp[id][0] = max(dp[id][0] , dp[k][1]) ;
                    int zz =lower_bound(all(vec[i]) , vec[i-1][k2]) - vec[i].begin() ;
               //     dp[id][1] = max(dp[id][1] , dp[k][1] + sf[i][j].S - sf[i][zz].S); 
                }
            }
            dp[id][0] = max(dp[id][0] , mx);
            dp[id][1] = max(dp[id][1] , mx) ;
        //    cout << i << " " << vec[i][j] << " : " << dp[id][0] << " " << dp[id][1] << "\n"; 
        }
        rep(j , 0 ,sz(vec[i])-1){
            mx2[i].pb(dp[sm+j][0] + sf[i][j].S) ;
            pmx[i].pb(dp[sm+j][1]);
            if(j!=0){
                mx2[i].back() = max(mx2[i].back() , mx2[i][sz(mx2[i])-2]) ;
                pmx[i].back() = max(pmx[i].back() , pmx[i][sz(pmx[i])-2]) ;
            }
        }
        if(i!=n-1){
            rep(j , 0 , sz(vec[i])-1){
                smx[i].pb(dp[sm+j][1]); 
                int zz =lower_bound(all(vec[i+1]) , vec[i][j]) - vec[i+1].begin() ;
                smx2[i].pb(dp[sm+j][1] - sf[i+1][zz].S) ;
            }
            per(j , sz(vec[i])-2 , 0){
                smx[i][j] = max(smx[i][j] , smx[i][j+1]) ;
                smx2[i][j] = max(smx2[i][j] , smx2[i][j+1]);
            }
        }
        sm += sz(vec[i]) ;
    }
    ll ans =0 ;
    rep(i , 0 , sm-1){
        ans = max({ans , dp[i][0] , dp[i][1]}) ;
    }
    return ans; 
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16