oj.uz

Submission #942191

# Submission time Handle Problem Language Result Execution time Memory
942191 2024-03-10T10:40:01 Z dsyz Group Photo (JOI21_ho_t3) C++17
0 / 100
 0 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -