Submission #153818

#	Time	Username	Problem	Language	Result	Execution time	Memory
153818		songc	만두 (JOI14_ho_t2)	C++14	100 / 100	20 ms	636 KiB

2014_ho_t2

#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] = T[j];
	}
	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 (stderr)

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: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40