Submission #1186640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186640		JooDdae	도장 모으기 (JOI14_stamps)	C++20	100 / 100	106 ms	71744 KiB

stamps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e12;

int n;
ll t, dp[3030][3030], tmp[3030], u[3030], v[3030], d[3030], e[3030];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> t;
	for(int i=1;i<=n;i++) cin >> u[i] >> v[i] >> d[i] >> e[i];

	fill(dp[0]+1, dp[0]+n+1, INF);

	for(int i=1;i<=n;i++) {
		fill(dp[i], dp[i]+n+1, INF);

		for(int j=0;j<=n;j++) {
			tmp[j] = dp[i-1][j] + 2*t*j + t;
		}
		for(int j=0;j<=n;j++) {
			dp[i][j] = min(dp[i][j], tmp[j] + u[i]+v[i]);
			if(j) dp[i][j] = min(dp[i][j], tmp[j] + d[i]+e[i]);
		}
		for(int j=1;j<=n;j++) {
			dp[i][j] = min(dp[i][j], min(tmp[j-1], dp[i][j-1]) + d[i]+v[i]);
		}
		for(int j=n-1;j>=0;j--) {
			dp[i][j] = min(dp[i][j], min(tmp[j+1], dp[i][j+1]) + u[i]+e[i]);
		}
	}

	cout << dp[n][0] + t;
}

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