QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#640942 | #6606. The Boomsday Project | rerebornzhou | TL | 0ms | 3552kb | C++20 | 1.5kb | 2024-10-14 17:04:22 | 2024-10-14 17:04:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define ull unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
const int N=1e6+10;
const int INF=1e18;
struct node{
int p,q;
};
map<int,int> mp;
void solve(){
int n,m,r;
cin>>n>>m>>r;
mp.clear();
vector<int> d(n+1),k(n+1),c(n+1);
for(int i=1;i<=n;i++){
cin>>d[i]>>k[i]>>c[i];
}
vector<node> a(m+1);
int sq=0;
for(int i=1;i<=m;i++){
cin>>a[i].p>>a[i].q;
sq+=a[i].q;
}
sort(a.begin(),a.end(),[&](node a,node b){ return a.p<b.p;});
vector<int> day(sq+1);
int last=0;
for(int i=1;i<=m;i++){
for(int j=last+1;j<=last+a[i].q;j++){
day[j]=a[i].p;
}
last=last+a[i].q;
mp[a[i].p]=last;
}
vector<int> f(sq+1,INF);
vector<vector<int>> pre(sq+1,vector<int>(n+1));
for(int i=1;i<=sq;i++){
for(int j=1;j<=n;j++){
pre[i][j]=mp[day[i]-d[j]];
}
}
f[0]=0;
for(int i=1;i<=sq;i++){
f[i]=f[i-1]+r;
for(int j=1;j<=n;j++){
f[i]=min({f[i],f[max(i-k[j],pre[i][j])]+c[j]});
// cout<<i<<" "<<day[i]<<" "<<d[j]<<" "<<mp[day[i]-d[j]]<<" "<<i-k[j]<<"\n";
}
}
cout<<f[sq]<<"\n";
}
signed main(){
int _=1;
// cin>>_;
while(_--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 3552kb
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 ...