Submission #216577

#	Time	Username	Problem	Language	Result	Execution time	Memory
216577		extraterrestrial	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	7 ms	5120 KiB

constellation3

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int BINF = 1e18;

const int N = 2e5 + 10;
int h[N], all[N], dp[N], dp2[N];
vector<pair<int, int>> have[N];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> h[i];
    h[i] = n - h[i];
  }  
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    have[x].pb({n - y + 1, c});
    all[x] += c;
  }
  for (int i = 1; i <= n; i++) {
    dp[i] = BINF;
  }
  for (int i = 1; i <= n; i++) {
    int mn = BINF;
    for (int j = h[i] + 1; j <= n; j++) {
      mn = min(mn, dp[j]);
      dp[j] = BINF;
    }
    dp[n + 1] = min(dp[n + 1], mn);
    if (!have[i].empty()) {
      for (int j = 1; j <= n + 1; j++) {
        dp2[j] = min(BINF, dp[j] + all[i]);
      }
      for (auto it : have[i]) {
        if (it.F > h[i - 1]) {
          for (int j = 1; j <= n + 1; j++) {
            dp2[min(j, it.F)] = min(dp2[min(j, it.F)], dp[j] + all[i] - it.S);
          }
        }
        else {
          dp2[it.F] = min(dp2[it.F], dp[n + 1] + all[i] - it.S);
        }
      }
      for (int j = 1; j <= n + 1; j++) {
        dp[j] = dp2[j];
      }
    }
  }
  int ans = BINF;
  for (int i = 1; i <= n + 1; i++) {
    ans = min(ans, dp[i]);
  }
  cout << ans << '\n';
} 

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