Submission #1019907

#TimeUsernameProblemLanguageResultExecution timeMemory
1019907GrayCatfish Farm (IOI22_fish)C++17
100 / 100
142 ms36432 KiB
#include "fish.h" #include <algorithm> #include <cassert> #include <deque> #include <iostream> #include <vector> #define ll long long #define ff first #define ss second #define ln "\n" using namespace std; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { ll n=N, m=M; vector a(N, vector<pair<ll, ll>>()); vector dp(N, vector<pair<ll, ll>>()); for (ll i=0; i<m; i++){ a[X[i]].push_back({W[i], Y[i]}); dp[X[i]].push_back({0, 0}); } for (ll i=0; i<n; i++){ sort(a[i].begin(), a[i].end(), [](auto op1, auto op2)->bool{ return op1.ss<op2.ss;}); dp[i].push_back({0, 0}); } for (ll i=1; i<N; i++){ // cout << i << ": " << endl; deque<pair<ll, ll>> bestU; pair<ll, ll> mx = {-1, -1}; ll sum=0, rsum=0; for (ll j=0; j<(ll)a[i].size(); j++) rsum+=a[i][j].ff; sum=rsum; ll pi=a[i].size()-1; for (ll j=a[i-1].size(); j>=0; j--){ while (j<(ll)a[i-1].size() and pi>=0 and a[i-1][j].ss-1<a[i][pi].ss) sum-=a[i][pi--].ff; if (max(dp[i-1][j].ff, dp[i-1][j].ss)+sum>mx.ff){ mx = {max(dp[i-1][j].ff, dp[i-1][j].ss)+sum, (j==(ll)a[i-1].size())?n:a[i-1][j].ss-1}; bestU.push_back(mx); // cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl; } } sum=0; for (ll j=0; j<=(ll)a[i].size(); j++){ while (!bestU.empty() and bestU.back().ss<(j==(ll)a[i].size()?n:a[i][j].ss-1)) { // cout << "Remove: " << bestU.back().ff << " " << bestU.back().ss << " at " << j << endl; bestU.pop_back(); } // cout << i << "-" << j << endl; dp[i][j].ss=(bestU.empty()?0:bestU.back().ff)-sum; if (j<(ll)a[i].size()) sum+=a[i][j].ff; // cout << i << "-" << j << endl; } if (i>1){ //-Change- // cout << i << ": "; pair<ll, ll> best = {-1, -1}; for (ll j=0; j<=(ll)a[i-2].size(); j++){ best=max(best, {max(dp[i-2][j].ff, dp[i-2][j].ss), (j==(ll)(a[i-2].size())?n:a[i-2][j].ss-1)}); } ll osum=0; for (ll j=0; j<(ll)a[i-1].size() and a[i-1][j].ss<=best.ss; j++){ osum+=a[i-1][j].ff; } // cout << osum << " -> "; sum=0; pi=0; for (ll j=0; j<=(ll)a[i].size(); j++){ while (pi<(ll)a[i-1].size() and a[i-1][pi].ss<=(j==(ll)(a[i].size())?n:a[i][j].ss-1)) sum+=a[i-1][pi++].ff; dp[i][j].ff=best.ff+max(sum, osum); } } assert(bestU.size()<=1); while (!bestU.empty()) bestU.pop_back(); mx = {-1, -1}; sum=rsum=0; for (ll j=0; j<(ll)a[i-1].size(); j++) rsum+=a[i-1][j].ff; for (ll j=0; j<=(ll)a[i-1].size(); j++){ if (rsum-sum+dp[i-1][j].ff>mx.ff){ mx = {rsum-sum+dp[i-1][j].ff, (j==(ll)a[i-1].size()?n:a[i-1][j].ss-1)}; bestU.push_back(mx); // cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl; } if (j<(ll)a[i-1].size()) sum+=a[i-1][j].ff; } sum=0; pi=(ll)a[i-1].size()-1; for (ll j=(ll)(a[i].size()); j>=0; j--){ // cout << "Spec: " << a[i-1][pi].ss << " w " << (j==(ll)(a[i].size())?n+1:a[i][j].ss-1) << endl; while (pi>=0 and a[i-1][pi].ss>(j==(ll)(a[i].size())?n+1:a[i][j].ss-1)) {sum+=a[i-1][pi--].ff;} while (!bestU.empty() and bestU.back().ss>(j==(ll)(a[i].size())?n+1:a[i][j].ss-1)) { // cout << "Remove: " << bestU.back().ff << " " << bestU.back().ss << " at " << j << endl; bestU.pop_back(); } // cout << i << "-" << j << "-" << sum << endl; dp[i][j].ff=max(dp[i][j].ff, (bestU.empty()?0:bestU.back().ff)-sum); } } // for (ll i=0; i<n; i++){ // for (ll j=0; j<(ll)dp[i].size(); j++) cout << dp[i][j].ff << " "; // cout << ln; // } // for (ll i=0; i<n; i++){ // for (ll j=0; j<(ll)dp[i].size(); j++) cout << dp[i][j].ss << " "; // cout << ln; // } // Thing to lookup -> the fact that dp[i][j] is column up to height[i][j]-1; ll res=0; for (ll i=0; i<=(ll)a[n-1].size(); i++){ res=max(res, max(dp[n-1][i].ff,dp[n-1][i].ss)); } return res; }
#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...