fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ln '\n'
  5. #define u unsigned
  6. #define f first
  7. #define ss second
  8.  
  9. ll logg(ll base ,ll x){
  10.     ll s=0;
  11.     if(!x)return 1;
  12.     while(x){
  13.         x/=base;
  14.         s++;
  15.     }
  16.     return  s;
  17. }
  18. const ll N=1000000007;
  19. const  ll mod=998244353;
  20.  
  21. ll fastPow(ll x,ll y){
  22.     if(y==0)
  23.         return 1;
  24.     //
  25.  
  26.     if(y%2==1){
  27.         ll b=x;
  28.         ll ans=fastPow(b,y/2)%N;
  29.         ans=(ans*ans)%N;
  30.         return (ans*b)%N;
  31.     }
  32.  
  33.     else{
  34.         ll b=x%N;
  35.         ll ans=fastPow(b,y/2)%N;
  36.         ans=(ans*ans)%N;
  37.         return ans;
  38.     }
  39.  
  40. }
  41. u ll GCD(u ll a, u ll b)
  42. {
  43.     return b == 0 ? a : GCD(b, a % b);
  44. }
  45. u ll lcm(u ll x,u ll y){
  46.     return (((x/GCD(x,y)))*y);
  47. }
  48. ll ceiling (ll x,ll y){
  49.     if(x%y)return x/y +1;
  50.     return x/y;
  51. }
  52. bool sortby(const pair<ll,ll>&a,const pair<ll,ll>&b){
  53.     if(a.first==b.first)
  54.         return a.second>b.second;
  55.     return a.first<b.first;
  56. }
  57. ll fact[1000000];
  58. void factorial(){
  59.     ll f=1;
  60.     fact[0]=1;
  61.     for(ll i=1;i<=15;i++){
  62.         f*=i;//f%=N;
  63.         fact[i]=f;
  64.         //mp[f]++;
  65.     }
  66. }
  67.  
  68. ll invMod(ll x){
  69.     return fastPow(x,mod-2)%mod;
  70. }
  71. bool isPrime(ll n){
  72.     if(n == 1){
  73.         return false;
  74.     }
  75.     for(ll i = 2; i*i<=n; i++){
  76.         if(n%i == 0){
  77.             return false;
  78.         }
  79.     }
  80.  
  81.     return true;
  82. }
  83. bool valid(int i,int n){
  84.     if(i>=0 && i<n)return 1;
  85.     return 0;
  86. }
  87.  
  88.  
  89. /*vector<vector<int>>v;
  90. void bits(){
  91.     ll p= fastPow(2,15);
  92.     vector<int>vvv;
  93.     v.push_back(vvv);
  94.     for(ll k=1;k<=p;k++){
  95.         int x= k;
  96.         vector<int>vin;
  97.         vector<int>vv;
  98.  
  99.         while(x){
  100.             vv.push_back(x%2);
  101.             x/=2;
  102.         }
  103.         int sz=vv.size();
  104.         ll z=15-sz;
  105.         for(int i=0;i<z;i++)vin.push_back(0);
  106.         for(int i=sz-1;i>=0;i--)vin.push_back(vv[i]);
  107.         v.push_back(vin);
  108.     }
  109. }*/
  110. ll count_bits(ll n){
  111.     ll nn=n,x=0;
  112.     while(nn){
  113.         if(nn&1)x++;
  114.         nn/=2;
  115.     }
  116.     return x;
  117. }
  118. int on_bits(long long n){
  119.     return __builtin_popcountll(n);
  120. }
  121. bool is_palindrome(ll x){
  122.     ll xx=x,y=0,len=logg(10,xx)-1;
  123.     if(len==0)return 1;
  124.     while(xx){
  125.         y+= fastPow(10,len)*(xx%10);
  126.         len--;xx/=10;
  127.     }
  128.     if(y==x)return 1;
  129.     return 0;
  130. }
  131. void solve(){
  132.     ll n,k,p;cin>>n>>k>>p;
  133.     vector<vector<ll>>bst,dp;
  134.     vector<ll>v(n+10),vk(k+10);
  135.     dp.assign(n+10,vector<ll>(k+10,0));
  136.     bst.assign(n+10,vector<ll>(k+10,0));
  137.     for(int i=1;i<=n;i++)cin>>v[i];
  138.     for(int i=1;i<=k;i++)cin>>vk[i];
  139.     multiset<ll>st;
  140.     // dp(i,k) => best senario for people from 1 to i where ith person takes kth key
  141.     // bst(i-1,k) => best senario for people from 1 to (i-1) without taking kth key
  142.     for(int i=1;i<=n;i++){
  143.         st.clear();
  144.         for(int j=1;j<=k;j++){
  145.             dp[i][j]=bst[i-1][j]+abs(v[i]-vk[j])+abs(vk[j]-p);/// calculate best!!
  146.             st.insert(dp[i][j]);
  147.         }
  148.         for(int j=1;j<=k;j++){
  149.             auto it=st.find(dp[i][j]);
  150.             st.erase(it);
  151.             bst[i][j]=*st.begin();/////////???
  152.             st.insert(dp[i][j]);
  153.         }
  154.     }
  155.     ll ans=1e18;
  156.     for(int i=1;i<=k;i++)ans=min(ans,dp[n][i]);
  157.     cout<<ans<<ln;
  158.     /// min dp[n][i] for all i =1 to k
  159. }
  160.  
  161. int main()
  162. {
  163.     ios_base::sync_with_stdio(0);
  164.     cin.tie(0);cout.tie(0);
  165.     int T=1;//cin>>T;
  166.     while(T--){
  167.         solve();
  168.     }
  169.     return 0;
  170. }
  171. /*
  172.  
  173.  */
Success #stdin #stdout 0.01s 5396KB
comments (?)
stdin
copy 
2 4 50
20 100
60 10 40 80
stdout
copy 
80
https://ideone.com/wgi9Nk
language:
C++14 (gcc 8.3)
created:
1 year 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!