oj.uz

Submission #153815

# Submission time Handle Problem Language Result Execution time Memory
153815 2019-09-16T14:39:41 Z songc None (JOI14_ho_t2) C++14
35 / 100
 20 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, ans;
int S[10101];
int D[20202], T[20202];

int main(){
	scanf("%d %d", &M, &N);
	for (int i=1; i<=20000; i++) D[i] = T[i] = (1<<30);
	for (int i=1; i<=M; i++) scanf("%d", &S[i]);
	sort(S+1, S+M+1, greater<int>());
	for (int i=1; i<=M; i++) S[i] += S[i-1];
	for (int i=1; i<=N; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		for (int j=0; j+x<=20000; j++) T[j+x] = min(D[j+x], D[j]+y);
		for (int j=0; j<=20000; j++) D[j+x] = T[j+x];
	}
	for (int j=19999; j>0; j--) D[j] = min(D[j], D[j+1]);
	for (int i=1; i<=M; i++) ans = max(ans, S[i]-D[i]);
	printf("%d\n", ans);
	return 0;
}

Compilation message

2014_ho_t2.cpp: In function 'int main()':
2014_ho_t2.cpp:11: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:13:32: 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", &S[i]);
                           ~~~~~^~~~~~~~~~~~~
2014_ho_t2.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 632 KB Output is correct
2 Correct 19 ms 632 KB Output is correct
3 Correct 20 ms 632 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 18 ms 504 KB Output is correct
6 Correct 18 ms 504 KB Output is correct
7 Correct 17 ms 508 KB Output is correct
8 Correct 18 ms 504 KB Output is correct
9 Correct 17 ms 504 KB Output is correct
10 Correct 18 ms 504 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -