시도 횟수: 2회

해결한 시간: 24:05

핵심 아이디어

<aside> 💡

나머지가 같은 것끼리 빼지고 더해진다.

$i$가 변화하면서 빼지고 더해지는 MOD들을 관리하며 슬라이딩 윈도우를 하면 된다.

MOD별로 묶어서 관리하면 구현하기 편하다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n, w;
int c[200'001];

void solve()
{
    cin >> n >> w;
    vector<ll> mod(2*w+1, 0LL); 
    for(int i = 1; i<=n; i++){
        cin >> c[i];
        mod[i%(2*w)] += c[i];
    }

    ll cur = 0;
    for(int i = 0; i<w; i++){
        cur += mod[i];
    }

    ll ans = cur;
    for(int i = w; i<2*w; i++){
        cur -= mod[i-w];
        cur += mod[i];
        ans = min(ans, cur);
    }
    for(int i = 0; i<w; i++){
        cur -= mod[i+w];
        cur += mod[i];
        ans = min(ans, cur);
    }

    cout << ans <<"\\n";
}

int main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while(_tc--) solve();    
    return 0;
}

복기

너무 잘한듯