Submission #1063603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063603		oscar1f	Sparklers (JOI17_sparklers)	C++17	100 / 100	197 ms	12168 KiB

sparklers

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

#define int long long

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

vector<int> calcCumu(vector<int> v) {
    vector<int> ans={0};
    int somCour=0;
    for (int i:v) {
        somCour+=i;
        ans.push_back(somCour);
    }
    return ans;
}

bool verif(int temps) {
    vector<int> listeGau,listeDro;
    for (int i=posInit;i>1;i--) {
        listeGau.push_back(2*temps-val[i]+val[i-1]);
    }
    for (int i=posInit+1;i<=nbVal;i++) {
        listeDro.push_back(2*temps-val[i]+val[i-1]);
    }
    vector<int> cumuGau=calcCumu(listeGau),cumuDro=calcCumu(listeDro);
    int tailleGau=cumuGau.size(),tailleDro=cumuDro.size();

    int minCour=INFINI*INFINI,maxCour=-INFINI*INFINI,posMax=0;
    vector<pair<int,int>> maxJusquaGau,maxDepuisGau;
    vector<int> minJusquaGau,minDepuisGau;
    for (int i=0;i<tailleGau;i++) {
        if (minCour>cumuGau[i]) {
            minCour=cumuGau[i];
        }
        if (maxCour<cumuGau[i]) {
            maxCour=cumuGau[i];
            posMax=i;
        }
        minJusquaGau.push_back(minCour);
        maxJusquaGau.push_back({maxCour,posMax});
    }
    minCour=INFINI*INFINI;
    maxCour=-INFINI*INFINI;
    for (int i=tailleGau-1;i>=0;i--) {
        if (minCour>cumuGau[i]) {
            minCour=cumuGau[i];
        }
        if (maxCour<cumuGau[i]) {
            maxCour=cumuGau[i];
            posMax=i;
        }
        minDepuisGau.push_back(minCour);
        maxDepuisGau.push_back({maxCour,posMax});
    }
    reverse(minDepuisGau.begin(),minDepuisGau.end());
    reverse(maxDepuisGau.begin(),maxDepuisGau.end());

    minCour=INFINI*INFINI;
    maxCour=-INFINI*INFINI;
    vector<pair<int,int>> maxJusquaDro,maxDepuisDro;
    vector<int> minJusquaDro,minDepuisDro;
    for (int i=0;i<tailleDro;i++) {
        if (minCour>cumuDro[i]) {
            minCour=cumuDro[i];
        }
        if (maxCour<cumuDro[i]) {
            maxCour=cumuDro[i];
            posMax=i;
        }
        minJusquaDro.push_back(minCour);
        maxJusquaDro.push_back({maxCour,posMax});
    }
    minCour=INFINI*INFINI;
    maxCour=-INFINI*INFINI;
    for (int i=tailleDro-1;i>=0;i--) {
        if (minCour>cumuDro[i]) {
            minCour=cumuDro[i];
        }
        if (maxCour<cumuDro[i]) {
            maxCour=cumuDro[i];
            posMax=i;
        }
        minDepuisDro.push_back(minCour);
        maxDepuisDro.push_back({maxCour,posMax});
    }
    reverse(minDepuisDro.begin(),minDepuisDro.end());
    reverse(maxDepuisDro.begin(),maxDepuisDro.end());

    int valMinGau=minJusquaGau.back(),valMaxGau=maxJusquaGau.back().first,posMaxGau=maxJusquaGau.back().second;
    int valMinDro=minJusquaDro.back(),valMaxDro=maxJusquaDro.back().first,posMaxDro=maxJusquaDro.back().second;
    if (valMinGau+valMaxDro<0 or valMinDro+valMaxGau<0) {
        return false;
    }
    int posGau=posMaxGau-1,posDro=posMaxDro-1;
    while (posGau>=0 and posDro>=0) {
        if (maxJusquaGau[posGau].first+minJusquaDro[posDro]>=0) {
            posGau=maxJusquaGau[posGau].second-1;
        }
        else if (maxJusquaDro[posDro].first+minJusquaGau[posGau]>=0) {
            posDro=maxJusquaDro[posDro].second-1;
        }
        else {
            return false;
        }
    } 

    posGau=posMaxGau+1;
    posDro=posMaxDro+1;
    while (posGau<tailleGau and posDro<tailleDro) {
        //cout<<posGau<<" "<<posDro<<endl;
        if (maxDepuisGau[posGau].first+minDepuisDro[posDro]>=0) {
            posGau=maxDepuisGau[posGau].second+1;
        }
        else if (maxDepuisDro[posDro].first+minDepuisGau[posGau]>=0) {
            posDro=maxDepuisDro[posDro].second+1;
        }
        else {
            return false;
        }
    } 
    return true;
}

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];
    }
    verif(23437500);
    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: 50 / 50