Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

Educational Codeforces Round 109 -Armchairs
Difference between en1 and en2, changed 1,851 character(s)
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 &mdash; 1) {↵
        cin >> a[i];↵
        if (a[i])v1.push_back(i);↵
        else  v0.push_back(i);↵
    }↵
    no1 = v1.size();↵
    no0 = n &mdash; no1;↵
    if (no1 == 0) {↵
        cout << "0" << endl;↵
        return;↵
    }↵
// all ar zero indexed↵
// dp[i][j] &mdash; min cost by choosing first i person and assigning to any of first j empty chairs(trivially i<=j)↵
// main transition  is  &mdash; dp[i][j] = min(dp[i][j &mdash; 1] , dp[i &mdash; 1][j &mdash; 1] + abs(v1[i] &mdash; 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 &mdash; 1)↵
    rep(j, 0, no0 &mdash; 1)↵
    dp[i][j] = inf; // because finding minimum we do this↵
    dp[0][0] = abs(v1[0] &mdash; v0[0]);// base case-to place zeroth person in zeroth chair↵
    rep(i, 0, no1 &mdash; 1) {↵
        rep(j, 1, no0 &mdash; 1) {↵
            if (i <= j) { // otherwise it is not possible↵
                if (i == 0) dp[i][j] = min(dp[i][j &mdash; 1] , abs(v1[i] &mdash; v0[j]));//easy↵
                else {↵
                    if (i != j) dp[i][j] = min(dp[i][j &mdash; 1] , dp[i &mdash; 1][j &mdash; 1] + abs(v1[i] &mdash; v0[j]));↵
                    else dp[i][j] = dp[i &mdash; 1][j &mdash; 1] + abs(v1[i] &mdash; v0[j]);↵
                }↵
            }↵
        }↵
    }↵
    cout << dp[no1 &mdash; 1][no0 &mdash; 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 

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)