Submission #1674590
Source Code Expand
#include <iostream> #include <vector> using namespace std; using int64 = long long; const int64 MINIMIZE = -1145141919810364364LL; // 最大値を計算するSegment tree template <typename T> struct SegmentTree { const T DEFULT_VAL = MINIMIZE; vector<T> dat; int end; SegmentTree(vector<T>& d) { int n = d.size(); end = 1; while (end < n) end *= 2; dat.resize(2 * end - 1, DEFULT_VAL); for (int i = 0; i < d.size(); i++) { dat[i + end - 1] = d[i]; } for (int i = end - 2; i >= 0; i--) { dat[i] = max(dat[2 * i + 1], dat[2 * i + 2]); } } void update(int idx, T a) { int id = idx + end - 1; dat[id] = a; while (id > 0) { id = (id - 1) / 2; dat[id] = max(dat[id * 2 + 1], dat[id * 2 + 2]); } } T query(int lb, int ub) { return query(lb, ub, 0, 0, end); } T query(int lb, int ub, int id, int node_lb, int node_ub) { if (node_ub <= lb || ub <= node_lb) { return DEFULT_VAL; } if (lb <= node_lb && node_ub <= ub) { return dat[id]; } else { T vl = query(lb, ub, id * 2 + 1, node_lb, (node_lb + node_ub) / 2), vr = query(lb, ub, id * 2 + 2, (node_lb + node_ub) / 2, node_ub); return max(vl, vr); } } }; int main() { int N, M, K; cin >> N >> M >> K; vector<int64> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } vector<int64> elts(N + 1, MINIMIZE); elts[0] = 0; SegmentTree<int64> segtree(elts); for (int i = 0; i < K; i++) { for (int j = N; j >= i + 1; j--) { int64 res = segtree.query(max(i, j - M), j); segtree.update(j, res + A[j - 1] * (i + 1)); /* if (res + A[j - 1] * (i + 1) >= 0) { cerr << "i: " << i << " j: " << j << " result: " << res + A[j - 1] * (i + 1) << endl; } */ } } cout << segtree.query(0, N + 1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | myusa |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2170 Byte |
Status | WA |
Exec Time | 2104 ms |
Memory | 3840 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 200 | 0 / 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 | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 1 ms | 256 KB |
subtask_1_2.txt | AC | 408 ms | 640 KB |
subtask_1_3.txt | TLE | 2104 ms | 3840 KB |
subtask_1_4.txt | AC | 24 ms | 512 KB |
subtask_1_5.txt | AC | 126 ms | 3840 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 1764 ms | 3840 KB |
subtask_1_8.txt | TLE | 2104 ms | 3840 KB |
subtask_1_9.txt | AC | 11 ms | 256 KB |
subtask_2_1.txt | AC | 2 ms | 256 KB |
subtask_2_2.txt | WA | 2 ms | 256 KB |
subtask_2_3.txt | AC | 2 ms | 256 KB |
subtask_2_4.txt | AC | 2 ms | 256 KB |
subtask_2_5.txt | AC | 1 ms | 256 KB |
subtask_2_6.txt | AC | 1 ms | 256 KB |
subtask_2_7.txt | AC | 2 ms | 256 KB |
subtask_2_8.txt | AC | 2 ms | 256 KB |
subtask_2_9.txt | AC | 2 ms | 256 KB |
subtask_3_1.txt | AC | 594 ms | 3840 KB |
subtask_3_2.txt | AC | 627 ms | 3840 KB |
subtask_3_3.txt | AC | 624 ms | 3840 KB |
subtask_3_4.txt | WA | 502 ms | 3584 KB |
subtask_3_5.txt | AC | 23 ms | 512 KB |
subtask_3_6.txt | WA | 313 ms | 3840 KB |
subtask_3_7.txt | AC | 571 ms | 3840 KB |
subtask_3_8.txt | AC | 55 ms | 640 KB |
subtask_3_9.txt | WA | 585 ms | 3840 KB |
subtask_4_1.txt | TLE | 2103 ms | 3840 KB |
subtask_4_10.txt | TLE | 2103 ms | 3840 KB |
subtask_4_11.txt | TLE | 2104 ms | 3840 KB |
subtask_4_12.txt | TLE | 2104 ms | 3840 KB |
subtask_4_13.txt | TLE | 2104 ms | 3840 KB |
subtask_4_2.txt | TLE | 2103 ms | 3840 KB |
subtask_4_3.txt | TLE | 2104 ms | 3840 KB |
subtask_4_4.txt | TLE | 2103 ms | 3840 KB |
subtask_4_5.txt | TLE | 2103 ms | 3840 KB |
subtask_4_6.txt | AC | 440 ms | 3840 KB |
subtask_4_7.txt | TLE | 2104 ms | 3840 KB |
subtask_4_8.txt | TLE | 2103 ms | 3840 KB |
subtask_4_9.txt | TLE | 2103 ms | 3840 KB |