QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261625#6471. Binary Transformationsillyakr#AC ✓31ms3904kbC++171.4kb2023-11-23 03:59:572023-11-23 03:59:57

Judging History

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

  • [2023-11-23 03:59:57]
  • 评测
  • 测评结果:AC
  • 用时:31ms
  • 内存:3904kb
  • [2023-11-23 03:59:57]
  • 提交

answer

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> c(n);
	for(int &x : c) cin >> x;
	string s, t;
	cin >> s >> t;
	vector<int> bad, one, zero;
	for(int i = 0; i < n; i++){
		if(s[i] == '1' && t[i] == '1') bad.emplace_back(c[i]);
		if(s[i] == '1' && t[i] == '0') one.emplace_back(c[i]);
		if(s[i] == '0' && t[i] == '1') zero.emplace_back(c[i]);
	}
	sort(bad.rbegin(),bad.rend());
	sort(one.rbegin(),one.rend());
	sort(zero.begin(),zero.end());
	int opt = 1000000000000000000ll;
	for(int i = 0; i <= sz(bad); i++){ // take i from bad
		int cur = 0, cost = 0;
		for(int l = 0; l < n; l++) if(s[l] == '1') cost += c[l];
		int j = 0, k = 0;
		for(int l = 0; l < i+sz(one); l++){
			if(j < i && (k == sz(one) || bad[j] > one[k])){
				cost -= bad[j];
				cur += cost;
				j++;
			} else{
				cost -= one[k];
				cur += cost;
				k++;
			}
		}
		j = i-1, k = 0;
		for(int l = 0; l < i+sz(zero); l++){
			if(j >= 0 && (k == sz(zero) || bad[j] < zero[k])){
				cost += bad[j];
				cur += cost;
				j--;
			} else{
				cost += zero[k];
				cur += cost;
				k++;
			}
		}
		opt = min(opt, cur);
	}
	cout << opt << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

input:

5
5 2 6 1 5
01110
10011

output:

21

result:

ok single line: '21'

Test #2:

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

input:

10
54 57 56 56 34 26 62 57 94 93
1101100111
0111110011

output:

1498

result:

ok single line: '1498'

Test #3:

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

input:

100
13497 84812 46650 96837 47518 81363 69563 49672 62222 59492 2399 70142 66019 23108 34561 48256 89591 70076 35039 20871 56909 44505 91578 96372 47174 73772 45594 75368 50125 79114 39144 60524 75020 85709 33811 68779 99668 89361 25932 45107 41881 70392 77449 37880 20372 49639 24933 76529 43903 136...

output:

83548857

result:

ok single line: '83548857'

Test #4:

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

input:

5000
50886926 178561126 309477916 5139934 455459823 294599549 460944689 43176650 632716226 555025479 477795091 310011879 958127540 186927804 155714602 843462644 929474310 799635718 772428338 968514343 887380366 808631811 808360122 22293929 980535861 850687942 247319462 116758037 69181306 269811221 6...

output:

2104162026353252

result:

ok single line: '2104162026353252'

Test #5:

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

input:

5000
34154420 736224872 296328298 34944768 423656577 337997514 108849674 378639629 590078761 728081782 70151687 346348332 284366348 448097569 963093070 3522475 999762244 413774162 461849534 742385899 176451353 555225317 685692077 80202722 457862794 793959561 656767332 407397530 146697163 260097858 4...

output:

4157294466908288

result:

ok single line: '4157294466908288'

Test #6:

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

input:

5000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...

output:

12502500000000000

result:

ok single line: '12502500000000000'

Test #7:

score: 0
Accepted
time: 19ms
memory: 3660kb

input:

5000
849924633 785824059 407776094 548948924 368153843 709670398 867649965 202806200 258860768 862107580 541511716 880224090 793914716 471795718 630654196 303835448 465602153 307860627 546661133 385966665 769975564 548491197 818519209 302983785 922571725 130390785 345482690 539462872 989455675 91530...

output:

2826402260843948

result:

ok single line: '2826402260843948'

Test #8:

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

input:

