Submission #829379

#	Time	Username	Problem	Language	Result	Execution time	Memory
829379		tolbi	Catfish Farm (IOI22_fish)	C++17	100 / 100	622 ms	95240 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<ll>> pref;
vector<vector<int>> ind;
vector<vector<int>> pos;
ll query(int x, int l, int r){
    if (pos[x].back()<l) return 0ll;
    if (pos[x][0]>r) return 0ll;
    if (l>r) return 0ll;
    auto itl = lower_bound(pos[x].begin(), pos[x].end(), l);
    auto itr = lower_bound(pos[x].begin(), pos[x].end(), r+1);
    itr--;
    ll hueh = 0;
    if (itl!=pos[x].begin()){
        itl--;
        hueh = pref[x][(itl-pos[x].begin())];
    }
    return pref[x][(itr-pos[x].begin())]-hueh;
}
int getup(int node){
    int xv = X[node];
    int yv = Y[node];
    return ind[xv][lower_bound(pos[xv].begin(), pos[xv].end(), yv+1)-pos[xv].begin()];
}
int getdown(int node){
    int xv = X[node];
    int yv = Y[node];
    return ind[xv][lower_bound(pos[xv].begin(), pos[xv].end(), yv)-pos[xv].begin()-1];
}
int getnextup(int node){
    int xv = X[node];
    int yv = Y[node];
    return ind[xv+1][lower_bound(pos[xv+1].begin(), pos[xv+1].end(), yv)-pos[xv+1].begin()];
}
int getnextdown(int node){
    int xv = X[node];
    int yv = Y[node];
    return ind[xv+1][lower_bound(pos[xv+1].begin(), pos[xv+1].end(), yv+1)-pos[xv+1].begin()-1];
}
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) {
    vector<vector<pair<int,pair<ll,int>>>> arr;
    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}});
    }
    pref.resize(arr.size());
    pos.resize(arr.size());
    ind.resize(arr.size());
    for (int i = 0; i < N; ++i)
    {
        sort(arr[i].begin(), arr[i].end());
        pref[i].resize(arr[i].size());
        pos[i].resize(arr[i].size());
        ind[i].resize(arr[i].size());
        for (int j = 0; j < arr[i].size(); j++){
            pref[i][j]=arr[i][j].second.first;
            if (j) pref[i][j]+=pref[i][j-1];
            pos[i][j]=arr[i][j].first;
            ind[i][j]=arr[i][j].second.second;
        }
    }
    //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:150:5: warning: multi-line comment [-Wcomment]
  150 |     //2 increasing, \
      |     ^
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i = 0; i < _Y.size(); ++i)
      |                     ~~^~~~~~~~~~~
fish.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 0; i < Y.size(); i++){
      |                     ~~^~~~~~~~~~
fish.cpp:141:27: 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]
  141 |         for (int j = 0; j < arr[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