USACO: Barn Repair

Problem Link : http://train.usaco.org/usacoprob2?a=dOLJGJAE7bv&S=barn1


/*
PROG: barn1
LANG: C++
*/
#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

bool test(int a,int b)
{
    return a>b;
}

int main()
{
    freopen("barn1.in","r",stdin);
    freopen("barn1.out","w",stdout);
    int sum=0,ans=0,m,s,c;
    int ara[300],len[300];
    cin>>m>>s>>c;
    loop(i,c)
    {
        cin>>ara[i];
    }
    ms(len,0);
    sort(ara,ara+c);
    int maxx=ara[c-1];
    int minx=ara[0];
    int cnt=0;
    sum=maxx-minx+1;

    for(int i=1;i<c;i++)
    {
        len[cnt++]=ara[i]-ara[i-1]-1;
    }

    sort(len,len+cnt,test);

    loop(i,m-1)
    {
        ans+=len[i];
    }
    cout<<sum-ans<<endl;
    return 0;
}

Advertisements

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