oj.uz

Submission #44563

# Submission time Handle Problem Language Result Execution time Memory
44563 2018-04-03T09:17:50 Z chpipis Watching (JOI13_watching) C++11
100 / 100
 323 ms 16920 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 2005;

int n, p, q;
int ev[MAXN], dp[MAXN][MAXN];
int prep[MAXN], preq[MAXN];

bool can(int w) {
    int ptr = 0;
    for (int i = 1; i <= n; i++) {
        while (ptr < i && ev[i] - w + 1 > ev[ptr])
            ptr++;
        prep[i] = ptr - 1;
    }
    ptr = 0;
    for (int i = 1; i <= n; i++) {
        while (ptr < i && ev[i] - 2 * w + 1 > ev[ptr])
            ptr++;
        preq[i] = ptr - 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= q; j++) {
            dp[i][j] = dp[prep[i]][j] + 1;
            if (j > 0)
                dp[i][j] = min(dp[i][j], dp[preq[i]][j - 1]);
        }
    }
    //printf("can(%d) ? %d\n", w, (int)(dp[n][q] <= p));
    return dp[n][q] <= p;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    scanf("%d %d %d", &n, &p, &q);
    ev[0] = -2e9;
    for (int i = 1; i <= n; i++)
        scanf("%d", &ev[i]);
    sort(ev + 1, ev + n + 1);
    if (p + q >= n) {
        puts("1");
    } else {
        int lo = 1, hi = 1e9;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (can(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        printf("%d\n", hi);
    }
    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ev[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 2 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 2 ms 1016 KB Output is correct
7 Correct 2 ms 1232 KB Output is correct
8 Correct 2 ms 1272 KB Output is correct
9 Correct 2 ms 1276 KB Output is correct
10 Correct 2 ms 1280 KB Output is correct
11 Correct 2 ms 1284 KB Output is correct
12 Correct 2 ms 1292 KB Output is correct
13 Correct 3 ms 1292 KB Output is correct
14 Correct 2 ms 1296 KB Output is correct
15 Correct 2 ms 1300 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8984 KB Output is correct
2 Correct 2 ms 8984 KB Output is correct
3 Correct 2 ms 8984 KB Output is correct
4 Correct 2 ms 8984 KB Output is correct
5 Correct 2 ms 8984 KB Output is correct
6 Correct 2 ms 8984 KB Output is correct
7 Correct 11 ms 9164 KB Output is correct
8 Correct 114 ms 15068 KB Output is correct
9 Correct 27 ms 15068 KB Output is correct
10 Correct 22 ms 15068 KB Output is correct
11 Correct 323 ms 16920 KB Output is correct
12 Correct 219 ms 16920 KB Output is correct
13 Correct 11 ms 16920 KB Output is correct
14 Correct 11 ms 16920 KB Output is correct
15 Correct 12 ms 16920 KB Output is correct