글 읽기 - 틀렸습니다. 틀렸습니다. 지겹습니다 ㅜㅜ

kgc0517 6년 전 0

A, B 둘다 부분 합 구한후에 A를 기준으로 B를 이분탐색 해서 답을 구하는데 틀렸다네요.. 어디가 문제인지 모르겠습니다 형님들.

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin', 'utf8').split('\n');
var idx = 0;
var K = parseInt(input[idx++]);
var N = parseInt(input[idx++]);
var A = input[idx++].split(' ').map(function(a){return parseInt(a)});
var M = parseInt(input[idx++]);
var B = input[idx++].split(' ').map(function(a){return parseInt(a)});
var cnt = 0;
//부분합 구하기.
A = partSum(A);
B = partSum(B);
//이분 탐색
for(var i = 0; i < A.length; i++){
  cnt += upperBound(B, K - A[i]) - lowBound(B, K - A[i]);
}

console.log(cnt);

function upperBound(array, value) {var s = 0;var e = array.length;var m;while (s <= e) {m = (s + e) >> 1;if (array[m] <= value) s = m + 1;else e = m - 1;}return array[s - 1] === value ? s : -1;}
function lowBound(array, value) {var s = 0;var e = array.length;var m;while (s <= e) {m = (s + e) >> 1;if (array[m] >= value) e = m - 1;else s = m + 1;}return array[e + 1] === value? e + 1 : -1;}
function partSum(array){
  var accueSum = [0];
  var partSum = [];
  for(var i = 1; i <= array.length; i++){
    accueSum[i] = array[i-1] + accueSum[i - 1];
    for (var j = 0; j < i; j++) partSum.push(accueSum[i] - accueSum[j]);
  }
  return partSum.sort(function (a, b) {return a - b});
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀렸습니다. 틀렸습니다. 지겹습니다 ㅜㅜ

kgc0517 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말