QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790283#9529. Farm ManagementatriyatuoliWA 0ms3652kbC++201.6kb2024-11-28 09:44:042024-11-28 09:44:04

Judging History

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

  • [2024-11-28 09:44:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3652kb
  • [2024-11-28 09:44:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct node{
	int w, l, r;
	
	bool operator<(const node & other)const{
		return w < other.w;
	}
};

void solve(){
	int n;
	ll m;
	cin >> n >> m;
	ll t = m;
	vector<node> crops(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> crops[i].w >> crops[i].l >> crops[i].r;
	}
	sort(crops.begin() + 1, crops.end());
	
	vector<ll> prel(n + 5), prewl(n + 5), prelr(n + 5), prewlr(n + 5);
	for(int i = 1; i <= n; i++){
		prel[i] = prel[i - 1] + crops[i].l;
		prewl[i] = prewl[i - 1] + crops[i].l * crops[i].w;
		prelr[i] = prelr[i - 1] + crops[i].r - crops[i].l;
		prewlr[i] = prewlr[i - 1] + (crops[i].r - crops[i].l) * crops[i].w;
	}
	
	ll ans = prewl[n];
	t -= prel[n];
	
	//prelr[n] - prelr [l] <= m 
	int p = lower_bound(prelr.begin() + 1, prelr.begin() + n + 1, prelr[n] - t) - prelr.begin();
	t -= prelr[n] - prelr[p-1];
	ans += prewlr[n] - prewlr[p-1];
	
	ans += t * crops[p-1].w;

	
	for(int i = 1; i <= n; i++){
		ll s = m;
		s -= prel[n];
		ll res = prewl[n];
		s += crops[i].l;
		res -= crops[i].l * crops[i].w;
		
		//prelr[n] - prelr[l] <= s
		//假如多开数组避免特判,则要注意开始和结束位置 
		int p1 = lower_bound(prelr.begin() + i + 1, prelr.begin() + n + 1, s,greater <ll>()) - prelr.begin();
		
		res += prewlr[n] - prewlr[p1-1];
		//cout << res << endl;
		
		s -= prelr[n] - prelr[p1-1];
		
		res += s * crops[p1-1].w;
		
		
		ans = max(ans, res);	
	}
	cout << ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
	
	return 0;
}

詳細信息

Test #1:

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

input:

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

output:

109

result:

ok single line: '109'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3552kb

input:

12 62
503792 9 10
607358 1 3
600501 10 10
33249 4 4
774438 6 6
197692 3 6
495807 8 8
790225 5 9
77272 3 8
494819 4 9
894779 3 9
306279 5 6

output:

35277263

result:

wrong answer 1st lines differ - expected: '35204500', found: '35277263'