oj.uz

답안 #473030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473030 2021-09-14T18:44:22 Z nicolaalexandra 구경하기 (JOI13_watching) C++14
0 / 100
 10 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[i] + val - 1);
    int poz2 = get_poz (v[i] + 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
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 5452 KB Output is correct
2 Correct 10 ms 5500 KB Output is correct
3 Incorrect 9 ms 5452 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 -