Codeforces Round #570 (Div. 3)

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 int q;
22 
23 int main() {
24     cin >> q;
25     while (q--) {
26         ll k, n, a, b; cin >> k >> n >> a >> b;
27         if (n * b >= k) puts("-1");
28         else printf("%lld\n", min(n, (k - b * n - 1) / (a - b)));
29     }
30     return 0;
31 }

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int maxn = 2e5 + 10;
22 int q;
23 
24 int main() {
25     scanf("%d", &q);
26     while (q--) {
27         int n, cnt[maxn] = {0}, maxx = 0; scanf("%d", &n);
28         rep1(i, 1, n) {
29             int x; scanf("%d", &x); maxx = max(maxx, x);
30             cnt[x]++;
31         }
32         sot(cnt, maxx);
33         ll ans = cnt[maxx]; int last = cnt[maxx];
34         for (int i = maxx - 1; i; i--) {
35             if (!last || !cnt[i]) break;
36             if (cnt[i] >= last) ans += last - 1, last--;
37             else ans += cnt[i], last = cnt[i];
38         }
39         printf("%lld\n", ans);
40     }
41     return 0;
42 }

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 int n, k;
22 ll ans = 0;
23 string s;
24 queue<string>q;
25 set<string>ss;
26 
27 int main() {
28     cin >> n >> k >> s;
29     q.push(s); ss.insert(s);
30     while (!q.empty() && (int)ss.size() < k) {
31         auto curr = q.front();
32         q.pop();
33         rep1(i, 0, (int)curr.size()) {
34             string tmp = curr;
35             tmp.erase(i, 1);
36             if (ss.find(tmp) == ss.end() && ss.size() < k) {
37                 q.push(tmp); ss.insert(tmp); ans += n - tmp.size();
38             }
39         }
40     }
41     if ((int)ss.size() < k) puts("-1");
42     else printf("%lld\n", ans);
43     return 0;
44 }