TNOJ 333 畢業 ( DP )

TNFSH Online Judge
應該很容易看出來，只有兩個狀態要維護，一個是即將扣學分的狀態和即將加學分的狀態，由左到右一一更新，O( N )。問題是數據規模到千萬，如果單純用scanf會TLE。。原來面對更大的數據時，簡單優化過的cin, cout 會更快是真的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 7;
typedef long long ll;
const ll INFL = 1e16;

int N;
int S[ MAXN ];

void solve(){
    ll dp0 = 0, dp1 = -INFL;
    for( int i = 0; i < N; ++i ){
        ll d0 = dp0, d1 = dp1;
        dp0 = max( dp0, d1 - S[ i ] );
        dp1 = max( dp1, d0 + S[ i ] );
    }
    cout << max( dp0, dp1 ) << "\n"; // printf( "%lld\n", max( dp0, dp1 ) );
}

int main(){
    ios::sync_with_stdio( false ); cin.tie( 0 );
    cin >> N; // scanf( "%d", &N );
    for( int i = 0; i < N; ++i )
        cin >> S[ i ]; // scanf( "%d", S + i );
    solve();
    return 0;
}