LightOJ ACM ICPC Preliminary 2016 Team Practice Contest G. Chocolates

Problem Link: G.Chocolates


//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
//#define i64 long long

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

vll v;

int main()
{
    int t;
    LL k , m , n , i , sum=0 , x , ans=0 , tmp;
    sf("%d", &t);
    while(t--)
    {
        v.clear();

        sf("%lld %lld %lld", &k, &m , &n);

        for(i=0; i<k; i++)
        {
            sf("%lld", &x);
            v.push_back(x);
        }

        sort(v.rbegin(), v.rend()); //for(i=0; i<k; i++) cerr << v[i] << " ";

        sum = ans = 1;

        for(i=1; i<k; i++)
        {
            if(v[i-1] == v[i])
            {
                ans+=sum;
            }

            else
            {
                sum+=(m * (v[i-1] - v[i]));
                ans+=sum;
            }
        }

        //cerr << ans << "\n";

        if(ans > n)
        {
            pf("impossible\n");
        }

        else
        {
            tmp = (n - ans) / k;

            pf("%lld\n", (tmp * k) + ans);
        }
    }

    return 0;
}