Submission #896236

#	Time	Username	Problem	Language	Result	Execution time	Memory
896236		MongHwa	만두 (JOI14_ho_t2)	C++17	100 / 100	641 ms	1108 KiB

2014_ho_t2

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

#define X first
#define Y second
#define INF 0x7f7f7f7f

int arr[10005], dp[10005];
pair<int, int> box[10005];
multiset<int> ms;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int m, n;
	cin >> m >> n;

	for(int i = 0; i < m; i++)
		cin >> arr[i];
	for(int i = 0; i < n; i++)
		cin >> box[i].X >> box[i].Y;

	sort(arr, arr+m, greater<>());

	fill(dp+1, dp+m+1, INF);

	for(int i = 0; i < n; i++)
	{
		ms.clear();
		for(int j = 0; j <= box[i].X; j++)
			if(m-j >= 0)
				ms.insert(dp[m-j]);
		
		for(int j = m; j >= 0; j--)
		{
			int temp = dp[j];
			dp[j] = min(dp[j], *ms.begin() + box[i].Y);
			ms.erase(ms.find(temp));
			if(j-box[i].X-1 >= 0)
				ms.insert(dp[j-box[i].X-1]);
		}
	}

	int ans = 0, sum = 0;
	for(int i = 0; i < m; i++)
	{
		sum += arr[i];
		ans = max(ans, sum-dp[i+1]);
	}

	cout << ans << '\n';
}

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