oj.uz

Submission #555005

# Submission time Handle Problem Language Result Execution time Memory
555005 2022-04-29T21:21:30 Z LucaDantas Group Photo (JOI21_ho_t3) C++17
5 / 100
 5000 ms 722640 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 ;
    	
    	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 283 ms 722508 KB Output is correct
2 Correct 262 ms 722504 KB Output is correct
3 Correct 280 ms 722564 KB Output is correct
4 Correct 269 ms 722588 KB Output is correct
5 Correct 277 ms 722496 KB Output is correct
6 Correct 277 ms 722540 KB Output is correct
7 Correct 262 ms 722640 KB Output is correct
8 Correct 262 ms 722488 KB Output is correct
9 Correct 269 ms 722504 KB Output is correct
10 Correct 262 ms 722588 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 722508 KB Output is correct
2 Correct 262 ms 722504 KB Output is correct
3 Correct 280 ms 722564 KB Output is correct
4 Correct 269 ms 722588 KB Output is correct
5 Correct 277 ms 722496 KB Output is correct
6 Correct 277 ms 722540 KB Output is correct
7 Correct 262 ms 722640 KB Output is correct
8 Correct 262 ms 722488 KB Output is correct
9 Correct 269 ms 722504 KB Output is correct
10 Correct 262 ms 722588 KB Output is correct
11 Correct 2163 ms 722544 KB Output is correct
12 Execution timed out 5048 ms 722580 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 722508 KB Output is correct
2 Correct 262 ms 722504 KB Output is correct
3 Correct 280 ms 722564 KB Output is correct
4 Correct 269 ms 722588 KB Output is correct
5 Correct 277 ms 722496 KB Output is correct
6 Correct 277 ms 722540 KB Output is correct
7 Correct 262 ms 722640 KB Output is correct
8 Correct 262 ms 722488 KB Output is correct
9 Correct 269 ms 722504 KB Output is correct
10 Correct 262 ms 722588 KB Output is correct
11 Correct 2163 ms 722544 KB Output is correct
12 Execution timed out 5048 ms 722580 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 722508 KB Output is correct
2 Correct 262 ms 722504 KB Output is correct
3 Correct 280 ms 722564 KB Output is correct
4 Correct 269 ms 722588 KB Output is correct
5 Correct 277 ms 722496 KB Output is correct
6 Correct 277 ms 722540 KB Output is correct
7 Correct 262 ms 722640 KB Output is correct
8 Correct 262 ms 722488 KB Output is correct
9 Correct 269 ms 722504 KB Output is correct
10 Correct 262 ms 722588 KB Output is correct
11 Correct 2163 ms 722544 KB Output is correct
12 Execution timed out 5048 ms 722580 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 722508 KB Output is correct
2 Correct 262 ms 722504 KB Output is correct
3 Correct 280 ms 722564 KB Output is correct
4 Correct 269 ms 722588 KB Output is correct
5 Correct 277 ms 722496 KB Output is correct
6 Correct 277 ms 722540 KB Output is correct
7 Correct 262 ms 722640 KB Output is correct
8 Correct 262 ms 722488 KB Output is correct
9 Correct 269 ms 722504 KB Output is correct
10 Correct 262 ms 722588 KB Output is correct
11 Correct 2163 ms 722544 KB Output is correct
12 Execution timed out 5048 ms 722580 KB Time limit exceeded
13 Halted 0 ms 0 KB -