← 返回题目列表

Codeforces · 1938/B

B. 景点得分

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Attraction Score - 原题 PDF 第 1 页
原题PDF第3页
Attraction Score - 原题 PDF 第 2 页
原题PDF第4页
可复制的 PDF 提取文本
Problem B
                        Attraction Score
                     Time limit: 4 seconds


There are n cities, numbered from 1 to n, in the fictional country of Manteiv. We can consider these cities to be on a
flat plane with a 2D coordinate system, where city i is at coordinates (xi, yi). No two cities are located at the same
position.

There are m highways, numbered from 1 to m, each of which is a line segment with two different cities as its endpoints
and has a number of attraction points alongside it. Specifically, highway j has aj attraction points and connects cities
uj and vj as its endpoints. Having intersections on highways causes traffic jams, and building a highway on top of
another highway costs a lot of money. Therefore, it is guaranteed that


     • no two highways intersect at any point other than at a city,

     • no highway passes through a city other than its two endpoints, and

     • there is at most one highway connecting each pair of cities.


The Manteiv Ministry of Tourism would like to choose a subset of cities as tourist attractions. Intuitively, the ministry
would like many pairs of chosen cities to be connected by a highway with many attraction points.  Formally, the
attraction score of a non-empty subset of cities S is defined as follows:

     • For every pair of integers (a, b) where a < b, cities a and b are in S, and they are connected by a highway, add
      the number of attraction points on the highway to the score.

     • Let f(S) be the number of pairs of integers (a, b) where a < b, cities a and b are in S, and they are not connected
     by a highway. The score incurs a penalty (negative) score of 106 multiplied by the square of f(S). In other
      words, subtract 106 × f(S)2 from the score.

For example, let n = 3, cities 1 and 2 be connected by a highway with 10 attraction points, cities 2 and 3 be connected
by a highway with 20 attraction points, and cities 1 and 3 not be connected by a highway.

     • The attraction score of the subset of cities {1} is 0.

     • The attraction score of the subset of cities {1, 2} is 10 −106 × 02 = 10.

     • The attraction score of the subset of cities {2, 3} is 20 −106 × 02 = 20.

     • The attraction score of the subset of cities {1, 2, 3} is 10 + 20 −106 × 12 = −999 970.


As an advisor to the ministry, you would like to find the maximum attraction score among all possible non-empty
subsets of cities S.

Input

The first line of input contains two integers n and m (1 ≤n ≤100 000; 0 ≤m ≤300 000). Each of the next n lines
contains two integers. The i-th line contains xi and yi (0 ≤xi, yi ≤109). Each of the next m lines contains three
integers. The j-th line contains uj, vj, and aj (1 ≤uj < vj ≤n; 0 ≤aj ≤106). The highways are guaranteed to
satisfy the conditions in the problem statement.

ICPC Asia Pacific Championship 2024 Problem B: Attraction Score

Output

Output an integer representing the maximum attraction score among all possible non-empty subsets of cities S.


 Sample Input #1                          Sample Output #1
 3 2                                    20
 0 0
 0 1
 1 0
 1 2 10
 2 3 20


Explanation for the sample input/output #1

This sample is the example given in the problem statement above. The subset of cities {2, 3} gives the highest attraction
score of 20.


 Sample Input #2                          Sample Output #2
 3 3                                    60
 0 0
 0 1
 1 0
 1 2 10
 2 3 20
 1 3 30


Explanation for the sample input/output #2

The cities and highways are illustrated by Figure B.1. By choosing cities 1, 2, and 3 in S, the attraction score would
be 10 + 20 + 30 −106 × 02 = 60.

                                                               1   City 2




                                                                 A2 = 20
                                                 A1 = 10


                                                               0   City 1       A3 = 30       City 3
                                                                   0                                             1


                                  Figure B.1: Illustration of sample input #2.





ICPC Asia Pacific Championship 2024 Problem B: Attraction Score