fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long dp[100005][505]; 
  5.  
  6. int main() {
  7.     int t;
  8.     scanf("%d",&t);
  9.     while(t--){
  10.             // ho jaa bhai jaldiii ho jaaa ...
  11.             long  i,j,n,m,k;
  12.             scanf("%ld%ld%ld",&n,&m,&k);
  13.             int arr[100100];
  14.             int  cost[100100];
  15.             long long tot=0;
  16.             for(i=0;i<n;i++){
  17.                     scanf("%d",&arr[i]);
  18.                         cost[i]=INT_MAX;
  19.                         tot+=arr[i];
  20.             }
  21.  
  22.             vector<pair<int  , pair< int,  int> > >ks;
  23.             for(i=0;i<k;i++){
  24.                     long l,r,c;
  25.                     scanf("%ld%ld%ld",&l,&r,&c);
  26.                     ks.push_back(make_pair(c,make_pair(l-1,r-1)));
  27.                     //for(j=l-1;j<r;j++){
  28.                      //   if(cost[j]==0 || cost[j]>c)cost[j]=c;
  29.                     //}
  30.             }
  31.             for(i=0;i<k;i++){
  32.                 for(j=ks[i].second.first; j<=ks[i].second.second;j++)
  33.                     cost[j]=min(cost[j], ks[i].first);
  34.             }
  35.     // cost ki list bana k knapsack lagaoo
  36.     memset(dp,0,sizeof(dp));
  37. 	for(i=1;i<=n;i++)dp[i][0]=dp[i-1][0]+arr[i];
  38. 	for(i=1;i<=n;i++){
  39. 		//dp[i][0]=dp[i-1][0]+arr[i-1];
  40. 		for(j=1;j<=k;j++){
  41. 			//if(i==0||j==0){dp[i][j]=0;continue;}
  42. 			if(cost[i-1]<=j)
  43. 				dp[i][j]=max(dp[i-1][j-cost[i-1]],dp[i-1][j]+arr[i-1]);
  44. 			else dp[i][j]=dp[i-1][j]+arr[i-1];
  45. 					//dp[i][j]=max(dp[i-1][j]+arr[i-1],dp[i-1][j-cost[i-1]]);
  46. 					//cout<<dp[i][j]<<" ";
  47. 					//getchar();
  48. 			}
  49. 				//cout<<"\n";
  50. 		}
  51. 	for(i=0;i<=n;i++){
  52. 	for(j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
  53. 			//cout<<dp[n-1][k-1]<<" "<<tot<<"\n";
  54. 		cout<<tot+dp[n][k]<<"\n";
  55.     }
  56. return 0;
  57. }
  58.  
  59.  
  60.  
  61.  
Success #stdin #stdout 0s 201088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gSQBY7
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!