fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <set>
  5. #include <deque>
  6. #include <algorithm>
  7. #include <queue>
  8. #include <cmath>
  9. #include <map>
  10. #include <complex>
  11. #include <cstring>
  12. #include <cfloat>
  13. #include <iomanip>
  14. #include <stack>
  15. #include <bitset>
  16.  
  17.  
  18. using namespace std;
  19. #define rep(i, a, b) for(int i = (a); i < (b); i++)
  20. #define repd(i, a, b) for(int i = (a); i > (b); i--)
  21. #define forIt(it, a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
  22. #define forRev(it, a) for(__typeof((a).rbegin()) it = (a).rbegin(); it != (a).rend(); it++)
  23. #define ft(a) __typeof((a).begin())
  24. #define ll long long
  25. #define ld long double
  26. #define fi first
  27. #define se second
  28. #define mk make_pair
  29. #define pb push_back
  30. #define sz(a) (int)(a).size()
  31. #define all(a) (a).begin(), (a).end()
  32. #define Rep(i,n) for(int i = 0; i < (n); ++i)
  33. #define bitcount(n) __builtin_popcountll(n)
  34. #define pii pair<int, int>
  35.  
  36.  
  37. typedef complex<ld> cplex;
  38. typedef vector<int> vi;
  39. typedef pair<int, int> ii;
  40. typedef pair<ii, int> iii;
  41. typedef vector<ii> vii;
  42. typedef vector<iii> viii;
  43.  
  44. const int N = 1000000 + 8;
  45. const int M = 1500 + 7;
  46. const int inf = 1e9 + 7;
  47. const long long linf = 1ll * inf * (inf - 1);
  48. const double pi = acos(-1);
  49. const double eps = 1e-6;
  50. const bool multipleTest = true;
  51.  
  52.  
  53. ll L[N];
  54. int a[N], b[N], cost[N];
  55. int id[N];
  56.  
  57. bool cmp(int u, int v) {
  58.     if (cost[u] != cost[v]) return cost[u] < cost[v];
  59.     return mk(a[u], b[u]) < mk(a[v], b[v]);
  60. }
  61.  
  62. int n, m, D;
  63.  
  64. ll q[N]; int top, bot;
  65.  
  66. void solve() {
  67.     cin >> n >> m >> D;
  68.     for(int i = 0; i < n; ++i) {
  69.         scanf("%d%d%d", a + i, b + i, cost + i);
  70.         id[i] = i;
  71.     }
  72.     sort(id, id + n, cmp);
  73.  
  74.     L[0] = 0;
  75.     for(int i = 1; i <= D; ++i) L[i] = linf;
  76.  
  77.     top = 0, bot = 0;
  78.  
  79.     for(int i = 0; i < n; ++i) {
  80.         int u = id[i];
  81.  
  82.         top = bot = 0;
  83.         int last = D;
  84.  
  85.         for(int j = D; j >= a[u]; --j) {
  86.             while (top < bot && q[top] > j - a[u]) ++top;
  87.             last = min(last, j - a[u]);
  88.             while (last >= max(0, j - b[u])) {
  89.                 while (top < bot && L[q[bot - 1]] >= L[last]) bot--;
  90.                 q[bot++] = last--;
  91.             }
  92.             L[j] = min(L[j], L[q[top]] + cost[u]);
  93.         }
  94.     }
  95.  
  96. //    for(int j = 0; j <= D; ++j) {
  97. //        cout << L[j] << ' ';
  98. //    }
  99. //    puts("");
  100.  
  101.     if (L[D] <= m) printf("%lld\n", L[D]);
  102.     else puts("IMPOSSIBLE");
  103.  
  104. }
  105.  
  106.  
  107.  
  108. int main() {
  109. #ifndef ONLINE_JUDGE
  110.     freopen("in.txt", "r", stdin);
  111.     clock_t t1 = clock();
  112. #endif
  113.     //        createTest();
  114.     //        return 0;
  115.         freopen("out.txt", "w", stdout);
  116.  
  117.  
  118.  
  119.  
  120.     int Test = 1;
  121.     if (multipleTest) {
  122.         cin >> Test;
  123.     }
  124.  
  125.     for(int i = 0; i < Test; ++i) {
  126.                 printf("Case #%d: ", i + 1);
  127.         solve();
  128.     }
  129.     //
  130. #ifndef ONLINE_JUDGE
  131. //    cout<<"\n" << 1.0 * (clock() - t1) / CLOCKS_PER_SEC<<endl;
  132. #endif
  133.  
  134. }
Success #stdin #stdout 0s 34720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L4fSsM
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!