Submission #749588

#	Time	Username	Problem	Language	Result	Execution time	Memory
749588		farhan132	Catfish Farm (IOI22_fish)	C++17	100 / 100	903 ms	58956 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll,  ll, ll > tp;

#define ff first
#define ss second
#define pb push_back
#define in insert

const ll INF = (ll)1e18;

#define mem(a , b) memset(a, b ,sizeof(a))

const ll N = 1e5 + 5;

ll dp[2][2][2][N], pref[2][2][2][N], suf[2][2][2][N];
ll n;
vector < ii > v[N];
vector < ll > sum[N];

long long max_weights(int _n, int m, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
  n = _n;
  mem(dp, 0); mem(pref, 0);
  for(ll i = 0; i < m; i++){
    v[X[i]].pb({Y[i], 0});
    v[X[i]].pb({Y[i] + 1, W[i]});
  }
  for(ll i = 0; i < n; i++){
    v[i].pb({n, 0}); v[i].pb({0, 0});
    sort(v[i].begin(), v[i].end());
    vector < ii > f;
    for(ll j = 0; j < v[i].size(); j++){
        if(!f.size()){
            f.pb(v[i][j]);
        }else{
            if(f.back().ff == v[i][j].ff){
                f.pop_back();
            }
            f.pb(v[i][j]);
        }
    }
    v[i] = f;
    ll S = 0;
    for(ll j = 0; j < v[i].size(); j++){
        S += v[i][j].ss; sum[i].pb(S);
    }
  }
  auto get = [&](ll i, ll k){
    auto it = upper_bound(v[i].begin(), v[i].end(), make_pair(k+1, -INF)) - v[i].begin() - 1;
    if(it < 0) it = 0;
    return sum[i][it];
  };
  ll row = 0;

  ll ans = 0;

  for(ll i = 0; i < n; i++){
    row ^= 1; 
    // 0 -> i-1 > i, i > i+1
    // 1 -> i-1 < i, i < i+1

    // 0 -> sz[i-1] < sz[i], sz[i] < sz[i+1]
    // 1 -> sz[i-1] > sz[i], sz[i] > sz[i+1] 

    ll sz = v[i].size();

    for(ll j = 0; j <= sz; j++){
        for(ll c = 0; c < 2; c++)
            dp[row][c][0][j] = dp[row][c][1][j] = -INF; 
    }
    for(ll l = 0; l < 2; l++){
        for(ll d1 = 0; d1 < 2; d1++){
            for(ll r = 0; r < 2; r++){
                for(ll d2 = 0; d2 < 2; d2++){
                    if((!l && d1) && (r && !d2)) continue;
                    for(ll j = 0; j < sz; j++){
                        ll V = 0;
                        ll J = 0;
                        if(i > 0){
                            auto it = upper_bound(v[i-1].begin(), v[i-1].end(), make_pair(v[i][j].ff, -INF)) - v[i-1].begin();
                            if(it == v[i-1].size()) it--;
                            J = it;
                        }
                        if(l == 0 && d1){
                            V = suf[1-row][l][d1][J] - get(i, v[i][j].ff);
                        }else if(l == 0){
                            V = pref[1-row][l][d1][J-1];
                        }
                        if(l == 1 && !d1){
                            V = pref[1-row][l][d1][J-1] + (i > 0 ? get(i - 1, v[i][j].ff) : 0);
                        }else if(l == 1){
                            V = suf[1-row][l][d1][J];
                        }
                        if(r == 0 && d2 && i + 1 < n){
                            V += get(i + 1, v[i][j].ff);
                        }
                        if(r == 1 && !d2){
                            V -= get(i, v[i][j].ff);
                        }
                        dp[row][r][d2][j] = max(dp[row][r][d2][j], V);
                        ans = max(ans, V);
                    }
                }
            }
        }
    }
    // cout << i << ' ' << ans << '\n';
    for(ll c = 0; c < 2; c++){
        for(ll d = 0; d < 2; d++){
            suf[row][c][d][sz] = -INF;
            for(ll j = sz; j >= 0; j--){
                suf[row][c][d][j] = max(suf[row][c][d][j + 1], dp[row][c][d][j]);
            }
            for(ll j = 0; j < sz; j++){
                pref[row][c][d][j] = max(dp[row][c][d][j], (j > 0 ? pref[row][c][d][j - 1]: -INF));
            }
        }
    }
  }

  return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:39:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(ll j = 0; j < v[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~
fish.cpp:51:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(ll j = 0; j < v[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~
fish.cpp:88:35: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                             if(it == v[i-1].size()) it--;
      |                                ~~~^~~~~~~~~~~~~~~~

• 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