Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <cstdio>
- #include <cstdlib>
- #include <set>
- #include <string>
- #include <algorithm>
- #include <stack>
- #include <map>
- #include <fstream>
- #pragma GCC optimize("no-stack-protector")
- #pragma comment(linker, "/STACK:99999999999999999")
- using namespace std;
- const long double eps = 1e-10;
- const long double inf = 999999999999999;
- const long double pi = 3.141592653589793238462643383279;
- ostream& operator << (ostream& out, const vector<long long>& s){
- for (int i = 0; i < s.size(); ++i){
- out << s[i] << ' ';
- }
- return out;
- }
- ostream& operator << (ostream& out, pair<int, int>& a){
- out << a.first << ' ' << a.second;
- return out;
- }
- struct heap{
- vector<int> a;
- void del(){
- swap(a[a.size() - 1], a[1]);
- a.pop_back();
- down(1);
- }
- void up(int i){
- while (i > 1 && a[i] > a[i / 2]){
- swap(a[i], a[i/2]);
- i /= 2;
- }
- }
- void down(int i){
- while (i * 2 < a.size()){
- int right = i * 2 + 1;
- int left = i * 2;
- int j = left;
- if (right < a.size() && a[right] > a[left]){
- j = right;
- }
- if (a[i] >= a[j]){
- break;
- }
- swap(a[i], a[j]);
- i = j;
- }
- }
- };
- long long Binss(const vector<int>& goo, long long z, int k){
- int l = 0, r = goo.size();
- while (r - l > 1){
- int mid = (r + l) / 2;
- if (mid >= ceil(((double)(z - goo[mid])) / k)){
- r = mid;
- } else{
- l = mid;
- }
- }
- return r;
- }
- int main(){
- // freopen("coins.in", "r", stdin);
- // freopen("coins.out", "w", stdout);
- // cout.precision(10);
- // cout << fixed;
- // ifstream fin("input.txt");
- cin.tie(0);
- ios_base::sync_with_stdio(false);
- int n, x, k;
- cin >> n >> x >> k;
- long long z = 0;
- int w = 0;
- heap goo;
- goo.a.push_back(0);
- for (int i = 0; i < n; ++i){
- int f;
- cin >> f;
- z += f;
- if (x != 0){
- w += f / x;
- f %= x;
- }
- if (f != 0){
- goo.a.push_back(f);
- goo.up(goo.a.size() - 1);
- }
- }
- vector<int> koo;
- for (int i = 0; i < w; ++i){
- if (i == 0){
- koo.push_back(x);
- continue;
- }
- koo.push_back(koo[i - 1] + x);
- }
- while (goo.a.size() > 1){
- if (koo.size() == 0){
- koo.push_back(goo.a[1]);
- } else{
- koo.push_back(koo[koo.size() - 1] + goo.a[1]);
- }
- goo.del();
- }
- cout << Binss(koo, z, k);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement