oj.uz

답안 #39683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39683 2018-01-17T06:59:48 Z 14kg 만두 팔기 (JOI14_manju) C++11
100 / 100
 163 ms 25660 KB 
#include <stdio.h>
#include <algorithm>
#define min2(x,y) (x<y?x:y)

using namespace std;
struct BOX {
	int cnt, value;
} box[501];
int n, m, in[10001], p[10001];
int dp[501][10001];
bool check[501][10001];

int max2(int x, int y) { return x > y ? x : y; }
int f(int x, int y) {
	if (x == 0 || y == 0) return 0;
	if (!check[x][y]) {
		check[x][y] = true;
		int cnt = min2(y, box[x].cnt);
		dp[x][y] = max2(f(x - 1, y), f(x - 1, y - cnt) + p[y] - p[y - cnt] - box[x].value);
	} return dp[x][y];
}
int main() {
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= m; i++) scanf("%d", &in[i]);
	for (int i = 1; i <= n; i++) scanf("%d %d", &box[i].cnt, &box[i].value);

	sort(in + 1, in + m + 1);
	for (int i = 1; i <= m; i++) p[i] = p[i - 1] + in[i];
	printf("%d", f(n, m));
}

Compilation message

t2.cpp: In function 'int main()':
t2.cpp:23:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &m, &n);
                        ^
t2.cpp:24:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= m; i++) scanf("%d", &in[i]);
                                                  ^
t2.cpp:25:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%d %d", &box[i].cnt, &box[i].value);
                                                                         ^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 25660 KB Output is correct
2 Correct 0 ms 25660 KB Output is correct
3 Correct 0 ms 25660 KB Output is correct
4 Correct 3 ms 25660 KB Output is correct
5 Correct 0 ms 25660 KB Output is correct
6 Correct 0 ms 25660 KB Output is correct
7 Correct 0 ms 25660 KB Output is correct
8 Correct 0 ms 25660 KB Output is correct
9 Correct 0 ms 25660 KB Output is correct
10 Correct 0 ms 25660 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 25660 KB Output is correct
2 Correct 9 ms 25660 KB Output is correct
3 Correct 26 ms 25660 KB Output is correct
4 Correct 19 ms 25660 KB Output is correct
5 Correct 19 ms 25660 KB Output is correct
6 Correct 9 ms 25660 KB Output is correct
7 Correct 9 ms 25660 KB Output is correct
8 Correct 23 ms 25660 KB Output is correct
9 Correct 9 ms 25660 KB Output is correct
10 Correct 19 ms 25660 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 25660 KB Output is correct
2 Correct 153 ms 25660 KB Output is correct
3 Correct 133 ms 25660 KB Output is correct
4 Correct 139 ms 25660 KB Output is correct
5 Correct 146 ms 25660 KB Output is correct
6 Correct 143 ms 25660 KB Output is correct
7 Correct 16 ms 25660 KB Output is correct
8 Correct 163 ms 25660 KB Output is correct
9 Correct 123 ms 25660 KB Output is correct
10 Correct 149 ms 25660 KB Output is correct