글 읽기 - 어느 부분에서 틀렸는지 도저히 모르겠어서 질문드립니다

lobo_prix 4년 전 0

최대연속부분합(Kadane Algorithm)을 N번 하는거로 접근했습니다.

문제가 살짝 모호해서 assert 걸어보니 모두 음수인 케이스도 있긴한데, 음수인 경우도 잘 처리했다고 생각합니다.

63%정도에서 틀리는데, 코드에 더이상 의심가는 부분이 없어서 도움을 요청합니다...

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n; cin>>n;
	int ans=0;
	vector<pair<int,int>> t;
	for(int _=0;_<n;_++){
		int l; cin>>l;
		int a[l];
		for(int i=0;i<l;i++)
			cin>>a[i];
		int p=0;
		int mx=*max_element(a,a+l);
		//assert(mx>=0);
		for(int i=0;i<l;i++)
			mx=max(mx, p=max(p,0)+a[i]);
		p=0;
		int si=0, i;
		for(i=0;i<l;i++){
			if(p<=0)
				si=i;
			if((p=max(p,0)+a[i])==mx)
				break;
		}
		ans+=mx;
		t.push_back({si,i});
	}
	cout<<ans<<endl;
	for(auto i:t)
		cout<<i.first+1<<' '<<i.second+1<<endl;
	return 0;
}

kyo20111 4년 전 2

보석 개수를 최소화시키지 않는 것 같습니다.

lobo_prix 4년 전 1

그러네요🤦
감사합니다!

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

문제

문제

출처

ICPC

어느 부분에서 틀렸는지 도저히 모르겠어서 질문드립니다

lobo_prix 4년 전 0

kyo20111 4년 전 2

lobo_prix 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말