oj.uz

Submission #575079

# Submission time Handle Problem Language Result Execution time Memory
575079 2022-06-09T15:51:07 Z tamthegod Watching (JOI13_watching) C++14
100 / 100
 187 ms 31820 KB 
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2000 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, p, q, a[maxN];
int f[maxN][maxN];
void ReadInput()
{
    cin >> n >> p >> q;
    p = min(p, n);
    q = min(q, n);
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
}
pair<int, int> cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.fi * 2 + a.se < b.fi * 2 + b.se) return a;
    if(a.fi * 2 + a.se > b.fi * 2 + b.se) return b;
    return a.fi > b.fi ? a : b;
}
bool chk(int x)
{
    for(int i=1; i<=n; i++)
    {
        int t = i;
        int id1 = lower_bound(a + 1, a + n + 1, a[i] - x + 1) - a;
        int id2 = lower_bound(a + 1, a + n + 1, a[i] - x * 2 + 1) - a;
        for(int j=0; j<=p; j++)
        {
            f[i][j] = oo;
            f[i][j] = f[id2 - 1][j] + 1;
            if(j > 0) f[i][j] = min(f[i][j], f[id1 - 1][j - 1]);
        }
    }
    return f[n][p] <= q;
}
void Solve()
{
    //chk(4);return;
    int low = 1, high = 1e9, mid;
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(chk(mid)) high = mid - 1;
        else low = mid + 1;
    }
    cout << low;
}
int32_t main()
{
  //  freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message

watching.cpp: In function 'bool chk(long long int)':
watching.cpp:57:13: warning: unused variable 't' [-Wunused-variable]
   57 |         int t = i;
      |             ^

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8444 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 167 ms 31820 KB Output is correct
4 Correct 187 ms 31760 KB Output is correct
5 Correct 14 ms 9560 KB Output is correct
6 Correct 171 ms 31696 KB Output is correct
7 Correct 8 ms 8532 KB Output is correct
8 Correct 22 ms 10348 KB Output is correct
9 Correct 85 ms 20308 KB Output is correct
10 Correct 171 ms 31740 KB Output is correct
11 Correct 17 ms 9804 KB Output is correct
12 Correct 112 ms 23720 KB Output is correct
13 Correct 12 ms 8544 KB Output is correct
14 Correct 14 ms 8660 KB Output is correct
15 Correct 13 ms 8660 KB Output is correct