Submission #721332

#	Time	Username	Problem	Language	Result	Execution time	Memory
721332		Yell0	Catfish Farm (IOI22_fish)	C++17	100 / 100	273 ms	35716 KiB

fish

#include <bits/stdc++.h>
#define r first
#define w second
 
using namespace std;
typedef long long ll;
typedef pair<int,ll> pii;
const int MN=1e5+2;

ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
  vector<vector<pii>> fish(N+2);
  for(int i=0;i<M;++i) fish[X[i]+1].push_back({Y[i]+1,(ll)W[i]});

  fish[0].push_back({0,0LL});
  fish[N+1].push_back({0,0LL});
  for(int i=1;i<=N;++i) {
    fish[i].push_back({0,0LL});
    sort(fish[i].begin(),fish[i].end());
    for(int j=1;j<(int)fish[i].size();++j) fish[i][j].w+=fish[i][j-1].w;
  }

  auto pfx=[&](int c,int r) {
    return (--upper_bound(fish[c].begin(),fish[c].end(),pii(r,LLONG_MAX)))->w;
  };

  vector<vector<int>> stops(N+2);
  stops[0].push_back(0);
  stops[N+1].push_back(0);
  for(int i=1;i<=N;++i) {
    for(pii f:fish[i-1]) stops[i].push_back(f.r);
    for(pii f:fish[i+1]) stops[i].push_back(f.r);
    sort(stops[i].begin(),stops[i].end());
    stops[i].erase(unique(stops[i].begin(),stops[i].end()),stops[i].end());
  }

  vector<ll> dp[2];
  dp[0]={0LL};
  dp[1]={0LL};
  for(int i=1;i<=N+1;++i) {
    vector<ll> ndp[2];
    ll pf=0,sf=0;
    int pfi=0,sfi=(int)stops[i-1].size()-1;
    for(int s=0;s<(int)stops[i].size();++s) {
      while(pfi<(int)stops[i-1].size()&&stops[i-1][pfi]<=stops[i][s]) {
        pf=max(pf,dp[0][pfi]-pfx(i-1,stops[i-1][pfi]));
        ++pfi;
      }
      ndp[0].push_back(max(dp[1][0],pf+pfx(i-1,stops[i][s])));
    }
    for(int s=(int)stops[i].size()-1;s>=0;--s) {
      while(sfi>=0&&stops[i-1][sfi]>=stops[i][s]) {
        sf=max(sf,max(dp[0][sfi],dp[1][sfi])+pfx(i,stops[i-1][sfi]));
        --sfi;
      }
      ndp[1].push_back(sf-pfx(i,stops[i][s]));
    }
    reverse(ndp[1].begin(),ndp[1].end());
    dp[0].clear();
    dp[1].clear();
    for(ll x:ndp[0]) dp[0].push_back(x);
    for(ll x:ndp[1]) dp[1].push_back(x);
  }

  return max(dp[0][0],dp[1][0]);
}

• 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