QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726063#2375. Life TransferLaVuna47AC ✓13ms7568kbC++202.5kb2024-11-08 21:27:572024-11-08 21:28:02

Judging History

This is the latest submission verdict.

  • [2024-11-08 21:28:02]
  • Judged
  • Verdict: AC
  • Time: 13ms
  • Memory: 7568kb
  • [2024-11-08 21:27:57]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(ll i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;

const ll INF = 8e13;

int solve()
{
	ll n,k,lc,pc,lm,pm,t,d;
	if (!(cin >> n>>k))
		return 1;
	cin >> lc >> pc >> lm >> pm >> t >> d;
	vector<ll> ar(n);
	FOR(i,0,n)
		cin >> ar[i];
	sort(rall(ar));
	vector<ll> p1(n+1);
	FOR(i,0,n)
		p1[i+1] = max(ar[i]-lc,0ll);
	FOR(i,1,n+1)
		p1[i] += p1[i-1];
	auto getSum1 = [&](ll l, ll r) -> ll
	{
		return p1[r + 1] - p1[l];
	};
	vector<ll> p2(n+4);
	FOR(i,0,n){
		p2[i+1] = min(ar[i]-lc,0ll);
		if(p2[i+1] < -d)
			p2[i+1] = -INF;
	}
	FOR(i,1,n+1)
		p2[i] += p2[i-1];
	auto getSum2 = [&](ll l, ll r) -> ll
	{
		return p2[r + 1] - p2[l];
	};
	vector<ll> p3(n+4);
	FOR(i,0,n)
		p3[i+1] = max(ar[i]-lm,0ll);
	FOR(i,1,n+1)
		p3[i] += p3[i-1];
	auto getSum3 = [&](ll l, ll r) -> ll
	{
		return p3[r + 1] - p3[l];
	};
	vector<ll> p4(n+4);
	FOR(i,0,n){
		p4[i+1] = min(ar[i]-lm,0ll);
		if(p4[i+1] < -d)
			p4[i+1] = -INF;
	}
	FOR(i,1,n+1)
		p4[i] += p4[i-1];
	auto getSum4 = [&](ll l, ll r) -> ll
	{
		return p4[r + 1] - p4[l];
	};
	vector<ll> p5(n+4);
	FOR(i,0,n)
		p5[i+1] = min(ar[i]-1,d);
	FOR(i,1,n+1)
		p5[i] += p5[i-1];
	auto getSum5 = [&](ll l, ll r) -> ll
	{
		return p5[r + 1] - p5[l];
	};
	ll ans = -1;
	ll pos = 0;
	ll cur;
	FOR(i,0,n+1)
	{
		ll cc = 0;
		ll cn = 0;	
		cc += getSum1(0,i-1);
		pos = max(n-(i)*(k-1),i);
		cc+= getSum5(pos,n-1);
		cc+= getSum3(i,pos-1);
		cn += getSum2(0,i-1);
		cn+= getSum4(i,pos-1);
		//cout << i << ' ' << pos << ' ' << cc << ' ' << cn<< ' ';
		if(-cn > cc){
			//cout << endl;
			continue;
		}
		cur = -cn*t;
		cur+= i*pc;
		cur+=(pos-i)*pm;
		//cout << cur;
		//cout << endl;
		if(ans == -1)	
			ans = cur;
		ans = min(ans,cur);
	}
	cout << ans;
	return 0;
}

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int TET = 1e9;
	//cin >> TET;
	for (int i = 1; i <= TET; i++)
	{
		if (solve())
		{
			break;
		}
		#ifdef ONPC
			cerr << "____________________________\n";
		#endif
	}
	#ifdef ONPC
		cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
	#endif
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

input:

2 2
18 1000 16 1
5 3
16 15

output:

1010

result:

ok single line: '1010'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

2 2
23 10 15 5
2 2
9 20

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

51 23
97 60 21 6
69 30
54 61 34 14 73 86 72 84 54 96 49 48 4 71 7 4 75 17 64 52 3 40 51 25 70 21 79 61 54 50 23 45 24 87 50 82 58 28 71 43 15 22 28 34 98 30 36 36 12 14 90

output:

219

result:

ok single line: '219'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

62 76
65 65 8 10
7 72
94 1 11 41 83 91 4 70 19 28 47 64 30 32 32 92 72 9 67 39 29 26 83 65 79 45 4 90 18 79 47 70 47 1 45 29 61 35 76 36 100 52 21 1 25 73 44 17 50 6 73 22 58 69 97 72 5 47 45 2 16 54

output:

65

result:

ok single line: '65'

Test #5:

score: 0
Accepted
time: 3ms
memory: 5208kb

input:

43582 91310
55575 60047 23173 24006
84244 90822
47556 37222 9274 59666 85416 14744 35005 68454 92243 43165 77238 98571 35979 33713 55303 46369 99271 14106 83145 85719 24960 10970 27031 76453 72640 13498 74273 36393 7420 62304 20312 50811 16983 88563 2608 45583 60922 92615 97712 128 61820 40109 70023...

output:

60047

result:

ok single line: '60047'

Test #6:

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

input:

30 76
98 62 11 1
7 5
21 100 8 41 57 21 100 48 48 22 47 99 69 7 36 71 52 98 32 46 54 9 50 37 20 59 34 26 46 47

output:

62

result:

ok single line: '62'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

318 177
965 725 889 371
301 720
957 962 940 427 168 115 538 394 855 170 156 648 768 339 162 842 743 727 806 198 45 90 404 745 168 636 96 849 71 185 456 104 907 409 484 742 207 980 938 889 666 729 920 757 912 892 34 113 953 874 837 306 934 132 697 494 648 215 685 788 508 404 90 232 230 570 718 362 98...

output:

1450

result:

ok single line: '1450'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

5 5
98 93 75 5
23 23
86 78 93 29 75

output:

208

result:

ok single line: '208'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

564 83453
98047 82325 62361 34671
30179 68383
69883 54005 88534 68864 33147 24734 2808 4900 10246 56039 20228 98823 22204 68955 55645 27519 91231 89271 49115 81898 11717 10165 26024 17090 19388 94538 92624 23588 64646 28156 93838 25045 39929 84976 7138 55506 80692 93933 87161 79953 37973 28162 26580...

output:

82325

result:

ok single line: '82325'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

6158 15278
43823 67615 4978 63699
88727 33282
77719 67731 33306 98068 14422 63259 45916 30211 13613 13914 7784 43496 19645 39454 93340 54306 78346 56423 90751 52171 7513 33252 7002 44852 96175 85892 85565 95015 12702 25692 25865 44354 74131 52784 16794 57577 58767 48332 26572 28227 98523 46865 97390...

output:

67615

result:

ok single line: '67615'

Test #11:

score: 0
Accepted
time: 7ms
memory: 6956kb

input:

74878 64717
88959 89319 37457 32099
8981 34750
86896 81749 94309 49998 80354 35423 61571 91269 67240 45199 37348 47368 57216 62409 19208 22998 8840 40045 1168 92838 77024 5819 15928 11261 35510 87736 31925 35590 38143 30966 26542 82888 89235 43716 35065 76523 99596 38380 49469 97128 66022 41482 7767...

output:

178638

result:

ok single line: '178638'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

5808 55534
43023 56965 605 27340
84039 3842
81602 71302 5402 2321 27176 93917 18412 88016 98194 46611 60816 12429 84566 58653 28140 3546 70006 9447 24227 37064 35897 41903 4184 34 43073 91739 3378 96773 88124 44894 11937 59101 27629 96194 58006 90339 83485 90409 82008 61450 94572 29201 19007 90101 9...

output:

56965

result:

ok single line: '56965'

Test #13:

score: 0
Accepted
time: 4ms
memory: 4644kb

input:

33246 52818
77 63 52 16
44774 68074
11 32 86 78 91 61 35 16 49 28 42 83 91 33 18 1 35 8 79 98 4 2 32 93 17 41 12 8 53 6 85 92 45 8 66 34 82 48 20 36 68 25 96 34 94 87 92 48 90 11 91 32 24 93 39 57 22 11 54 45 100 19 25 45 67 47 47 48 50 30 12 55 17 91 90 23 27 42 96 73 35 48 76 46 71 74 49 6 85 61 1...

output:

63

result:

ok single line: '63'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

8767 91010
98312 88704 81533 9267
72583 10494
90380 45362 16498 77529 96486 90049 63822 25130 90751 66840 14865 27674 89845 40253 93811 33109 18816 62628 94229 84807 86323 1842 17068 82167 2014 88732 20884 72963 27817 43538 27422 62702 17305 7536 37131 61696 87832 33217 7122 43724 35286 32613 39718 ...

output:

88704

result:

ok single line: '88704'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4908kb

input:

36345 57977
88961 97289 71142 76195
16430 65187
69810 95203 79749 15646 42432 76061 32014 41590 72325 94712 65109 77200 39615 44281 66127 58712 45138 76005 84479 42292 70878 48161 94599 64491 74694 15873 37677 27779 27072 82986 60314 49542 16822 32135 84018 36162 88897 19652 6852 17399 47792 67559 5...

output:

97289

result:

ok single line: '97289'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

2 2
14 37 8 24
10 44
25 82

output:

37

result:

ok single line: '37'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

6 1
90 86 25 21
72 50
95 11 84 59 72 83

output:

1134

result:

ok single line: '1134'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

10 4
74 91 43 43
2 20
81 37 99 54 49 64 80 94 35 72

output:

268

result:

ok single line: '268'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

5 3
91 60 77 11
24 72
29 42 70 71 7

output:

1104

result:

ok single line: '1104'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

10 2
83 58 34 13
9 26
11 39 8 68 4 92 33 89 19 42

output:

505

result:

ok single line: '505'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10 2
49 76 40 3
100 92
81 85 24 63 4 77 30 57 43 29

output:

310

result:

ok single line: '310'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

9 2
78 46 23 17
38 54
42 66 75 30 35 24 72 59 95

output:

153

result:

ok single line: '153'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

7 7
60 70 39 7
64 100
2 97 10 81 82 5 62

output:

70

result:

ok single line: '70'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

9 2
87 19 11 10
0 59
61 13 77 5 78 10 43 5 71

output:

86

result:

ok single line: '86'

Test #25:

score: 0
Accepted
time: 3ms
memory: 5320kb

input:

44900 58846
54314 63681 11586 8090
87466 56029
82193 99919 35683 59523 81794 35514 73365 38403 40609 13116 36552 66698 67122 18088 41145 31708 40054 91330 2415 91735 58718 99850 48725 67866 665 1236 50036 6636 89854 81453 87635 33378 13610 92614 45510 69008 84130 19510 6864 29283 5635 73086 66369 73...

output:

63681

result:

ok single line: '63681'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3928kb

input:

12192 48379
81593 79884 20649 20006
43138 82065
62832 41686 49537 1269 62681 345 39866 44302 84882 78034 29284 76442 75093 9935 3392 30364 447 3519 58234 46600 67948 1568 47054 93409 41551 91709 23481 9597 48652 94946 68818 13040 2073 94566 74350 62873 79185 1940 33612 6645 63243 24053 68869 93348 9...

output:

79884

result:

ok single line: '79884'

Test #27:

score: 0
Accepted
time: 13ms
memory: 7568kb

input:

93879 80590
65217 99501 60827 26353
69544 64427
84371 60638 75490 67641 80369 66757 68283 94453 72699 18756 51464 24241 78081 1628 68476 59735 72697 52120 71369 88134 19043 25527 35496 83628 46182 3258 54377 74328 34794 22594 95215 71714 20169 39559 89656 75524 93157 51633 51421 52391 14977 64605 15...

output:

199002

result:

ok single line: '199002'

Test #28:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

15673 96200
72583 48681 58151 11016
23753 7680
37456 23771 79783 2980 43949 57703 76242 8613 41808 77629 25420 26125 96279 83685 14625 53582 64624 82695 20391 51445 7378 56978 39785 55421 27678 22999 31981 91411 15480 84230 75911 25665 95178 86262 63705 94977 64391 62391 29473 6586 96522 32869 59169...

output:

48681

result:

ok single line: '48681'

Test #29:

score: 0
Accepted
time: 7ms
memory: 7264kb

input:

86870 39884
17173 96695 11817 63495
48140 7801
69332 16060 43784 3021 55485 48855 84284 589 72533 42581 80427 20820 97316 51516 94339 21437 76855 39162 1380 83483 85180 94471 43260 85523 93001 98878 2499 74727 61919 68428 96472 18043 49423 19247 9760 2803 40437 74642 55001 62732 37458 67507 53806 59...

output:

290085

result:

ok single line: '290085'

Test #30:

score: 0
Accepted
time: 3ms
memory: 4192kb

input:

23010 58975
82492 78157 35622 48020
87456 96371
78498 71247 78244 50965 95994 8926 36909 26988 70836 87791 14103 96479 40617 98618 69454 48663 18480 19397 58054 22198 7970 22947 65089 70101 25535 35138 6178 74876 57850 61090 57222 17321 82754 46141 51617 30756 67207 71858 48097 82378 23668 30113 819...

output:

78157

result:

ok single line: '78157'

Test #31:

score: 0
Accepted
time: 11ms
memory: 7168kb

input:

82056 51765
89734 76801 75399 73872
31776 1568
99320 34425 38328 72176 77358 18096 8213 65577 2219 53167 59134 69740 80546 34488 54527 41168 36543 31965 52993 30042 76542 39122 38049 96782 58641 14500 99847 85966 77835 42060 33755 20925 16119 64243 83221 51717 69958 37099 52387 44454 32945 36381 312...

output:

153602

result:

ok single line: '153602'

Test #32:

score: 0
Accepted
time: 6ms
memory: 5196kb

input:

45213 57140
49494 55805 22218 41707
65679 91771
65172 9074 95205 68991 44586 62519 85216 99640 56816 99352 97485 9974 5074 9447 45492 12825 38970 93730 64873 46919 71427 33257 66452 82248 29309 30014 90163 98089 55286 73967 29293 25685 97703 96892 56879 37598 66626 95084 66160 8280 6182 52226 32031 ...

output:

55805

result:

ok single line: '55805'

Test #33:

score: 0
Accepted
time: 4ms
memory: 4640kb

input:

29017 74165
82289 63637 40797 19659
18528 77712
20375 99665 28352 12592 85694 67503 99405 61088 42846 25604 28572 82851 41473 31591 35855 77823 78433 1953 81793 75671 81427 36340 51412 7821 74031 34304 60878 41376 82862 58743 52809 97271 60641 40800 43049 70287 18431 50737 15392 17329 85210 41099 49...

output:

63637

result:

ok single line: '63637'

Test #34:

score: 0
Accepted
time: 0ms
memory: 4796kb

input:

34285 54597
85486 90474 63187 58941
48434 97626
71458 44729 55497 91646 79477 66045 13557 10937 93450 84870 58031 13872 18930 39231 40786 79141 97253 907 85392 96960 41958 28053 79808 6758 28981 2711 35619 67139 63127 59949 57705 2294 37057 18747 48486 24688 61360 81140 39886 70575 61407 58392 11333...

output:

90474

result:

ok single line: '90474'

Test #35:

score: 0
Accepted
time: 12ms
memory: 7272kb

input:

91025 8963
82052 70439 25779 69309
74981 8558
13786 49758 59407 14631 73464 85702 86627 43995 87132 49643 99182 1023 65361 57406 78730 66317 17704 91723 61055 95406 49434 58741 83459 24879 49617 87405 55912 62643 37526 19660 71972 58597 56685 35884 29926 94976 75179 7178 15931 94104 84333 81558 1829...

output:

774829

result:

ok single line: '774829'

Test #36:

score: 0
Accepted
time: 2ms
memory: 4044kb

input:

17555 89738
94209 89195 71845 26325
64088 69719
31023 26038 26305 40917 69818 87834 29786 1457 43955 43443 84316 84495 67326 34520 46916 26185 6642 14691 40840 47369 96588 79728 12607 27095 199 98869 69862 18034 91511 43855 17634 47492 72374 74435 35384 45265 65166 97015 5251 66882 18190 48441 2414 ...

output:

89195

result:

ok single line: '89195'

Test #37:

score: 0
Accepted
time: 3ms
memory: 5176kb

input:

45547 55777
69850 91043 29548 47195
93963 1401
65720 17084 86229 30496 14142 58876 40891 84225 30010 87791 91275 64299 5768 2917 67759 96459 18320 56688 37095 23654 1065 121 58085 14655 53019 88831 73059 73767 53085 42109 24272 51693 58995 98941 62777 75069 90167 87382 69218 76948 88255 1393 44074 5...

output:

91043

result:

ok single line: '91043'

Test #38:

score: 0
Accepted
time: 7ms
memory: 5680kb

input:

54589 71676
94478 39800 49837 35616
88697 36501
86628 97511 46137 47412 75937 84861 77911 86314 48206 85510 59779 47915 45636 8068 12445 93696 62090 43989 73857 87852 96424 88499 62682 66991 39986 66976 60956 24883 64298 76355 48865 59105 19958 43784 10343 78814 64130 93424 55162 20010 41309 51659 6...

output:

39800

result:

ok single line: '39800'

Test #39:

score: 0
Accepted
time: 6ms
memory: 5312kb

input:

42280 33381
73910 95230 62723 19381
28025 78920
38166 58639 84679 85263 50434 22923 81624 75230 74736 6667 13223 10434 66365 80513 93170 460 4195 15715 57811 42685 54396 73161 12155 54399 13390 84278 41174 28738 23744 55459 94760 35990 87509 39759 92793 35227 74300 70939 54229 12138 19725 8095 41039...

output:

190460

result:

ok single line: '190460'

Test #40:

score: 0
Accepted
time: 5ms
memory: 5148kb

input:

41358 84349
91497 72988 76444 41958
36690 28830
28749 87763 99519 11866 94614 95061 17481 74751 34762 89605 47820 33212 59668 13307 52567 64124 98009 41105 70778 5060 68646 20530 25354 63850 35148 67350 78179 5325 68534 94565 45174 598 54085 99026 98753 77025 37618 47950 14914 97762 10883 73614 7949...

output:

72988

result:

ok single line: '72988'

Test #41:

score: 0
Accepted
time: 9ms
memory: 6544kb

input:

70566 22145
28347 41070 3987 1720
82761 13513
70565 57398 20734 418 41228 86924 51089 92114 95739 48463 87084 85061 35891 5751 81622 38675 75847 72370 36849 96276 17409 60191 88420 38383 26681 35806 42929 81438 92959 75842 23240 89127 61235 38769 83819 30987 92330 80964 93351 1519 56002 89771 45246 ...

output:

164280

result:

ok single line: '164280'

Test #42:

score: 0
Accepted
time: 1ms
memory: 3988kb

input:

3216 67785
19534 23868 10108 16436
90272 17837
88445 58011 92884 34560 65245 5788 70256 61461 50901 5506 46909 43131 85753 68864 36183 62988 26742 71134 63846 22451 57919 51863 57751 32074 49612 3253 41508 3556 93178 22055 44973 32950 7715 81531 39033 79770 82941 33745 5981 22801 6768 99379 8474 484...

output:

23868

result:

ok single line: '23868'