Cherchez vol 2 - Suma - pag 194(ONI 2005) - 90 puncte

#include <bits/stdc++.h>
// http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=683

using namespace std;

ifstream fin("suma2.in");
ofstream fout("suma2.out");

inline void max_self(int& a, int b) {
    a = max(a, b);
}

int main() {
    int N;
    fin >> N;
    int M = N;
    vector < int > a;
    a.push_back(0);
    while(N--) {
        string s;
        fin >> s;
        for(int i = 0; i < (int)s.size(); ++i)
            a.push_back(s[i] - '0');
    }
    N = a.size() - 1;
    vector < vector < int > > dp(4, vector < int >(M + 1, -1));
    dp[1][1] = a[1];
    dp[2][1] = a[1] * 10 + a[2];
    if(a[2])
        dp[2][2] = a[1] + a[2];
    dp[3][1] = a[1] * 100 + a[2] * 10 + a[3];
    if(a[3])
         max_self(dp[3][2], a[1] * 10 + a[2] + a[3]);
    if(a[2] && a[3])
        dp[3][3] = a[1] + a[2] + a[3];
    for(int i = 4; i <= N; ++i) {
        int DIM = min(i, M);
        for(int j = 2; j <= DIM; ++j) {
            if(a[i] > 0 && dp[(i - 1) % 4][j - 1] != -1)
                max_self(dp[i % 4][j], dp[(i - 1) % 4][j - 1] + a[i]);
            if(a[i - 1] > 0 && dp[(i - 2) % 4][j - 1] != -1)
                max_self(dp[i % 4][j], dp[(i - 2) % 4][j - 1] + a[i - 1] * 10 + a[i]);
            if(a[i - 2] > 0 && dp[(i - 3) % 4][j - 1] != -1)
                max_self(dp[i % 4][j], dp[(i - 3) % 4][j - 1] + a[i - 2] * 100 + a[i - 1] * 10 + a[i]);
        }
    }
    fout << dp[N % 4][M];
}