fork download
copy 
  1. //****** @mdazmat9 **********
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. #define UB upper_bound
  6. #define LB lower_bound
  7. #define BS binary_search
  8. #define EB emplace_back
  9. #define PB push_back
  10. #define endl "\n"
  11. #define MOD 1000000007
  12. #define MOD2 998244353
  13. #define F first
  14. #define S second
  15. #define ALL(a) (a).begin(),(a).end()
  16. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  17. int fast_pow(int x, int y, int p);
  18. map<int,vector<pair<int,int>>> save;
  19. class Node{
  20. public:
  21.     int a,b,profit;
  22. };
  23. Node node[5001];
  24. int dp[5001][5001];
  25. int n;
  26. int rec(int pos,int k){
  27.     if(pos==n){
  28.         return 0;
  29.     }
  30.  
  31.     int& ans=dp[pos][k]; // refernce created
  32.     if(ans!=-1)return ans;
  33.     ans=INT_MIN;
  34.     if(k>=node[pos].a){
  35.         k+=node[pos].b;
  36.         ans=max(ans,rec(pos+1,k));
  37.         int cnt=1;
  38.         int temp=0;
  39.         for(auto x:save[pos]){
  40.             if(k-cnt>=0){
  41.                 temp+=x.F;
  42.                 ans=max(ans,temp+rec(pos+1,k-cnt));
  43.                 cnt++;
  44.             }
  45.         }
  46.     }
  47.     return ans;
  48. }
  49.  
  50. void solve() {
  51.     int m,k;cin>>n>>m>>k;
  52.     for(int i=0;i<n;i++){
  53.         cin>>node[i].a>>node[i].b>>node[i].profit;
  54.     }
  55.     map<int,int> mp;
  56.     for(int i=0;i<m;i++){
  57.         int u,v;cin>>u>>v;
  58.         u--;v--;
  59.         mp[v]=max(mp[v],u);
  60.     }
  61.     for(int i=0;i<n;i++){
  62.         mp[i]=max(i,mp[i]);
  63.     }
  64.     for(auto x:mp){
  65.         save[x.S].EB(node[x.F].profit,x.F);
  66.     }
  67.  
  68.     for(auto& x:save){
  69.         sort(ALL(x.S),greater<pair<int,int>>());
  70.     }
  71.     memset(dp,-1, sizeof(dp));
  72.     cout<<max(-1ll,rec(0,k))<<endl;
  73.  
  74. }
  75. int32_t main() {
  76.     IOS;
  77.     int test = 1;
  78. //    cin >> test;
  79.     for(int i=1;i<=test;i++){
  80.         solve();
  81.     }
  82.     return 0;
  83. }
  84. int fast_pow(int x, int y, int p) {
  85.     int res = 1;
  86.     x = x % p;
  87.     while (y > 0) {
  88.         if (y & 1)
  89.             res = (res * x) % p;
  90.         y = y >> 1;
  91.         x = (x * x) % p;
  92.     }
  93.     return res;
  94. }
Success #stdin #stdout 0.05s 198972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ubpfJ5
language:
C++14 (gcc 8.3)
created:
4 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!