QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135940#386. 蔬菜maomao9032 1386ms255612kbC++173.8kb2023-08-06 16:10:552023-08-06 16:10:56

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:10:56]
  • 评测
  • 测评结果:32
  • 用时:1386ms
  • 内存:255612kb
  • [2023-08-06 16:10:55]
  • 提交

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 bellman(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 (bellman(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;
        }
        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 + m;
        REP (i, 0, n) {
            if (c[i] == 0) {
                continue;
            }
            REP (j, 0, p) {
                int cap = c[i] - (ll) j * x[i];
                if (cap <= 0) {
                    break;
                }
                addEdge(i, ptr, cap, 0);
                addEdge(ptr, j + n, m, 0);
                ptr++;
            }
        }
        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: 4
Accepted
time: 128ms
memory: 255612kb

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:

5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
538...

result:

ok 1000 lines

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: 30ms
memory: 243580kb

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: 4
Accepted
time: 26ms
memory: 244292kb

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:

19710744019
29502521099
0

result:

ok 3 lines

Test #6:

score: 4
Accepted
time: 42ms
memory: 247812kb

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

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: 4
Accepted
time: 34ms
memory: 243100kb

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:

6378316679
3067441255
0
5979135708
5381624606
4305622027

result:

ok 6 lines

Test #9:

score: 4
Accepted
time: 28ms
memory: 245200kb

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:

4632506925
2344032743
0
4480012381
4773122746
3675557989
1547318727
3061284455

result:

ok 8 lines

Test #10:

score: 0
Wrong Answer
time: 21ms
memory: 243120kb

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:

8669421833
8939839715
6087164445
3668867269
7296313033
0
8221344811
2459718681
1250570093
9210257597

result:

wrong answer 1st lines differ - expected: '8432923194', found: '8669421833'

Test #11:

score: 0
Wrong Answer
time: 32ms
memory: 243132kb

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:

18194794173
11514758366
16980575556
20412468746
19337978276
9715584344
21486959216
15766356939
23635940156
0
24710430626
28058028543
3377773346
22561449686
14531125276
25784921096
29248844700
5600862281
13168489659
7770799643

result:

wrong answer 4th lines differ - expected: '20365892697', found: '20412468746'

Test #12:

score: 0
Wrong Answer
time: 502ms
memory: 244464kb

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:

407940387627
243674585384
371119577860
355388000180
444568088674
69870248386
144709424400
359320894600
401403315978
420268025157
434583100354
151804385350
414131869527
433334976814
269218588084
374771745948
421999894837
78119222996
412068042227
186278191687
427908865427
343474152119
438327470974
445...

result:

wrong answer 1st lines differ - expected: '380195908671', found: '407940387627'

Test #13:

score: 4
Accepted
time: 1386ms
memory: 244828kb

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:

140644766077
68760004759
202765832116
219154961064
201593278448
213815383548
220174997702
219826116198
177506449175
129670735199
216093024650
217767535360
166642569825
217269539400
195010857268
220078265904
183265000081
94130934409
82340524370
220174997702
190335429219
219755306628
121786087377
1991...

result:

ok 100 lines

Test #14:

score: 0
Wrong Answer
time: 846ms
memory: 244352kb

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:

271178187314
60333205634
421891113731
402396146539
398365408879
364091298361
297726839174
52484542974
319850715724
419944001611
354349647337
243717730275
324275491034
351053015013
44631749476
18884833951
422809118646
186919362906
392196705913
284452513244
27499908651
0
180959819146
414918537941
3705...

result:

wrong answer 1st lines differ - expected: '259074329832', found: '271178187314'

Test #15:

score: 0
Wrong Answer
time: 1178ms
memory: 244368kb

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:

352595586524
114663473743
68277791084
372034607517
440512615581
394459020057
405988448107
427218586627
137320344913
203989678160
383246813787
284328997224
333090846724
51630891124
347719401574
415424065227
43075037734
234132715274
420141873787
318462291874
433700675741
424859682347
450537817275
3757...

result:

wrong answer 1st lines differ - expected: '337540171791', found: '352595586524'

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: