제출 #377420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377420		reymontada61	Pinball (JOI14_pinball)	C++14	51 / 100	8 ms	620 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m;
const int MXN = 1005;
int l[MXN], r[MXN], to[MXN], c[MXN];

int lec[MXN], ric[MXN];

int MXE = LLONG_MAX / 2;

int ans = MXE;
bool can;

signed main() {

	cin >> m >> n;
	for (int i=1; i<=m; i++) {
		cin >> l[i] >> r[i] >> to[i] >> c[i];
	}
	
	for (int i=1; i<=m; i++) {
		if (l[i] == 1) {
			lec[i] = c[i];
		}
		else {
			lec[i] = MXE;
			for (int x=1; x<i; x++) {
				if (l[i] <= to[x] && to[x] <= r[i]) {
					lec[i] = min(lec[i], lec[x] + c[i]);
				}
			}
		}
		
		if (r[i] == n) {
			ric[i] = c[i];
		}
		else {
			ric[i] = MXE;
			for (int x=1; x<i; x++) {
				if (l[i] <= to[x] && to[x] <= r[i]) {
					ric[i] = min(ric[i], ric[x] + c[i]);
				}
			}
		}
		
		if (lec[i] == MXE || ric[i] == MXE) continue;
		
		can = true;
		ans = min(ans, lec[i] + ric[i] - c[i]);
			
	}
	
	if (can) cout << ans << endl;
	else cout << -1 << endl;
	
}

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