Submission #995684

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
typedef long long lint;
typedef pair<long long,long long> pl;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
lint a[20010],b[20010];
lint zyo[19];
int n;
vector<pl> mer(vector<pl> a,vector<pl> b){
	vector<pl> ret;
	rep(i,b.size()) a.pb(b[i]);
	sort(a.begin(),a.end());
	lint l=0,h=0;
	rep(i,a.size()){
		if(h<a[i].fi){
			if(l>0 && h>0) ret.pb(mp(l,h));
			l=a[i].fi;h=a[i].se;
		}
		else{
			h=max(h,a[i].se);
		}
	}
	ret.pb(mp(l,h));
	return ret;
}
bool cal(int x,lint y){
	//cout<<x<<' '<<y<<endl;
	vector<pl> v;
	v.pb(mp(zyo[x]*y,zyo[x]*(y+1)));
	rep(i,n) b[i]=a[i]%zyo[x+1];
	//rep(i,n) cout<<b[i]<<' ';cout<<endl;
	rep(i,n){
		//rep(j,v.size()) printf("(%lld,%lld),",v[j].fi,v[j].se);cout<<endl;
		vector<pl> w;
		rep(j,v.size()){
			if(v[j].fi<=b[i] && b[i]<v[j].se) return true;
			//cout<<v[i].fi<<' '<<v[i].se<<endl;
			//cout<<b[i]<<endl;
			//cout<<(zyo[x+1]+v[i].fi-b[i])%zyo[x+1]<<' '<<(zyo[x+1]+v[i].se-b[i])%zyo[x+1]<<endl;
			lint z=(zyo[x+1]+v[j].se-b[i])%zyo[x+1];
			if(z<1) z+=zyo[x+1];
			w.pb(mp((zyo[x+1]+v[j].fi-b[i])%zyo[x+1],z));
		}
		v=mer(v,w);
	}
	return false;
}
int main()
{
	int out=0;
	cin>>n;
	rep(i,n) cin>>a[i];
	zyo[0]=1;rep(i,18) zyo[i+1]=zyo[i]*10;
	rep(i,18){
		int x=0;
		rep(j,10){
			if(cal(i,j)) x=max(x,j);
		}
		//cout<<x<<endl;
		out+=x;
	}
	cout<<out<<endl;
}

Submission Info

Judge Result