Submission #625773

#	Time	Username	Problem	Language	Result	Execution time	Memory
625773		inwbear	Catfish Farm (IOI22_fish)	C++17	100 / 100	675 ms	100472 KiB

fish

//#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define imx INT_MAX
const long long MMX = (long long)(1e18);
typedef long long LL;
vector<pair<int,LL> > dw[100005],val[100005];
vector<pair<int,pair<int,int> > >up[100005];
vector<pair<LL,int> >lup[100005],ldw[100005],lze[100005];
vector<LL>rup[100005];
int c1,c2,si1,si2,c3,cr,crr;
LL ze[100005],rr,rrdw,rrup,ans;

long long max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
  for(int i=0;i<M;i++){
    up[X[i]+2].pb({Y[i]+1,{W[i],-1}});
    up[X[i]].pb({Y[i]+1,{W[i],1}});
    dw[X[i]].pb({Y[i]+1,W[i]});
    val[X[i]+1].pb({Y[i]+1,W[i]});
  }
  for(int i=1;i<=N;i++){
      sort(all(up[i]));
      sort(all(dw[i]));
      sort(all(val[i]));
  }
  lze[0].pb({0,0});
  for(int i=1;i<=N;i++){
    for(int j=0;j<dw[i].size();j++){
      ldw[i].pb({0,dw[i][j].F});
      if(j!=0)dw[i][j].S+=dw[i][j-1].S;
    }

    c1=lup[i-1].size()-1,c2=ldw[i-1].size()-1,c3=val[i].size()-1,rr=-1;
    rrdw=0;
    for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
    for(int j=ldw[i].size()-1;j>-1;j--){
      cr=ldw[i][j].S;
      if(c1!=-1){
        while(lup[i-1][c1].S>=cr){
          rr=max(rr,lup[i-1][c1].F);
          c1--;
          if(c1==-1)break;
        }
      }
      if(c2!=-1){
        while(ldw[i-1][c2].S>=cr){
          rr=max(rr,ldw[i-1][c2].F);
          c2--;
          if(c2==-1)break;
        }
      }
      if(c3!=-1){
        while(val[i][c3].F>cr){
          rrdw-=val[i][c3].S;
          c3--;
          if(c3==-1)break;
        }
      }
      if(rr==-1)continue;
      ldw[i][j].F=rr+dw[i][j].S-rrdw;
    }

    c1=0,c2=0,c3=0,rrup=0,rrdw=0,rr=-MMX;
    for(int j=0;j<up[i].size();j++){
      rrup+=up[i][j].S.F;
      if(j!=up[i].size()-1){
        if(up[i][j].F==up[i][j+1].F)continue;
      }
      cr=up[i][j].F;
      if(c1!=lup[i-1].size()){
        while(lup[i-1][c1].S<=cr){
          crr=lup[i-1][c1].S;
          if(c2!=val[i-1].size()){
            while(val[i-1][c2].F<=crr){
              rrdw-=val[i-1][c2].S;
              c2++;
              if(c2==val[i-1].size())break;
            }
          }
          if(c3!=val[i].size()){
            while(val[i][c3].F<=crr){
              rrdw-=val[i][c3].S;
              c3++;
              if(c3==val[i].size())break;
            }
          }
          //printf("// %lld",rrdw);
          rr=max(rr,lup[i-1][c1].F+rrdw);
          c1++;
          if(c1==lup[i-1].size())break;
        }
      }
      rup[i].pb(rrup);
      if(rr==-MMX){
        lup[i].pb({0,up[i][j].F});
        continue;
      }
      //printf("=/ %lld %lld",rrup,rr);
      lup[i].pb({rrup+rr,up[i][j].F});
    }

    c1=lze[i-1].size()-1,c2=val[i-1].size()-1,rrdw=0,rr=-1;
    for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
    for(int j=lup[i].size()-1;j>-1;j--){
      cr=lup[i][j].S;
      if(c1!=-1){
        while(lze[i-1][c1].S>=cr){
          rr=max(rr,lze[i-1][c1].F);
          c1--;
          if(c1==-1)break;
        }
      }
      if(c2!=-1){
        while(val[i-1][c2].F>cr){
          rrdw+=val[i-1][c2].S;
          c2--;
          if(c2==-1)break;
        }
      }
      if(rr==-1)continue;
      //printf("//%d %lld\n",lup[i][j].S,rr+rup[i][j]+rrdw);
      lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]+rrdw);
    }

    c1=0,c2=0,rr=-1,rrdw=0;
    for(int j=0;j<lup[i].size();j++){
      cr=lup[i][j].S;
      if(c1!=lze[i-1].size()){
        while(lze[i-1][c1].S<=cr){
          crr=lze[i-1][c1].S;
          if(c2!=val[i-1].size()){
            while(val[i-1][c2].F<=crr){
              rrdw-=val[i-1][c2].S;
              c2++;
              if(c2==val[i-1].size())break;
            }
          }
          rr=max(rr,lze[i-1][c1].F+rrdw);
          c1++;
          if(c1==lze[i-1].size())break;
        }
      }
      if(rr==-1)continue;
      lup[i][j].F=max(lup[i][j].F,rr+rup[i][j]);
    }
    ze[i]=ze[i-1];
    lze[i].pb({ze[i-1],0});
    si1=lup[i-1].size();
    si2=ldw[i-1].size();
    lup[i-1].pb({0,imx});
    ldw[i-1].pb({0,imx});
    for(c1=0,c2=0;c1<si1||c2<si2;){
      ze[i]=max(ze[i],lup[i-1][c1].F);
      ze[i]=max(ze[i],ldw[i-1][c2].F);
      if(lup[i-1][c1].S<ldw[i-1][c2].S){
        lze[i].pb(lup[i-1][c1]);
        c1++;
      }
      else if(lup[i-1][c1].S>ldw[i-1][c2].S){
        lze[i].pb(ldw[i-1][c2]);
        c2++;
      }
      else{
        lze[i].pb({max(lup[i-1][c1].F,ldw[i-1][c2].F),lup[i-1][c1].S});
        c1++,c2++;
      }
    }
    // printf("=%d=\n",i);
    // for(int j=0;j<lup[i].size();j++)printf("%lld %d\n",lup[i][j].F,lup[i][j].S);
    // for(int j=0;j<ldw[i].size();j++)printf("[%lld %d]\n",ldw[i][j].F,ldw[i][j].S);
    // for(int j=0;j<lze[i].size();j++)printf("{%lld %d}\n",lze[i][j].F,lze[i][j].S);
    for(int j=0;j<lup[i].size();j++)ans=max(ans,lup[i][j].F);
    for(int j=0;j<ldw[i].size();j++)ans=max(ans,ldw[i][j].F);
    for(int j=0;j<lze[i].size();j++)ans=max(ans,lze[i][j].F);
  }
  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: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<dw[i].size();j++){
      |                 ~^~~~~~~~~~~~~
fish.cpp:39: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]
   39 |     for(int j=0;j<val[i].size();j++)rrdw+=val[i][j].S;
      |                 ~^~~~~~~~~~~~~~
