fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<bits/stdc++.h>
  3. #define vi vector<int>
  4. #define int long long 
  5. #define pf printf
  6. #define mod 1000000009
  7. using namespace std;
  8. void boost(){
  9.     ios_base::sync_with_stdio(0); 
  10.     cin.tie(0); 
  11.     cout.tie(0); 
  12. }
  13. int pow(int n,int m){
  14.     if(m%2==0){
  15.       int pro=pow(n,m/2);
  16.       return ((pro)%mod*(pro)%mod)%mod;
  17.     }else{
  18.        return ((n)%mod*(pow(n,m-1))%mod)%mod;
  19.     }
  20. }
  21. int32_t main(){
  22.   boost();
  23.   int t,t1=0;
  24.   cin>>t;
  25.   while(t--){
  26.       t1++;
  27.       int w,n;
  28.       cin>>w>>n;
  29.       int a[w]={0};
  30.       for(int i=0;i<w;i++){
  31.           cin>>a[i];
  32.       }
  33.       sort(a,a+w);
  34.       int prefix[w]={0};
  35.       int suffix[w+1]={0};
  36.       suffix[w]=0;
  37.       int ans[n]={0};
  38.       for(int i=0;i<w;i++){
  39.           if(i==0){
  40.               prefix[i]=a[i];
  41.           }else{
  42.               prefix[i]=prefix[i-1]+a[i];
  43.           }
  44.       }
  45.       for(int i=w-1;i>=0;i--){
  46.           if(i==w-1){
  47.               suffix[i]=n-a[i];
  48.           }else{
  49.               suffix[i]=suffix[i+1]+n-a[i];
  50.           }
  51.       }
  52.       for(int i=0;i<w;i++){
  53.         int curr=a[i];
  54.         int low=i+1,high=w-1;
  55.         while(low<=high){
  56.             int mid=low+(high-low)/2;
  57.             int front=a[mid]-a[i];
  58.             int back=n-a[mid]+a[i];
  59.             if(front<=back){
  60.                 low=mid+1;
  61.             }else{
  62.                 high=mid-1;
  63.             }
  64.         }
  65.         if(low-1>=0){
  66.             ans[i]=(prefix[low-1]-prefix[i]-(low-1-i)*a[i])+(suffix[0]-suffix[i])-i*(n-a[i]);
  67.             if(low<w){
  68.                 ans[i]+=(suffix[low]+(w-low)*a[i]);
  69.             }
  70.         }  
  71.       }
  72.       int mini=LONG_LONG_MAX;
  73.       for(int i=0;i<w;i++){
  74.           mini=min(mini,ans[i]);
  75.       }
  76.       pf("Case #%lld: %lld\n",t1,mini);
  77.   }
  78. return 0;
  79. }
Runtime error #stdin #stdout 0s 4452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A7wLX4
language:
C++14 (gcc 8.3)
created:
5 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!