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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
첫줄 = コンソール.数読み();n = 첫줄[0];limit = 첫줄[1];a = コンソール.数読み();// 덱: 목록 하나와 머리 번호. 자리빼기(0)은 뒤의 것을 모두 당기니 머리 번호만 옮긴다dq = [];head = 0; // dq[head..]가 창 안의 '가장 힘든 구간' 후보(힘이 큰 것부터)left = 0;total = 0;count = 0;bestLen = 0;bestStart = 0;繰り返す (right = 0; right < n; right++){ total += a[right]; 間 (dq.個数 > head && a[dq[dq.個数 - 1]] <= a[right]) { dq.位置で取り除く(dq.個数 - 1); } dq.追加(right); // 가장 힘든 구간(dq[head])은 케이블카로 지나가니 뺀다. 넘치면 왼쪽을 줄인다 間 (total - a[dq[head]] > limit) { total -= a[left]; もし (dq[head] == left) { head += 1; } left += 1; } length = right - left + 1; count += length; もし (length > bestLen) { bestLen = length; bestStart = left + 1; }}コンソール.書く(count);コンソール.書く(bestLen + " " + bestStart);