Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
984. Hosting
Олимпиадные задачи на английском языке| 03/07/2008 | Лето 2008 дорешивание ( 6J) |
| 14/07/2008 | Лето 2008 - 6 (J) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
There are `n` major cities in the world. These cities are labeled from 0 to `n-1`, which in order to form a convex polygon on a single plain. Each year, the ACM-ICPC Committee has to select one city from these cities to host the ACM-ICPC world final. The selection process is described as follows:
- At the first phase, they create a shortlist. In order to do so, with a starting city `s` and a selection step `d`, they put all the cities with label `s+i*d` into the shortlist for all `i` such that `0\ ≤\ i` and `s+i*d\ <\ n`.
- At the second phase, one city will be selected from the shortlist to organize the ACM-ICPC world final. At that year, they might choose the city which is the most to the North (maximal `y` coordinate), to the South (minimal `y` coordinate), to the East (maximal `x` coordinate) or to the West (minimal `x` coordinate).
There is a cost associated with each city to organize the ACM-ICPC world final. It is assumed that this cost does not change over years. Your task is to compute the total cost the ACM-ICPC Committee has to pay to organize the ACM-ICPC world finals for a given number of years.
Input
The first line contains the integer number `n` (`1\ ≤\ n\ ≤\ 100\ 000`). Each line of the next `n` lines describes one city, which contains three integer numbers `x`, `y`, and `c`. The pair `(x,\ y)` is a 2-D coordinate specifying the location of the city (`-200\ 000\ ≤\ x,\ y\ ≤\ 200\ 000`). `c` is the associated cost to organize the ACM-ICPC world final in that city (`1\ ≤\ c\ ≤\ 1000`). The next line contains an integer number `m`, which is the number of years the ACM-ICPC Committee want to compute the cost to organize the ACM-ICPC world finals (`1\ ≤\ m\ ≤\ 100\ 000`). Each line of the next `m` lines contains three integer numbers `s`, `d` (`0\ ≤\ s\ <\ n`; `1\ ≤\ d`), and `p`. The value of `p` can be 0, 1, 2 or 3 for selecting the city most to North, the South, the East or the West respectively.
Output
Write the total cost for the ACM-ICPC Committee to organize the ACM-ICPC world finals.
Sample Input 1
4 -1 1 2 0 4 3 5 3 2 1 -1 2 2 0 1 0 0 2 1
Sample Output 1
5
Sample Input 2
3 0 0 2 1 1 3 2 10 2 2 1 1 1 0 2 0
Sample Output 2
5
