Submission #1061997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061997		oscar1f	Sparklers (JOI17_sparklers)	C++17	50 / 100	22 ms	1624 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=1000+5,INFINI=1000*1000*1000;
int nbVal,posInit,tempsInit;
int val[TAILLE_MAX];
bool fonctionne[TAILLE_MAX][TAILLE_MAX];

bool verif(int temps) {
    for (int i=1;i<=nbVal;i++) {
        for (int j=i;j<=nbVal;j++) {
            fonctionne[i][j]=false;
        }
    }
    int fin;
    fonctionne[posInit][posInit]=true;
    for (int taille=2;taille<=nbVal;taille++) {
        for (int deb=1;deb+taille-1<=nbVal;deb++) {
            fin=deb+taille-1;
            if ((fonctionne[deb][fin-1] or fonctionne[deb+1][fin]) and 2*(taille-1)*temps>=val[fin]-val[deb]) {
                fonctionne[deb][fin]=true;
            }
        }
    }
    return fonctionne[1][nbVal];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal>>posInit>>tempsInit;
    for (int i=1;i<=nbVal;i++) {
        cin>>val[i];
    }
    int deb=0,fin=INFINI,mid;
    while (deb!=fin) {
        mid=(deb+fin)/2;
        if (verif(mid)) {
            fin=mid;
        }
        else {
            deb=mid+1;
        }
    }
    cout<<(deb+tempsInit-1)/tempsInit<<endl;
    return 0;
}
 

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50