5000
858334536 291579079 939817827 616670505 953271951 639275218 195018084 296183549 282696212 253163958 683085095 963938222 319620974 708656462 689235761 883186446 97035434 161865478 900938167 136393156 113621194 789884512 5265187 571163086 434518593 215616883 133277845 13829370 485639544 854109543...

output:

2363170015443603

result:

ok single line: '2363170015443603'

Test #9:

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

input:

5000
352236476 961367577 947816315 900259305 904176367 255488035 696523945 837717800 727270673 69386532 68897434 826352991 812999992 326566610 879027982 812057597 138137708 633233399 539075320 866603206 830756394 553767152 434534141 296900178 508567267 3103791 66227192 612990603 499523194 707450554 ...

output:

14236552454

result:

ok single line: '14236552454'

Test #10:

score: 0
Accepted
time: 31ms
memory: 3904kb

input:

5000
726348216 668902390 420494770 778435537 494281513 665460463 591899323 224539301 532001609 507672248 767712930 553824564 777985921 231721851 268158137 301283488 450290606 336665845 345494023 737533666 383758497 207034616 130859462 85971269 782833310 366895593 665177061 618837737 560121310 796238...

output:

25130414676276

result:

ok single line: '25130414676276'

Test #11:

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

input:

5000
85847518 372293747 811797861 385071820 98025645 851186185 196988260 942796534 85852193 469973222 192030064 928259303 583094829 350159926 632513301 577791477 192753561 207485467 240824821 483371947 935433345 515926568 517327431 716269639 984628437 576570342 75510099 353041213 433060055 769102674...

output:

44711745036

result:

ok single line: '44711745036'

Test #12:

score: 0
Accepted
time: 31ms
memory: 3724kb

input:

5000
254884344 849195755 826996580 692884946 794820399 637335931 185621481 299517691 128165402 688657789 412676687 276571256 779468406 702775076 105375851 975192873 219077074 68849305 314515751 328120608 110989330 368169082 641375999 453573156 732911598 203268694 354263175 522961967 23573360 2194117...

output:

57097816218978

result:

ok single line: '57097816218978'

Test #13:

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

input:

5000
838877334 669709110 95692267 403362681 107183097 493072030 695035579 392144234 615429193 756889887 302288748 438920754 24254324 188582464 859993416 660629315 998575549 685316096 28783915 834686915 272377405 101399886 148589065 924380430 771622752 329850000 744419686 38363955 981300580 911722013...

output:

904191312068

result:

ok single line: '904191312068'

Test #14:

score: 0
Accepted
time: 27ms
memory: 3904kb

input:

5000
734418544 771133631 755316256 441479428 271062575 164710507 730090579 241093993 758077200 381110052 424721226 61370149 692696859 540987468 632394726 994248964 315781036 630679222 596391837 997442178 249935858 769878828 709253369 933093460 332222321 787591402 399095319 797887711 278863488 333544...

output:

236691787134755

result:

ok single line: '236691787134755'

Test #15:

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

input:

5000
317930874 689604230 956235200 963710382 659541046 126926966 978865155 758222817 718283444 751993083 460237136 345605129 338215081 814070529 493162741 353401660 483028636 790602857 546757202 513562308 440549992 481971848 397588831 950626978 232995262 334570662 719693605 938754566 266821793 93850...

output:

1428631755161

result:

ok single line: '1428631755161'

Test #16:

score: 0
Accepted
time: 28ms
memory: 3772kb

input:

5000
824100850 814984586 141710169 515741480 803568911 150536082 708543082 284797505 852752626 398061317 279538300 621979704 883369079 400677430 170009221 940237324 615313485 307470702 777329807 386027502 420757368 9838443 164075063 598174663 169696719 906512348 449434926 162874799 559374463 9514019...

output:

304932420643723

result:

ok single line: '304932420643723'

Test #17:

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

input:

1
1
0
1

output:

1

result:

ok single line: '1'

Test #18:

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

input:

1
1000000000
1
0

output:

0

result:

ok single line: '0'

Test #19:

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

input:

1
1
1
1

output:

0

result:

ok single line: '0'

Test #20:

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

input:

1
1000
0
0

output:

0

result:

ok single line: '0'