oj.uz

Submission #698578

# Submission time Handle Problem Language Result Execution time Memory
698578 2023-02-13T21:40:58 Z Richem Watching (JOI13_watching) C++14
50 / 100
 1000 ms 32668 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) {
        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[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) {
                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 9 ms 16980 KB Output is correct
2 Correct 8 ms 16596 KB Output is correct
3 Correct 8 ms 16664 KB Output is correct
4 Correct 19 ms 17108 KB Output is correct
5 Correct 9 ms 16980 KB Output is correct
6 Correct 31 ms 17120 KB Output is correct
7 Correct 9 ms 16984 KB Output is correct
8 Correct 9 ms 17000 KB Output is correct
9 Correct 10 ms 16980 KB Output is correct
10 Correct 10 ms 16980 KB Output is correct
11 Correct 20 ms 17100 KB Output is correct
12 Correct 16 ms 16980 KB Output is correct
13 Correct 9 ms 16980 KB Output is correct
14 Correct 10 ms 17020 KB Output is correct
15 Correct 10 ms 16980 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24828 KB Output is correct
2 Correct 8 ms 16540 KB Output is correct
3 Execution timed out 1096 ms 32668 KB Time limit exceeded
4 Halted 0 ms 0 KB -