QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#486880#8707. JobsPhysics2123030 0ms0kbC++17751b2024-07-22 10:14:552024-07-22 10:14:57

Judging History

你现在查看的是最新测评结果

  • [2024-07-22 10:14:57]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-07-22 10:14:55]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
inline int add(int x,int y){
  int s=x+y; if(s>=p)s-=p; return s;
}
inline void chadd(int &x,int y){
  if((x+=y)>=p)x-=p;
}
main(){
  ios::sync_with_stdio(false);
  int n,sq; cin>>n,sq=sqrt(n);
  vector<int> d(n),x(n),f(n,1);
  for(int i=0;i<n;i++)
    cin>>d[i]>>x[i];
  vector r(n,vector<int>(sq));
  for(int i=n-1;~i;i--){
    if(d[i]<sq){
      if(int y=i+d[i]*(x[i]+1);i+d[i]<n)
        chadd(f[i],add(r[i+d[i]][d[i]],y<n?p-r[y][d[i]]:0));
    }
    else for(int j=i+d[i];j<n&&j<=i+d[i]*x[i];j+=d[i])
      chadd(f[i],f[j]);
    for(int j=1;j<sq;j++)
      r[i][j]=add(i+j<n?r[i+j][j]:0,f[i]);
  }
  cout<<f[0]<<endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Memory Limit Exceeded

Test #1:

score: 0
Memory Limit Exceeded

input:

299955 1000000000000000000
-2 0
10 1
-9 2
14 3
-11 4
17 5
-21 6
22 7
-22 8
23 9
-41 10
-89 10
49 11
99 12
-120 14
-23 8
130 15
24 16
-51 13
55 19
-144 20
-24 18
-30 18
-54 13
64 24
-105 14
145 21
-60 20
-183 25
61 28
-334 30
340 31
111 26
-135 33
-184 33
191 35
-231 17
-505 27
-570 32
-257 25
238 37...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #14:

score: 0
Runtime Error

input:

17 5
-3 0
4 1
-4 2
9 3
-5 4
13 5
-6 6
8 7
-23 8
28 9
-26 10
31 11
-28 12
33 13
-39 14
41 15
-7 16

output:


result:


Subtask #3:

score: 0
Memory Limit Exceeded

Test #42:

score: 0
Memory Limit Exceeded

input:

300000 0
-1677 0
1678 1
-3010 2
3011 3
-8141 4
8142 5
-11233 6
11234 7
-14400 8
14401 9
-17045 10
17046 11
-19521 12
19522 13
-23178 14
23179 15
-26907 16
26908 17
-28884 18
28885 19
-30742 20
30743 21
-35957 22
35958 23
-38436 24
38437 25
-39739 26
39740 27
-42432 28
42433 29
-47866 30
47867 31
-48...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%