oj.uz

Submission #371252

# Submission time Handle Problem Language Result Execution time Memory
371252 2021-02-26T09:54:00 Z Atill83 Relativnost (COCI15_relativnost) C++14
56 / 140
 4000 ms 1604 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e4+7;
const int MAXN = (int) 1e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, c;
int a[MAXN], b[MAXN];

const int BS = 700;

int dp[MAXN][21];


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

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>c;

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

    for(int i = 0; i * BS < n; i++){
        dp[i][0] = 1;
        for(int j = i*BS; j < min((i + 1) * BS, n); j++){
            a[j] %= mod;
            b[j] %= mod;
            int a_cur = a[j], b_cur = b[j];
            
            dp[i][c] = (dp[i][c - 1] * a_cur % mod + dp[i][c] * (a_cur + b_cur) % mod) % mod;
            for(int l = c - 1; l > 0; l--){
                dp[i][l] = (dp[i][l - 1] * a_cur % mod + dp[i][l] * b_cur % mod) % mod;
            }

            dp[i][0] = dp[i][0] * b_cur % mod;
        }
    }
 
 
    int q;
    cin>>q;

    for(int i = 0; i < q; i++){
        int idx;
        cin>>idx;
        idx--;
        cin>>a[idx]>>b[idx];
        a[idx] %= mod;
        b[idx] %= mod;
        int block = idx / BS;
        for(int j = 0; j <= c; j++)
            dp[block][j] = 0;
        dp[block][0] = 1;
        for(int j = block*BS; j < min((block + 1) * BS, n); j++){
            int a_cur = a[j], b_cur = b[j];
            dp[block][c] = (dp[block][c - 1] * a_cur % mod + dp[block][c] * (a_cur + b_cur) % mod) % mod;
            for(int l = c - 1; l > 0; l--){
                dp[block][l] = (dp[block][l - 1] * a_cur % mod + dp[block][l] * b_cur % mod) % mod;
            }
            dp[block][0] = dp[block][0] * b_cur % mod;
        }


        vector<int> ans(c + 1, 0);
        ans[0] = 1;
        
        for(int i = 0; i*BS < n; i++){
            vector<int> nans(c + 1, 0);
            for(int l = c; l >= 0; l--){
                for(int j = c; j >= 0; j--){
                    nans[(min(c, l + j))] += ans[l] * dp[i][j] % mod; 
                    nans[(min(c, l + j))] %= mod; 
                }
            }
            ans = nans;
        }

        cout<<ans[c]<<endl;
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 512 KB Output is correct
2 Correct 55 ms 424 KB Output is correct
3 Correct 82 ms 364 KB Output is correct
4 Correct 3474 ms 1340 KB Output is correct
5 Execution timed out 4058 ms 1388 KB Time limit exceeded
6 Execution timed out 4099 ms 1308 KB Time limit exceeded
7 Execution timed out 4098 ms 1388 KB Time limit exceeded
8 Execution timed out 4059 ms 1604 KB Time limit exceeded
9 Execution timed out 4070 ms 1516 KB Time limit exceeded
10 Execution timed out 4050 ms 1260 KB Time limit exceeded