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 |
|
|
|
|
|
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 |