Barn Repair


/*
ID: tausiq11
PROG: barn1
LANG: C++
*/

#include <cstdio>
#include <algorithm>
using namespace std;

int main ()
{
    freopen ("barn1.in", "r", stdin);
	freopen ("barn1.out", "w", stdout);

    int m;
    int s;
    int c;
    int stalls [205];

    scanf ("%d %d %d", &m, &s, &c);

    for ( int i = 0; i < c; i++ )
        scanf ("%d", &stalls [i] );

    sort (stalls, stalls + c);

    int diff [205];
    int index = 0;

    for ( int i = 1; i < c; i++ )
        diff [index++] = (stalls [i] - stalls [i - 1]) - 1;

    sort (diff, diff + index);

    int minimize = 0;

    if ( index <= m - 1 ) {
        for ( int i = 0; i < index; i++ )
        minimize += (diff [i]);
    }

    else {
        for ( int i = 0; i < m - 1; i++ )
            minimize += (diff [--index]);
    }

    minimize = s - minimize;
    minimize -= stalls [0] - 1;
    minimize -= (s - stalls [c - 1]);

    printf ("%d\n", minimize);
    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s