Submission #1022035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022035		huutuan	Trains (BOI24_trains)	C++14	100 / 100	103 ms	6740 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10, S=320, mod=1e9+7;
int d[S][S], f[N];
int a[N], b[N], n;
vector<pair<pair<int, int>, int>> v[N];

void add(int &x, int y){
   x=x+y>=mod?x+y-mod:x+y;
}

void sub(int &x, int y){
   x=x<y?x-y+mod:x-y;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i] >> b[i];
   f[1]=1;
   for (int i=1; i<=n; ++i){
      for (int j=1; j<S; ++j) add(f[i], d[j][i%j]);
      f[i]%=mod;
      for (auto &j:v[i]) sub(d[j.first.first][j.first.second], j.second);
      if (!a[i] || !b[i]) continue;
      if (a[i]<S){
         add(d[a[i]][i%a[i]], f[i]);
         if (i+1ll*a[i]*b[i]<=n) v[i+1ll*a[i]*b[i]].push_back({{a[i], i%a[i]}, f[i]});
      }else{
         for (int j=i+a[i], k=1; j<=n && k<=b[i]; j+=a[i], ++k) add(f[j], f[i]);
      }
   }
   int ans=0;
   for (int i=1; i<=n; ++i) add(ans, f[i]);
   cout << ans << '\n';
   return 0;
}

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