Submission #998517
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); if(j<i) dp[i%2][j] = 0; while(mx.size() && dp[(i+1)%2][mx.back()] <= dp[(i+1)%2][j]) mx.pop_back(); mx.push_back(j); } /* cout << i << ":"; rep(j,N) cout << dp[i%2][j] << ","; cout << endl; // */ } for(int j = 0; j < N; j++) { res = max(res, dp[(K-1)%2][j]); } cout << res << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | konjo |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1704 Byte |
Status | AC |
Exec Time | 551 ms |
Memory | 2560 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 | 51 ms | 512 KB |
subtask_1_3.txt | AC | 516 ms | 2560 KB |
subtask_1_4.txt | AC | 7 ms | 384 KB |
subtask_1_5.txt | AC | 51 ms | 2560 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 201 ms | 2560 KB |
subtask_1_8.txt | AC | 518 ms | 2560 KB |
subtask_1_9.txt | AC | 4 ms | 256 KB |
subtask_2_1.txt | AC | 2 ms | 256 KB |
subtask_2_2.txt | AC | 2 ms | 256 KB |
subtask_2_3.txt | AC | 2 ms | 256 KB |
subtask_2_4.txt | AC | 2 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 | 2 ms | 256 KB |
subtask_2_8.txt | AC | 2 ms | 256 KB |
subtask_2_9.txt | AC | 2 ms | 256 KB |
subtask_3_1.txt | AC | 90 ms | 2560 KB |
subtask_3_2.txt | AC | 91 ms | 2560 KB |
subtask_3_3.txt | AC | 88 ms | 2560 KB |
subtask_3_4.txt | AC | 73 ms | 2176 KB |
subtask_3_5.txt | AC | 6 ms | 384 KB |
subtask_3_6.txt | AC | 68 ms | 2560 KB |
subtask_3_7.txt | AC | 90 ms | 2560 KB |
subtask_3_8.txt | AC | 11 ms | 512 KB |
subtask_3_9.txt | AC | 93 ms | 2560 KB |
subtask_4_1.txt | AC | 519 ms | 2560 KB |
subtask_4_10.txt | AC | 459 ms | 2560 KB |
subtask_4_11.txt | AC | 551 ms | 2560 KB |
subtask_4_12.txt | AC | 550 ms | 2560 KB |
subtask_4_13.txt | AC | 550 ms | 2560 KB |
subtask_4_2.txt | AC | 541 ms | 2560 KB |
subtask_4_3.txt | AC | 518 ms | 2560 KB |
subtask_4_4.txt | AC | 519 ms | 2560 KB |
subtask_4_5.txt | AC | 443 ms | 2560 KB |
subtask_4_6.txt | AC | 79 ms | 2560 KB |
subtask_4_7.txt | AC | 304 ms | 2560 KB |
subtask_4_8.txt | AC | 509 ms | 2560 KB |
subtask_4_9.txt | AC | 256 ms | 2560 KB |