oj.uz

Submission #129732

# Submission time Handle Problem Language Result Execution time Memory
129732 2019-07-13T06:01:55 Z 김세빈(#3138) 도장 모으기 (JOI14_stamps) C++14
85 / 100
 1000 ms 380 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll D[2][3030];
ll n, t;

int main()
{
	ll i, j, k;
	ll u1, v1, u2, v2, c1, c2, c3, c4;
	
	scanf("%lld%lld", &n, &t);
	
	for(i=1; i<=n; i++){
		D[0][i] = 1e18;
	}
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld%lld%lld", &u1, &v1, &u2, &v2);
		c1 = u1 + v1; c2 = u2 + v2;
		c3 = v1 + u2 + (n - i) * t * 2;
		c4 = u1 + v2 - (n - i) * t * 2;
			
		for(j=0; j<=n; j++){
			ll &v = D[1][j] = D[0][j] + c1;
			if(j) v = min(v, D[0][j] + c2);
			
			for(k=1; j-k>=0; k++){
				v = min(v, D[0][j - k] + c3 * k);
			}
			
			for(k=1; j+k<=n; k++){
				v = min(v, D[0][j + k] + c4 * k);
			}
		}
		
		for(j=0; j<=n; j++){
			swap(D[0][j], D[1][j]);
		}
	}
	
	printf("%lld\n", D[0][0] + (n + 1) * t);
	
	return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
stamps.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &u1, &v1, &u2, &v2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
75.0 / 75.0

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

Subtask #3
0 / 15.0

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