|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Leto
|
Katarina obožava da putuje i već je počela da pravi planove za ovo leto. Napravila
je spisak sa n egzotičnih mesta koja bi volela da poseti. Za svako mesto poznato je koliko
dana bi ona tamo ostala, to su vrednosti ti, i pri tome za svako i ≠ j važi
ti ≠ tj.
Katarina ima p prijatelja sa kojima može da putuje. Međutim, ne žele svi prijate i da
idu na sva mesta, već postoji p parova brojeva bi i ei
(1 ≤ bi ≤ ei ≤ n).
Oni nam govore da i-ti prijatelj želi da ide samo na mesta sa rednim brojem j
takvim da važi bi ≤ j ≤ ei.
Potrebno je pronaći koliko najviše dana Katarina može da provede na putovanjima, ako
moraju da budu zadovoljeni sledeći uslovi:
- Katarina nigde ne može da putuje sama.
- Sa svakim prijateljem ona može da ide na najviše jedno mesto.
- Svako mesto ona može posetiti najviše jednom.
Ulaz:
(Ulazni podaci se učitavaju iz datoteke leto.in.)
U prvom redu ulazne datoteke
se nalazi broj n (n ≤ 5.000), broj mesta. U sledećem redu nalazi se n brojeva razdvojenih
razmacima, to su vrednosti ti (1 ≤ ti ≤ 100.000).
Sledi red u kome se nalazi broj p
(p ≤ 5.000), broj prijatelja. U svakom od narednih p redova nalaze se po dva broja,
bi i ei.
Izlaz:
(Izlazni podaci se ispisuju u datoteku leto.out.) U izlaznu datoteku treba upisati
samo jedan broj, koliko najviše dana mogu trajati sva Katarinina putovanja zajedno.
Primer:
leto.in
|
|
leto.out
|
8
2 3 1 4 6 5 20 9
5
5 6
2 5
1 2
8 8
8 8
|
|
23
|
Objašnjenje.
Postoji 8 mesta, na prvom se ostaje 2 dana, na drugom 3 dana, itd. Katarina
ima 5 prijatelja. Prvi prijatelj želi da ide na mesto 5 ili 6, drugi na neko od mesta 2, 3,
4 i 5, itd. Optimalno rešenje dobija se na primer ako sa prvim prijateljem ode na šesto
mesto (5 dana), sa drugim na peto mesto (6 dana), sa trećim na drugo (3 dana), i sa petim
na osmo mesto (9 dana). To ukupno daje 5 + 6 + 3 + 9 = 23 dana.
Napomena.
U 60% test primera biće n, p ≤ 1.000, a u 30% n, p ≤ 200.
|
|
fajl: leto.cpp
|
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxN = 5000;
typedef struct { int t, index; } Mesto;
bool compareMesta(Mesto const& m1, Mesto const& m2) {
return (m1.t > m2.t);
}
typedef struct { int b, e, index; } Interval;
bool compareIntervali(Interval const& i1, Interval const& i2) {
return (i1.e < i2.e) || (i1.e == i2.e && i1.b > i2.b);
}
int n, p;
Mesto mesta[maxN];
Interval intervali[maxN];
int res;
int intervaluDodeljen[maxN], tmp[maxN];
void ucitajPodatke() {
freopen("leto.in", "r", stdin);
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &(mesta[i].t));
mesta[i].index = i;
}
scanf("%d", &p);
for (int i = 0; i < p; i++) {
scanf("%d%d", &(intervali[i].b), &(intervali[i].e));
intervali[i].b--;
intervali[i].e--;
}
}
void sortirajMesta() {
sort(mesta, mesta + n, compareMesta);
}
void sortirajIntervale() {
sort(intervali, intervali + p, compareIntervali);
}
bool uIntervalu(int mesto, int interval) {
return intervali[interval].b <= mesto && mesto <= intervali[interval].e;
}
int probajDaDodas(int mesto) {
int interval = 0;
while (interval < p) {
tmp[interval] = intervaluDodeljen[interval];
if (uIntervalu(mesto, interval))
if (tmp[interval] == -1) {
tmp[interval] = mesto;
return interval;
}
else if (tmp[interval] > mesto) {
int pom = tmp[interval];
tmp[interval] = mesto;
mesto = pom;
}
interval++;
}
return -1;
}
void resi() {
for (int i = 0; i < p; i++)
intervaluDodeljen[i] = -1;
for (int i = 0; i < n; i++) {
int dodatU = probajDaDodas(mesta[i].index);
if (dodatU != -1) {
res += mesta[i].t;
for (int j = 0; j <= dodatU; j++)
intervaluDodeljen[j] = tmp[j];
}
}
}
void sacuvajResenje() {
freopen("leto.out", "w", stdout);
printf("%d\n", res);
}
int main() {
ucitajPodatke();
sortirajMesta();
sortirajIntervale();
resi();
sacuvajResenje();
return 0;
}
|
|
|