fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int         long long int
  4. #define rep(i,a,b)  for(int i=a; i<b; i++)
  5.  
  6. const int N = 2e5+5;
  7. int a[N], n, m, k, sum[N];
  8. pair<int,int>offer[N];
  9. int dp[2005];
  10.  
  11. signed main()
  12. {
  13.        ios_base::sync_with_stdio(false);
  14.        cin.tie(0);
  15.        cout.tie(0);
  16.        cin>>n>>m>>k;
  17.        rep(i,1,n+1) cin>>a[i];
  18.        sort(a+1,a+1+n);
  19.        rep(i,1,k+1)
  20.        {
  21.               sum[i] = sum[i-1] + a[i];
  22.        }
  23.        rep(i,0,m)
  24.        {
  25.               int x,y;
  26.               cin>>x>>y;
  27.               offer[i+1]={x,y};
  28.        }
  29.        sort(offer+1, offer+1+m);
  30.        rep(i, 0, k+1) dp[i]=sum[i];
  31.        for(int j=1; j<=m; j++)
  32.        {
  33.               for(int i=0; i<=k; i++)
  34.               {
  35.                      if(offer[j].first>i) continue;
  36.                      dp[i] = min(dp[i], sum[i] - sum[i-offer[j].first+offer[j].second] + dp[i-offer[j].first]);
  37.               }
  38.        }
  39.        cout<<dp[k];
  40. }
  41.  
Success #stdin #stdout 0s 21504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dxPbeg
language:
C++14 (gcc 8.3)
created:
5 years 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!