Submission #788575

#	Time	Username	Problem	Language	Result	Execution time	Memory
788575		mosiashvililuka	Catfish Farm (IOI22_fish)	C++17	100 / 100	258 ms	73724 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,X[300009],Y[300009],W[300009],DP0[300009],DP1[300009],best[300009],pas;
vector <pair <long long, long long> > dp0[300009],dp1[300009],pr[300009];
long long max_weights(int NN, int MM, std::vector<int> XX, std::vector<int> YY, std::vector<int> WW) {
    a=NN;b=MM;
    for(i=0; i<b; i++){
        XX[i]++;YY[i]++;
        X[i+1]=XX[i];Y[i+1]=YY[i];W[i+1]=WW[i];
    }

    for(i=1; i<=b; i++){
        //if(Y[i]!=1){
            dp0[X[i]].push_back({Y[i]-1,0});
            dp1[X[i]].push_back({Y[i]-1,0});
        //}
        pr[X[i]].push_back({Y[i],W[i]});
    }

    for(i=0; i<=a; i++){
        if(i!=0){
            dp0[i].push_back({a+4,0});
            dp1[i].push_back({a+4,0});
        }
        /*dp0[i].push_back({0,0});
        dp1[i].push_back({0,0});*/
        pr[i].push_back({0,0});
    }

    for(i=0; i<=a; i++){
        sort(dp0[i].begin(),dp0[i].end());
        sort(dp1[i].begin(),dp1[i].end());
        sort(pr[i].begin(),pr[i].end());
        for(j=1; j<pr[i].size(); j++){
            pr[i][j].second+=pr[i][j-1].second;
        }
    }
    //return max(pr[1].back().second,pr[2].back().second);

    for(i=1; i<=a; i++){
        //DP0[i-1] DP1[i-1] best[i-1]
        DP0[i-1]=-N;
        DP1[i-1]=-N;
        for(j=0; j<dp0[i-1].size(); j++){
            best[i-1]=max(best[i-1],dp0[i-1][j].second);
        }
        ii=0;
        for(j=0; j<dp0[i-1].size(); j++){
            while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i-1][j].first) ii++;
            DP0[i-1]=max(DP0[i-1],dp0[i-1][j].second+pr[i][ii].second);
        }
        ii=0;
        for(j=0; j<dp1[i-1].size(); j++){
            while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i-1][j].first) ii++;
            DP1[i-1]=max(DP1[i-1],dp1[i-1][j].second-pr[i-1][ii].second);
        }
        //dp1[i]
        ii=0;
        for(j=0; j<dp1[i].size(); j++){
            while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i][j].first) ii++;
            dp1[i][j].second=pr[i-1][ii].second+DP1[i-1];
            dp1[i][j].second=max(dp1[i][j].second,best[i-1]);
        }

        //dp0[i]
        ii=0;
        for(j=0; j<dp0[i].size(); j++){
            dp0[i][j].second=dp1[i][j].second;
            while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i][j].first) ii++;
            zx=-pr[i][ii].second+DP0[i-1];
            dp0[i][j].second=max(dp0[i][j].second,zx);
        }
    }


    /*for(i=1; i<=a; i++){
        cout<<i<<":\n";
        for(j=0; j<dp0[i].size(); j++){
            cout<<"dp0 "<<i<<" "<<j<<":  "<<dp0[i][j].first<<" "<<dp0[i][j].second<<"\n";
        }
        cout<<"\n";
        for(j=0; j<dp1[i].size(); j++){
            cout<<"dp1 "<<i<<" "<<j<<":  "<<dp1[i][j].first<<" "<<dp1[i][j].second<<"\n";
        }
        cout<<"----------------------------------------------------------\n";
    }*/

    for(i=1; i<=a; i++){
        for(j=0; j<dp0[i].size(); j++){
            pas=max(pas,dp0[i][j].second);
        }
        for(j=0; j<dp1[i].size(); j++){
            pas=max(pas,dp1[i][j].second);
        }
    }

    /*for(i=1; i<=a; i++){
        pas=max(pas,best[i]);
    }*/
    return pas;
}

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: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=1; j<pr[i].size(); j++){
      |                  ~^~~~~~~~~~~~~
fish.cpp:46: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]
   46 |         for(j=0; j<dp0[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:50: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]
   50 |         for(j=0; j<dp0[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:51:23: 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]
   51 |             while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i-1][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~
fish.cpp:55: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]
   55 |         for(j=0; j<dp1[i-1].size(); j++){
      |                  ~^~~~~~~~~~~~~~~~
fish.cpp:56:23: 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]
   56 |             while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i-1][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~~~
fish.cpp:61: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]
   61 |         for(j=0; j<dp1[i].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:62:23: 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]
   62 |             while(ii+1<pr[i-1].size()&&pr[i-1][ii+1].first<=dp1[i][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~~~
fish.cpp:69: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]
   69 |         for(j=0; j<dp0[i].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:71:23: 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]
   71 |             while(ii+1<pr[i].size()&&pr[i][ii+1].first<=dp0[i][j].first) ii++;
      |                   ~~~~^~~~~~~~~~~~~
fish.cpp:91: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]
   91 |         for(j=0; j<dp0[i].size(); j++){
      |                  ~^~~~~~~~~~~~~~
fish.cpp:94: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]
   94 |         for(j=0; j<dp1[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