A ridge walk that takes the cable car over the hardest section
Along a ridge, n trail sections lie in a row, numbered 1 to n.
Walking section i costs aᵢ energy.
A hiker picks consecutive sections l through r (1 ≤ l ≤ r ≤ n) as a 'route'.
The one section of the route that costs the most energy is crossed by cable car and costs nothing. Even if several sections tie for the most, the cable car covers only one section.
If the total energy of the remaining sections is at most T, the route is 'walkable'.
A route with a single section costs 0 and is always walkable.
On the first line print the number of walkable routes (l, r).
On the second line print the number of sections in the walkable route with the most sections, and its start l. If there are several such routes, choose the smallest l.
Input
The first line has n and T, and the second line has a₁ … aₙ separated by single spaces. 1 ≤ n ≤ 10,000, 0 ≤ T ≤ 10,000,000,000,000 (10^13), 1 ≤ aᵢ ≤ 1,000,000,000. All are integers
Output
Two lines: the number of walkable routes, then the section count and start of the longest route separated by one space. Plain digits, no commas
Example 1 · stdin
6 5
3 9 2 4 1 7
stdout
14
3 1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Extending a route one section to the right never lowers 'sum − maximum' (a new section below the maximum adds itself; one above it adds the old maximum). So two pointers work: move the right end r one step at a time and advance the left end l only on overflow, and the walkable routes ending at r number r − l + 1. Finding the window maximum from scratch each time is n², so a deque keeps only 'positions that can still become the maximum', largest first: pop back candidates not larger than the new section, push it, and pop the front once the left end passes it. Example: with T = 5, 9 2 4 rides over 9 and costs 2 + 4 = 6, not allowed, while 2 4 1 costs 2 + 1 = 3, allowed. Trap one: sliding the window on sum ≤ T alone (forgetting the cable car) is wrong. Trap two: shrinking once with if on overflow may still give the longest length but miscounts — it must be while. Trap three: if you don't pop the front when the left end passes it, you keep subtracting a big section that already left the window. Trap four: if you discard sections smaller than the current maximum, you don't know the next maximum once it leaves. Trap five: >= on equal lengths keeps the later start. Trap six: the sum reaches 10^13, so use long long in C/C++ and long in Java/C# (a 32-bit int holds about 2.1 billion). Python integers don't overflow, and numbers in JavaScript, TypeScript and Craykon are exact up to 2^53 (about 9×10^15). Deques differ: Python collections.deque, Java ArrayDeque and C++ std::deque exist; C# has no deque class, so use an array with head and tail indices (same in C). shift() on a JavaScript/TypeScript array and RemoveAt(0) on a Craykon list move everything behind, so pop the front by just raising a head index.
Pythonmain.py · 31 lines
import sysfrom collections import dequedata = sys.stdin.buffer.read().split()n, limit = int(data[0]), int(data[1])a = [int(x) for x in data[2:2 + n]]dq = deque() # 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다left = 0total = 0 # 창 안의 힘의 합count = 0best_len = 0best_start = 0for right in range(n): total += a[right] while dq and a[dq[-1]] <= a[right]: dq.pop() dq.append(right) # 가장 힘든 구간(dq[0])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while total - a[dq[0]] > limit: total -= a[left] if dq[0] == left: dq.popleft() left += 1 length = right - left + 1 count += length # right에서 끝나는 길은 시작이 left..right인 것 모두 if length > best_len: # 같으면 먼저 찾은(시작이 앞선) 것을 둔다 best_len = length best_start = left + 1print(count)print(best_len, best_start)
JavaScriptmain.js · 32 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const limit = data[1];const a = data.slice(2, 2 + n);// 덱: 배열 하나와 머리 번호. shift()는 뒤의 것을 모두 당기니 쓰지 않는다const dq = new Array(n);let head = 0;let tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)let left = 0;let total = 0;let count = 0;let bestLen = 0;let bestStart = 0;for (let right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] === left) head++; left++; } const length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}console.log(count + "\n" + bestLen + " " + bestStart);
TypeScriptmain.ts · 34 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n: number = data[0];const limit: number = data[1];const a: number[] = data.slice(2, 2 + n);// 덱: 배열 하나와 머리 번호. shift()는 뒤의 것을 모두 당기니 쓰지 않는다const dq: number[] = new Array<number>(n).fill(0);let head = 0;let tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)let left = 0;let total = 0;let count = 0;let bestLen = 0;let bestStart = 0;for (let right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] === left) head++; left++; } const length: number = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}console.log(`${count}\n${bestLen} ${bestStart}`);
JavaMain.java · 39 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); long limit = Long.parseLong(st.nextToken()); long[] a = new long[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); // 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다 ArrayDeque<Integer> dq = new ArrayDeque<>(); int left = 0, bestLen = 0, bestStart = 0; long total = 0; // 10^13까지 가서 int로는 넘친다 long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (!dq.isEmpty() && a[dq.peekLast()] <= a[right]) dq.pollLast(); dq.addLast(right); // 가장 힘든 구간(맨 앞)은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq.peekFirst()] > limit) { total -= a[left]; if (dq.peekFirst() == left) dq.pollFirst(); left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } System.out.println(count); System.out.println(bestLen + " " + bestStart); }}
C#Main.cs · 42 lines
using System;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]); long limit = long.Parse(data[1]); var a = new long[n]; for (int i = 0; i < n; i++) a[i] = long.Parse(data[2 + i]); // .NET에는 Deque 클래스가 없다: 배열 하나와 머리·꼬리 번호로 덱을 만든다 var dq = new int[n]; int head = 0, tail = 0; // dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터) int left = 0, bestLen = 0, bestStart = 0; long total = 0; // 10^13까지 가서 int로는 넘친다 long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) head++; left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } Console.WriteLine(count); Console.WriteLine($"{bestLen} {bestStart}"); }}
C++main.cpp · 38 lines
#include <deque>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long limit; cin >> n >> limit; vector<long long> a(n); for (auto &x : a) cin >> x; deque<int> dq; // 창 안에서 '가장 힘든 구간' 후보의 자리. 힘이 큰 것부터 작은 것 순서로 남는다 int left = 0, bestLen = 0, bestStart = 0; long long total = 0; // 10^13까지 가서 int로는 넘친다 long long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (!dq.empty() && a[dq.back()] <= a[right]) dq.pop_back(); dq.push_back(right); // 가장 힘든 구간(dq.front())은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq.front()] > limit) { total -= a[left]; if (dq.front() == left) dq.pop_front(); left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } cout << count << "\n" << bestLen << " " << bestStart << "\n"; return 0;}
Cmain.c · 36 lines
#include <stdio.h>#define MAXN 10000static long long a[MAXN];static int dq[MAXN]; /* 덱: dq[head..tail-1]이 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터) */int main(void) { int n; long long limit; if (scanf("%d %lld", &n, &limit) != 2) return 1; for (int i = 0; i < n; i++) scanf("%lld", &a[i]); int head = 0, tail = 0, left = 0, bestLen = 0, bestStart = 0; long long total = 0; /* 10^13까지 가서 int로는 넘친다 */ long long count = 0; for (int right = 0; right < n; right++) { total += a[right]; while (tail > head && a[dq[tail - 1]] <= a[right]) tail--; dq[tail++] = right; /* 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 */ while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) head++; left++; } int length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; } } printf("%lld\n%d %d\n", count, bestLen, bestStart); return 0;}
Craykonmain.cray · 41 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];limit = 첫줄[1];a = Console.ReadNumbers();// 덱: 목록 하나와 머리 번호. 자리빼기(0)은 뒤의 것을 모두 당기니 머리 번호만 옮긴다dq = [];head = 0; // dq[head..]가 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)left = 0;total = 0;count = 0;bestLen = 0;bestStart = 0;for (right = 0; right < n; right++){ total += a[right]; while (dq.Count > head && a[dq[dq.Count - 1]] <= a[right]) { dq.RemoveAt(dq.Count - 1); } dq.Add(right); // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 while (total - a[dq[head]] > limit) { total -= a[left]; if (dq[head] == left) { head += 1; } left += 1; } length = right - left + 1; count += length; if (length > bestLen) { bestLen = length; bestStart = left + 1; }}Console.WriteLine(count);Console.WriteLine(bestLen + " " + bestStart);