QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698338#7744. ElevatorEverlasting Journey (Tianshu Li, Luhanming Yao, Keyan Dong)TL 0ms3820kbC++203.5kb2024-11-01 18:59:192024-11-01 18:59:19

Judging History

This is the latest submission verdict.

  • [2024-11-01 18:59:19]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3820kb
  • [2024-11-01 18:59:19]
  • Submitted

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

output:


result: