Submission #998208
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <sstream> #include <utility> #include <set> #include <map> #include <queue> #include <stack> #include <algorithm> #include <istream> #include <ostream> #include <cstdlib> #include <cmath> #include <cstdio> using namespace std; #define fi first #define se second #define mkp make_pair #define all(x) (x).begin(), (x).end() #define pb push_back #define rep(i,n) for(ll i=0; i < (n); ++i) #define rrep(i,n) for(ll i=((n)-1); i >= 0; --i) #define OPLT(T) bool operator<(const T & lop_, const T & rop_) #define OPEQ(T) bool operator==(const T & lop_, const T & rop_) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; //istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; }; //ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; }; ll dp[2][100100]; int main() { ll N, M, K; ll res = 0; cin >> N >> M >> K; vector<ll> A(N); rep(i,N) cin >> A[i]; rep(i,K) { deque<ll> mx; rep(j,N) { while(mx.size() && mx.front() < j-M) mx.pop_front(); ll m; if(mx.size() == 0) { m = 0; } else { m = dp[(i+1)%2][mx.front()]; } //cout << i <<"," << j << "," << m << endl; dp[i%2][j] = m + A[j] * (i+1); res = max(res, dp[i%2][j]); while(mx.size() && dp[(i+1)%2][mx.back()] <= dp[(i+1)%2][j]) mx.pop_back(); mx.push_back(j); } } cout << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | konjo |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1563 Byte |
Status | WA |
Exec Time | 568 ms |
Memory | 2688 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, 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 | 3 ms | 256 KB |
sample_2.txt | AC | 3 ms | 256 KB |
sample_3.txt | AC | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 55 ms | 512 KB |
subtask_1_3.txt | AC | 544 ms | 2560 KB |
subtask_1_4.txt | AC | 7 ms | 384 KB |
subtask_1_5.txt | AC | 52 ms | 2560 KB |
subtask_1_6.txt | WA | 3 ms | 256 KB |
subtask_1_7.txt | AC | 211 ms | 2560 KB |
subtask_1_8.txt | AC | 545 ms | 2560 KB |
subtask_1_9.txt | WA | 4 ms | 256 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 | WA | 3 ms | 256 KB |
subtask_2_6.txt | WA | 3 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 | 94 ms | 2688 KB |
subtask_3_2.txt | AC | 94 ms | 2560 KB |
subtask_3_3.txt | AC | 93 ms | 2560 KB |
subtask_3_4.txt | AC | 76 ms | 2176 KB |
subtask_3_5.txt | AC | 7 ms | 384 KB |
subtask_3_6.txt | AC | 71 ms | 2560 KB |
subtask_3_7.txt | AC | 94 ms | 2560 KB |
subtask_3_8.txt | AC | 12 ms | 512 KB |
subtask_3_9.txt | AC | 96 ms | 2688 KB |
subtask_4_1.txt | AC | 555 ms | 2560 KB |
subtask_4_10.txt | AC | 475 ms | 2560 KB |
subtask_4_11.txt | AC | 568 ms | 2560 KB |
subtask_4_12.txt | AC | 565 ms | 2560 KB |
subtask_4_13.txt | AC | 566 ms | 2560 KB |
subtask_4_2.txt | AC | 565 ms | 2560 KB |
subtask_4_3.txt | AC | 548 ms | 2560 KB |
subtask_4_4.txt | AC | 545 ms | 2560 KB |
subtask_4_5.txt | AC | 468 ms | 2560 KB |
subtask_4_6.txt | AC | 82 ms | 2560 KB |
subtask_4_7.txt | AC | 318 ms | 2560 KB |
subtask_4_8.txt | AC | 541 ms | 2560 KB |
subtask_4_9.txt | AC | 266 ms | 2560 KB |