Cod sursa(job #1350056)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 20 februarie 2015 17:22:47
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#define DIM 66000
using namespace std;

ifstream fin("proc.in");
ofstream fout("proc.out");

int N,K,P,timp,n,X,C,sol;
pair <int,int> v[DIM];
int cmp(pair <int,int> a,pair <int,int> b){;
    return a.first+C*a.second<b.first+C*b.second;
}
void up(int x){
    int c,p;
    c=x;
    p=c/2;
    while(p>=1 && cmp(v[c],v[p])){
        swap(v[c],v[p]);
        c=p;
        p/=2;
    }
}
void down(int x){
    int p,c;
    p=x;
    c=p*2;
    while(c<=n){
        if(c+1<=n && cmp(v[c+1],v[c]))
            c++;
        if(cmp(v[c],v[p])){
            swap(v[c],v[p]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
void insert(int a,int b){
    v[++n]=make_pair(a,b);
    up(n);
}
int main(){
    fin>>N>>K>>P;
    C=1;
    for(int i=1;i<=N;i++)
        insert(0,i);
    X=N-K;
    C=2;
    for(int i=1;i<=X;i++){
        v[1].first+=v[1].second*C;
        down(1);
    }
    C=1;
    for(int i=1;i<=K;i++){
        v[1].first+=v[1].second;
        sol=max(sol,v[i].first);
        down(1);
    }
    fout<<sol;
    fin.close();fout.close();
    return 0;
}