Submission #2272755
Source Code Expand
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////
struct slidemax {
ll que[MAX_N];
int s, e;
void init() {
s = 0; e = 0;
memset(que, 0, sizeof(que));
}
void add(ll x) {
while(s < e && que[e - 1] < x) e--;
que[e++] = x;
}
void remove(ll x) {
if(s < e && que[s] == x) s++;
}
bool empty() {
return s == e;
}
ll get() {
if(s == e) return -linf;
else return que[s];
}
void show() {
debug(vi(que + s, que + e));
}
};
int N, M, K;
ll dp[2][100010];
ll A[100010];
slidemax que;
void solve() {
cin >> N >> M >> K;
rep(i, 0, N) cin >> A[i];
int now = 0, nex = 1;
rep(i, 0, N) dp[now][i] = A[i];
rep(k, 2, K + 1) {
// debug(vl(dp[now], dp[now] + N));
que.init();
rep(i, 0, k - 1) {
que.add(dp[now][i]);
if(i >= M) que.remove(dp[now][i - M]);
}
// que.show();
rep(i, 0, k - 1) dp[nex][i] = -linf;
rep(i, k - 1, N) {
dp[nex][i] = que.get();
dp[nex][i] += A[i] * k;
que.add(dp[now][i]);
if(i >= M) que.remove(dp[now][i - M]);
}
swap(now, nex);
}
ll res = 0;
rep(i, 0, N) {
MAX(res, dp[now][i]);
}
cout << res << "\n";
}
int main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(0);
#endif
cout << fixed;
cout.precision(20);
srand((unsigned int)time(NULL));
#ifdef LOCAL
//freopen("in.txt", "wt", stdout); //for tester
freopen("in.txt", "rt", stdin);
#endif
solve();
#ifdef LOCAL
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
omochana2 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3009 Byte |
Status |
AC |
Exec Time |
365 ms |
Memory |
4224 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, 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 |
1792 KB |
sample_2.txt |
AC |
2 ms |
1792 KB |
sample_3.txt |
AC |
2 ms |
1792 KB |
subtask_1_1.txt |
AC |
4 ms |
1792 KB |
subtask_1_2.txt |
AC |
53 ms |
2048 KB |
subtask_1_3.txt |
AC |
345 ms |
4224 KB |
subtask_1_4.txt |
AC |
6 ms |
1920 KB |
subtask_1_5.txt |
AC |
17 ms |
4224 KB |
subtask_1_6.txt |
AC |
17 ms |
1792 KB |
subtask_1_7.txt |
AC |
123 ms |
4224 KB |
subtask_1_8.txt |
AC |
346 ms |
4224 KB |
subtask_1_9.txt |
AC |
25 ms |
1792 KB |
subtask_2_1.txt |
AC |
4 ms |
1792 KB |
subtask_2_2.txt |
AC |
3 ms |
1792 KB |
subtask_2_3.txt |
AC |
3 ms |
1792 KB |
subtask_2_4.txt |
AC |
4 ms |
1792 KB |
subtask_2_5.txt |
AC |
4 ms |
1792 KB |
subtask_2_6.txt |
AC |
4 ms |
1792 KB |
subtask_2_7.txt |
AC |
4 ms |
1792 KB |
subtask_2_8.txt |
AC |
4 ms |
1792 KB |
subtask_2_9.txt |
AC |
3 ms |
1792 KB |
subtask_3_1.txt |
AC |
45 ms |
4224 KB |
subtask_3_2.txt |
AC |
46 ms |
4224 KB |
subtask_3_3.txt |
AC |
44 ms |
4224 KB |
subtask_3_4.txt |
AC |
37 ms |
3712 KB |
subtask_3_5.txt |
AC |
6 ms |
1920 KB |
subtask_3_6.txt |
AC |
29 ms |
4224 KB |
subtask_3_7.txt |
AC |
44 ms |
4224 KB |
subtask_3_8.txt |
AC |
8 ms |
2048 KB |
subtask_3_9.txt |
AC |
46 ms |
4224 KB |
subtask_4_1.txt |
AC |
355 ms |
4224 KB |
subtask_4_10.txt |
AC |
279 ms |
4224 KB |
subtask_4_11.txt |
AC |
365 ms |
4224 KB |
subtask_4_12.txt |
AC |
363 ms |
4224 KB |
subtask_4_13.txt |
AC |
360 ms |
4224 KB |
subtask_4_2.txt |
AC |
357 ms |
4224 KB |
subtask_4_3.txt |
AC |
346 ms |
4224 KB |
subtask_4_4.txt |
AC |
356 ms |
4224 KB |
subtask_4_5.txt |
AC |
303 ms |
4224 KB |
subtask_4_6.txt |
AC |
37 ms |
4224 KB |
subtask_4_7.txt |
AC |
193 ms |
4224 KB |
subtask_4_8.txt |
AC |
351 ms |
4096 KB |
subtask_4_9.txt |
AC |
163 ms |
4224 KB |