좌표 0~1,000,000 안에서 2*k + 1짜리 연속 부분수열의 합의 최대값을 구하면 된다.
<코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> using namespace std; int n, k, a[1000001], s, ans; int main() { scanf("%d%d", &n, &k); for (int i = 0, b, c; i < n; i++) { scanf("%d%d", &b, &c); a[c] = b; } k = k * 2 + 1; for (int i = 0; i <= 1000000; i++) { if (i >= k) s -= a[i - k]; s += a[i]; ans = s > ans ? s : ans; } printf("%d\n", ans); return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 11762 A Towering Problem (0) | 2017.08.31 |
|---|---|
| 1884 고속도로 (0) | 2017.08.31 |
| 14619 섬 여행 (0) | 2017.08.30 |
| 11664 선분과 점 (0) | 2017.08.30 |
| 1069 집으로 (0) | 2017.08.30 |