fork(1) download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <stack>
  7. #include <bitset>
  8. #include <algorithm>
  9. #include <functional>
  10. #include <numeric>
  11. #include <utility>
  12. #include <sstream>
  13. #include <iostream>
  14. #include <iomanip>
  15. #include <cstdio>
  16. #include <cmath>
  17. #include <cstdlib>
  18. #include <ctime>
  19. #include <climits>
  20. #include <memory.h>
  21. #include<cstring>
  22. using namespace std;
  23.  
  24. struct temp
  25. {
  26.    long long int l;
  27.    long long int r;
  28.    long long int c;
  29. }task[500005];
  30.  
  31. bool acompare(temp lhs, temp rhs)
  32. {
  33.     return lhs.c < rhs.c;
  34. }
  35.  
  36.  
  37. int main() {
  38. 	ios_base::sync_with_stdio(0);
  39. 	long long int t;
  40. 	cin >> t;
  41. 	while(t--)
  42.     {
  43.         long long int N,M,K;
  44.         cin >> N >> K >> M;
  45.         long long int arr[N+1];
  46.         long long int sum=0;
  47.         for(long long int i=1;i<=N;i++)
  48.             {
  49.                 cin >> arr[i];
  50.                 sum +=arr[i];
  51.             }
  52.          long long int dp[N+1][K+1];
  53.          memset(dp,0,sizeof(dp));
  54. //        cout << "hi" << endl;
  55.         for(long long int i=0;i<M;i++)
  56.         {
  57.             cin >> task[i].l >> task[i].r >> task[i].c;
  58.         }
  59.          sort(task,task+M,acompare);
  60. //           for(long long int i=0;i<M;i++)
  61. //        {
  62. //            cout << task[i].l << " " << task[i].r << " " << task[i].c << endl;
  63. //        }
  64.         long long int cost[N+1];
  65.  
  66.        for(long long int i=1;i<=N;i++)
  67.           cost[i]=1000;
  68.         for(long long int i=task[0].l;i<=task[0].r;i++)
  69.         {
  70.               cost[i]=task[0].c;
  71.         }
  72.         for(long long int i=1;i<M;i++)
  73.         {
  74.             for(long long int s=task[i].l;s<=task[i].r;s++)
  75.             {
  76.                 if(cost[s]==1000)
  77.                     cost[s]=task[i].c;
  78.                 else
  79.                     break;
  80.             }
  81.             for(long long int e=task[i].r;e>=task[i].l;e--)
  82.             {
  83.                 if(cost[e]==1000)
  84.                     cost[e]=task[i].c;
  85.                 else
  86.                     break;
  87.             }
  88.         }
  89. //        for(long long int i=1;i<=N;i++)
  90. //          cout << cost[i] << " ";
  91. //          cout << endl;
  92.         for(long long int i=1;i<=K;i++)
  93.         {
  94.             if(arr[1]<0)
  95.             {
  96.                 if(i>=cost[1])
  97.                     dp[1][i]=arr[1];
  98.                 else
  99.                     dp[1][i]=0;
  100.             }
  101.         }
  102.         for(long long int i=2;i<=N;i++)
  103.         {
  104.            for(long long int j=1;j<=K;j++)
  105.         {
  106.              if(j>=cost[i])
  107.              {
  108.                  dp[i][j]=min(dp[i-1][j],arr[i]+dp[i-1][j-cost[i]]);
  109.              }
  110.              else
  111.              {
  112.                  dp[i][j]=dp[i-1][j];
  113.              }
  114.         }
  115.         }
  116.         long long int ans = sum-dp[N][K];
  117.         cout << ans <<endl;
  118.     }
  119. }
  120.  
Success #stdin #stdout 0s 14960KB
comments (?)
stdin
copy 
1
4 10 4
-804289383 -846930886 -681692777 4 
1 1 50
2 2 30
3 4 20
1 4 10
stdout
copy 
-1485982156
https://ideone.com/0Ebhl2
language:
C++ (gcc 8.3)
created:
8 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!