제출 #212456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212456		rama_pang	별자리 3 (JOI20_constellation3)	C++14	35 / 100	101 ms	46712 KiB

constellation3

#include "bits/stdc++.h"
using namespace std;
using lint = long long;

const int MAXN = 200005;

int N, M;
int A[MAXN], X[MAXN], Y[MAXN], C[MAXN];

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];
  }
}

namespace Dynamic_Programming { // O(N^2) DP solution
  
  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]);
      }
    }
  }

  long long solve() {
    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++) {
        maximum = max(maximum, DP[i][j]);
      }
    }

    return sum_all - maximum; 
  }

}

int main() {
  read();
  Dynamic_Programming::init();
  cout << Dynamic_Programming::solve() << "\n";
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 65