Submission #999289

#	Time	Username	Problem	Language	Result	Execution time	Memory
999289		AdamGS	Sparklers (JOI17_sparklers)	C++17	50 / 100	89 ms	16372 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e9+7;
const int LIM=1e3+7;
ll T[LIM], n, k, t;
ll odw[LIM][LIM], dp[LIM][LIM];
ll solve(ll l, ll r, ll x) {
  if(odw[l][r]) return dp[l][r];
  odw[l][r]=1;
  dp[l][r]=-INF;
  if(l>r || r<k || k<l) return dp[l][r];
  ll a=solve(l+1, r, x), b=solve(l, r-1, x);
  if(a>=T[l+1]-T[l]) dp[l][r]=max(dp[l][r], a-T[l+1]+T[l]+t*x*2);
  if(b>=T[r]-T[r-1]) dp[l][r]=max(dp[l][r], b-T[r]+T[r-1]+t*x*2);
  return dp[l][r];
}
bool check(ll x) {
  rep(i, n) rep(j, n) odw[i][j]=dp[i][j]=0;
  dp[k][k]=2*x*t;
  odw[k][k]=1;
  return solve(0, n-1, x)>=0;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> k >> t; --k;
  rep(i, n) cin >> T[i]; 
  ll po=0, ko=INF;
  while(po<ko) {
    ll sr=(po+ko)/2;
    if(check(sr)) ko=sr; else po=sr+1;
  }
  cout << po << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50