Submission #1067040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067040		epicci23	Catfish Farm (IOI22_fish)	C++17	9 / 100	450 ms	76748 KiB

fish

#include "bits/stdc++.h"
#include "fish.h"
//#define int64_t long long
#define all(v) v.begin() , v.end()
#define sz(a) (int64_t)a.size()
using namespace std;

const int64_t INF = 1e15;

long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
  int64_t n,m,ans=0;
  n=N,m=M;
  vector<array<int64_t,3>> ar(m);
  for(int64_t i=0;i<m;i++){
    ar[i][0]=X[i];
    ar[i][1]=Y[i];
    ar[i][2]=W[i];
    ar[i][0]++;
  }
  vector<int64_t> consider[n+5];
  vector<array<int64_t,2>> pre[n+5];
  vector<array<int64_t,2>> fish[n+5];

  for(int64_t i=0;i<m;i++){
    if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
    if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
  }

  for(int64_t i=0;i<=n;i++){
    consider[i].push_back(0);
    sort(all(consider[i]));
    consider[i].erase(unique(all(consider[i])),consider[i].end());
  }

  for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
  for(int64_t i=1;i<=n;i++){
    fish[i].push_back({0,0});
    sort(all(fish[i]));
    int64_t cur=0;
    for(auto x:fish[i]){
      cur+=x[1];
      pre[i].push_back({x[0],cur});
    }
  }

  vector<int64_t> dp[n+5][2];
  for(int64_t i=0;i<=n;i++){
    dp[i][0].assign(sz(consider[i]),0);
    dp[i][1].assign(sz(consider[i]),0);
  }

  auto get_sum=[&](int64_t i,int64_t j)->int64_t{
   if(i<1 || i>n) return 0;
   array<int64_t,2> bs={j+1,-1};
   int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
   if(it>0) return pre[i][it-1][1];
   return 0;
  };

  for(int64_t i=1;i<=n;i++){
    // calc increasing dp
    vector<array<int64_t,2>> v;
    int64_t cur=0;
    for(int64_t j=0;j<sz(dp[i-1][0]);j++){
      cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
      v.push_back({consider[i-1][j],cur});
    }

    auto get_val=[&](int64_t u,int64_t t)->int64_t{
      array<int64_t,2> bs={u+1,-1};
      int64_t it=lower_bound(all(v),bs)-v.begin();
      if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
      return -INF;
    };
    
    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      int64_t val=get_sum(i-1,u)+get_val(u,1);
      dp[i][0][j]=max(dp[i][0][j],val);
    }

    // calc decrasing dp

    v.clear();
    cur=0;
    for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
      cur=max(cur,dp[i-1][1][j]);
      v.push_back({consider[i-1][j],cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(dp[i][1]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
    }
    
    if(i>=2){ // new block
      vector<array<int64_t,2>> arka[2];
      cur=0;
      for(int64_t j=0;j<sz(consider[i-2]);j++){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]);
        cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
        arka[0].push_back({u,cur});
      }
      cur=0;
      for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
        cur=max(cur,dp[i-2][1][j]);
        arka[1].push_back({u,cur});
      }
      reverse(all(arka[1]));

      auto get_kucuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
        if(it>0) return arka[0][it-1][1];
        return -INF;
      };

      auto get_buyuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
        if(it<sz(arka[1])) return arka[1][it][1];
        return -INF;
      };

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
        dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
      }

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
        dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
      }
    }

    // inc to dec

    v.clear();
    cur=0;
    //cout << "kur: " << '\n';
    for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
      int64_t u=consider[i-1][j];
      //cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n';
      cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
      v.push_back({u,cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
      //cout << "hmm: " << i << ' ' << j << ' ' << u << '\n';
      //cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n';
      //cout << dp[i][1][j] << '\n';
    }
   
    for(int64_t j=0;j<sz(consider[i]);j++){
      //cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n';
      //cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n';
      ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
      ans=max(ans,dp[i][1][j]);
    }
  }
  return ans;
}


