fork download
copy 
  1. //Author: NguyenBaoAnh
  2. //Problem: C
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define ii pair<int,int>
  7. #define vi vector<int>
  8. #define pb push_back
  9. #define all(s) s.begin(), s.end()
  10. #define fi first
  11. #define se second
  12. const int N=1e5, M=1e5, Ban=(1<<1)+(1<<8)+(1<<9);
  13. const ll Mod=1e9+7, oo=1e18;
  14. int n, m;
  15. ll P, C, a[N+5], s[N+5], dp[N+5][70];
  16. signed main()
  17. {
  18.     //Its cookin' time!!
  19.     freopen("WHOME.inp", "r", stdin); freopen("WHOME.out", "w", stdout);
  20.     ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
  21.     cin>>n>>m>>P>>C;
  22.     for(int i=1; i<=n; i++) cin>>a[i];
  23.     for(int i=0; i<m; i++) cin>>s[i];
  24.     sort(a+1, a+n+1);
  25.     for(int i=1; i<=n; i++)
  26.         for(int msk=0; msk<(1<<m); msk++) dp[i][msk]=-oo;
  27.     for(int i=1; i<=n; i++) {
  28.         for(int msk=0; msk<(1<<m); msk++) {
  29.             int S=0;
  30.             for(int j=0; j<m; j++)
  31.                 if((msk>>j)&1) S+=s[j];
  32.             if(S<=i) dp[i][msk]=max(dp[i][msk], dp[i-1][msk]);
  33.             for(int j=0; j<m; j++) {
  34.                 if(i<s[j]) continue;
  35.                 ll d=a[i]-a[i-s[j]+1];
  36.                 int SS, msk2=msk|(1<<j);
  37.                 if((msk>>j)&1) SS=S; else SS=S+s[j];
  38.                 if(SS<=i) dp[i][msk2]=max(dp[i][msk2], dp[i-s[j]][msk]+P-d*d*C);
  39.             }
  40.         }
  41.     }
  42.     cout<<dp[n][(1<<m)-1];
  43.     return 0;
  44. }
  45.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Hb2HHp
language:
C++14 (gcc 8.3)
created:
10 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!