Submission #644348

#	Time	Username	Problem	Language	Result	Execution time	Memory
644348		NintsiChkhaidze	Catfish Farm (IOI22_fish)	C++17	100 / 100	475 ms	132032 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
using namespace std;
 
const int N = 100005;
ll dp[N][5];
vector <ll> p[N],pref[N];
vector <pair<ll,ll> > prc[N],v[N],suff[N];
 
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
 
  for (int i = 0;i < m; i++){
    X[i]++,Y[i]++;
    v[X[i] + 1].pb({Y[i],0});
    v[X[i] - 1].pb({Y[i],0});
    v[X[i]].pb({Y[i],(ll)W[i]});
  }

  for (int j = 1; j <= n; j++){
  	v[j].pb({0,0LL}),v[j].pb({n,0LL});
  	sort(v[j].begin(),v[j].end());

    vector <pair<ll,ll>> vec; vec.clear();
    vec.pb(v[j][0]);
    for (int i = 1; i < v[j].size(); i++){
      if (v[j][i].f == vec.back().f) vec[vec.size() - 1].s += v[j][i].s;
      else vec.pb(v[j][i]);
    }
    
    v[j] = vec;
    p[j].pb(v[j][0].s);
    for (int i = 1; i < v[j].size(); i++)
      p[j].pb(v[j][i].s + p[j][i - 1]);
  }

  for (int j = 1; j <= n; j++){
    for (int i = 0; i < v[j].size(); i++){
      ll a = v[j][i].f,val2 =0,val=0,valp = 0,vals=0;
      int l,r;
      if (j > 1){
        l = 0,r = v[j - 1].size() - 1; 
        while (l <= r){
          int mid = (l+r)>>1;
          if (v[j - 1][mid].f <= a) {
            valp = pref[j - 1][mid];
            val2 = p[j - 1][mid];
            l = mid + 1;
          }
          else r = mid - 1;
        }
      }
      
      l=0,r=suff[j-1].size()-1,vals=0; 
      while (l<=r){
        int mid= (l+r)>>1;
        if (suff[j - 1][mid].f >= a) {
          vals = suff[j - 1][mid].s;
          l = mid + 1;
        } else r = mid - 1;
      }
      
      dp[a][0] = vals - p[j][i];
      dp[a][1] = valp + val2; 
      if (j < 3) continue;
      l = 0,r = prc[j - 2].size() - 1,val = 0;
      while (l<=r){
        int mid= (l+r)>>1;
        if (prc[j - 2][mid].f <= a) 
            val = prc[j - 2][mid].s,l=mid+1;
        else r = mid-1;
      }
      
      dp[a][1] = max(dp[a][1], val + val2);
    }

    if (j == n) break;
    ll ls = 0;
    for (int i=v[j].size() - 1;i >= 0; i--){
      ll a = v[j][i].f,val=0;
      int l =0,r = v[j + 1].size() - 1; 
      while (l<=r){
        int mid=(l+r)>>1;
        if (v[j + 1][mid].f <= a){
          val = p[j + 1][mid];
          l = mid + 1;
        }else r = mid - 1;
      }

      suff[j].pb({a,max(ls, max(dp[a][0],dp[a][1]) + val)});
      ls = max(ls, max(dp[a][0],dp[a][1]) + val);
    }
    
    ls = 0;
    for (int i=0;i<v[j].size();i++){
      ll a = v[j][i].f;
      pref[j].pb(max(ls,dp[a][1] - p[j][i]));
      ls= max(ls,dp[a][1] - p[j][i]);
    }
    
    ls=0;
    for (int i=0;i<v[j].size();i++){
      ll a = v[j][i].f;
      prc[j].pb({a,max(ls, max(dp[a][0],dp[a][1]))}); 
      ls = prc[j][i].s;
    }
    
  }
  
  ll ans = 0;
  for (int i=0;i<v[n].size();i++){
    int a = v[n][i].f;
    ans=max({ans,dp[a][0],dp[a][1]});
  }
      
  return ans;
}

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:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 1; i < v[j].size(); i++){
      |                     ~~^~~~~~~~~~~~~
fish.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 1; i < v[j].size(); i++)
      |                     ~~^~~~~~~~~~~~~
fish.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < v[j].size(); i++){
      |                     ~~^~~~~~~~~~~~~
fish.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i=0;i<v[j].size();i++){
      |                  ~^~~~~~~~~~~~
fish.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i=0;i<v[j].size();i++){
      |                  ~^~~~~~~~~~~~
fish.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i=0;i<v[n].size();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