Submission #1083809

#TimeUsernameProblemLanguageResultExecution timeMemory
1083809SamueleVidCatfish Farm (IOI22_fish)C++17
9 / 100
65 ms14424 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long constexpr int MAXN = 1e5 + 5; ll sum_tutto(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { ll sum = 0; for (auto x : W) sum += x; return sum; } ll res_minore_di_due(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { if (N == 2) { // massimo tra 0 e 1 ll one = 0; ll zero = 0; for (int i = 0; i < M; i ++) { if (X[i] == 0) zero += W[i]; else one += W[i]; } return max(one, zero); } // altrimenti piazza una riga in 2 e poi prendi prefisso maggiore piazzando in 1 ll sum = 0; for (int i = 0; i < M; i ++) { if (X[i] == 1) sum += W[i]; } // cout << "sum : " << sum << '\n'; vector<vector<ll>> pos(2, vector<ll>(N + 5, 0)); for (int i = 0; i < M; i ++) { pos[X[i]][Y[i]] += W[i]; } // for (int i = 0; i < N + 5; i ++) { // cout << pos[0][i] << " "; // } // cout << '\n'; // for (int i = 0; i < N + 5; i ++) { // cout << pos[1][i] << " "; // } // cout << '\n'; ll best_res = sum; ll sum_zero = 0; ll sum_uno = 0; for (int i = 0; i < N + 5; i ++) { sum_zero += pos[0][i]; sum_uno += pos[1][i]; best_res = max(best_res, sum - sum_uno + sum_zero); // cout << "per i : " << i << " avremmo " << sum - sum_uno + sum_zero << '\n'; } return best_res; } ll res_y_zero(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { vector<vector<ll>> dp(2, vector<ll>(N + 5)); // posso prendere a sx o no, posizione vector<int> grid(N + 5); for (int i = 0; i < M; i ++) grid[X[i]] = W[i]; for (int i = N - 1; i >= 0; i --) { dp[0][i] = dp[0][i + 1]; dp[0][i] = max(dp[0][i], dp[0][i + 2] + grid[i + 1]); dp[0][i] = max(dp[0][i], dp[1][i + 3] + grid[i + 1]); if (i == 0) continue; dp[1][i] = dp[0][i + 1] + grid[i - 1]; dp[1][i] = max(dp[1][i], grid[i - 1] + dp[0][i + 2] + grid[i + 1]); dp[1][i] = max(dp[1][i], grid[i - 1] + dp[1][i + 3] + grid[i + 1]); } return dp[0][0]; } ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { bool all_even = 1; for (auto x : X) if (x % 2) all_even = 0; if (all_even) return sum_tutto(N, M, X, Y, W); bool minore_di_due = 1; for (auto x : X) if (x >= 2) minore_di_due = 0; if (minore_di_due) return res_minore_di_due(N, M, X, Y, W); bool y_zero = 1; for (auto y : Y) if (y >= 0) minore_di_due = 0; return res_y_zero(N, M, X, Y, W); }

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:96:10: warning: unused variable 'y_zero' [-Wunused-variable]
   96 |     bool y_zero = 1;
      |          ^~~~~~
#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...