Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <math.h>
- #include <stdlib.h>
- int mp = 0;
- void swap(int *a, int *b)
- {
- int t = *a;
- *a = *b;
- *b = t;
- }
- int min(int a, int b)
- {
- if (a < b)
- return a;
- return b;
- }
- int max(int a, int b)
- {
- if (a > b)
- return a;
- return b;
- }
- int partition(int arr[][3], int low, int high)
- {
- int pivot = arr[high][0]; // pivot
- int i = (low - 1); // Index of smaller element
- for (int j = low; j <= high - 1; j++)
- {
- // If current element is smaller than or
- // equal to pivot
- if (arr[j][0] <= pivot)
- {
- i++; // increment index of smaller element
- swap(&arr[i][0], &arr[j][0]);
- swap(&arr[i][1], &arr[j][1]);
- swap(&arr[i][2], &arr[j][2]);
- }
- }
- swap(&arr[i + 1][0], &arr[high][0]);
- swap(&arr[i + 1][1], &arr[high][1]);
- swap(&arr[i + 1][2], &arr[high][2]);
- return (i + 1);
- }
- /* The main function that implements QuickSort
- arr[] --> Array to be sorted,
- low --> Starting index,
- high --> Ending index */
- void quickSort(int arr[][3], int low, int high)
- {
- if (low < high)
- {
- /* pi is partitioning index, arr[p] is now
- at right place */
- int pi = partition(arr, low, high);
- // Separately sort elements before
- // partition and after partition
- quickSort(arr, low, pi - 1);
- quickSort(arr, pi + 1, high);
- }
- }
- int algo(int n_events, int events[][3], int max_dealine)
- {
- int i, j, taux;
- int aux[n_events+1][max_dealine+1];
- //printf("%d\n", max_dealine);
- for (j = 0; j <= n_events; j++)
- {
- aux[j][0] = 0;
- //printf("%d ",aux[j][0] );
- }
- for (i = 1; i <= max_dealine; i++)
- {
- aux[0][i] = 0;
- //printf("%d",aux[0][i] );
- }
- for (i = 1; i <= n_events; i++)
- {
- for (j = 1; j <= max_dealine; j++)
- {
- taux = min(j, events[i-1][0]) - events[i-1][1];
- if (taux < 0)
- {
- aux[i][j] = aux[i - 1][j];
- }
- else
- {
- aux[i][j] = max(aux[i - 1][j], events[i-1][2] + aux[i - 1][taux]);
- //printf("%d ", aux[i][j]);
- }
- }
- //printf("\n");
- }
- return aux[n_events][max_dealine];
- }
- int main(int argc, char const *argv[])
- {
- int i, n_events, maxi;
- scanf("%d", &n_events);
- int events[n_events][3];
- for (i = 0; i < n_events; i++)
- scanf("%d %d %d", &events[i][0], &events[i][1], &events[i][2]);
- quickSort(events, 0, n_events - 1);
- //printf("QUICK SORT\n");
- //for (int i=0;i<n_events;i++){
- //printf("%d %d %d\n",events[i][0],events[i][1],events[i][2]);
- //}
- int max_dealine = events[n_events - 1][0];
- //printf("saddsadsa\n");
- maxi = algo(n_events, events, max_dealine);
- printf("%d\n",maxi);
- /*
- int used[n_events];
- for (i = 0; i < n_events; i++)
- used[i] = 0;
- for (i = 0; i < n_events; i++)
- if (events[i][0] > bd)
- bd = events[i][0];
- max_profit(events, used, n_events, bd, 0, 0);
- printf("%d\n", mp);
- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement