D. Holidays

Codeforces

IDCF10018D

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Everyone knows that the battle of Endor is just a myth fabled by George Lucas for promotion of his movie. Actually, no battle of Endor has happened and the First Galactic Empire prospers to this day. There are creatures of n races living in the First Galactic Empire. In order to demonstrate their freedom, equality and brotherhood the Emperor commanded to introduce the holidays. During each of these holidays creatures of one non-empty subset of races should give gifts to creatures of another non-empty subset of races, not intersecting the first one. The Emperor's stuff is not very strong in maths so you should calculate how many such holidays can be introduced. Two holidays are considered different if they differ in the subset of races which give gifts or in the subset of races which receive gifts. The input contains the only integer n (1 ≤ n ≤ 200000) — the number of races living in the First Galactic Empire. Find the number of holidays the Emperor commanded to introduce. This number can be very large, so output the reminder of division of this number by 109 + 9. ## Input The input contains the only integer n (1 ≤ n ≤ 200000) — the number of races living in the First Galactic Empire. ## Output Find the number of holidays the Emperor commanded to introduce. This number can be very large, so output the reminder of division of this number by 109 + 9. [samples]

**Definitions** Let $ D, N, M \in \mathbb{Z} $ with $ 2 \leq D \leq 1000 $, $ 2 \leq N \leq 1000 $, $ 1 \leq M < N $. Let $ C \in \mathbb{Z}^{D \times N} $ be a matrix where $ c_{d,n} $ is the utility consumption on day $ d \in \{1, \dots, D\} $ during portion $ n \in \{1, \dots, N\} $. **Constraints** All $ c_{d,n} \geq 0 $ and $ c_{d,n} \leq 10^9 $. **Objective** Find $ s \in \{1, \dots, N - M + 1\} $ and $ S \in \mathbb{R} $ such that: $$ S = \sum_{d=1}^{D} \sum_{i=0}^{M-1} c_{d, s+i} $$ is maximized over all valid starting positions $ s $. Output $ s $ and $ S $.

API Response (JSON)

{
  "problem": {
    "name": "D. Holidays",
    "description": {
      "content": "Everyone knows that the battle of Endor is just a myth fabled by George Lucas for promotion of his movie. Actually, no battle of Endor has happened and the First Galactic Empire prospers to this day. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10018D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Everyone knows that the battle of Endor is just a myth fabled by George Lucas for promotion of his movie. Actually, no battle of Endor has happened and the First Galactic Empire prospers to this day.\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ D, N, M \\in \\mathbb{Z} $ with $ 2 \\leq D \\leq 1000 $, $ 2 \\leq N \\leq 1000 $, $ 1 \\leq M < N $.  \nLet $ C \\in \\mathbb{Z}^{D \\times N} $ be a matrix where $ c_{d,n} $ is the uti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments