Submission #811226

#	Time	Username	Problem	Language	Result	Execution time	Memory
811226		blackyuki	Catfish Farm (IOI22_fish)	C++17	78 / 100	124 ms	37456 KiB

fish

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001;

ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
    vvp g(N+1);
    rep(i,M)g[X[i]+1].pb(Y[i]+1,W[i]);
    g[0].pb(0,0);
    rep(i,N+1)sort(all(g[i]));
    vi dp1(N+1,-inf),dp2(N+1,-inf);
    vvi dp3(N+1),dp4(N+1);
    rep(i,N+1)rep(j,g[i].size()){
        dp3[i].pb(-inf);dp4[i].pb(-inf);
    }
    dp1[0]=0;dp3[0][0]=0;
    REP(i,1,N+1){
        chmax(dp1[i],dp1[i-1]);chmax(dp2[i],dp2[i-1]);
        if(i<N)rep(j,g[i].size()){
            ll val=-inf;
            chmax(val,dp2[i-1]);
            if(i>1)chmax(val,dp1[i-2]);
            ll l=lb(g[i-1],P(g[i][j].fi,-1))-1;
            if(l>=0)chmax(val,dp3[i-1][l]);
            if(j>0)chmax(val,dp3[i][j-1]);
            val+=g[i][j].se;
            chmax(dp1[i],val);
            dp3[i][j]=val;
            if(j>0)chmax(dp3[i][j],dp3[i][j-1]);
        }
        for(int j=g[i].size()-1;j>=0;j--){
            ll val=-inf;
            if(i>1)chmax(val,dp1[i-2]);
            if(i>1)chmax(val,dp2[i-2]);
            ll l=lb(g[i-1],P(g[i][j].fi+1,-1));
            if(l<g[i-1].size())chmax(val,dp4[i-1][l]);
            if(j+1<g[i].size())chmax(val,dp4[i][j+1]);
            val+=g[i][j].se;
            chmax(dp2[i],val);
            dp4[i][j]=val;
            if(j+1<g[i].size())chmax(dp4[i][j],dp4[i][j+1]);
        }
    }
    return max(dp1[N],dp2[N]);
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:52:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             if(l<g[i-1].size())chmax(val,dp4[i-1][l]);
      |                ~^~~~~~~~~~~~~~
fish.cpp:53:19: 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]
   53 |             if(j+1<g[i].size())chmax(val,dp4[i][j+1]);
      |                ~~~^~~~~~~~~~~~
fish.cpp:57:19: 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]
   57 |             if(j+1<g[i].size())chmax(dp4[i][j],dp4[i][j+1]);
      |                ~~~^~~~~~~~~~~~

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