oj.uz

Submission #698580

# Submission time Handle Problem Language Result Execution time Memory
698580 2023-02-13T21:49:34 Z Richem Watching (JOI13_watching) C++14
100 / 100
 264 ms 32808 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];

int temps[MAX_NOMBRE][MAX_NOMBRE] = {0};
int idTemps = 1;

bool possible(int taille) {
    dp[0][0] = 0;

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

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

    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();

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

    cout << dicho();
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16980 KB Output is correct
2 Correct 10 ms 16588 KB Output is correct
3 Correct 9 ms 16580 KB Output is correct
4 Correct 10 ms 17108 KB Output is correct
5 Correct 9 ms 17024 KB Output is correct
6 Correct 9 ms 17008 KB Output is correct
7 Correct 9 ms 17056 KB Output is correct
8 Correct 8 ms 17060 KB Output is correct
9 Correct 8 ms 16980 KB Output is correct
10 Correct 9 ms 17060 KB Output is correct
11 Correct 9 ms 16980 KB Output is correct
12 Correct 10 ms 17092 KB Output is correct
13 Correct 10 ms 17020 KB Output is correct
14 Correct 9 ms 16960 KB Output is correct
15 Correct 8 ms 16968 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24852 KB Output is correct
2 Correct 8 ms 16596 KB Output is correct
3 Correct 214 ms 32788 KB Output is correct
4 Correct 264 ms 32808 KB Output is correct
5 Correct 31 ms 25428 KB Output is correct
6 Correct 260 ms 32796 KB Output is correct
7 Correct 21 ms 24964 KB Output is correct
8 Correct 41 ms 25844 KB Output is correct
9 Correct 129 ms 30636 KB Output is correct
10 Correct 254 ms 32796 KB Output is correct
11 Correct 33 ms 25556 KB Output is correct
12 Correct 164 ms 32484 KB Output is correct
13 Correct 21 ms 24968 KB Output is correct
14 Correct 22 ms 24916 KB Output is correct
15 Correct 26 ms 24988 KB Output is correct