Submission #1128517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128517		Ludissey	Catfish Farm (IOI22_fish)	C++17	100 / 100	180 ms	58424 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<int> dpHOLE; // 1 fois 0
vector<int> dpRESTART; // >2 fois 0
vector<vector<int>> dpUP; // en montant
vector<vector<int>> dpDOWN; // en montant
vector<vector<pair<int,int>>> fish;
vector<vector<pair<pair<int,int>,int>>> pos;
vector<int> pref;
int N,M;
 
long long max_weights(signed n, signed m, std::vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
  N=n; M=m; 
  fish.resize(n);
  pref.resize(n);
  pos.resize(n);
  dpUP.resize(n);
  dpDOWN.resize(n);
  dpRESTART.resize(n);
  dpHOLE.resize(n);
  for (int i = 0; i < m; i++)
  {
    fish[X[i]].push_back({Y[i],W[i]});
    pref[X[i]]+=W[i];
  }
  for (int i = 0; i < n; i++)
  {
    sort(all(fish[i]));
    for (int j = 0; j < sz(fish[i]); j++)
    {
      if(i>0) pos[i-1].push_back({{fish[i][j].first,fish[i][j].second},false});
      if(i<n-1) pos[i+1].push_back({{fish[i][j].first,fish[i][j].second},true});
    }
  }
  for (int i = 0; i < n; i++)
  {
    sort(all(pos[i]));
    dpUP[i].resize(sz(pos[i]),0);
    dpDOWN[i].resize(sz(pos[i]),0);
  }
  for (int i = 1; i < n; i++)
  {
    int mx=dpRESTART[i-1];
    dpRESTART[i]=max(dpRESTART[i-1],dpHOLE[i-1]);
    int mxD=0;
    if(sz(dpUP[i-1])>0) mxD=dpUP[i-1].back();
    int k=0;
    for (int j = 0; j < sz(pos[i]); j++)
    {
      while(k<sz(pos[i-1])&&pos[i][j].first.first>pos[i-1][k].first.first){
        mx=max(dpUP[i-1][k],mx);
        k++;
      }
      if(pos[i][j].second) mx+=pos[i][j].first.second;
      dpUP[i][j]=max(dpHOLE[i],mx);
    }

    k=sz(pos[i-1])-1;
    for (int j = sz(pos[i])-1; j >= 0; j--)
    {
      while(k>=0&&pos[i][j].first.first<pos[i-1][k].first.first){
        mxD=max(dpDOWN[i-1][k],mxD);
        if(!pos[i-1][k].second) mxD+=pos[i-1][k].first.second;
        k--;
      }
      dpDOWN[i][j]=max(mxD,dpHOLE[i-1]);
    }
    while(k>=0){
      mxD=max(dpDOWN[i-1][k],mxD);
      if(!pos[i-1][k].second) mxD+=pos[i-1][k].first.second;
      k--;
    }
    dpHOLE[i]=mxD;
  }
  int ret=0;
  if(sz(dpUP[n-1])>0) ret+=dpUP[n-1].back();
  ret=max(max(dpHOLE[n-1],ret),dpRESTART[n-1]);
  return ret;
}

• 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