Submission #1070807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070807		beaconmc	Catfish Farm (IOI22_fish)	C++17	35 / 100	1118 ms	1061636 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

const ll maxn = 100005;


set<ll> heights[maxn];
vector<ll> realheights[maxn];


unordered_map<ll,ll> weights[maxn];

unordered_map<ll,ll> p[maxn];

vector<array<ll,2>>  dp[maxn];

unordered_map<ll,ll> pref[maxn][2];
unordered_map<ll,ll> pref2[maxn][2];
unordered_map<ll,ll> suff[maxn][2];


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                  std::vector<int> W) {
FOR(i,0,maxn) weights[i].reserve(128);
FOR(i,0,M){
    Y[i]++;

    weights[X[i]][Y[i]] = W[i];

    if (X[i] > 0) heights[X[i]-1].insert(Y[i]);
    if (X[i] > 1) heights[X[i]-2].insert(Y[i]);
    heights[X[i]].insert(Y[i]);
    heights[X[i]+1].insert(Y[i]);
    heights[X[i]+2].insert(Y[i]);
}
FOR(i,0,maxn) heights[i].insert(0);

FOR(i,0,maxn) heights[i].insert(maxn);
//131072

FOR(i,0,maxn){
    p[i].reserve(128);
    FOR(k,0,2){
        pref[i][k].reserve(128);
        pref2[i][k].reserve(128);
        suff[i][k].reserve(128);
    }
}
FOR(i,0,maxn){

    p[i][0] = 0;
    ll prev = 0;
    for (auto j : heights[i]){
        if (j==0) continue;
        p[i][j] = p[i][prev] + weights[i][j];
        prev = j;
    }
}
FOR(i,0,maxn){
    for (auto k : heights[i]) realheights[i].push_back(k);
}
FOR(i,0,maxn){
    dp[i].resize(heights[i].size());
}

FOR(i,1,N+1){
    FOR(X,0,dp[i].size()){
        ll j = realheights[i][X];
        FOR(k,0,2){


            if (i<2) continue;
            ll temp = 0;
            ll add = 0;
            if (k==0){
                if (X==dp[i].size()-1) continue;
                ll up = *upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]);
                ll down = *(--upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]));
                temp = max(temp, suff[i-1][0][up] - p[i-1][down]);
                temp = max(temp, suff[i-1][1][up] - p[i-1][down]);

                // FOR(p,j+1,N+1){
                //     if (fish[i-1][p]) add += weights[i-1][p];
                //     temp = max(temp, dp[i-1][p][0] + add);
                //     temp = max(temp, dp[i-1][p][1] + add);
                // }
            }else{
                ll down = *(--upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]));
                ll down2 = *(--upper_bound(realheights[i-2].begin(), realheights[i-2].end(), realheights[i][X]));

                temp = max(temp, pref[i-1][0][down]);
                temp = max(temp, pref[i-1][1][down] + p[i-2][down2]);

                // FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
                // FOR(p,0,j+1){
                //     if (fish[i-2][p]) add -= weights[i-2][p];
                //     temp = max(temp, dp[i-1][p][0]);
                //     temp = max(temp, dp[i-1][p][1] + add);
                // }
            }


            dp[i][X][k] = temp;
        }
    }
    ll sz = realheights[i].size();

    FOR(k,0,2){
        ll tempadd = 0;
        ll tempadd2 = 0;


        FOR(j,0,sz){
            tempadd += weights[i][realheights[i][j]];
            suff[i][k][realheights[i][j]] = dp[i][j][k]+tempadd;
        }

        FOR(j,0,sz){
            tempadd2 -= weights[i-1][realheights[i][j]];
            pref[i][k][realheights[i][j]] = dp[i][j][k] + tempadd2;
            pref2[i][k][realheights[i][j]] = dp[i][j][k];
        }
        ll prev = 0;
        FOR(j,1,sz){
            pref[i][k][realheights[i][j]] = max(pref[i][k][realheights[i][j]], pref[i][k][prev]);
            pref2[i][k][realheights[i][j]] = max(pref2[i][k][realheights[i][j]], pref2[i][k][prev]);
            prev = realheights[i][j];
        }
        prev = realheights[i][sz-1];
        FORNEG(j,sz-2,-1){
            suff[i][k][realheights[i][j]] = max(suff[i][k][realheights[i][j]], suff[i][k][prev]);

            prev = realheights[i][j];
        }

    }
    // cout << i << endl;
    // cout << suff[2][2][0] << "FUCK" << endl;

}


// cout << dp[3][2][0] << endl;



ll ans = 0;

FOR(i,0,N+1){
    FOR(j,0,dp[i].size()){
        ans = max(dp[i][j][0], ans);
        ans = max(dp[i][j][1], ans);
    }
}
return ans;





}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   73 |     FOR(X,0,dp[i].size()){
      |         ~~~~~~~~~~~~~~~~         
fish.cpp:73:5: note: in expansion of macro 'FOR'
   73 |     FOR(X,0,dp[i].size()){
      |     ^~~
fish.cpp:82:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 if (X==dp[i].size()-1) continue;
      |                     ~^~~~~~~~~~~~~~~~
fish.cpp:80:16: warning: unused variable 'add' [-Wunused-variable]
   80 |             ll add = 0;
      |                ^~~
fish.cpp:74:12: warning: unused variable 'j' [-Wunused-variable]
   74 |         ll j = realheights[i][X];
      |            ^
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  156 |     FOR(j,0,dp[i].size()){
      |         ~~~~~~~~~~~~~~~~         
fish.cpp:156:5: note: in expansion of macro 'FOR'
  156 |     FOR(j,0,dp[i].size()){
      |     ^~~

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