Submission #3656965
Source Code Expand
/** * File : C.cpp * Author : Kazune Takahashi * Created : 11/24/2018, 8:48:33 PM * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <functional> #include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725)); #include <chrono> // std::chrono::system_clock::time_point start_time, end_time; // start = std::chrono::system_clock::now(); // double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count(); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; int N; string S; int Q; int k[100]; typedef tuple<int, ll> X; vector<X> D, C; int main() { cin >> N >> S >> Q; for (auto i = 0; i < Q; i++) { cin >> k[i]; } int m = 0; for (auto i = 0; i < N; i++) { if (S[i] == 'D') { D.push_back(X(i, m)); } else if (S[i] == 'M') { m++; } else if (S[i] == 'C') { C.push_back(X(i, m)); } } int D_size = D.size(); int C_size = C.size(); for (auto q = 0; q < Q; q++) { int K = k[q]; ll ans = 0; ll ind_d = 0; ll left = 0; ll right = 0; ll sum = 0; while (ind_d < D_size) { while (left < C_size && get<0>(C[left]) < get<0>(D[ind_d])) { sum -= get<1>(C[left]); left++; } while (right < C_size && get<0>(C[right]) - get<0>(D[ind_d]) < K) { sum += get<1>(C[right]); right++; } ans += sum - (right - left) * get<1>(D[ind_d]); ind_d++; } cout << ans << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - k-DMC |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 2238 Byte |
Status | AC |
Exec Time | 398 ms |
Memory | 19444 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 600 / 600 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | dmc-dmc-00, dmc-dmc-01, dmc-dmc-02, dmc-dmc-03, dmc-dmc-04, dmc-large-00, dmc-large-01, dmc-large-02, dmc-large-03, dmc-large-04, dmc-random-00, dmc-random-01, dmc-random-02, dmc-random-03, dmc-random-04, dmc-special-00, dmc-special-01, dmc-special-02, dmc-special-03, sample_01, sample_02, sample_03, sample_04 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
dmc-dmc-00 | AC | 389 ms | 17644 KB |
dmc-dmc-01 | AC | 395 ms | 17768 KB |
dmc-dmc-02 | AC | 383 ms | 14696 KB |
dmc-dmc-03 | AC | 392 ms | 18284 KB |
dmc-dmc-04 | AC | 398 ms | 14956 KB |
dmc-large-00 | AC | 77 ms | 3200 KB |
dmc-large-01 | AC | 77 ms | 3588 KB |
dmc-large-02 | AC | 78 ms | 3588 KB |
dmc-large-03 | AC | 76 ms | 3204 KB |
dmc-large-04 | AC | 77 ms | 3200 KB |
dmc-random-00 | AC | 68 ms | 3460 KB |
dmc-random-01 | AC | 54 ms | 2308 KB |
dmc-random-02 | AC | 54 ms | 3460 KB |
dmc-random-03 | AC | 47 ms | 2308 KB |
dmc-random-04 | AC | 37 ms | 1924 KB |
dmc-special-00 | AC | 76 ms | 19444 KB |
dmc-special-01 | AC | 128 ms | 17388 KB |
dmc-special-02 | AC | 179 ms | 18548 KB |
dmc-special-03 | AC | 74 ms | 19060 KB |
sample_01 | AC | 1 ms | 256 KB |
sample_02 | AC | 1 ms | 256 KB |
sample_03 | AC | 1 ms | 256 KB |
sample_04 | AC | 1 ms | 256 KB |