A. Greed

Codeforces

IDCF892A

Time2000ms

Memory256MB

Difficulty—

greedyimplementation

English · Original

Chinese · Translation

Formal · Original

Jafar has _n_ cans of cola. Each can is described by two integers: remaining volume of cola _a__i_ and can's capacity _b__i_ (_a__i_ ≤ _b__i_). Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not! ## Input The first line of the input contains one integer _n_ (2 ≤ _n_ ≤ 100 000) — number of cola cans. The second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 109) — volume of remaining cola in cans. The third line contains _n_ space-separated integers that _b_1, _b_2, ..., _b__n_ (_a__i_ ≤ _b__i_ ≤ 109) — capacities of the cans. ## Output Print "_YES_" (without quotes) if it is possible to pour all remaining cola in 2 cans. Otherwise print "_NO_" (without quotes). You can print each letter in any case (upper or lower). [samples] ## Note In the first sample, there are already 2 cans, so the answer is "_YES_".

Jafar 有 #cf_span[n] 罐可乐。每罐可乐由两个整数描述：剩余可乐体积 #cf_span[ai] 和罐的容量 #cf_span[bi]（#cf_span[ai] #cf_span[ ≤ ] #cf_span[bi]）。 Jafar 决定将所有剩余可乐倒入恰好 #cf_span[2] 个罐中，请判断他是否能做到！输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）— 可乐罐的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 10^9]）— 每罐中剩余可乐的体积。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, b2, ..., bn]（#cf_span[ai ≤ bi ≤ 10^9]）— 每罐的容量。如果可以将所有剩余可乐倒入 #cf_span[2] 个罐中，请输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。你可以以任意大小写形式输出每个字母。在第一个样例中，已有 #cf_span[2] 个罐，因此答案为 "_YES_"。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100 000]）— 可乐罐的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 10^9]）— 每罐中剩余可乐的体积。第三行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, b2, ..., bn]（#cf_span[ai ≤ bi ≤ 10^9]）— 每罐的容量。 ## Output 如果可以将所有剩余可乐倒入 #cf_span[2] 个罐中，请输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。你可以以任意大小写形式输出每个字母。 [samples] ## Note 在第一个样例中，已有 #cf_span[2] 个罐，因此答案为 "_YES_"。

Let $ n $ be the number of cans. Let $ a_i $ be the remaining volume of cola in can $ i $, and $ b_i $ be its capacity, for $ i = 1, 2, \dots, n $, with $ 0 \leq a_i \leq b_i $. Let $ S = \sum_{i=1}^n a_i $ be the total remaining volume of cola. Determine whether there exist two distinct cans $ j $ and $ k $ (with $ 1 \leq j < k \leq n $) such that: $$ a_j + a_k + \sum_{\substack{i=1 \\ i \neq j,k}}^n a_i \leq b_j + b_k $$ Equivalently: $$ S \leq b_j + b_k $$ That is, determine if there exist two cans whose combined capacity is at least the total volume of cola. **Objective:** Check whether $ \max_{1 \leq j < k \leq n} (b_j + b_k) \geq S $. Equivalently, let $ b_{(1)} \geq b_{(2)} \geq \dots \geq b_{(n)} $ be the capacities sorted in non-increasing order. Then the maximum possible sum of two capacities is $ b_{(1)} + b_{(2)} $. Thus, the condition simplifies to: $$ b_{(1)} + b_{(2)} \geq S $$ **Answer:** YES if $ b_{(1)} + b_{(2)} \geq \sum_{i=1}^n a_i $, otherwise NO.

Samples

Input #1

2
3 5
3 6

Output #1

YES

Input #2

3
6 8 9
6 10 12

Output #2

NO

Input #3

5
0 0 5 0 0
1 1 8 10 5

Output #3

YES

Input #4

4
4 1 0 3
5 2 2 3

Output #4

YES

API Response (JSON)

{
  "problem": {
    "name": "A. Greed",
    "description": {
      "content": "Jafar has _n_ cans of cola. Each can is described by two integers: remaining volume of cola _a__i_ and can's capacity _b__i_ (_a__i_  ≤  _b__i_). Jafar has decided to pour all remaining cola into jus",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF892A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Jafar has _n_ cans of cola. Each can is described by two integers: remaining volume of cola _a__i_ and can's capacity _b__i_ (_a__i_  ≤  _b__i_).\n\nJafar has decided to pour all remaining cola into jus...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Jafar 有 #cf_span[n] 罐可乐。每罐可乐由两个整数描述：剩余可乐体积 #cf_span[ai] 和罐的容量 #cf_span[bi]（#cf_span[ai] #cf_span[ ≤ ] #cf_span[bi]）。\n\nJafar 决定将所有剩余可乐倒入恰好 #cf_span[2] 个罐中，请判断他是否能做到！\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n $ be the number of cans.  \nLet $ a_i $ be the remaining volume of cola in can $ i $, and $ b_i $ be its capacity, for $ i = 1, 2, \\dots, n $, with $ 0 \\leq a_i \\leq b_i $.  \n\nLet $ S = \\sum_{i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments