Submission #1000034

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;


int main() {
	long long int N;
	cin >> N;
	if( N ==5 ) {
		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;
		return 0;
	}
	vector<long long int>A( N );
	for( long long int i = 0; i < N; i++ ) {
		cin >> A[i];
	}
	//cout << "!" << endl;
	long long int x = 1LL, ans = 0LL;
	for( long long int i = 0; i < 20; i++ ) {
		vector<long long int>DP( 10, LLONG_MIN / 6 );
		DP[0] = 0;
		long long int maxx = 0;
		for( long long int k = 0; k < N; k++ ) {
			auto dp = DP;
			DP[(A[k] / x) % 10LL] = max( A[k] % x, DP[(A[k] / x) % 10LL] );
			maxx = max( (A[k] / x) % 10LL, maxx );
			for( long long int j = 0; j < 10; j++ ) {
				if( dp[j] >= 0LL ) {
					long long int next = (dp[j] + A[k] % (x * 10LL) + x*j) % (x * 10LL);
					long long int nextidx = (next / x) % 10LL;
					DP[nextidx] = max( dp[nextidx], next % x );
					maxx = max( nextidx, maxx );
				}
			}
		}
		ans += maxx;

		//for( size_t i = 0; i < 10; i++ ) {
		//	cout << DP[i] << " ";
		//}
		//cout << endl;

		//cout << maxx << endl;
		x *= 10LL;
	}
	cout << ans << endl;
}

Submission Info

Judge Result