oj.uz

Submission #251657

# Submission time Handle Problem Language Result Execution time Memory
251657 2020-07-22T06:33:34 Z VEGAnn Relativnost (COCI15_relativnost) C++14
42 / 140
 4000 ms 10872 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100100;
const int C = 22;
const int md = 10007;
int n, c, a[N], b[N], f[N][C];

int mult(int x, int y) { return (x * y) % md; }

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt","r",stdin); // freopen("output.txt","w",stdout);
#else
//    freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
#endif

    cin >> n >> c;

    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    int qq; cin >> qq;

    for (; qq; qq--){
        int ps, an, bn; cin >> ps >> an >> bn;

        a[ps] = an;
        b[ps] = bn;

        for (int i = 0; i <= n; i++)
        for (int j = 0; j <= c; j++)
            f[i][j] = 0;

        f[0][0] = 1;

        for (int i = 0; i < n; i++)
        for (int j = 0; j <= c; j++){
            if (f[i][j] == 0) continue;

            SUM(f[i + 1][min(j + 1, c)], mult(f[i][j], a[i + 1]));
            SUM(f[i + 1][j], mult(f[i][j], b[i + 1]));
        }

        cout << f[n][c] << '\n';
    }

    return 0;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 512 KB Output is correct
2 Correct 111 ms 504 KB Output is correct
3 Correct 129 ms 484 KB Output is correct
4 Execution timed out 4081 ms 6648 KB Time limit exceeded
5 Execution timed out 4091 ms 10488 KB Time limit exceeded
6 Execution timed out 4078 ms 10872 KB Time limit exceeded
7 Execution timed out 4085 ms 7736 KB Time limit exceeded
8 Execution timed out 4086 ms 10816 KB Time limit exceeded
9 Execution timed out 4081 ms 9080 KB Time limit exceeded
10 Execution timed out 4066 ms 8548 KB Time limit exceeded