oj.uz

Submission #95321

# Submission time Handle Problem Language Result Execution time Memory
95321 2019-01-30T05:18:35 Z Retro3014 None (JOI14_ho_t2) C++17
35 / 100
 15 ms 632 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

#define INF 1000000000
#define MAX_M 10005

int N, M;
vector<int> P;
vector<pair<int, int> > B;
int DP[MAX_M+1];


int main(){
	scanf("%d%d", &M, &N);
	for(int i=0; i<M; i++){
		int x;
		scanf("%d", &x); P.push_back(x);
	}sort(P.begin(), P.end());
	for(int i=0; i<N; i++){
		int x, y;
		scanf("%d%d", &x, &y); B.push_back(make_pair(x, y));
	}
	for(int i=1; i<=M; i++) DP[i] = INF;
	for(int i=0; i<B.size(); i++){
		for(int j=M-B[i].first; j>=0; j--){
			DP[j+B[i].first] = min(DP[j+B[i].first], DP[j]+B[i].second);
		}
		int T = INF;
		for(int j=M; j>=0; j--){
			T = min(T, DP[j]); DP[j] = T;
		}
	}
	int ans = 0;
	int sum = 0;
	for(int i=1; i<=M; i++){
		sum+=P.back(); P.pop_back();
		ans = max(ans, sum-DP[i]);
	}
	printf("%d", ans);
	return 0;
}

Compilation message

2014_ho_t2.cpp: In function 'int main()':
2014_ho_t2.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<B.size(); i++){
               ~^~~~~~~~~
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:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x); P.push_back(x);
   ~~~~~^~~~~~~~~~
2014_ho_t2.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y); B.push_back(make_pair(x, y));
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
35.0 / 35.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -