Submission #199784

#	Time	Username	Problem	Language	Result	Execution time	Memory
199784		arnold518	도장 모으기 (JOI14_stamps)	C++14	100 / 100	183 ms	71288 KiB

stamps

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;
const ll INF = 1e18;

int N;
ll A[MAXN+10], B[MAXN+10], C[MAXN+10], D[MAXN+10], T;
ll dp[MAXN+10][MAXN+10], E[MAXN+10], F[MAXN+10];

int main()
{
	int i, j, k;

	scanf("%d%lld", &N, &T);
	for(i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &A[i], &B[i], &C[i], &D[i]);

	for(i=1; i<=N; i++) dp[0][i]=INF; dp[0][0]=T;
	for(i=1; i<=N; i++)
	{
		for(j=0; j<=N; j++) E[j]=dp[i-1][j]+(2*j+1)*T+(A[i]+D[i])*j;
		for(j=0; j<=N; j++) F[j]=dp[i-1][j]+(2*j+1)*T-(B[i]+C[i])*j;
		for(j=N-1; j>=0; j--) E[j]=min(E[j], E[j+1]);
		for(j=1; j<=N; j++) F[j]=min(F[j], F[j-1]);

		for(j=0; j<=N; j++)
		{
			dp[i][j]=INF;

			dp[i][j]=min(dp[i][j], dp[i-1][j]+A[i]+B[i]+(2*j+1)*T);
			if(j>0) dp[i][j]=min(dp[i][j], dp[i-1][j]+C[i]+D[i]+(2*j+1)*T);
			if(j<N) dp[i][j]=min(dp[i][j], -(A[i]+D[i])*j+E[j+1]);
			if(j>0) dp[i][j]=min(dp[i][j], (B[i]+C[i])*j+F[j-1]);
		}
	}
	printf("%lld\n", dp[N][0]);
}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:22:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=1; i<=N; i++) dp[0][i]=INF; dp[0][0]=T;
  ^~~
stamps.cpp:22:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=1; i<=N; i++) dp[0][i]=INF; dp[0][0]=T;
                                    ^~
stamps.cpp:17:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
stamps.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~
stamps.cpp:20:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &A[i], &B[i], &C[i], &D[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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