Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.80 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. #include <math.h>
  4.  
  5. #include <stdlib.h>
  6.  
  7.  
  8.  
  9. int mp = 0;
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17. void swap(int *a, int *b)
  18.  
  19. {
  20.  
  21. int t = *a;
  22.  
  23. *a = *b;
  24.  
  25. *b = t;
  26.  
  27. }
  28.  
  29.  
  30.  
  31.  
  32.  
  33. int min(int a, int b)
  34.  
  35. {
  36.  
  37. if (a < b)
  38.  
  39. return a;
  40.  
  41. return b;
  42.  
  43. }
  44.  
  45.  
  46.  
  47. int max(int a, int b)
  48.  
  49. {
  50.  
  51. if (a > b)
  52.  
  53. return a;
  54.  
  55. return b;
  56.  
  57. }
  58.  
  59.  
  60.  
  61. int partition(int arr[][3], int low, int high)
  62.  
  63. {
  64.  
  65. int pivot = arr[high][0]; // pivot
  66.  
  67.  
  68.  
  69. int i = (low - 1); // Index of smaller element
  70.  
  71.  
  72.  
  73. for (int j = low; j <= high - 1; j++)
  74.  
  75. {
  76.  
  77. // If current element is smaller than or
  78.  
  79.  
  80.  
  81. // equal to pivot
  82.  
  83.  
  84.  
  85. if (arr[j][0] <= pivot)
  86.  
  87.  
  88.  
  89. {
  90.  
  91.  
  92.  
  93. i++; // increment index of smaller element
  94.  
  95.  
  96.  
  97.  
  98.  
  99. swap(&arr[i][0], &arr[j][0]);
  100.  
  101. swap(&arr[i][1], &arr[j][1]);
  102.  
  103. swap(&arr[i][2], &arr[j][2]);
  104.  
  105. }
  106.  
  107. }
  108.  
  109.  
  110.  
  111. swap(&arr[i + 1][0], &arr[high][0]);
  112.  
  113. swap(&arr[i + 1][1], &arr[high][1]);
  114.  
  115. swap(&arr[i + 1][2], &arr[high][2]);
  116.  
  117. return (i + 1);
  118.  
  119. }
  120.  
  121.  
  122.  
  123. /* The main function that implements QuickSort
  124.  
  125.  
  126.  
  127. arr[] --> Array to be sorted,
  128.  
  129.  
  130.  
  131. low --> Starting index,
  132.  
  133.  
  134.  
  135. high --> Ending index */
  136.  
  137.  
  138.  
  139. void quickSort(int arr[][3], int low, int high)
  140.  
  141.  
  142.  
  143. {
  144.  
  145.  
  146.  
  147. if (low < high)
  148.  
  149.  
  150.  
  151. {
  152.  
  153.  
  154.  
  155. /* pi is partitioning index, arr[p] is now
  156.  
  157.  
  158.  
  159. at right place */
  160.  
  161.  
  162.  
  163. int pi = partition(arr, low, high);
  164.  
  165.  
  166.  
  167. // Separately sort elements before
  168.  
  169.  
  170.  
  171. // partition and after partition
  172.  
  173.  
  174.  
  175. quickSort(arr, low, pi - 1);
  176.  
  177.  
  178.  
  179. quickSort(arr, pi + 1, high);
  180.  
  181. }
  182.  
  183. }
  184.  
  185.  
  186.  
  187. int algo(int n_events, int events[][3], int max_dealine)
  188.  
  189.  
  190.  
  191. {
  192.  
  193.  
  194.  
  195. int i, j, taux;
  196.  
  197. int aux[n_events+1][max_dealine+1];
  198.  
  199.  
  200.  
  201. //printf("%d\n", max_dealine);
  202.  
  203.  
  204.  
  205. for (j = 0; j <= n_events; j++)
  206.  
  207. {
  208.  
  209. aux[j][0] = 0;
  210.  
  211. //printf("%d ",aux[j][0] );
  212.  
  213. }
  214.  
  215.  
  216.  
  217. for (i = 1; i <= max_dealine; i++)
  218.  
  219.  
  220.  
  221. {
  222.  
  223. aux[0][i] = 0;
  224.  
  225. //printf("%d",aux[0][i] );
  226.  
  227. }
  228.  
  229.  
  230.  
  231. for (i = 1; i <= n_events; i++)
  232.  
  233. {
  234.  
  235. for (j = 1; j <= max_dealine; j++)
  236.  
  237. {
  238.  
  239. taux = min(j, events[i-1][0]) - events[i-1][1];
  240.  
  241. if (taux < 0)
  242.  
  243. {
  244.  
  245. aux[i][j] = aux[i - 1][j];
  246.  
  247. }
  248.  
  249.  
  250.  
  251. else
  252.  
  253. {
  254.  
  255. aux[i][j] = max(aux[i - 1][j], events[i-1][2] + aux[i - 1][taux]);
  256.  
  257. //printf("%d ", aux[i][j]);
  258.  
  259. }
  260.  
  261.  
  262.  
  263. }
  264.  
  265. //printf("\n");
  266.  
  267. }
  268.  
  269.  
  270.  
  271. return aux[n_events][max_dealine];
  272.  
  273. }
  274.  
  275.  
  276.  
  277. int main(int argc, char const *argv[])
  278.  
  279. {
  280.  
  281.  
  282.  
  283. int i, n_events, maxi;
  284.  
  285.  
  286.  
  287.  
  288.  
  289. scanf("%d", &n_events);
  290.  
  291. int events[n_events][3];
  292.  
  293.  
  294.  
  295. for (i = 0; i < n_events; i++)
  296.  
  297.  
  298.  
  299. scanf("%d %d %d", &events[i][0], &events[i][1], &events[i][2]);
  300.  
  301.  
  302.  
  303. quickSort(events, 0, n_events - 1);
  304.  
  305.  
  306.  
  307. //printf("QUICK SORT\n");
  308.  
  309. //for (int i=0;i<n_events;i++){
  310.  
  311. //printf("%d %d %d\n",events[i][0],events[i][1],events[i][2]);
  312.  
  313. //}
  314.  
  315.  
  316.  
  317. int max_dealine = events[n_events - 1][0];
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325. //printf("saddsadsa\n");
  326.  
  327.  
  328.  
  329. maxi = algo(n_events, events, max_dealine);
  330.  
  331. printf("%d\n",maxi);
  332.  
  333. /*
  334.  
  335.  
  336.  
  337. int used[n_events];
  338.  
  339.  
  340.  
  341. for (i = 0; i < n_events; i++)
  342.  
  343.  
  344.  
  345. used[i] = 0;
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353. for (i = 0; i < n_events; i++)
  354.  
  355.  
  356.  
  357. if (events[i][0] > bd)
  358.  
  359.  
  360.  
  361. bd = events[i][0];
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369. max_profit(events, used, n_events, bd, 0, 0);
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377. printf("%d\n", mp);
  378.  
  379.  
  380.  
  381. */
  382.  
  383.  
  384.  
  385.  
  386.  
  387. return 0;
  388.  
  389. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement