QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665037 | #7744. Elevator | D06 | AC ✓ | 69ms | 5976kb | C++14 | 1.9kb | 2024-10-22 01:00:55 | 2024-10-22 01:00:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct t1
{
long long c,w,f;
}t[100005];
bool cmp(t1 a,t1 b)
{
return a.f>b.f;
}
long long ans,k;
long long cur,n;
void solve(int i,long long l,bool f)
{
// cout<<i<<" "<<l<<" "<<f<<" "<<ans<<" "<<cur<<" "<<t[i].c<<endl;
if(i==n+1)
{
return;//边界,1~n都已处理完成
}
if(l==1)
{
if(t[i].w==1)
{
cur=max(cur,t[i].f);
ans=ans+cur;
cur=0;
t[i].c--;
if(!t[i].c)
{
solve(i+1,k,f);
}
else
{
solve(i,k,f);
}
}
else
{
ans=ans+cur;
cur=0;
solve(i,k,f=true);
}
return;
}//保证以下的l至少为2
if(t[i].w==1&&f)
{
t[i].c--;
f=false;
if(!t[i].c)
{
solve(i+1,l,f);
return;
}
}//处理f标记,若f标记未去除,则w必定为2
if(l/t[i].w>t[i].c)
{
cur=max(cur,t[i].f);
solve(i+1,l-t[i].c*t[i].w,f);
}//容量绰绰有余
else if(l/t[i].w==t[i].c)
{
cur=max(cur,t[i].f);
ans=ans+cur;
cur=0;
solve(i+1,k,f|(l%t[i].w));
}//容量刚好够
else
{
cur=max(cur,t[i].f);//至少能运载一个
ans=ans+cur;
cur=0;
t[i].c-=(l/t[i].w);
ans=ans+t[i].c/(k/t[i].w)*t[i].f;
t[i].c%=(k/t[i].w);
if(t[i].c)
{
solve(i,k,f|(l%t[i].w));
}
else
{
solve(i+1,k,f|(l%t[i].w));
}
}//容量不够
}
int main()
{
// freopen("L.in","r",stdin);
// freopen("L.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>t[i].c>>t[i].w>>t[i].f;
}
sort(t+1,t+n+1,cmp);
// cout<<"---"<<endl;
for(int i=1;i<=n;i++)
{
// cout<<i<<':'<<t[i].c<<" "<<t[i].w<<" "<<t[i].f<<endl;
}
cur=ans=0;
// cout<<"i l f ans cur"<<endl;
solve(1,k,false);//只有w=1才有可能产生标记,而每次w=1都会删除原来的标记
cout<<ans+cur<<"\n";
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 0
Accepted
time: 41ms
memory: 5960kb
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:
9 1 23 4 5 7 1 3 9 6 1 10 4 9 17 6 4 1 8 5 5 7 1 3 23 6 3 3 2 2 2 3 8 1 5 6 9 11 147 7 10 2 7 7 8 6 5 5 1 7 3 5 10 7 7 10 8 1 4 2 3 9 1 5 2 9 1 6 7 7 6 10 18 8 10 4 10 9 2 8 3 5 9 3 6 5 3 2 6 1 3 2 2 1 6 9 6 3 4 8 9 9 2 6 1 2 6 7 5 2 5 21 8 1 2 3 4 9 3 4 6 5 9 6 1 7 3 7 3 2 2 8 7 3 5 9 7 10 7 3 2 4 ...
result:
ok 5501 lines
Test #3:
score: 0
Accepted
time: 58ms
memory: 5976kb
input:
3 100000 8 8 2 6 7 2 8 5 1 10 7 2 7 4 1 7 6 2 9 7 1 2 3 1 1 5 1 10 5 1 1 3 2 10 5 2 5 7 1 6 5 2 7 7 2 1 5 1 6 2 2 10 8 1 7 7 1 1 10 2 6 9 1 1 8 1 4 10 1 4 6 1 1 4 1 4 1 2 9 3 2 6 6 1 3 4 1 7 9 2 5 8 2 4 7 2 1 2 2 10 6 2 9 3 1 3 2 2 3 2 2 4 7 2 4 8 1 1 5 2 3 5 2 7 7 2 9 1 1 4 5 1 2 2 1 9 3 2 1 9 2 2 ...
output:
568601 4708350936 93900404329230
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 69ms
memory: 5900kb
input:
3 100000 174 90429 1 64237 30851 1 44358 63571 2 89174 20391 2 28747 13561 2 88689 81508 2 28383 85733 1 5777 37524 2 34730 10588 2 88519 61493 2 83682 55885 1 65270 17669 2 63015 85387 1 64757 91420 2 74020 9067 2 91750 20809 1 52771 36478 2 17941 62064 1 36433 72912 2 6100 53923 2 73971 65825 2 39...
output:
2156004461915 884586357480 59034901233
result:
ok 3 lines
Test #5:
score: 0
Accepted
time: 66ms
memory: 5900kb
input:
3 100000 4418822 19907 1 13081 59730 2 93611 35050 1 5867 87777 1 21890 18374 1 82418 79526 2 76106 33510 2 45826 75573 1 42240 35449 1 98727 80720 2 65290 32021 2 51348 52399 2 97828 75498 2 51728 89905 1 22825 2855 1 26204 11427 1 99583 55530 2 37895 22256 2 92230 19533 1 9142 16138 1 54018 53102 ...
output:
84699074 270668 100000
result:
ok 3 lines
Extra Test:
score: 0
Extra Test Passed