100 Accepted
time_space_table: /1577/shuttle.1.in:AC mem=3352k time=4ms /1577/shuttle.10.in:AC mem=3352k time=25ms /1577/shuttle.11.in:AC mem=3352k time=59ms /1577/shuttle.12.in:AC mem=3352k time=58ms /1577/shuttle.13.in:AC mem=3352k time=61ms /1577/shuttle.14.in:AC mem=3352k time=50ms /1577/shuttle.15.in:AC mem=3352k time=56ms /1577/shuttle.16.in:AC mem=3352k time=53ms /1577/shuttle.17.in:AC mem=3352k time=3ms /1577/shuttle.2.in:AC mem=3352k time=3ms /1577/shuttle.3.in:AC mem=3352k time=5ms /1577/shuttle.4.in:AC mem=3352k time=3ms /1577/shuttle.5.in:AC mem=3352k time=3ms /1577/shuttle.6.in:AC mem=3352k time=3ms /1577/shuttle.7.in:AC mem=3352k time=6ms /1577/shuttle.8.in:AC mem=3352k time=8ms /1577/shuttle.9.in:AC mem=3352k time=14ms
代码
#include<bits/stdc++.h>
#define int long long
// #define MOD 1000000007
using namespace std;
int k,n,c;
struct node{
int l,r,x;
}a[50005];
struct cmp2{
bool operator ()(node a,node b){
return a.r<b.r;
}
};
bool cmp(node a,node b){return a.l<b.l;}
multiset<node,cmp2>s;
signed main(){
cin>>k>>n>>c;
for(int i=1;i<=k;i++)
cin>>a[i].l>>a[i].r>>a[i].x;
sort(a+1,a+k+1,cmp);
int tot=1,siz=0,ans=0;
for(int i=1;i<=n;i++){
while(a[tot].l==i&&tot<=k){
s.insert(a[tot]);
siz+=a[tot].x;
tot++;
}
while(!s.empty()&&s.begin()->r==i){
siz-=s.begin()->x;
ans+=s.begin()->x;
s.erase(s.begin());
}
while(siz>c){
multiset<node,cmp2>::iterator it=--s.end();
node t=*it;
s.erase(it);
if(siz-c>t.x)siz-=t.x;
else t.x-=siz-c,s.insert(t),siz=c;
}
}
cout<<ans;
return 0;
}
信息
- 递交者
- 题目
- P1577 [Usaco2009 Feb]庙会捷运Fair Shuttle
- 语言
- C++
- 代码长度
- 1 KiB
- 递交时间
- 2022-12-4 13:54:07
- 评测时间
- 2023-12-17 23:47:34
- 分数
- 100
- 总耗时
- 414ms
- 峰值内存
- 3.3 MiB