답안 #554974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554974	2022-04-29T19:19:03 Z	Pietra	Group Photo (JOI21_ho_t3)	C++14	12 / 100	920 ms	1242860 KB

Main

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

const int maxn = 22 ; 
const int inf = 1e18 ; 

int n, ans, v[maxn], go[maxn][maxn], test[maxn], dp[(1<<maxn)][maxn] ; 

// se eu ja coloquei os caras de mask e meu ultimo 
// foi i eu testo qual colocar agr com o preço de manter ok o pref 

int solve(int mask, int last){

	if(mask == (1<<n) - 1) return 0 ; 
	if(dp[mask][last+1] != -1) return dp[mask][last+1] ;
	
	int ans = inf ; 
	
	for(int i = 0 ; i < n ; i++){
		if(!(mask&(1<<i)) && last <= i + 1){
			int ct = 0 ; 
			for(int j = 0 ; j < n ; j++) if(mask&(1<<j)) ct += go[j][i] ; 
			ans = min(ans, solve((mask|(1<<i)), i) + ct) ;
		}
	}
	
	return dp[mask][last+1] = ans ; 

}

int32_t main(){

	ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; 

	cin >> n ; 

	for(int i = 0 ; i < n ; i++){
		cin >> v[i] ; v[i]-- ; 
	} 

	memset(dp, -1, sizeof dp) ; 

	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < i ; j++) go[v[i]][v[j]] = 1 ; 
	}

    cout << solve(0, -1) << "\n" ; 

}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	722512 KB	Output is correct
2	Correct	273 ms	722628 KB	Output is correct
3	Correct	283 ms	722540 KB	Output is correct
4	Correct	268 ms	722600 KB	Output is correct
5	Correct	313 ms	722560 KB	Output is correct
6	Correct	286 ms	722532 KB	Output is correct
7	Correct	294 ms	722608 KB	Output is correct
8	Correct	326 ms	722584 KB	Output is correct
9	Correct	291 ms	722548 KB	Output is correct
10	Correct	333 ms	722596 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	722512 KB	Output is correct
2	Correct	273 ms	722628 KB	Output is correct
3	Correct	283 ms	722540 KB	Output is correct
4	Correct	268 ms	722600 KB	Output is correct
5	Correct	313 ms	722560 KB	Output is correct
6	Correct	286 ms	722532 KB	Output is correct
7	Correct	294 ms	722608 KB	Output is correct
8	Correct	326 ms	722584 KB	Output is correct
9	Correct	291 ms	722548 KB	Output is correct
10	Correct	333 ms	722596 KB	Output is correct
11	Correct	394 ms	722488 KB	Output is correct
12	Correct	564 ms	722504 KB	Output is correct
13	Correct	495 ms	722604 KB	Output is correct
14	Correct	743 ms	722556 KB	Output is correct
15	Correct	723 ms	722608 KB	Output is correct
16	Correct	748 ms	722612 KB	Output is correct
17	Correct	746 ms	722612 KB	Output is correct
18	Correct	782 ms	722572 KB	Output is correct
19	Correct	771 ms	722612 KB	Output is correct
20	Correct	714 ms	722516 KB	Output is correct

Subtask #3

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	722512 KB	Output is correct
2	Correct	273 ms	722628 KB	Output is correct
3	Correct	283 ms	722540 KB	Output is correct
4	Correct	268 ms	722600 KB	Output is correct
5	Correct	313 ms	722560 KB	Output is correct
6	Correct	286 ms	722532 KB	Output is correct
7	Correct	294 ms	722608 KB	Output is correct
8	Correct	326 ms	722584 KB	Output is correct
9	Correct	291 ms	722548 KB	Output is correct
10	Correct	333 ms	722596 KB	Output is correct
11	Correct	394 ms	722488 KB	Output is correct
12	Correct	564 ms	722504 KB	Output is correct
13	Correct	495 ms	722604 KB	Output is correct
14	Correct	743 ms	722556 KB	Output is correct
15	Correct	723 ms	722608 KB	Output is correct
16	Correct	748 ms	722612 KB	Output is correct
17	Correct	746 ms	722612 KB	Output is correct
18	Correct	782 ms	722572 KB	Output is correct
19	Correct	771 ms	722612 KB	Output is correct
20	Correct	714 ms	722516 KB	Output is correct
21	Runtime error	920 ms	1242860 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	722512 KB	Output is correct
2	Correct	273 ms	722628 KB	Output is correct
3	Correct	283 ms	722540 KB	Output is correct
4	Correct	268 ms	722600 KB	Output is correct
5	Correct	313 ms	722560 KB	Output is correct
6	Correct	286 ms	722532 KB	Output is correct
7	Correct	294 ms	722608 KB	Output is correct
8	Correct	326 ms	722584 KB	Output is correct
9	Correct	291 ms	722548 KB	Output is correct
10	Correct	333 ms	722596 KB	Output is correct
11	Correct	394 ms	722488 KB	Output is correct
12	Correct	564 ms	722504 KB	Output is correct
13	Correct	495 ms	722604 KB	Output is correct
14	Correct	743 ms	722556 KB	Output is correct
15	Correct	723 ms	722608 KB	Output is correct
16	Correct	748 ms	722612 KB	Output is correct
17	Correct	746 ms	722612 KB	Output is correct
18	Correct	782 ms	722572 KB	Output is correct
19	Correct	771 ms	722612 KB	Output is correct
20	Correct	714 ms	722516 KB	Output is correct
21	Runtime error	920 ms	1242860 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	722512 KB	Output is correct
2	Correct	273 ms	722628 KB	Output is correct
3	Correct	283 ms	722540 KB	Output is correct
4	Correct	268 ms	722600 KB	Output is correct
5	Correct	313 ms	722560 KB	Output is correct
6	Correct	286 ms	722532 KB	Output is correct
7	Correct	294 ms	722608 KB	Output is correct
8	Correct	326 ms	722584 KB	Output is correct
9	Correct	291 ms	722548 KB	Output is correct
10	Correct	333 ms	722596 KB	Output is correct
11	Correct	394 ms	722488 KB	Output is correct
12	Correct	564 ms	722504 KB	Output is correct
13	Correct	495 ms	722604 KB	Output is correct
14	Correct	743 ms	722556 KB	Output is correct
15	Correct	723 ms	722608 KB	Output is correct
16	Correct	748 ms	722612 KB	Output is correct
17	Correct	746 ms	722612 KB	Output is correct
18	Correct	782 ms	722572 KB	Output is correct
19	Correct	771 ms	722612 KB	Output is correct
20	Correct	714 ms	722516 KB	Output is correct
21	Runtime error	920 ms	1242860 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-