QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #135971 | #386. 蔬菜 | maomao90 | 12 | 2044ms | 255480kb | C++17 | 3.9kb | 2023-08-06 16:43:48 | 2023-08-06 16:43:52 |
Judging History
answer
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 100005;
int n, m, k;
int a[MAXN], s[MAXN], c[MAXN], x[MAXN];
struct Edge {
int v, flow, cap, cost, rid;
};
const int MAXSZ = 10000005;
vector<Edge> adj[MAXSZ];
void addEdge(int u, int v, int cap, int cost) {
//cerr << ' ' << u << " -> " << v << ": " << cap << ' ' << cost << '\n';
int id = SZ(adj[u]), rid = SZ(adj[v]);
adj[u].pb({v, 0, cap, cost, rid});
adj[v].pb({u, 0, 0, -cost, id});
}
bool inq[MAXSZ];
int p[MAXSZ];
ll d[MAXSZ];
queue<int> qu;
ll spfa(int src, int sink) {
REP (i, 0, sink + 1) {
d[i] = LINF;
}
d[src] = 0;
qu.push(src);
inq[src] = 1;
while (!qu.empty()) {
int u = qu.front(); qu.pop();
inq[u] = 0;
for (auto [v, flow, cap, cost, rid] : adj[u]) {
if (flow == cap) {
continue;
}
if (mnto(d[v], d[u] + cost)) {
p[v] = rid;
if (!inq[v]) {
inq[v] = 1;
qu.push(v);
}
}
}
}
return d[sink] < 0;
}
pll mcmf(int src, int sink) {
int flow = 0;
ll cost = 0;
while (spfa(src, sink)) {
int v = sink;
int cflow = INF;
while (v != src) {
int rid = p[v];
int u = adj[v][rid].v, id = adj[v][rid].rid;
mnto(cflow, adj[u][id].cap - adj[u][id].flow);
v = u;
}
assert(cflow != 0);
flow += cflow;
v = sink;
while (v != src) {
int rid = p[v];
int u = adj[v][rid].v, id = adj[v][rid].rid;
cost += (ll) cflow * adj[u][id].cost;
adj[u][id].flow += cflow;
adj[v][rid].flow -= cflow;
v = u;
}
}
return {flow, cost};
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> m >> k;
REP (i, 0, n) {
cin >> a[i] >> s[i] >> c[i] >> x[i];
}
while (k--) {
int p; cin >> p;
int ptr = n + p;
REP (i, 0, n) {
int tc = c[i];
REP (j, 0, p) {
if (tc == 0) {
break;
}
int mn = min(tc, x[i]);
addEdge(i, ptr, mn, 0);
addEdge(ptr, j + n, m, 0);
if (j) {
addEdge(ptr, ptr - 1, mn, 0);
}
ptr++;
tc -= mn;
}
}
assert(ptr < MAXSZ);
int src = ptr, sink = src + 1;
REP (i, 0, n) {
if (c[i] == 0) {
continue;
}
addEdge(src, i, 1, -s[i] - a[i]);
if (c[i] > 1) {
addEdge(src, i, c[i] - 1, -a[i]);
}
}
REP (i, 0, p) {
addEdge(i + n, sink, m, 0);
}
auto [flow, cost] = mcmf(src, sink);
cout << -cost << '\n';
REP (j, 0, sink + 1) {
adj[j].clear();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 71ms
memory: 255480kb
input:
2 10 1000 259797249 60066473 9 0 657887346 358579182 4 0 186 129 274 463 677 637 835 737 751 867 121 884 344 551 269 705 547 206 401 882 218 243 151 238 105 228 755 135 260 886 578 757 687 207 1000 383 52 541 756 941 811 203 543 76 622 680 697 892 429 852 678 968 143 166 248 280 716 590 712 497 611 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '5388370280', found: '0'
Test #2:
score: 0
Time Limit Exceeded
input:
3 10 1000 205125900 9988638 3006 3 653037726 899605481 1668 5 193351848 830912321 2662 4 591 552 340 885 902 468 639 317 221 890 514 387 67 256 265 988 437 850 402 110 550 684 829 995 740 761 848 862 165 899 463 344 188 581 384 14 950 23 447 406 822 653 927 506 692 857 982 83 979 561 492 80 670 610 ...
output:
result:
Test #3:
score: 0
Time Limit Exceeded
input:
4 10 1000 33948837 28049112 4 0 298287997 181421719 3992 4 161609860 108313774 756 1 648188106 116922725 507 2 637 315 392 357 205 560 581 199 875 653 147 632 368 721 107 57 49 990 50 284 328 727 708 870 47 298 552 293 894 336 737 679 802 12 155 999 943 204 892 474 909 722 908 446 207 828 25 645 599...
output:
result:
Test #4:
score: 4
Accepted
time: 28ms
memory: 243572kb
input:
1000 10 2 330056130 87020329 15 5 53267267 13625789 26 5 96957440 515239 16 4 51636208 554404357 10 2 130467237 134566286 12 2 545883716 368592555 9 4 146302460 97114705 10 3 180304917 61240612 23 5 222297586 107536572 10 2 30919682 170918867 5 2 65345319 126097967 14 4 7233688 364788096 1 5 3080051...
output:
29694087433 0
result:
ok 2 lines
Test #5:
score: 0
Wrong Answer
time: 26ms
memory: 245708kb
input:
1000 10 3 675157042 12359813 25 5 277968875 533124187 8 1 332344484 123262373 10 5 687216434 5167563 16 4 21552233 789226486 39 6 93422582 175976216 9 4 51398430 169644805 9 2 221963828 108069551 12 4 164834987 220155752 17 4 215018780 44293304 7 5 433963179 51666148 11 5 514344715 12037779 8 6 5648...
output:
19642857614 29342382772 0
result:
wrong answer 1st lines differ - expected: '19710744019', found: '19642857614'
Test #6:
score: 4
Accepted
time: 31ms
memory: 243928kb
input:
1000 10 4 250594901 214585365 24 4 139512286 218395154 16 5 11346740 396799183 8 2 106988334 354932449 11 4 147559632 182030639 9 6 46125802 258811686 26 5 15955541 23582097 3 6 191415555 119648890 31 6 460291442 660422480 10 4 433277674 97690056 8 4 375073615 560822761 16 2 263491833 415896574 4 4 ...
output:
43920121237 55790309864 0 16664311383
result:
ok 4 lines
Test #7:
score: 4
Accepted
time: 25ms
memory: 243092kb
input:
4 1 4 425217020 15806609 7 1 66979860 46578773 6 1 202610725 623940006 2 1 229550101 163273548 1 0 2 4 0 3
output:
1267574360 2118008400 0 1692791380
result:
ok 4 lines
Test #8:
score: 0
Wrong Answer
time: 34ms
memory: 245188kb
input:
6 2 6 23602530 930857485 18 2 431299452 289279806 4 2 619090386 58652793 6 2 219860061 237052132 3 0 523103032 191555771 3 2 179320910 198330131 5 1 6 2 0 5 4 3
output:
5552491954 3067441255 0 5505286894 5302363454 4305622027
result:
wrong answer 1st lines differ - expected: '6378316679', found: '5552491954'
Test #9:
score: 0
Wrong Answer
time: 38ms
memory: 245140kb
input:
8 1 8 81446843 635804869 3 1 614273534 933045193 3 0 136538335 53642523 4 1 84948498 30366685 2 1 178551349 284430910 1 1 55487083 97007461 5 1 103025903 693688113 1 1 86148957 54466864 6 1 7 2 0 6 8 4 1 3
output:
2133795286 1513965728 0 2133795286 2133795286 1856641130 796714016 1704146586
result:
wrong answer 1st lines differ - expected: '4632506925', found: '2133795286'
Test #10:
score: 0
Wrong Answer
time: 27ms
memory: 245148kb
input:
10 2 10 57436010 7396690 8 2 135208941 177659140 6 1 475063731 93338309 5 2 137851607 23309100 6 2 604574294 41421505 12 2 89812663 365884812 6 0 37155596 48815900 7 1 27524398 94241322 18 2 3338499 465995804 8 1 431195947 159531936 6 2 8 9 5 3 6 0 7 2 1 10
output:
8000908950 8055957746 6087164445 3668867269 7296313033 0 7887413056 2459718681 1250570093 8055957746
result:
wrong answer 1st lines differ - expected: '8432923194', found: '8000908950'
Test #11:
score: 0
Wrong Answer
time: 32ms
memory: 243168kb
input:
20 3 20 96416430 56866423 30 2 396938719 227830843 7 2 599724674 408738749 6 1 187774150 532516315 8 1 310596338 53688891 18 1 5235355 148980754 23 1 25498474 192191994 20 1 114959291 45917168 41 2 279558306 241279214 12 1 723312454 520844807 6 1 358163490 175005609 35 2 186599524 6050400 21 1 41524...
output:
17627363504 11068988504 16546751295 19776344444 18701853974 9225113856 20850834914 15363112882 22911335328 0 23938258646 26391758167 3377773346 21881085121 14148894265 24965181964 26847533091 5446145827 12872013410 7368907629
result:
wrong answer 1st lines differ - expected: '18194794173', found: '17627363504'
Test #12:
score: 0
Wrong Answer
time: 1148ms
memory: 244940kb
input:
100 10 100 406085531 0 256 6 488453208 0 17 1 124812354 0 379 5 206382730 0 166 2 59755808 0 232 3 651586153 0 5 0 850852607 0 18 6 40747617 0 463 5 100176583 0 169 2 388245710 0 64 2 142925115 0 437 5 89345232 0 110 6 117374227 0 161 4 495011760 0 85 3 364445574 0 230 6 11146967 0 381 4 330128696 0...
output:
377689283694 230323861740 344221402672 330286931486 401113484250 68115175070 140581236854 333939099574 371623656722 387841218259 398385429440 147285231977 383157034351 397741977491 252114797714 347349567684 389370898797 76314729113 381479817757 177658087419 394457352460 319330427222 400173321104 401...
result:
wrong answer 1st lines differ - expected: '380195908671', found: '377689283694'
Test #13:
score: 0
Wrong Answer
time: 46ms
memory: 245264kb
input:
100 10 100 84874714 324226332 9 0 52601637 269176097 1 0 67851879 297600724 12 0 405605998 472917964 4 0 153548790 402744578 13 0 435884156 1136077 11 0 14910667 383535600 10 0 168286835 281289747 10 0 78423450 742931469 11 0 358134019 385980593 10 0 175069185 268593330 1 0 14615806 23957040 3 0 775...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '140644766077', found: '0'
Test #14:
score: 0
Wrong Answer
time: 1753ms
memory: 246720kb
input:
100 10 100 317386930 501868182 85 5 25062724 18840804 170 2 463034212 23848214 73 3 432730715 569203785 73 2 488275692 443317748 40 1 201536883 108312856 494 6 224762079 108382582 280 5 498475491 201136657 127 5 121911782 206635164 18 1 364945022 441955296 243 6 242820856 463554839 53 1 34189587 469...
output:
258975737283 59540737307 399631024587 383577303406 379752257272 348074735091 285071065455 51411566118 306811939054 398410601655 338778159830 232342485328 310923384653 335605811922 43256338642 18786525376 400190930349 178746018820 373699957053 272023401369 26945883690 0 173629553486 394467893542 3541...
result:
wrong answer 1st lines differ - expected: '259074329832', found: '258975737283'
Test #15:
score: 0
Wrong Answer
time: 2044ms
memory: 245108kb
input:
100 10 100 423264529 23065397 16 2 65505757 560316797 489 5 64125869 211869650 196 2 555609039 118462171 55 3 140619063 730947145 156 2 157599720 534911466 431 5 70280309 256155766 355 4 202969461 37781149 59 3 263202635 12967263 11 5 27468877 397850784 336 4 73136894 671546815 248 3 158522982 58972...
output:
337540171791 113167635245 65122087997 356227182241 419670089496 378104717251 388528584661 407543907013 136889339969 199801083536 367396282263 272081152072 320438372841 49106905581 333569611816 397072323783 41099314373 226937638897 401260957075 306030137714 413033565604 405449590367 428368927297 3599...
result:
wrong answer 2nd lines differ - expected: '114663473743', found: '113167635245'
Test #16:
score: 0
Time Limit Exceeded
input:
1000 10 1000 28557210 0 5 0 191654255 0 8 0 243403601 0 11 0 94860920 0 8 0 404774804 0 13 0 311811831 0 4 0 673550607 0 4 0 641021571 0 6 0 860547233 0 1 0 21411898 0 1 0 609283427 0 7 0 635347662 0 1 0 406097380 0 1 0 179125001 0 19 0 401573793 0 1 0 493634820 0 1 0 87403335 0 3 0 68393887 0 3 0 1...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
1000 10 1000 469416089 0 1542 6 72412911 0 5001 6 414542486 0 2241 6 50273230 0 3811 4 754101190 0 182 5 894251859 0 35 1 145389258 0 935 3 372506986 0 248 2 32139087 0 973 1 385593512 0 2413 4 70620890 0 2750 3 685092377 0 459 5 848097 0 1963 5 253692035 0 2686 4 4063672 0 997 1 619901379 0 119 5 5...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
1000 10 1000 41500779 611619051 28 0 349414516 448439268 5 0 147540424 628693738 3 0 10755206 79077343 6 0 48201391 23005984 1 0 76338997 116812065 10 0 344335287 206662435 8 0 179087907 57600273 16 0 347318663 561157989 14 0 333052082 600429262 3 0 2645534 19035483 1 0 656442646 495472547 1 0 31910...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
1000 10 1000 523826881 267601488 1933 6 222759806 373521768 703 1 82973669 91707731 974 5 157987147 47647063 2329 3 836264202 15373500 476 5 62140592 434606429 3635 6 321065511 133757281 2529 4 159628661 34422463 296 3 346359931 66337259 1321 6 236466844 150347180 3623 5 415110138 80301411 573 4 936...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
1000 10 1000 371297930 2589514 38 5 457327315 44327896 453 5 346702241 103735489 115 1 347857720 406985951 1056 2 115956187 65182030 1855 6 531421894 88186156 628 4 264072642 146446376 1002 4 14124511 60216573 2117 3 126965238 456172543 1641 3 624802669 50866892 374 3 207266830 122670591 686 1 71765...
output:
result:
Test #21:
score: 0
Memory Limit Exceeded
input:
100000 10 100000 80490238 0 10 0 412537563 0 14 0 21181014 0 1 0 625993179 0 1 0 326968915 0 16 0 30925671 0 23 0 582412286 0 1 0 94688576 0 9 0 179414398 0 4 0 408007577 0 4 0 129562717 0 17 0 156102155 0 8 0 5550809 0 12 0 97350310 0 1 0 29647020 0 19 0 242774917 0 18 0 331624399 0 6 0 26685353 0 ...
output:
result:
Test #22:
score: 0
Memory Limit Exceeded
input:
100000 10 100000 1386689 0 13654 1 192354335 0 21325 1 123487984 0 3 6 111976384 0 7 4 19097442 0 57141 6 107009099 0 20 6 550817081 0 12 2 158008205 0 75893 4 421469592 0 2 1 67201666 0 4 1 101043 0 70419 5 186696749 0 58090 3 164098916 0 11 2 44085360 0 5600 2 127604162 0 7 3 14165277 0 62062 5 17...
output:
result:
Test #23:
score: 0
Memory Limit Exceeded
input:
100000 10 100000 57670424 59915101 1 0 20996046 240064711 6 0 14692965 654408947 5 0 1168950 69896025 1 0 76347067 54529463 18 0 36249765 135065197 12 0 44143065 938117161 3 0 293579617 195440690 10 0 199259851 234071916 1 0 84702633 351764917 1 0 454345 238046507 5 0 232845317 155949573 3 0 4935428...
output:
result:
Test #24:
score: 0
Memory Limit Exceeded
input:
100000 10 100000 289986115 4739847 38350 2 57026240 91092422 10577 3 252927616 222394733 28 5 36049460 54592586 15713 2 79837943 187064510 9 2 45748456 236547115 11 3 42978 342438 56187 4 131599438 43739583 5 4 160946046 162354194 8 6 36183869 67961650 62833 3 18298451 19698311 28100 4 26718106 3957...
output:
result:
Test #25:
score: 0
Memory Limit Exceeded
input:
100000 10 100000 102886915 66843464 7 4 44645629 150091317 9 3 230897371 193994356 9 2 112478722 520127313 81534 5 473816614 29620309 24673 4 289437976 286840870 104194 5 7128199 1047278 51720 5 5671631 5600890 12602 1 48355153 37931094 22487 5 74884644 53420016 6 2 15487201 44649308 19614 6 4417303...