fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. inline int my_getchar_unlocked(){
  5.   static char buf[1048576];
  6.   static int s = 1048576;
  7.   static int e = 1048576;
  8.   if(s == e && e == 1048576){
  9.     e = fread_unlocked(buf, 1, 1048576, stdin);
  10.     s = 0;
  11.   }
  12.   if(s == e){
  13.     return EOF;
  14.   }
  15.   return buf[s++];
  16. }
  17. inline void rd(int &x){
  18.   int k;
  19.   int m=0;
  20.   x=0;
  21.   for(;;){
  22.     k = my_getchar_unlocked();
  23.     if(k=='-'){
  24.       m=1;
  25.       break;
  26.     }
  27.     if('0'<=k&&k<='9'){
  28.       x=k-'0';
  29.       break;
  30.     }
  31.   }
  32.   for(;;){
  33.     k = my_getchar_unlocked();
  34.     if(k<'0'||k>'9'){
  35.       break;
  36.     }
  37.     x=x*10+k-'0';
  38.   }
  39.   if(m){
  40.     x=-x;
  41.   }
  42. }
  43. inline void rd(long long &x){
  44.   int k;
  45.   int m=0;
  46.   x=0;
  47.   for(;;){
  48.     k = my_getchar_unlocked();
  49.     if(k=='-'){
  50.       m=1;
  51.       break;
  52.     }
  53.     if('0'<=k&&k<='9'){
  54.       x=k-'0';
  55.       break;
  56.     }
  57.   }
  58.   for(;;){
  59.     k = my_getchar_unlocked();
  60.     if(k<'0'||k>'9'){
  61.       break;
  62.     }
  63.     x=x*10+k-'0';
  64.   }
  65.   if(m){
  66.     x=-x;
  67.   }
  68. }
  69. inline long long rd_ll(void){
  70.   long long x;
  71.   rd(x);
  72.   return x;
  73. }
  74. struct MY_WRITER{
  75.   char buf[1048576];
  76.   int s;
  77.   int e;
  78.   MY_WRITER(){
  79.     s = 0;
  80.     e = 1048576;
  81.   }
  82.   ~MY_WRITER(){
  83.     if(s){
  84.       fwrite_unlocked(buf, 1, s, stdout);
  85.     }
  86.   }
  87. }
  88. ;
  89. MY_WRITER MY_WRITER_VAR;
  90. void my_putchar_unlocked(int a){
  91.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  92.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  93.     MY_WRITER_VAR.s = 0;
  94.   }
  95.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  96. }
  97. inline void wt_L(char a){
  98.   my_putchar_unlocked(a);
  99. }
  100. inline void wt_L(long long x){
  101.   int s=0;
  102.   int m=0;
  103.   char f[20];
  104.   if(x<0){
  105.     m=1;
  106.     x=-x;
  107.   }
  108.   while(x){
  109.     f[s++]=x%10;
  110.     x/=10;
  111.   }
  112.   if(!s){
  113.     f[s++]=0;
  114.   }
  115.   if(m){
  116.     my_putchar_unlocked('-');
  117.   }
  118.   while(s--){
  119.     my_putchar_unlocked(f[s]+'0');
  120.   }
  121. }
  122. template<class T> inline T popFirst(multiset<T> &a){
  123.   T res = *(a.begin());
  124.   a.erase(a.begin());
  125.   return res;
  126. }
  127. template<class T> inline T getFirst(multiset<T> &a){
  128.   return *(a.begin());
  129. }
  130. template<class T> inline T popLast(multiset<T> &a){
  131.   T res;
  132.   typename multiset<T>::iterator it;
  133.   it = a.end();
  134.   it--;
  135.   res = *it;
  136.   a.erase(it);
  137.   return res;
  138. }
  139. template<class T> inline T getLast(multiset<T> &a){
  140.   typename multiset<T>::iterator it;
  141.   it = a.end();
  142.   it--;
  143.   return *it;
  144. }
  145. template<class T> inline T popFirst(set<T> &a){
  146.   T res = *(a.begin());
  147.   a.erase(a.begin());
  148.   return res;
  149. }
  150. template<class T> inline T getFirst(set<T> &a){
  151.   return *(a.begin());
  152. }
  153. template<class T> inline T popLast(set<T> &a){
  154.   T res;
  155.   typename set<T>::iterator it;
  156.   it = a.end();
  157.   it--;
  158.   res = *it;
  159.   a.erase(it);
  160.   return res;
  161. }
  162. template<class T> inline T getLast(set<T> &a){
  163.   typename set<T>::iterator it;
  164.   it = a.end();
  165.   it--;
  166.   return *it;
  167. }
  168. int N;
  169. int K;
  170. int R;
  171. int A;
  172. multiset<long long> a;
  173. multiset<long long> b;
  174. long long s;
  175. long long t;
  176. long long u;
  177. int ress;
  178. long long res[200000];
  179. int main(){
  180.   int FmcKpFmN, Lj4PdHRW, e98WHCEY;
  181.   rd(N);
  182.   rd(K);
  183.   rd(R);
  184.   for(Lj4PdHRW=(0);Lj4PdHRW<(K);Lj4PdHRW++){
  185.     rd(A);
  186.     a.insert(A);
  187.     s += A;
  188.   }
  189.   for(e98WHCEY=(0);e98WHCEY<(N-K);e98WHCEY++){
  190.     b.insert(rd_ll());
  191.   }
  192.   for(FmcKpFmN=(0);FmcKpFmN<(R);FmcKpFmN++){
  193.     t = s;
  194.     s -= popFirst(a);
  195.     a.insert(t);
  196.     s += t;
  197.     if(b.size() && getLast(a) > getFirst(b)){
  198.       t = popLast(a);
  199.       u = popFirst(b);
  200.       a.insert(u);
  201.       b.insert(t);
  202.       s += u - t;
  203.     }
  204.   }
  205.   for(long long x : a){
  206.     res[ress++] = x;
  207.   }
  208.   for(long long x : b){
  209.     res[ress++] = x;
  210.   }
  211.   {
  212.     int a2conNHc;
  213.     if(ress==0){
  214.       wt_L('\n');
  215.     }
  216.     else{
  217.       for(a2conNHc=(0);a2conNHc<(ress-1);a2conNHc++){
  218.         wt_L(res[a2conNHc]);
  219.         wt_L(' ');
  220.       }
  221.       wt_L(res[a2conNHc]);
  222.       wt_L('\n');
  223.     }
  224.   }
  225.   return 0;
  226. }
  227. // cLay varsion 20201031-1
  228.  
  229. // --- original code ---
  230. // int N, K, R, A;
  231. // multiset<ll> a, b;
  232. // ll s, t, u;
  233. // int ress; ll res[2d5];
  234. // {
  235. //   rd(N,K,R);
  236. //   rep(K){
  237. //     rd(A);
  238. //     a.insert(A);
  239. //     s += A;
  240. //   }
  241. //   rep(N-K) b.insert(rd_ll());
  242. // 
  243. //   rep(R){
  244. //     t = s;
  245. //     s -= popFirst(a);
  246. //     
  247. //     a.insert(t);
  248. //     s += t;
  249. // 
  250. //     if(b.size() && getLast(a) > getFirst(b)){
  251. //       t = popLast(a);
  252. //       u = popFirst(b);
  253. //       a.insert(u);
  254. //       b.insert(t);
  255. //       s += u - t;
  256. //     }
  257. //   }
  258. // 
  259. //   for(ll x : a) res[ress++] = x;
  260. //   for(ll x : b) res[ress++] = x;
  261. //   wt(res(ress));
  262. // }
  263.  
Time limit exceeded #stdin #stdout 5s 4328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zm6aJ7
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!