oj.uz

Submission #212456

# Submission time Handle Problem Language Result Execution time Memory
212456 2020-03-23T04:57:20 Z rama_pang Constellation 3 (JOI20_constellation3) C++14
35 / 100
 101 ms 46712 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3584 KB Output is correct
2 Correct 8 ms 3584 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3200 KB Output is correct
6 Correct 7 ms 3328 KB Output is correct
7 Correct 8 ms 3328 KB Output is correct
8 Correct 8 ms 3584 KB Output is correct
9 Correct 7 ms 3456 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Correct 7 ms 3200 KB Output is correct
12 Correct 6 ms 3072 KB Output is correct
13 Correct 7 ms 2944 KB Output is correct
14 Correct 6 ms 2944 KB Output is correct
15 Correct 6 ms 3200 KB Output is correct
16 Correct 7 ms 3200 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 2176 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 6 ms 2176 KB Output is correct
22 Correct 5 ms 512 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3584 KB Output is correct
2 Correct 8 ms 3584 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3200 KB Output is correct
6 Correct 7 ms 3328 KB Output is correct
7 Correct 8 ms 3328 KB Output is correct
8 Correct 8 ms 3584 KB Output is correct
9 Correct 7 ms 3456 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Correct 7 ms 3200 KB Output is correct
12 Correct 6 ms 3072 KB Output is correct
13 Correct 7 ms 2944 KB Output is correct
14 Correct 6 ms 2944 KB Output is correct
15 Correct 6 ms 3200 KB Output is correct
16 Correct 7 ms 3200 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 2176 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 6 ms 2176 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 89 ms 44616 KB Output is correct
24 Correct 89 ms 44656 KB Output is correct
25 Correct 92 ms 44792 KB Output is correct
26 Correct 97 ms 46200 KB Output is correct
27 Correct 97 ms 45048 KB Output is correct
28 Correct 88 ms 44152 KB Output is correct
29 Correct 88 ms 45176 KB Output is correct
30 Correct 101 ms 46712 KB Output is correct
31 Correct 92 ms 44988 KB Output is correct
32 Correct 49 ms 34936 KB Output is correct
33 Correct 53 ms 36600 KB Output is correct
34 Correct 48 ms 35576 KB Output is correct
35 Correct 50 ms 36216 KB Output is correct
36 Correct 54 ms 38008 KB Output is correct
37 Correct 55 ms 38136 KB Output is correct
38 Correct 68 ms 36856 KB Output is correct
39 Correct 29 ms 896 KB Output is correct
40 Correct 39 ms 22648 KB Output is correct
41 Correct 28 ms 768 KB Output is correct
42 Correct 28 ms 1024 KB Output is correct
43 Correct 38 ms 22912 KB Output is correct
44 Correct 27 ms 768 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3584 KB Output is correct
2 Correct 8 ms 3584 KB Output is correct
3 Correct 8 ms 3456 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3200 KB Output is correct
6 Correct 7 ms 3328 KB Output is correct
7 Correct 8 ms 3328 KB Output is correct
8 Correct 8 ms 3584 KB Output is correct
9 Correct 7 ms 3456 KB Output is correct
10 Correct 6 ms 3072 KB Output is correct
11 Correct 7 ms 3200 KB Output is correct
12 Correct 6 ms 3072 KB Output is correct
13 Correct 7 ms 2944 KB Output is correct
14 Correct 6 ms 2944 KB Output is correct
15 Correct 6 ms 3200 KB Output is correct
16 Correct 7 ms 3200 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 6 ms 2176 KB Output is correct
19 Correct 5 ms 512 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 6 ms 2176 KB Output is correct
22 Correct 5 ms 512 KB Output is correct
23 Correct 89 ms 44616 KB Output is correct
24 Correct 89 ms 44656 KB Output is correct
25 Correct 92 ms 44792 KB Output is correct
26 Correct 97 ms 46200 KB Output is correct
27 Correct 97 ms 45048 KB Output is correct
28 Correct 88 ms 44152 KB Output is correct
29 Correct 88 ms 45176 KB Output is correct
30 Correct 101 ms 46712 KB Output is correct
31 Correct 92 ms 44988 KB Output is correct
32 Correct 49 ms 34936 KB Output is correct
33 Correct 53 ms 36600 KB Output is correct
34 Correct 48 ms 35576 KB Output is correct
35 Correct 50 ms 36216 KB Output is correct
36 Correct 54 ms 38008 KB Output is correct
37 Correct 55 ms 38136 KB Output is correct
38 Correct 68 ms 36856 KB Output is correct
39 Correct 29 ms 896 KB Output is correct
40 Correct 39 ms 22648 KB Output is correct
41 Correct 28 ms 768 KB Output is correct
42 Correct 28 ms 1024 KB Output is correct
43 Correct 38 ms 22912 KB Output is correct
44 Correct 27 ms 768 KB Output is correct
45 Runtime error 100 ms 7032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Halted 0 ms 0 KB -