oj.uz

Submission #51756

# Submission time Handle Problem Language Result Execution time Memory
51756 2018-06-21T03:28:54 Z model_code None (JOI14_ho_t2) C++17
100 / 100
 11 ms 748 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1001001001;
const int LIM_M = 10000;
const int LIM_N = 500;

int M, N;
int P[LIM_M + 10];
int C[LIM_N + 10], E[LIM_N + 10];

int PSum[LIM_M + 10];
int dp[LIM_M + 10];

int main() {
	int i, j;
	
	scanf("%d%d", &M, &N);
	for (i = 0; i < M; ++i) {
		scanf("%d", &P[i]);
	}
	for (j = 0; j < N; ++j) {
		scanf("%d%d", &C[j], &E[j]);
	}
	
	//	PSum[i] := maximum price for selling i manjus.
	sort(P, P + M, greater<int>());
	for (i = 0; i < M; ++i) {
		PSum[i + 1] = PSum[i] + P[i];
	}
	
	//	dp[i] := minimum expense for boxes to pack i manjus.
	//	invariant: dp[0] <= dp[1] <= ... <= dp[M].
	for (i = 0; i <= M; ++i) {
		dp[i] = INF;
	}
	dp[0] = 0;
	for (j = 0; j < N; ++j) {
		for (i = M; i >= 0; --i) {
			if (dp[i] > dp[max(i - C[j], 0)] + E[j]) {
				dp[i] = dp[max(i - C[j], 0)] + E[j];
			}
		}
	}
	
	int ans = 0;
	for (i = 0; i <= M; ++i) {
		if (ans < PSum[i] - dp[i]) {
			ans = PSum[i] - dp[i];
		}
	}
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

2014_ho_t2.cpp: In function 'int main()':
2014_ho_t2.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &M, &N);
  ~~~~~^~~~~~~~~~~~~~~~
2014_ho_t2.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &P[i]);
   ~~~~~^~~~~~~~~~~~~
2014_ho_t2.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &C[j], &E[j]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 4 ms 544 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 660 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 4 ms 680 KB Output is correct
10 Correct 4 ms 680 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 680 KB Output is correct
2 Correct 9 ms 680 KB Output is correct
3 Correct 9 ms 680 KB Output is correct
4 Correct 9 ms 680 KB Output is correct
5 Correct 9 ms 740 KB Output is correct
6 Correct 3 ms 740 KB Output is correct
7 Correct 8 ms 740 KB Output is correct
8 Correct 11 ms 740 KB Output is correct
9 Correct 3 ms 740 KB Output is correct
10 Correct 9 ms 748 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 4 ms 544 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 660 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 4 ms 680 KB Output is correct
10 Correct 4 ms 680 KB Output is correct
11 Correct 9 ms 680 KB Output is correct
12 Correct 9 ms 680 KB Output is correct
13 Correct 9 ms 680 KB Output is correct
14 Correct 9 ms 680 KB Output is correct
15 Correct 9 ms 740 KB Output is correct
16 Correct 3 ms 740 KB Output is correct
17 Correct 8 ms 740 KB Output is correct
18 Correct 11 ms 740 KB Output is correct
19 Correct 3 ms 740 KB Output is correct
20 Correct 9 ms 748 KB Output is correct
21 Correct 10 ms 748 KB Output is correct
22 Correct 9 ms 748 KB Output is correct
23 Correct 10 ms 748 KB Output is correct
24 Correct 10 ms 748 KB Output is correct
25 Correct 9 ms 748 KB Output is correct
26 Correct 9 ms 748 KB Output is correct
27 Correct 4 ms 748 KB Output is correct
28 Correct 9 ms 748 KB Output is correct
29 Correct 10 ms 748 KB Output is correct
30 Correct 10 ms 748 KB Output is correct