yl-9/probench huggingface dataset:
# All Pairs Segments

## Problem Description

[Shirobon - FOX](https://soundcloud.com/shirobon/fox?in=mart_207/sets/fav)

⠀



You are given $ n $ points on the $ x $ axis, at increasing positive integer coordinates $ x_1 < x_2 < \ldots < x_n $ .

For each pair $ (i, j) $ with $ 1 \leq i < j \leq n $ , you draw the segment $ [x_i, x_j] $ . The segments are closed, i.e., a segment $ [a, b] $ contains the points $ a, a+1, \ldots, b $ .

You are given $ q $ queries. In the $ i $ -th query, you are given a positive integer $ k_i $ , and you have to determine how many points with integer coordinates are contained in exactly $ k_i $ segments.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ , $ q $ ( $ 2 \le n \le 10^5 $ , $ 1 \le q \le 10^5 $ ) — the number of points and the number of queries.

The second line of each test case contains $ n $ integers $ x_1, x_2, \ldots, x_n $ ( $ 1 \leq x_1 < x_2 < \ldots < x_n \leq 10^9 $ ) — the coordinates of the $ n $ points.

The third line of each test case contains $ q $ integers $ k_1, k_2, \ldots, k_q $ ( $ 1 \leq k_i \leq 10^{18} $ ) — the parameters of the $ q $ queries.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ , and the sum of $ q $ over all test cases does not exceed $ 10^5 $ .

## Output Format

For each test case, output a single line with $ q $ integers: the $ i $ -th integer is the answer to the $ i $ -th query.

## Sample #1

### Sample Input #1

```
3
2 2
101 200
2 1
6 15
1 2 3 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 8
254618033 265675151 461318786 557391198 848083778
6 9 15 10 6 9 4 4294967300
```

### Sample Output #1

```
0 100 
0 0 0 0 2 0 0 0 3 0 2 0 0 0 0 
291716045 0 0 0 291716045 0 301749698 0
```

## Hint

In the first example, you only draw the segment $ [101, 200] $ . No point is contained in exactly $ 2 $ segments, and the $ 100 $ points $ 101, 102, \ldots, 200 $ are contained in exactly $ 1 $ segment.

In the second example, you draw $ 15 $ segments: $ [1, 2], [1, 3], [1, 5], [1, 6], [1, 7], [2, 3], [2, 5], [2, 6], [2, 7], [3, 5], [3, 6], [3, 7], [5, 6], [5, 7], [6, 7] $ . Points $ 1, 7 $ are contained in exactly $ 5 $ segments; points $ 2, 4, 6 $ are contained in exactly $ 9 $ segments; points $ 3, 5 $ are contained in exactly $ 11 $ segments.

## Limit



Time Limit
1.50s

Memory Limit
250.00MB

Tags: implementation, math
Difficulty: 1200
# Max Plus Size

## Problem Description

[EnV - Dynasty](https://soundcloud.com/envyofficial/env-dynasty)

⠀



You are given an array $ a_1, a_2, \ldots, a_n $ of positive integers.

You can color some elements of the array red, but there cannot be two adjacent red elements (i.e., for $ 1 \leq i \leq n-1 $ , at least one of $ a_i $ and $ a_{i+1} $ must not be red).

Your score is the maximum value of a red element plus the number of red elements. Find the maximum score you can get.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ) — the length of the array.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 1000 $ ) — the given array.

## Output Format

For each test case, output a single integer: the maximum possible score you can get after coloring some elements red according to the statement.

## Sample #1

### Sample Input #1

```
4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 4 5
9
17 89 92 42 29 92 14 70 45
```

### Sample Output #1

```
7
6
10
97
```

## Hint

In the first test case, you can color the array as follows: $ [\color{red}{5}, 4, \color{red}{5}] $ . Your score is $ \max([5, 5]) + \text{size}([5, 5]) = 5+2 = 7 $ . This is the maximum score you can get.

