fork download 
  1. /*
  2.     Author: Nguyen Nhut Truong
  3.     From Chuyen Tien Giang High School For The Gifed
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. //#define int long long
  9. #define start signed main
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define eb emplace_back
  14. #define il pair<int,ll>
  15. #define ii pair<int,int>
  16. #define len(s) (int)s.size()
  17. #define all(s) (s).begin(),(s).end()
  18. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  19.  
  20. #define MASK(x) ((1LL)<<(x))
  21. #define Bit(x,i) (((x)>>(i))&1)
  22. #define Countbit(x) __builtin_popcountll(x)
  23.  
  24. typedef long long ll;
  25. typedef long double ld;
  26.  
  27. int dx[]={1,-1,0,0,-1,1,1,-1};
  28. int dy[]={0,0,1,-1,-1,-1,1,1};
  29.  
  30. template <class C> bool Minimize(C &a, C b) { if (a>b) { a=b; return true; } return false;}
  31. template <class C> bool Maximize(C &a, C b) { if (a<b) { a=b; return true; } return false;}
  32.  
  33. inline ll add(ll a,ll b,ll c) { return (a+b)%c; };
  34. inline ll suf(ll a,ll b,ll c) { return (a-b+c)%c; };
  35. inline ll mul(ll a,ll b,ll c) { return ((a%c)*(b%c))%c; };
  36.  
  37. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  38.  
  39. ll rand(ll l,ll r){
  40.     assert(l<=r);
  41.     return l+rd()%(r-l+1);
  42. }
  43.  
  44. void MakeInp() {
  45.     ofstream cout("Task.inp");
  46.  
  47.     cout.close();
  48. }
  49.  
  50. /// Constant Limit
  51.  
  52. const int N=1e5+5,M=1e3+5,INF=1e9,lim=1e6;
  53. const int block=448,base=31;
  54.  
  55. ll Mod=1e9+7,Mod_base=1777777777,LNF=1e18;
  56.  
  57. ///________________________________________________________________________________________________________
  58.  
  59.  
  60. ll a[N];
  61. int n,q;
  62.  
  63. namespace task1{
  64.     ll b[N];
  65.  
  66.     void solve() {
  67.         while (q--) {
  68.             ll c;
  69.             int k; cin>>c>>k;
  70.             for (int i=1;i<=n;++i)
  71.             if (a[i]<=c) b[i]=a[i]; else b[i]=2*c-a[i];
  72.  
  73.             sort(b+1,b+n+1);
  74.             ll res=0;
  75.             for (int i=1;i<=k;++i) res+=b[i];
  76.  
  77.             cout<<res<<'\n';
  78.         }
  79.     }
  80. }
  81.  
  82. namespace task2 {
  83.     ll pre[N];
  84.  
  85.     ll f(ll x,int k,ll c) {
  86.         ll y=k-x;
  87.         ll j=n-y+1;
  88.  
  89.         // j+y-1=n
  90.         // j=n-y+1
  91.         // j-1=n-y
  92.  
  93.         return pre[x]+2*c*y-(pre[n]-pre[n-y]);
  94.     }
  95.  
  96.     void solve() {
  97.         sort(a+1,a+n+1);
  98.         for (int i=1;i<=n;++i) pre[i]=pre[i-1]+a[i];
  99.  
  100.         while (q--) {
  101.             ll c,res=0;
  102.             int k; cin>>c>>k;
  103.  
  104.             int l=0,r=k;
  105.             while (l<=r) {
  106.                 int m1=l+(r-l)/3;
  107.                 int m2=r-(r-l)/3;
  108.  
  109.                 if (f(m1,k,c)<=f(m2,k,c)) {
  110.                     res=m1;
  111.                     r=m2-1;
  112.                 } else l=m1+1;
  113.             }
  114.  
  115.             cout<<f(res,k,c)<<'\n';
  116.         }
  117.     }
  118. }
  119.  
  120. start() {
  121.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  122.     OpenFile("APEN");
  123.  
  124.     cin>>n>>q;
  125.     for (int i=1;i<=n;++i) cin>>a[i];
  126.  
  127.     //task1::solve();
  128.     //task2::solve();
  129.  
  130.     if (n<=1e3 && q<=1e3) task1::solve(); else task2::solve();
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.     //cerr<<"\nBien dich thanh cong\nTime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/OAcexe
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

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!