QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#691989#9529. Farm Managementwangshengzhe#WA 1ms5760kbC++141.6kb2024-10-31 13:34:432024-10-31 13:34:45

Judging History

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

  • [2024-10-31 13:34:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5760kb
  • [2024-10-31 13:34:43]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
using LL = long long;
using ll = long long;

const int N = 2E5 + 10;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double ef = 1e-12;
const double PI = acos(-1);

#define rep(i,a,b) for(int i = a;i<=b;i++)
#define pre(i,a,b) for(int i = a;i>=b;i--)
#define int long long

int n, m;
struct node {
	int le, ri;
	int w;
};
node p[100005];
node qian[100005], ho[100005];

bool cmp(node a, node b)
{
	return a.w < b.w;
}

int find1(int le, int ri, int tar)
{
	int pp = le - 1;
	while (le < ri)
	{
		int mid = (le + ri) >> 1;
		if (ho[mid].ri + qian[mid - 1].le - p[pp].le <= m) ri = mid;
		else le = mid + 1;
	}
	return le;
}

void solve()
{
	cin >> n >> m;
	rep(i, 1, n) {
		cin >> p[i].w >> p[i].le >> p[i].ri;
	}
	sort(p + 1, p + n + 1, cmp);
	rep(i, 1, n) {
		qian[i].le = qian[i - 1].le + p[i].le;
		qian[i].w = qian[i - 1].w + p[i].w * p[i].le;
	}
	pre(i, n, 1) {
		ho[i].ri = ho[i + 1].ri + p[i].ri;
		ho[i].w = ho[i + 1].w + p[i].w * p[i].ri;
	}
	int ans = 0;
	rep(i, 1, n)
	{
		int pp = find1(i + 1, n + 1, m - qian[i - 1].le);
		int an = ho[pp].w + qian[pp - 2].w + (m - qian[pp - 2].le - ho[pp].ri) * p[pp].w;
		ans = max(ans, an);
	}
	pre(i, n, 1)
	{
		int an = qian[i - 1].w + ho[i + 1].w + (m - qian[i - 1].le - ho[i + 1].ri) * p[i].w;
		ans = max(ans, an);
	}
	cout << ans << endl;
	return;
}

signed main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	int t = 1;
	//cin >> t;

	while (t--) {
		solve();
	}

	return 0;

}



詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5720kb

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: 1ms
memory: 5760kb

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:

44007019

result:

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