QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#698338 | #7744. Elevator | Everlasting Journey (Tianshu Li, Luhanming Yao, Keyan Dong) | TL | 0ms | 3820kb | C++20 | 3.5kb | 2024-11-01 18:59:19 | 2024-11-01 18:59:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int V = 5010;
const int E = 100100;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k,p;
void __(){
scanf("%lld%lld",&n,&m);
map<ll,ll> mp1,mp2;
for(int i=1;i<=n;i++){
int c,w,f;
scanf("%d%d%d",&c,&w,&f);
if(w==1) mp1[f]+=c;
else mp2[f]+=c;
}
vector<PII> v1,v2;
vector<int> vx;
for(auto [u,v]:mp1) v1.push_back({u,v});
for(auto [u,v]:mp2) v2.push_back({u,v});
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
ll ans=0;
while(v1.size()&&v2.size()){
auto u=v1.back(),v=v2.back();
if(u.first<=v.first){
ll cnt=m/2;
ans+=v2.back().second/cnt*v2.back().first;
v2.back().second%=cnt;
}else{
ll cnt=m;
ans+=v1.back().second/cnt*v1.back().first;
v1.back().second%=cnt;
}
ll need=m;
ll res=0;
while(v1.size()&&v2.size()){
auto &u=v1.back(),&v=v2.back();
if(need>=2&&u.first<=v.first){
if(v.second*2<=need){
need-=v.second*2;
ans=max(ans,v.first);
v2.pop_back();
}else{
v.second-=need/2;
need%=2;
ans=max(ans,v.first);
}
}else{
if(u.second<=need){
need-=u.second;
ans=max(ans,u.first);
v1.pop_back();
}else{
u.second-=need;
need=0;
ans=max(ans,u.first);
}
}
}
while(need>1&&v2.size()){
auto &v=v2.back();
if(v.second*2<=need){
need-=v.second*2;
ans=max(ans,v.first);
v2.pop_back();
}else{
v.second-=need/2;
need%=2;
ans=max(ans,v.first);
}
}
while(need>0&&v1.size()){
if(u.second<=need){
need-=u.second;
ans=max(ans,u.first);
v1.pop_back();
}else{
u.second-=need;
need=0;
ans=max(ans,u.first);
}
}
}
while(v2.size()){
ans+=v2.back().first;
ll need=m;
while(need>1&&v2.size()){
auto &v=v2.back();
if(v.second*2<=need){
need-=v.second*2;
ans=max(ans,v.first);
v2.pop_back();
}else{
v.second-=need/2;
need%=2;
ans=max(ans,v.first);
}
}
}
while(v1.size()){
ans+=v1.back().first;
ll need=m;
while(need>0&&v1.size()){
auto &u=v1.back();
if(u.second<=need){
need-=u.second;
ans=max(ans,u.first);
v1.pop_back();
}else{
u.second-=need;
need=0;
ans=max(ans,u.first);
}
}
}
printf("%lld\n",ans);
}
int main(){
int _;
cin>>_;
while(_--){
__();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
2 4 6 1 1 8 7 2 5 1 1 7 3 2 6 8 1200000 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345
output:
24 100000
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
5501 8 104 5 2 3 6 2 4 5 2 3 6 2 9 8 2 4 2 1 3 7 2 4 8 2 8 1 290 3 1 1 12 12 6 1 2 1 2 2 1 1 2 1 2 4 6 1 1 1 2 5 6 1 4 4 1 4 6 2 4 6 2 5 4 2 5 4 1 4 5 334 1 1 4 1 2 3 4 2 1 5 1 1 2 1 2 13 218 5 2 3 5 1 4 1 2 1 1 2 5 3 2 2 1 1 3 4 2 2 1 2 5 2 2 1 2 1 5 3 2 1 5 2 1 1 1 4 10 260 7 2 1 5 1 1 5 2 4 6 1 6...