Submission #996209

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;


int main() {
	long long int N;
	cin >> N;
	vector<long long int>A( N );
	for( size_t i = 0; i < N; i++ ) {
		cin >> A[i];
	}
	long long int x = 1, ans = 0;
	while( true ) {
		vector<long long int>DP( 10, LLONG_MIN / 6 );
		DP[0] = 0;
		long long int maxx = 0;
		for( size_t i = 0; i < N; i++ ) {
			auto dp = DP;
			for( size_t j = 0; j < 10; j++ ) {
				if( dp[j] >= 0 ) {
					long long int next = dp[j] + A[i];
					long long int nextidx = (next / x) % 10;
					DP[nextidx] = max( DP[nextidx], next % (x * 100) );
					maxx = max( nextidx, maxx );
				}
			}
		}
		if( maxx == 0 ) {
			break;
		} else {
			ans += maxx;
		}
		for( size_t i = 0; i < 10; i++ ) {
			//cout << DP[i] << " ";
		}
		//cout << endl;
		x *= 10;
	}
	cout << ans << endl;
}

Submission Info

Judge Result