Submission #1057074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057074		noyancanturk	Catfish Farm (IOI22_fish)	C++17	0 / 100	115 ms	39808 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 l,int r){
  if(n<=i)return 0;
  auto rp=lower_bound(pref[i].begin(),pref[i].end(),pii{r+1,0}),
        lp=lower_bound(pref[i].begin(),pref[i].end(),pii{l,0});
  /*
  cerr<<"my i is "<<i<<"\n";
  cerr<<(rp-pref[i].begin())<<" rp\n";
  cerr<<r<<" :: ";
  cerr<<rp->first<<" "<<rp->second<<"\n";
  */
  rp--;
  if(lp==pref[i].begin())return rp->second;
  lp--;
  return rp->second-lp->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});
    sort(pref[i].begin(),pref[i].end());
    for(int j=0;j<size(pref[i]);j++){
      inds[i].push_back(pref[i][j].first);
    }
    for(int j=1;j<size(pref[i]);j++){
      pref[i][j].second+=pref[i][j-1].second;
    }
    /*
    cerr<<"pref "<<i<<" {\n";
    for(auto[f,s]:pref[i]){
      cerr<<"\b"<<f<<" "<<s<<"\n";
    }cerr<<"}\n";
    */
  }
  dp[0].resize(pref[0].size());
  up[0].resize(pref[0].size());
  for(int i=0;i<size(dp[0]);i++){
    dp[0][i]=pref[0][i].second;
    up[0][i]=0;
  }
  for(int i=1;i<n;i++){
    dp[i].resize(pref[i].size());
    up[i].resize(pref[i].size());
    lint max1=0;
    int pp=0;
    for(int j=0;j<size(dp[i]);j++){
      /*
  cerr<<"ok\n";
  cerr<<j<<" "<<size(dp[i])<<"\n";
  cerr<<pp<<" "<<size(up[i-1])<<"\n";
      */
      while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
        max1=max(max1,up[i-1][pp]-p(i-1,0,inds[i-1][pp]));
        pp++;
      }
      /*
      cerr<<"bruh\n";
      cerr<<size(dp[i])<<" "<<size(up[i])<<" "<<size(inds[i])<<"\n";
      cerr<<j<<"\n";
      */
      dp[i][j]=max(dp[i][j],max1+p(i-1,0,inds[i][j])+p(i+1,0,inds[i][j]));
      //cerr<<"??\n";
      up[i][j]=max(up[i][j],max1+p(i-1,0,inds[i][j]));
      auto p=upper_bound(inds[i-1].begin(),inds[i-1].end(),inds[i][j]);
      if(p!=inds[i-1].begin()){
        //cerr<<"right here\n";
        p--;
        //cerr<<"it moved\n";
        up[i][j]=max(up[i][j],dp[i-1][p-inds[i-1].begin()]);
        //cerr<<"oops\n";
      }
      //cerr<<"ok i guess\n";
    }  
    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,0,inds[i][j])+p(i+1,0,inds[i][j]));
    }
  }
  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:40: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]
   40 |     for(int j=0;j<size(pref[i]);j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:43: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]
   43 |     for(int j=1;j<size(pref[i]);j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=0;i<size(dp[0]);i++){
      |               ~^~~~~~~~~~~~
fish.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int j=0;j<size(dp[i]);j++){
      |                 ~^~~~~~~~~~~~
fish.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |       while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
      |             ~~^~~~~~~~~~~~~~
fish.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i=0;i<size(dp[n-1]);i++){
      |               ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 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