Submission #1287358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287358		kerem	만두 (JOI14_ho_t2)	C++20	100 / 100	10 ms	580 KiB

2014_ho_t2

#include <bits/stdc++.h>
using namespace std;
//~ #define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 1000
#define inf (int)1e9
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

void solve(){
	int n,m;
	cin >> m >> n;
	int p[m+1],box[n][2];
	for(int i=1;i<=m;i++)
		cin >> p[i];
	for(int i=0;i<n;i++)
		cin >> box[i][0] >> box[i][1];
		
	sort(p+1,p+m+1,greater<int>());
	int cost[m+1]={0};
	for(int i=1;i<=m;i++)
		cost[i]=cost[i-1]+p[i];
	int dp[m+1]={0};
	for(int i=1;i<=m;i++)
		dp[i]=inf;
	for(int i=0;i<n;i++){
		for(int j=m-1;j>=0;j--){
			if(dp[j]==inf) continue;
			if(j+box[i][0]>m)
				dp[m]=min(dp[m],dp[j]+box[i][1]);
			else
				dp[j+box[i][0]]=min(dp[j+box[i][0]],dp[j]+box[i][1]);
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++)
		ans=max(ans,cost[i]-dp[i]);
	cout << ans << endl;
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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