Submission #1210188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210188		mychecksedad	Sparklers (JOI17_sparklers)	C++20	50 / 100	1976 ms	28400 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;
    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(dp[1][n][0][0] || dp[1][n][1][0]){
      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: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50