제출 #1067168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1067168		epicci23	메기 농장 (IOI22_fish)	C++17	100 / 100	759 ms	77512 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]+1;
    ar[i][1]=Y[i]+1;
    ar[i][2]=W[i];
  }
  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());
  }
   
  int64_t res[n+5];
  memset(res,0,sizeof(res));

  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++){
    //start
    for(int64_t j=0;j<sz(consider[i]);j++){
      dp[i][0][j]=max(dp[i][0][j],(i>=3 ? res[i-3] : 0)+get_sum(i-1,consider[i][j]));
      dp[i][1][j]=max(dp[i][1][j],(i>=3 ? res[i-3] : 0)
         +get_sum(i-1,consider[i][j])+get_sum(i+1,consider[i][j]));
    }

    // 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 0;
    };
    
    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 0;
      };

      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 0;
      };

      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;
    for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
      int64_t u=consider[i-1][j];
      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));
    }
   
    for(int64_t j=0;j<sz(consider[i]);j++){
      ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
      ans=max(ans,dp[i][1][j]);
    }
    res[i]=ans;
  }
  return max(res[n],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