Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Apr 17th, 2012  |  syntax: None  |  size: 0.81 KB  |  hits: 18  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<fstream>
  4. #include<queue>
  5. using namespace std;
  6. ifstream f1("install.in");
  7. ofstream f2("install.out");
  8.  
  9. int N,i,T[100001],n;
  10. int W[100001];
  11. struct Per{int t,n,ind;};
  12. bool operator<(Per a,Per b)
  13.  {if(a.n>1 && b.n>1){return a.n*a.t<b.n*b.t;};
  14.   if(a.n>1)return true;
  15.   if(b.n>1)return false;}
  16. priority_queue<Per> Q;
  17. Per P;
  18.  
  19. main()
  20. {f1>>N;
  21.  for(i=0;i<N;i++)f1>>T[i];
  22.  sort(T,T+N);
  23.  
  24.  
  25.  P.n=N;
  26.  P.t=T[0];
  27.  P.ind=0;
  28.  f2<<T[0]*N<<endl;
  29.  W[0]=N;
  30.  n=N;
  31.  
  32.  for(i=1;i<N;i++){
  33.     P.n=W[i-1];
  34.     W[i]=W[i-1];
  35.     P.t=T[i];
  36.     P.ind=i;
  37.     n+=W[i-1];
  38.     Q.push(P);
  39.    
  40.     while(n>N){
  41.       P=Q.top();
  42.       Q.pop();
  43.       W[P.ind]--;
  44.       P.n--;
  45.       n--;
  46.       Q.push(P);}
  47.    
  48.     P=Q.top();
  49.     f2<<max(P.t*P.n,T[i])<<endl;
  50.   }
  51. }
create a new version of this paste RAW Paste Data