oj.uz

답안 #473032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473032 2021-09-14T18:49:10 Z nicolaalexandra 구경하기 (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

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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 10956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -