QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#577676#7744. ElevatorzhangjiahaoTL 0ms3564kbC++141.3kb2024-09-20 13:59:382024-09-20 13:59:38

Judging History

你现在查看的是最新测评结果

  • [2024-09-20 13:59:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3564kb
  • [2024-09-20 13:59:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

struct node{
	int c,f;
}a1[100005],a2[100005];
bool cmp(node a,node b) {
	return a.f>b.f;
}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
void work() {
	int n,n1=0,n2=0;
	int c,w,f;
	long long m;
	read(n);
	read(m);
	for(int i=1;i<=n;i++) {
		read(c);
		read(w);
		read(f);
		if(w==1) {
			n1++;
			a1[n1].c=c;
			a1[n1].f=f;
		} else {
			n2++;
			a2[n2].c=c;
			a2[n2].f=f;
		}
	}
	sort(a1+1,a1+n1+1,cmp);
	sort(a2+1,a2+n2+1,cmp);
	int l1=1,l2=1;
	long long sum=0,ans=0;
	while(l1<=n1||l2<=n2) {
		if(l1<=n1&&a1[l1].f>a2[l2].f) {
			if(sum==0) ans+=a1[l1].f;
			if(sum+a1[l1].c<=m) {
				sum+=a1[l1].c;
				l1++;
			} else {
				a1[l1].c-=m-sum;
				sum=0;
			}
		} else if(l2<=n2) {
			if(sum==0) ans+=a2[l2].f;
			if(sum+2*a2[l2].c<=m) {
				sum+=2*a2[l2].c;
				l2++;
			} else {
				a2[l2].c-=(m-sum)/2;
				if((m-sum)%2==1) {
					if(l1<=n1) {
						a1[l1].c--;
						if(a1[l1].c==0) l1++;
					}
				}
				sum=0;
			}
		}
	}
	cout<<ans<<"\n";
}
int main() {
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3564kb

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: