Submission #1270859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270859		repmann	Pinball (JOI14_pinball)	C++20	51 / 100	2 ms	584 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, M;
struct Device
{
  int a, b, c, d;
}D[1001];
ll DP[2][3001];
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> M >> N;
  for(int i = 1; i <= M; i++) cin >> D[i].a >> D[i].b >> D[i].c >> D[i].d;
  vector <pair <ll, ll>> scale;
  for(ll i = 1; i <= M; i++) scale.push_back({D[i].a, (i << 20) + 1});
  for(ll i = 1; i <= M; i++) scale.push_back({D[i].b, (i << 20) + 2});
  for(ll i = 1; i <= M; i++) scale.push_back({D[i].c, (i << 20) + 3});
  sort(scale.begin(), scale.end());
  if((scale[0].first != 1) || (scale[3 * M - 1].first != N)) {cout << "-1\n"; return 0;}
  int prev = 0;
  N = 0;
  for(pair <int, int> p : scale)
  {
    N += p.first > prev;
    prev = p.first;
    if((p.second & 3) == 1) D[p.second >> 20].a = N;
    if((p.second & 3) == 2) D[p.second >> 20].b = N;
    if((p.second & 3) == 3) D[p.second >> 20].c = N;
  }
  for(int i = 0; i <= N; i++) DP[0][i] = DP[1][i] = 1e18;
  ll sol = 1e18, a, b;
  for(int i = 1; i <= M; i++)
  {
    a = b = 1e18;
    if(D[i].a == 1) a = 0;
    else for(int j = D[i].a; j <= D[i].b; j++) a = min(DP[0][j], a);
    if(D[i].b == N) b = 0;
    else for(int j = D[i].a; j <= D[i].b; j++) b = min(DP[1][j], b);
    sol = min(a + b + D[i].d, sol);
    for(int j = D[i].a; j <= D[i].b; j++) DP[0][D[i].c] = min(DP[0][j] + D[i].d, DP[0][D[i].c]);
    for(int j = D[i].a; j <= D[i].b; j++) DP[1][D[i].c] = min(DP[1][j] + D[i].d, DP[1][D[i].c]);
    if(D[i].a == 1) DP[0][D[i].c] = min(1LL * D[i].d, DP[0][D[i].c]);
    if(D[i].b == N) DP[1][D[i].c] = min(1LL * D[i].d, DP[1][D[i].c]);
  }
  if(sol == 1e18) sol = -1;
  cout << sol << '\n';

  return 0;
}

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