/*void _(){
  int64_t n,m,ans=0;
  cin >> n >> m;
  vector<array<int64_t,3>> ar(m);
  for(int64_t i=0;i<m;i++){
    cin >> ar[i][0] >> ar[i][1] >> ar[i][2];
    ar[i][0]++;
  }
  vector<int64_t> consider[n+5];
  vector<array<int64_t,2>> pre[n+5];
  vector<array<int64_t,2>> fish[n+5];

  for(int64_t i=0;i<m;i++){
    if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
    if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
  }

  for(int64_t i=0;i<=n;i++){
    consider[i].push_back(0);
    sort(all(consider[i]));
    consider[i].erase(unique(all(consider[i])),consider[i].end());
  }

  for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
  for(int64_t i=1;i<=n;i++){
    fish[i].push_back({0,0});
    sort(all(fish[i]));
    int64_t cur=0;
    for(auto x:fish[i]){
      cur+=x[1];
      pre[i].push_back({x[0],cur});
    }
  }

  vector<int64_t> dp[n+5][2];
  for(int64_t i=0;i<=n;i++){
    dp[i][0].assign(sz(consider[i]),0);
    dp[i][1].assign(sz(consider[i]),0);
  }

  auto get_sum=[&](int64_t i,int64_t j)->int64_t{
   if(i<1 || i>n) return 0;
   array<int64_t,2> bs={j+1,-1};
   int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
   if(it>0) return pre[i][it-1][1];
   return 0;
  };

  for(int64_t i=1;i<=n;i++){
    // calc increasing dp
    vector<array<int64_t,2>> v;
    int64_t cur=0;
    for(int64_t j=0;j<sz(dp[i-1][0]);j++){
      cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
      v.push_back({consider[i-1][j],cur});
    }

    auto get_val=[&](int64_t u,int64_t t)->int64_t{
      array<int64_t,2> bs={u+1,-1};
      int64_t it=lower_bound(all(v),bs)-v.begin();
      if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
      return -INF;
    };
    
    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      int64_t val=get_sum(i-1,u)+get_val(u,1);
      dp[i][0][j]=max(dp[i][0][j],val);
      //cout << "hm0: " << i << ' ' << j << ' ' << u << '\n';
      //cout << dp[i][0][j] << '\n';
    }

    // calc decrasing dp

    v.clear();
    cur=0;
    for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
      cur=max(cur,dp[i-1][1][j]);
      v.push_back({consider[i-1][j],cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(dp[i][1]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
      //cout << "hm1: " << i << ' ' << j << ' ' << u << '\n';
      //cout << dp[i][1][j] << '\n';
    }
    
    if(i>=2){ // new block
      vector<array<int64_t,2>> arka[2];
      cur=0;
      for(int64_t j=0;j<sz(consider[i-2]);j++){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]);
        cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
        arka[0].push_back({u,cur});
      }
      cur=0;
      for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
        int64_t u=consider[i-2][j];
        cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
        cur=max(cur,dp[i-2][1][j]);
        arka[1].push_back({u,cur});
      }
      reverse(all(arka[1]));

      auto get_kucuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
        if(it>0) return arka[0][it-1][1];
        return -INF;
      };

      auto get_buyuk=[&](int64_t u)->int64_t{
        array<int64_t,2> bs={u+1,-1};
        int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
        if(it<sz(arka[1])) return arka[1][it][1];
        return -INF;
      };

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
        dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
        //cout << "b0: " << i << ' ' << j << ' ' << u << '\n';
        //cout << dp[i][0][j] << '\n';
      }

      for(int64_t j=0;j<sz(consider[i]);j++){
        int64_t u=consider[i][j];
        dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
        dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
        //cout << "b1: " << i << ' ' << j << ' ' << u << '\n';
        //cout << dp[i][1][j] << '\n';
      }
    }

    // inc to dec

    v.clear();
    cur=0;
    //cout << "kur: " << '\n';
    for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
      int64_t u=consider[i-1][j];
      //cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n';
      cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
      v.push_back({u,cur});
    }
    reverse(all(v));

    for(int64_t j=0;j<sz(consider[i]);j++){
      int64_t u=consider[i][j];
      dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
      //cout << "hmm: " << i << ' ' << j << ' ' << u << '\n';
      //cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n';
      //cout << dp[i][1][j] << '\n';
    }
   
    for(int64_t j=0;j<sz(consider[i]);j++){
      //cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n';
      //cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n';
      ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
      ans=max(ans,dp[i][1][j]);
    }
  }
  cout << ans << '\n';
}

int64_t32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int64_t tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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