Submission #698575

#	Time	Username	Problem	Language	Result	Execution time	Memory
698575		Richem	Watching (JOI13_watching)	C++14	50 / 100	1094 ms	33128 KiB

watching

#include <iostream>
#include <unordered_map>
#include <set>
#define int long long
using namespace std;

const int MAX_NOMBRE = 2042, INF = 1e12;

int nbPos, nbPetit, nbGrand;
multiset<int> pos;

unordered_map<int, int> idPos;

void input() {
    cin >> nbPos >> nbPetit >> nbGrand;
    nbPetit = min(nbPetit, nbPos);
    nbGrand = min(nbGrand, nbPos);

    for(int cur = 0; cur < nbPos; cur++) {
        int posCur;
        cin >> posCur;

        pos.insert(posCur);
    }
    
    int idCur = 1;
    for(auto cur : pos) {
        idPos[cur] = idCur++;
    }
}

int getPos(int posInit, int dist) {
    auto it = pos.lower_bound(posInit - dist+1);

    if(it == pos.begin()) {
        return 0;
    }
    it--;
    return idPos[*it];
}

int dp[MAX_NOMBRE][MAX_NOMBRE];

bool possible(int taille) {
    for(int i = 0; i < MAX_NOMBRE; i++) {
        for(int j = 0; j < MAX_NOMBRE; j++) {
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;

    int curPt = 1;
    for(auto valPt : pos) {
        for(int curPetit = 0; curPetit <= nbPetit; curPetit++) {
            if(curPetit > 0) {
                dp[curPt][curPetit] = min(dp[curPt][curPetit], dp[getPos(valPt, taille)][curPetit-1]);
            }
            dp[curPt][curPetit] = min(dp[curPt][curPetit], dp[getPos(valPt, taille*2)][curPetit] + 1);

            if(curPt == nbPos && dp[curPt][curPetit] <= nbGrand) {
                return 1;
            }
        }
        curPt++;
    }

    return 0;
}

int dicho() {
    int deb = 1, fin = INF;

    while(deb < fin) {
        int milieu = (deb + fin) / 2;

        if(possible(milieu)) {
            fin = milieu;
        }
        else {
            deb = milieu+1;
        }
    }

    return deb;
}

signed main() {
    input();

    cout << dicho();
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50