제출 #942191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942191		dsyz	Group Photo (JOI21_ho_t3)	C++17	0 / 100	0 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll H[N];
	for(ll i = 0;i < N;i++){
		cin>>H[i];
	}
	ll dp[N][1ll<<N];
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < (1ll<<N);j++){
			dp[i][j] = 1e18;
		}
	}
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < (1ll<<N);j++){
			ll on = 0;
			for(ll bit = 0;bit < N;bit++){
				if(j & (1ll<<bit)){
					on++;
				}
			}
			if(on != i + 1) continue;
			if(i == 0){
				ll first = 0;
				for(ll bit = 0;bit < N;bit++){
					if(j & (1ll<<bit)){
						first = bit;
					}
				}
				dp[i][j] = first;
				continue;
			}
			for(ll bit = 0;bit < N;bit++){
				if(j & (1ll<<bit)){
					ll minus = 0;
					for(ll b = 0;b < bit;b++){
						if(j & (1ll<<b)){
							minus++;
						}
					}
					ll right = 0;
					for(ll b = bit + 1;b < N;b++){
						if(j & (1ll<<b)){
							right++;
						}
					}
					if(bit + right <= i) dp[i][j] = min(dp[i][j],dp[i - 1][j ^ (1ll<<bit)]);
					else dp[i][j] = min(dp[i][j],dp[i - 1][j ^ (1ll<<bit)] + (bit + right - i) - minus);
				}
			}
		}
	}
	cout<<dp[N - 1][(1ll<<N) - 1]<<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36