Submission #625695

#TimeUsernameProblemLanguageResultExecution timeMemory
625695I_love_Hoang_YenCatfish Farm (IOI22_fish)C++17
70 / 100
729 ms2097152 KiB
#include "bits/stdc++.h" using namespace std; #define int long long #define i_1 jakcjacjl struct Fish { int col, row; int weight; }; bool operator < (const Fish& a, const Fish& b) { if (a.col != b.col) return a.col < b.col; return a.row < b.row; } void upMax(int& f, int val) { if (val > f) f = val; } // sub1 - 3 {{{ // fishes are on even columns -> build piers on odd columns // & catch all fishes int sub1(const std::vector<Fish>& fishes) { int res = 0; for (const auto& fish : fishes) { res += fish.weight; } return res; } // fishes are on first 2 columns int sub2(int n, const std::vector<Fish>& fishes) { std::vector<int> zeroes(n); // prefix sum of fish weights at column == 0 std::vector<int> ones(n); // prefix sum of fish weights at column == 1 for (const auto& fish : fishes) { if (fish.col == 0) zeroes[fish.row] += fish.weight; if (fish.col == 1) ones[fish.row] += fish.weight; } std::partial_sum(zeroes.begin(), zeroes.end(), zeroes.begin()); std::partial_sum(ones.begin(), ones.end(), ones.begin()); int res = ones.back(); // init: only catch fishes at column == 1 for (int i = 0; i < n; ++i) { // build pier until at column 1, row 0-i if (n == 2) upMax(res, zeroes[i]); else upMax(res, zeroes[i] + ones.back() - ones[i]); } return res; } // all fishes are on row == 0 int sub3(int n, const std::vector<Fish>& fishes) { std::vector<int> weights(n); // weights[i] = weight of fish at column i for (const auto& fish : fishes) { weights[fish.col] += fish.weight; } // f[i] = best strategy if we BUILD PIER AT i, only considering col 0..i // i-4 i-3 i-2 i-1 i std::vector<int> f(n); f[0] = 0; for (int i = 1; i < n; ++i) { f[i] = std::max(f[i-1], weights[i-1]); if (i >= 2) { upMax(f[i], f[i-2] + weights[i-1]); } if (i >= 3) { upMax(f[i], f[i-3] + weights[i-2] + weights[i-1]); } } int res = 0; for (int i = 0; i < n; ++i) { int cur = f[i]; if (i + 1 < n) cur += weights[i+1]; upMax(res, cur); } return res; } // }}} // sub 5 N <= 300 {{{ int sub5(int n, const std::vector<Fish>& fishes) { // Init weights[i][j] = sum of fish on column i, from row 0 -> row j std::vector<std::vector<int>> weights(n, std::vector<int> (n, 0)); for (const auto& fish : fishes) { weights[fish.col][fish.row] += fish.weight; } for (int col = 0; col < n; ++col) { std::partial_sum(weights[col].begin(), weights[col].end(), weights[col].begin()); } // f[c][r] = best strategy if we last BUILD PIER AT column c, row r // only considering fishes <= (c, r) // g[c][r] = similar to f[c][r] but consider fishes at column c, in row [r, n-1] std::vector<std::vector<int>> f(n, std::vector<int> (n, 0)), g(n, std::vector<int> (n, 0)); // f <= g for (int c = 1; c < n; ++c) { for (int r = 0; r < n; ++r) { // this is first pier f[c][r] = g[c][r] = weights[c-1][r]; // last pier at column i-1 for (int lastRow = 0; lastRow < n; ++lastRow) { if (lastRow <= r) { int cur = std::max( f[c-1][lastRow] + weights[c-1][r] - weights[c-1][lastRow], g[c-1][lastRow]); upMax(f[c][r], cur); upMax(g[c][r], cur); } else { upMax(f[c][r], g[c-1][lastRow]); upMax(g[c][r], g[c-1][lastRow] + weights[c][lastRow] - weights[c][r]); } } // last pier at column i-2 if (c >= 2) { for (int lastRow = 0; lastRow < n; ++lastRow) { int cur = g[c-2][lastRow] + weights[c-1][std::max(lastRow, r)]; upMax(f[c][r], cur); upMax(g[c][r], cur); } } // last pier at column i-3 if (c >= 3) { for (int lastRow = 0; lastRow < n; ++lastRow) { int cur = g[c-3][lastRow] + weights[c-2][lastRow] + weights[c-1][r]; upMax(f[c][r], cur); upMax(g[c][r], cur); } } } } int res = 0; for (int c = 0; c < n; ++c) { for (int r = 0; r < n; ++r) { assert(g[c][r] >= f[c][r]); int cur = g[c][r]; if (c + 1 < n) { cur += weights[c+1][r]; } upMax(res, cur); } } return res; } // }}} // N <= 3000 {{{ int sub6(int n, const std::vector<Fish>& fishes) { // Init weights[i][j] = sum of fish on column i, from row 0 -> row j std::vector<std::vector<int>> weights(n, std::vector<int> (n, 0)); for (const auto& fish : fishes) { weights[fish.col][fish.row] += fish.weight; } for (int col = 0; col < n; ++col) { std::partial_sum(weights[col].begin(), weights[col].end(), weights[col].begin()); } // f[c][r] = best strategy if we last BUILD PIER AT column c, row r // only considering fishes <= (c, r) // g[c][r] = similar to f[c][r] but consider fishes at column c, in row [r, n-1] std::vector<std::vector<int>> f(n, std::vector<int> (n, 0)), g(n, std::vector<int> (n, 0)), g_prefix_max(n, std::vector<int> (n, 0)), g_suffix_max(n, std::vector<int> (n, 0)), g_with_next_col_suffix_max(n, std::vector<int> (n, 0)), g_with_next_col_prefix_max(n, std::vector<int> (n, 0)), f_with_next_col_prefix_max(n, std::vector<int> (n, 0)); // f <= g for (int c = 0; c < n; ++c) { // compute {{{ if (c > 0) { for (int r = 0; r < n; ++r) { // this is first pier f[c][r] = g[c][r] = weights[c-1][r]; // last pier at column i-1 if (c >= 1) { // last row <= r int cur = std::max( g_prefix_max[c-1][r], f_with_next_col_prefix_max[c-1][r] + weights[c-1][r]); upMax(f[c][r], cur); upMax(g[c][r], cur); // last row > r if (r + 1 < n) { upMax(f[c][r], g_suffix_max[c-1][r + 1]); upMax(g[c][r], g_with_next_col_suffix_max[c-1][r + 1] - weights[c][r]); } } // last pier at column i-2 if (c >= 2) { int cur = std::max( g_prefix_max[c-2].back() + weights[c-1][r], g_with_next_col_prefix_max[c-2].back()); upMax(f[c][r], cur); upMax(g[c][r], cur); } // last pier at column i-3 if (c >= 3) { int cur = g_with_next_col_prefix_max[c-3].back() + weights[c-1][r]; upMax(f[c][r], cur); upMax(g[c][r], cur); } } } // }}} // aggregate {{{ // g_prefix_max[c][r] = max(g[c][0], .., g[c][r]) auto MAX = [] (auto a, auto b) { return std::max(a, b); }; std::partial_sum(g[c].begin(), g[c].end(), g_prefix_max[c].begin(), MAX); std::partial_sum(g[c].rbegin(), g[c].rend(), g_suffix_max[c].rbegin(), MAX); if (c + 1 < n) { // g_with_next_col_prefix_max[c][r] = max( // g[c][0] + weights[c+1][0], // ... // g[c][r] + weights[c+1][r]) for (int r = 0; r < n; ++r) { g_with_next_col_prefix_max[c][r] = g[c][r] + weights[c+1][r]; } g_with_next_col_suffix_max[c] = g_with_next_col_prefix_max[c]; std::partial_sum( g_with_next_col_prefix_max[c].begin(), g_with_next_col_prefix_max[c].end(), g_with_next_col_prefix_max[c].begin(), MAX); std::partial_sum( g_with_next_col_suffix_max[c].rbegin(), g_with_next_col_suffix_max[c].rend(), g_with_next_col_suffix_max[c].rbegin(), MAX); for (int r = 0; r < n; ++r) { f_with_next_col_prefix_max[c][r] = f[c][r] - weights[c][r]; } std::partial_sum( f_with_next_col_prefix_max[c].begin(), f_with_next_col_prefix_max[c].end(), f_with_next_col_prefix_max[c].begin(), MAX); } // }}} } int res = 0; for (int c = 0; c < n; ++c) { for (int r = 0; r < n; ++r) { assert(g[c][r] >= f[c][r]); int cur = g[c][r]; if (c + 1 < n) { cur += weights[c+1][r]; } upMax(res, cur); } } return res; } // }}} /* int sub7(int n, const std::vector<Fish>& fishes) { // fishesAt[col] = vector storing all fishes at column `col` std::vector<std::vector<std::pair<int, int>>> fishesAt(n); std::vector<std::vector<int>> weights(n); for (const auto& fish : fishes) { fishesAt[fish.col].push_back({fish.row, fish.weight}); } for (int c = 0; c < n; ++c) { fishesAt[c].push_back({-1, 0}); std::sort(fishesAt[c].begin(), fishesAt[c].end()); fishesAt[c].push_back({1000111, 0}); for (auto [row, weight] : fishesAt[c]) { weights[c].push_back(weight); } std::partial_sum(weights[c].begin(), weights[c].end(), weights[c].begin()); } // f[c][r] = best strategy if we last BUILD PIER AT column c, row r // only considering fishes <= (c, r) // g[c][r] = similar to f[c][r] but consider fishes at column c, in row [r, n-1] std::vector<std::vector<int>> f(n), g(n), g_prefix_max(n), g_suffix_max(n), g_with_next_col_suffix_max(n), g_with_next_col_prefix_max(n), f_with_next_col_prefix_max(n); for (int c = 0; c < n; ++c) { // compute {{{ int k = (int) fishesAt[c].size(); f[c].resize(k); g[c].resize(k); if (c > 0) { for (int i = 0; i < k - 1; ++i) { // ignore last int r = fishesAt[c][i].first; int i_1 = lower_bound( fishesAt[c-1].begin(), fishesAt[c-1].end(), std::make_pair(r+1, -1LL)) - fishesAt[c-1].begin(); --i_1; assert(fishesAt[c-1][i_1].first <= r && fishesAt[c-1][i_1 + 1].first > r); #define r ajckajcl // this is first pier f[c][i] = g[c][i] = weights[c-1][i_1]; // last pier at column i-1 { // last row <= r int cur = std::max( g_prefix_max[c-1][i_1], f_with_next_col_prefix_max[c-1][i_1] + weights[c-1][i_1]); f[c][i] = std::max(f[c][i], cur); g[c][i] = std::max(g[c][i], cur); // last row > r if (r + 1 < k-1) { f[c][i] = std::max(f[c][i], } } #undef r } } // }}} } return 0; } */ #undef int long long max_weights( int n, int nFish, std::vector<int> xs, std::vector<int> ys, std::vector<int> ws) { std::vector<Fish> fishes; for (int i = 0; i < nFish; ++i) { fishes.push_back({xs[i], ys[i], ws[i]}); } if (std::all_of(xs.begin(), xs.end(), [] (int x) { return x % 2 == 0; })) { return sub1(fishes); } if (*std::max_element(xs.begin(), xs.end()) <= 1) { return sub2(n, fishes); } if (*std::max_element(ys.begin(), ys.end()) == 0) { return sub3(n, fishes); } if (n <= 300) return sub5(n, fishes); return sub6(n, fishes); }
#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...