Submission #46890

#	Time	Username	Problem	Language	Result	Execution time	Memory
46890		SpaimaCarpatilor	Sparklers (JOI17_sparklers)	C++17	0 / 100	13 ms	4772 KiB

sparklers

#include<bits/stdc++.h>

using namespace std;

int N, K, T, x[100009];
bool dp[2018][2018];

bool ok (int S)
{
    memset (dp, 0, sizeof (dp));
    dp[K][K] = 1;///j is the last visited
    for (int i=K; i>=1; i--)
        for (int j=K; j<=N; j++)
        {
            if ((x[j] - x[i] > 2LL * S * T * (j - i) && 2LL * S * T <= 1000000000) || dp[i][j] == 0)
            {
                dp[i][j] = 0;
                continue;
            }
            dp[i - 1][j] |= dp[i][j], dp[i][j + 1] |= dp[i][j];
        }
    return dp[1][N];
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d", &N, &K, &T);
for (int i=1; i<=N; i++)
    scanf ("%d", &x[i]);
int p = 1, u = 1e9, mij, ras = -1;
while (p <= u)
{
    mij = (p + u) >> 1;
    if (ok (mij)) ras = mij, u = mij - 1;
    else p = mij + 1;
}
printf ("%d\n", ras);
return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d %d", &N, &K, &T);
 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:32:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &x[i]);
     ~~~~~~^~~~~~~~~~~~~

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