比赛场次 353
比赛名称 20161223
比赛状态 已结束比赛成绩
开始时间 2016-12-23 19:10:00
结束时间 2016-12-23 22:00:00
开放分组 全部用户
注释介绍
题目名称 萌化大革命
输入输出 checklist.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarMealy AAAAAAAAAA 0.070 s 9.33 MiB 100
GravatarKZNS AAAAAAAAAA 0.099 s 7.18 MiB 100
GravatarOstmbh AAAAAAAAAA 0.113 s 8.11 MiB 100
Gravatar1azyReaper AAAAAAAAAA 0.124 s 6.43 MiB 100
Gravatarconfoo AAAAAAAAAA 0.218 s 15.87 MiB 100
GravatarShirry AAWAWWAAAA 0.098 s 8.09 MiB 70

萌化大革命

★★☆   输入文件:checklist.in   输出文件:checklist.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


公元6666年,11区在当时的国家主席的引导下,爆发了如火如荼的萌化大革命,各地学生热烈响应,其中一部分学生想要见主席,于是他们就来到了天门广场,他们由于政治信仰的不同,被分为H个蕾姆卫兵(a)和G个艾米莉亚卫兵(b),主席迫切的想要接见这些学生,为了公平,根据先来后到的原则,对于报名的蕾姆卫兵,必须按照$a_1,a_2,......a_H$的顺序进行接见,对于G个报名的艾米莉亚卫兵,必须按照$b_1,b_2,......b_G$的顺序进行接见,即在总共接见的H+G个卫兵中,对于两种卫兵的任意编号$i<j$,接见的顺序编号$c_i$和$c_j$必须满足$c_i<c_j$

每一个卫兵在天门广场有一个二维坐标$(x,y)$,由于$a_1$是香之港の记者,所以主席必须先接见$a_1$,初始位置也在$a_1$,由于$a_H$是德克士,主席要跟他谈笑风生,所以$a_H$必须是主席最后一个接见的学生。

每次离开一个学生去接见另一个学生时,若两个学生的距离为$D$,则主席会减少$D^2$秒的寿命,而作为主席钦定的总理你,则需要帮助主席安排行程,减少主席的寿命流失,因为主席说过,他流失了多少寿命,你就要续上双倍的~

【输入格式】

第一行两个整数H,G,表示两种卫兵的数量

接下来H行每行两个整数,为每个蕾姆卫兵的坐标

接下来G行每行两个整数,为每个艾米莉娅卫兵的坐标

【输出格式】

只有一行一个整数,为最小的损失寿命

【样例输入】

3 2

0 0

1 0

2 0

0 3

1 3

【样例输出】

  20

【提示】

最优接见顺序:

$a_1$->$b_1$->$b_2$->$a_2$->$a_3$

$(0,0)$->$(0,3)$->$(1,3)$->$(1,0)$->$(2,0)$

耗费为$3^2+1^2+3^2+1^2=20$

其他两种唯二可能的方案:

$(0,0)$->$(0,3)$->$(1,0)$->$(1,3)$->$(2,0)$

耗费为$9+10+9+10=39$

$(0,0)$->$(1,0)$->$(0,3)$->$(1,3)$->$(2,0)$

耗费为$1+10+1+10=22$

数据范围:

对于100%的数据,$1<=H,G<=1000$,横纵坐标是$0....1000$之内的整数

【来源】

USACO 2016-2017 金组第二题