QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738778#9529. Farm ManagementzxcdxwWA 0ms3808kbC++141.4kb2024-11-12 19:54:362024-11-12 19:54:49

Judging History

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

  • [2024-11-12 19:54:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3808kb
  • [2024-11-12 19:54:36]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define ll long long
#define lowbit(x) (x)&(-x)
#define int long long
//#define double long double 
const int N = 1e6 + 5;
const ll base = 131;
const ll mod = 998244353;
struct syz {
    int a, b, c;
    syz() {}
    syz(int aa, int bb, int cc) :a(aa), b(bb), c(cc)
    {}
    bool operator <(syz x) {
        if (this->a == x.a) {
            return this->b < x.b;
        }
        return this->a > x.a;
    }
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<syz>w(n + 1);
    for (int i = 1; i <= n; ++i) cin >> w[i].a >> w[i].b >> w[i].c;
    sort(w.begin() + 1, w.end());
    vector<int>pre(n + 1), presum(n + 1);
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + w[i].c - w[i].b, presum[i] = presum[i - 1] + (w[i].c - w[i].b) * w[i].a;
    ll ma = 0, sum = 0, Sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += w[i].b;
        Sum += w[i].b * w[i].a;
    }
    for (int i = n; i >= 1; --i) {
        ma = max(ma, Sum + (m - sum) * w[i].a);
        int res = m - sum + w[i].b;
        auto now = upper_bound(pre.begin() + 1, pre.end(), res) - pre.begin() - 1;
        ma = max(ma, Sum - w[i].b * w[i].a + presum[now] + (res - pre[now]) * w[i].a);
    }
    cout << ma << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

34859047

result:

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