Submission #745541

#	Time	Username	Problem	Language	Result	Execution time	Memory
745541		doowey	Catfish Farm (IOI22_fish)	C++17	0 / 100	145 ms	30624 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 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]));
    }
    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)1e18, -(ll)1e18));
        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].size() - 2;
        take = 0ll;
        for(int j = cand[i].size() - 1; j >= 0 ; j -- ){
            while(pp >= 0 && cand[i - 1][pp] > cand[i][j]){
                maxi(take, max(dp[i - 1][pp].fi, dp[i - 1][pp].se) + get_sum(i, cand[i - 1][pp]));
                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);

            maxi(meow, dp[i][j].fi);
            maxi(meow, dp[i][j].se);
        }

        // 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 ++ ){
            cout << "(" << cand[i][j] << ": " << dp[i][j].fi << "," << dp[i][j].se << ") ";
        }
        cout << "\n";
        */
    }
    return meow;
}

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:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0 ;j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j = 0; j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             while(pp < cand[i - 1].size() && cand[i - 1][pp] < cand[i][j]){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int j = 0 ; j < cand[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:114:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] < cand[i][j]){
      |                             ~~~^~~~~~~~~~~~~~~~~~~~

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