Submission #1070931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070931		beaconmc	Catfish Farm (IOI22_fish)	C++17	100 / 100	877 ms	281560 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];
     
            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:37: 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++)
......
   67 |             FOR(j,1,realheights[i].size()){
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:67:13: note: in expansion of macro 'FOR'
   67 |             FOR(j,1,realheights[i].size()){
      |             ^~~
fish.cpp:66:16: warning: unused variable 'prev' [-Wunused-variable]
   66 |             ll prev = 0;
      |                ^~~~
fish.cpp:9:37: 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++)
......
   76 |             FOR(X,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:76:13: note: in expansion of macro 'FOR'
   76 |             FOR(X,0,dp[i].size()){
      |             ^~~
fish.cpp:85:30: 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]
   85 |                         if (X==dp[i].size()-1) continue;
      |                             ~^~~~~~~~~~~~~~~~
fish.cpp:83:24: warning: unused variable 'add' [-Wunused-variable]
   83 |                     ll add = 0;
      |                        ^~~
fish.cpp:134:20: warning: unused variable 'prev' [-Wunused-variable]
  134 |                 ll prev = 0;
      |                    ^~~~
fish.cpp:9:37: 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++)
......
  161 |             FOR(j,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:161:13: note: in expansion of macro 'FOR'
  161 |             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