Submission #94963

#	Time	Username	Problem	Language	Result	Execution time	Memory
94963		bogdan10bos	Watching (JOI13_watching)	C++14	100 / 100	425 ms	16120 KiB

watching

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

const int NMAX = 2000;

int N, A, B;
int v[NMAX + 5];
int dp[NMAX + 5][NMAX + 5];
/// dp[i][j] - primele i, j camere mari

bool can(int w)
{
    int pA = 1, pB = 1;
    for(int i = 1; i <= N; i++)
        for(int j = 0; j <= B; j++)
        {
            while(v[i] - v[pA] + 1 > w) pA++;
            while(v[i] - v[pB] + 1 > 2 * w) pB++;

            dp[i][j] = dp[pA - 1][j] + 1;
            if(j > 0)   dp[i][j] = min(dp[i][j], dp[pB - 1][j - 1]);
        }
    return (dp[N][B] <= A);
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &A, &B);
    A = min(A, N); B = min(B, N);
    for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
    sort(v + 1, v + N + 1);

    int p = 1, u = 1e9;
    int ans = 0;
    while(p <= u)
    {
        int mij = p + (u - p) / 2;
        if( can(mij) )
        {
            ans = mij;
            u = mij - 1;
        }
        else
            p = mij + 1;
    }
    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &A, &B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:38:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
                                 ~~~~~^~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50