Submission #3639359
Source Code Expand
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (ll i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr << #x << ": " << (x) << endl
#define debug2(x, y) cerr << #x << ": " << (x) << " " << #y << ": " << y << endl;
#define int long long
using namespace std;
using II = pair<int, int>;
using VII = vector<II>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
template <class T = int> inline T in() { T x; cin >> x; return x; }
template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { int n = d.size(); REP (i, n) s << d[i] << " "; return s; }
template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& dd) { for (vector<T> d: dd) s << d << endl; return s; }
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
const int MOD = 1e9 + 7;
template <class T = int>
class SegTree {
using VT = vector<T>;
int orig_n;
// k番目のノードの[l, r)について[a, b)を求める
T query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) { return UNIT; }
if (a <= l && r <= b) { return dat[k]; }
T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return f(vl, vr);
}
public:
int N;
VT dat;
function<T(T, T)> f;
T UNIT;
SegTree() {}
SegTree(int n, function<T(T, T)> f_, const T unit) : orig_n(n), f(f_), UNIT(unit) {
for (N = 1; N < n; N *= 2);
dat = VT(2 * N - 1, UNIT);
}
SegTree(const VT& a, function<T(T, T)> f_ = [](int a, int b) { return min(a, b); }, T unit = 1e15)
: orig_n(a.size()), f(f_), UNIT(unit) {
for (N = 1; N < a.size(); N *= 2);
dat = VT(2 * N - 1);
REP (i, a.size()) {
dat[N - 1 + i] = a[i];
}
for (int k = N - 2; k >= 0; k--) {
dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
}
}
// k番目をaに
void update(int k, int a) {
k += N - 1;
dat[k] = a;
while (k > 0) {
k = (k - 1) / 2;
dat[k] = f(dat[2 * k + 1], dat[2 * k + 2]);
}
}
// [a, b)でのクエリ
T query(int a, int b) {
assert(0 <= a && a < b && b <= orig_n);
return query(a, b, 0, 0, N);
}
};
template <class T = int>
vector<T> slide_min(const vector<T>& a, int w, function<bool(T, T)> cmp = less<T>()) {
int n = a.size();
vector<T> ret(n);
deque<T> dq;
REP (i, n) {
while (!dq.empty() && !cmp(a[dq.back()], a[i])) {
dq.pop_back();
}
dq.push_back(i);
while (dq.front() <= i - w) {
dq.pop_front();
}
ret[i] = dq.front();
}
return ret;
}
signed main() {
int N, M, K; cin >> N >> M >> K;
VI A(N);
REP (i, N) cin >> A[i];
VVI dp(K + 1, VI(N + 1, 0));
REPI (i, 1, K + 1) {
dp[i][0] = -1;
}
VVI mas(K + 1, VI(N + 1));
REPI (i, 1, K + 1) {
REPI (j, 1, N + 1) {
dp[i][j] = dp[i - 1][mas[i - 1][j - 1]] + i * A[j - 1];
}
// スライド最大値
mas[i] = slide_min<int>(dp[i], K, greater<int>());
}
int ans = 0;
REP (j, N + 1) {
ans = max(ans, dp[K][j]);
}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
knshnb |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3606 Byte |
Status |
WA |
Exec Time |
829 ms |
Memory |
472944 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 |
80 ms |
47488 KB |
subtask_1_3.txt |
WA |
815 ms |
472944 KB |
subtask_1_4.txt |
WA |
6 ms |
2944 KB |
subtask_1_5.txt |
WA |
25 ms |
11248 KB |
subtask_1_6.txt |
WA |
2 ms |
896 KB |
subtask_1_7.txt |
WA |
282 ms |
159984 KB |
subtask_1_8.txt |
WA |
814 ms |
472944 KB |
subtask_1_9.txt |
WA |
4 ms |
2688 KB |
subtask_2_1.txt |
WA |
1 ms |
384 KB |
subtask_2_2.txt |
AC |
1 ms |
384 KB |
subtask_2_3.txt |
WA |
1 ms |
384 KB |
subtask_2_4.txt |
AC |
1 ms |
384 KB |
subtask_2_5.txt |
WA |
1 ms |
256 KB |
subtask_2_6.txt |
WA |
1 ms |
256 KB |
subtask_2_7.txt |
WA |
1 ms |
384 KB |
subtask_2_8.txt |
WA |
1 ms |
384 KB |
subtask_2_9.txt |
WA |
1 ms |
384 KB |
subtask_3_1.txt |
WA |
94 ms |
50416 KB |
subtask_3_2.txt |
WA |
94 ms |
50416 KB |
subtask_3_3.txt |
WA |
91 ms |
48752 KB |
subtask_3_4.txt |
WA |
75 ms |
40332 KB |
subtask_3_5.txt |
WA |
6 ms |
2816 KB |
subtask_3_6.txt |
WA |
53 ms |
26864 KB |
subtask_3_7.txt |
WA |
94 ms |
50416 KB |
subtask_3_8.txt |
WA |
10 ms |
5248 KB |
subtask_3_9.txt |
WA |
94 ms |
50416 KB |
subtask_4_1.txt |
WA |
817 ms |
472944 KB |
subtask_4_10.txt |
WA |
818 ms |
472944 KB |
subtask_4_11.txt |
WA |
816 ms |
472944 KB |
subtask_4_12.txt |
WA |
818 ms |
472944 KB |
subtask_4_13.txt |
WA |
816 ms |
472944 KB |
subtask_4_2.txt |
WA |
815 ms |
472944 KB |
subtask_4_3.txt |
WA |
815 ms |
472944 KB |
subtask_4_4.txt |
WA |
829 ms |
472944 KB |
subtask_4_5.txt |
WA |
692 ms |
401008 KB |
subtask_4_6.txt |
WA |
76 ms |
39408 KB |
subtask_4_7.txt |
WA |
437 ms |
250736 KB |
subtask_4_8.txt |
WA |
803 ms |
466300 KB |
subtask_4_9.txt |
WA |
368 ms |
210032 KB |