Submission #1057233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057233		noyancanturk	메기 농장 (IOI22_fish)	C++17	3 / 100	139 ms	42580 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});
  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});
    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);
    }
    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]=pref[0][i+1].second;
    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,0,inds[i-1][pp]));
        pp++;
      }
      dp[i][j]=max(dp[i][j],max1+p(i-1,0,inds[i][j])+p(i+1,0,inds[i][j]));
      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()){
        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,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:35: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]
   35 |     for(int j=0;j<size(pref[i]);j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:38: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]
   38 |     for(int j=1;j<size(pref[i]);j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0;i<size(dp[0]);i++){
      |               ~^~~~~~~~~~~~
fish.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int j=0;j<size(dp[i]);j++){
      |                 ~^~~~~~~~~~~~
fish.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |       while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
      |             ~~^~~~~~~~~~~~~~
fish.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i=0;i<size(dp[n-1]);i++){
      |               ~^~~~~~~~~~~~~~

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