Submission #1105837

#TimeUsernameProblemLanguageResultExecution timeMemory
1105837Zero_OPCatfish Farm (IOI22_fish)C++17
0 / 100
31 ms11168 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include <fish.h> #endif // LOCAL using namespace std; #define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i) #define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i) #define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i) #define all(v) begin(v), end(v) #define compact(v) v.erase(unique(all(v)), end(v)) #define sz(v) (int)v.size() #define dbg(x) "[" #x " = " << (x) << "]" template<typename T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } using ll = long long; using ld = long double; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); } template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); } const int MAX = 3e5 + 5; int n, m; struct fish{ int x, y, w; } fishes[MAX]; namespace subtask1{ bool check(){ rep(i, 0, m) if(fishes[i].x& 1) return false; return true; } ll solve(){ ll sum = 0; rep(i, 0, m){ if((i > 0) || (i < n - 1)){ sum += fishes[i].w; } } return sum; } } namespace subtask2{ bool check(){ for(int i = 0; i < m; ++i){ if(fishes[i].x > 1) return false; } return true; } ll sum[3][MAX]; ll f[3][MAX], g[3][MAX]; ll solve(){ memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); rep(i, 0, m){ sum[fishes[i].x][fishes[i].y] += fishes[i].w; } rep(i, 0, 2){ rep(j, 0, n){ sum[i][j] += (j > 0 ? sum[i][j - 1] : 0); } } ll ans = max(sum[0][n - 1], sum[1][n - 1]); if(n > 2){ rep(i, 0, n){ maximize(ans, sum[1][n - 1] - sum[1][i] + sum[0][i]); } } return ans; } } namespace subtask3{ bool check(){ rep(i, 0, m){ if(fishes[i].y > 0) return false; } return true; } ll dp[MAX], s[MAX]; ll solve(){ rep(i, 0, m) s[fishes[i].x] = fishes[i].w; dp[0] = 0; ll res = 0; rep(i, 1, n){ dp[i] = max(dp[i - 1], s[i - 1]); if(i >= 2) maximize(dp[i], dp[i - 2] + s[i - 1]); if(i >= 3) maximize(dp[i], dp[i - 3] + s[i - 2] + s[i - 1]); maximize(res, dp[i] + s[i + 1]); } return res; } } namespace subtask45{ bool check(){ return n <= 300; } ll pref[305][305]; ll solve(){ rep(i, 0, m){ pref[fishes[i].x + 1][fishes[i].y + 1] += fishes[i].w; } FOR(i, 1, n){ FOR(j, 1, n){ pref[i][j] += pref[i][j - 1]; } } const ll inf = 1e18; vector<vector<ll>> f(n + 1, vector<ll>(n + 1, -inf)); vector<vector<ll>> g(n + 1, vector<ll>(n + 1, -inf)); /* let f[c][r] = the maximum sum of weights if we put a pier (c, r) but we don't consider the fishes (c, r') with r' >= r g[c][r] = the maximum sum of weights if we put a pier (c, r) but we consider the fishes (c, r') with r' >= r let R[i] the height of pier on column c the we put consider when R[i - 1] < R[i] -> it contributes to f[c][r] consider when R[i - 1] > R[i] -> it contributes to g[c][r] when calculating f[c][r] : - consider R[i - 2] > R[i - 1] < R[i] - consider R[i - 2] < R[i - 1] < R[i] */ FOR(i, 0, n){ f[1][i] = g[1][i] = 0; } FOR(c, 2, n){ FOR(r, 0, n){ if(r == 0){ maximize(f[c][r], g[c - 1][r]); } FOR(k, 0, r){ maximize(f[c][r], f[c - 1][k] + pref[c - 1][r] - pref[c - 1][k]); // cout << dbg(c) << dbg(r) << dbg(f[c - 1][k] + pref[c - 1][r] + pref[c - 1][k]) << '\n'; } if(c > 2 && r > 0){ FOR(k, 0, n){ maximize(f[c][r], max(f[c - 2][r], g[c - 2][r]) + pref[c - 1][max(r, k)]); // cout << dbg(c) << dbg(r) << dbg(max(f[c - 2][r], g[c - 2][r]) + pref[c - 1][max(r, k)]) << '\n'; } } FOR(k, r, n){ maximize(g[c][r], max(f[c - 1][k], g[c - 1][k]) + pref[c][k] - pref[c][r]); // cout<< dbg(c) << dbg(r) << dbg(max(f[c - 1][k], g[c - 1][k]) + pref[c][k] - pref[c][r]) << '\n'; } } } ll ans = 0; FOR(c, 1, n){ FOR(r, 1, n){ maximize(ans, max(f[c][r], g[c][r]) + (c < n ? pref[c + 1][r] : 0)); } } // FOR(i, 1, n){ // FOR(j, 1, n){ // cout << pref[j][n - i + 1] << " \n"[j == n]; // } // } // cout << "F[r][c] : \n"; // FOR(i, 1, n){ // FOR(j, 1, n){ // cout << f[j][n - i + 1] << " \n"[j == n]; // } // } // // cout << '\n' << "G[r][c] : \n"; // FOR(i, 1, n){ // FOR(j, 1, n){ // cout << g[j][n - i + 1] << " \n"[j == n]; // } // } // cerr << "subtask 4, 5 : "; return ans; } } ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){ n = N; m = M; rep(i, 0, M) fishes[i] = {X[i], Y[i], W[i]}; // if(subtask1::check()) return subtask1::solve(); // if(subtask2::check()) return subtask2::solve(); // if(subtask3::check()) return subtask3::solve(); if(subtask45::check()) return subtask45::solve(); return -1; } #ifdef LOCAL int main(){ freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); int N, M; cin >> N >> M; vector<int> X(M), Y(M), W(M); rep(i, 0, M){ cin >> X[i] >> Y[i] >> W[i]; } cout << max_weights(N, M, X, Y, W) << '\n'; } #endif // LOCAL

Compilation message (stderr)

fish.cpp: In function 'bool minimize(T&, const T&)':
fish.cpp:18:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |     if(a > b) return a = b, true; return false;
      |     ^~
fish.cpp:18:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
fish.cpp: In function 'bool maximize(T&, const T&)':
fish.cpp:23:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |     if(a < b) return a = b, true; return false;
      |     ^~
fish.cpp:23:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
#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...