Submission #1241865

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)



string A;
int dp[1010][2];
//-----------------------------------------------------------------------------------
int main() {
    cin >> A;
    reverse(A.begin(), A.end());

    rep(i, 0, 1010) rep(j, 0, 2) dp[i][j] = -1;
    dp[0][0] = 0;

    int n = A.length();
    rep(i, 0, n) rep(j, 0, 2) rep(k, 0, 10) if(0 <= dp[i][j]) {
        int c = A[i] - '0';

        int sm = c + k + j;

        int up = sm / 10;
        int down = sm % 10;

        if (k == down && down == c) dp[i + 1][up] = max(dp[i + 1][up], dp[i][j] + 1);
        else dp[i + 1][up] = max(dp[i + 1][up], dp[i][j]);
    }

    printf("%d\n", max(dp[n][0], dp[n][1]));
}

Submission Info

Judge Result