Submission #3659534


Source Code Expand

Copy
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

int D[1000001], C[1000001];
long long PSC[1000001], PSD[1000001], temp[1000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	TEST(freopen("debug.txt", "w", stderr));
	int N, Q, pd1, pd2, pc1, pc2;
	string s;
	cin >> N >> s >> Q;
	for (int i = 0; i < N; i++) {
		D[i + 1] = (s[i] == 'D') + D[i];
		C[i + 1] = (s[i] == 'C') + C[i];
		PSD[i + 1] = PSD[i] + D[i + 1];
		PSC[i + 1] = PSC[i] + C[i + 1];
	}
	s = 'A' + s;
	for (; Q; Q--) {
		int K;
		long long ans = 0;
		cin >> K;
		memset(temp, 0, sizeof(temp));
		for (int i = 1; i + K <= N; i++) {
			temp[i] = 1LL * D[i] * C[i + K] + temp[i - 1];
		}
		for (int i = 1; i <= N; i++) {
			if (s[i] == 'M') {
				ans += 1LL * D[i] * (PSC[i + K - 1] - PSC[i - 1]) + 1LL * C[i] * (PSD[i - 1] - PSD[max(i - K, 0)]) - 1LL * K*D[i] * C[i] - (temp[i - 1] - temp[max(i - K, 0)]);
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

Submission Info

Submission Time
Task C - k-DMC
User Lawali
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1154 Byte
Status
Exec Time 475 ms
Memory 32584 KB

Judge Result

Set Name All
Score / Max Score 0 / 600
Status
× 23
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 471 ms 32584 KB
dmc-dmc-01 471 ms 32584 KB
dmc-dmc-02 469 ms 32584 KB
dmc-dmc-03 469 ms 32584 KB
dmc-dmc-04 475 ms 32584 KB
dmc-large-00 328 ms 32584 KB
dmc-large-01 324 ms 32584 KB
dmc-large-02 330 ms 32584 KB
dmc-large-03 320 ms 32584 KB
dmc-large-04 339 ms 32584 KB
dmc-random-00 271 ms 32056 KB
dmc-random-01 214 ms 31848 KB
dmc-random-02 164 ms 32056 KB
dmc-random-03 145 ms 31864 KB
dmc-random-04 134 ms 31676 KB
dmc-special-00 165 ms 32584 KB
dmc-special-01 285 ms 32584 KB
dmc-special-02 155 ms 32584 KB
dmc-special-03 158 ms 32584 KB
sample_01 5 ms 14592 KB
sample_02 5 ms 14592 KB
sample_03 6 ms 14592 KB
sample_04 6 ms 14592 KB