QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189941#3221. Clique ColoringKKT89AC ✓0ms4124kbC++171.7kb2023-09-28 01:40:092023-09-28 01:40:10

Judging History

This is the latest submission verdict.

  • [2023-09-28 01:40:10]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 4124kb
Show
  • [2023-09-28 01:40:09]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<ll> a(n);
	ll res=0;
	for(int i=0;i<n;i++){
		cin >> a[i];
		res+=a[i];
	}
	sort(a.rbegin(), a.rend());
	if(n==1){
		printf("%lld\n",res);
	}
	else if(n==2){
		printf("%lld\n",res-1);
	}
	else if(n==3){
		printf("%lld\n",res-3);
	}
	else if(n==4){
		if(a[2]>2){
			printf("%lld\n",res-a[3]-3+max(0LL,a[3]-3));
		}
		else if(a[0]==2){
			printf("4\n");
		}
		else if(a[1]==2){
			printf("%lld\n",a[0]+1);
		}
		else{ // a[2]==2
			printf("%lld\n",a[0]+a[1]-1);
		}
	}
	else{
		if(a[0]==2){
			printf("4\n");
		}
		else if(a[1]==2){
			if(a[0]==3)printf("5\n"); // 3の時だけ2つ必要
			else printf("%lld\n",a[0]+1); // それ以外は1つでOK
		}
		else if(a[2]==2){
			printf("%lld\n",a[0]+a[1]-1); // 余ってる頂点が少なくとも4ある
		}
		else if(a[3]==2){
			printf("%lld\n",a[0]+a[1]+a[2]-3);
		}
		else if(a[4]==2){
			printf("%lld\n",a[0]+a[1]+a[2]+a[3]-6); // 常に6だけ減らせる
		}
		else if(a[4]>3){
			printf("%lld\n",res-10);
		}
		else{ // a[4]==3
			// a[0]+a[1]+a[2]+a[3]-6 をベースに考える
			// a[4]の3がカバーしきれないケースは？
			res=a[0]+a[1]+a[2]+a[3]-6;
			if(a[0]==3){
				printf("%lld\n",res+1);
			}
			else if(a[0]==4){
				if(a[1]>=4){
					printf("%lld\n",res);
				}
				else{
					printf("%lld\n",res+1);
				}
			}
			else{
				printf("%lld\n",res);
			}

		}
	}
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
4

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
4
1000000000

output:

1000000003

result:

ok single line: '1000000003'

Test #3:

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

input:

3
447893992
4
1000000000

output:

1447893993

result:

ok single line: '1447893993'

Test #4:

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

input:

4
1000000000
1000000000
409299805
305205736

output:

2714505535

result:

ok single line: '2714505535'

Test #5:

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

input:

5
701636407
83399801
260677870
1000000000
4

output:

2045714072

result:

ok single line: '2045714072'

Test #6:

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

input:

1
3

output:

3

result:

ok single line: '3'

Test #7:

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

input:

2
497280904
3

output:

497280906

result:

ok single line: '497280906'

Test #8:

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

input:

3
3
4
495505982

output:

495505986

result:

ok single line: '495505986'

Test #9:

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

input:

4
4
3
4
4

output:

9

result:

ok single line: '9'

Test #10:

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

input:

5
4
4
3
4
1000000000

output:

1000000006

result:

ok single line: '1000000006'

Test #11:

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

input:

2
3
3

output:

5

result:

ok single line: '5'

Test #12:

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

input:

3
1000000000
3
3

output:

1000000003

result:

ok single line: '1000000003'

Test #13:

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

input:

4
378634918
3
3
4

output:

378634922

result:

ok single line: '378634922'

Test #14:

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

input:

5
693604254
3
3
1000000000
4

output:

1693604255

result:

ok single line: '1693604255'

Test #15:

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

input:

3
3
3
3

output:

6

result:

ok single line: '6'

Test #16:

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

input:

4
3
3
741443949
3

output:

741443952

result:

ok single line: '741443952'

Test #17:

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

input:

5
798458902
3
3
85709420
3

output:

884168322

result:

ok single line: '884168322'

Test #18:

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

input:

4
3
3
3
3

output:

6

result:

ok single line: '6'

Test #19:

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

