oj.uz

Submission #698577

# Submission time Handle Problem Language Result Execution time Memory
698577 2023-02-13T21:37:57 Z Richem Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16796 KB 
#include <iostream>
#include <unordered_map>
#include <set>
using namespace std;

const int MAX_NOMBRE = 2042, INF = 1e9;

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;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    input();

    cout << dicho();
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 16624 KB Output is correct
2 Correct 82 ms 16612 KB Output is correct
3 Correct 80 ms 16616 KB Output is correct
4 Correct 89 ms 16700 KB Output is correct
5 Correct 71 ms 16624 KB Output is correct
6 Correct 84 ms 16592 KB Output is correct
7 Correct 70 ms 16620 KB Output is correct
8 Correct 71 ms 16624 KB Output is correct
9 Correct 70 ms 16628 KB Output is correct
10 Correct 76 ms 16620 KB Output is correct
11 Correct 78 ms 16620 KB Output is correct
12 Correct 78 ms 16624 KB Output is correct
13 Correct 69 ms 16580 KB Output is correct
14 Correct 85 ms 16624 KB Output is correct
15 Correct 82 ms 16596 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16796 KB Output is correct
2 Correct 70 ms 16520 KB Output is correct
3 Execution timed out 1093 ms 16724 KB Time limit exceeded
4 Halted 0 ms 0 KB -