1582E - Pchelyonok and Segments - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define float long double
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("Ofast")
#ifndef ONLINE_JUDGE
#include "dbg.hpp"
#else
#define debug(...) 8
#endif
int a[(int)1e5+10],pre[(int)1e5+10];
int dp[(int)1e5+10][460];
void solve(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    pre[i]=pre[i-1]+a[i];
  }
  // memset(dp,0,sizeof(dp));
  // debug(pre);
  int k=0,ans=0;
  while((k*(k+1))/2<=n) k++;
  debug(k);
  // int dp[n+5][k+5]={};
  for(int i=1;i<k;i++){
    dp[n+1][i]=-1e9+10;
  }
  int ok=10;
  dp[n+1][0]=1e9+10;
  for(int i=n;i;i--){
    for(int j=0;j<k;j++){
      int ans = dp[i+1][j];//fun(idx+1,k);
      if(j>0 && i+j-1<=n && pre[i+j-1]-pre[i-1]<dp[i+j][j-1]){
        ans = max(ans,pre[i+j-1]-pre[i-1]);
      }
      dp[i][j]=ans;
    }
  }
  for(int i=0;i<k;i++){
    if(dp[1][i]>0){
      ans=i;
    }
  }
  cout<<ans<<'\n';
}

signed main() { 
   #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
      solve();
    }
}