Submission #1005336

---

Source Code Expand

//ビームサーチ
#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <algorithm>
#define int long long
using namespace std;

int n;
int a[20000];
int power[17];

void randomSuffle() {
	static bool used[20000] = {false};
	static int b[20000];
	int t;
	
	for (int i = 0; i < n; i++) {
		do {
			t = rand() % n;
		} while (used[t]);
		
		used[t] = true;
		b[i] = a[t];
	}
	for (int i = 0; i < n; i++) {
		a[i] = b[i];
	}
}

signed main() {
	int i, j, k, l;
	
	power[0] = 1;
	for (i = 1; i < 17; i++) { power[i] = power[i - 1] * 10; }
	
	cin >> n;
	for (i = 0; i < n; i++) { cin >> a[i]; }
	randomSuffle();

	//ビームサーチ(商品1から順に選ぶ, 選ばない, をする)
	//「mod 10^k == x」のもののうち, width個だけを"適当に"採用。
	//状態は：「金額」で持てばよい。
	
	int WIDTH = 50 * 5000 / n;
	static vector<int> states[2][10];
	int ans = 0;
	
	for (i = 0; i < 17; i++) {
		for (j = 0; j < 10; j++) states[0][j].clear();
		states[0][0].push_back(0);
		
		for (j = 0; j < n; j++) {
			for (k = 0; k < 10; k++) {	//mod 10^i == k
				for (l = 0; l < states[0][k].size(); l++) {
					int money = a[j] + states[0][k][l];
					int mod = (money / power[i]) % 10;
					states[1][k].push_back(states[0][k][l]);
					states[1][mod].push_back(money);
				}
			}
			
			for (k = 0; k < 10; k++) { states[0][k].clear(); }
			for (k = 0; k < 10; k++) {
				for (l = 0; l < min(WIDTH, (int)states[1][k].size()); l++) {
					states[0][k].push_back(states[1][k][l]);
				}
			}
			for (k = 0; k < 10; k++) {
				states[1][k].clear();
			}
		}
		
		for (j = 9; j >= 0; j--) { if (states[0][j].size() > 0) { break; } }
		ans += j;
	}
	
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result