Submission #1120816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120816		ntdaccode	Trains (BOI24_trains)	C++17	100 / 100	387 ms	162104 KiB

Main

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 1e6 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
const int SIZE = 150;

int n, d[M], x[M], f[M];
vector<int> sum[SIZE + 10][SIZE + 10];

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  if(fopen("1.inp","r")) {
    freopen("1.inp","r",stdin);
    freopen("1.ans","w",stdout);
  }

  #define task ""
  if(fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n;
  for(int i = 1;i <= n; i++) {
      cin >> d[i] >> x[i];
      f[i] = 1;
  }

  for(int i = 1;i <= SIZE; i++) {
    for(int j = 0;j <= i - 1; j++) {
        sum[j][i].pb(0);
    }
  }

  for(int i = n; i != 0; i--) {
      if(d[i] != 0) {
        if(d[i] > SIZE) {
            int cnt = 1;
            for(int j = i + d[i]; j <= n; j += d[i]) {
                if(cnt > x[i]) break;
                f[i] = (f[i] + f[j]) % mod;
                cnt++;
            }
            //cout << i <<  " ";
        }
        else {
           // cout << "A";
          int du = i % d[i];
          int sz = sum[du][d[i]].size();
          int lim = sz - 1 - min(x[i],sz - 1);
          f[i] = (f[i] + sum[du][d[i]].back() - sum[du][d[i]][lim] + mod) % mod;
        }
      }
      for(int j = 1;j <= SIZE; j++) {
          int du = i % j;
          sum[du][j].pb( (sum[du][j].back() + f[i]) % mod);
      }
  }
  cout << f[1] % mod;
  //cerr << (float)clock()/CLOCKS_PER_SEC << "\n";


}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("1.ans","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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