Codeforces Beta Round #43 F. 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()) ); }