Submission #219618

#	Time	Username	Problem	Language	Result	Execution time	Memory
219618		Haunted_Cpp	Relativnost (COCI15_relativnost)	C++17	42 / 140	326 ms	768 KiB

relativnost

    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <set>
    #include <map>
    #include <unordered_set>
    #include <unordered_map>
    #include <queue>
    #include <cassert>
    #include <string>
    #include <cstring>
    #include <bitset>
    #include <random>
    #include <chrono>
    #include <iomanip>
     
    /*
    #pragma GCC optimize ("Ofast")
    #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
    #pragma GCC optimize("unroll-loops")
    */
     
    #define FOR(i, a, b) for(int i = a; i < (int) b; i++)
    #define F0R(i, a) FOR (i, 0, a)
    #define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
    #define R0F(i, a) ROF(i, a, 0)
    #define GO(i, a) for (auto i : a)
     
    #define rsz resize
    #define eb emplace_back
    #define pb push_back
    #define sz(x) (int) x.size()
    #define all(x) x.begin(), x.end()
    #define rall(x) x.rbegin(), x.rend()
    #define f first
    #define s second
     
    using namespace std;
     
    typedef pair<int, int> pii;
    typedef vector<int> vi;
    typedef vector<pii> vpii;
    typedef vector<vi> vvi;
    typedef vector<vpii> vvpii;
    typedef long long i64;
    typedef vector<i64> vi64;
    typedef vector<vi64> vvi64;
    typedef pair<i64, i64> pi64;
    typedef vector<pi64> vpi64;
     
    const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
    const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
    const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};
     
    // 30 Pts - Dynamic Programming to count the ways O ( N * Q * C).
     
    const int MOD = 1e4 + 7;
    const int N = 1e3 + 1;
    const int C = 20 + 1;
     
    void add (int &a, int b) {
      a += b;
      if (a >= MOD) a -= MOD;
    }
     
    int mult (int a, int b) {
      int res = a * b;
      if (res >= MOD) res %= MOD;
      return res;
    }
     
    int n, c;
    int dp [N][C], cor [N], incolor[N];
     
    int solve (int p = 0, int has = 0) {
      if (p >= n) return (has >= c);
      int &res = dp[p][has];
      if (~res) return res;
      res = 0;
      add (res, mult (incolor[p], solve (p + 1, has)));
      add (res, mult (cor[p], solve (p + 1, min (20, has + 1))));
      return res;
    }
     
    int main () {
      ios::sync_with_stdio(0);
      cin.tie(0);
      cin >> n >> c;
      F0R (i, n) {
        cin >> cor[i];
        cor[i] %= MOD;
      }
      F0R (i, n) {
        cin >> incolor[i];
        incolor[i] %= MOD;
      }
      int q;
      cin >> q;
      memset (dp, -1, sizeof(dp));
      while (q--) {
        int cliente, nova_cor, nova_incolor;
        cin >> cliente >> nova_cor >> nova_incolor;
        --cliente;
        cor[cliente] = (nova_cor >= MOD ? nova_cor % MOD : nova_cor);
        incolor[cliente] = (nova_incolor >= MOD ? nova_incolor % MOD : nova_incolor);
        FOR (i, 0, cliente + 1) {
          F0R (j, C) {
            dp[i][j] = -1;
          }
        }
        cout << solve () << '\n';
      }
      return 0;
    }

• Subtask 1: 42 / 140