Submission #3667105


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <chrono>
using namespace std;

int main() {
	int N;
	cin >> N;
	string s;
	cin >> s;
	int Q;
	cin >> Q;
	vector<int> vk;
	vector<int> va;
	for (int i = 0; i != Q; ++i) {
		int k;
		cin >> k;
		vk.push_back(k - 1);
		va.push_back(0);
	}
	for (int i = 0; i != Q; ++i) {
		int d = 0, m = 0, dm = 0;
		for (int j = 0; j != vk[i]; ++j) {
			if (s[j] == 'C') va[i] += dm;
			else if (s[j] == 'D') ++d;
			else if (s[j] == 'M') {
				++m;
				dm += d;
			}
		}
		for (int j = 0; j + vk[i] < N; ++j) {
			if (s[j + vk[i]] == 'C') va[i] += dm;
			else if (s[j + vk[i]] == 'D') ++d;			
			else if (s[j + vk[i]] == 'M') {
				++m;
				dm += d;
			}

			if (s[j] == 'D') {
				--d;
				dm -= m;
			}
			else if (s[j] == 'M') --m;

		}
	}
	for (auto a : va) {
		cout << a << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task C - k-DMC
User taku0728
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1077 Byte
Status
Exec Time 798 ms
Memory 1412 KB

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 600 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 758 ms 1412 KB
dmc-dmc-01 786 ms 1412 KB
dmc-dmc-02 746 ms 1412 KB
dmc-dmc-03 768 ms 1412 KB
dmc-dmc-04 798 ms 1412 KB
dmc-large-00 284 ms 1412 KB
dmc-large-01 288 ms 1412 KB
dmc-large-02 290 ms 1412 KB
dmc-large-03 280 ms 1412 KB
dmc-large-04 289 ms 1412 KB
dmc-random-00 252 ms 1412 KB
dmc-random-01 200 ms 1412 KB
dmc-random-02 165 ms 1412 KB
dmc-random-03 137 ms 1412 KB
dmc-random-04 108 ms 1412 KB
dmc-special-00 212 ms 1412 KB
dmc-special-01 268 ms 1412 KB
dmc-special-02 265 ms 1412 KB
dmc-special-03 214 ms 1412 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB
sample_04 1 ms 256 KB