fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3. #define INF 800000000000
  4. #define MOD 100000007
  5. #define MAXN 100005
  6. #define ins insert
  7. #define pb push_back
  8. #define mp make_pair
  9. #define sz size
  10. #define all(a) a.begin(), a.end()
  11. #define rep(i, a, b) for(int i = a; i < b; ++i)
  12. #define sd(n) scanf("%d",&n)
  13. #define sll(n) scanf("%I64d",&n)
  14. #define pdn(n) printf("%d\n",n)
  15. #define plln(n) printf("%I64d\n",n)
  16. #define pd(n) printf("%d ",n)
  17. #define nl() printf("\n")
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef vector<int> vi;
  23. typedef vector<ll> vl;
  24. typedef vector<vi> vvi;
  25. typedef vector<vl> vvl;
  26. typedef pair<int, int> pii;
  27.  
  28. namespace patch
  29. {
  30.     template < typename T > std::string to_string( const T& n )
  31.     { 
  32.         std::ostringstream stm ;
  33.         stm << n ;
  34.         stm.str() ;
  35.     }
  36. }
  37.  
  38. ll modpow(ll base, ll exponent, int modulus)
  39. {
  40.     ll result = 1;
  41.     while (exponent > 0)
  42.     {
  43.         if (exponent % 2 == 1)
  44.             result = (result * base) % modulus;
  45.         exponent = exponent >> 1;
  46.         base = (base * base) % modulus;
  47.     }
  48.     return result;
  49. }
  50.  
  51. ll gcd(ll u, ll v)
  52. {
  53.     return (v != 0) ? gcd(v, u % v) : u;
  54. }
  55.  
  56. int t, n, k, m, score[10001];
  57. vvi ad(10001), del(10001);
  58. multiset<int> mm;
  59. ll mincost[10001], dp[10001][501];
  60.  
  61. /*ll solve(int idx, int rem) {
  62.     if(rem < 0)
  63.         return -50000000LL;
  64.     if(idx == 0)
  65.         return 0;
  66.     if(dp[idx][rem] != 800000000LL)
  67.         return dp[idx][rem];
  68.     return dp[idx][rem] = max(solve(idx-1, rem-mincost[idx]), solve(idx-1, rem)+(ll)score[idx]);
  69. }*/
  70.  
  71. int main() {
  72.     //ios_base::sync_with_stdio(0);
  73.     //cin.tie(0);
  74.     //cout.tie(0);
  75.     sd(t);
  76.     while(t--) {
  77.         mm.clear();
  78.         rep(i, 0, 10001) {
  79.             rep(j, 0, 501)
  80.                 dp[i][j] = 0;
  81.             ad[i].clear();
  82.             del[i].clear();    
  83.         }
  84.         sd(n); sd(k); sd(m);
  85.         rep(i, 1, n+1)
  86.             scanf("%d", &score[i]);
  87.         rep(i, 0, m) {
  88.             int l, r, c;
  89.             sd(l); sd(r); sd(c);
  90.             ad[l].pb(c);
  91.             del[r].pb(c);
  92.         }
  93.         mm.ins(k+5);
  94.         rep(i, 1, n+1) {
  95.             rep(j, 0, ad[i].sz()) {
  96.                 mm.ins(ad[i][j]);
  97.             }
  98.             mincost[i] = *mm.begin();
  99.             rep(j, 0, del[i].sz()) {
  100.                 mm.erase(mm.find(del[i][j]));
  101.             }
  102.         }
  103.         //rep(i, 1, n+1)
  104.         //    cout << mincost[i] << endl;
  105.         dp[0][0] = 0LL;
  106.         rep(i, 1, n+1)
  107.             dp[i][0] = dp[i-1][0] + (ll)score[i];
  108.         rep(i, 1, n+1) {
  109.             rep(j, 1, k+1) {
  110.                 if(j >= mincost[i])
  111.                     dp[i][j] = max(dp[i-1][j]+(ll)score[i], dp[i-1][j-mincost[i]]);
  112.                 else
  113.                     dp[i][j] = dp[i-1][j]+(ll)score[i];
  114.             }
  115.         }      
  116.         printf("%lld\n", dp[n][k]);  
  117.     }
  118.     return 0;
  119. }
Success #stdin #stdout 0.02s 42680KB
comments (?)
stdin
copy 
1
5 10 1
-1 -2 -3 -4 -5
1 1 4
stdout
copy 
-14
https://ideone.com/EJBqIN
language:
C++ (gcc 8.3)
created:
9 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!