Bitland has N cities connected by one common highway. East of the first
the city has a Bitzon warehouse. Distance from Bitzon warehouse to first city
is m1 time units, from the first to the second city - m2 time units, and so on as
shown in the illustration:
A pile of parcels is brought to the warehouse every day for the courier to take out. For everyone
the address (city number) and the time when the parcel is to be delivered.
Parcels may be delivered by courier earlier than planned, but necessarily not later than specified
time.
The courier leaves the warehouse in the morning (we will consider this moment at time 0) and travels from one city
delivering parcels to another.
In this task, we will assume that the delivery of the parcel does not take time, only driving from
from one city to another.
Task. Known list of parcels to be delivered by the courier. Find:
1. Will the courier be able to deliver all parcels without delay.
2. In as little time as possible, the courier will be able to deliver all parcels and return to the warehouse.
Initial data. The first line contains the number of cities N. The second line contains
N integers - distances m1, m2,. . . , mN. The third line contains the number of parcels K.
Finally, follow the K lines describing all the parcels. Each of these lines is presented after
two integers: city number ai (1 ≤ ai ≤ N) where the parcel is to be delivered,
and the latest possible delivery time ti
.
Assume that the courier leaves the warehouse at time 0. Can be delivered to the same city
more than one parcel. The courier can deliver the parcels in any order (but without delay).
Results. Output a single integer in the least amount of time possible
all parcels and return to the warehouse. If at least one parcel cannot be delivered on time,
output −1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
|
#include <iostream>
using namespace std;
int main()
{
int N; //how many cities
int K; //how many parcels
cin >> N;
int m[N]; //distance between cities
for(int i = 0; i < N; i++)
{
cin >> m[i];
}
//--------------------------------
cin >> K;
int a[K];
int t[K];
for(int i = 0; i < K; i++)
{
if(i == K)
{
}
cin >> a[1] >> t[i];
}
//---------------------------------
for(int i = 0; i < K; i++)
{
for(int j = 0; j < i; j++)
{
if(a[i] == a[j])
{
}
if(a[i] != a[j])
{
for(int k = 0; k < j; k++)
{
}
}
}
}
return 0;
}
/*
6
30 30 40 20 10 70
3
2 70
5 130
3 180
*/
// the result should be 260
|