QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797378#9529. Farm ManagementSword1E1WA 0ms3844kbC++201.9kb2024-12-02 21:51:312024-12-02 21:51:31

Judging History

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

  • [2024-12-02 21:51:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-12-02 21:51:31]
  • 提交

answer

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

#define dbg(x...) \
do { \
std::cout << #x << " -> "; \
err(x); \
} while (0)

void err() {
	std::cout << std::endl;
}

template<class T, class... Ts>
void err(T arg, Ts &... args) {
	std::cout << fixed << setprecision(10) << arg << ' ';
	err(args...);
}

const int maxn = 1e5 + 5;
struct node {
	int w,l,r;
	bool operator < (const node & b) const {
		return w < b.r;
	}
}a[maxn];

void GENSHEN_START() {
	int n,m;cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		cin >> a[i].w >> a[i].l >> a[i].r;
	}	
	sort (a + 1,a + 1 + n);
	int sum = 0;
	for (int i = 1;i <= n;i++) {
		sum += a[i].l;
	}
	vector <int> suf (n + 1),suf_val(n + 1);
	for (int i = n;i >= 1;i--) {
        if (i == n) {
            suf[i] = (a[i].r - a[i].l);
            suf_val[i] = (a[i].r - a[i].l) * a[i].w;
            continue;
        }
		suf[i] = suf[i + 1] + (a[i].r - a[i].l);
		suf_val[i] = (a[i].r - a[i].l) * a[i].w + suf_val[i + 1];
	}
    int ans = 0,mx = 0;
    for (int i = 1;i <= n;i++) {
        ans += a[i].w * a[i].l;
    }
    mx = max(mx,ans);
	for (int i = 1;i <= n;i++) {
        int res = ans - a[i].l * a[i].w;
		int now = sum - a[i].l;
		int mod = m - now;
        if (i == n) {
            mx = max(mx,res + mod * a[i].w);
            continue;
        }
		int w = upper_bound(suf.rbegin(),suf.rbegin() + (n - i),mod) - suf.rbegin();
        // dbg(num);
        //dbg(i,w);
		if (w == 0) {
            res += mod * a[n - w].w;
        }
        else {
            res += suf_val[n - w + 1] + (mod - suf[n - w + 1]) * a[n - w].w;
        }
        mx = max(mx,res);
        //dbg(i,mx,res);
	}
    cout << mx << '\n';
}

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

// 3 10
// 2 3 6
// 6 3 3
// 8 3 4

signed main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int T = 1;
	//cin >> T;
	while (T--) GENSHEN_START();
	return 0;
}

详细

Test #1:

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

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

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:

34616000

result:

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