oj.uz

Submission #282282

# Submission time Handle Problem Language Result Execution time Memory
282282 2020-08-24T08:40:14 Z MKopchev Sparklers (JOI17_sparklers) C++14
0 / 100
 11 ms 4736 KB 
#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;

    //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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4736 KB Output is correct
2 Correct 8 ms 4608 KB Output is correct
3 Incorrect 8 ms 4608 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4736 KB Output is correct
2 Correct 8 ms 4608 KB Output is correct
3 Incorrect 8 ms 4608 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4736 KB Output is correct
2 Correct 8 ms 4608 KB Output is correct
3 Incorrect 8 ms 4608 KB Output isn't correct
4 Halted 0 ms 0 KB -