풀이
그리디하게 풀면 된다.
가장 큰 값까지 간 다음 가능한 시간 동안 계속 풀을 뜯어 먹는다.
그리고 이후의 값들 중 가장 큰 값을 찾고
이 동작을 반복한다.
코드
#include <cstdio>
#include <algorithm>
long long l, n, r, f, b, x[100003], c[100003];
int main() {
scanf("%lld %lld %lld %lld", &l, &n, &f, &b);
for (int i = 1; i <= n; i++) scanf("%lld %lld", &x[i], &c[i]);
for (int i = n; i >= 1; i--)
r += (f - b) * (x[i] - x[i-1]) * (c[i] = std::max(c[i], c[i+1]));
printf("%lld\n", r);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이