fork download
copy 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16. #include <bitset>
  17.  
  18. #define MAX 610
  19. #define MOD 1000000007
  20. #define PI 3.1415926535897932384
  21. #define F first
  22. #define S second
  23. #define pb push_back
  24. #define mp make_pair
  25. typedef long long ll;
  26.  
  27. int n, k, p;
  28. int cost[MAX];
  29. int dp[MAX][MAX][3]; // DP[ current_gum ][ num_teeth ][ val /prev_col /cont_teeth_for_this_gum ]
  30. vector<pair<int, int> > gum[MAX];
  31. vector<int> res;
  32.  
  33. void solve(){
  34.  
  35.     // Initial state of DP
  36.     memset(dp, -1, sizeof(dp));
  37.     dp[0][0][0] = 0;
  38.  
  39.     for(int i = 1;i <= k;i++){
  40.         int acm = cost[i]; // Initial cost of anesthesia
  41.  
  42.         for(int l = -1;l < (int)gum[i].size();l++){
  43.             if(l != -1) acm += gum[i][l].F; // Cost of curing teeh[0, l] in gum[i]
  44.  
  45.             // Num holds the number of cured teeth
  46.             for(int num = 0;num <= n;num++){
  47.                 if(dp[i-1][num][0] == -1) continue;
  48.  
  49.                 if(l == -1){
  50.                     dp[i][num][0] = dp[i-1][num][0];
  51.                     dp[i][num][1] = num;
  52.                     dp[i][num][2] = 0;
  53.                     continue;
  54.                 }
  55.  
  56.                 if(dp[i][num+l+1][0] == -1 || dp[i][num+l+1][0] > dp[i-1][num][0]+acm){
  57.                     dp[i][num+l+1][0] = dp[i-1][num][0]+acm;
  58.                     dp[i][num+l+1][1] = num;
  59.                     dp[i][num+l+1][2] = l+1;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.  
  65.     int cur; // Cur is the number of cured teeth untill gum[i], initially i == k
  66.     for(int i = n;i >= 0;i--){
  67.         if(dp[k][i][0] != -1 && dp[k][i][0] <= p){ cur = i; break; }
  68.     }
  69.  
  70.  
  71.     for(int i = k;i > 0;i--){
  72.         for(int j = 0;j < dp[i][cur][2];j++) res.pb(gum[i][j].S); // Values on answer
  73.  
  74.         // Cur receives number of teeth cured untill gum[i-1]
  75.         cur = dp[i][cur][1];
  76.     }
  77.  
  78.     // Print answer
  79.     cout << res.size() << endl;
  80.     for(int i = 0;i < res.size();i++) cout << res[i] << " \n"[i == res.size()-1];
  81. }
  82.  
  83. int main(){
  84.     //freopen("in", "r", stdin);
  85.     //freopen("out", "w", stdout);
  86.  
  87.     // ______________Read input:
  88.     cin >> n >> k >> p;
  89.  
  90.     for(int i = 1;i <= k;i++) cin >> cost[i];
  91.  
  92.     for(int x, y, i = 1;i <= n;i++){
  93.         cin >> x >> y;
  94.         gum[y].pb(mp(x, i));
  95.     }
  96.     //_________________________
  97.  
  98.     // Sort values for each gum
  99.     for(int i = 1;i <= n;i++) sort(gum[i].begin(), gum[i].end());
  100.  
  101.     solve();
  102.  
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0s 7788KB
comments (?)
stdin
copy 
4 2 10
1 2
1 2
5 2
3 1
3 2
stdout
copy 
3
1 4 3
https://ideone.com/KJZ306
language:
C++14 (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!