Submission #1023157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023157		avighna	Modsum (NOI12_modsum)	C++17	25 / 25	179 ms	1888 KiB

modsum

#include <bits/stdc++.h>

typedef long long ll;

const ll MAX_SUM = 100001;

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

    ll n;
    std::cin >> n;
    std::vector<std::pair<ll, ll>> a(n);
    for (auto &i : a) {
        std::cin >> i.first >> i.second;
    }

    std::vector<ll> dp(MAX_SUM);
    dp[0] = 1;
    for (ll i = 0; i < n; ++ i) {
        std::vector<ll> ndp(MAX_SUM);
        for (ll j = 0; j < MAX_SUM; ++ j) {
            for (ll k = a[i].first; k <= a[i].second; ++ k) {
                if (j - k >= 0) {
                    ndp[j] += dp[j - k];
                }
            }
        }
        dp = ndp;
    }

    ll ans = 0;
    for (ll i = 0; i < MAX_SUM; ++ i) {
        ll mod_val = ((((i * i) % 5) * ((i * i) % 5)) % 5 + 2 * ((i * i) % 5)) % 5;
        ans += dp[i] * (mod_val + 1);
    }
    std::cout << ans << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5