oj.uz

Submission #554974

# Submission time Handle Problem Language Result Execution time Memory
554974 2022-04-29T19:19:03 Z Pietra Group Photo (JOI21_ho_t3) C++14
12 / 100
 920 ms 1242860 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -