제출 #1311774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311774		thuhienne	Shopping Plans (CCO20_day2problem3)	C++20	15 / 25	101 ms	20660 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

int n,m,k;

vector <int> good[200009];
pair <int,int> lim[200009];

ll def;
vector <ll> print;

struct temptation {
	int type,pos;
	ll cost;
	const bool operator < (const temptation & other) const {
		return cost > other.cost;
	}
};

void djt() {
	priority_queue <temptation> pq;
	
	ll temp = 0;
	for (int i = 1;i <= m;i++) {
		temp += good[i][0];
	}
	
	print.push_back(temp);
	
	pq.push({1,2,temp + good[1][1] - good[1][0]});
	
	while (pq.size()) {
		if (print.size() >= k) break;
		
		int type = pq.top().type,pos = pq.top().pos;
		ll cost = pq.top().cost;
		
		pq.pop();
		
//		cout << type << " " << pos << " " << cost << '\n';
		
		print.push_back(cost);
		
		if (type < m) {
			pq.push({type + 1,2,cost + good[type + 1][1] - good[type + 1][0]});
			if (pos == 2) pq.push({type + 1,2,cost + good[type + 1][1] - good[type + 1][0] - good[type][1] + good[type][0]});
		}
		
		if (pos < good[type].size()) {
			pq.push({type,pos + 1,cost + good[type][pos] - good[type][pos - 1]});
		}
		
	}
	
	while (print.size() < k) print.push_back(-1);
	for (int i = 0;i < k;i++) cout << (print[i] == -1 ? -1 : print[i] + def) << '\n';
	
}

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

	cin >> n >> m >> k;
	for (int i = 1;i <= n;i++) {
		int a,c;cin >> a >> c;
		good[a].push_back(c);
	}
	for (int i = 1;i <= m;i++) {
		cin >> lim[i].first >> lim[i].second;
	}
	
	for (int i = 1;i <= m;i++) {
		
		if (good[i].empty()) {
			for (int j = 1;j <= k;j++) cout << -1 << '\n';
			re;
		}
		
		if (good[i].size() == 1) {
			def += good[i][0];
			swap(good[i],good[m]);
			
			m--;
			i--;
		}
		
	}
	
	if (m == 0) {
		cout << def << '\n';
		for (int i = 1;i < k;i++) cout << -1 << '\n';
		re;
	}
	
	for (int i = 1;i <= m;i++) sort(good[i].begin(),good[i].end());
	
	sort(good + 1,good + 1 + m,[] (vector <int> & a,vector <int> & b) {
		return a[1] - a[0] < b[1] - b[0];
	});
	
//	re;
	djt();

}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5