제출 #1003533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003533		hyakup	Cigle (COI21_cigle)	C++17	100 / 100	111 ms	67436 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;

const int maxn = 5e3 + 10;
const int maxm = 1e7;

int dp[maxn][maxn], v[maxn], suf[maxn];

int main(){
  int n; cin >> n;
  for( int i = 1; i <= n; i++ ) cin >> v[i];
  int resp = 0;
  for( int j = n - 1; j >= 1; j-- ){
    // bug(j);
    // for( int k = 0; k <= n; k++ ) cout << dp[j][k] << " "; cout << endl;
    for( int k = n; k > j; k-- ) suf[k] = max( dp[j][k], suf[k + 1] );
    int k = j + 1, cont = 0;
    int sumL = 0, sumR = v[k];
    int pref = dp[j][k];
    for( int i = j - 1; i >= 0; i-- ){
      // bug(i);
      // bug(sumL);
      while( k < n && sumR <= sumL ){
        if( sumL == sumR ) cont++;
        sumR += v[++k];
        pref = max( pref, dp[j][k] + cont );
      }
      // bug(k) ;
      // bug(sumR);
      // bug(cont);

      dp[i][j] = max( pref, suf[k + 1] + cont );
      resp = max( resp, dp[i][j] );
      sumL += v[i + 1];
    }
  }
  cout << resp << endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52