oj.uz

Submission #1023157

# Submission time Handle Problem Language Result Execution time Memory
1023157 2024-07-14T11:20:59 Z avighna Modsum (NOI12_modsum) C++17
25 / 25
 179 ms 1888 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1880 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1880 KB Output is correct
2 Correct 6 ms 1884 KB Output is correct
3 Correct 5 ms 1884 KB Output is correct
4 Correct 7 ms 1884 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1884 KB Output is correct
2 Correct 18 ms 1880 KB Output is correct
3 Correct 25 ms 1884 KB Output is correct
4 Correct 17 ms 1880 KB Output is correct
5 Correct 19 ms 1884 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1880 KB Output is correct
2 Correct 34 ms 1884 KB Output is correct
3 Correct 32 ms 1884 KB Output is correct
4 Correct 32 ms 1880 KB Output is correct
5 Correct 34 ms 1884 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 1884 KB Output is correct
2 Correct 152 ms 1880 KB Output is correct
3 Correct 179 ms 1884 KB Output is correct
4 Correct 159 ms 1888 KB Output is correct
5 Correct 153 ms 1884 KB Output is correct