Submission #1264842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264842		ivopav	Trains (BOI24_trains)	C++20	100 / 100	419 ms	319492 KiB

Main

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

using i64=long long int;

int main(){
    i64 kor=400;
    i64 mod=1e9+7;
    i64 n;
    cin >> n;
    vector<i64> comb(n,0);
    vector<vector<i64>> kolzbr(kor,vector<i64>(kor,0)); 
    vector<vector<i64>> kolzbrmak(n,vector<i64>(kor,0)); 
    i64 rje=0;
    comb[0]=1;
    for (i64 i=0;i<n;i++){
        i64 unos;
        i64 unos2;
        cin >> unos >> unos2;
        //cout << "a\n";

        for (i64 j=1;j<kor;j++){
            i64 pom=i%j;
          //  cout << i << " " << j << " " << pom << "\n";
           // cout << kolzbr[j][pom] << " " << kolzbrmak[i][j] << "\n";
            comb[i]+=kolzbr[j][pom];
            comb[i]%=mod;
            kolzbr[j][pom]+=kolzbrmak[i][j];
            kolzbr[j][pom]%=mod;
            
            
        }
        //cout << "b\n";
        if (unos*unos2==0){
     //       cout << comb[i] << "\n";
            rje+=comb[i];
            rje%=mod;
            continue;
        }
        if (unos>=kor){
            i64 kol=0;
            for (i64 j=i+unos;j<n && kol<unos2;j+=unos,kol++){
             //   cout << i << " " << j << "-=-\n";
                comb[j]+=comb[i];
                comb[j]%=mod;
            }
        }
        else {
            i64 indkra=i+unos*unos2;
            if (indkra<n){
                kolzbrmak[indkra][unos]-=comb[i];
                kolzbrmak[indkra][unos]+=mod;
                kolzbrmak[indkra][unos]%=mod;
                
                
            }
            kolzbr[unos][i%unos]+=comb[i];
            kolzbr[unos][i%unos]%=mod;
        }
        //cout << "c\n";
      //  cout << comb[i] << "\n";
        rje+=comb[i]; 
        rje%=mod;
    }
    cout << rje << "\n";

}

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