Submission #363256

#	Time	Username	Problem	Language	Result	Execution time	Memory
363256		denkendoemeer	Sparklers (JOI17_sparklers)	C++14	100 / 100	43 ms	2924 KiB

sparklers

#include<bits/stdc++.h>
#define ll long long
const ll inf=1e18;
using namespace std;
ll t,x[100005],dp[100005];
int n,k;
bool calc(ll nr)
{
    nr=nr*2;
    if (t*nr>(ll)1e9)
        return 1;
    int i;
    for(i=1;i<=n;i++)
        dp[i]=x[i]-i*t*nr;
    int st=1,dr=n;
    for(i=1;i<=k;i++)
        if (dp[st]<=dp[i])
            st=i;
    for(i=k;i<=n;i++)
        if (dp[dr]>=dp[i])
            dr=i;
    int l=k,r=k;
    ll v1=dp[l],v2=dp[r];
    while(st<=l || r<=dr){
        int auxl=l,auxr=r;
        while(l>=st && dp[l]>=v2){
            v1=max(v1,dp[l]);
            l--;
        }
        while(r<=dr && dp[r]<=v1){
            v2=min(v2,dp[r]);
            r++;
        }
        if (l==auxl && r==auxr)
            return 0;
    }
    l=1;
    r=n;
    v1=dp[l];
    v2=dp[r];
    while(l<=st || dr<=r){
        int auxl=l,auxr=r;
        while(l<=st && dp[l]>=v2){
            v1=max(v1,dp[l]);
            l++;
        }
        while(r>=dr && dp[r]<=v1){
            v2=min(v2,dp[r]);
            r--;
        }
        if (l==auxl && r==auxr)
            return 0;
    }
    return 1;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d%d%lld",&n,&k,&t);
    int i;
    for(i=1;i<=n;i++)
        scanf("%lld",&x[i]);
    ll st=0,dr=1e9,mij,last;
    while(st<=dr){
        mij=(st+dr)/2;
        if (calc(mij)){
            last=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    printf("%lld\n",last);
return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     scanf("%d%d%lld",&n,&k,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%lld",&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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