oj.uz

Submission #805514

# Submission time Handle Problem Language Result Execution time Memory
805514 2023-08-03T17:24:49 Z hariaakas646 Watching (JOI13_watching) C++17
100 / 100
 384 ms 15496 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

vi vec;
int n, p, q;

bool check(int w)
{
    vvi dp(n + 1, vi(p + 1));
    vi pre1(n + 1), pre2(n + 1);
    forr(i, 1, n + 1)
    {
        auto it = lower_bound(all(vec), vec[i] - 2 * w + 1);
        if (it != vec.begin())
        {
            it--;
            pre2[i] = it - vec.begin();
        }
        else
            pre2[i] = 0;

        it = lower_bound(all(vec), vec[i] - w + 1);
        if (it != vec.begin())
        {
            it--;
            pre1[i] = it - vec.begin();
        }
        else
            pre1[i] = 0;
    }
    frange(i, p + 1) dp[0][i] = 0;
    forr(i, 1, n + 1)
    {
        frange(j, p + 1)
        {
            int v = dp[pre2[i]][j];
            dp[i][j] = v + 1;
            if (j > 0)
            {
                v = dp[pre1[i]][j - 1];
                dp[i][j] = min(dp[i][j], v);
            }
        }
    }
    return dp[n][p] <= q;
}

int main()
{

    scd(n);
    scd(p);
    scd(q);
    if (p + q >= n)
    {
        printf("1");
        return 0;
    }
    vec = vi(n + 1);
    forr(i, 1, n + 1) scd(vec[i]);
    sort(all(vec));
    int lo = 1;
    int hi = 1e9;

    while (lo != hi)
    {
        int mid = (lo + hi) / 2;
        if (check(mid))
        {
            hi = mid;
        }
        else
            lo = mid + 1;
    }
    printf("%d", lo);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
watching.cpp:74:5: note: in expansion of macro 'scd'
   74 |     scd(n);
      |     ^~~
watching.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
watching.cpp:75:5: note: in expansion of macro 'scd'
   75 |     scd(p);
      |     ^~~
watching.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
watching.cpp:76:5: note: in expansion of macro 'scd'
   76 |     scd(q);
      |     ^~~
watching.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
watching.cpp:83:23: note: in expansion of macro 'scd'
   83 |     forr(i, 1, n + 1) scd(vec[i]);
      |                       ^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 27 ms 1468 KB Output is correct
9 Correct 137 ms 6352 KB Output is correct
10 Correct 384 ms 15496 KB Output is correct
11 Correct 21 ms 1184 KB Output is correct
12 Correct 179 ms 8128 KB Output is correct
13 Correct 8 ms 468 KB Output is correct
14 Correct 9 ms 564 KB Output is correct
15 Correct 9 ms 440 KB Output is correct