Submission #32737026

---

Source Code Expand

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int MN=1e6+5;
vector<int>f[MN];
int C[10];

bool cmp(int x,int y){
	int s=0,t=0;
	for(int i=1;i<=9;i++)s+=f[x][i],t+=f[y][i];
	if(s<t)return 0;
	if(s>t)return 1;
	for(int i=9;i>=1;i--){
		if(f[x][i]>f[y][i])return 1;
		if(f[x][i]<f[y][i])return 0;
	}
	return 1;
}

void print(vector<int>vec){
	for(int i=9;i>=1;i--){
		for(int k=1;k<=vec[i];k++)cout<<i;
	}
	puts("");
}

signed main(void){

	int N=read();
	for(int i=1;i<=9;i++)C[i]=read();
	for(int i=0;i<=N+1;i++)f[i].resize(10);
	for(int i=1;i<=N;i++){
		for(int j=1;j<=9;j++){
			if(i<C[j])continue;
			f[i-C[j]][j]++;
			if(cmp(i-C[j],i))f[i]=f[i-C[j]];
			f[i-C[j]][j]--;
		}
		if(cmp(i,N+1))f[N+1]=f[i];
	}
	for(int i=9;i>=1;i--){
		for(int k=1;k<=f[N+1][i];k++)cout<<i;
	}
	puts("");

	return 0;
}

Submission Info

Judge Result