oj.uz

Submission #199783

# Submission time Handle Problem Language Result Execution time Memory
199783 2020-02-03T10:42:13 Z arnold518 도장 모으기 (JOI14_stamps) C++14
85 / 100
 1000 ms 2552 KB 
#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];

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++)
		{
			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);
			for(k=j+1; k<=N; k++) dp[i][j]=min(dp[i][j], dp[i-1][k]+(2*k+1)*T+(A[i]+D[i])*(k-j));
			for(k=j-1; k>=0; k--) dp[i][j]=min(dp[i][j], dp[i-1][k]+(2*k+1)*T+(B[i]+C[i])*(j-k));

			//printf("%lld ", dp[i][j]);
		}
		printf("\n");
	}
	printf("%lld\n", dp[N][0]);
}

Compilation message

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: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 7 ms 760 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 508 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 7 ms 760 KB Output is correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 7 ms 760 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 7 ms 760 KB Output is correct
13 Correct 7 ms 888 KB Output is correct
14 Correct 7 ms 760 KB Output is correct
15 Correct 7 ms 760 KB Output is correct
16 Correct 7 ms 760 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 2552 KB Time limit exceeded
2 Halted 0 ms 0 KB -