oj.uz

Submission #855462

# Submission time Handle Problem Language Result Execution time Memory
855462 2023-10-01T09:27:30 Z RiverFlow Watching (JOI13_watching) C++14
50 / 100
 30 ms 10848 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)100 + 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][N], a[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);

    memset(dp, -1, sizeof dp);

    dp[0][0][0] = 0;

    FOR(i, 1, n) FOR(j, 0, p) FOR(k, 0, q) {
        FOR(z, 1, i) {
            if (j > 0 and dp[z - 1][j - 1][k] != -1)
                mini(dp[i][j][k], max(dp[z - 1][j - 1][k], a[i] - a[z] + 1));
            if (k > 0 and dp[z - 1][j][k - 1] != -1)
                mini(dp[i][j][k], max(dp[z - 1][j][k - 1], (a[i] - a[z] + 2) / 2));
        }
    }

    int res = INT_MAX;
    FOR(j, 0, p) FOR(k, 0, q) if (dp[n][j][k] != -1)
        res = min(res, dp[n][j][k]);
    cout << res;
}


/*     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 2 ms 5464 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 5712 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 3 ms 5528 KB Output is correct
9 Correct 2 ms 5468 KB Output is correct
10 Correct 13 ms 5468 KB Output is correct
11 Correct 15 ms 5468 KB Output is correct
12 Correct 30 ms 5508 KB Output is correct
13 Correct 2 ms 5468 KB Output is correct
14 Correct 2 ms 5468 KB Output is correct
15 Correct 2 ms 5468 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 10848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -