oj.uz

Submission #280385

# Submission time Handle Problem Language Result Execution time Memory
280385 2020-08-22T17:09:50 Z Hehehe Watching (JOI13_watching) C++14
100 / 100
 408 ms 32120 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e3 + 11;
const int X = 1e6;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, m, a[N], dp[N][N], S, B;

bool ok(int small, int big, int w){

    memset(dp, 0x3f, sizeof(dp));

    dp[0][0] = 0;

    for(int j = 1; j <= small; j++) dp[0][j] = 0;

    for(int i = 1; i <= n; i++){

        int x = (upper_bound(a + 1, a + n + 1, a[i] + w - 1) - a) - 1;
        int y = (upper_bound(a + 1, a + n + 1, a[i] + 2*w - 1) - a) - 1;

        for(int j = 0; j <= small; j++){
            if(j != small)dp[x][j + 1] = min(dp[x][j + 1], dp[i - 1][j]);
            dp[y][j] = min(dp[y][j], dp[i - 1][j] + 1);
        }
    }

    return (dp[n][small] <= big);
}

void solve(){

    cin >> n >> S >> B;

    S = min(S, n);
    B = min(B, n);

    for(int i = 1; i <= n; i++)cin >> a[i];

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

    int l = 0, r = 1e9, ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ok(S, B, mid)){
            ans = mid;
            r = mid - 1;
        }else l = mid + 1;
    }

    cout << ans << '\n';

}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 32000 KB Output is correct
2 Correct 132 ms 32000 KB Output is correct
3 Correct 133 ms 32000 KB Output is correct
4 Correct 134 ms 32000 KB Output is correct
5 Correct 132 ms 32048 KB Output is correct
6 Correct 142 ms 32012 KB Output is correct
7 Correct 152 ms 31992 KB Output is correct
8 Correct 137 ms 32000 KB Output is correct
9 Correct 135 ms 32000 KB Output is correct
10 Correct 134 ms 32000 KB Output is correct
11 Correct 139 ms 32000 KB Output is correct
12 Correct 139 ms 32048 KB Output is correct
13 Correct 134 ms 32000 KB Output is correct
14 Correct 134 ms 32000 KB Output is correct
15 Correct 141 ms 31992 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 32000 KB Output is correct
2 Correct 138 ms 31992 KB Output is correct
3 Correct 341 ms 32000 KB Output is correct
4 Correct 388 ms 32120 KB Output is correct
5 Correct 157 ms 32000 KB Output is correct
6 Correct 408 ms 31992 KB Output is correct
7 Correct 149 ms 32000 KB Output is correct
8 Correct 166 ms 32000 KB Output is correct
9 Correct 229 ms 32000 KB Output is correct
10 Correct 362 ms 32120 KB Output is correct
11 Correct 160 ms 31992 KB Output is correct
12 Correct 312 ms 32072 KB Output is correct
13 Correct 151 ms 32120 KB Output is correct
14 Correct 156 ms 32000 KB Output is correct
15 Correct 156 ms 32000 KB Output is correct