Подразделы

Другие разделы

Дата и время

09/04/2025 02:23:32

Авторизация

984. Hosting

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Sample Output 1

Sample Input 2

Sample Output 2

Источник: РГУ им. И.Канта, осенний командный турнир, 2007

03/07/2008	Лето 2008 дорешивание ( 6J)
14/07/2008	Лето 2008 - 6 (J)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

984. Hosting

Hosting