Submission #950845

#TimeUsernameProblemLanguageResultExecution timeMemory
950845sysiaCatfish Farm (IOI22_fish)C++17
100 / 100
355 ms47284 KiB
//Sylwia Sapkowska #include <bits/stdc++.h> #include "fish.h" #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif typedef long long ll; typedef pair<int, int> T; const ll oo = 1e18; void ckmax(ll &a, ll b){ a = max(a, b); } ll max_weights(int n, int m, vector<int>x, vector<int>y, vector<int>w){ vector<vector<T>>where(n+2); vector<vector<ll>>valid(n+1), pref(n+1); for (int i = 0; i<m; i++){ where[x[i]+1].emplace_back(y[i]+1, w[i]); } valid[0].emplace_back(0); where[0].emplace_back(0, 0); pref[0].emplace_back(0); for (int i = 1; i<=n; i++){ valid[i].emplace_back(0); for (auto [j, val]: where[i]) valid[i].emplace_back(j-1); for (auto [j, val]: where[i-1]) valid[i].emplace_back(j); for (auto [j, val]: where[i+1]) valid[i].emplace_back(j); sort(valid[i].begin(), valid[i].end()); where[i].emplace_back(0, 0); sort(where[i].begin(), where[i].end()); pref[i].resize((int)where[i].size()); for (int j = 1; j<(int)where[i].size(); j++) pref[i][j] = pref[i][j-1] + (ll)where[i][j].second; valid[i].erase(unique(valid[i].begin(), valid[i].end()), valid[i].end()); debug(i, where[i], pref[i], valid[i]); } vector dp(1, vector<ll>(3, -oo)); dp[0][0] = 0; dp[0][1] = 0; auto less = [&](int i, int h){//ostatni <= h w where[i] int l = 0, r = (int)where[i].size()-1; int ans = 0; while (r >= l){ int m = (l+r)/2; if (where[i][m].first <= h){ ans = m; l = m+1; } else r = m-1; } return ans; }; for (int i = 1; i<=n; i++){ int s = (int)valid[i].size(); int t = (int)valid[i-1].size(); vector new_dp(s, vector<ll>(3, -oo)); debug(i); //h = 0 //1) poprzednia miala dodatnie pole for (int j = 1; j<t; j++){ int h = valid[i-1][j]; ckmax(new_dp[0][2], max(dp[j][1], dp[j][0]) + pref[i][less(i, h)]); //<= h } //2) poprzednia byla zerem new_dp[0][0] = max(dp[0][2], dp[0][0]); //h > 0 //1) poprzednia byla pusta for (int j = 1; j<s; j++){ int h = valid[i][j]; new_dp[j][0] = new_dp[j][1] = max(dp[0][2], dp[0][0] + pref[i-1][less(i-1, h)]); } //2) poprzednia cos miala miau ll mx = -oo; int ptr = -1; for (int j = 1; j<s; j++){ int h = valid[i][j]; while (ptr + 1 < (int)valid[i-1].size() && valid[i-1][ptr+1] <= h){ ptr++; mx = max(mx, dp[ptr][0] - pref[i-1][less(i-1, valid[i-1][ptr])]); } int tt = less(i-1, h); ckmax(new_dp[j][0], mx+pref[i-1][tt]); ckmax(new_dp[j][1], mx+pref[i-1][tt]); } mx = -oo; ptr = t; for (int j = s-1; j>=1; j--){ int h = valid[i][j]; while (ptr >= 1 && valid[i-1][ptr-1] >= h){ ptr--; mx = max(mx, dp[ptr][1] + pref[i][less(i, valid[i-1][ptr])]); } ckmax(new_dp[j][1], mx-pref[i][less(i, h)]); } for (int j = 0; j<s; j++){ int h = valid[i][j]; debug(h, new_dp[j]); } swap(dp, new_dp); } debug(dp); ll ans = 0; for (int j = 0; j<(int)dp.size(); j++){ for (int rep = 0; rep < 3; rep++){ ans = max(ans, dp[j][rep]); } } return ans; }

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:115:17: warning: unused variable 'h' [-Wunused-variable]
  115 |             int h = valid[i][j];
      |                 ^
#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...