Submission #1070801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070801		beaconmc	Catfish Farm (IOI22_fish)	C++17	9 / 100	1067 ms	410104 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;
     
     
    set<ll> heights[maxn];
    vector<ll> realheights[maxn];
     
    unordered_map<ll,ll> fish[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,M){
            Y[i]++;
            fish[X[i]][Y[i]] = 1;
            weights[X[i]][Y[i]] = W[i];
     
            if (X[i] > 0) heights[X[i]-1].insert(Y[i]);
            heights[X[i]].insert(Y[i]);
            heights[X[i]+1].insert(Y[i]);
        }
        FOR(i,0,maxn) heights[i].insert(0);
     
        FOR(i,0,maxn) heights[i].insert(maxn);
     
        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:9:37: 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]
    9 |     #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   63 |             FOR(X,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:63:13: note: in expansion of macro 'FOR'
   63 |             FOR(X,0,dp[i].size()){
      |             ^~~
fish.cpp:72:30: 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]
   72 |                         if (X==dp[i].size()-1) continue;
      |                             ~^~~~~~~~~~~~~~~~
fish.cpp:70:24: warning: unused variable 'add' [-Wunused-variable]
   70 |                     ll add = 0;
      |                        ^~~
fish.cpp:64:20: warning: unused variable 'j' [-Wunused-variable]
   64 |                 ll j = realheights[i][X];
      |                    ^
fish.cpp:9:37: 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]
    9 |     #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  146 |             FOR(j,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:146:13: note: in expansion of macro 'FOR'
  146 |             FOR(j,0,dp[i].size()){
      |             ^~~

• 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