Submission #1270849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270849		repmann	Pinball (JOI14_pinball)	C++20	In queue	0 ms	0 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][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++)
  {
    for(int j = 0; j <= N; j++) DP[0][i][j] = DP[1][i][j] = 1e18;
  }
  ll sol = 1e18, a, b;
  for(int i = 1; i <= M; i++)
  {
    a = b = 1e18;
    for(int j = D[i].a; j <= D[i].b; j++) a = min(DP[0][1][j], a);
    for(int j = D[i].a; j <= D[i].b; j++) b = min(DP[1][N][j], b);
    sol = min(a + b + D[i].d, sol);
    for(int j = 1; j <= D[i].c; j++)
    {
      for(int k = D[i].a; k <= D[i].b; k++) DP[0][j][D[i].c] = min(DP[0][j][k] + D[i].d, DP[0][j][D[i].c]);
    }
    for(int j = D[i].c; j <= N; j++)
    {
      for(int k = D[i].a; k <= D[i].b; k++) DP[1][j][D[i].c] = min(DP[1][j][k] + D[i].d, DP[1][j][D[i].c]);
    }
    DP[0][D[i].a][D[i].c] = min(1LL * D[i].d, DP[0][D[i].a][D[i].c]);
    DP[1][D[i].b][D[i].c] = min(1LL * D[i].d, DP[1][D[i].b][D[i].c]);
  }
  if(sol == 1e18) sol = -1;
  cout << sol << '\n';

  return 0;
}