QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797375#9529. Farm ManagementSword1E1WA 0ms3572kbC++201.9kb2024-12-02 21:49:282024-12-02 21:49:33

Judging History

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

  • [2024-12-02 21:49:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2024-12-02 21:49:28]
  • 提交

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++) {
        if (i == n) {
            mx = max(mx,m * a[i].w);
            continue;
        }
        int res = ans - a[i].l * a[i].w;
		int now = sum - a[i].l;
		int mod = m - now;
		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: 0
Wrong Answer
time: 0ms
memory: 3572kb

input:

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

output:

119

result:

wrong answer 1st lines differ - expected: '109', found: '119'