SRM322 D1E-D2M GroupWork

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

仕事スキルが$s_i$の人が$p_i$人いる．同じグループの人はその中で最小の仕事スキルと同じ仕事スキルになる．よってグループのグループの生産力は，グループ人数を$K$，グループの中の最小仕事スキルを$X$とおくと$K \times X$となる．グループの生産力の最大値を求める．

生産力はグループ人数と最小仕事スキルで決まるので，最小仕事スキルを決めると，それ以上の仕事スキルの人はいればいるほど生産力はあがる．最小仕事スキル$X$を全探索して，それ以上の人数をかけた値のmaxを取った．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class GroupWork {

    public:

    long long bestGroup(vector <int> p, vector <int> s) {
      int n = p.size();

      vector<pair<ll, ll> > v(n);
      rep(i, n) {
          v[i].first = s[i];
          v[i].second = p[i];
      }

      sort(v.begin(), v.end());

      ll ans = 0;
      rep(i, n) {
          ll cnt = 0;
          REP(j, i, n) {
              cnt += v[j].second;
          }
          ans = max(ans, cnt * v[i].first);
      }

      return ans;
    }
};
Nov 18th, 2016
srm, topcoder