Submission #1238980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238980		AlperenT_	Catfish Farm (IOI22_fish)	C++20	61 / 100	1098 ms	55840 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 int maxn = 6e5 + 10 , inf = 1e9+ 10 , mod = 998244353;
vector <int> vec[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 = sz(vec[0]) ;
    rep(i , 1 ,n-1){
        rep(j , 0 ,sz(vec[i])-1){
            int id = sm + j; ll mx =0  ; 
            int xx = lower_bound(all(vec[i-1]) , vec[i][j]) - vec[i-1].begin() ;
            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"; 
        }
        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: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16