Submission #1023970

#TimeUsernameProblemLanguageResultExecution timeMemory
1023970OtalpCatfish Farm (IOI22_fish)C++17
100 / 100
739 ms249244 KiB
#include "fish.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define ll long long #define pii pair<int, int> #define ff first #define ss second const int MAXN = 500100; int n, w[MAXN], m; pii a[MAXN]; namespace B{ unordered_map<ll, ll> d[200100]; unordered_map<ll, ll> dp[200100]; unordered_map<ll, ll> pref[200100]; unordered_map<ll, ll> ddp[200100]; vector<ll> pos[200100]; ll suf[200100]; ll solve(){ for(ll i=1; i<=m; i++){ d[a[i].ff][a[i].ss] += w[i]; } for(int i=0; i<=n; i++){ d[i][0] += 0; d[i][n] += 0; } for(int i=0; i<=n; i++){ for(auto h: d[i]){ pos[i].pb(h.ff); } } for(ll i=1; i<=n; i++){ sort(pos[i].begin(), pos[i].end()); } for(ll i=1; i<=n; i++){ dp[0][i] = -1e18; ddp[0][i] = -1e18; } dp[0][0] = 0; ddp[0][0] = 0; for(ll i=1; i<=n; i++){ //cout<<"_____________________\n"; //cout<<i<<'\n'; vector<ll> alpos; for(auto h: pos[i-1]) alpos.pb(h); for(auto h: pos[i+1]) alpos.pb(h); sort(alpos.begin(), alpos.end()); int gls = 0; for(ll h: pos[i]){ ll j = h; pref[i][j] = pref[i][gls] + d[i][j]; gls = j; } vector<ll> dpos; for(auto h: dp[i-1]){ dpos.pb(h.ff); } sort(dpos.begin(), dpos.end()); ll mx = -1e18; ll ls = pos[i].size()-1; for(ll h = dpos.size()-1; h>=0; h--){ ll j = dpos[h]; while(ls > 0 and pos[i][ls] > j) ls--; mx = max(mx, dp[i-1][j] + pref[i][j]); suf[j] = mx; } ll pddp = -1e18, pdp = -1e18; mx = -1e18; for(ll h = dpos.size()-1; h>=0; h--){ ll j = dpos[h]; mx = max(mx, dp[i-1][j]); } ll pls=-1, dpls=-1; ls = -1; ll lls = -1; for(ll j: alpos){ //cout<<j<<' '; while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){ ls += 1; while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++; pdp = max(pdp, ddp[i-1][dpos[ls]]-pref[i-1][pos[i-1][lls]]); } while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++; while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++; ddp[i][j] = mx; dp[i][j] = 0; //if(dpls < 0){ // cout<<"asdas\n"; // cout<<j<<'\n'; // cout<<dpls+1<<'\n'; // continue; //} ddp[i][j] = max(ddp[i][j], pdp + pref[i-1][pos[i-1][dpls]]); dp[i][j] = ddp[i][j]; if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]); else dp[i][j] = max(dp[i][j], suf[dpos[ls]]-pref[i][pos[i][pls]]); dp[i][j] = max(dp[i][j], pdp+pref[i-1][pos[i-1][dpls]]); } //cout<<'\n'; } //for(ll i=1; i<=n; i++){ // for(ll j=0; j<=n; j++){ // cout<<pref[i][j]<<' '; // } // cout<<'\n'; //} ll ans = 0; for(ll i=0; i<=n; i++) ans = max(ans, dp[n][i]); return ans; } } long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { n = N; m = M; for(int i=1; i<=m; i++){ a[i] = {X[i-1]+1, Y[i-1]+1}; } for(int i=1; i<=m; i++){ w[i] = W[i-1]; } return B::solve(); }

Compilation message (stderr)

fish.cpp: In function 'long long int B::solve()':
fish.cpp:80:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 while(ls + 1 < dpos.size() and dpos[ls + 1] <= j){
      |                       ~~~~~~~^~~~~~~~~~~~~
fish.cpp:82:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                     while(lls + 1 < pos[i-1].size() and pos[i-1][lls + 1] <= dpos[ls]) lls++;
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:85:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 while(pls + 1 < pos[i].size() and pos[i][pls + 1] <= j) pls ++;
      |                       ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp:86:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                 while(dpls + 1 < pos[i-1].size() and pos[i-1][dpls + 1] <= j) dpls ++;
      |                       ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:97:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   97 |                 if(dpos.size() > ls + 1) dp[i][j] = max(dp[i][j], suf[dpos[ls + 1]]-pref[i][pos[i][pls]]);
      |                    ~~~~~~~~~~~~^~~~~~~~
fish.cpp:69:16: warning: unused variable 'pddp' [-Wunused-variable]
   69 |             ll pddp = -1e18, pdp = -1e18;
      |                ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...