글 읽기 - 정확히 60%에서 틀리는데 이유를 모르겠습니다.

(追記) (追記ここまで)

정확히 60%에서 틀리는데 이유를 모르겠습니다.

1208번 - 부분수열의 합 2

khqwer 1년 전 0

20개를 기준으로 좌우로 나누고 hashmap을 이용한 dp를 이용해서 합이 같은 경우에 대해서 계산했습니다.

그런데 정확히 60%에서 틀림이 나옵니다. 크게 문제를 경우를 남는 경우가 문제인가 싶어서 u64를 사용했는데

뭐가 문제인지 모르겠습니다.

use std::{collections::HashMap, io};
fn main() {
 let input = std::io::read_to_string(io::stdin()).unwrap();
 let input: Vec<&str> = input.trim().lines().collect();
 let nums: Vec<i64> = input[0]
 .trim()
 .split_ascii_whitespace()
 .map(|s| s.parse::<i64>().unwrap())
 .collect();
 let numarray: Vec<i64> = input[1]
 .trim()
 .split_ascii_whitespace()
 .map(|s| s.parse::<i64>().unwrap())
 .collect();
 let leftarray = if nums[0] > 20 {
 numarray[..20].to_vec()
 } else {
 numarray.clone()
 };
 let rightarray = if nums[0] > 20 {
 numarray[20..].to_vec()
 } else {
 Vec::new()
 };
 let mut counter = 0u64;
 let mut leftbasket: HashMap<i64, u64> = HashMap::new();
 for i in 0..leftarray.len() {
 let mut temparray = HashMap::new();
 temparray.insert(leftarray[i], 1);
 if !leftbasket.is_empty() {
 for (value, cnt) in leftbasket.iter() {
 *temparray.entry(*value + leftarray[i]).or_insert(0) += *cnt;
 }
 }
 for (value, cnt) in temparray.iter() {
 if *value == nums[1] {
 counter += *cnt;
 }
 *leftbasket.entry(*value).or_insert(0) += *cnt;
 }
 }
 let mut rightbasket: HashMap<i64, u64> = HashMap::new();
 if !rightarray.is_empty() {
 for i in 0..rightarray.len() {
 let mut temparray = HashMap::new();
 temparray.insert(rightarray[i], 1);
 if !rightbasket.is_empty() {
 for (value, cnt) in rightbasket.iter() {
 *temparray.entry(*value + rightarray[i]).or_insert(0) += *cnt;
 }
 }
 for (value, cnt) in temparray.iter() {
 if *value==nums[1]{counter+=1;}
 *rightbasket.entry(*value).or_insert(0) += *cnt;
 }
 }
 for (value, cnt) in leftbasket.iter() {
 if let Some(right_cnt) = rightbasket.get(&(nums[1] - *value)) {
 counter += *cnt * right_cnt;
 }
 }
 }
 println!("{}", counter);
}

khqwer 1년 전 0

rightbasket에 if *value==num[1] {counter+=cnt;}를 잘못써서 틀린거네요 ᅲ.ᅲ

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

정확히 60%에서 틀리는데 이유를 모르겠습니다.

khqwer 1년 전 0

khqwer 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말