input:

5
3
3
4
3
3

output:

8

result:

ok single line: '8'

Test #20:

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

input:

5
3
3
3
3
3

output:

7

result:

ok single line: '7'

Test #21:

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

input:

1
2

output:

2

result:

ok single line: '2'

Test #22:

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

input:

2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #23:

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

input:

3
275630553
2
1000000000

output:

1275630552

result:

ok single line: '1275630552'

Test #24:

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

input:

4
4
85561698
2
4

output:

85561703

result:

ok single line: '85561703'

Test #25:

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

input:

5
343830664
2
266706206
477214206
4

output:

1087751074

result:

ok single line: '1087751074'

Test #26:

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

input:

2
2
3

output:

4

result:

ok single line: '4'

Test #27:

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

input:

3
2
3
1000000000

output:

1000000002

result:

ok single line: '1000000002'

Test #28:

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

input:

4
3
2
277873868
1000000000

output:

1277873868

result:

ok single line: '1277873868'

Test #29:

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

input:

5
2
136812254
473248215
3
4

output:

610060470

result:

ok single line: '610060470'

Test #30:

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

input:

3
3
2
3

output:

5

result:

ok single line: '5'

Test #31:

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

input:

4
3
2
1000000000
3

output:

1000000003

result:

ok single line: '1000000003'

Test #32:

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

input:

5
2
3
261722051
3
1000000000

output:

1261722051

result:

ok single line: '1261722051'

Test #33:

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

input:

4
3
3
3
2

output:

6

result:

ok single line: '6'

Test #34:

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

input:

5
3
3
857509551
3
2

output:

857509554

result:

ok single line: '857509554'

Test #35:

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

input:

5
3
3
3
2
3

output:

6

result:

ok single line: '6'

Test #36:

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

input:

2
2
2

output:

3

result:

ok single line: '3'

Test #37:

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

input:

3
2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #38:

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

input:

4
615064899
2
2
4

output:

615064902

result:

ok single line: '615064902'

Test #39:

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

input:

5
4
1000000000
1000000000
2
2

output:

2000000001

result:

ok single line: '2000000001'

Test #40:

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

input:

3
2
3
2

output:

4

result:

ok single line: '4'

Test #41:

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

input:

4
4
2
3
2

output:

6

result:

ok single line: '6'

Test #42:

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

input:

5
2
3
1000000000
4
2

output:

1000000004

result:

ok single line: '1000000004'

Test #43:

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

input:

4
2
3
2
3

output:

5

result:

ok single line: '5'

Test #44:

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

input:

5
2
3
54069329
2
3

output:

54069332

result:

ok single line: '54069332'

Test #45:

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

input:

5
3
3
3
2
2

output:

6

result:

ok single line: '6'

Test #46:

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

input:

3
2
2
2

output:

3

result:

ok single line: '3'

Test #47:

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

input:

4
2
4
2
2

output:

5

result:

ok single line: '5'

Test #48:

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

input:

5
2
2
395669578
2
906198920

output:

1301868497

result:

ok single line: '1301868497'

Test #49:

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

input:

4
3
2
2
2

output:

4

result:

ok single line: '4'

Test #50:

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

input:

5
3
2
1000000000
2
2

output:

1000000002

result:

ok single line: '1000000002'

Test #51:

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

input:

5
2
3
2
3
2

output:

5

result:

ok single line: '5'

Test #52:

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

input:

4
2
2
2
2

output:

4

result:

ok single line: '4'

Test #53:

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

input:

5
2
2
2
1000000000
2

output:

1000000001

result:

ok single line: '1000000001'

Test #54:

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

input:

5
2
2
2
3
2

output:

5

result:

ok single line: '5'

Test #55:

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

input:

5
2
2
2
2
2

output:

4

result:

ok single line: '4'

Test #56:

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

input:

5
1000000000
1000000000
1000000000
1000000000
1000000000

output:

4999999990

result:

ok single line: '4999999990'

Test #57:

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

input:

2
3
3

output:

5

result:

ok single line: '5'

Test #58:

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

input:

5
2
3
4
5
6

output:

12

result:

ok single line: '12'
English 繁體中文 简体中文

Server Time: 2025-04-08 08:49:02 | OpenSource Project