Submission #1063589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063589		oscar1f	Sparklers (JOI17_sparklers)	C++17	50 / 100	30 ms	15452 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];
int dv[TAILLE_MAX][TAILLE_MAX],pb[TAILLE_MAX][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;
}

void DFS(int lig,int col) {
    if (pb[lig][col]==0 and dv[lig][col]==0) {
        dv[lig][col]=1;
        DFS(lig+1,col);
        DFS(lig,col+1);
    }
} 

bool verif(int temps) {
    //cout<<temps<<endl;
    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();
    for (int i=0;i<=tailleGau;i++) {
        for (int j=0;j<=tailleDro;j++) {
            pb[i][j]=1;
            dv[i][j]=0;
        }
    }
    for (int i=0;i<tailleGau;i++) {
        for (int j=0;j<tailleDro;j++) {
            if (cumuGau[i]+cumuDro[j]>=0) {
                pb[i][j]=0;
            }
        }
    }
    /*for (int i:cumuGau) {
        for (int j:cumuDro) {
            if (i+j>=0) {
                cout<<1<<" ";
            }
            else {
                cout<<0<<" ";
            }
        }
        cout<<endl;
    } 
    cout<<endl;*/
    DFS(0,0);
    return (dv[tailleGau-1][tailleDro-1]==1);
}

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