Submission #373359

#	Time	Username	Problem	Language	Result	Execution time	Memory
373359		BartolM	Watching (JOI13_watching)	C++17	100 / 100	667 ms	16300 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2005;

int n, A, B;
int p[N];
int dp[N][N];
int nx_w[N], nx_2w[N];

int rek(int pos, int kol) {
    if (kol>A) return INF;
    if (pos>=n) return 0;

    int &ret=dp[pos][kol];
    if (ret!=-1) return ret;

    ret=rek(nx_w[pos], kol+1);
    ret=min(ret, rek(nx_2w[pos], kol)+1);
    return ret;
}

int check(int w) {
    for (int i=0; i<n; ++i) {
        nx_w[i]=nx_2w[i]=i+1;
        for (int j=i+1; j<n; ++j) {
            if (p[j]-p[i]<w) nx_w[i]=j+1;
            if (p[j]-p[i]<2*w) nx_2w[i]=j+1;
        }
    }
    memset(dp, -1, sizeof dp);
    return rek(0, 0)<=B;
}

void solve() {
    sort(p, p+n);
    int lo=1, hi=1e9+3, mid;
    while (lo<hi) {
        mid=(lo+hi)/2;
        if (check(mid)) hi=mid;
        else lo=mid+1;
    }
    printf("%d\n", lo);
}

void load() {
    scanf("%d %d %d", &n, &A, &B);
    for (int i=0; i<n; ++i) scanf("%d", p+i);
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'void load()':
watching.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |     scanf("%d %d %d", &n, &A, &B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:60:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     for (int i=0; i<n; ++i) scanf("%d", p+i);
      |                             ~~~~~^~~~~~~~~~~

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