Submission #166946

#	Time	Username	Problem	Language	Result	Execution time	Memory
166946		theStaticMind	Sparklers (JOI17_sparklers)	C++14	0 / 100	3 ms	376 KiB

sparklers

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,k,t;
      cin>>n>>k>>t;
      vector<int> arr;
      for(int i=0;i<n;i++){
            int x;
            cin>>x;
            arr.pb(x);
      }
      int l=0,r=1e10,ans;
      while(l<=r){
            int mid=(l+r)/2;
            int diff=mid*t;
            int L=arr[k];
            int R=arr[k];
            int i=k-1,j=k+1;
            while(i>=0||j<n){
                  if(i>=0&&arr[i]>=L-2*diff){
                        i--;
                        L-=diff*2;
                        R+=diff;
                  }
                  else if(j<n&&arr[j]<=R+2*diff){
                        j++;
                        L-=diff;
                        R+=diff*2;
                  }
                  else break;
            }
            if(i<0&&j>=n){
                  r=mid-1;
                  ans=mid;
            }
            else{
                  l=mid+1;
            }
      }
      cout<<ans;
}

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