Submission #645996

#	Time	Username	Problem	Language	Result	Execution time	Memory
645996		mosiashvililuka	Catfish Farm (IOI22_fish)	C++17	100 / 100	507 ms	87788 KiB

fish

#include<bits/stdc++.h>
#include "fish.h"
using namespace std;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,ANS;
vector <pair <long long, long long> > fish[100009],JM[100009];
vector <long long> v[100009],dp[100009],dp2[100009],jm[100009],f[100009];
long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW) {
    a=NN;M=MM;
    for(i=1; i<=M; i++){
        fish[XX[i-1]+1].push_back({YY[i-1]+1,WW[i-1]});
    }
    for(i=1; i<=a; i++){
        fish[i].push_back({0,0});
        sort(fish[i].begin(),fish[i].end());
    }
    for(i=1; i<=a; i++){
        v[i].push_back(0);
        for(j=0; j<fish[i-1].size(); j++){
            v[i].push_back(fish[i-1][j].first);
        }
        for(j=0; j<fish[i+1].size(); j++){
            v[i].push_back(fish[i+1][j].first);
        }
        sort(v[i].begin(),v[i].end());
        dp[i].resize(v[i].size());dp2[i].resize(v[i].size());
        jm[i].resize(v[i].size());f[i].resize(v[i].size());
        /*zx=0;
        for(j=0; j<v[i].size(); j++){
            zx+=v[i][j];
            jm[i][j]=zx;
        }*/

        JM[i].resize(fish[i].size());
        zx=0;
        for(j=0; j<JM[i].size(); j++){
            zx+=fish[i][j].second;
            JM[i][j]={fish[i][j].first,zx};
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(JM[i].begin(),JM[i].end(),make_pair(v[i][j]+1,0LL))-JM[i].begin();c--;
            if(c<0) continue;
            jm[i][j]=JM[i][c].second;
        }
    }
    /*for(i=1; i<=a; i++){
        cout<<i<<":\n";
        for(j=0; j<v[i].size(); j++){
            cout<<v[i][j]<<" "<<jm[i][j]<<"\n";
        }
    }*/
    for(i=2; i<=a; i++){
        zx=-N;
        for(j=0; j<v[i-1].size(); j++){
            zx=max(zx,dp[i-1][j]);
            f[i-1][j]=zx;
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
            dp2[i][j]=max(dp2[i][j],f[i-1][c]);
        }
        zx=-N;
        for(j=0; j<v[i-1].size(); j++){
            zx=max(zx,dp2[i-1][j]-jm[i-1][j]);
            f[i-1][j]=zx;
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
            d=lower_bound(JM[i-1].begin(),JM[i-1].end(),make_pair(v[i][j]+1,0LL))-JM[i-1].begin();d--;
            dp2[i][j]=max(dp2[i][j],f[i-1][c]+/*jm[i-1][c]*/JM[i-1][d].second);
        }
        zx=-N;e=v[i-1].size();
        for(j=e-1; j>=0; j--){
            zx=max(zx,max(dp[i-1][j],dp2[i-1][j]));
            f[i-1][j]=zx;
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();
            if(c>=v[i-1].size()) continue;
            dp2[i][j]=max(dp2[i][j],f[i-1][c]);
        }
        //
        //
        zx=-N;
        for(j=0; j<v[i-1].size(); j++){
            zx=max(zx,dp[i-1][j]);
            f[i-1][j]=zx;
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
            dp2[i][j]=max(dp2[i][j],f[i-1][c]);
        }
        zx=-N;
        for(j=0; j<v[i-1].size(); j++){
            zx=max(zx,dp2[i-1][j]-jm[i-1][j]);
            f[i-1][j]=zx;
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();c--;
            d=lower_bound(JM[i-1].begin(),JM[i-1].end(),make_pair(v[i][j]+1,0LL))-JM[i-1].begin();d--;
            dp2[i][j]=max(dp2[i][j],f[i-1][c]+/*jm[i-1][c]*/JM[i-1][d].second);
        }
        zx=-N;e=v[i-1].size();
        for(j=e-1; j>=0; j--){
            /*c=lower_bound(v[i].begin(),v[i].end(),v[i-1][j]+1)-v[i].begin();c--;
            xc=jm[i][c];*/
            d=lower_bound(JM[i].begin(),JM[i].end(),make_pair(v[i-1][j]+1,0LL))-JM[i].begin();d--;
            xc=JM[i][d].second;
            zx=max(zx,max(dp[i-1][j],dp2[i-1][j])+xc);
            f[i-1][j]=zx;
        }
        for(j=0; j<v[i].size(); j++){
            c=lower_bound(v[i-1].begin(),v[i-1].end(),v[i][j]+1)-v[i-1].begin();
            if(c>=v[i-1].size()) continue;
            dp[i][j]=max(dp[i][j],f[i-1][c]-jm[i][j]);
        }
    }
    ANS=-N;
    for(i=1; i<=a; i++){
        for(j=0; j<dp[i].size(); j++){
            ANS=max(ANS,dp[i][j]);
            ANS=max(ANS,dp2[i][j]);
        }
    }
    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:19:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for(j=0; j<fish[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~~
fish.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(j=0; j<fish[i+1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~~
fish.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(j=0; j<JM[i].size(); j++){
      |                  ~^~~~~~~~~~~~~
fish.cpp:40:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:54:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(j=0; j<v[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:58:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(j=0; j<v[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:67:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:77:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:79:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             if(c>=v[i-1].size()) continue;
      |                ~^~~~~~~~~~~~~~~
fish.cpp:85:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(j=0; j<v[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:89:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:94:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(j=0; j<v[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:98:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:112:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(j=0; j<v[i].size(); j++){
      |                  ~^~~~~~~~~~~~
fish.cpp:114:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             if(c>=v[i-1].size()) continue;
      |                ~^~~~~~~~~~~~~~~
fish.cpp:120:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(j=0; j<dp[i].size(); j++){
      |                  ~^~~~~~~~~~~~~

• 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