제출 #1326260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326260		aren_dance	Tricks of the Trade (CEOI23_trade)	C++20	5 / 100	8092 ms	6260 KiB

trade

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+1;
ll c[N];
ll s[N];
void upsolve(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		cin>>c[i];
	}
	for(int i=1;i<=n;++i){
		cin>>s[i];
	}
	vector<int> a(n+1,0);
	ll answ=-1e18;
	int l,r;
	vector<int> an(n+1,0);
	for(int i=1;i<=n;++i){
		multiset<ll> st;
		ll cur=0ll;
		for(int j=i;j<=n;++j){
			cur-=c[j];
			if(st.size()<k){
				st.insert(s[j]);
				cur+=s[j];
			}
			else{
				if(*st.begin()<s[j]){
					cur-=*st.begin();
					st.erase(st.begin());
					st.insert(s[j]);
					cur+=s[j];
				}
			}
			if(st.size()==k){
				if(answ<cur){
					answ=cur;
					for(int e=1;e<=n;++e){
						an[e]=0;
					}
					vector<pair<ll,int>> o;
					for(int e=i;e<=j;++e){
						o.push_back({s[e],e});
					}
					sort(o.rbegin(),o.rend());
					for(int e=0;e<k;++e){
						an[o[e].second]=1;
					}
				}
				if(answ==cur){
					vector<pair<ll,int>> o;
					for(int e=i;e<=j;++e){
						o.push_back({s[e],e});
					}
					sort(o.rbegin(),o.rend());
					for(int e=0;e<k;++e){
						an[o[e].second]=1;
					}
				}
			}
		}
	}
	cout<<answ<<'\n';
	for(int i=1;i<=n;++i){
		cout<<an[i];
	}
}
int main()
{
	int t;
	t=1;
	while(t--){
		upsolve();
	}
	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45