Submission #829342

#	Time	Username	Problem	Language	Result	Execution time	Memory
829342		tolbi	Catfish Farm (IOI22_fish)	C++17	58 / 100	1085 ms	53672 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
typedef long long ll;
#include "fish.h"
vector<vector<ll>> dp;
vector<int> X,Y;
int N,M;
vector<vector<pair<int,pair<ll,int>>>> arr;
ll query(int x, int l, int r){
    ll rval = 0;
    for (int i = 0; i < arr[x].size(); i++){
        if (arr[x][i].first>=l && arr[x][i].first<=r){
            rval+=arr[x][i].second.first;
        }
    }
    return rval;
}
int getup(int node){
    int xv = X[node];
    int yv = Y[node];
    for (int i = 0; i < arr[xv].size(); i++){
        if (arr[xv][i].first>yv){
            return arr[xv][i].second.second;
        }
    }
    assert(false);
    return 23;
}
int getdown(int node){
    int xv = X[node];
    int yv = Y[node];
    for (int i = arr[xv].size()-1; i >= 0; i--){
        if (arr[xv][i].first<yv){
            return arr[xv][i].second.second;
        }
    }
    assert(false);
    return 23;
}
int getnextup(int node){
    int xv = X[node];
    int yv = Y[node];
    for (int i = 0; i < arr[xv+1].size(); i++){
        if (arr[xv+1][i].first>=yv){
            return arr[xv+1][i].second.second;
        }
    }
    assert(false);
    return 23;
}
int getnextdown(int node){
    int xv = X[node];
    int yv = Y[node];
    for (int i = arr[xv+1].size()-1; i >= 0; i--){
        if (arr[xv+1][i].first<=yv){
            return arr[xv+1][i].second.second;
        }
    }
    assert(false);
    return 23;
}
long long f(int node, int flag){
    int x = X[node];
    int y = Y[node];
    //cout<<x<<" "<<y<<" "<<flag<<endl;
    if (dp[node][flag]!=-1) return dp[node][flag];
    if (flag==1){
        dp[node][flag]=0;
        if (y<N){
            ll crr = 0;
            int next = getup(node);
            if (x>0) crr = query(x-1,y,Y[next]-1);
            dp[node][flag]=crr+f(getup(node),1);
        }
        if (x+1<N){
            int next = getnextup(node);
            ll crr = query(x,y,Y[next]-1);
            dp[node][flag]=max(dp[node][flag],crr+f(next,1));
            next=getnextdown(node);
            crr = query(x+1,Y[next],y-1);
            dp[node][flag]=max(dp[node][flag],crr+f(next,0));
        }
    }
    else if (flag==0){
        dp[node][flag]=0;
        if (y-1>=0){
            int next = getdown(node);
            dp[node][flag]=query(x,Y[next],y-1)+f(next,0);
        }
        if (x+1<N){
            dp[node][flag]=max(dp[node][flag],f(getnextup(node),0));
            if (y==0){
                dp[node][flag]=max(dp[node][flag],f(M+x+1,2));
            }
        }
    }
    else {
        dp[node][flag]=0;
        if (y<N){
            dp[node][flag]=f(getup(node),2);
        }
        if (x+1<N){
            int next = getnextup(node);
            ll crr = query(x,y,Y[next]-1);
            dp[node][flag]=max(dp[node][flag],crr+f(next,1));
            next=getnextdown(node);
            crr = query(x+1,Y[next],y-1);
            dp[node][flag]=max(dp[node][flag],crr+f(next,0));
        }
    }
    if (flag!=0 && x+2<N){
        dp[node][flag]=max(dp[node][flag],f(M+x+2,1));
    }
    //cout<<x<<" "<<y<<" "<<flag<<" "<<dp[node][flag]<<endl;
    return dp[node][flag];
};

long long max_weights(int _N, int _M, std::vector<int> _X, std::vector<int> _Y, std::vector<int> _W) {
    N=_N;
    vector<int> W;
    arr.resize(N);
    vector<int> bb(N,0);
    for (int i = 0; i < _Y.size(); ++i)
    {
        if (_Y[i]==0) bb[_X[i]]=_W[i];
        else {
            X.push_back(_X[i]);
            Y.push_back(_Y[i]);
            W.push_back(_W[i]);
            M++;
        }
    }
    for (int i = 0; i < N; ++i)
    {
        X.push_back(i);
        Y.push_back(0);
        W.push_back(bb[i]);
    }
    for (int i = 0; i < N; i++){
        X.push_back(i);
        Y.push_back(N);
        W.push_back(0);
    }
    for (int i = 0; i < Y.size(); i++){
        arr[X[i]].push_back({Y[i],{W[i],i}});
    }
    for (int i = 0; i < N; ++i)
    {
        sort(arr[i].begin(), arr[i].end());
    }
    //0 decreasing
    //1 increasing
    //2 increasing, \
    but forbidden to profit from back
    //coutarr(X);
    //coutarr(Y);
    //coutarr(W);
    //cout<<M<<endl;
    dp.resize(Y.size(),vector<ll>(3,-1));
    return f(M,2);
}

Compilation message (stderr)

fish.cpp:154:5: warning: multi-line comment [-Wcomment]
  154 |     //2 increasing, \
      |     ^
fish.cpp: In function 'll query(int, int, int)':
fish.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < arr[x].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~
fish.cpp: In function 'int getup(int)':
fish.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < arr[xv].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~
fish.cpp: In function 'int getnextup(int)':
fish.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < arr[xv+1].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < _Y.size(); ++i)
      |                     ~~^~~~~~~~~~~
fish.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < Y.size(); i++){
      |                     ~~^~~~~~~~~~

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