Submission #745579

#	Time	Username	Problem	Language	Result	Execution time	Memory
745579		doowey	Catfish Farm (IOI22_fish)	C++17	9 / 100	122 ms	30116 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
 
#define fi first
#define se second
#define mp make_pair
 
const int N = (int)1e5 + 10;
 
vector<int> cand[N];
vector<pii> fish[N];
vector<ll> fish_cum[N];
vector<pii> dp[N];
 
int fin_index(int id, int h){
    int ii = lower_bound(cand[id].begin(), cand[id].end(), h) - cand[id].begin();
    if(ii >= cand[id].size() || cand[id][ii] != h) return -1;
    else return ii;
}
 
void maxi(ll &u, ll v){
    u=max(u, v);
}
 
ll get_sum(int id, ll pre){
    int jj = lower_bound(fish[id].begin(), fish[id].end(), mp(pre + 1, -1ll)) - fish[id].begin();
    jj -- ;
    if(jj < 0) return 0ll;
    return fish_cum[id][jj];
}
 
ll F[N][2];
ll Q[N];
 
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for(auto &x : X){
        x ++ ;
    } // assume x is in range [1; n]
    for(int i = 0 ; i < m ; i ++ ){
        if(Y[i] > 0){
            cand[X[i]].push_back(Y[i] - 1);
        }
        fish[X[i]].push_back(mp(Y[i], W[i]));
        Q[X[i]] = W[i];
    }
    ll tot;
    for(int i = 0; i <= n; i ++ ){
        cand[i].push_back(n - 1);
        cand[i].push_back(-1);
        sort(cand[i].begin(), cand[i].end());
        dp[i].resize(cand[i].size(), mp(-(ll)1e16, -(ll)1e16));
        sort(fish[i].begin(), fish[i].end());
        for(auto x : fish[i]){
            tot = x.se;
            if(!fish_cum[i].empty()) tot += fish_cum[i].back();
            fish_cum[i].push_back(tot);
        }
 
    }
    dp[0][0] = mp(0ll,0ll);
    ll meow = 0ll;
    // .fi means increasing direction, .se means decreasing direction
    int las;
    ll val;
    int pp;
    ll take;
    ll current;
    for(int i = 1; i <= n; i ++){
        // ----------------- SAME HEIGHT HANDLING -----------
        for(int j = 0 ;j < cand[i].size(); j ++ ){
            las = fin_index(i - 1, cand[i][j]);
            if(las != -1){
                val = max(dp[i - 1][las].fi, dp[i - 1][las].se);
                maxi(dp[i][j].fi, val);
                maxi(dp[i][j].se, val);
            }
        }
 
        // DECREASING HEIGHT HANDLING
        pp = cand[i - 1].size() - 1;
        take = 0ll;
        for(int j = cand[i].size() - 1; j >= 0 ; j -- ){
            while(pp >= 0 && cand[i - 1][pp] > cand[i][j]){
                ll A = max(dp[i - 1][pp].fi, dp[i - 1][pp].se);
                ll B = get_sum(i, cand[i - 1][pp]);
                current = (ll)max(dp[i - 1][pp].fi, dp[i - 1][pp].se) + (ll)get_sum(i, cand[i - 1][pp]);
                maxi(take, current);
                pp -- ;
            }
            current = take - get_sum(i, cand[i][j]);
            maxi(dp[i][j].se, current);
        }
        // INCREASING HEIGHT HANDLING
 
        pp = 0; // transition from 0 is different
 
        take = -(ll)1e18;
        for(int j = 0; j < cand[i].size(); j ++ ){
            while(pp < cand[i - 1].size() && cand[i - 1][pp] <= cand[i][j]){
                maxi(take, dp[i - 1][pp].fi - get_sum(i - 1, cand[i - 1][pp]));
                pp ++ ;
            }
            current = take + get_sum(i - 1, cand[i][j]);
            maxi(dp[i][j].fi, current);
            maxi(dp[i][j].se, current);
 
         
        }
 
        // INCREASING HEIGHT IF PREV IS EMPTY
 
        pp = 0;
        take = 0ll;
        for(int j = 0 ; j < cand[i].size(); j ++ ){
            while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] <= cand[i][j]){
                maxi(take, dp[i - 2][pp].fi);
                maxi(take, dp[i - 2][pp].se);
                pp ++ ;
            }
            current = take + get_sum(i - 1, cand[i][j]);
            maxi(dp[i][j].fi, current);
            maxi(dp[i][j].se, current);
        }
        if(i >= 2){
            pp = cand[i - 2].size() - 1;
            take = 0ll;
            for(int j = cand[i].size() - 1; j >= 0 ; j --  ){
                while(pp >= 0 && cand[i - 2][pp] > cand[i][j]){
                    maxi(take, max(dp[i - 2][pp].fi, dp[i - 2][pp].se) + get_sum(i - 1, cand[i - 2][pp]));
                    pp -- ;
                }
                maxi(dp[i][j].fi, take);
                maxi(dp[i][j].se, take);
            }
        }
       for(int j = 0 ; j < cand[i].size(); j ++ ){
         	maxi(meow, dp[i][j].fi);
            maxi(meow, dp[i][j].se);
       }
        /*
        cout << i << ": ";
        for(int j = 0; j < cand[i].size(); j ++ ){
            cout << "(" << cand[i][j] << ": " << dp[i][j].fi << " : " << dp[i][j].se << ") ";
        }
        cout << "\n";
        */
    }
    for(int i = 2; i <= n; i ++ ){
        // i taken
        F[i][1] = max(Q[i - 1] + max(F[i - 2][0], F[i - 2][1]), F[i - 1][1]);
        F[i][0] = max(Q[i] + F[i - 1][1], F[i - 1][0]);
    }
    ll chomp = max(F[n][1], F[n][0]);
    //cout << meow << "/" << chomp << "\n";
    return chomp;
}

Compilation message (stderr)

fish.cpp: In function 'int fin_index(int, int)':
fish.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(ii >= cand[id].size() || cand[id][ii] != h) return -1;
      |        ~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int j = 0 ;j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:89:20: warning: unused variable 'A' [-Wunused-variable]
   89 |                 ll A = max(dp[i - 1][pp].fi, dp[i - 1][pp].se);
      |                    ^
fish.cpp:90:20: warning: unused variable 'B' [-Wunused-variable]
   90 |                 ll B = get_sum(i, cand[i - 1][pp]);
      |                    ^
fish.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0; j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:104:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while(pp < cand[i - 1].size() && cand[i - 1][pp] <= cand[i][j]){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int j = 0 ; j < cand[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:120:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] <= cand[i][j]){
      |                             ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |        for(int j = 0 ; j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~

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