Code c++ Bài Vòng tròn số trong Đề thi OLP Miền Trung Tây Nguyên bảng Không chuyên vòng chung kết năm 2023

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)


const int INF = 1e9 , mod = 1e9 + 7;

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }

typedef long long ll;
typedef double db;
const int N = 2e3 + 5;

ll dp[N][N][3], a[N];
int n , k;
void readip(){
    cin >> n >> k;
    FOR(i, n) cin >> a[i];
    memset(dp, -0x3f, sizeof dp);
}

void solve(){
    FOR(i, 3) dp[0][0][i] = 0;
    REP(i, 1, n){
        FOR(j, i) FOR(t, 3){
            maximize(dp[i][j][t], dp[i-1][j][t]);
            ll val = dp[i-1][j][t];
            if ((t+1) % 3 == 1) val -= a[i - 1];
            else val += a[i - 1];
            maximize(dp[i][j+1][(t+1)%3], val);
        }
    }
    ll res = -1e18;
    FOR(i, 3) maximize(res, dp[n][3*k][i]);
    cout << res;
}

int main(){

        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        freopen("b.inp","r",stdin);
        freopen("b.out","w",stdout);

        readip();
        solve();

}