Posters on a Fence (APCS 2022-01 Expert)

2.0s 256M

A wall consists of \(n\) unit-width planks with heights \(h_i\). There are \(k\) posters of widths \(w_1,\ldots,w_k\). All posters must have the same positive integer height and be placed from left to right in the given order. Each poster covers consecutive planks; posters cannot overlap, but gaps are allowed. A poster cannot exceed the height of any plank it covers. Find the maximum common height.

Input Format

The first line contains \(n,k\). The second line lists the plank heights \(h_i\). The third lists the poster widths \(w_i\).

Output Format

Print the maximum common height allowing all posters to be placed in order.

Constraints

\(1\le n\le200000\), \(1\le k\le\min(n,5000)\), \(1\le h_i\le10^9\), \(w_i\ge1\), \(\sum w_i\le n\).

Scoring

  • 20 points: \(n\le100\), \(k=1\).
  • 40 points: \(k=1\).
  • 40 points: No additional restrictions.

Each scored test is worth 5 points.

Sample Input 1

5 1
6 3 7 5 1
3

Sample Output 1

3

Sample Input 2

10 3
5 3 7 5 1 7 5 3 8 4
2 2 1

Sample Output 2

5

Source

APCS 2022-01 public archive version: h084。

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.