글 읽기 - 반례 부탁드립니다. 예제는 전부 맞습니다.

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

반례 부탁드립니다. 예제는 전부 맞습니다.

4097번 - 수익

naneunmuneo 1년 전 0

날짜별로 각 값들의 누적을 dp배열에 넣었고

모든날이 적자가일 경우에는 적자가 가장 적게난날을 출력하고 그것이 아니라면

0일부터 가장 많이 누적된 값에서 (0일부터 많이 누적된날 까지중) 가장 적게 누적된값을 빼줍니다.

s일에서 e일까지의 수익은 e일까지의 수익 -(s-1)일 까지의 수익이다.
- 시작일 전날 까지의 수익은 제외해야하기에 라는 생각으로 짯습니다.

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int main() {
 ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
 while (true)
 {
 int N; cin >> N;
 if (!N)break;
 
 vector<int> dp(N + 1); dp[0] = 0; // 계산상의 편의를 위해 0일에는 수익 0
 vector<int> val(N); // 값들 저장
 for (int i = 1; i <= N; ++i)
 {
 cin >> dp[i];
 val[i-1]=dp[i];
 dp[i] += dp[i - 1];
 }
 auto max_val = max_element(val.begin(), val.end()); 
 if (*max_val < 0)
 {
 cout << *max_val << '\n';
 continue;
 }
 
 auto max_iter = max_element(dp.begin()+1, dp.end()); // 0일부터 가장 많이 누적한 값
 auto min_iter = min_element(dp.begin(), max_iter); // 0일부터 최대전까지 가장 적은값
 cout << *max_iter - *min_iter<<'\n';
 }
 return 0;
}

naneunmuneo 1년 전 1

아 접근을 잘못했네요

-100,-111,-222,1,2,-1000 에서 반례확인했습니다.

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

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

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

한국어 | English (Beta)

문제

문제

출처

ICPC