Submission #448251

#	Time	Username	Problem	Language	Result	Execution time	Memory
448251		JovanB	만두 (JOI14_ho_t2)	C++17	100 / 100	16 ms	492 KiB

2014_ho_t2

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int INF = 1e9;
 
int dp[20005];
int a[10005];
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=n; i++){
        cin >> a[i];
	}
	sort(a+1, a+1+n);
	reverse(a+1, a+1+n);
	for(int i=1; i<=2e4; i++) dp[i] = INF;
	for(int i=1; i<=m; i++){
        int x, y;
        cin >> x >> y;
        for(int j=2e4; j>=x; j--){
            dp[j] = min(dp[j], y + dp[j-x]);
        }
	}
	for(int j=2e4-1; j>=1; j--){
        dp[j] = min(dp[j], dp[j+1]);
	}
	int res = 0;
	int sum = 0;
	for(int i=1; i<=n; i++){
        sum += a[i];
        res = max(res, sum - dp[i]);
	}
	cout << res << "\n";
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40