제출 #18789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18789		choyi0521	도장 모으기 (JOI14_stamps)	C++14	85 / 100	50 ms	1176 KiB

stamps

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 3000;
typedef long long ll;
int n, t, s1[MAX_N + 1], s2[MAX_N + 1];
int u[MAX_N + 1], v[MAX_N + 1], d[MAX_N + 1], e[MAX_N + 1];
ll dp[MAX_N + 1];
int main() {
	scanf("%d %d", &n, &t);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d %d", &u[i], &v[i], &d[i], &e[i]);
		s1[i] = s1[i - 1] + u[i] + v[i];
		s2[i] = s2[i - 1] + min(u[i] + v[i], d[i] + e[i]);
	}
	fill(dp + 1, dp + 1 + n, 1e18);
	ll mini = 1e18;
	for (int i = 0; i <n; i++) {
		if(i) mini = min(mini, (ll)v[i] + d[i] - 2 * i*t);
		for (int j = i + 1; j <= n; j++) {
			dp[j] = min({ dp[j],
				dp[i] + s1[j] - s1[i] + (j - i)*t,
				dp[i] + (3 * j - i)*t + s2[j - 1] - s2[i] + u[j] + e[j] +mini });
			if (j != i + 1) dp[j] = min(dp[j],
				dp[i] + (3 * j - 3 * i - 2)*t + s2[j - 1] - s2[i + 1] + u[j] + e[j] + v[i + 1] + d[i + 1]);
		}
	}
	printf("%lld", dp[n] + t);
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 75 / 75
• Subtask 3: 0 / 15