oj.uz

Submission #20839

# Submission time Handle Problem Language Result Execution time Memory
20839 2017-02-25T12:59:44 Z kdh9949 만두 팔기 (JOI14_manju) C++14
100 / 100
 36 ms 41536 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, a[10010], b[505], c[505], dp[505][20010], ans;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", a + i);
	for(int i = 1; i <= m; i++) scanf("%d%d", c + i, b + i);
	fill(dp[0] + 1, dp[0] + n + 10001, 1e9);
	for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n + 10000; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= c[i]) dp[i][j] = min(dp[i][j], dp[i - 1][j - c[i]] + b[i]);
		}
	}
	for(int i = n + 9999; i >= 1; i--) dp[m][i] = min(dp[m][i], dp[m][i + 1]);
	sort(a + 1, a + n + 1, greater<int>());
	for(int i = 1; i <= n; i++){
		a[i] += a[i - 1];
		ans = max(ans, a[i] - dp[m][i]);
	}
	printf("%d\n", ans);
}

Compilation message

t2.cpp: In function 'int main()':
t2.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
t2.cpp:8:48: 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", a + i);
                                                ^
t2.cpp:9:57: 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%d", c + i, b + i);
                                                         ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41536 KB Output is correct
2 Correct 0 ms 41536 KB Output is correct
3 Correct 3 ms 41536 KB Output is correct
4 Correct 0 ms 41536 KB Output is correct
5 Correct 3 ms 41536 KB Output is correct
6 Correct 0 ms 41536 KB Output is correct
7 Correct 0 ms 41536 KB Output is correct
8 Correct 0 ms 41536 KB Output is correct
9 Correct 3 ms 41536 KB Output is correct
10 Correct 3 ms 41536 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41536 KB Output is correct
2 Correct 33 ms 41536 KB Output is correct
3 Correct 23 ms 41536 KB Output is correct
4 Correct 19 ms 41536 KB Output is correct
5 Correct 36 ms 41536 KB Output is correct
6 Correct 16 ms 41536 KB Output is correct
7 Correct 26 ms 41536 KB Output is correct
8 Correct 26 ms 41536 KB Output is correct
9 Correct 16 ms 41536 KB Output is correct
10 Correct 26 ms 41536 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41536 KB Output is correct
2 Correct 13 ms 41536 KB Output is correct
3 Correct 19 ms 41536 KB Output is correct
4 Correct 16 ms 41536 KB Output is correct
5 Correct 29 ms 41536 KB Output is correct
6 Correct 26 ms 41536 KB Output is correct
7 Correct 6 ms 41536 KB Output is correct
8 Correct 16 ms 41536 KB Output is correct
9 Correct 26 ms 41536 KB Output is correct
10 Correct 13 ms 41536 KB Output is correct