Submission #1039154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039154		Marco_Escandon	Catfish Farm (IOI22_fish)	C++17	37 / 100	1097 ms	108264 KiB

fish

#include<bits/stdc++.h>
using namespace std;
#include "fish.h"
typedef long long ll;
#pragma optimize("O3")
#define x first
#define y second
vector<vector<pair<ll,ll>>>  cad;
vector<vector<ll>>  indice;
/// @brief costo en la columna i
/// @param i columna
/// @param j valor del puente
/// @return 
ll cost(ll i, ll j){
    ll a=-1,b=cad[i].size();
    while(abs(a-b)!=1){
        ll m=(a+b)/2;
        if(cad[i][m].x<=j) a=m;
        else b=m;
    }
    if(b==0) return 0;
    return cad[i][b-1].y;
}
/// @brief mayor k tal que indice[i][k] <= j
/// @param i columna 
/// @param j valor
/// @return posicion 
ll idx(ll i, ll j){
    ll a=-1,b=indice[i].size();
    while(abs(a-b)!=1){
        ll m=(a+b)/2;
        if(indice[i][m]<=j) a=m;
        else b=m;
    }
    return b-1;
}
long long max_weights(int n, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> w) {
    cad.resize(n+1); indice.resize(n+1);
    vector<vector<vector<ll>>>  dp(n+1);
    for(int i=0; i<X.size(); i++){
        cad[X[i]+1].push_back({Y[i]+1,w[i]});
        if(X[i]!=0)   indice[X[i]].push_back(Y[i]+1);
        if(X[i]+2<=n) indice[X[i]+2].push_back(Y[i]+1);
    }
    for(int i=0; i<cad.size(); i++)
    {
        indice[i].push_back(0);
        sort(cad[i].begin(),cad[i].end());
        sort(indice[i].begin(),indice[i].end());
        dp[i].assign(indice[i].size(),{0,0});
        for(int j=1; j<cad[i].size(); j++)
            cad[i][j].y+=cad[i][j-1].y;
    }
    vector<vector<vector<ll>>>  dpac=dp;
    ll bs=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<indice[i].size(); j++)
        {
            ll idxtemp=idx(i-1,indice[i][j]);
            ll costoij=cost(i,indice[i][j]);
            ll costoi_1j=cost(i-1,indice[i][j]);
            if(idxtemp+1<dpac[i-1].size()) dp[i][j][0]=max(dp[i][j][0],dpac[i-1][idxtemp+1][0]-costoij);
            
            for(int l=0; l<=idxtemp; l++)                                                      
                dp[i][j][1]=max(dp[i][j][1],(dp[i-1][l][1]-cost(i-1,indice[i-1][l]))+costoi_1j);
            if(i>=2)
            {

                for(int l=0; l<dp[i-2].size(); l++)
                {
                    dp[i][j][1]=max(dp[i][j][1],dpac[i-2][l][1]+cost(i-1,indice[i-2][l]));
                    dp[i][j][1]=max(dp[i][j][1],dpac[i-2][l][1]+costoi_1j);
                }
                    
            }

            dpac[i][j][0]=max(dp[i][j][0],dp[i][j][1]);
            if(i<n) dpac[i][j][0]+=cost(i+1,indice[i][j]);

            dpac[i][j][1]=max(dp[i][j][0],dp[i][j][1]);

            bs=max(bs,max(dp[i][j][0],dp[i][j][1]));// salvar la respuesta
        }
        for(int j=indice[i].size()-2; j>-1; j--)
            dpac[i][j][0]=max(dpac[i][j][0],dpac[i][j+1][0]);
    }
    return bs;
}

Compilation message (stderr)

fish.cpp:5: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    5 | #pragma optimize("O3")
      | 
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0; i<X.size(); i++){
      |                  ~^~~~~~~~~
fish.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0; i<cad.size(); i++)
      |                  ~^~~~~~~~~~~
fish.cpp:51: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]
   51 |         for(int j=1; j<cad[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~
fish.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j=0; j<indice[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~~~~
fish.cpp:63:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(idxtemp+1<dpac[i-1].size()) dp[i][j][0]=max(dp[i][j][0],dpac[i-1][idxtemp+1][0]-costoij);
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 for(int l=0; l<dp[i-2].size(); l++)
      |                              ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 14 / 14
• Subtask 8: 0 / 16