n일 동안의 날씨 기록이 있다.
i번째 날에 든 볕의 양은 s_i이고, 내린 비의 양은 w_i이다.
곶감은 이어진 며칠 동안 말리는데, 그동안 든 볕의 합이 S 이상이고 내린 비의 합이 R 이하여야 잘 마른다.
말리기 시작하는 날과 끝내는 날을 고르는 방법 가운데 곶감이 잘 마르는 방법을 좋은 기간이라고 하자. 하루만 말리는 것도 기간이다.
질문 q개가 주어진다.
질문 "S R"마다 좋은 기간의 수, 가장 짧은 좋은 기간의 날수, 그 기간이 시작하는 날의 번호를 빈칸 하나로 띄워 한 줄에 출력하라.
가장 짧은 좋은 기간이 여럿이면 가장 먼저 시작하는 것을 고른다.
좋은 기간이 없으면 0 0 0을 출력한다.
예시 1의 첫 질문 "5 3"에서 좋은 기간은 4일~5일, 5일, 4일~6일, 5일~6일로 네 개이고, 가장 짧은 것은 5일 하루이다.
입력
첫 줄에 n과 q가 빈칸 하나로 띄워 주어진다. 둘째 줄에 s_1, …, s_n이, 셋째 줄에 w_1, …, w_n이 빈칸 하나로 띄워 주어진다. 다음 q줄에 S와 R이 빈칸 하나로 띄워 주어진다. 1 ≤ n ≤ 9,000, 1 ≤ q ≤ 150, 0 ≤ s_i, w_i ≤ 10^9, 0 ≤ S, R ≤ 10^13(모두 정수이고, 쉼표 없이 숫자만 주어진다)
출력
질문마다 한 줄에 좋은 기간의 수, 가장 짧은 좋은 기간의 날수, 그 기간이 시작하는 날의 번호. 좋은 기간이 없으면 0 0 0
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
끝내는 날 r을 하나로 정해 두면, 시작하는 날을 앞으로 당길수록 볕의 합도 비의 합도 늘기만 해요(값이 0 이상이라서요). 그래서 비 조건은 시작하는 날이 어떤 날 lo 이후일 때만 맞고, 볕 조건은 어떤 날 hi 이전일 때만 맞아요. r로 끝나는 좋은 기간은 시작하는 날이 lo부터 hi까지인 hi - lo + 1개이고, 그중 가장 짧은 것은 hi에서 시작해요. r이 하루 늘면 lo도 hi도 뒤로만 가요. 그래서 포인터 셋(r, lo, hi)이 저마다 처음부터 끝까지 한 번만 지나가고, 질문 하나가 n에 비례하는 시간에 끝나요. 합도 다시 더하지 않고, lo..r의 비 합과 hi..r의 볕 합을 하나씩 넣고 빼며 들고 가요. 여덟 언어의 풀이는 모양이 거의 같아요. C·C++·Java·C#·JavaScript·TypeScript는 rainSum -= rain[lo++]처럼 빼면서 포인터를 옮기는 것을 한 줄에 쓸 수 있고, Python과 크레이콘은 ++를 식 안에 쓸 수 없어서 두 줄로 나눠 써요. 함정 하나: 시작하는 날마다 끝내는 날을 하나씩 늘려 가며 모든 기간을 보면 질문 하나에 기간을 약 4,000만 개, 모두 60억 개쯤 봐야 해요. 비가 한 번도 오지 않아 중간에 그만둘 수도 없는 입력이 있어요. 이렇게 짠 Python 풀이는 시간 안에 끝나지 않았고, 같은 방식의 C 풀이도 이 컴퓨터에서 가장 큰 입력에 12초가 걸렸어요. 함정 둘: lo가 hi보다 뒤에 있으면 r로 끝나는 좋은 기간이 없는 거예요. lo <= hi를 확인하지 않고 hi - lo + 1을 더하면 음수가 더해져요. 예시 1의 첫 질문은 4가 아니라 2가 되고, 둘째 질문은 0 0 0이 아니라 -1 1 3이 돼요. 함정 셋: hi를 옮기는 반복에 hi < r이 없으면 S가 0일 때 hi가 r을 넘어가 날이 하나도 없는 기간을 세요. 예시 1의 셋째 질문 "0 1"에서 JavaScript는 5 1 1이 아니라 12 -1 3을 출력해요. JavaScript는 목록 끝을 넘겨 읽어도 undefined를 줄 뿐이라 조용히 틀리고, Python은 IndexError로, Java·C#은 예외로 멈춰요. C·C++은 무슨 일이 생길지 정해져 있지 않아요. 함정 넷: 가장 짧은 기간이 여럿이면 가장 먼저 시작하는 것을 골라야 해요. r을 앞에서부터 늘려 가므로 <로 비교해야 먼저 찾은 것이 남아요. <=로 비교하면 예시 1의 셋째 질문에서 시작하는 날이 1이 아니라 6이 돼요. 함정 다섯: 합이 9 × 10^12까지 커져요. Java·C#·C·C++은 합과 S, R을 long/long long에 담아야 해요. Java에서 합을 int에 담으면 예시 2의 첫 질문에서 30억이 -1294967296으로 바뀌어 1 3 1이 아니라 0 0 0이 나와요. Python의 정수는 크기 제한이 없고, JavaScript·TypeScript·크레이콘의 수는 2^53까지 정확해서 그대로 맞아요. 좋은 기간의 수는 많아야 약 4,050만이라 int에 들어가요.
Pythonmain.py · 44 줄
import sysdef solve(n, sun, rain, need, limit): """햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날).""" count = 0 best_len = best_start = 0 lo = 0 # 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0 # 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) rain_sum = 0 # lo..r의 비 합 sun_sum = 0 # hi..r의 햇볕 합 for r in range(n): rain_sum += rain[r] while rain_sum > limit: rain_sum -= rain[lo] lo += 1 sun_sum += sun[r] while hi < r and sun_sum - sun[hi] >= need: sun_sum -= sun[hi] hi += 1 # 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if sun_sum >= need and lo <= hi: count += hi - lo + 1 if best_len == 0 or r - hi + 1 < best_len: best_len = r - hi + 1 best_start = hi + 1 return count, best_len, best_startdef main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) sun = [int(x) for x in data[2:2 + n]] rain = [int(x) for x in data[2 + n:2 + 2 * n]] out = [] pos = 2 + 2 * n for _ in range(q): need, limit = int(data[pos]), int(data[pos + 1]) pos += 2 out.append("%d %d %d" % solve(n, sun, rain, need, limit)) print("\n".join(out))main()
JavaScriptmain.js · 37 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun = data.slice(2, 2 + n);const rain = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need, limit) { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 38 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun: number[] = data.slice(2, 2 + n);const rain: number[] = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need: number, limit: number): [number, number, number] { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out: string[] = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
JavaMain.java · 45 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] sun = new long[n]; long[] rain = new long[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) sun[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) rain[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(in.readLine()); long need = Long.parseLong(st.nextToken()); long limit = Long.parseLong(st.nextToken()); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } out.append(count).append(' ').append(bestLen).append(' ').append(bestStart).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 줄
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), q = int.Parse(p[1]); long[] sun = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] rain = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long need = long.Parse(p[0]), limit = long.Parse(p[1]); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } sb.Append(count).Append(' ').Append(bestLen).Append(' ').Append(bestStart).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 39 줄
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<long long> sun(n), rain(n); for (auto& v : sun) cin >> v; for (auto& v : rain) cin >> v; while (q--) { long long need, limit; cin >> need >> limit; int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long long rainSum = 0; // lo..r의 비 합 long long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } cout << count << ' ' << bestLen << ' ' << bestStart << '\n'; } return 0;}
Cmain.c · 36 줄
#include <stdio.h>static long long sun[9000], rain[9000];int main(void) { int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &sun[i]) != 1) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &rain[i]) != 1) return 0; for (int k = 0; k < q; k++) { long long need, limit; if (scanf("%lld %lld", &need, &limit) != 2) return 0; int count = 0, best_len = 0, best_start = 0; int lo = 0; /* 비 합이 limit 이하가 되는 가장 이른 시작 날 */ int hi = 0; /* 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) */ long long rain_sum = 0; /* lo..r의 비 합 */ long long sun_sum = 0; /* hi..r의 햇볕 합 */ for (int r = 0; r < n; r++) { rain_sum += rain[r]; while (rain_sum > limit) rain_sum -= rain[lo++]; sun_sum += sun[r]; while (hi < r && sun_sum - sun[hi] >= need) sun_sum -= sun[hi++]; /* 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 */ if (sun_sum >= need && lo <= hi) { count += hi - lo + 1; if (best_len == 0 || r - hi + 1 < best_len) { best_len = r - hi + 1; best_start = hi + 1; } } } printf("%d %d %d\n", count, best_len, best_start); } return 0;}
Craykonmain.cray · 45 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];q = 첫줄[1];볕 = 콘솔.수들읽기();비 = 콘솔.수들읽기();반복 (k = 0; k < q; k++){ 줄 = 콘솔.수들읽기(); need = 줄[0]; limit = 줄[1]; 센수 = 0; 짧은길이 = 0; 짧은시작 = 0; lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0; // 볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) 비합 = 0; // lo..r의 비 합 볕합 = 0; // hi..r의 볕 합 반복 (r = 0; r < n; r++) { 비합 = 비합 + 비[r]; 동안 (비합 > limit) { 비합 = 비합 - 비[lo]; lo = lo + 1; } 볕합 = 볕합 + 볕[r]; 동안 (hi < r && 볕합 - 볕[hi] >= need) { 볕합 = 볕합 - 볕[hi]; hi = hi + 1; } // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 만약 (볕합 >= need && lo <= hi) { 센수 = 센수 + hi - lo + 1; 만약 (짧은길이 == 0 || r - hi + 1 < 짧은길이) { 짧은길이 = r - hi + 1; 짧은시작 = hi + 1; } } } 콘솔.쓰기(센수 + " " + 짧은길이 + " " + 짧은시작);}