oj.uz

답안 #165264

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
165264 2019-11-26T10:09:36 Z egekabas Relativnost (COCI15_relativnost) C++14
42 / 140
 693 ms 4088 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n, c, q;
ll sq = 1000009;
ll a[100009];
ll b[100009];
ll tmp[1009][25];
ll sqdp[1009][25];
ll sqval[1009][25];
ll mod = 10007;
void upd(ll idx){
    tmp[0][0] = b[idx*sq];
    tmp[0][1] = a[idx*sq];
    ll i;
    for(i = 1; i < sq && idx*sq+i < n; ++i){
        tmp[i][0] = b[idx*sq+i]*tmp[i-1][0]%mod;
        for(ll j = 1; j <= c; ++j){
            tmp[i][j] = b[idx*sq+i]*tmp[i-1][j]%mod;
            tmp[i][j] += a[idx*sq+i]*tmp[i-1][j-1]%mod;
            tmp[i][j] %= mod;
        }
        tmp[i][c] += a[idx*sq+i]*tmp[i-1][c]%mod;
        tmp[i][c] %= mod;
    }
    for(ll j = 0; j <= c; ++j){
        sqval[idx][j] = tmp[i-1][j];
//        cout << j << " " << tmp[i-1][j] << "\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> c;
    for(ll i = 0; i < n; ++i)
        cin >> a[i];
    for(ll i = 0; i < n; ++i)
        cin >> b[i];
    cin >> q;
    for(ll i = 0; i < n; i += sq)
        upd(i/sq);
    
    while(q--){
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        --t1;
        a[t1] = t2;
        b[t1] = t3;
        upd(t1/sq);
        //if(t1/sq == 0)
            for(ll j = 0; j <= c; ++j)
                sqdp[0][j] = sqval[0][j];
        for(ll i = 1; i*sq < n; ++i){
            for(ll j = 0; j < c; ++j)
                for(ll k = 0; k <= j; ++k){
            sqdp[i][j] += (sqdp[i-1][k]*sqval[i][j-k])%mod;
            sqdp[i][j] %= mod;
                }
            for(ll j = 0; j <= c; ++j)
                for(ll k = c-j; k <= c; ++k){
                    sqdp[i][c] += sqdp[i-1][j]*sqval[i][k]%mod;
                    sqdp[i][c] %= mod;
                }
        }
        cout << sqdp[(n-1)/sq][c] << "\n";
    }
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 503 ms 596 KB Output is correct
2 Correct 645 ms 576 KB Output is correct
3 Correct 693 ms 680 KB Output is correct
4 Runtime error 24 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 35 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 39 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 29 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 34 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 30 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 34 ms 4060 KB Execution killed with signal 11 (could be triggered by violating memory limits)