Submission #1022602
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T>
struct sliding_window {
deque<pair<int, T> > data;
function<bool (T const &, T const &)> cmp;
template <typename F>
sliding_window(F a_lt) : cmp(a_lt) {}
T front() { return data.front().second; } // smallest
void push_back(int i, T a) { while (not data.empty() and cmp(a, data.back().second)) data.pop_back(); data.emplace_back(i, a); }
void pop_front(int i) { if (data.front().first == i) data.pop_front(); }
void push_front(int i, T a) { if (data.empty() or not cmp(data.front().second, a)) data.emplace_front(i, a); }
};
const ll inf = ll(1e18)+9;
int main() {
int n, m, k; cin >> n >> m >> k;
vector<int> a(n); repeat (i,n) cin >> a[i];
if (n == m) {
vector<vector<ll> > dp = vectors(k, n, - inf);
repeat (j,n) dp[0][j] = a[j];
repeat (i,k-1) {
repeat (j,n-1) setmax(dp[i][j+1], dp[i][j]);
repeat (j,n) {
if (j-1 >= 0) {
setmax(dp[i+1][j], dp[i][j-1] + (i+2) *(ll) a[j]);
}
}
}
ll ans = *whole(max_element, dp[k-1]);
cout << ans << endl;
} else {
vector<vector<ll> > dp = vectors(k, n, - inf);
repeat (j,n) dp[0][j] = a[j];
repeat (i,k-1) {
sliding_window<ll> rmq( (greater<ll>()) );
rmq.push_back(-1, - inf);
repeat (j,n) {
if (j-m-1 >= -1) rmq.pop_front(j-m-1);
setmax(dp[i+1][j], rmq.front() + (i+2) *(ll) a[j]);
rmq.push_back(j, dp[i][j]);
}
}
ll ans = *whole(max_element, dp[k-1]);
cout << ans << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
kimiyuki |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2389 Byte |
Status |
AC |
Exec Time |
934 ms |
Memory |
236672 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
subtask3 |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
200 / 200 |
300 / 300 |
100 / 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, 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 |
256 KB |
sample_2.txt |
AC |
2 ms |
256 KB |
sample_3.txt |
AC |
2 ms |
256 KB |
subtask_1_1.txt |
AC |
2 ms |
256 KB |
subtask_1_2.txt |
AC |
42 ms |
23808 KB |
subtask_1_3.txt |
AC |
399 ms |
236672 KB |
subtask_1_4.txt |
AC |
6 ms |
1536 KB |
subtask_1_5.txt |
AC |
48 ms |
5376 KB |
subtask_1_6.txt |
AC |
3 ms |
512 KB |
subtask_1_7.txt |
AC |
163 ms |
79872 KB |
subtask_1_8.txt |
AC |
403 ms |
236672 KB |
subtask_1_9.txt |
AC |
4 ms |
1408 KB |
subtask_2_1.txt |
AC |
3 ms |
256 KB |
subtask_2_2.txt |
AC |
3 ms |
256 KB |
subtask_2_3.txt |
AC |
3 ms |
256 KB |
subtask_2_4.txt |
AC |
3 ms |
256 KB |
subtask_2_5.txt |
AC |
2 ms |
256 KB |
subtask_2_6.txt |
AC |
2 ms |
256 KB |
subtask_2_7.txt |
AC |
3 ms |
256 KB |
subtask_2_8.txt |
AC |
3 ms |
256 KB |
subtask_2_9.txt |
AC |
3 ms |
256 KB |
subtask_3_1.txt |
AC |
125 ms |
24960 KB |
subtask_3_2.txt |
AC |
126 ms |
24960 KB |
subtask_3_3.txt |
AC |
122 ms |
24192 KB |
subtask_3_4.txt |
AC |
101 ms |
19968 KB |
subtask_3_5.txt |
AC |
8 ms |
1536 KB |
subtask_3_6.txt |
AC |
85 ms |
13184 KB |
subtask_3_7.txt |
AC |
125 ms |
24960 KB |
subtask_3_8.txt |
AC |
14 ms |
2688 KB |
subtask_3_9.txt |
AC |
130 ms |
24960 KB |
subtask_4_1.txt |
AC |
876 ms |
236672 KB |
subtask_4_10.txt |
AC |
811 ms |
236672 KB |
subtask_4_11.txt |
AC |
934 ms |
236672 KB |
subtask_4_12.txt |
AC |
933 ms |
236672 KB |
subtask_4_13.txt |
AC |
931 ms |
236672 KB |
subtask_4_2.txt |
AC |
920 ms |
236672 KB |
subtask_4_3.txt |
AC |
880 ms |
236672 KB |
subtask_4_4.txt |
AC |
879 ms |
236672 KB |
subtask_4_5.txt |
AC |
750 ms |
200576 KB |
subtask_4_6.txt |
AC |
106 ms |
19456 KB |
subtask_4_7.txt |
AC |
505 ms |
125312 KB |
subtask_4_8.txt |
AC |
863 ms |
232960 KB |
subtask_4_9.txt |
AC |
423 ms |
104960 KB |