oj.uz

답안 #1052918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052918 2024-08-11T05:57:39 Z vjudge1 Trains (BOI24_trains) C++17
58 / 100
 474 ms 288128 KB 
#include<bits/stdc++.h>

using namespace std;

const int mod = 1'000'000'007;
const int SQ = 300, N = 100'000 + 5;
vector<int> chains[SQ][SQ];
int n, d[N], x[N], cnt[N], tnt[N][SQ];

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

  for(int i = n; i >= 1; i --)
      for(int j = 1; j < SQ; j++)
	chains[j][i % j].push_back(i);

  cnt[1] = 1;
  int ans = 0;

  for(int i = 1; i <= n; i ++)
    {
      for(int j = 1; j < SQ; j++)
	cnt[i] = (cnt[i] + tnt[i][j]) % mod;
      ans = (ans + cnt[i]) % mod;

      for(int j = 1; j < SQ; j++)
	{
	  chains[j][i % j].pop_back();
	  if(chains[j][i % j].size())
	    tnt[i + j][j] = (tnt[i + j][j] + tnt[i][j]) % mod;
	}
      
      if(d[i] == 0) continue;

      if(d[i] >= SQ)
	{
	  for(int k = i + d[i]; k <= n; k += d[i])
	    cnt[k] = (cnt[i] + cnt[k]) % mod;
	}
      else
	{
	  x[i] = min(x[i], (n - i) / d[i]) + 1;
	  if(chains[d[i]][i % d[i]].size())
	    tnt[i + d[i]][d[i]] = (tnt[i + d[i]][d[i]] + cnt[i]) % mod;
	  if(x[i] * d[i] + i <= n)
	    tnt[x[i] * d[i] + i][d[i]] = (tnt[x[i] * d[i] + i][d[i]] + mod - cnt[i]) % mod;
	}
    }
  
  cout << ans << endl;
  return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 1 ms 4000 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 2 ms 3928 KB Output is correct
17 Correct 1 ms 3932 KB Output is correct
18 Correct 1 ms 3932 KB Output is correct
19 Correct 1 ms 3932 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 1 ms 4000 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 2 ms 3928 KB Output is correct
17 Correct 1 ms 3932 KB Output is correct
18 Correct 1 ms 3932 KB Output is correct
19 Correct 1 ms 3932 KB Output is correct
20 Correct 44 ms 29004 KB Output is correct
21 Incorrect 21 ms 13148 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 36 ms 23440 KB Output is correct
3 Correct 28 ms 17728 KB Output is correct
4 Correct 47 ms 29780 KB Output is correct
5 Correct 341 ms 231500 KB Output is correct
6 Correct 465 ms 287944 KB Output is correct
7 Correct 474 ms 287940 KB Output is correct
8 Correct 1 ms 3928 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 57 ms 34604 KB Output is correct
12 Correct 446 ms 288060 KB Output is correct
13 Correct 1 ms 3932 KB Output is correct
14 Correct 58 ms 34584 KB Output is correct
15 Correct 466 ms 288128 KB Output is correct

Subtask #4
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 144588 KB Output is correct
2 Correct 194 ms 124712 KB Output is correct
3 Correct 466 ms 287952 KB Output is correct
4 Correct 336 ms 212944 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 54 ms 34456 KB Output is correct
8 Correct 447 ms 288108 KB Output is correct

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 1 ms 3928 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 1 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 1 ms 4000 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 2 ms 3928 KB Output is correct
17 Correct 1 ms 3932 KB Output is correct
18 Correct 1 ms 3932 KB Output is correct
19 Correct 1 ms 3932 KB Output is correct
20 Correct 44 ms 29004 KB Output is correct
21 Incorrect 21 ms 13148 KB Output isn't correct
22 Halted 0 ms 0 KB -