In the second test case, you can color the array as follows: $ [\color{red}{4}, 5, \color{red}{4}] $ . Your score is $ \max([4, 4]) + \text{size}([4, 4]) = 4+2 = 6 $ . This is the maximum score you can get.

In the third test case, you can color the array as follows: $ [\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 4, \color{red}{5}] $ . Your score is $ \max([3, 3, 4, 3, 5]) + \text{size}([3, 3, 4, 3, 5]) = 5+5 = 10 $ . This is the maximum score you can get.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, dp, greedy
Difficulty: 800
# Complex Segments (Hard Version)

## Problem Description

[Ken Arai - COMPLEX](https://soundcloud.com/diatomichail2/complex)

⠀



This is the hard version of the problem. In this version, the constraints on $ n $ and the time limit are higher. You can make hacks only if both versions of the problem are solved.

A set of (closed) segments is complex if it can be partitioned into some subsets such that

- all the subsets have the same size; and
- a pair of segments intersects if and only if the two segments are in the same subset.

You are given $ n $ segments $ [l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n] $ . Find the maximum size of a complex subset of these segments.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of segments.

The second line of each test case contains $ n $ integers $ l_1, l_2, \ldots, l_n $ ( $ 1 \le l_i \le 2n $ ) — the left endpoints of the segments.

The third line of each test case contains $ n $ integers $ r_1, r_2, \ldots, r_n $ ( $ l_i \leq r_i \le 2n $ ) — the right endpoints of the segments.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the maximum size of a complex subset of the given segments.

## Sample #1

### Sample Input #1

```
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10
```

### Sample Output #1

```
3
4
4
```

## Hint

In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments.

In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: $ \{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\} $ .

In the third test case, it is optimal to make a single group containing all the segments except the second.

## Limit



Time Limit
13.00s

Memory Limit
250.00MB

Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings
Difficulty: 3400
# Complex Segments (Easy Version)

## Problem Description

[Ken Arai - COMPLEX](https://soundcloud.com/diatomichail2/complex)

⠀



This is the easy version of the problem. In this version, the constraints on $ n $ and the time limit are lower. You can make hacks only if both versions of the problem are solved.

A set of (closed) segments is complex if it can be partitioned into some subsets such that

- all the subsets have the same size; and
- a pair of segments intersects if and only if the two segments are in the same subset.

You are given $ n $ segments $ [l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n] $ . Find the maximum size of a complex subset of these segments.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^4 $ ) — the number of segments.

The second line of each test case contains $ n $ integers $ l_1, l_2, \ldots, l_n $ ( $ 1 \le l_i \le 2n $ ) — the left endpoints of the segments.

The third line of each test case contains $ n $ integers $ r_1, r_2, \ldots, r_n $ ( $ l_i \leq r_i \le 2n $ ) — the right endpoints of the segments.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^4 $ .

## Output Format

For each test case, output a single integer: the maximum size of a complex subset of the given segments.

## Sample #1

### Sample Input #1

```
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10
```

### Sample Output #1

```
3
4
4
```

## Hint

In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments.

In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: $ \{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\} $ .

In the third test case, it is optimal to make a single group containing all the segments except the second.

## Limit



Time Limit
6.00s

Memory Limit
250.00MB

Tags: binary search, data structures, divide and conquer, dsu, greedy, math, sortings
Difficulty: 3300
# Max Plus Min Plus Size

## Problem Description

[EnV - The Dusty Dragon Tavern](https://soundcloud.com/envyofficial/env-the-dusty-dragon-tavern)

⠀



You are given an array $ a_1, a_2, \ldots, a_n $ of positive integers.

You can color some elements of the array red, but there cannot be two adjacent red elements (i.e., for $ 1 \leq i \leq n-1 $ , at least one of $ a_i $ and $ a_{i+1} $ must not be red).

Your score is the maximum value of a red element, plus the minimum value of a red element, plus the number of red elements. Find the maximum score you can get.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the array.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the given array.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the maximum possible score you can get after coloring some elements red according to the statement.

## Sample #1

### Sample Input #1

```
4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 5 4
10
17 89 92 42 29 41 92 14 70 45
```

### Sample Output #1

```
12
11
12
186
```

## Hint

In the first test case, you can color the array as follows: $ [\color{red}{5}, 4, \color{red}{5}] $ . Your score is $ \max([5, 5]) + \min([5, 5]) + \text{size}([5, 5]) = 5+5+2 = 12 $ . This is the maximum score you can get.

In the second test case, you can color the array as follows: $ [4, \color{red}{5}, 4] $ . Your score is $ \max([5]) + \min([5]) + \text{size}([5]) = 5+5+1 = 11 $ . This is the maximum score you can get.

In the third test case, you can color the array as follows: $ [\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 5, \color{red}{4}] $ . Your score is $ \max([3, 3, 4, 3, 4]) + \min([3, 3, 4, 3, 4]) + \text{size}([3, 3, 4, 3, 4]) = 4+3+5 = 12 $ . This is the maximum score you can get.

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: data structures, dp, dsu, greedy, implementation, matrices, sortings
Difficulty: 2200
# Tree Pruning

## Problem Description

[t+pazolite, ginkiha, Hommarju - Paved Garden](https://soundcloud.com/fractalex-gd/ginkiha-paved-garden-little)

⠀



You are given a tree with $ n $ nodes, rooted at node $ 1 $ . In this problem, a leaf is a non-root node with degree $ 1 $ .

In one operation, you can remove a leaf and the edge adjacent to it (possibly, new leaves appear). What is the minimum number of operations that you have to perform to get a tree, also rooted at node $ 1 $ , where all the leaves are at the same distance from the root?

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 3 \leq n \leq 5 \cdot 10^5 $ ) — the number of nodes.

Each of the next $ n-1 $ lines contains two integers $ u $ , $ v $ ( $ 1 \leq u, v \leq n $ , $ u \neq v $ ), describing an edge that connects $ u $ and $ v $ . It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the minimum number of operations needed to achieve your goal.

## Sample #1

### Sample Input #1

```
3
7
1 2
1 3
2 4
2 5
4 6
4 7
7
1 2
1 3
1 4
2 5
3 6
5 7
15
12 9
1 6
6 14
9 11
8 7
3 5
13 5
6 10
13 15
13 6
14 12
7 2
8 1
1 4
```

### Sample Output #1

```
2
2
5
```

## Hint

In the first two examples, the tree is as follows:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2018C/46789adad3b93ca642b297f7ca0ca574c7f98f60.png)In the first example, by removing edges $ (1, 3) $ and $ (2, 5) $ , the resulting tree has all leaves (nodes $ 6 $ and $ 7 $ ) at the same distance from the root (node $ 1 $ ), which is $ 3 $ . The answer is $ 2 $ , as it is the minimum number of edges that need to be removed to achieve the goal.

In the second example, removing edges $ (1, 4) $ and $ (5, 7) $ results in a tree where all leaves (nodes $ 4 $ and $ 5 $ ) are at the same distance from the root (node $ 1 $ ), which is $ 2 $ .

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: brute force, dfs and similar, greedy, sortings, trees
Difficulty: 1700
# Speedbreaker

## Problem Description

[Djjaner - Speedbreaker](https://soundcloud.com/luciano-ferrari-151560131/speedbreaker)

⠀



There are $ n $ cities in a row, numbered $ 1, 2, \ldots, n $ left to right.

- At time $ 1 $ , you conquer exactly one city, called the starting city.
- At time $ 2, 3, \ldots, n $ , you can choose a city adjacent to the ones conquered so far and conquer it.

You win if, for each $ i $ , you conquer city $ i $ at a time no later than $ a_i $ . A winning strategy may or may not exist, also depending on the starting city. How many starting cities allow you to win?

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of cities.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the deadlines for conquering the cities.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the number of starting cities that allow you to win.

## Sample #1

### Sample Input #1

```
3
6
6 3 3 3 5 5
6
5 6 4 1 4 5
9
8 6 4 2 1 3 5 7 9
```

### Sample Output #1

```
3
0
1
```

## Hint

In the first test case, cities $ 2 $ , $ 3 $ , and $ 4 $ are good starting cities.

In the second test case, there are no good starting cities.

In the third test case, the only good starting city is city $ 5 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, data structures, dp, greedy, implementation, two pointers
Difficulty: 1900
# Cards Partition

## Problem Description

[DJ Genki vs Gram - Einherjar Joker](https://soundcloud.com/leon-hwang-368077289/einherjar-joker-dj-genki-vs-gram)

⠀



You have some cards. An integer between $ 1 $ and $ n $ is written on each card: specifically, for each $ i $ from $ 1 $ to $ n $ , you have $ a_i $ cards which have the number $ i $ written on them.

There is also a shop which contains unlimited cards of each type. You have $ k $ coins, so you can buy at most $ k $ new cards in total, and the cards you buy can contain any integer between $ \mathbf{1} $ and $ \mathbf{n} $ , inclusive.

After buying the new cards, you must partition all your cards into decks, according to the following rules:

- all the decks must have the same size;
- there are no pairs of cards with the same value in the same deck.

Find the maximum possible size of a deck after buying cards and partitioning them optimally.

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains two integers $ n $ , $ k $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ , $ 0 \leq k \leq 10^{16} $ ) — the number of distinct types of cards and the number of coins.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^{10} $ , $ \sum a_i \geq 1 $ ) — the number of cards of type $ i $ you have at the beginning, for each $ 1 \leq i \leq n $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer: the maximum possible size of a deck if you operate optimally.

## Sample #1

### Sample Input #1

```
9
3 1
3 2 2
5 4
2 6 1 2 4
2 100
1410065408 10000000000
10 8
7 4 6 6 9 3 10 2 8 7
2 12
2 2
2 70
0 1
1 0
1
3 0
2 1 2
3 1
0 3 3
```

### Sample Output #1

```
2
3
1
7
2
2
1
1
2
```

## Hint

In the first test case, you can buy one card with the number $ 1 $ , and your cards become $ [1, 1, 1, 1, 2, 2, 3, 3] $ . You can partition them into the decks $ [1, 2], [1, 2], [1, 3], [1, 3] $ : they all have size $ 2 $ , and they all contain distinct values. You can show that you cannot get a partition with decks of size greater than $ 2 $ , so the answer is $ 2 $ .

In the second test case, you can buy two cards with the number $ 1 $ and one card with the number $ 3 $ , and your cards become $ [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5] $ , which can be partitioned into $ [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5] $ . You can show that you cannot get a partition with decks of size greater than $ 3 $ , so the answer is $ 3 $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: 2-sat, brute force, greedy, implementation, math
Difficulty: 1600
# Robin Hood Archery

## Problem Description

At such times archery was always the main sport of the day, for the Nottinghamshire yeomen were the best hand at the longbow in all merry England, but this year the Sheriff hesitated...



Sheriff of Nottingham has organized a tournament in archery. It's the final round and Robin Hood is playing against Sheriff!

There are $ n $ targets in a row numbered from $ 1 $ to $ n $ . When a player shoots target $ i $ , their score increases by $ a_i $ and the target $ i $ is destroyed. The game consists of turns and players alternate between whose turn it is. Robin Hood always starts the game, then Sheriff and so on. The game continues until all targets are destroyed. Both players start with score $ 0 $ .

At the end of the game, the player with most score wins and the other player loses. If both players have the same score, it's a tie and no one wins or loses. In each turn, the player can shoot any target that wasn't shot before. Both play optimally to get the most score possible.

Sheriff of Nottingham has a suspicion that he might lose the game! This cannot happen, you must help Sheriff. Sheriff will pose $ q $ queries, each specifying $ l $ and $ r $ . This means that the game would be played only with targets $ l, l+1, \dots, r $ , as others would be removed by Sheriff before the game starts.

For each query $ l $ , $ r $ , determine whether the Sheriff can not lose the game when only considering the targets $ l, l+1, \dots, r $ .

## Input Format

The first line of input contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ , $ q $ ( $ 1 \le n,q \le 2\cdot10^5 $ ) — the number of targets and the queries Sheriff will pose.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ ) — the points for hitting each target.

