Submission #995592

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
long long cnt[12][10], cnt2[12][10], Ktw[12];
long long dp[1000][10000], sum = 0, power[12];
void solve(int y) {
	vector<int>vec;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < min(50LL, cnt[y][i]); j++)vec.push_back(i);
	}
	for (int i = 0; i < 500; i++) { for (int j = 0; j < 5000; j++)dp[i][j] = 0; }
	dp[0][0] = 1;
	for (int i = 0; i < vec.size(); i++) {
		for (int j = 0; j < 5000; j++) {
			if (dp[i][j] == 0)continue;
			dp[i + 1][j] = 1;
			dp[i + 1][j + vec[i]] = 1;
		}
	}
	for (int i = 0; i < 5000; i++) { if (dp[vec.size()][i] == 1)cnt2[y][i % 10] = 1; }
}
int main() {
	int n; cin >> n;
	power[0] = 1; for (int i = 1; i < 12; i++)power[i] = power[i - 1] * 10;
	for (int i = 0; i < n; i++) {
		string S; cin >> S;
		while (S.size() < 12)S = '0' + S;
		for (int j = 0; j < 12; j++) {
			cnt[11 - j][S[j] - '0']++; Ktw[11 - j] += (S[j] - '0');
		}
	}
	for (int i = 0; i < 12; i++)solve(i);
	long long maxn = 0;
	for (int i = 0; i < 12; i++) {
		int sumn = 0;
		for (int j = 0; j <= (maxn / power[i]); j++) {
			for (int k = 0; k < 10; k++) {
				if (cnt2[i][k] == 1)sumn = max(sumn, (j + k) % 10);
			}
		}
		sum += sumn;
		maxn += Ktw[i] * power[i];
	}
	cout << sum << endl;
	return 0;
}

Submission Info

Judge Result