Submission #554974

#	Time	Username	Problem	Language	Result	Execution time	Memory
554974		Pietra	Group Photo (JOI21_ho_t3)	C++14	12 / 100	920 ms	1242860 KiB

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36