Submission #555005

#	Time	Username	Problem	Language	Result	Execution time	Memory
555005		LucaDantas	Group Photo (JOI21_ho_t3)	C++17	5 / 100	5048 ms	722640 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 ;
    	
    	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: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36