oj.uz

Submission #698576

# Submission time Handle Problem Language Result Execution time Memory
698576 2023-02-13T21:36:17 Z Richem Watching (JOI13_watching) C++14
50 / 100
 1000 ms 33084 KB 
#include <iostream>
#include <unordered_map>
#include <set>
#define int long long
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;
}

signed main() {
    input();

    cout << dicho();
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 32852 KB Output is correct
2 Correct 135 ms 32972 KB Output is correct
3 Correct 141 ms 32852 KB Output is correct
4 Correct 149 ms 32840 KB Output is correct
5 Correct 132 ms 32932 KB Output is correct
6 Correct 173 ms 32924 KB Output is correct
7 Correct 133 ms 32924 KB Output is correct
8 Correct 137 ms 32924 KB Output is correct
9 Correct 141 ms 32924 KB Output is correct
10 Correct 131 ms 32920 KB Output is correct
11 Correct 136 ms 32932 KB Output is correct
12 Correct 140 ms 32852 KB Output is correct
13 Correct 134 ms 32928 KB Output is correct
14 Correct 130 ms 32852 KB Output is correct
15 Correct 131 ms 32924 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 33044 KB Output is correct
2 Correct 128 ms 32852 KB Output is correct
3 Execution timed out 1082 ms 33084 KB Time limit exceeded
4 Halted 0 ms 0 KB -