Submission #678778

#TimeUsernameProblemLanguageResultExecution timeMemory
678778pls33Catfish Farm (IOI22_fish)C++17
44 / 100
1099 ms2097152 KiB
#include <bits/stdc++.h> #ifndef _AAAAAAAAA #include "fish.h" #endif using namespace std; #pragma region dalykai using p32 = pair<int, int>; using p32u = pair<uint32_t, uint32_t>; using p64 = pair<int64_t, int64_t>; using p64u = pair<uint64_t, uint64_t>; using vi16 = vector<int16_t>; using vi16u = vector<uint16_t>; using vi32 = vector<int>; using vi32u = vector<uint32_t>; using vi64 = vector<int64_t>; using vi64u = vector<uint64_t>; using vp32 = vector<p32>; using vp32u = vector<p32u>; using vp64 = vector<p64>; using vp64u = vector<p64u>; using vvi32 = vector<vi32>; using vvi32u = vector<vi32u>; using vvi64 = vector<vi64>; using vvi64u = vector<vi64u>; using vvp32 = vector<vp32>; using vvp32u = vector<vp32u>; using vvp64 = vector<vp64>; using vvp64u = vector<vp64u>; #pragma endregion struct node_t { int64_t val; p32 range; node_t *left, *right; node_t(p32 r) { val = 0; range = r; left = nullptr; right = nullptr; } void update() { if (!right || range.second - range.first == 1) { return; } val = max(left->val, right->val); } void expand() { if (range.second - range.first == 1 || right) { return; } int mid = (range.first + range.second) / 2; left = new node_t({range.first, mid}); right = new node_t({mid, range.second}); } int contains(p32 query) { if (query.first >= range.second || query.second <= range.first) { return 0; } if (range.first >= query.first && range.second <= query.second) { return 1; } return 2; } }; void update(node_t *node, int64_t val, p32 dest) { if (!node || !node->contains(dest)) { return; } if (node->contains(dest) == 1) { node->val = max(node->val, val); return; } node->expand(); update(node->left, val, dest); update(node->right, val, dest); node->update(); } int64_t query(node_t *node, p32 dest) { if (!node || !node->contains(dest)) { return 0; } if (node->contains(dest) == 1) { return node->val; } return max(query(node->left, dest), query(node->right, dest)); } void assign_max(int64_t val, p32 fish, vvi64 &vect) { vect[fish.first][fish.second] = max(vect[fish.first][fish.second], val); } int64_t weight_sum(int i, int j, vvi64 &prefix, int row) { if (i == -1) { return 0; } int64_t sum = prefix[row][j]; if (i) { sum -= prefix[row][i - 1]; } return sum; } int64_t new_weight(p32 lhs, p32 rhs, vvi64 &prefix) { int64_t left = rhs.first > 0 ? weight_sum(0, rhs.second, prefix, rhs.first - 1) : 0; int64_t right = (rhs.first + 1 < (int)prefix.size()) ? weight_sum(0, rhs.second, prefix, rhs.first + 1) : 0; if (lhs.first == -1) { return left + right; } if (rhs.first - lhs.first > 2) { return left + right; } if (rhs.first - lhs.first == 2) { if (lhs.second >= rhs.second) { return right; } left -= weight_sum(0, lhs.second, prefix, rhs.first - 1); return left + right; } if (lhs.second > rhs.second) { left = -weight_sum(0, rhs.second, prefix, rhs.first); return left + right; } left -= weight_sum(0, lhs.second, prefix, rhs.first) + weight_sum(0, lhs.second, prefix, rhs.first - 1); return left + right; } long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { vp32 fish; int max_y = 0; for (int i = 0; i < M; i++) { max_y = max(max_y, Y[i]); if (X[i]) { fish.push_back({X[i] - 1, Y[i]}); } if (X[i] < N - 1) { fish.push_back({X[i] + 1, Y[i]}); } } vvi64 prefix(N, vi64(max_y + 1)); for (int i = 0; i < M; i++) { prefix[X[i]][Y[i]] = W[i]; } for (auto &row : prefix) { for (int i = 1; i < (int)row.size(); i++) { row[i] += row[i - 1]; } } sort(fish.begin(), fish.end()); auto it = unique(fish.begin(), fish.end()); fish.erase(it, fish.end()); vvi64 decrease(N, vi64(max_y + 1)); vvi64 increase(N, vi64(max_y + 1)); vp32 check; node_t *fish_count = new node_t({0, N}); for (auto &f : fish) { int64_t initial = new_weight(p32(-1, -1), f, prefix); if (f.first > 2) { initial += query(fish_count, {0, f.first - 2}); } assign_max(initial, f, increase); assign_max(initial, f, decrease); check.push_back(f); for (int cur = (int)check.size() - 2; cur >= 0; cur--) { auto &[i, j] = check[cur]; if (f.first - i > 3) { break; } if (i == f.first) { continue; } int64_t prev = new_weight(p32(i, j), f, prefix); if (i == f.first - 1) { if (j < f.second) { assign_max(prev + increase[i][j], f, increase); } else { assign_max(prev + decrease[i][j], f, decrease); } } else { prev += max(increase[i][j], decrease[i][j]); assign_max(prev, f, increase); assign_max(prev, f, decrease); } } update(fish_count, max(increase[f.first][f.second], decrease[f.first][f.second]), {f.first, f.first + 1}); } return fish_count->val; } #ifdef _AAAAAAAAA int main() { freopen("fish.in", "r", stdin); #ifndef __linux__ atexit([]() { freopen("con", "r", stdin); system("pause"); }); #endif int N, M; assert(2 == scanf("%d %d", &N, &M)); std::vector<int> X(M), Y(M), W(M); for (int i = 0; i < M; ++i) { assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i])); } long long result = max_weights(N, M, X, Y, W); printf("%lld\n", result); return 0; } #endif

Compilation message (stderr)

fish.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
fish.cpp:31: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   31 | #pragma endregion
      |
#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...