QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683241#9529. Farm ManagementHHAZ#WA 0ms3564kbC++202.1kb2024-10-27 19:38:062024-10-27 19:38:08

Judging History

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

  • [2024-10-27 19:38:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3564kb
  • [2024-10-27 19:38:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define endl '\n'
#define sz(x) (int)(x).size()
#define all(t) (t).begin(), (t).end()
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define debug(x) cout<<#x<<": "<<x<<endl
const int N=2e5+10,M=1e6+10;

struct node {
	ll l;
	ll r;
	ll w;
};

bool cmp(node x, node y) {
	return x.w < y.w;
}

void solve() 
{
	int n, m;
	cin >> n >> m;
	node a[n + 5];
	ll sl[n + 5], sr[n + 5], ansl[n + 5], ansr[n + 5];
	memset(sl, 0, sizeof(sl));
	memset(sr, 0, sizeof(sr));
	memset(ansl, 0, sizeof(ansl));
	memset(ansr, 0, sizeof(ansr));
	rep(i, 1, n) {
		cin >> a[i].w >> a[i].l >> a[i].r;
	}
	sort(a + 1, a + n + 1, cmp);
	rep(i, 1, n) {
		sl[i] = sl[i - 1] + a[i].l;
		sr[i] = sr[i - 1] + a[i].r;
		ansl[i] = ansl[i - 1] + a[i].l * a[i].w;
		ansr[i] = ansr[i - 1] + a[i].r * a[i].w;
	}
	ll maxx = 0;
	rep(i, 1, n) {
		ll x = m - sl[i - 1], ans = ansl[i - 1], l = i + 1, r = n;
		if(i == n || a[n].r + sl[n - 1] - sl[i] >= x) {
			maxx = max(maxx, ans + ansl[n - 1] - ansl[i] + max(x - sl[n - 1] + sl[i], 0ll) * a[i].w);
		}
		while(l < r) {
			ll mid = (l + r) >> 1;
			if(sr[n] - sr[mid - 1] + sl[mid - 1] - sl[i] <= x) {
				r = mid;
			}
			else {
				l = mid + 1;
			}
		}
		ans += ansr[n] - ansr[l - 1];
		x -= sr[n] - sr[l - 1];
		ans += ansl[l - 1] - ansl[i];
		x -= sl[l - 1] - sl[i];
		ans += x * a[i].w;
		maxx = max(maxx, ans);
	}
	cout << maxx;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	// cin >> T;
	//	cout.flush();
	//		ofstream outfile("C:\\Users\\86187\\OneDrive\\桌面\\1.txt");
	//		outfile << "a[1]=0;a[2]=1;";
	//		ll l = 1e7 + 1;
	//		rep(i, 3, 1e9) {
	//			printf("%lld\n", i);
	//			ll x = (i - 1) * ((a[i - 1] + a[i - 2]) % mod);
	//			x %= mod;
	//			if(i == l) {
	//				outfile << "a[" << i << "]=" << x << ";";
	//			}
	//			if(i == l + 1) {
	//				outfile << "a[" << i << "]=" << x << ";";
	//				l += 1e7;
	//			}
	//		}
	while(T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

36066030

result:

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