I thought about it for a long time and i am cleearly commenting the code to help understand it easily ↵
↵
↵
↵
#include<bits/stdc++.h>↵
#include <iostream>↵
using namespace std;↵
#define rep(i,x,y) for(int i=x; i<=y; i++)↵
#define ll long long↵
#define inf 1000000000000↵
void solve() {↵
int n, sum = 0, ans = 0, no1, no0, k, smal = inf;↵
cin >> n;↵
int a[n];↵
vector< int > v1, v0;↵
rep(i, 0, n — 1) {↵
cin >> a[i];↵
if (a[i])v1.push_back(i);↵
else v0.push_back(i);↵
}↵
no1 = v1.size();↵
no0 = n — no1;↵
if (no1 == 0) {↵
cout << "0" << endl;↵
return;↵
}↵
// all ar zero indexed↵
// dp[i][j] — min cost by choosing first i person and assigning to any of first j empty chairs(trivially i<=j)↵
// main transition is — dp[i][j] = min(dp[i][j — 1] , dp[i — 1][j — 1] + abs(v1[i] — v0[j]));↵
// meaning- u did not consider last chair(leaving it empty) then dp[i][j-1] or u considerd it and gave the last chair to last person↵
//ans will be dp[nop][noo]↵
int dp[no1][no0];↵
rep(i, 0, no1 — 1)↵
rep(j, 0, no0 — 1)↵
dp[i][j] = inf; // because finding minimum we do this↵
dp[0][0] = abs(v1[0] — v0[0]);// base case-to place zeroth person in zeroth chair↵
rep(i, 0, no1 — 1) {↵
rep(j, 1, no0 — 1) {↵
if (i <= j) { // otherwise it is not possible↵
if (i == 0) dp[i][j] = min(dp[i][j — 1] , abs(v1[i] — v0[j]));//easy↵
else {↵
if (i != j) dp[i][j] = min(dp[i][j — 1] , dp[i — 1][j — 1] + abs(v1[i] — v0[j]));↵
else dp[i][j] = dp[i — 1][j — 1] + abs(v1[i] — v0[j]);↵
}↵
}↵
}↵
}↵
cout << dp[no1 — 1][no0 — 1] << endl;↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(nullptr);↵
solve();↵
}↵
↵
↵
i cannot code it here properly for some reason ,so check my submission ↵
↵
↵
#include<bits/stdc++.h>↵
#include <iostream>↵
using namespace std;↵
#define rep(i,x,y) for(int i=x; i<=y; i++)↵
#define ll long long↵
#define inf 1000000000000↵
void solve() {↵
int n, sum = 0, ans = 0, no1, no0, k, smal = inf;↵
cin >> n;↵
int a[n];↵
vector< int > v1, v0;↵
rep(i, 0, n — 1) {↵
cin >> a[i];↵
if (a[i])v1.push_back(i);↵
else v0.push_back(i);↵
}↵
no1 = v1.size();↵
no0 = n — no1;↵
if (no1 == 0) {↵
cout << "0" << endl;↵
return;↵
}↵
// all ar zero indexed↵
// dp[i][j] — min cost by choosing first i person and assigning to any of first j empty chairs(trivially i<=j)↵
// main transition is — dp[i][j] = min(dp[i][j — 1] , dp[i — 1][j — 1] + abs(v1[i] — v0[j]));↵
// meaning- u did not consider last chair(leaving it empty) then dp[i][j-1] or u considerd it and gave the last chair to last person↵
//ans will be dp[nop][noo]↵
int dp[no1][no0];↵
rep(i, 0, no1 — 1)↵
rep(j, 0, no0 — 1)↵
dp[i][j] = inf; // because finding minimum we do this↵
dp[0][0] = abs(v1[0] — v0[0]);// base case-to place zeroth person in zeroth chair↵
rep(i, 0, no1 — 1) {↵
rep(j, 1, no0 — 1) {↵
if (i <= j) { // otherwise it is not possible↵
if (i == 0) dp[i][j] = min(dp[i][j — 1] , abs(v1[i] — v0[j]));//easy↵
else {↵
if (i != j) dp[i][j] = min(dp[i][j — 1] , dp[i — 1][j — 1] + abs(v1[i] — v0[j]));↵
else dp[i][j] = dp[i — 1][j — 1] + abs(v1[i] — v0[j]);↵
}↵
}↵
}↵
}↵
cout << dp[no1 — 1][no0 — 1] << endl;↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(nullptr);↵
solve();↵
}↵
↵
↵
