Educational Codeforces Round 109 -Armchairs

Revision en1, by electro177, 2021-05-18 10:02:20

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

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(); }

Tags iterative dp, editorial, #implementation, # dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English electro177 2021-05-18 10:07:14 1851
en1 English electro177 2021-05-18 10:02:20 2061 Initial revision (published)