Submission #1057338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057338		noyancanturk	Catfish Farm (IOI22_fish)	C++17	100 / 100	143 ms	44080 KiB

fish

#include "fish.h"
  
#include<bits/stdc++.h>
using namespace std;
  
using lint=long long;
  
const int lim=1e5+100;
  
using pii=pair<int,lint>;
  
int n,m;
vector<int>inds[lim];
vector<lint> dp[lim],up[lim];
vector<pii>pref[lim];
lint p(int i,int r){
  if(n<=i)return 0;
  auto rp=lower_bound(pref[i].begin(),pref[i].end(),pii{r+1,0});
  rp--;
  return rp->second;
}
  
lint max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W) {
  n=N,m=M;
  for(int i=0;i<m;i++){
    pref[X[i]].push_back({Y[i]+1,W[i]});
  }
  for(int i=0;i<n;i++){
    pref[i].push_back({0,0});
    pref[i].push_back({n+6,0});
    sort(pref[i].begin(),pref[i].end());
    for(int j=0;j<size(pref[i]);j++){
      if(pref[i][j].first)inds[i].push_back(pref[i][j].first-1);
      else inds[i].push_back(0);
    }
    for(int j=1;j<size(pref[i]);j++){
      pref[i][j].second+=pref[i][j-1].second;
    }
  }
  dp[0].resize(inds[0].size());
  up[0].resize(inds[0].size());
  for(int i=0;i<size(dp[0]);i++){
    dp[0][i]=p(1,inds[0][i]);
    up[0][i]=0;
  }
  for(int i=1;i<n;i++){
    dp[i].resize(inds[i].size());
    up[i].resize(inds[i].size());
    lint max1=0;
    int pp=0;
    for(int j=0;j<size(dp[i]);j++){
      while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
        max1=max(max1,up[i-1][pp]-p(i-1,inds[i-1][pp]));
        pp++;
      }
      dp[i][j]=max(dp[i][j],max1+p(i-1,inds[i][j])+p(i+1,inds[i][j]));
      up[i][j]=max(up[i][j],max1+p(i-1,inds[i][j]));
      auto p=upper_bound(inds[i-1].begin(),inds[i-1].end(),inds[i][j]);
      if(p!=inds[i-1].begin()){
        p--;
        up[i][j]=max(up[i][j],dp[i-1][p-inds[i-1].begin()]);
      }
    }  
    max1=0;
    pp=size(up[i-1]);
    pp--; 
    for(int j=int(size(dp[i]))-1;0<=j;j--){
      while(0<=pp&&inds[i][j]<=inds[i-1][pp]){
        max1=max(max1,dp[i-1][pp]);
        pp--;
      }
      dp[i][j]=max(dp[i][j],max1-p(i,inds[i][j])+p(i+1,inds[i][j]));
    }
    /*
    cerr<<i<<" {\n";
    for(int j=0;j<dp[i].size();j++){
      cerr<<"  "<<inds[i][j]<<" :: "<<dp[i][j]<<"\n";
    }cerr<<"}{\n";
    for(int j=0;j<dp[i].size();j++){
      cerr<<"  "<<inds[i][j]<<" :: "<<up[i][j]<<"\n";
    }cerr<<"}\n";
    */
  }
  lint ans=0;
  for(int i=0;i<size(dp[n-1]);i++){
    ans=max(ans,dp[n-1][i]);
  }
  return ans;
}

Compilation message (stderr)

fish.cpp: In function 'lint max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int j=0;j<size(pref[i]);j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j=1;j<size(pref[i]);j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<size(dp[0]);i++){
      |               ~^~~~~~~~~~~~
fish.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int j=0;j<size(dp[i]);j++){
      |                 ~^~~~~~~~~~~~
fish.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
      |             ~~^~~~~~~~~~~~~~
fish.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i=0;i<size(dp[n-1]);i++){
      |               ~^~~~~~~~~~~~~~

• 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