oj.uz

Submission #698575

# Submission time Handle Problem Language Result Execution time Memory
698575 2023-02-13T21:35:47 Z Richem Watching (JOI13_watching) C++14
50 / 100
 1000 ms 33128 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 32932 KB Output is correct
2 Correct 164 ms 32852 KB Output is correct
3 Correct 159 ms 32932 KB Output is correct
4 Correct 172 ms 32924 KB Output is correct
5 Correct 162 ms 32932 KB Output is correct
6 Correct 171 ms 32852 KB Output is correct
7 Correct 166 ms 32924 KB Output is correct
8 Correct 162 ms 32852 KB Output is correct
9 Correct 168 ms 32928 KB Output is correct
10 Correct 170 ms 32928 KB Output is correct
11 Correct 177 ms 32928 KB Output is correct
12 Correct 166 ms 32856 KB Output is correct
13 Correct 162 ms 32852 KB Output is correct
14 Correct 162 ms 32928 KB Output is correct
15 Correct 187 ms 32984 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 33100 KB Output is correct
2 Correct 163 ms 32924 KB Output is correct
3 Execution timed out 1094 ms 33128 KB Time limit exceeded
4 Halted 0 ms 0 KB -