fish.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=0;j<up[i].size();j++){
      |                 ~^~~~~~~~~~~~~
fish.cpp:70:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |       if(j!=up[i].size()-1){
      |          ~^~~~~~~~~~~~~~~~
fish.cpp:74:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       if(c1!=lup[i-1].size()){
      |          ~~^~~~~~~~~~~~~~~~~
fish.cpp:77:16: 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]
   77 |           if(c2!=val[i-1].size()){
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:81:20: 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]
   81 |               if(c2==val[i-1].size())break;
      |                  ~~^~~~~~~~~~~~~~~~~
fish.cpp:84:16: 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]
   84 |           if(c3!=val[i].size()){
      |              ~~^~~~~~~~~~~~~~~
fish.cpp:88:20: 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]
   88 |               if(c3==val[i].size())break;
      |                  ~~^~~~~~~~~~~~~~~
fish.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |           if(c1==lup[i-1].size())break;
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:107: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]
  107 |     for(int j=0;j<val[i-1].size();j++)rrdw-=val[i-1][j].S;
      |                 ~^~~~~~~~~~~~~~~~
fish.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int j=0;j<lup[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp:132:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |       if(c1!=lze[i-1].size()){
      |          ~~^~~~~~~~~~~~~~~~~
fish.cpp:135:16: 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]
  135 |           if(c2!=val[i-1].size()){
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:139:20: 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]
  139 |               if(c2==val[i-1].size())break;
      |                  ~~^~~~~~~~~~~~~~~~~
fish.cpp:144:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |           if(c1==lze[i-1].size())break;
      |              ~~^~~~~~~~~~~~~~~~~
fish.cpp:176:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for(int j=0;j<lup[i].size();j++)ans=max(ans,lup[i][j].F);
      |                 ~^~~~~~~~~~~~~~
fish.cpp:177:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int j=0;j<ldw[i].size();j++)ans=max(ans,ldw[i][j].F);
      |                 ~^~~~~~~~~~~~~~
fish.cpp:178:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for(int j=0;j<lze[i].size();j++)ans=max(ans,lze[i][j].F);
      |                 ~^~~~~~~~~~~~~~

• 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