QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#679475#9529. Farm Managementucup-team3670#WA 0ms3792kbC++171.6kb2024-10-26 17:41:242024-10-26 17:41:24

Judging History

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

  • [2024-10-26 17:41:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-10-26 17:41:24]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)

using namespace std;

int main(){
 	cin.tie(0);
 	ios::sync_with_stdio(false);
 	int n;
 	long long m;
 	cin >> n >> m;
 	vector<int> w(n), l(n), r(n);
 	forn(i, n){
 		cin >> w[i] >> l[i] >> r[i];
 	}
 	long long ans = 0;
 	long long sl = 0;
 	forn(i, n) sl += l[i];
 	long long sl2 = 0;
 	forn(i, n) sl2 += l[i] * 1ll * w[i];
 	vector<long long> su(n + 1), su2(n + 1);
 	for (int i = n - 1; i >= 0; --i){
 		su[i] = su[i + 1] + (r[i] - l[i]);
 		su2[i] = su2[i + 1] + (r[i] - l[i]) * 1ll * w[i];
 	}
 	forn(i, n){
 		long long lft = m - sl + l[i];
 		ans = max(ans, sl2 - l[i] * 1ll * w[i] + lft * 1ll * w[i]);
 	}
 	forn(i, n){
 		int lf = 0, rg = n - 1;
 		int res = -1;
 		while (lf <= rg){
 			int mid = (lf + rg) / 2;
 			long long mx = su[mid] - (i <= mid ? r[i] - l[i] : 0);
 			mx += sl - l[i];
 			if (mx >= m){
 				res = mid;
 				rg = mid - 1;
 			}
 			else{
 				lf = mid + 1;
 			}
 		}
 		if (res == 0 && i == 0) res = -1;
 		assert(res != i);
 		if (res == -1){
 			long long rem = m - (sl + su[0] - r[i]);
 			ans = max(ans, (sl2 + su2[0] - r[i] * 1ll * w[i]) + rem * w[i]);
 		}
 		else{
 			long long cur = su2[res] - (i <= res ? (r[i] - l[i]) * 1ll * w[i] : 0ll);
 			cur += sl2 - l[i] * 1ll * w[i];
 			long long rem = su[res] - (i <= res ? r[i] - l[i] : 0);
 			rem += sl - l[i];
 			assert(rem >= m);
 			rem -= m;
 			ans = max(ans, cur - w[res] * 1ll * rem);
 		}
 	}
 	cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3792kb

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:

33655073

result:

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