include iostream include vector include set include map include algori

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n, k;
cin >> n >> k;
map<int, multiset< int > > g;
for (int i = 0; i < n; ++i) {
int m, p;
cin >> m >> p;
g[m].insert(p);
}
if (k > n || g.size() < k) {
cout << 0 << " " << 0 << endl;
return 0;
}
map<int, int> num;
for (map<int, multiset<int> >::iterator it = g.begin(); it != g.end(); ++it) {
num[(it->second.size())]++;
}
int maxlen = 0;
int cnt = 0;
for (map<int, int>::iterator it = num.begin(); it != num.end(); ++it) {
if (it->first > maxlen && it->second >= k) {
maxlen = it->first;
cnt = it->second;
}
}
/* if (num.size() < k) {
multiset<int> st;
for (map<int, multiset<int> >::iterator it = g.begin(); it != g.end(); ++it) {
st.insert(*(it->second.rbegin()));
}
int sum = 0;
int i_pref = st.size() - k;
int i = 0;
for (multiset<int>::iterator it = st.begin(); i < st.size(); ++it, ++i) {
if (i >= i_pref) {
sum += *it;
}
}
cout << 1 << " " << sum << endl;
system("pause");
return 0;
} else { */
/* int mxsz1 = 0, mxsz2 = 0;
for (set<int>::iterator it = num.begin(); it != num.end(); ++it) {
if (g[*it].size() > mxsz1) {
mxsz1 = g[*it].size();
} else if (g[*it].size() > mxsz2) {
mxsz2 = g[*it].size();
}
}
int mx = min(mxsz1, mxsz2);
for (set<int>::iterator it = num.begin(); it != num.end(); ++it) {
if (g[*it].size() < mx) {
g.erase(*it);
}
} */
vector<int> sums;
for (map<int, multiset<int> >::iterator it = g.begin(); it != g.end(); ++it) {
int sum = 0;
int i = 0;
int i_pref = it->second.size() - maxlen;
if (it->second.size() >= maxlen) {
for (multiset<int>::iterator im = it->second.begin(); im != it->second.end(); ++im, ++i) {
if (i >= i_pref)
sum += *im;
}
}
sums.push_back(sum);
}
sort(sums.rbegin(), sums.rend());
int sum = 0;
for (int i = 0; i < k; ++i) {
sum += sums[i];
}
cout << maxlen << " " << sum << endl;
//system("pause");
return 0;
}