BOJ)11974 Subsequences Summing to Sevens

문제: icpc.me/11974

N마리의 소가 각각의 고유 ID를 가지고 있을 때 연속된 소의 고유 ID의 합이 7의 배수인 구간의 길이를 출력하는 문제이다.

소를 입력 받은 후에 소의 partial sum을 저장한 뒤 partial sum을 7로 나눈 나머지를 저장한다면 

해당 값이 같은 가장 긴 구간이 답이될 것이다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, a[50000], p[50000], r;
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    for (int i = 0; i < n; i++) {
        if (!i)
            p[i] = a[i];
        else
            p[i] = p[i - 1] + a[i];
    }
    for (int i = 0; i < n; i++) 
        p[i] = p[i] % 7;
    for (ll i = 0; i < 7; i++) {
        ll x = -1;
        ll y = n + 1;
        for (ll j = 0; j < n; j++) {
            if (p[j] == i) {
                x = max(j, x);
                y = min(j, y);
            }
        }
        if (x != -1 && y != n + 1) {
            r = max(r, x - y);
        }
    }
    printf("%lld", r);
    return 0;
}