QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#174593 | #6606. The Boomsday Project | LFCode | WA | 525ms | 55120kb | C++14 | 1.3kb | 2023-09-10 10:35:04 | 2023-09-10 10:35:05 |
Judging History
answer
#include<cstdio>
#define lg(x) (31-__builtin_clz(x))
#define llg(x) (63-__builtin_clzll(x))
#define int long long
const int N=300086,INF=1e18+7;
int n,m,r,tot,a[N],np[N],f[N];
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
struct cinf{int d,k,c,mn;}c[N];
struct STList{
int sze,a[N][20];
STList(){sze=0;}
bool push(int x){
a[++sze][0]=x;
for(int i=1;(1<<i)<=sze;i++)
a[sze][i]=Min(a[sze][i-1],a[sze-(1<<(i-1))][i-1]);
return true;
}
int query(int l,int r){
if(l>r)return INF;if(l<1)return 0;if(r>sze)r=sze;int lo=llg(r-l+1);
return Min(a[r][lo],a[l+(1<<lo)-1][lo]);
}
}rmq;
int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
signed main(){
n=read();m=read();r=read();
for(int i=1;i<=n;i++){c[i].d=read();c[i].k=read();c[i].c=read();np[i]=1;}
for(int i=1;i<=m;i++){
int p=read();int q=read();
for(int j=1;j<=q;j++)a[++tot]=p;
}
for(int i=1;i<=tot;i++){
f[i]=f[i-1]+r;
for(int j=1;j<=n;j++){
int pos=i-c[j].k+1;pos=Max(pos,1);
while(a[np[j]]<a[i]-c[j].d+1)np[j]++;
pos=Max(np[j],pos);
f[i]=Min(f[i],rmq.query(pos-1,i-1)+c[j].c);
}
rmq.push(f[i]);
}
printf("%lld",f[tot]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7672kb
input:
2 1 10 1 3 12 1 2 9 1 10
output:
42
result:
ok 1 number(s): "42"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7656kb
input:
2 4 10 1 3 12 1 2 9 1 3 2 3 3 3 4 1
output:
45
result:
ok 1 number(s): "45"
Test #3:
score: 0
Accepted
time: 511ms
memory: 54844kb
input:
500 100 1000 95 20 20892 73 627 55354 52 747 1404314 19 676 597007 65 814 1569851 91 397 691575 81 4 4575 97 382 624404 21 197 201850 67 799 643576 27 895 1510533 3 800 552439 49 954 1149851 70 892 676406 82 882 1348956 1 318 324094 43 238 439111 94 397 471003 16 119 130686 1 637 77731 79 292 35234 ...
output:
450790
result:
ok 1 number(s): "450790"
Test #4:
score: 0
Accepted
time: 525ms
memory: 54904kb
input:
500 100 1000 8 910 1405086 65 931 697221 73 534 1051699 74 13 7497 64 631 991592 79 481 511568 92 892 477132 91 588 842013 21 389 750794 19 955 1333270 85 889 1334457 46 295 505372 83 486 449366 67 67 119659 82 446 408487 25 736 319997 31 889 23280 1 41 74813 93 928 1189573 88 468 455471 7 10 18865 ...
output:
3276270
result:
ok 1 number(s): "3276270"
Test #5:
score: 0
Accepted
time: 474ms
memory: 53652kb
input:
500 100 1000 35 122 153490 71 121 27207 73 967 409546 88 325 182835 37 602 533155 61 546 114146 70 359 251186 64 429 591088 63 445 428802 81 819 408704 49 364 244867 64 937 1422956 98 505 713891 1 454 61697 91 673 116038 89 463 123737 67 724 1061372 31 1 1838 73 127 173419 72 122 8068 55 928 65539 3...
output:
762564
result:
ok 1 number(s): "762564"
Test #6:
score: -100
Wrong Answer
time: 515ms
memory: 55120kb
input:
500 100 1000 77 590 825100 67 901 1633566 29 703 886708 86 223 168970 6 676 1162365 46 669 1308904 73 96 125961 37 529 774376 79 741 516927 95 835 602321 25 208 384673 16 20 12510 41 226 164928 68 836 1412302 52 689 418717 40 481 789905 10 838 220638 35 846 885451 54 736 1470524 13 490 224433 12 354...
output:
301385
result:
wrong answer 1st numbers differ - expected: '300840', found: '301385'