Submission #1312036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312036		thuhienne	Shopping Plans (CCO20_day2problem3)	C++20	20 / 25	186 ms	56872 KiB

Main

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

using ll = long long;

#define re exit(0);

#define int ll

const int maxn = 200009;

int n,m,k;
ll def;

vector <int> good[maxn];
int sl[maxn];
pair <int,int> lim[maxn];

vector <ll> print;

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

temptation moveon(int type,ll cost) {
	type++;
	return {type,lim[type].first + 1,1,sl[type] + 1,cost + good[type][lim[type].first + 1] - good[type][lim[type].first]};
}

void djt() {
	priority_queue <temptation> pq;
	
	ll temp = 0;
	for (int i = 1;i <= m;i++) {
		for (int j = 1;j <= lim[i].first;j++) temp += good[i][j];
	}
	print.push_back(temp);
	
	pq.push(moveon(0,temp));
	
	while (pq.size()) {
		if (print.size() >= k) break;
		
		int type = pq.top().type,
			currpos = pq.top().currpos,
			use = pq.top().use,
			lastpos = pq.top().lastpos;
		ll cost = pq.top().cost;
		
		pq.pop();
		
		print.push_back(cost);
		
		if (type < m) {
			//chuyen sang
//			move(type + 1);
			pq.push(moveon(type,cost));
			//undo
			if (use == 1 && currpos == lim[type].first + 1) {
				pq.push(moveon(type,cost - good[type][lim[type].first + 1] + good[type][lim[type].first]));
			}
		}
		
		//tang currpos len 1
		if (currpos + 1 < lastpos) {
			pq.push({type,currpos + 1,use,lastpos,cost + good[type][currpos + 1] - good[type][currpos]});
		}
		
		//fixed pos va tang 1 thang nao do len
		if (use <= lim[type].first - 1) {
			//lay thang o vi tri lim[type].first - use va tang len 1
			int nextmove = lim[type].first - use;
			pq.push({type,nextmove + 1,use + 1,currpos,cost + good[type][nextmove + 1] - good[type][nextmove]});
		} else if (use + 1 <= lim[type].second && currpos != 1) {
			//them thang o 1
			pq.push({type,1,use + 1,currpos,cost + good[type][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";
	
}

struct Group {
	int soluong;
	pair <int,int> limit;
	vector <int> A;
	bool operator < (const Group & other) {
		return A[A.back() + 1] - A[A.back()] < other.A[A.back() + 1] - other.A[A.back()];
	}
} temp[maxn];

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

	cin >> n >> m >> k;
	
	for (int i = 1;i <= m;i++) good[i].push_back(0);
	for (int i = 1;i <= n;i++) {
		int a,c;cin >> a >> c;
		good[a].push_back(c);
		sl[a]++;
	}
	for (int i = 1;i <= m;i++) {
		cin >> lim[i].first >> lim[i].second;
		lim[i].second = min(lim[i].second,sl[i]);
		
		sort(good[i].begin(),good[i].end());
	}
	
	//handle all -1 case and constant case
	for (int i = 1;i <= m;i++) {
		
		if (lim[i].first > lim[i].second) {
			for (int j = 1;j <= k;j++) cout << -1 << '\n';
			re;
		}
		
		if (sl[i] == lim[i].first || lim[i].second == 0) {
			for (int j = 1;j <= lim[i].first;j++) def += good[i][j];
			
			swap(good[i],good[m]);
			swap(sl[i],sl[m]);
			swap(lim[i],lim[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++) {
		good[i].push_back(lim[i].first);
		
		temp[i] = {sl[i],lim[i],good[i]};
	}
	sort(temp + 1,temp + 1 + m);
	for (int i = 1;i <= m;i++) {
		sl[i] = temp[i].soluong;
		lim[i] = temp[i].limit;
		good[i] = temp[i].A;
		
		good[i].pop_back();
	}
	
	djt();

}

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