686 . 密室逃脫

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

nanj0178

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

25.0% (7/28)

Tags

apcsc apcsc-enumerate

Description

你和朋友一行 $N$ 人被困在密室中，提示上寫道「人山人海，$M$ 斤八兩」並放著一個體重計，你馬上意識到要取前兩個字解讀，也就是放上三個總和 $M$ 斤的人。

然而你卻好奇有多少通關方式，因此你問了現場 $N$ 個人的體重，並想找出有多少種選出三人的方式總和剛好是 $M$ 斤。請注意，兩人體重有可能會相同，此時他們仍算不同人。

Input Format

輸入第一行是兩個空白分隔的數字 $N, M$ 分別代表密室人數和目標總重。
第二行有 $N$ 個空白分隔的數字 $a_1, a_2, \dots, a_N$ ， 代表所有人分別幾斤。

$30\%$ 測資保證 $1\le N\le 200$ ， $1\le M, a_i\le 10^ 9$ 。

$70\%$ 測資保證 $1\le N\le 5000$ ， $1\le M, a_i\le 10^ 9$ 。

Output Format

輸出一行一個整數，代表有幾種選出三人的方法可以過關。

Sample Input 1

3 6
2 1 3

Sample Output 1

1

Sample Input 2

6 10
1 2 3 4 5 6

Sample Output 2

3

Hints

Problem Source

LeetCode 3Sum

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 $1\le N\le 200$ 30
3 0~15 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 2 3
9 1000 524288 65536 2 3
10 1000 524288 65536 3
11 1000 524288 65536 3
12 1000 524288 65536 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
Submit
Back to Top