제출 #1347574

#제출 시각아이디문제언어결과실행 시간메모리
1347574killerzaluuModsum (NOI12_modsum)C++20
25 / 25
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

int cnt_mod(long long l, long long r, int rem) {
    if (l > r) return 0;
    long long first = l;
    while (first <= r && first % 5 != rem) first++;
    if (first > r) return 0;
    return (r - first) / 5 + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long dp[5] = {};
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;

        long long cnt[5] = {};
        for (int r = 0; r < 5; r++) {
            cnt[r] = cnt_mod(v, w, r);
        }

        long long ndp[5] = {};
        for (int a = 0; a < 5; a++) {
            for (int b = 0; b < 5; b++) {
                ndp[(a + b) % 5] += dp[a] * cnt[b];
            }
        }

        for (int j = 0; j < 5; j++) dp[j] = ndp[j];
    }

    int val[5] = {1, 4, 5, 5, 4};

    long long ans = 0;
    for (int r = 0; r < 5; r++) {
        ans += dp[r] * val[r];
    }

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...