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