题目名称	140. [USACO Jan08] 化装晚会
输入输出	`costume.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	16 MiB
测试数据	9
题目来源	BYVoid 于2008-10-04加入
开放分组	全部用户
提交状态
分类标签	USACO 分治
	分享题解

通过：146，提交：280，通过率：52.14%
dateri	100	0.000 s	0.00 MiB	C++
cy	100	0.000 s	0.00 MiB	C++
syzhaoss	100	0.000 s	0.00 MiB	C++
梦那边的美好ET	100	0.007 s	0.39 MiB	C++
xiao er	100	0.010 s	0.03 MiB	Pascal
粘粘自喜	100	0.011 s	0.39 MiB	C++
devil	100	0.012 s	0.39 MiB	C++
Zayin	100	0.012 s	0.39 MiB	C++
jhyjhy	100	0.012 s	1.05 MiB	C++
digital-T	100	0.012 s	1.05 MiB	C++

本题关联比赛
20100919
20181001
20181001

关于化装晚会的近10条评论(全部评论)
有一个简单的做法，可以暴力，但是发现sort以后会满足单调性，左端点递增的同时，r不会递增，所以可以用这个优化暴力，为O(n) 帅气的背影 2018-10-24 22:05 9楼
回复 @Ezoi_Magic doge : 为什么我T了！你还我正确率！ Janis 2016-09-26 20:46 8楼
sort后枚举就行了... Hakurou! 2016-07-11 18:24 7楼
寡人就想偷个懒，超了2次时重写才A掉安呐一条小咸鱼。 2016-02-20 07:25 6楼
本来想着树状数组+离散化（压缩内存）+二分A掉，结果太蒻调不出来，怒上n^2.... liu_runda 2016-02-19 21:30 5楼
其实数据很水 O(n^2)水过 0 2015-10-21 21:45 4楼
回复 @HouJikan : 用前缀和就可以了，不需要用树状数组。 /k 2015-10-21 21:24 3楼
$n2$ Dissolute丶Tokgo 2015-10-04 15:09 2楼
我用的是树状数组，然后空间有点不够啊= = 肯定有更好的办法的吧 HouJikan 2014-08-29 15:51 1楼

140. [USACO Jan08] 化装晚会

★☆ 输入文件：costume.in 输出文件：costume.out 简单对比
时间限制：1 s 内存限制：16 MiB

【题目描述】

万圣节又到了！Farmer John打算带他的奶牛去参加一个化装晚会，但是，FJ只做了一套能容下两头总长不超过$S(1\leq S\leq 10^6)$的牛的恐怖服装。

FJ养了$N(2\leq n\leq 2\times 10^4)$头按$1,2,\cdots,n$的顺序编号的奶牛，编号为$i$的奶牛的长度为$l_i(1\leq l_i\leq 10^6)$。如果两头奶牛的总长度不超过$S$，那么她们就能穿下这套服装。

FJ想知道，如果他想选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。

【输入格式】

第1行: 2个用空格隔开的整数：$n,S$。

第2..N+1行: 第$i+1$为$1$个整数：$l_i$。

【输出格式】

第1行: 输出1个整数，表示FJ可选择的所有方案数。注意奶牛顺序不同的两种方案是被视为相同的

【输入样例】

【输出样例】

【样例解释】

4种选择分别为：奶牛1和奶牛3；奶牛1和奶牛4；奶牛2和奶牛4；奶牛3和奶牛4。