ACM (UVa) : 11389


// http://uva.onlinejudge.org/external/113/11389.html

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

int main ()
{
    int n;
    int d;
    int r;

    while ( scanf ("%d %d %d", &n, &d, &r) ) {

        if ( !n && !d && !r )
            return 0;

        int morn [102];
        int eve [102];

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

        sort (morn, morn + n);

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

        sort (eve, eve + n);

        int cost = 0;

        for ( int i = 0; i < n; i++ ) {
            int temp = morn [i] + eve [n - i - 1];

            if ( temp > d )
                cost += (temp - d);
        }

        printf ("%d\n", cost * r);

    }

    return 0;
}
Advertisements

4 thoughts on “ACM (UVa) : 11389

  1. @mr,
    probably i don’t get ur point
    u need explanation of the solution to understand the problem?
    may be u r on a wrong track ..
    first off, try to understand the problem and try to solve it
    if u can’t solve the problem then see the Uva forums
    and after that you can see the solution and try to figure out ur mistakes .. good luck 🙂

  2. Can you please Describe Why we check the i th sorted element of the First array and (n-i)th sorted element of Second array ??
    Why we can’t Check the i’th element of both Normal Array / Sorted array or i th unsorted element of the First array and (n-i)th unsorted element of Second array ??

  3. @Dhruvbo
    We sorted both arrays in ascending order.
    So, lowest value will be at the beginning of each array
    and, highest value will be at the end of each array.

    If we assign, morn [0] + eve [0] to a driver, then we are giving him the highest advantage among all. Aren’t we? He has to drive the lowest possible distance.

    Similarly, if we assign morn [n – 1] + eve [n – 1] to a driver, then we are making his life miserable. He has to drive the largest possible distance. Moreover, the authority may need to pay him a good overtime amount.

    But as you know, we are trying to minimize the overtime amount. Can you see why I did, what I had done? Give it a shot, I believe you will get the point. 🙂

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