제출 #1317777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317777		tuncay_pasha	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	332 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int dp[N][N];
signed main(){
  int n;
  cin >> n;
  vector < int > a(n + 1);
  for(int i = 1; i <= n; ++i)
    cin >> a[i];
  vector<int> pre(n + 1, 0);
  for (int i = 1; i <= n; ++i){
    pre[i] = pre[i - 1] + a[i];
  }
  for (int i = 1; i <= n; ++i){
    dp[i][0] = 1;
  }
  for (int i = 1; i <= n; ++i){
    for (int j = 0; j < i; ++j){
      int sum1 = pre[i] - pre[j];
      for (int k = 0; k < j; ++k){
        int sum2 = pre[j] - pre[k];
        if (sum1 < sum2){
          continue;
        }
        dp[i][j] = max(dp[i][j], dp[j][k] + 1);
      }
    }
  }
  int res = 0;
  for (int i = 0; i < n; ++i) {
    res = max(res, dp[n][i]);
  }
  cout << res << '\n';
  
  // dp[i][j] -> solve(1, j) + [j + 1; i]
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27