Submission #11111

#	Time	Username	Problem	Language	Result	Execution time	Memory
11111		ainta	Sequence (BOI14_sequence)	C++98	100 / 100	384 ms	2148 KiB

sequence

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long Res = 99999999999999999LL;
void Do(int Num, vector<int>w, int p, int ck){
	int i, n = w.size(), j;
	if (p > 1000000)return;
	if (n == 1){
		if (ck){
			if (w[0] == 0)Res = min(Res, (long long)Num);
			return;
		}
		int tt;
		long long S = Num, P = p;
		if (w[0] & 1){
			for (i = 1; i<10; i++){
				if ((1 << i)&w[0])break;
			}
			tt = i;
			if (tt == 10){
				S += P * 10;
			}
			else{
				for (i = 9; i >= 1; i--){
					if ((1 << i)&w[0]){
						if (tt == i)P *= 10;
						S += P*i;
						P *= 10;
					}
				}
			}
		}
		else{
			for (i = 9; i >= 0; i--){
				if ((1 << i)&w[0]){
					S += P*i;
					P *= 10;
				}
			}
		}
		if (S * 10 < p) S += p;
		Res = min(Res, S);
		return;
	}
	vector<int>R((n - 1) / 10 + 1);
	if (Num * 10 >= p){
		for (j = 0; j < n; j++){
			if (j)R[j / 10] |= w[j] & ~(1 << (j % 10));
			else R[j / 10] |= w[j];
		}
		Do(Num, R, -1, 1);
	}
	if (ck)return;
	for (i = 0; i < 10; i++){
		vector<int>R((n - 1 + i) / 10 + 1);
		for (j = 0; j < n; j++){
			R[(i + j) / 10] |= w[j] & ~(1 << ((i + j) % 10));
		}
		Do(Num + i*p, R, p * 10, 0);
	}
}
int main()
{
	int i, n;
	scanf("%d", &n);
	vector<int>L(n);
	for (i = 0; i < n; i++){
		scanf("%d", &L[i]);
		L[i] = 1 << L[i];
	}
	Do(0, L, 1, 0);
	printf("%lld\n", Res);
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33