Submission #2936195
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <utility> #include <queue> #include <set> #include <map> #include <deque> #include <iomanip> #include <cstdio> using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define PB push_back #define inf 1000000007 #define rep(i,n) for(int i=0;i<(int)(n);++i) template <typename T> class SlideMin { public: vector<int> deq; vector<T> res; int n,k; SlideMin(vector<T> Array,int sz){ n = (int)Array.size(), k = sz; deq.resize(n), res.resize(n); int s = 0, t = 0; rep(i,n){ //iを追加した場合に添字deq[t-1]の値がa[i]以上のときdeqから削除されるまで採用されることはないので //最大値を取る場合は Array[deq[t-1]] <= Array[i] とする while(s < t && Array[deq[t-1]] <= Array[i]){ t--; } deq[t++] = i; res[i] = Array[deq[s]]; if(deq[s] == i-k+1){ s++; } } } }; int main(){ int n,k; ll m; cin >> n >> m >> k; vector<ll> v(n); rep(i,n){ cin >> v[i]; } vector<vector<ll> > dp(k+1,vector<ll>(n)); dp[1] = v; for(ll i=2;i<=k;i++){ SlideMin<ll> sm(dp[i-1],k); for(ll j=i;j<n;j++){ dp[i][j] = sm.res[j-1]+v[j]*i; } } ll mx = 0; rep(i,n){ mx = max(mx,dp[k][i]); } cout << mx << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | mtsd |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1715 Byte |
Status | WA |
Exec Time | 636 ms |
Memory | 239024 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 | WA | 1 ms | 256 KB |
subtask_1_2.txt | AC | 48 ms | 24064 KB |
subtask_1_3.txt | WA | 633 ms | 239024 KB |
subtask_1_4.txt | WA | 5 ms | 1664 KB |
subtask_1_5.txt | WA | 49 ms | 7720 KB |
subtask_1_6.txt | WA | 2 ms | 512 KB |
subtask_1_7.txt | WA | 237 ms | 82224 KB |
subtask_1_8.txt | WA | 633 ms | 239024 KB |
subtask_1_9.txt | WA | 3 ms | 1408 KB |
subtask_2_1.txt | WA | 1 ms | 384 KB |
subtask_2_2.txt | AC | 1 ms | 256 KB |
subtask_2_3.txt | WA | 1 ms | 256 KB |
subtask_2_4.txt | AC | 1 ms | 256 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 | 256 KB |
subtask_3_1.txt | WA | 99 ms | 27344 KB |
subtask_3_2.txt | WA | 99 ms | 27340 KB |
subtask_3_3.txt | WA | 97 ms | 26556 KB |
subtask_3_4.txt | WA | 79 ms | 21960 KB |
subtask_3_5.txt | WA | 5 ms | 1536 KB |
subtask_3_6.txt | WA | 69 ms | 15568 KB |
subtask_3_7.txt | WA | 99 ms | 27344 KB |
subtask_3_8.txt | WA | 9 ms | 2944 KB |
subtask_3_9.txt | WA | 99 ms | 27340 KB |
subtask_4_1.txt | WA | 634 ms | 239024 KB |
subtask_4_10.txt | WA | 632 ms | 239024 KB |
subtask_4_11.txt | WA | 636 ms | 239024 KB |
subtask_4_12.txt | WA | 633 ms | 239024 KB |
subtask_4_13.txt | WA | 635 ms | 239024 KB |
subtask_4_2.txt | WA | 635 ms | 239024 KB |
subtask_4_3.txt | WA | 633 ms | 239024 KB |
subtask_4_4.txt | WA | 635 ms | 239024 KB |
subtask_4_5.txt | WA | 540 ms | 202960 KB |
subtask_4_6.txt | WA | 86 ms | 21844 KB |
subtask_4_7.txt | WA | 352 ms | 127696 KB |
subtask_4_8.txt | WA | 626 ms | 235460 KB |
subtask_4_9.txt | WA | 301 ms | 107280 KB |