Submission

----------

Score: 0

User: Jokul

Problemset: ความลึก

Language: c

Time: 0.942 second

Submitted On: 2025-04-15 14:50:56

#include <stdio.h>

int main() {
    int n, q, maxd = 0;
    scanf("%d %d", &n, &q);

    int d[n + 1], l[n + 1], ship[q], depth[n + 1];

    // Initialize depth array
    depth[0] = 0;

    // Read d and l arrays
    for (int i = 0; i < n; i++) {
        scanf("%d", &d[i]);
        scanf("%d", &l[i]);

        // Update depth based on d
        depth[i + 1] = depth[i] + d[i];

        // Track maximum depth
        if (depth[i + 1] > maxd) {
            maxd = depth[i + 1];
        }
    }

    // Array to store maximum lengths at each depth
    int wide[maxd + 1];
    for (int i = 0; i <= maxd; i++) {
        wide[i] = 0; // Initialize wide array
    }

    // Calculate maximum lengths for each depth
    for (int i = 0; i < n; i++) {
        for (int j = depth[i]; j <= maxd; j++) {
            if (wide[j] < wide[depth[i]] + l[i]) {
                wide[j] = wide[depth[i]] + l[i];
            }
        }
    }

    // Process queries
    for (int i = 0; i < q; i++) {
        scanf("%d", &ship[i]);
    }

    // Answer each query
    for (int i = 0; i < q; i++) {
        int ans = 0;
        for (int j = maxd; j > 0; j--) {
            if (ship[i] <= wide[j]) {
                ans = j;
                break;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}