oj.uz

Submission #15959

# Submission time Handle Problem Language Result Execution time Memory
15959 2015-08-02T13:11:52 Z myungwoo Sequence (BOI14_sequence) C++14
9 / 100
 1000 ms 11204 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;

int N;
int A[MAXN];
lld ans = 12345678900000;

void dfs(lld n, lld v, vector<int> &arr)
{
	if (arr.empty() && ans > v){ ans = v; return; }
	if (v+n >= ans) return;
	vector <int> nxt[10];
	for (int i=0;i<10;i++){
		lld m = v + i*n;
		for (int p: arr){
			lld now = m + p;
			bool sw = 0;
			for (lld tmp=now;tmp;tmp/=10) if (tmp%10 == A[p]){ sw = 1; break; }
			if (!sw) nxt[i].pb(p);
		}
	}
	vector <int> tmp;
	for (int i=0;i<10;i++) tmp.pb(i);
	sort(all(tmp), [nxt](const int &a, const int &b){
		return sz(nxt[a]) < sz(nxt[b]);
	});
	for (int d: tmp){
		dfs(n*10, v + d*n, nxt[d]);
	}
}

int main()
{
	scanf("%d", &N);
	for (int i=0;i<N;i++) scanf("%d", A+i);
	vector <int> tmp;
	for (int i=0;i<N;i++) tmp.pb(i);
	dfs(1, 0, tmp);
	printf("%lld\n", ans);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 10 ms 2252 KB Output is correct
3 Correct 0 ms 2124 KB Output is correct
4 Correct 7 ms 2124 KB Output is correct
5 Correct 1 ms 2124 KB Output is correct
6 Correct 0 ms 2124 KB Output is correct
7 Correct 61 ms 2124 KB Output is correct
8 Correct 27 ms 2384 KB Output is correct
9 Correct 0 ms 2124 KB Output is correct
10 Correct 65 ms 2340 KB Output is correct
11 Correct 5 ms 2300 KB Output is correct
12 Correct 5 ms 2124 KB Output is correct
13 Correct 9 ms 2124 KB Output is correct
14 Correct 33 ms 2320 KB Output is correct
15 Correct 17 ms 2320 KB Output is correct

Subtask #2
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 17 ms 2252 KB Output is correct
3 Correct 0 ms 2124 KB Output is correct
4 Correct 7 ms 2124 KB Output is correct
5 Correct 0 ms 2124 KB Output is correct
6 Correct 0 ms 2124 KB Output is correct
7 Correct 379 ms 2384 KB Output is correct
8 Correct 60 ms 2124 KB Output is correct
9 Correct 46 ms 2384 KB Output is correct
10 Correct 0 ms 2124 KB Output is correct
11 Execution timed out 1000 ms 2492 KB Program timed out
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Execution timed out 1000 ms 5360 KB Program timed out
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 15 ms 2252 KB Output is correct
3 Correct 0 ms 2124 KB Output is correct
4 Correct 7 ms 2124 KB Output is correct
5 Execution timed out 1000 ms 11204 KB Program timed out
6 Halted 0 ms 0 KB -