Codeforces Beta Round #43 F. Hercule Poirot Problem

Hercule Poirot Problem

動的計画法。i番目の列のj番目まで石を置いたときに得られる最大コイン数を覚えてく。O(nm)じゃないとTLE。cinを使うとTLE。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);

    vector<long long> T(m,0);

    for ( int i=0; i<n; i++ )
    {
        vector<long long> P(m,-10000ll*n*m);
        
        if ( i%2 == 0 )
            for ( int j=1; j<m; j++ )
                P[j] = max( P[j-1], T[j-1] );
        else
            for ( int j=m-2; j>=0; j-- )
                P[j] = max( P[j+1], T[j+1] );

        int s = 0;

        for ( int j=0; j<m; j++ )
        {
            int t;
            scanf("%d",&t);
            s += t;
            T[j] = P[j]+s;
        }       
    }

    printf( "%lld\n", *max_element(T.begin(),T.end()) );
}