MojaCoder will discontinue its service and shut down the judging system on December 31, 2026.

002 E1 - Radar I

2 secs 1024 MB

6 3
70 80 20 0 10 10 50 90

$T,C$ が小さいので、今から $i$ 〜 $i+C-1$ 分後の降水量の合計を毎回求めて全捜索します。

1つ目のケースについて考えます。

$i=1$ なら $i+C-1$ までの降水量の合計は

R[1]+R[2]+R[3]=70+80+20=170

です。この降水量の合計 $R_{t}+R_{t+1}+...+R_{t+C-1}$ が $1≤t≤T$ を満たす $t$ のうち最も小さい $t$ を答えます。

計算量 $O(TC)$ で答えることができました。

#include <stdio.h>

int main(){
    int T, C;  scanf("%d%d", &T, &C);
    
    int R[T+C-1];
    for(int i=0; i<T+C-1; i++) scanf(" %d", &R[i]);
    
    int ans, MIN=1e9;
    for(int i=0; i<T; i++){
        
        int sum = 0;
        
        for(int j=0; j<C; j++) sum += R[i+j];
        
        if(sum<MIN){
            MIN = sum;
            ans = i+1;
        }
    }
    
    printf("%d\n", ans);
}