Submission #1072431

#TimeUsernameProblemLanguageResultExecution timeMemory
1072431vjudge1Catfish Farm (IOI22_fish)C++17
0 / 100
85 ms23980 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector <ll>; using ii = pair <ll, ll>; using vii = vector <ii>; using vi = vector <int>; const ll MAXN = 1E5+16, INF = ll(1E18)+16; ll dp[MAXN]; vii ccs[MAXN]; ll max_weights (int n, int m, vi vx, vi vy, vi vw) { for (ll i = 0; i < m; i++) ccs[vx[i]].push_back({ vy[i]+1, vw[i] }); for (ll x = 0; x < n; x++) { sort(ccs[x].begin(), ccs[x].end()); ccs[x].insert(ccs[x].begin(), ii{ -1, 0 }); // ps[x].push_back(0); ll acc = 0; for (auto &[y, w] : ccs[x]) { acc += w; w = acc; } } auto fget = [&](ll x, ll y) -> ll { // pier at column x up until y if (x < 0 || n <= x) return 0; return (upper_bound(ccs[x].begin(), ccs[x].end(), ii{ y, INF })-1)->second; }; ll ans = fget(1, n); // all second column for (ll y = 0; y <= n; y++) { ans = max(ans, fget(0, y) + fget(1, n) - fget(1, y)); } 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...