Then follow $ q $ lines, each with two integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) — the range of the targets that is considered for each query.

It is guaranteed that the sum of both $ n $ and $ q $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each query, output "YES", if the Sheriff does not lose the game when only considering the targets $ l, l+1, \dots, r $ , and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Sample #1

### Sample Input #1

```
2
3 3
1 2 2
1 2
1 3
2 3
5 3
2 1 2 1 1
1 2
1 3
4 5
```

### Sample Output #1

```
NO
NO
YES
NO
NO
YES
```

## Limit



Time Limit
3.00s

Memory Limit
250.00MB

Tags: data structures, divide and conquer, greedy, hashing
Difficulty: 1900
# Milky Days

## Problem Description

What is done is done, and the spoilt milk cannot be helped.



Little John is as little as night is day — he was known to be a giant, at possibly $ 2.1 $ metres tall. It has everything to do with his love for milk.

His dairy diary has $ n $ entries, showing that he acquired $ a_i $ pints of fresh milk on day $ d_i $ . Milk declines in freshness with time and stays drinkable for a maximum of $ k $ days. In other words, fresh milk acquired on day $ d_i $ will be drinkable between days $ d_i $ and $ d_i+k-1 $ inclusive.

Every day, Little John drinks drinkable milk, up to a maximum of $ m $ pints. In other words, if there are less than $ m $ pints of milk, he will drink them all and not be satisfied; if there are at least $ m $ pints of milk, he will drink exactly $ m $ pints and be satisfied, and it's a milk satisfaction day.

