Submission #1075575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075575		oscar1f	Trains (BOI24_trains)	C++17	100 / 100	610 ms	363328 KiB

Main

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

#define int long long

const int TAILLE_MAX=100*1000+5,MAX_LIM=400,MODU=1000*1000*1000+7;
int nbVal,limite;
vector<int> cumu[MAX_LIM][MAX_LIM];
int duree[TAILLE_MAX],nbTraj[TAILLE_MAX];
int rep[TAILLE_MAX];


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal;
    for (int i=1;i<=nbVal;i++) {
        cin>>duree[i]>>nbTraj[i];
        if (duree[i]==0) {
            duree[i]=MODU;
        }
    }
    limite=sqrt(nbVal);
    for (int i=1;i<limite;i++) {
        for (int j=0;j<i;j++) {
            cumu[i][j].push_back(0);
        }
    }
    for (int i=nbVal;i>=1;i--) {
        if (duree[i]>=limite) {
            for (int j=i;j<=min(nbVal,i+duree[i]*nbTraj[i]);j+=duree[i]) {
                rep[i]+=rep[j];
            }
        }
        else if (i+duree[i]*nbTraj[i]>=nbVal) {
            rep[i]=cumu[duree[i]][i%duree[i]].back();
        }
        else {
            rep[i]=cumu[duree[i]][i%duree[i]].back()-cumu[duree[i]][i%duree[i]][cumu[duree[i]][i%duree[i]].size()-nbTraj[i]-1];
        }
        rep[i]+=MODU+1;
        rep[i]%=MODU;
        for (int j=1;j<limite;j++) {
            cumu[j][i%j].push_back(cumu[j][i%j].back()+rep[i]);
        }
        //cout<<i<<" : "<<rep[i]<<endl;
    }
    cout<<rep[1]<<endl;
    return 0;
}
 

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29