Submission #1210202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210202		mychecksedad	Sparklers (JOI17_sparklers)	C++20	0 / 100	0 ms	328 KiB

sparklers

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define cerr if(false)cerr
const int N = 5000+100, M = 1e5+10, K = 52, MX = 30;


ll n, k, T, a[N];
array<ll, 3> dp[N][N][2];
void solve(){
  cin >> n >> k >> T;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  int L = 0, R = 1e9, ans = 0;
  while(L <= R){
    ll S = L+R>>1;

    int l = k, r = k;
    ll mn = a[k], mx = a[k];
    while(l > 1 || r < n){
      bool move = false;

      bool r_move = (r < n && mx + S * T >= a[r + 1] - (r-l+1) * S * T);
      bool l_move = (l > 1 && mn - S * T <= a[l - 1] + (r-l+1) * S * T);

      if(r_move && ((l_move && a[r + 1] - a[r] <= a[l] - a[l - 1]) || !l_move)){
        mx = mx + S * T;
        mn = a[r + 1] - (r-l+1) * S * T;
        move = true;
        ++r;
      }else if(l_move){
        mn = mn - S * T;
        mx = a[l - 1] + (r-l+1) * S * T;
        --l;
        move = true;
      }


      if(!move) break;
    }

    // for(int i = 1; i <= n; ++i){
    //   for(int j = i; j <= n; ++j) dp[i][j][0] = dp[i][j][1] = {0, 0, 0};
    // }
    // cerr << S << '\n';
    // dp[k][k][0] = dp[k][k][1] = {1, a[k], a[k]};
    // for(int d = 1; d <= n; ++d){
    //   for(int l = 1; l + d <= n; ++l){
    //     int r = l + d;

    //     vi V = {l, r};

    //     array<ll, 3> v = {0, 0, 0};
    //     array<ll, 3> q = {0, 0, 0};
    //     for(int p = 0; p < 2; ++p){
    //       if(dp[l + 1][r][p][0]){
    //         if(v[0]){
    //           v[1] = min(v[1], dp[l + 1][r][p][1] - S * T);
    //           v[2] = max(v[2], dp[l + 1][r][p][2] + S * T);
    //         }else{
    //           v[0] = 1;
    //           v[1] = dp[l + 1][r][p][1] - S * T;
    //           v[2] = dp[l + 1][r][p][2] + S * T;
    //         }
    //       }
    //       if(dp[l][r - 1][p][0]){
    //         if(q[0]){
    //           q[1] = min(q[1], dp[l][r - 1][p][1]);
    //           q[2] = max(q[2], dp[l][r - 1][p][2]);
    //         }else{
    //           q[0] = 1;
    //           q[1] = dp[l][r - 1][p][1] - S * T;
    //           q[2] = dp[l][r - 1][p][2] + S * T;
    //         }
    //       }
    //     }
    //     if(v[0] && v[1] <= a[l] + (r-l)*S*T)
    //       dp[l][r][0] = {v[0], v[1], min(v[2], a[l] + (r-l)*S*T)};
    //     if(q[0] && q[2] >= a[r] - (r-l)*S*T)
    //       dp[l][r][1] = {q[0], max(q[1], a[r] - (r-l)*S*T), q[2]};

    //     cerr << l << ' ' << r << " :\n";
    //     cerr << dp[l][r][0][0] << ' ' << dp[l][r][0][1] << ' ' << dp[l][r][0][2] << '\n';
    //     cerr << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
    //     cerr << dp[l][r][1][0] << ' ' << dp[l][r][1][1] << ' ' << dp[l][r][1][2] << '\n';
    //     cerr << q[0] << ' ' << q[1] << ' ' <<q[2] << '\n';
    //     cerr << '\n';
    //   }
    //   cerr <<'\n';
    // }
    if(l == 1 && r == n){
      R = S - 1;
      ans = S;
    }else L = S + 1;
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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