Submission #1070930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070930		beaconmc	Catfish Farm (IOI22_fish)	C++17	100 / 100	960 ms	313052 KiB

fish

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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;


basic_string<ll> realheights[maxn];
 
unordered_map<ll, ll> weights;
 
basic_string<ll> p[maxn];
 
basic_string<array<ll,2>>  dp[maxn];
 
basic_string<ll> pref[maxn][2];
basic_string<ll> pref2[maxn][2];
basic_string<ll> suff[maxn][2];
 
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    weights.reserve(2097152);
    weights.max_load_factor(0.25);
    FOR(i,0,M){
        Y[i]++;
        weights[X[i]*(ll)100000000+Y[i]] = W[i];
 
        if (X[i] > 0) realheights[X[i]-1].push_back(Y[i]);
        realheights[X[i]].push_back(Y[i]);
        realheights[X[i]+1].push_back(Y[i]);
        realheights[X[i]+2].push_back(Y[i]);
    }
    FOR(i,0,maxn) realheights[i].push_back(0);
    FOR(i,0,maxn) realheights[i].push_back(maxn);

    FOR(i,0,maxn){
        sort(realheights[i].begin(), realheights[i].end());
        auto it = unique(realheights[i].begin(), realheights[i].end());
        realheights[i].resize(it-realheights[i].begin());
        sort(realheights[i].begin(), realheights[i].end());
    }
 
    FOR(i,0,maxn){
        FOR(k,0,2){
            pref[i][k].resize(realheights[i].size());
            pref2[i][k].resize(realheights[i].size());
            suff[i][k].resize(realheights[i].size());
        }
        p[i].resize(realheights[i].size());
        dp[i].resize(realheights[i].size());
    }

 
 
 
    FOR(i,0,maxn){
        p[i][0] = 0;
        ll prev = 0;
        FOR(j,1,realheights[i].size()){
            p[i][j] = p[i][j-1] + weights[i*(ll)100000000+realheights[i][j]];
        }
    }
 
 
 
    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 down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
 
                    temp = max(temp, suff[i-1][0][down] - p[i-1][down]);
                    temp = max(temp, suff[i-1][1][down] - 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(), j) - realheights[i-1].begin() - 1;
                    ll down2 = upper_bound(realheights[i-2].begin(), realheights[i-2].end(), j) - realheights[i-2].begin() - 1;
 
 
                    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*(ll)100000000+realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[(i-1)*(ll)100000000+realheights[i][j]];
                pref[i][k][j] = dp[i][j][k] + tempadd2;
                pref2[i][k][j] = dp[i][j][k];
            }
            ll prev = 0;
            FOR(j,1,sz){
                pref[i][k][j] = max(pref[i][k][j], pref[i][k][j-1]);
                pref2[i][k][j] = max(pref2[i][k][j], pref2[i][k][j-1]);
 
            }
 
            FORNEG(j,sz-2,-1){
                suff[i][k][j] = max(suff[i][k][j], suff[i][k][j+1]);
 
 
            }
 
        }
        // cout << i << endl;
        // cout << suff[2][2][0] << "FUCK" << 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:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   68 |         FOR(j,1,realheights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:68:9: note: in expansion of macro 'FOR'
   68 |         FOR(j,1,realheights[i].size()){
      |         ^~~
fish.cpp:67:12: warning: unused variable 'prev' [-Wunused-variable]
   67 |         ll prev = 0;
      |            ^~~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   77 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:77:9: note: in expansion of macro 'FOR'
   77 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:86:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:84:20: warning: unused variable 'add' [-Wunused-variable]
   84 |                 ll add = 0;
      |                    ^~~
fish.cpp:135:16: warning: unused variable 'prev' [-Wunused-variable]
  135 |             ll prev = 0;
      |                ^~~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  162 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:162:9: note: in expansion of macro 'FOR'
  162 |         FOR(j,0,dp[i].size()){
      |         ^~~

• 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