oj.uz

Submission #473785

# Submission time Handle Problem Language Result Execution time Memory
473785 2021-09-16T08:54:26 Z Lam_lai_cuoc_doi Watching (JOI13_watching) C++17
100 / 100
 93 ms 16020 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e3 + 5;
constexpr int Inf = 1e9 + 7;

int n, q, p;
int a[N], cp(1), cq(2);
int dp[N][N];

void Read()
{
    cin >> n >> p >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

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

bool Check(int v)
{
    for (int i = 1, ip = 1, iq = 1; i <= n; ++i)
    {
        while (ip < i && a[i] - a[ip] + 1 > cp * v)
            ++ip;
        while (iq < i && a[i] - a[iq] + 1 > cq * v)
            ++iq;

        for (int j = 0; j <= p; ++j)
        {
            dp[i][j] = dp[iq - 1][j] + 1;
            if (j)
                dp[i][j] = min(dp[i][j], dp[ip - 1][j - 1]);
        }
    }

    for (int i = 0; i <= p; ++i)
        if (dp[n][i] <= q)
            return true;
    return false;
}

void Solve()
{
    if (p + q >= n)
    {
        cout << 1;
        return;
    }

    if (p > q)
    {
        swap(p, q);
        swap(cp, cq);
    }

    int l = 1, m, h = 1e9;
    while (l <= h)
    {
        m = (l + h) / 2;
        if (Check(m))
            h = m - 1;
        else
            l = m + 1;
    }

    cout << l;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

watching.cpp: In function 'void read(T&)':
watching.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8268 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 7 ms 8396 KB Output is correct
8 Correct 16 ms 9348 KB Output is correct
9 Correct 16 ms 9292 KB Output is correct
10 Correct 13 ms 9068 KB Output is correct
11 Correct 13 ms 9064 KB Output is correct
12 Correct 93 ms 16020 KB Output is correct
13 Correct 6 ms 8396 KB Output is correct
14 Correct 6 ms 8396 KB Output is correct
15 Correct 6 ms 8396 KB Output is correct