Submission #627356

#	Time	Username	Problem	Language	Result	Execution time	Memory
627356		ainta	Catfish Farm (IOI22_fish)	C++17	100 / 100	692 ms	122456 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
 
 
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned ll;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
#define N_ 101000

vc<pii>Z[N_];
vc<int>YY[N_], GG[N_];
vc<ll>D1[N_], D2[N_];

int n, m;
map<int,int>MM[N_];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  n=N,m=M;
  rep(i,M){
    Y[i]++;
    Z[X[i]].pb({Y[i],W[i]});
    MM[X[i]][Y[i]] = W[i];
  }
  rep(i,N){
    sort(all(Z[i]));
  }
  rep(i,N){
    rng(j,i-1,i+1){
      if(j<0||j>=N)continue;
      for(auto [y,w] : Z[j]){
        YY[i].pb(y);
      }
    }
    YY[i].pb(0);
    sort(all(YY[i]));
    YY[i].resize(unique(all(YY[i])) - YY[i].begin());
    D1[i].resize(si(YY[i]));
    D2[i].resize(si(YY[i]));
    rep(j,si(YY[i])){
      GG[i].pb(MM[i][YY[i][j]]);
    }
  }
  ll INF = 1e18;
  rng(i,1,N-1){
    ll s = 0;
    int pv = 0;
    ll Mx = -INF;
    ll pM = 0;
    rep(j,si(YY[i-1])){
      pM=max(pM, D1[i-1][j]);
      pM=max(pM, D2[i-1][j]);
    }
    rep(j,si(YY[i])){
      while(pv < si(YY[i-1]) && YY[i-1][pv] <= YY[i][j]){
        int y = YY[i-1][pv];
        int g = GG[i-1][pv];
        s += g;
        Mx=max(Mx, D1[i-1][pv]-s);
        pv++;
      }
      D1[i][j] = max({D1[i][j], Mx + s, pM});
    }
    Mx = -INF;
    pv = si(YY[i-1]) - 1;
    per(j,si(YY[i])){
      while(pv >= 0 && YY[i-1][pv] > YY[i][j]){
        int y = YY[i-1][pv];
        int g = MM[i][y];
        Mx=max(Mx, max(D1[i-1][pv], D2[i-1][pv])-s);
        pv--;
        s += g;
      }
      D2[i][j] = max({D2[i][j], Mx + s, pM});
    }
    //printf("%d\n",i);
    //rep(j,si(YY[i])){
      //printf("%lld %lld\n",D1[i][j],D2[i][j]);
    //}
  }
  ll ans=0;
  rep(i,si(YY[N-1])){
    ans=max({ans, D1[N-1][i], D2[N-1][i]});
  }
  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:78:13: warning: unused variable 'y' [-Wunused-variable]
   78 |         int y = YY[i-1][pv];
      |             ^

• 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