Submission #627307

#TimeUsernameProblemLanguageResultExecution timeMemory
627307czhang2718Catfish Farm (IOI22_fish)C++17
100 / 100
210 ms59896 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define f first #define s second const int N=3e5+4; int n,m; vector<pair<int,int>> fish[N]; vector<ll> dp[N], dp1[N], inc[N]; long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { for(int i=0; i<m; i++){ fish[X[i]+1].push_back({Y[i], W[i]}); } for(int i=1; i<=n; i++){ fish[i].push_back({0, 0}); fish[i].push_back({n, 0}); sort(fish[i].begin(), fish[i].end()); int p=fish[i].size(); if(p>1 && fish[i][1].f==fish[i][0].f) fish[i].erase(fish[i].begin()); } int i=0; fish[i].push_back({0, 0}); dp[i].resize(2); dp1[i].resize(2); inc[i].resize(2); for(int i=1; i<=n; i++){ int p=fish[i].size(); dp[i].resize(p+1, -1e18); dp1[i].resize(p+1, -1e18); inc[i].resize(p+1, -1e18); ll sum=0; pair<int, ll> nxt={0,0}, prv={0,0}; for(int j=0; j<p; j++){ auto fi=fish[i][j]; int y=fi.f, w=fi.s; while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){ nxt.s+=fish[i+1][nxt.f].s; nxt.f++; } while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){ prv.s+=fish[i-1][prv.f].s; prv.f++; } int k=upper_bound(fish[i-1].begin(), fish[i-1].end(), make_pair(y, int(1e9)))-fish[i-1].begin(); dp[i][j]=max(dp1[i-1][k]-sum, prv.s+inc[i-1][k-1]); // cout << "inc " << prv.s+(fish[i-1][k-1].f?inc[i-1][k-1]:0) << "\n"; int k2; if(i>=2){ k2=upper_bound(fish[i-2].begin(), fish[i-2].end(), make_pair(y, int(1e9)))-fish[i-2].begin(); dp[i][j]=max({dp[i][j], dp1[i-2][k2], dp[i-2][k2-1]+prv.s}); } inc[i][j]=max( j?inc[i][j-1]:ll(-1e18), -sum + max(prv.s+inc[i-1][k-1], i>=2?max(dp1[i-2][k2], dp[i-2][k2-1]+prv.s):0)); sum+=w; // cout << "inc[" << i << "][" << j << "] " << inc[i][j] << "\n"; // cout << "dp[" << i << "][" << j << "] " << dp[i][j] << "\n"; dp1[i][j]=dp[i][j]+nxt.s; if(j) dp[i][j]=max(dp[i][j], dp[i][j-1]); } for(int j=p-1; j>=0; j--){ dp1[i][j]=max(dp1[i][j+1], dp1[i][j]); } } return dp1[n][0]; }

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:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
      |                   ~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
      |                   ~~~~~^~~~~~~~~~~~~~~~~
#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...