oj.uz

Submission #199784

# Submission time Handle Problem Language Result Execution time Memory
199784 2020-02-03T10:49:46 Z arnold518 도장 모으기 (JOI14_stamps) C++14
100 / 100
 183 ms 71288 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], 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

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.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 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 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 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 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 5 ms 760 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 888 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 632 KB Output is correct
7 Correct 5 ms 764 KB Output is correct
8 Correct 5 ms 764 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 760 KB Output is correct
11 Correct 5 ms 888 KB Output is correct
12 Correct 5 ms 888 KB Output is correct
13 Correct 5 ms 888 KB Output is correct
14 Correct 5 ms 888 KB Output is correct
15 Correct 5 ms 888 KB Output is correct
16 Correct 8 ms 888 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 71032 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 173 ms 71264 KB Output is correct
4 Correct 141 ms 62840 KB Output is correct
5 Correct 109 ms 52088 KB Output is correct
6 Correct 51 ms 24312 KB Output is correct
7 Correct 32 ms 15352 KB Output is correct
8 Correct 168 ms 71160 KB Output is correct
9 Correct 171 ms 71160 KB Output is correct
10 Correct 183 ms 71160 KB Output is correct
11 Correct 171 ms 71160 KB Output is correct
12 Correct 170 ms 71160 KB Output is correct
13 Correct 176 ms 71288 KB Output is correct
14 Correct 169 ms 71288 KB Output is correct
15 Correct 171 ms 71160 KB Output is correct
16 Correct 180 ms 71288 KB Output is correct
17 Correct 172 ms 71160 KB Output is correct