제출 #969940

#제출 시각아이디문제언어결과실행 시간메모리
969940maksim1744메기 농장 (IOI22_fish)C++17
23 / 100
1047 ms13288 KiB
/* author: Maksim1744 created: 26.04.2024 01:52:26 */ #include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; #define mp make_pair #define pb push_back #define eb emplace_back #define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll)) #define mine(a) (*min_element((a).begin(), (a).end())) #define maxe(a) (*max_element((a).begin(), (a).end())) #define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin()) #define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin()) #define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin()) #define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin()) template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;} template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;} template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;} template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;} template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;} template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;} template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;} template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;} template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);} template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);} template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;} template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;} #ifdef HOME #define SHOW_COLORS #include "/mnt/c/Libs/tools/print.cpp" #else #define show(...) void(0) #define debugf(fun) fun #define debugv(var) var #define mclock void(0) #define shows void(0) #define debug if (false) #define OSTREAM(...) ; #define OSTREAM0(...) ; #endif const ll inf = 1e18; ll max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { int sz = maxe(Y) + 1; vector<ll> dp1(sz + 1, -inf); vector<ll> dp2(sz + 1, -inf); vector<vector<pair<int, int>>> atx(n); for (int i = 0; i < m; ++i) { atx[X[i]].eb(Y[i], W[i]); } dp1[0] = dp2[0] = 0; for (int i = 0; i < n; ++i) { vector<ll> next_dp1(sz + 1, -inf); vector<ll> next_dp2(sz + 1, -inf); for (int h = 0; h <= sz; ++h) { for (int h2 = 0; h2 <= sz; ++h2) { { ll cur = 0; if (i > 0 && h2 < h) { for (const auto& [y, w] : atx[i - 1]) { if (h2 <= y && y < h) { cur += w; } } } cur += dp1[h2]; next_dp2[h] = max(next_dp2[h], cur); next_dp1[h] = max(next_dp1[h], cur); } { ll cur = 0; if (h2 > h) { for (const auto& [y, w] : atx[i]) { if (h2 > y && y >= h) { cur += w; } } } cur += dp2[h2]; next_dp1[h2] = max(next_dp1[h2], cur); next_dp2[h] = max(next_dp2[h], cur); } } next_dp2[h] = max(next_dp2[h], maxe(dp2)); } swap(dp1, next_dp1); swap(dp2, next_dp2); show(dp1, dp2); } return max(maxe(dp1), maxe(dp2)); } #ifdef HOUSE int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<int> x(m), y(m), w(m); for (int i = 0; i < m; ++i) { cin >> x[i] >> y[i] >> w[i]; } cout << max_weights(n, m, x, y, w) << '\n'; return 0; } #endif
#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...