Submission #1040213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040213		vnm06	Catfish Farm (IOI22_fish)	C++17	100 / 100	298 ms	65872 KiB

fish

#include<bits/stdc++.h>
#include "fish.h"
#include <vector>

using namespace std;

int n, m;
vector<long long> sums[100005], height[100005];
vector<long long> dp[100005], dp2[100005], best_dp[100005];
vector<pair<int, int> > pos[100005];
long long bests[100005];
long long bests_osak[100005];

long long get_sum(int row, int k)
{
  if(row<0 || row>=n) return 0;
  if(sums[row].size()==0) return 0;
  int t=sums[row].size();
  if(pos[row][0].first>k) return 0;
  if(pos[row][t-1].first<=k) return sums[row][t-1];
  int le=0, ri=t;
  while(ri-le>1)
  {
    int mid=((le+ri)>>1);
    if(pos[row][mid-1].first<=k) le=mid;
    else ri=mid;
  }
  return sums[row][le-1];
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) 
{
  long long otg=0;
  n=N;
  m=M;
  for(int i=0; i<M; i++)
  {
    pos[X[i]].push_back({Y[i], W[i]});
  }
  for(int i=0; i<N; i++) 
  {
    sort(pos[i].begin(), pos[i].end());
    long long s=0;
    for(int j=0; j<pos[i].size(); j++)
    {
      s+=pos[i][j].second;
      sums[i].push_back(s);
    }
  }
  for(int i=0; i<N; i++)
  {
    if(i) for(int j=0; j<pos[i-1].size(); j++) height[i].push_back(pos[i-1][j].first);
    if(i<N-1) for(int j=0; j<pos[i+1].size(); j++) height[i].push_back(pos[i+1][j].first);
    sort(height[i].begin(), height[i].end());
    int id_l=-1;
    long long stv=0;
    if(i) {bests[i]=bests[i-1]; bests_osak[i]=bests_osak[i-1];}
    dp[i].resize(height[i].size());
    dp2[i].resize(height[i].size());
    for(int t=0; t<height[i].size(); t++)
    {
      long long ans=0, k=height[i][t], ans2=0;
      if(t && k==height[i][t-1]) continue;
      //ako ne se snizhava (mozhe i da e pyrvo)
      if(i>=3) ans=max(ans, bests[i-3]+get_sum(i-1, k)+get_sum(i+1, k));
      if(i>=2)
      {
        ans=max(ans, bests[i-2]+get_sum(i+1, k));
        ans=max(ans, bests_osak[i-2]+get_sum(i-1, k)+get_sum(i+1, k));
      }
      if(i)
      {
        while(id_l+1<height[i-1].size() && height[i-1][id_l+1]<=k) 
        {
          id_l++;
          stv=max(stv, dp[i-1][id_l]-get_sum(i, height[i-1][id_l])-get_sum(i-1, height[i-1][id_l]));
          /////cout<<id_l<<endl;
        }
      }
      ans=max(ans, stv+get_sum(i-1, k)+get_sum(i+1, k));
      dp[i][t]=ans;
      otg=max(otg, ans);
      bests[i]=max(bests[i], dp[i][t]);
      bests_osak[i]=max(bests_osak[i], dp[i][t]-get_sum(i+1, k));

      //cout<<t<<endl;
      if(i && id_l+1<best_dp[i-1].size()) ans2=best_dp[i-1][id_l+1]-get_sum(i, k)+get_sum(i+1, k);
      dp2[i][t]=ans2;
      otg=max(otg, ans2);
      bests[i]=max(bests[i], dp2[i][t]);
      bests_osak[i]=max(bests_osak[i], dp2[i][t]-get_sum(i+1, k));
    
      //cout<<i<<" "<<height[i][t]<<" "<<dp[i][t]<<" "<<dp2[i][t]<<endl;
      //ako trygne da se snizhava
    
    }
    for(int t=0; t<height[i].size(); t++)
    {
      best_dp[i].push_back(max(dp[i][t], dp2[i][t]));
    }
    for(int t=height[i].size()-2; t>=0; t--) best_dp[i][t]=max(best_dp[i][t], best_dp[i][t+1]);
  }
  return otg;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j=0; j<pos[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
fish.cpp:52:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if(i) for(int j=0; j<pos[i-1].size(); j++) height[i].push_back(pos[i-1][j].first);
      |                        ~^~~~~~~~~~~~~~~~
fish.cpp:53:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     if(i<N-1) for(int j=0; j<pos[i+1].size(); j++) height[i].push_back(pos[i+1][j].first);
      |                            ~^~~~~~~~~~~~~~~~
fish.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int t=0; t<height[i].size(); t++)
      |                  ~^~~~~~~~~~~~~~~~~
fish.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while(id_l+1<height[i-1].size() && height[i-1][id_l+1]<=k)
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       if(i && id_l+1<best_dp[i-1].size()) ans2=best_dp[i-1][id_l+1]-get_sum(i, k)+get_sum(i+1, k);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int t=0; t<height[i].size(); t++)
      |                  ~^~~~~~~~~~~~~~~~~

• 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