oj.uz

답안 #219522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219522 2020-04-05T13:21:04 Z Haunted_Cpp Relativnost (COCI15_relativnost) C++17
42 / 140
 644 ms 1152 KB 
#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 = 10007;
const int N = 1e3 + 5;
const int C = 20 + 5;

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;
  while (q--) {
    int cliente, nova_cor, nova_incolor;
    cin >> cliente >> nova_cor >> nova_incolor;
    --cliente;
    cor[cliente] = nova_cor % MOD;
    incolor[cliente] = nova_incolor % MOD;
    memset (dp, -1, sizeof(dp));
    cout << solve () << '\n';
  }
  return 0;
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 570 ms 632 KB Output is correct
2 Correct 644 ms 512 KB Output is correct
3 Correct 451 ms 512 KB Output is correct
4 Runtime error 11 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 9 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 10 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 11 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 9 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 9 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 10 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)