Submission #1147920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147920		fryingduc	Pinball (JOI14_pinball)	C++20	51 / 100	1093 ms	1540 KiB

pinball

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, m, a[maxn], b[maxn], c[maxn], d[maxn];
pair<int, long long> fl[maxn], fr[maxn];

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  long long res = 1e18;
  for (int i = 1; i <= n; ++i) {
    fl[i] = make_pair(a[i], d[i]);
    fr[i] = make_pair(b[i], -d[i]);
    for (int j = 1; j < i; ++j) {
      if (a[i] <= c[j] and c[j] <= b[i]) {
        pair<int, long long> x = fl[j]; x.second += d[i];
        fl[i] = min(fl[i], x);
        x = fr[j]; x.second -= d[i];
        fr[i] = max(fr[i], x);
      }
    }
    if (fl[i].first == 1 and fr[i].first == m) {
      res = min(res, fl[i].second - fr[i].second - d[i]);
    }
  }
  debug(res);
  cout << (res == 1e18 ? -1 : res);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49