QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#486880 | #8707. Jobs | Physics212303 | 0 | 0ms | 0kb | C++17 | 751b | 2024-07-22 10:14:55 | 2024-07-22 10:14:57 |
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%