Submission #997863
Source Code Expand
#ifdef DEBUG #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; mt19937 mrand(random_device{} ()); int rnd(int x) { return mrand() % x; } typedef long double ld; typedef long long ll; #ifdef DEBUG #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #else #define eprintf(...) ; #endif #define pb push_back #define mp make_pair #define sz(x) ((int) (x).size()) #define TASK "text" const int inf = (int) 1.01e9; const ld eps = 1e-9; const ld pi = acos((ld) -1.0); void precalc() { } const int maxn = (int) 1e5 + 10; int a[maxn]; int n, m, k; int read() { if (scanf("%d%d%d", &n, &m, &k) < 3) { return 0; } for (int i = 0; i < n; ++i) { scanf("%d", a + i); } return 1; } long long infll = (long long) 1e18; long long dp[maxn]; void solve() { for (int i = 0; i < n; ++i) { dp[i] = a[i]; } vector<pair<long long, int> > st; for (int iter = 1; iter < k; ++iter) { st.clear(); int left = 0; for (int i = 0; i < n; ++i) { long long d0 = dp[i]; dp[i] = sz(st) == left ? -infll : (st[left].first + (long long) a[i] * (iter + 1)); //eprintf("%lld%c", dp[i], " \n"[i == n - 1]); if (left < sz(st) && st[left].second < i - m) { ++left; } if (d0 > -infll) { while (sz(st) > left && st.back().first <= d0) { st.pop_back(); } st.pb(mp(d0, i)); } } } printf("%lld\n", *max_element(dp, dp + n)); } int main() { precalc(); #ifdef LOCAL freopen(TASK ".out", "w", stdout); assert(freopen(TASK ".in", "r", stdin)); #endif while (1) { if (!read()) { break; } solve(); #ifdef DEBUG eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC); #endif } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | XraY |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1867 Byte |
Status | WA |
Exec Time | 371 ms |
Memory | 2552 KB |
Compile Error
./Main.cpp: In function ‘int read()’: ./Main.cpp:46:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", a + i); ^
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 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 | 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 | 36 ms | 384 KB |
subtask_1_3.txt | AC | 358 ms | 1408 KB |
subtask_1_4.txt | AC | 5 ms | 256 KB |
subtask_1_5.txt | AC | 19 ms | 1408 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 129 ms | 1408 KB |
subtask_1_8.txt | AC | 358 ms | 1408 KB |
subtask_1_9.txt | AC | 3 ms | 256 KB |
subtask_2_1.txt | AC | 3 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 | 48 ms | 1408 KB |
subtask_3_2.txt | AC | 48 ms | 1408 KB |
subtask_3_3.txt | AC | 47 ms | 1408 KB |
subtask_3_4.txt | AC | 39 ms | 1152 KB |
subtask_3_5.txt | AC | 5 ms | 256 KB |
subtask_3_6.txt | AC | 31 ms | 1408 KB |
subtask_3_7.txt | AC | 48 ms | 1408 KB |
subtask_3_8.txt | AC | 7 ms | 384 KB |
subtask_3_9.txt | AC | 48 ms | 1408 KB |
subtask_4_1.txt | AC | 359 ms | 1408 KB |
subtask_4_10.txt | WA | 285 ms | 2552 KB |
subtask_4_11.txt | WA | 371 ms | 1792 KB |
subtask_4_12.txt | WA | 367 ms | 1664 KB |
subtask_4_13.txt | WA | 363 ms | 1536 KB |
subtask_4_2.txt | WA | 360 ms | 1408 KB |
subtask_4_3.txt | AC | 359 ms | 1408 KB |
subtask_4_4.txt | AC | 359 ms | 1408 KB |
subtask_4_5.txt | AC | 305 ms | 1408 KB |
subtask_4_6.txt | AC | 40 ms | 1408 KB |
subtask_4_7.txt | AC | 197 ms | 1408 KB |
subtask_4_8.txt | AC | 354 ms | 1408 KB |
subtask_4_9.txt | AC | 166 ms | 1408 KB |