글 읽기 - 고수형님들 죽겠습니다. 제발 반례좀 주시면 감사하겠습니다.

mduddns 3년 전 0

72퍼정도까지 가서 틀렸습니다가 뜹니다.

정올 기출이라 정올에서 돌려봤더니 정올에선 다 맞았다고 뜨는데

차이가 음수가 가능한것 정도인거같은데 잘모르겠습니다..

부분합 구한후 리스트에 넣고 리스트 하나 정렬해서 list1에 대한값 이분탐색으로 갯수 셌습니다....

반례주시면 감사하겠씁니다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int t,n,m;
	static int[] a;
	static int[] b;
	static long[] sa;
	static long[] sb;
	static List<Long> list1;
	static List<Long> list2;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		//정올 사이트에서는 성공코드...
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		t = Integer.parseInt(br.readLine());
		n = Integer.parseInt(br.readLine());
		a = new int[n+1];
		sa = new long[n+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<n+1; i++) {
			a[i] = Integer.parseInt(st.nextToken());
			sa[i] = sa[i-1]+a[i];
		}
		m = Integer.parseInt(br.readLine());
		b = new int[m+1];
		sb = new long[m+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<m+1; i++) {
			b[i] = Integer.parseInt(st.nextToken());
			sb[i] = sb[i-1]+b[i];
		}
		list1 = new ArrayList<>();
		list2 = new ArrayList<>();
		for(int i=1; i<n+1; i++) {
			for(int j=i; j<n+1; j++) {
				list1.add((sa[j]-sa[i-1]));
			}
		}
		for(int i=1; i<m+1; i++) {
			for(int j=i; j<m+1; j++) {
				list2.add((sb[j]-sb[i-1]));
			}
		}
		Collections.sort(list2);
		int ans=0;
		Map<Long,Long> map = new HashMap<>();
		//list2에 대해서 binarysearch하자.
		//한번 찾은건 hashmap에 저장.
		for(int i=0; i<list1.size(); i++) {
			long tmp = t-list1.get(i);
			if(map.containsKey(tmp)) {
				long k = map.get(tmp);
				ans+=k;
			}
			else {
				long k = binarySearch(0, list2.size()-1, tmp);
				map.put(tmp, k);
				ans+=k;
			}
		}

		bw.append(ans+"");
		bw.flush();
		bw.close();



	}

	public static long binarySearch(int start, int end, long search) {
		if(start==end) {
			if(list2.get(start)==search) {
				return 1;
			}
			return 0;
		}
		int mid = (start+end)/2;
		long number = list2.get(mid);
		long ret=0;
		if(number>=search) {
			ret+=binarySearch(start,mid,search);
		}
		if(number<=search) {
			ret+=binarySearch(mid+1, end, search);
		}
		return ret;
		
		
	}
	

}

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

문제

문제

출처

ICPC

고수형님들 죽겠습니다. 제발 반례좀 주시면 감사하겠습니다.

mduddns 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말