QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#640942#6606. The Boomsday ProjectrerebornzhouTL 0ms3552kbC++201.5kb2024-10-14 17:04:222024-10-14 17:04:28

Judging History

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

  • [2024-10-14 17:04:28]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3552kb
  • [2024-10-14 17:04:22]
  • 提交

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
...

output:


result: