QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #521736 | #6606. The Boomsday Project | Monkey_Lee | TL | 0ms | 8188kb | C++20 | 839b | 2024-08-16 14:19:56 | 2024-08-16 14:19:57 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int maxn=505;
const int maxs=300500;
int n,m;
long long r,c[maxn];
int d[maxn],k[maxn];
int st[maxs],top=0,p,q;
int to[maxn*maxs];
long long f[maxs];
int main()
{
scanf("%d%d%lld",&n,&m,&r);
for(int i=1;i<=n;i++)
scanf("%d%d%lld",&d[i],&k[i],&c[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p,&q);
while(q--)
st[++top]=p;
}
sort(st+1,st+top+1);
for(int j=1;j<=n;j++)
{
int pt=1;
for(int i=0;i<top;i++)
{
while(pt<top&&pt+1-i<=k[j]&&st[pt+1]-st[i+1]+1<=d[j])
pt++;
to[i*n+j]=pt;
}
}
memset(f,31,sizeof(f));f[0]=0;
for(int i=0;i<top;i++)
{
f[i+1]=min(f[i+1],f[i]+r);
for(int j=1;j<=n;j++)
f[to[i*n+j]]=min(f[to[i*n+j]],f[i]+c[j]);
}
printf("%lld\n",f[top]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7112kb
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: 0ms
memory: 8188kb
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: -100
Time Limit Exceeded
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