QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #694877 | #7744. Elevator | konghaojie# | TL | 1ms | 5112kb | C++17 | 2.5kb | 2024-10-31 18:52:17 | 2024-10-31 18:52:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+5;
int f[N][2];
void init(){
for(int i=0;i<N;i++){
f[i][0]=f[i][1]=0;
}
}
void solve(){
int n,k;cin>>n>>k;
set<int>st1,st2;
for(int i=0;i<n;i++){
int c,w,f0;cin>>c>>w>>f0;
f[f0][w-1]+=c;
if(w==1) st1.insert(f0);
else st2.insert(f0);
}
int ans=0;
stack<int>St1,St2;
for(auto x:st1){
St1.push(x);
}
for(auto x:st2){
St2.push(x);
}
while(!St1.empty()||!St2.empty()){
// cout<<"ok1"<<endl;
if(St2.empty()||(!St1.empty()&&St1.top()>St2.top())){
// cout<<"o1"<<endl;
int num1=St1.top();
St1.pop();
int cnt1=f[num1][0];
int c=cnt1/k;
if(cnt1%k!=0) c++;
int res=c*k-cnt1;
ans+=c*num1;
f[num1][0]=0;
while(res>0){
if((res==1&&St1.empty())||(St1.empty()&&St2.empty())) break;
if(St2.empty()||(!St1.empty()&&St1.top()>St2.top())){
int num1=St1.top();
if(res>=f[num1][0]){
res-=f[num1][0];
f[num1][0]=0;
St1.pop();
}else{
f[num1][0]-=res;
res=0;
}
}else{
int d=res/2;
int num2=St2.top();
if(d>=f[num2][1]){
res-=f[num2][1]*2;
f[num2][1]=0;
St2.pop();
}else{
f[num2][1]-=d;
res%=2;
}
}
}
// cout<<"o2"<<endl;
}else{
// cout<<"o3"<<endl;
int num2=St2.top();
St2.pop();
int cnt2=f[num2][1];
int k0=k/2;
int c=cnt2/k0;
if(cnt2%k0!=0) c++;
int res=c*k-cnt2*2;
ans+=c*num2;
f[num2][1]=0;
while(res>0){
// cout<<"k1"<<endl;
if((res==1&&St1.empty())||(St1.empty()&&St2.empty())) break;
if(St2.empty()||(!St1.empty()&&St1.top()>St2.top())){
// cout<<"d1"<<endl;
// if(St1.empty()){
// cout<<"no"<<endl;
// }
int num1=St1.top();
if(res>=f[num1][0]){
res-=f[num1][0];
f[num1][0]=0;
St1.pop();
}else{
f[num1][0]-=res;
res=0;
}
// cout<<"d2"<<endl;
}else{
// cout<<"d3"<<endl;
int d=res/2;
int num2=St2.top();
if(d>=f[num2][1]){
res-=f[num2][1]*2;
f[num2][1]=0;
St2.pop();
}else{
f[num2][1]-=d;
res%=2;
}
// cout<<"d4"<<endl;
}
// cout<<"k2"<<endl;
}
// cout<<"o4"<<endl;
}
// cout<<"ok2"<<endl;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
init();
cin>>t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5112kb
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...