Algorithm

D. Ilya and Roads
time limit per test
3 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/313/problem/D
input
standard input
output
standard output

Everything is great about Ilya's city, except the roads. The thing is, the only ZooVille road is represented as n holes in a row. We will consider the holes numbered from 1 to n, from left to right.

Ilya is really keep on helping his city. So, he wants to fix at least k holes (perharps he can fix more) on a single ZooVille road.

The city has m building companies, the i-th company needs ci money units to fix a road segment containing holes with numbers of at least li and at most ri. The companies in ZooVille are very greedy, so, if they fix a segment containing some already fixed holes, they do not decrease the price for fixing the segment.

Determine the minimum money Ilya will need to fix at least k holes.

Input

The first line contains three integers n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). The next m lines contain the companies' description. The i-th line contains three integers li, ri, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109).

Output

Print a single integer — the minimum money Ilya needs to fix at least k holes.

If it is impossible to fix at least k holes, print -1.

Please, do not use the %lld specifier to read or write 64-bit integers in ะก++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples
input
Copy
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6
output
Copy
17
input
Copy
10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13
output
Copy
2
input
Copy
10 1 9
5 10 14
output
Copy
-1



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 3e2 + 1;
long long oo = 1e16;
int n, m, k;
long long cost[N][N], dp[N][N];

long long rec(int idx, int rem) {
  if(rem <= 0)
    return 0;

  if(idx > n)
    return oo;

  long long &ret = dp[idx][rem];
  if(ret != -1)
    return ret;
  ret = oo;

  ret = min(ret, rec(idx + 1, rem));
  for(int i = idx; i <= n; ++i)
    ret = min(ret, rec(i + 1, rem - (i - idx + 1)) + cost[idx][i]);

  return ret;
}

int main() {
  scanf("%d %d %d", &n, &m, &k);

  for(int i = 0; i <= n; ++i)
    for(int j = 0; j <= n; ++j)
      cost[i][j] = oo;

  for(int i = 0, l, r, c; i < m; ++i) {
    scanf("%d %d %d", &l, &r, &c);
    for(int j = l; j <= r; ++j)
      cost[l][j] = min(cost[l][j], 1ll * c);
  }

  memset(dp, -1, sizeof dp);
  if(rec(1, k) < oo)
    printf("%lld\n", rec(1, k));
  else
    puts("-1");

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6

Output

x
–
+
cmd
17
Advertisements

Demonstration

Codeforces Solution-Ilya and Roads-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+