oj.uz

답안 #1052912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052912 2024-08-11T05:54:23 Z vjudge1 Trains (BOI24_trains) C++17
42 / 100
 412 ms 288040 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]);
	}
      
      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 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4024 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 3928 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 3932 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 1 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 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4024 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 3928 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 3932 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 1 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 Incorrect 47 ms 29044 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Incorrect 33 ms 23220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 145736 KB Output is correct
2 Correct 171 ms 125392 KB Output is correct
3 Correct 412 ms 287948 KB Output is correct
4 Correct 290 ms 213452 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 51 ms 35352 KB Output is correct
8 Correct 408 ms 288040 KB Output is correct

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4024 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 3928 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 3932 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 1 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 Incorrect 47 ms 29044 KB Output isn't correct
21 Halted 0 ms 0 KB -