Submission #1210424

#TimeUsernameProblemLanguageResultExecution timeMemory
1210424thangdz2k7Catfish Farm (IOI22_fish)C++20
100 / 100
125 ms35564 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; template <int D, typename T> struct Vec : public vector<Vec<D - 1, T>> { static_assert(D >= 1, "Dimension must be positive"); template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {} }; template <typename T> struct Vec<1, T> : public vector<T> { Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {} }; long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W){ vector <vector <pair <int, int>>> fishes(N); vector <int> siz(N); for (int i = 0; i < N; ++ i) fishes[i].emplace_back(N, 0); for (int i = 0; i < M; ++ i) fishes[X[i]].emplace_back(Y[i], W[i]); Vec <2, vector <long long>> dp(N, 2); for (int i = 0; i < N; ++ i){ sort(fishes[i].begin(), fishes[i].end()); siz[i] = fishes[i].size(); for (int t : {0, 1}) dp[i][t].resize(siz[i], 0); } auto maxl = [&](long long &a, long long b) -> void { a = max(a, b); }; for (int i = 1; i < N; ++ i){ long long val_up = 0; int ptr = 0; for (int j = 0; j < siz[i]; ++ j){ auto [y, w] = fishes[i][j]; if (y == N) y ++; while (ptr < siz[i - 1] && fishes[i - 1][ptr].first < y){ val_up = max(val_up, dp[i - 1][0][ptr]); val_up += fishes[i - 1][ptr].second; ptr ++; } dp[i][0][j] = val_up; } long long val_down = 0; ptr = siz[i - 1] - 1; for (int j = siz[i] - 1; j >= 0; -- j){ auto [y, w] = fishes[i][j]; while (ptr >= 0 && fishes[i - 1][ptr].first > y){ val_down = max(val_down, dp[i - 1][1][ptr]); ptr --; } val_down += w; dp[i][1][j] = val_down; } maxl(dp[i][1][siz[i] - 1], dp[i][0][siz[i] - 1]); maxl(dp[i][1][siz[i] - 1], dp[i - 1][1][0]); maxl(dp[i][0][0], dp[i - 1][1][0]); } return max(dp[N - 1][0][siz[N - 1] - 1], dp[N - 1][1][0]); }
#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...