Submission #1674592


Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAX_N = 1 << 18;
const int def = 0;

struct MaxSegTree {
	int n;
	ll dat[2 * MAX_N - 1];
	void init(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) dat[i] = def;
	}

	void update(int k, ll a) {
		k += n - 1;
		dat[k] = a;
		while(k > 0) k = (k - 1) / 2, dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}

	ll query(int a, int b) { return query(a, b, 0, 0, n); }

	ll query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return def;
		if(a <= l && r <= b) return dat[k];
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr);
	}

	void show() {
		for(int i = 0; i < n; i++) cout << dat[i + n - 1] << " ";
		cout << endl;
	}
} st[2];

ll A[100000];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M, K;
	cin >> N >> M >> K;
	for(int i = 0; i < N; i++) {
		cin >> A[i];
	}
	st[0].init(N);
	st[1].init(N);

	MaxSegTree* cur = &st[0];
	MaxSegTree* nxt = &st[1];
	for(ll i = 1; i <= K; i++) {
		//cur->show();
		for(int j = 0; j < N; j++) {
			nxt->update(j, 0);
		}
		for(int j = i - 1; j < N; j++) {
			ll sum = A[j] * i;
			sum += cur->query(max(0, j - M), j);
			nxt->update(j, sum);
		}
		swap(cur, nxt);
	}

	//cur->show();
	cout << cur->query(0, N) << endl;
}

Submission Info

Submission Time
Task A - Struck Out
User femto16
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1550 Byte
Status TLE
Exec Time 2103 ms
Memory 8448 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 0 / 100 200 / 200 300 / 300 0 / 100
Status
AC × 3
AC × 8
TLE × 2
AC × 12
AC × 21
AC × 32
TLE × 14
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
subtask3 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt
Case Name Status Exec Time Memory
sample_1.txt AC 2 ms 2304 KB
sample_2.txt AC 2 ms 2304 KB
sample_3.txt AC 2 ms 2304 KB
subtask_1_1.txt AC 2 ms 2304 KB
subtask_1_2.txt AC 414 ms 2688 KB
subtask_1_3.txt TLE 2103 ms 8448 KB
subtask_1_4.txt AC 23 ms 2432 KB
subtask_1_5.txt AC 98 ms 8448 KB
subtask_1_6.txt AC 4 ms 2304 KB
subtask_1_7.txt AC 1697 ms 8448 KB
subtask_1_8.txt TLE 2103 ms 8448 KB
subtask_1_9.txt AC 10 ms 2304 KB
subtask_2_1.txt AC 3 ms 2304 KB
subtask_2_2.txt AC 2 ms 2304 KB
subtask_2_3.txt AC 3 ms 2304 KB
subtask_2_4.txt AC 2 ms 2304 KB
subtask_2_5.txt AC 2 ms 2304 KB
subtask_2_6.txt AC 2 ms 2304 KB
subtask_2_7.txt AC 3 ms 2304 KB
subtask_2_8.txt AC 3 ms 2304 KB
subtask_2_9.txt AC 2 ms 2304 KB
subtask_3_1.txt AC 626 ms 8448 KB
subtask_3_2.txt AC 768 ms 8448 KB
subtask_3_3.txt AC 748 ms 8448 KB
subtask_3_4.txt AC 625 ms 8320 KB
subtask_3_5.txt AC 22 ms 2432 KB
subtask_3_6.txt AC 359 ms 8448 KB
subtask_3_7.txt AC 550 ms 8448 KB
subtask_3_8.txt AC 65 ms 2688 KB
subtask_3_9.txt AC 703 ms 8448 KB
subtask_4_1.txt TLE 2103 ms 8448 KB
subtask_4_10.txt TLE 2103 ms 8448 KB
subtask_4_11.txt TLE 2103 ms 8448 KB
subtask_4_12.txt TLE 2103 ms 8448 KB
subtask_4_13.txt TLE 2103 ms 8448 KB
subtask_4_2.txt TLE 2103 ms 8448 KB
subtask_4_3.txt TLE 2103 ms 8448 KB
subtask_4_4.txt TLE 2103 ms 8448 KB
subtask_4_5.txt TLE 2103 ms 8448 KB
subtask_4_6.txt AC 400 ms 8448 KB
subtask_4_7.txt TLE 2103 ms 8448 KB
subtask_4_8.txt TLE 2103 ms 8448 KB
subtask_4_9.txt TLE 2103 ms 8448 KB