oj.uz

답안 #575079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
575079 2022-06-09T15:51:07 Z tamthegod 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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