답안 #555005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555005	2022-04-29T21:21:30 Z	LucaDantas	Group Photo (JOI21_ho_t3)	C++17	5 / 100	5000 ms	722640 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 ;
    	
    	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	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-