oj.uz

Submission #373358

# Submission time Handle Problem Language Result Execution time Memory
373358 2021-03-04T09:18:45 Z BartolM Watching (JOI13_watching) C++17
0 / 100
 132 ms 16256 KB 
#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;
ll 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(ll 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]<w*2) nx_2w[i]=j+1;
        }
    }
    memset(dp, -1, sizeof dp);
    return rek(0, 0)<=B;
}

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

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

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

Compilation message

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("%lld", p+i);
      |                             ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 16256 KB Output is correct
2 Incorrect 64 ms 16108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 16236 KB Output is correct
2 Incorrect 66 ms 16108 KB Output isn't correct
3 Halted 0 ms 0 KB -