oj.uz

Submission #855467

# Submission time Handle Problem Language Result Execution time Memory
855467 2023-10-01T09:43:00 Z RiverFlow Watching (JOI13_watching) C++14
100 / 100
 136 ms 16472 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b || a == -1) { a = b; return 1; } return 0;
}

const int N = (int)2e3 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int dp[N][N], a[N], nxt1[N], nxt2[N];

void main_code() {
    int n, p, q; cin >> n >> p >> q;

    for(int i = 1; i <= n; ++i) cin >> a[i];

    sort(a + 1, a + n + 1);

    if (p + q >= n) evoid(1);
    // binary search w

    // dp[i][j] => min k have used so that cover first i point

    // j : number of small camera used

    int l = 1, r = (int)1e9 + 100, ans = -1;

    while (l <= r) {
        int m = (l + r) >> 1, w = m;
        memset(dp, -1, sizeof dp); dp[0][0] = 0;
        int j = 0; FOR(i, 1, n) {
            while (j + 1 <= n and a[j + 1] - a[i] + 1 <= w) ++j;
            nxt1[i] = j;
        }
        j = 0; FOR(i, 1, n) {
             while (j + 1 <= n and (a[j + 1] - a[i] + 2) / 2 <= w) ++j;
            nxt2[i] = j;
        }
        FOR(i, 0, n - 1) FOR(j, 0, p) if (dp[i][j] != -1) {
            if (j + 1 <= p)
                mini(dp[nxt1[i + 1]][j + 1], dp[i][j]);
            mini(dp[nxt2[i + 1]][j], dp[i][j] + 1);
        }
        bool ok = 0;
        FOR(j, 0, p) if (dp[n][j] != -1 and dp[n][j] <= q) {
            ok = 1; break ;
        }
        if (ok) {
            ans = m; r = m - 1;
        } else
            l = m + 1;
    }

    cout << ans;
}


/*     Let the river flows naturally     */

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16216 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 13 ms 16260 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 15 ms 16220 KB Output is correct
8 Correct 14 ms 16264 KB Output is correct
9 Correct 14 ms 16220 KB Output is correct
10 Correct 16 ms 16216 KB Output is correct
11 Correct 24 ms 16216 KB Output is correct
12 Correct 14 ms 16220 KB Output is correct
13 Correct 13 ms 16220 KB Output is correct
14 Correct 13 ms 16220 KB Output is correct
15 Correct 14 ms 16260 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16472 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 16 ms 16216 KB Output is correct
8 Correct 26 ms 16220 KB Output is correct
9 Correct 63 ms 16468 KB Output is correct
10 Correct 136 ms 16280 KB Output is correct
11 Correct 23 ms 16216 KB Output is correct
12 Correct 104 ms 16468 KB Output is correct
13 Correct 15 ms 16216 KB Output is correct
14 Correct 15 ms 16220 KB Output is correct
15 Correct 21 ms 16216 KB Output is correct