QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678347 | #9529. Farm Management | ucup-team5234# | WA | 3ms | 4660kb | C++23 | 3.5kb | 2024-10-26 14:42:09 | 2024-10-26 14:42:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int) (x).size()
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(auto i = (a); i < (b); i++)
#define For(i, a, b, c) \
for(auto i = (a); i != (b); i += (c))
#define REPR(i, n) for(auto i = (n) - 1; i >= 0; i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase(unique(ALL(v)), (v).end())
#define eb emplace_back
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> PI;
typedef pair<ll, ll> PL;
const double EPS = 1e-6;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const ll LINF = 1e18;
const double math_PI = acos(-1);
template<typename T>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(
a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(
T &t, const V &v) {
t = v;
}
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(
T &t, const V &v) {
for(auto &e: t) fill_v(e, v);
}
template<class T>
bool chmax(T &a, const T &b) {
if(a < b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmin(T &a, const T &b) {
if(a > b) {
a = b;
return true;
}
return false;
}
template<typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &p) {
cin >> p.first >> p.second;
return is;
}
template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
for(T &x: vec) is >> x;
return is;
}
template<typename T>
string join(vector<T> &vec, string splitter) {
stringstream ss;
REP(i, SZ(vec)) {
if(i != 0) ss << splitter;
ss << vec[i];
}
return ss.str();
}
template<typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
os << join(vec, " ");
return os;
}
#ifdef LOCAL
#include "./cpp-dump/dump.hpp"
#include "./cpp-dump/mytypes.hpp"
#define dump(...) cpp_dump(__VA_ARGS__)
namespace cp = cpp_dump;
#else
#define dump(...)
#define preprocess(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(...)
#endif
int main() {
int n, m;
cin >> n >> m;
ll ans = 0;
map<ll, ll> M;
vector<PL> V(n);
ll mn = 0;
REP(i, n) {
ll w, l, r;
cin >> w >> l >> r;
V[i] = { w, l };
ans += w * l;
mn += l;
M[w] += r - l;
}
ll sum = 0;
vll A, B, C;
for(auto [k, v]: M) {
sum += v;
A.push_back(k);
B.push_back(v);
C.push_back(sum);
}
vll D;
D.push_back(0);
REPR(i, SZ(C)) {
D.push_back(D.back() + B[i] * A[i]);
}
rev(D);
dump(A, B, C, D);
ll mx = 0;
REP(i, n) {
auto [w, l] = V[i];
ll cur = ans - w * l;
ll rest = m - mn + l;
auto ind = lower_bound(ALL(A), w) - A.begin();
if(sum - C[ind] + B[ind] > rest) {
auto it = lower_bound(C.begin() + ind, C.end(), sum - rest);
int i = it - C.begin();
cur += D[(it - C.begin()) + 1]
+ min(B[i], *it - (sum - rest)) * A[i];
rest = 0;
} else {
cur += D[ind];
rest -= sum - C[ind] + B[ind];
}
cur += A[ind] * rest;
dump(rest, cur);
chmax(mx, cur);
}
cout << mx << endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3516kb
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: 0
Accepted
time: 0ms
memory: 3712kb
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:
35204500
result:
ok single line: '35204500'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
15 32 835418 2 3 178262 1 3 527643 2 2 519710 1 1 774544 3 3 82312 1 1 808199 1 1 809396 1 3 255882 1 3 80467 1 3 874973 1 3 813965 1 2 198275 1 2 152356 1 3 802055 1 1
output:
22000255
result:
ok single line: '22000255'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
13 20 526447 1 1 807398 2 2 4167 1 2 944031 2 2 830685 2 2 394251 1 2 505011 1 2 968848 1 1 58170 1 3 32504 1 1 792273 3 3 196120 1 2 714507 1 1
output:
12878768
result:
ok single line: '12878768'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
13 32 582584 1 3 335440 3 3 971984 1 2 864169 1 2 528515 1 1 382399 1 2 459855 1 2 406909 2 3 66780 2 3 885118 3 3 434844 1 2 93331 1 3 502509 1 3
output:
22065034
result:
ok single line: '22065034'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
12 77 30244 1 7 518214 3 8 486001 8 9 152634 2 3 180255 3 4 791887 1 6 635820 2 9 881171 3 5 337905 3 8 683182 5 5 300786 3 6 339094 7 9
output:
50453764
result:
ok single line: '50453764'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 3923726 826284 215861 638800 471693 146746 886003 140800 532315 684546 673434 604071 814259 170671 299465 525449 104262 689547 855391 215333 591975 803421 795321 31606 984783 103838 361911 601318 145693 450227 686945
output:
1597735409747
result:
ok single line: '1597735409747'
Test #8:
score: -100
Wrong Answer
time: 3ms
memory: 4660kb
input:
100000 16648414311 252800 55607 195981 157144 548469 789695 643048 2 2 907957 3 3 32532 231618 316365 194428 227513 762023 4231 393553 699179 898052 3 5 507551 3 5 747498 1 4 857939 9 9 440056 764429 796585 495571 117772 838593 4059 551203 870687 60877 597981 770178 593237 4 10 438147 218335 370780 ...
output:
158329674326016
result:
wrong answer 1st lines differ - expected: '4148641232436282', found: '158329674326016'