Submission #1095011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095011		epicci23	Trains (BOI24_trains)	C++17	100 / 100	211 ms	9036 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int MOD = 1e9 + 7;

int add(int a,int b){
  if(a+b>=MOD) return a+b-MOD;
  return a+b;
}

int mult(int a,int b){
  if(a*b>=MOD) return a*b%MOD;
  return a*b;
}

int eks(int a,int b){
  if(a>=b) return a-b;
  return a-b+MOD;
}

const int BL = 400;

void _(){
  int n; cin >> n;
  array<int,2> ar[n+5];
  int dp[n+5];
  vector<int> Remove[n+5];
  memset(dp,0,sizeof(dp));
  for(int i=1;i<=n;i++) cin >> ar[i][0] >> ar[i][1];
  
  for(int i=1;i<=n;i++){
  	if(!ar[i][0] || !ar[i][1]) continue;
  	if(ar[i][0]>=BL) continue;
  	if(i+ar[i][0]*ar[i][1]<=n) Remove[i+ar[i][0]*ar[i][1]].push_back(i);
  }

  int pre[BL][BL];
  memset(pre,0,sizeof(pre));

  for(int i=n;i>=1;i--){ // DONT FORGET TO UPDATE PREFIX ARRAY!!!!
    int a,b;
    for(int x:Remove[i]){
      a=ar[x][0],b=ar[x][1];
      dp[x]=eks(dp[x],pre[a][x%a]);
    }
  	a=ar[i][0],b=ar[i][1];
  	if(ar[i][0]==0 || ar[i][1]==0) dp[i]=1;
    else if(a>=BL){
      for(int j=1;j<=b;j++){
      	int u=i+j*a;
      	if(u>n) break;
      	dp[i]=add(dp[i],dp[u]);
      }
      dp[i]=add(dp[i],1LL);
    }
    else{
      dp[i]=add(dp[i],pre[a][i%a]);
      dp[i]=add(dp[i],1LL);
    }
    //cout << "finished: " << i << ' ' << dp[i] << '\n';
  	for(int j=1;j<BL;j++) pre[j][i%j]=add(pre[j][i%j],dp[i]);	
  }
  cout << dp[1] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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