QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135973#386. 蔬菜maomao9012 2050ms255440kbC++173.9kb2023-08-06 16:46:252023-08-06 16:46:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-06 16:46:26]
  • 评测
  • 测评结果:12
  • 用时:2050ms
  • 内存:255440kb
  • [2023-08-06 16:46:25]
  • 提交

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, c[i], 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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 77ms
memory: 255440kb

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: 40ms
memory: 243776kb

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: 29ms
memory: 244116kb

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: 46ms
memory: 243912kb

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: 27ms
memory: 243088kb

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: 26ms
memory: 245148kb

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: 32ms
memory: 243220kb

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: 19ms
memory: 243192kb

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

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: 1182ms
memory: 244680kb

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: 50ms
memory: 245204kb

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: 1752ms
memory: 244604kb

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: 2050ms
memory: 244668kb

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...

output:


result: