fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. const int base=31;
  9. int Test=1;
  10. void home()
  11. {
  12.     if(fopen("main.inp","r")) 
  13.     freopen("main.inp","r",stdin),
  14.     freopen("main.out","w",stdout);
  15. }
  16. int n,m,a[50005];
  17. int dp[50005][300];
  18. int mu[10];
  19. string chuyen(int n)
  20. {
  21.     string s="";
  22.     for(;n;n/=3)
  23.     {
  24.         s=char(n%3+'0')+s;
  25.     }
  26.     return s;
  27. }
  28. int bit(int mask,int i)
  29. {
  30.     while(i--)
  31.         mask/=3;
  32.     return mask%3;
  33. }
  34. int OR(int mask,int i,int type)
  35. {
  36.     return mask+mu[i]*(type-bit(mask,i));
  37. }
  38. int l[10],r[10];
  39. int Nmask=1;
  40. void Tcmduc_VOI26()
  41. {
  42.     cin>>n>>m;mu[0]=1;
  43.     for(int i=1;i<=5;i++)mu[i]=mu[i-1]*3;
  44.     for(int i=1;i<=n;i++)cin>>a[i];
  45.     for(int i=1;i<=m;i++)cin>>l[i]>>r[i];
  46.     Nmask=mu[m];
  47.     for(int i=0;i<=n;i++)for(int j=0;j<Nmask;j++)dp[i][j]=oo;
  48.     dp[0][0]=0;
  49.     for(int i=0;i<n;i++)
  50.     {
  51.         for(int mask=0;mask<Nmask;mask++)
  52.         {
  53.             if(dp[i][mask]==oo)continue;
  54.             int pos1=0;int nmask=mask;
  55.             for(int j=1;j<=m;j++)
  56.             {
  57.                 if(r[j]==i)nmask=OR(nmask,j-1,2);
  58.                 if(bit(nmask,j-1)==1)pos1=j;
  59.             }
  60.             if(pos1)dp[i+1][nmask]=min(dp[i+1][nmask],dp[i][mask]+a[i+1]*(pos1-1));
  61.             else dp[i+1][nmask]=min(dp[i+1][nmask],dp[i][mask]+a[i+1]*m);
  62.             for(int j=1;j<=m;j++)
  63.             {
  64.                 if(bit(nmask,j-1)==2)continue;
  65.                 if(bit(nmask,j-1)==1)
  66.                 {
  67.                     dp[i+1][OR(nmask,j-1,2)]=min(dp[i+1][OR(nmask,j-1,2)],dp[i][mask]+a[i+1]*m);
  68.                 }
  69.                 if(bit(nmask,j-1)==0)
  70.                 {
  71.                     if(l[j]<=i+1&&r[j]>=i+1)
  72.                     {
  73.                         int nnmask=nmask;
  74.                         if(pos1)nnmask=OR(nmask,pos1-1,2);
  75.                         dp[i+1][OR(nnmask,j-1,1)]=min(dp[i+1][OR(nnmask,j-1,1)],dp[i][mask]+a[i+1]*(j-1));
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.     }
  81.     int ans=oo;
  82.     for(int i=0;i<Nmask;i++)ans=min(ans,dp[n][i]);
  83.     cout<<ans<<' ';
  84. }
  85. signed main()
  86. {
  87.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  88.     while(Test--)Tcmduc_VOI26();
  89.     return 0;
  90. }
  91.  
  92.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sCgJRG
language:
C++14 (gcc 8.3)
created:
8 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!