codeforces Gym 100500C C. ICPC Giveaways 排序

Problem C. ICPC Giveaways
Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/gym/100500/attachments

Description

During the preparation for the ICPC contest, the organizers prepare bags full of giveaways for the contestants. Each bag usually contains an MP3 Player, a Sim Card, a USB HUB, a USB Flash Drive, ... etc. A problem happened during the delivery of the components of the bags, so not every component was delivered completely to the organizers. For example the organizers ordered 10 items of 4 different types, and what was delivered was 7, 6, 8, 9 from each type respectively. The organizers decided to form bags anyway, but they have to abide by 2 rules. All formed bags should have exactly the same items, and no bag should contain 2 items of the same type (either 1 or 0). Knowing that each item has an amusement value (for sure an MP3 Player is much more amusing than a Sim Card), the organizers decided to get the max possible total amusement. The total amusement is the amusement value of a single bag multiplied by the number of bags. Note that not every contestant should receive a bag. The amusement value of each item type is calculated using this equation:(i × i) mod C where i is an integer that represents the item type, and C is a value that will be given as an input. Please help the ICPC organizers to determine what the maximum total amusement is.

Input

T is the number of test cases. For each test case there will be 3 integers M,N and C, where M is the number of items, N is the total number of types, and C is as described above then M integer representing the type of each item. 1 ≤ T ≤ 100 1 ≤ M ≤ 10, 000 1 ≤ N ≤ 10, 000 1 ≤ C ≤ 10, 000 1 ≤ itemi ≤ N

Output

For each test case print a single line containing: Case_x:_y x is the case number starting from 1. y is the required answer. Replace the underscores with spaces.

Sample Input

1 10 3 9 1 1 2 2 1 1 2 3 1 2

Sample Output

Case 1: 20

HINT

题意

要求你准备袋子，每个袋子里的东西都要求完全一样，然后问你价值最高为多少，价值=袋子的价格*可以准备的袋子数量

题解：

排序，然后O(n)扫一遍就好啦~

代码

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

const int maxn=;

#define mod 1000000007

#define eps 1e-9

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//*************************************************************************************

struct node

{

    ll x,y;

};

ll m,n,c;

bool cmp(node a,node b)

{

    if(a.x==b.x)

        return a.y>b.y;

    return a.x>b.x;

}

node a[];

int main()

{

    int t=read();

    for(int cas=;cas<=t;cas++)

    {

        m=read(),n=read(),c=read();

        memset(a,,sizeof(a));

        for(int i=;i<=n;i++)

            a[i].y=(i*i)%c;

        for(int i=;i<=m;i++)

        {

            ll x=read();

            a[x].x++;

        }

        sort(a+,a+n+,cmp);

        ll ans=;

        ll sum=;

        for(int i=;i<=n;i++)

        {

            if(a[i].x==)

                break;

            sum+=a[i].y;

            ans=max(ans,a[i].x*sum);

        }

        printf("Case %d: %lld\n",cas,ans);

    }

}

巴特西

codeforces Gym 100500C C. ICPC Giveaways 排序

最新文章

热门文章