fork download
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. int* initdkntor(int n, int * brokens, int m)
  7. {
  8. int * p = (int *)malloc(sizeof(int) * n);
  9. memset(p, 0, sizeof(int) * n);
  10. for (int i = 0; i < m; i++)
  11. {
  12. for (int j = brokens[i * 2] - 1; j < brokens[i * 2 + 1]; j++)
  13. p[j] = 1;
  14. }
  15. return p;
  16. }
  17.  
  18. int* tryit(int *seed, int n, int a, int b)
  19. {
  20. int * p = (int *)malloc(sizeof(int) * n);
  21. memcpy(p, seed, sizeof(int) * n);
  22. for (int i = a - 1; i < b; i++) p[i] = 0;
  23. return p;
  24. }
  25.  
  26. int check(int *p, int n)
  27. {
  28. for (int i = 0; i < n; i++) if (p[i]) return 1;
  29. return 0;
  30. }
  31.  
  32. int solve(int *seed, int seedcost, int n, int *sp, int spn)
  33. {
  34. if (!check(seed, n)) return seedcost;
  35. if (!spn) return -1;
  36. int min = -1;
  37. for (int i = 0; i < spn; i++)
  38. {
  39. int * seed1 = tryit(seed, n, sp[i*3], sp[i*3+1]);
  40. int cost = solve(seed1, seedcost + sp[i*3+2], n, sp + 3 * (i+1), spn - i-1);
  41. if (cost != -1)
  42. if (cost < min || min == -1) min = cost;
  43. }
  44. return min;
  45. }
  46.  
  47. int main()
  48. {
  49. int s;
  50. int n;
  51. int m;
  52. cin >> n >> m >> s;
  53. int * bk = new int[n * 2];
  54. for (int i = 0; i < n; i++)
  55. cin >> bk[i*2] >> bk[i*2+1];
  56. int * sp = new int[m * 3];
  57. for (int i = 0; i < m; i++)
  58. cin >> sp[i*3] >> sp[i*3+1] >> sp[i*3+2];
  59. int * dkntor = initdkntor(s, bk, n);
  60. int result = solve(dkntor, 0, s, sp, m);
  61. cout << result << endl;
  62. return 0;
  63. }
Success #stdin #stdout 0s 4352KB
stdin
1 3 15
5 10
3 7 2
6 12 5
2 11 6
stdout
6