Submission #129835

#	Time	Username	Problem	Language	Result	Execution time	Memory
129835		onjo0127	도장 모으기 (JOI14_stamps)	C++11	100 / 100	270 ms	212764 KiB

stamps

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

const long long INF = 1LL * 1e18;
long long DP[3009][3009], L[3009][3009], R[3009][3009];
long long U[3009], V[3009], D[3009], E[3009];

int main() {
	int N, T; scanf("%d%d",&N,&T);
	for(int i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &U[i], &V[i], &D[i], &E[i]);
	for(int i=1; i<=N; i++) DP[0][i] = INF;
	for(int i=1; i<=N; i++) {
		for(int j=0; j<=N; j++) {
			DP[i][j] = DP[i-1][j] + T + U[i] + V[i];
			if(j) DP[i][j] = min(DP[i][j], DP[i-1][j] + T + D[i] + E[i]);
		}
		L[i][0] = DP[i-1][0];
		for(int k=1; k<N; k++) L[i][k] = min(L[i][k-1], -(D[i] + V[i] - 2LL*T*i) * k + DP[i-1][k]);
		R[i][N] = (U[i] + E[i] + 2*T*i) * N + DP[i-1][N];
		for(int k=N-1; k>0; k--) R[i][k] = min(R[i][k+1], (U[i] + E[i] + 2LL*T*i) * k + DP[i-1][k]);

		for(int j=0; j<=N; j++) {
			if(j) DP[i][j] = min(DP[i][j], L[i][j-1] + T + (D[i] + V[i] - 2LL*T*i) * j);
			if(j+1<=N) DP[i][j] = min(DP[i][j], R[i][j+1] + T - (U[i] + E[i] + 2LL*T*i) * j);
		}
	}
	printf("%lld", DP[N][0] + T);
	return 0;
}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:9:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, T; scanf("%d%d",&N,&T);
            ~~~~~^~~~~~~~~~~~~~
stamps.cpp:10:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &U[i], &V[i], &D[i], &E[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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