Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include<conio.h>
- #include <algorithm>
- #include <stack>
- #include <stdio.h>
- #include <iostream>
- #include <fstream>
- using namespace std;
- class WeightedInterval {
- public:
- int start, finish, weight;
- bool operator < (const WeightedInterval& x) const {
- if (finish != x.finish)
- return finish < x.finish;
- }
- } *intervals;
- int binary_search(int lo, int hi, int val) {
- int mid;
- while (lo < hi) {
- mid = lo + (hi - lo + 1) / 2;
- if (intervals[mid].finish <= val)
- lo = mid;
- else
- hi = mid - 1;
- }
- if (intervals[lo].finish > val)
- return 0;
- return lo;
- }
- int greatestNonOverlappingInterval(int i) {
- return binary_search(0, i-1, intervals[i].start);
- }
- int main() {
- int N, i = 1, *dp, *p;
- int start, fin, weight;
- fstream myfile("plik.txt", ios_base::in);
- myfile >> N;
- intervals = new WeightedInterval[N + 1];
- while(i <= N)
- {
- myfile >> start;
- myfile >> fin;
- weight = abs(start-fin);
- intervals[i].start = start;
- intervals[i].finish = fin;
- intervals[i].weight = weight;
- i++;
- }
- sort(intervals + 1, intervals + N + 1);
- dp = new int[N + 1];
- p = new int[N + 1];
- dp[0] = p[0] = 0;
- for (i = 1; i <= N; i++)
- {
- p[i] = greatestNonOverlappingInterval(i);
- dp[i] = max(intervals[i].weight + dp[p[i]], dp[i-1]);
- }
- printf("%d\n", dp[N]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement