제출 #1163475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163475		dzuizz	Akcija (COCI21_akcija)	C++20	40 / 110	152 ms	16800 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,k; cin>>n>>k;
	pair<int,int> a[n]; // (d,w)
	for(int i=0;i<n;++i)
		cin>>a[i].second>>a[i].first;

	// Subtask 2 - k=1
	if(k==1){
		sort(a,a+n);
		pair<int,int> ans={0,0};
		priority_queue<int> pq;
		for(int t=n,i=n-1;t>=1;--t){
			while(i>=0&&a[i].first>=t)
				pq.emplace(-a[i--].second);
			if(pq.size()){
				//cout<<pq.top()<<'\n';
				++ans.first;
				ans.second-=pq.top();
				pq.pop();
			}
		}
		cout<<ans.first<<" "<<ans.second<<'\n';
		return 0;
	}
	
	// Subtask 4
	sort(a,a+n);
	vector<pair<int,int>> v;
	for(int msk=0;msk<1<<n;++msk){
		int s=0,c=0;
		bool flag=1;
		for(int i=0;i<n;++i)if(msk>>i&1){
			if(a[i].first<=s) flag=0;
			++s,c+=a[i].second;
		}
		if(flag) v.emplace_back(s,c);
	}
	sort(v.begin(),v.end(),[&](const pair<int,int>&a,const pair<int,int>&b){
		return a.first==b.first?a.second<b.second:a.first>b.first;
	});
	for(int i=0;i<k;++i){
		if(i<(int)v.size())
			cout<<v[i].first<<" "<<v[i].second<<'\n';
		else
			cout<<"0 0\n";
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20