Submission #282285

#	Time	Username	Problem	Language	Result	Execution time	Memory
282285		MKopchev	Sparklers (JOI17_sparklers)	C++14	50 / 100	49 ms	4668 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e3+42,inf=1e9;

int n,k,t,inp[nmax];

int mem[nmax][nmax];

int cur_v;

int ask(int l,int r)
{
    if(k<l||k>r)return 0;

    if(l==r)return 1;
    if(mem[l][r]!=-1)return mem[l][r];

    if(inp[r]-inp[l]<=2LL*(r-l)*t*cur_v)
    {
        if(ask(l,r-1))mem[l][r]=1;
        else if(ask(l+1,r))mem[l][r]=1;
        else mem[l][r]=0;
    }
    else mem[l][r]=0;

    //cout<<l<<" "<<r<<" -> "<<mem[l][r]<<endl;

    return mem[l][r];
}
bool test(int v)
{
    //cout<<"v= "<<v<<endl;

    memset(mem,-1,sizeof(mem));

    cur_v=v;

    return ask(1,n);
}
int main()
{
    scanf("%i%i%i",&n,&k,&t);

    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    int ok=inf/t+1,not_ok=-1;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        if(test(av))ok=av;
        else not_ok=av;
    }
    printf("%i\n",ok);
    return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%i%i%i",&n,&k,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sparklers.cpp:45:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
      |                          ~~~~~^~~~~~~~~~~~~~

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