记录编号	596205	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO24 Open Silver]Bessie’s Interview	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	2.078 s
提交时间	2024-10-23 17:22:26	内存使用	11.97 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 300010
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	ll st,ed,id;
}pnt[MAXN];
bool cmp(node a,node b){
	return a.ed<b.ed;
}
ll n,k,ans_t;
ll t[MAXN],ans[MAXN];
priority_queue<ll> f;
priority_queue<ll,vector<ll>,greater<ll> > q;
map <ll,bool> used,ins;
pair <ll,ll> find(ll x){
	ll ans1=0,ans2=0;
	ll l=0,r=n;
	while(l<r){
		ll mid=(l+r)/2;
		if(pnt[mid].ed<x)l=mid+1;
		else r=mid;
	}
	ans1=l;
	l=0,r=n;
	while(l<r){
		ll mid=(l+r+1)/2;
		if(pnt[mid].ed<=x)l=mid;
		else r=mid-1;
	}
	ans2=l;
	return make_pair(ans1,ans2);
}
int main(){
	freopen("interview.in","r",stdin);
	freopen("interview.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		pnt[i].id=i;
		t[i]=read();
		if(i<=k){
			q.push(t[i]);
			pnt[i].ed=t[i],pnt[i].st=0;
		}else{
			pnt[i].st=q.top();
			q.pop();
			pnt[i].ed=pnt[i].st+t[i];
			q.push(pnt[i].ed);
		}
	}
	ans_t=q.top();
	f.push(q.top());
	sort(pnt+1,pnt+1+n,cmp);
//	for(int i=1;i<=n;i++)cout<<pnt[i].st<<" "<<pnt[i].ed<<endl;
	while(!f.empty()){
		ll tp=f.top();
		f.pop();
		if(used[tp])continue;
		used[tp]=1;
		pair <ll,ll> now=find(tp);
//		cout<<tp<<" "<<now.first<<" "<<now.second<<endl;
		for(int i=now.first;i<=now.second;i++){
			if(pnt[i].id<=k)ans[pnt[i].id]=1;
			if(!used[pnt[i].st]&&!ins[pnt[i].st]){
				f.push(pnt[i].st);
				ins[pnt[i].st]=1;
			}
		}
	}
	cout<<ans_t<<endl;
	for(int i=1;i<=k;i++){
		if(ans[i])cout<<"1";
		else cout<<"0";
	}
	return 0;
}