글 읽기 - 2036 / 수열의 점수 / 반례 부탁드립니다

Green55 6년 전 0

어디가 틀렸을까요? 수열을 0, 1, 1보다 큰 양수, 음수로 나누어 저장해 풀었습니다.

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, zero=0, one=0;
	long long ans=0;
	cin >> n;
	vector<int> plus, minus;
	while(n--){
		int a;
		cin >> a;
		if(a==0) ++zero;
		else if(a==1) ++one;
		else if(a<0) minus.push_back(a);
		else plus.push_back(a);
	}
	//양수는 큰 것끼리 짝지어 곱해서 더한다.
	sort(plus.begin(),plus.end(),greater<int>());
	for(int i=0; i<(int)plus.size()-1; i+=2)
		ans += plus[i]*plus[i+1];
	//짝지어지지 못한 양수가 있다면 더한다.
	if(plus.size()&1)
		ans += plus.back();
	//1은 무조건 더한다.
	ans += one;
	sort(minus.begin(),minus.end());
	//음수는 절댓값이 큰것끼리 곱해서 더한다.
	for(int i=0; i<(int)minus.size()-1; i+=2)
		ans += minus[i]*minus[i+1];
	//짝지어지지 못한 음수가 있다면, 0이 있으면 곱하고, 없으면 더한다.
	if((minus.size()&1)&&zero==0)
		ans += minus.back();
	cout << ans;
}

chogahui05 6년 전 1

아. 알고리듬이 맞은 거 같은데. 틀렸습니다가 뙇~ 하고 뜨면

오버플로우를 의심해 봐야 겠지요?

long long 형 변수 = long long형 변수 + (int형 변수 * int형 변수) 인데

int형 변수의 절대치가 100만까지 들어올 수 있거든요.. 100만 * 100만이면 딱 봐도 10^12인데 이건 2^31보다 크지 않나요?

Green55 6년 전 0

감사합니다

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

문제

문제

출처

ICPC

2036 / 수열의 점수 / 반례 부탁드립니다

Green55 6년 전 0

chogahui05 6년 전 1

Green55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말