Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 894 byte
#include <stdio.h>
#include <string.h>
int cache[10000];
int choice[10000];
int e[10000];
int s[10000];
int n;
int k;
int best(int index)
{
int min = -1, ido, max = 0, i, b;
for (i = index, b = s[i]; b <= k && i < n; i++, b += s[i]) {
if (max < e[i])
max = e[i];
ido = max + cache[i + 1];
if (ido < min || min == -1) {
min = ido;
choice[index] = i;
}
}
cache[index] = min;
return min;
}
int main(int argc, char **argv)
{
int i;
memset(cache, 0, 10000 * sizeof(int));
if (scanf("%d %d", &n, &k) != 2) {
printf("Keves parameter\n");
return 1;
}
for (i = 0; i < n; i++)
if (scanf("%d %d", &s[i], &e[i]) != 2) {
printf("Keves paramter\n");
return 1;
}
for (i = n - 1; i > 0; i--)
best(i);
printf("%d\n", best(0));
i = 0;
while (i < n && choice[i] < n) {
printf("%d %d\n", i + 1, choice[i] + 1);
i = choice[i] + 1;
}
return 0;
}
