oj.uz

Submission #702040

# Submission time Handle Problem Language Result Execution time Memory
702040 2023-02-22T13:56:32 Z Tien_Noob Watching (JOI13_watching) C++17
100 / 100
 330 ms 16076 KB 
//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e3;
int dp[N + 1][N + 1];
int last[N + 1][2];
int a[N + 1], p, q, 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 mid)
{
    for (int t = 1; t <= 2; ++ t)
    {
        int j = 1;
        for (int i = 1; i <= n; ++ i)
        {
            while(a[j] + 1LL * t * mid - 1 < a[i])
            {
                ++j;
            }
            last[i][t - 1] = j;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 0; j <= q; ++ j)
        {
            if (j > 0)
            {
                dp[i][j] = min(dp[i][j], dp[last[i][1] - 1][j - 1]);
            }
            dp[i][j] = min(dp[i][j], dp[last[i][0] - 1][j] + 1);
        }
    }
    return *min_element(dp[n], dp[n] + q + 1) <= p;
}
void solve()
{
    if (max(p, q) >= n)
    {
        cout << 1;
        return ;
    }
    int low = 1, high = 1e9;
    while(low <= high)
    {
        int mid = (low + high)/2;
        if (check(mid))
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    cout << low;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15956 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 52 ms 15984 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 328 KB Output is correct
7 Correct 51 ms 15956 KB Output is correct
8 Correct 50 ms 15956 KB Output is correct
9 Correct 52 ms 15964 KB Output is correct
10 Correct 52 ms 15980 KB Output is correct
11 Correct 51 ms 15956 KB Output is correct
12 Correct 54 ms 15980 KB Output is correct
13 Correct 54 ms 15980 KB Output is correct
14 Correct 52 ms 15976 KB Output is correct
15 Correct 53 ms 16076 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16020 KB Output is correct
2 Correct 51 ms 15980 KB Output is correct
3 Correct 255 ms 16016 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 57 ms 16016 KB Output is correct
8 Correct 174 ms 16020 KB Output is correct
9 Correct 72 ms 16016 KB Output is correct
10 Correct 67 ms 16028 KB Output is correct
11 Correct 330 ms 16016 KB Output is correct
12 Correct 188 ms 15956 KB Output is correct
13 Correct 57 ms 16020 KB Output is correct
14 Correct 55 ms 16016 KB Output is correct
15 Correct 55 ms 16020 KB Output is correct