Submission #634741

#TimeUsernameProblemLanguageResultExecution timeMemory
634741l_rehoCatfish Farm (IOI22_fish)C++17
18 / 100
88 ms8136 KiB
#include "fish.h" #include <cassert> #include <cstdio> #include <vector> #include "fish.h" #include <cassert> #include <cstdio> // BEGIN SECRET #include <string> // END SECRET #include <vector> #include <bits/stdc++.h> using namespace std; vector<vector<int>> V; struct info{ int y; int w; int flag; }; struct CustomCompare { bool operator()(info const& p, info const& p1) { return (p.y > p1.y) || (p.y == p1.y && p.flag > p1.flag); } }; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){ // se X[i] è pari, allora posso ergere ponti per prendere tutti bool subtask1 = true; bool subtask2 = true; bool subtask3 = true; bool subtask4 = true; long long ans = 0; // for(int i = 0; i < (int)X.size(); i++) // V[X[i]][Y[i]] = W[i]; for(int i = 0; i < (int)X.size(); i++){ subtask1 &= X[i] % 2 == 0; subtask2 &= X[i] <= 1; subtask3 &= Y[i] == 0; subtask4 &= N <= 300; } if(subtask1){ ans = accumulate(W.begin(), W.end(), 0L); return ans; } if(subtask2){ if(N == 1) return 0; if(N == 2){ long long x0 = 0, x1 = 0; for(int i = 0; i < (int)X.size(); i++){ if(X[i] == 1) x1 += W[i]; else x0 += W[i]; } return max(x1, x0); } priority_queue<info, vector<info>, CustomCompare> pq; long long x1 = 0; for(int i = 0; i < (int)X.size(); i++){ pq.push({Y[i], W[i], X[i] == 0}); if(X[i] == 1) x1 += W[i]; } long long curr = x1; ans = curr; while(!pq.empty()){ info p = pq.top(); pq.pop(); if(p.flag) curr += p.w, ans = max(ans, curr); else curr -= p.w; } return ans; } if(subtask3){ long long dp[M][3]; for(int i = 0; i < M; i++) for(int j = 0; j < 3; j++) dp[i][j] = 0; vector<pair<int, int>> V; for(int i = 0; i < M; i++) V.push_back({X[i], W[i]}); sort(V.begin(), V.end()); dp[0][0] = V[0].second; if(V[0].first != 0) { dp[0][1] = V[0].second; } dp[0][2] = max(dp[0][1], dp[0][0]); for(int i = 1; i < M; i++){ if(abs(V[i].first-V[i-1].first) == 1){ if(V[i].first < N-1) dp[i][0] = dp[i-1][1]+V[i].second; if(i >= 2){ dp[i][1] = dp[i-2][2] + V[i].second; }else dp[i][1] = V[i].second; dp[i][2] = max(dp[i-1][2], max(dp[i][0], dp[i][1])); }else{ dp[i][1] = dp[i][2] = dp[i-1][2] + V[i].second; if(V[i].first < N-1) dp[i][0] = dp[i][1]; } } return dp[M-1][2]; } return ans; }
#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...