Little John always drinks the freshest drinkable milk first.

Determine the number of milk satisfaction days for Little John.

## Input Format

The first line of the input contains a single integer $ t $ ( $ 1\leq t \leq 10^4 $ ), the number of test cases.

The first line of each test case consists of three integers $ n $ , $ m $ , $ k $ ( $ 1\le n $ , $ m $ , $ k \le 10^5 $ ), the number of diary entries, the maximum pints needed for a milk satisfaction day, and the duration of milk's freshness.

Then follow $ n $ lines of each test case, each with two integers $ d_i $ and $ a_i $ ( $ 1\le d_i $ , $ a_i \le 10^6 $ ), the day on which the milk was acquired and the number of pints acquired. They are sorted in increasing values of $ d_i $ , and all values of $ d_i $ are distinct.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

## Output Format

For each test case, output a single integer, the number of milk satisfaction days.

## Sample #1

### Sample Input #1

```
6
1 1 3
1 5
2 3 3
1 5
2 7
4 5 2
1 9
2 6
4 9
5 6
5 2 4
4 7
5 3
7 1
11 2
12 1
4 1 3
5 10
9 4
14 8
15 3
5 5 5
8 9
10 7
16 10
21 5
28 9
```

### Sample Output #1

```
3
3
4
5
10
6
```

## Hint

In the first test case, $ 5 $ pints of milk are good for $ 3 $ days before spoiling.

In the second test case, the following will happen:

- On day $ 1 $ , he will receive $ 5 $ pints of milk and drink $ 3 $ of them (leaving $ 2 $ pints from day $ 1 $ );
- On day $ 2 $ , he will receive $ 7 $ pints of milk and drink $ 3 $ of them (leaving $ 2 $ pints from day $ 1 $ and $ 4 $ pints from day $ 2 $ );
- On day $ 3 $ , he will drink $ 3 $ pints from day $ 2 $ (leaving $ 2 $ pints from day $ 1 $ and $ 1 $ pint from day $ 2 $ );
- On day $ 4 $ , the milk acquired on day $ 1 $ will spoil, and he will drink $ 1 $ pint from day $ 2 $ (no more milk is left).

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: brute force, data structures, greedy, implementation
Difficulty: 2200