Submission #3780283

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VRSORT(v) sort(v.rbegin(), v.rend());//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll dp[2000][2001];
  ll a[2000];
  ll sum[2000];
  int n,k;
  cin >> n >> k;
  REP(i,n) REP(j,j+1) dp[i][j] = INT32_MAX;
  cin >> a[0];
  sum[0] = a[0];
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum [i] = sum[i-1] + a[i];
  }
  dp[0][0] = 0;
  dp[0][1] = 1;
  for(int i=1;i<n;i++){
    dp[i][0] = 0;
    for(int j=1;j<=i+1;j++){
      if(dp[i-1][j-1] < sum[i-1]){
        dp[i][j] = min(dp[i-1][j], (dp[i-1][j-1]*a[i])/sum[i-1] + 1);
      }
      else{
        dp[i][j] = dp[i-1][j];
      }
    }
    int ans;
    REP(i,n+1){
      if(dp[n-1][i] <= k) ans = i;
      else break;
    }
    if(k == sum[n-1]) cout << 1 << endl;
    else cout << ans << endl;
  }
}

Submission Info

Judge Result