제출 #212651

#제출 시각아이디문제언어결과실행 시간메모리
212651rama_pang별자리 3 (JOI20_constellation3)C++14
100 / 100
616 ms45448 KiB
#include "bits/stdc++.h" using namespace std; class Dyanmic_Programming { // O(N^2) DP solution private: int N, M; int A[2005], X[2005], Y[2005], C[2005]; long long DP[2005][2005]; // DP[height][column] = DP with domain(height, column) if we are forced to pick cell (heigth, column). int Star[2005][2005]; void init() { for (int i = 0; i < M; i++) { for (int height = Y[i]; height <= N + 1; height++) { Star[height][X[i]] = max(Star[height][X[i]], C[i]); } } } public: long long solve() { init(); for (int height = 1; height <= N + 1; height++) { // height N + 1 to merge all components into one for (int left = 1, right = left; left <= N; left = (++right)) { if (A[left] >= height) continue; // this cell is still occupied by a building (white cell). while (right + 1 <= N && A[right + 1] < height) { right++; } // column = left...right is connected to each other, now we find the transition vector<pair<pair<int, int>, long long>> maximum_values; // maximum values of disjoint domains for cells [height - 1][left...right] for (int l = left, r = l; l <= right; l = (++r)) { if (A[l] >= height - 1) continue; while (r + 1 <= right && A[r + 1] < height - 1) { r++; } { // with star long long mx = 0; for (int k = l; k <= r; k++) { mx = max(mx, DP[height - 1][k]); } maximum_values.push_back({{l, r}, mx}); } } long long sum_max_values = 0; for (auto &values : maximum_values) { sum_max_values += values.second; } for (int column = left; column <= right; column++) { DP[height][column] = sum_max_values + Star[height][column]; } for (auto &values : maximum_values) { for (int column = values.first.first; column <= values.first.second; column++) { DP[height][column] -= values.second; // This is not necessarily the correct domain and forbidden, so we subtract it DP[height][column] += DP[height - 1][column] - Star[height - 1][column]; // This is the real domain and forbidden, minus the Star in (height - 1, column). } } } } long long sum_all = 0; long long maximum = 0; for (int i = 0; i < M; i++) { sum_all += C[i]; } for (int i = N + 1; i >= 1; i--) { for (int j = 1; j <= N; j++) { if (i == N + 1 ) { maximum = max(maximum, DP[i][j]); } } } return sum_all - maximum; } void read() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> N; for (int i = 1; i <= N; i++) { cin >> A[i]; } cin >> M; for (int i = 0; i < M; i++) { cin >> X[i] >> Y[i] >> C[i]; } } }; class Full_Solution { private: int N, M; vector<int> A, X, Y, C; class DisjointSet { public: vector<int> p; DisjointSet(int n) { p.resize(n); iota(begin(p), end(p), 0); } int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); } }; class SegmentTree { private: vector<long long> tree; vector<long long> lazy; int sz; void push(int n) { for (int c = 0; c < 2; c++) { tree[n * 2 + c] += lazy[n]; lazy[n * 2 + c] += lazy[n]; } lazy[n] = 0; } void pull(int n) { tree[n] = max(tree[n * 2], tree[n * 2 + 1]); } void RangeSumUpdate(int n, int tl, int tr, int l, int r, long long x) { if (tr < l || r < tl || tl > tr || l > r) return; if (l <= tl && tr <= r) { tree[n] += x; lazy[n] += x; return; } push(n); int mid = (tl + tr) / 2; RangeSumUpdate(n * 2, tl, mid, l, r, x); RangeSumUpdate(n * 2 + 1, mid + 1, tr, l, r, x); pull(n); } long long RangeMaximumQuery(int n, int tl, int tr, int l, int r) { if (tr < l || r < tl || tl > tr || l > r) return 0; if (l <= tl && tr <= r) return tree[n]; push(n); int mid = (tl + tr) / 2; return max(RangeMaximumQuery(n * 2, tl, mid, l, r), RangeMaximumQuery(n * 2 + 1, mid + 1, tr, l, r)); } public: SegmentTree(int n) { sz = n; tree.assign(4 * n, 0); lazy.assign(4 * n, 0); } void RangeSumUpdate(int l, int r, long long x) { return RangeSumUpdate(1, 0, sz - 1, l, r, x); } long long RangeMaximumQuery(int l, int r) { return RangeMaximumQuery(1, 0, sz - 1, l, r); } }; vector<vector<pair<int, int>>> CalculateStarDifference() { vector<vector<pair<int, int>>> StarDifference(N + 2); // SD[height] = Points where Star[height][column] - Star[height - 1][column] > 0, with (column, value) vector<vector<int>> YCoordinates(N + 1); vector<vector<int>> stars_per_column(N + 1); for (int i = 0; i < M; i++) { YCoordinates[X[i]].emplace_back(Y[i]); } for (int i = 1; i <= N; i++) { sort(begin(YCoordinates[i]), end(YCoordinates[i])); YCoordinates[i].resize(unique(begin(YCoordinates[i]), end(YCoordinates[i])) - begin(YCoordinates[i])); } for (int i = 1; i <= N; i++) { stars_per_column[i].resize(YCoordinates[i].size()); } for (int i = 0; i < M; i++) { int where = lower_bound(begin(YCoordinates[X[i]]), end(YCoordinates[X[i]]), Y[i]) - begin(YCoordinates[X[i]]); stars_per_column[X[i]][where] = max(stars_per_column[X[i]][where], C[i]); } for (int i = 1; i <= N; i++) { for (int j = 1; j < stars_per_column[i].size(); j++) { stars_per_column[i][j] = max(stars_per_column[i][j], stars_per_column[i][j - 1]); } } for (int i = 1; i <= N; i++) { for (int j = 0; j < stars_per_column[i].size(); j++) { int value = stars_per_column[i][j] - (j > 0 ? stars_per_column[i][j - 1] : 0); StarDifference[YCoordinates[i][j]].emplace_back(i, value); } } return StarDifference; } vector<vector<int>> CalculateBuildingsWithHeight() { vector<vector<int>> BuildingsWithHeight(N + 2); // bwh[height] = A[i] such that A[i] = height - 1 for (int i = 1; i <= N; i++) { BuildingsWithHeight[A[i] + 1].emplace_back(i); } return BuildingsWithHeight; } long long SumAll() { // sum of all C[i] long long res = 0; for (int i = 0; i < M; i++) { res += C[i]; } return res; } public: void read() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> N; A.resize(N + 1); for (int i = 1; i <= N; i++) { cin >> A[i]; } cin >> M; X.resize(M); Y.resize(M); C.resize(M); for (int i = 0; i < M; i++) { cin >> X[i] >> Y[i] >> C[i]; } } long long solve() { // initialization vector<vector<pair<int, int>>> StarDifference; // Points where Star[height][column] - Star[height - 1][column] > 0, with (height, value) StarDifference = CalculateStarDifference(); vector<vector<int>> BuildingsWithHeight(N + 2); // BWH[height] = A[i] such that A[i] = height - 1 BuildingsWithHeight = CalculateBuildingsWithHeight(); // DP optimized with Segment Tree SegmentTree seg(N + 1); DisjointSet left_bound(N + 1), right_bound(N + 1); // left and right bound of components vector<bool> active(N + 1, false); // determine if column is already active (height > A[column]) for (int height = 1; height <= N + 1; height++) { // Merge Components vector<pair<int, int>> LR_bounds_old; // to-be-merged components of height - 1 vector<pair<int, int>> LR_bounds_new; // result of merged components of height for (auto &col : BuildingsWithHeight[height]) { if (col - 1 >= 1 && active[col - 1]) { int l = left_bound.Find(col - 1); int r = right_bound.Find(col - 1); assert(r == col - 1); LR_bounds_old.emplace_back(l, r); } if (col + 1 <= N && active[col + 1]) { int l = left_bound.Find(col + 1); int r = right_bound.Find(col + 1); assert(l == col + 1); LR_bounds_old.emplace_back(l, r); } } for (auto &col : BuildingsWithHeight[height]) { active[col] = true; if (col - 1 >= 1 && active[col - 1]) { left_bound.p[col] = col - 1; right_bound.p[col - 1] = col; } if (col + 1 <= N && active[col + 1]) { right_bound.p[col] = col + 1; left_bound.p[col + 1] = col; } } for (auto &col : BuildingsWithHeight[height]) { int l = col, r = col; if (col - 1 >= 1 && active[col - 1]) l = left_bound.Find(col - 1); if (col + 1 <= N && active[col + 1]) r = right_bound.Find(col + 1); LR_bounds_new.emplace_back(l, r); } sort(begin(LR_bounds_old), end(LR_bounds_old)); LR_bounds_old.resize(unique(begin(LR_bounds_old), end(LR_bounds_old)) - begin(LR_bounds_old)); sort(begin(LR_bounds_new), end(LR_bounds_new)); LR_bounds_new.resize(unique(begin(LR_bounds_new), end(LR_bounds_new)) - begin(LR_bounds_new)); // Update the DP on Segment Tree // Add sum_of_maximums_of_previous_components - maximum_this_component int ptr = 0; for (auto &new_component : LR_bounds_new) { long long sum_of_maximums = 0; for (; ptr < LR_bounds_old.size(); ptr++) { if (new_component.first <= LR_bounds_old[ptr].first && LR_bounds_old[ptr].second <= new_component.second) { long long current_maximum = seg.RangeMaximumQuery(LR_bounds_old[ptr].first, LR_bounds_old[ptr].second); seg.RangeSumUpdate(LR_bounds_old[ptr].first, LR_bounds_old[ptr].second, -current_maximum); sum_of_maximums += current_maximum; } else if (new_component.second < LR_bounds_old[ptr].first) { break; } } seg.RangeSumUpdate(new_component.first, new_component.second, sum_of_maximums); } // Add StarDifference (Star[height][column] - Star[height - 1][column]) for (auto &stars : StarDifference[height]) { int column = stars.first; int value = stars.second; seg.RangeSumUpdate(column, column, value); } } return SumAll() - seg.RangeMaximumQuery(1, N); } }; int main() { Full_Solution Solver; Solver.read(); cout << Solver.solve() << "\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In member function 'std::vector<std::vector<std::pair<int, int> > > Full_Solution::CalculateStarDifference()':
constellation3.cpp:212:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 1; j < stars_per_column[i].size(); j++) {
                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:218:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < stars_per_column[i].size(); j++) {
                       ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp: In member function 'long long int Full_Solution::solve()':
constellation3.cpp:338:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; ptr < LR_bounds_old.size(); ptr++) {
                ~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...