제출 #776629

#제출 시각아이디문제언어결과실행 시간메모리
776629mousebeaver메기 농장 (IOI22_fish)C++17
67 / 100
1052 ms34092 KiB
#define ll long long #define pll pair<ll, ll> #include "fish.h" #include <bits/stdc++.h> using namespace std; struct fish { ll height; ll weight; ll below; ll above; //Sums of weights in column ll bigPier; //No bigger pier in the previous column -> first one to be caught ll noPier; //No pier in this column -> first one to be caught ll smallPier; //Bigger pier in the previous column -> first one not below a pier }; bool operator < (fish a, fish b) { return (a.height < b.height); } ll transitionBig(vector<vector<fish>>& dp, ll i, ll preind, ll index) { //Return dp[i][index].bigPier based on dp[i-1][preind] if(dp[i][index].height < dp[i-1][preind].height) { //The given pier is not bigger! return 0; } ll sum = 0; //Sum of the fish that get catched additionally if(dp[i][index].height > dp[i-1][preind].height) { //The piers have different size //Search for the last caught fish ll left = preind; ll right = dp[i-1].size()-1; while(left < right) { ll mid = (left+right+1)/2; if(dp[i-1][mid].height < dp[i][index].height) { left = mid; } else { right = mid-1; } } sum = dp[i-1][left].below + dp[i-1][left].weight - dp[i-1][preind].below; } return max(dp[i-1][preind].bigPier, dp[i-1][preind].noPier) + sum; } ll transitionSmall(vector<vector<fish>>& dp, ll i, ll preind, ll index) { //Return dp[i][index].smallPier based on dp[i-1][preind] if(dp[i][index].height >= dp[i-1][preind].height) { //The given pier is not strictly smaller! return 0; } ll sum = 0; //Sum of the fish that get catched additionally //Search for the last caught fish ll left = index; ll right = dp[i].size()-1; while(left < right) { ll mid = (left+right+1)/2; if(dp[i][mid].height < dp[i-1][preind].height) { left = mid; } else { right = mid-1; } } sum = dp[i][left].below + dp[i][left].weight - dp[i][index].below; return max(dp[i-1][preind].bigPier, dp[i-1][preind].smallPier) + sum; } long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { bool sub1 = true; bool sub2 = true; bool sub3 = true; for(ll i = 0; i < M; i++) { if(X[i] % 2 == 1) { sub1 = false; } if(X[i] > 1) { sub2 = false; } if(Y[i] != 0) { sub3 = false; } } if(sub1) { ll sum = 0; for(int i : W) { sum += (ll) i; } return sum; } if(sub2) { vector<pll> left(0); vector<pll> right(0); //Height, weight ll lsum = 0; ll rsum = 0; for(ll i = 0; i < M; i++) { if(X[i] == 0) { left.push_back({Y[i], W[i]}); lsum += W[i]; } else { right.push_back({Y[i], W[i]}); rsum += W[i]; } } sort(left.begin(), left.end()); sort(right.begin(), right.end()); ll output = max(lsum, rsum); if(N > 2) { ll lindex = -1; ll rindex = -1; ll shadow = 0; ll roof = 0; for(ll i = 0; i < N; i++) { while(lindex+1 < (ll) left.size() && left[lindex+1].first <= i) { lindex++; shadow += left[lindex].second; } while(rindex+1 < (ll) right.size() && right[rindex+1].first <= i) { rindex++; roof += right[rindex].second; } output = max(output, shadow + rsum - roof); } } return output; } if(sub3) { vector<ll> w(N, 0); for(ll i = 0; i < M; i++) { w[X[i]] = W[i]; } vector<vector<ll>> dp(N, vector<ll> (3, 0)); //Pier, no pier + uncaught, no pier + caught for(ll i = 1; i < N; i++) { //Pier: dp[i][0] = dp[i-1][0]; dp[i][0] = max(dp[i][0], dp[i-1][1]+w[i-1]); dp[i][0] = max(dp[i][0], dp[i-1][2]); //no pier + uncaught: dp[i][1] = dp[i-1][1]; dp[i][1] = max(dp[i][1], dp[i-1][2]); //no pier + caught: dp[i][2] = dp[i-1][0]+w[i]; } return max(max(dp[N-1][0], dp[N-1][1]), dp[N-1][2]); } vector<vector<fish>> grid(N, vector<fish> (0)); for(ll i = 0; i < M; i++) { fish f; f.height = Y[i]; f.weight = W[i]; f.bigPier = 0; f.smallPier = 0; f.noPier = 0; grid[X[i]].push_back(f); } fish top, bottom; top.height = N; top.weight = 0; top.noPier = 0; top.bigPier = 0; top.smallPier = 0; bottom.height = -1; bottom.weight = 0; bottom.smallPier = 0; bottom.bigPier = 0; bottom.noPier = 0; for(ll i = 0; i < N; i++) { grid[i].push_back(top); grid[i].push_back(bottom); sort(grid[i].begin(), grid[i].end()); ll sum = 0; for(ll j = 0; j < (ll) grid[i].size(); j++) { grid[i][j].below = sum; sum += grid[i][j].weight; } sum = 0; for(ll j = grid[i].size()-1; j >= 0; j--) { grid[i][j].above = sum; sum += grid[i][j].weight; } } for(ll i = 0; i < (ll) grid[0].size(); i++) { grid[0][i].bigPier = 0; grid[0][i].smallPier = 0; grid[0][i].noPier = 0; } for(ll i = 1; i < N; i++) { //no pier: ll preind = 0; ll postind = 0; ll premax = 0; while(preind < (ll) grid[i-1].size()) { while(postind < (ll) grid[i].size() && grid[i-1][preind].height >= grid[i][postind].height) { grid[i][postind].noPier = max(grid[i-1][preind].bigPier, grid[i-1][preind].smallPier)+grid[i][postind].below; postind++; } premax = max(premax, grid[i-1][preind].noPier); preind++; } for(ll j = 0; j < (ll) grid[i].size(); j++) { grid[i][j].noPier = max(grid[i][j].noPier, premax); } //calculate DP[i][j]: for(ll j = 0; j < (ll) grid[i].size(); j++) { //bigPier grid[i][j].bigPier = 0; for(ll k = 0; k < (ll) grid[i-1].size(); k++) { grid[i][j].bigPier = max(grid[i][j].bigPier, transitionBig(grid, i, k, j)); } //smallPier grid[i][j].smallPier = 0; for(ll k = 0; k < (ll) grid[i-1].size(); k++) { grid[i][j].smallPier = max(grid[i][j].smallPier, transitionSmall(grid, i, k, j)); } } } ll output = 0; for(fish f : grid[N-1]) { ll val = max(max(f.noPier, f.bigPier), f.smallPier); output = max(output, val); } return output; }
#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...