C. Bugged [AtCoder Beginner Contest 063 / AtCoder Regular Contest 075]

http://arc075.contest.atcoder.jp/tasks/arc075_a

解法

http://arc075.contest.atcoder.jp/submissions/1322929
DPで解く
dp[i][j] := i個までの問題を使って、合計得点をj点にできるか
これを構築して、あとは、作れる得点の中で10の倍数でない最大の物を答える

int N, A[101010];
int dp[101][10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    
    dp[0][0] = 1;
    rep(i, 0, N) rep(j, 0, 10001) if(dp[i][j]) {
        dp[i + 1][j] = 1;
        dp[i + 1][j + A[i]] = 1;
    }
 
    int ans = 0;
    rep(j, 0, 10001) if (j % 10 && dp[N][j]) ans = max(ans, j);
    cout << ans << endl;
}