fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define inf 10000000000000
  4. #define pi pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define maxn 5050
  8. using namespace std;
  9. int n,m;
  10. ll dp[maxn];
  11. int vt[maxn][maxn];
  12. int a[maxn];
  13. ll s[maxn];
  14. pi b[maxn];
  15. int main()
  16. {
  17.     ios::sync_with_stdio(false);
  18.     cin.tie(nullptr);
  19.     cout.tie(nullptr);
  20.     cin>>n>>m;
  21.     for(int i=1; i<=n; i++)
  22.     {
  23.         cin>>a[i];
  24.     }
  25.     sort(a+1,a+n+1);
  26.     for(int i=1; i<=m; i++)
  27.     {
  28.         cin>>b[i].fi>>b[i].se;
  29.     }
  30.     sort(b+1,b+m+1);
  31.     for(int i=n; i>=1; i--)
  32.     {
  33.         dp[i]=inf;
  34.     }
  35.     for(int j=1; j<=m; j++)
  36.     {
  37.         for(int i=1; i<=n; i++)
  38.         {
  39.             s[i]=s[i-1]+abs(a[i]-b[j].fi);
  40.         }
  41.         deque<int>q;
  42.         int c=b[j].se;
  43.         for(int i=n; i>=max(n-c+2,0); i--)
  44.         {
  45.             while(!q.empty()&&dp[q.back()-1]+s[n]-s[q.back()-1]>dp[i-1]+s[n]-s[i-1])q.pop_back();
  46.             q.push_back(i);
  47.         }
  48.         for(int i=n; i>=1; i--)
  49.         {
  50.             while(!q.empty()&&q.front()>i)
  51.             {
  52.                 q.pop_front();
  53.             }
  54.             if(i-c+1>=1)
  55.             {
  56.                 int p=i-c+1;
  57.                 while(!q.empty()&&dp[q.back()-1]+s[n]-s[q.back()-1]>dp[p-1]+s[n]-s[p-1])q.pop_back();
  58.                 q.push_back(p);
  59.             }
  60.             dp[i]=min(dp[i],dp[q.front()-1]+s[i]-s[q.front()-1]);
  61.         }
  62.     }
  63.     ll ds=dp[n];
  64.     if(ds==inf)ds=-1;
  65.     cout<<ds;
  66. }
  67.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UB0ZjR
language:
C++14 (gcc 8.3)
created:
16 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!