Submission #3640789
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> 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<int> 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) { int prv = dp[i - 1][mas[i - 1][j - 1]]; dp[i][j] = prv == -1 ? -1 : prv + i * A[j - 1]; } // スライド最大値 mas[i] = slide_min<int>(dp[i], K, greater<int>()); } cout << *max_element(ALL(dp[K])) << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | knshnb |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2225 Byte |
Status | WA |
Exec Time | 839 ms |
Memory | 474992 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 | 81 ms | 47488 KB |
subtask_1_3.txt | WA | 826 ms | 472944 KB |
subtask_1_4.txt | WA | 6 ms | 2944 KB |
subtask_1_5.txt | WA | 26 ms | 11248 KB |
subtask_1_6.txt | AC | 2 ms | 896 KB |
subtask_1_7.txt | WA | 288 ms | 159984 KB |
subtask_1_8.txt | WA | 830 ms | 472944 KB |
subtask_1_9.txt | AC | 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 | AC | 1 ms | 256 KB |
subtask_2_6.txt | AC | 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 | 95 ms | 50416 KB |
subtask_3_2.txt | WA | 96 ms | 50416 KB |
subtask_3_3.txt | WA | 92 ms | 48752 KB |
subtask_3_4.txt | WA | 77 ms | 40332 KB |
subtask_3_5.txt | WA | 6 ms | 2816 KB |
subtask_3_6.txt | WA | 54 ms | 26864 KB |
subtask_3_7.txt | WA | 96 ms | 50416 KB |
subtask_3_8.txt | WA | 11 ms | 5248 KB |
subtask_3_9.txt | WA | 96 ms | 50416 KB |
subtask_4_1.txt | WA | 829 ms | 472944 KB |
subtask_4_10.txt | WA | 826 ms | 472944 KB |
subtask_4_11.txt | WA | 828 ms | 472944 KB |
subtask_4_12.txt | WA | 839 ms | 472944 KB |
subtask_4_13.txt | WA | 827 ms | 472944 KB |
subtask_4_2.txt | WA | 827 ms | 472944 KB |
subtask_4_3.txt | WA | 828 ms | 474992 KB |
subtask_4_4.txt | WA | 834 ms | 472944 KB |
subtask_4_5.txt | WA | 702 ms | 401008 KB |
subtask_4_6.txt | WA | 76 ms | 39408 KB |
subtask_4_7.txt | WA | 443 ms | 250736 KB |
subtask_4_8.txt | WA | 812 ms | 466300 KB |
subtask_4_9.txt | WA | 375 ms | 210032 KB |