oj.uz

Submission #473032

# Submission time Handle Problem Language Result Execution time Memory
473032 2021-09-14T18:49:10 Z nicolaalexandra Watching (JOI13_watching) C++14
50 / 100
 19 ms 10956 KB 
#include <bits/stdc++.h>
#define DIM 110
#define INF 1000000000
using namespace std;

struct idk{
    int poz,p,q;
};
deque <idk> c;
int viz[DIM][DIM][DIM],v[DIM];
int n,p,q,i;

int get_poz (int x){
    int st = 1, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] <= x){
            sol = mid;
            st = mid+1;
        } else dr = mid-1;
    }
    return sol;
}

int verif (int val){

    int poz1 = get_poz (v[1] + val - 1);
    int poz2 = get_poz (v[1] + 2 * val - 1);

    c.clear();
    memset (viz,0,sizeof viz);
    c.push_back({poz1,p-1,q});
    c.push_back({poz2,p,q-1});
    viz[poz1][p-1][q] = 1;
    viz[poz2][p][q-1] = 1;

    while (!c.empty()){
        int poz = c.front().poz;
        int p = c.front().p;
        int q = c.front().q;
        c.pop_front();

        if (poz == n)
            return 1;

        if (p){
            int new_poz = get_poz (v[poz+1] + val - 1);
            if (!viz[new_poz][p-1][q]){
                viz[new_poz][p-1][q] = 1;
                c.push_back({new_poz,p-1,q});
            }
        }

        if (q){
            int new_poz = get_poz (v[poz+1] + 2 * val - 1);
            if (!viz[new_poz][p][q-1]){
                viz[new_poz][p][q-1] = 1;
                c.push_back({new_poz,p,q-1});
            }
        }
    }

    return 0;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>p>>q;
    for (i=1;i<=n;i++)
        cin>>v[i];

    sort (v+1,v+n+1);
    p = min (p,n), q = min (q,n);

    int st = 0, dr = INF, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    cout<<sol;

    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5452 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 11 ms 5580 KB Output is correct
4 Correct 10 ms 5444 KB Output is correct
5 Correct 11 ms 5508 KB Output is correct
6 Correct 19 ms 5508 KB Output is correct
7 Correct 9 ms 5452 KB Output is correct
8 Correct 9 ms 5452 KB Output is correct
9 Correct 10 ms 5504 KB Output is correct
10 Correct 13 ms 5452 KB Output is correct
11 Correct 14 ms 5508 KB Output is correct
12 Correct 14 ms 5512 KB Output is correct
13 Correct 9 ms 5452 KB Output is correct
14 Correct 9 ms 5452 KB Output is correct
15 Correct 10 ms 5504 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 10956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -