oj.uz

Submission #956382

# Submission time Handle Problem Language Result Execution time Memory
956382 2024-04-01T17:49:40 Z Ariadna Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 11348 KB 
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e4+7;

int ways(int i, int n, vector<int>& a, vector<int>& b, int colour, int c, int total) {
    if (i == n) {
        if (colour < c) return 0;
        return total % mod;
    }
    if (n-i < c-colour) return 0;
    return (ways(i+1, n, a, b, colour+1, c, (total * a[i]) % mod) + ways(i+1, n, a, b, colour, c, (total*b[i]) % mod)) % mod;
}

int main() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        a[i] %= mod;
        b[i] %= mod;
    }
    int ans = -1;
    int q;
    cin >> q;
    while (q--) {
        int i, a_, b_;
        cin >> i >> a_ >> b_; 
        --i;
        if (a_ != a[i] || b_ != b[i] || ans == -1) {
            a[i] = a_; b[i] = b_;
            ans = ways(0, n, a, b, 0, c, 1) % mod;
        }
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4010 ms 348 KB Time limit exceeded
2 Execution timed out 4019 ms 348 KB Time limit exceeded
3 Execution timed out 4064 ms 348 KB Time limit exceeded
4 Execution timed out 4054 ms 6996 KB Time limit exceeded
5 Execution timed out 4099 ms 11076 KB Time limit exceeded
6 Execution timed out 4037 ms 11348 KB Time limit exceeded
7 Execution timed out 4033 ms 8212 KB Time limit exceeded
8 Execution timed out 4022 ms 11344 KB Time limit exceeded
9 Execution timed out 4009 ms 9552 KB Time limit exceeded
10 Execution timed out 4061 ms 9032 KB Time limit exceeded