13335번: Trucks

https://www.acmicpc.net/problem/13335

$O(n)$

본문대로 구현하기

#include<cstdio>
int n, w, l, s[1001], b[1001];
int main() {
    scanf("%d%d%d", &n, &w, &l);
    for (int i = 1, j = 1; i <= n; i++) {
        scanf("%d", s + i);
        s[i] += s[i - 1];
        b[i] = b[i - 1] + 1;
        while (s[i] - s[j - 1] > l || b[i] - b[j] == w) b[i] = b[j++] + w;
    }
    printf("%d", b[n] + w);
    return 0;
}