AE1B SPOJ

AE1B.cpp

// contest: http://www.spoj.com/problems/AE1B/
// author: Nguyễn Minh Tuấn
// language: C/C++
#include <bits/stdc++.h>

#define _for(i,a,b) for(int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define _it(i,v) for (typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define _all(v) v.begin(), v.end()

#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define sqr(x) ((x)*(x))
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


// __gcd algorithm
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a; 
}
// end __gcd

// power modulo algorithm
ll power_modulo(ll a, ll base, ll mod) {
    if(!base) { return 1; }
    ll temp = power_modulo(a, base / 2, mod);
    if(base & 1) return a * sqr(temp) % mod;
    return sqr(temp) % mod;
}
// end power modulo

// quick sort algorithm
void quick_sort(int A[], int l, int r) {
    int i = l, j = r;
    int pivot = A[(l + r) / 2];
    if(l >= r) return;
    while(i <= j) {
        while(A[i] < pivot) i++;
    while(A[j] > pivot) j--;
    if(i <= j) swap(A[i++], A[j--]);
    }
    quick_sort(A, l, j); quick_sort(A, i, r);
}
// End quick sort algorithm

// int_To_String algorithm
string int_To_String(int i)
{
    stringstream ss;
    ss << i;
    return ss.str();
}

int string_To_int(string s) {
    return atoi(s.c_str());
}
// end int_To_String algorithm

// KMP algorithm
int KMP(string s, string t) {
    int n = s.length(), m = t.length();
    int* pit = new int[m+1];
    if(m >= 0) pit[0] = 0;
    if(m >= 1) pit[1] = 0;
    FOR(i, 2, m) { 
        for(int j = pit[i-1]; ;j = pit[j]) {
            if(t[j] == t[i-1]) { pit[i] = j + 1; break; }
            if(j == 0) { pit[i] = 0; break; }
        }
    }
        for(int i = 0, j = 0; i < n; ) {
        if(s[i] == t[j]) {
            i++; j++;
            if(j == m) return i - m;
        } else if(j > 0) {
            j = pit[j];
        } else i++;
    } delete[] pit; return -1;
}
// end KMP algorithm

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // solution starts...

    int n, k, s;
    int A[10000];
    cin >> n >> k >> s;
    FOR(i,0,n-1) cin >> A[i];
    int cnt = 0, sum = 0;
    sort(A,A+n, greater<int>());
    FOR(i,0,n) {
        if(sum < k*s) {
            sum += A[i];
            cnt++;
        } else {
            cout << cnt << endl;
            return 0;
        }
    }
    // solution ends...

    return 0;
}