Submission #998056
Source Code Expand
#include <iostream> #include <fstream> #include <sstream> #include <vector> #include <set> #include <bitset> #include <map> #include <deque> #include <string> #include <algorithm> #include <numeric> #include <cstdio> #include <cassert> #include <cstdlib> #include <cstring> #include <ctime> #include <cmath> #define pb push_back #define pbk pop_back #define mp make_pair #define fs first #define sc second #define all(x) (x).begin(), (x).end() #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i) #define len(a) ((int) (a).size()) #ifdef CUTEBMAING #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif #define rank hurank using namespace std; typedef long long int64; typedef long double ld; typedef unsigned long long lint; const int inf = (1 << 30) - 1; const int64 linf = (1ll << 62) - 1; const int N = 1e6 + 100; int n, m, k; int a[N]; int64 dp[N]; int parent[N], rank[N]; int64 value[N]; inline int findSet(int v) { if (parent[v] != v) { return parent[v] = findSet(parent[v]); } return v; } inline void unite(int a, int b) { a = findSet(a); b = findSet(b); if (a == b) { return ; } if (rank[a] == rank[b]) { rank[a]++; } if (rank[a] > rank[b]) { swap(a, b); } parent[a] = b; } int main() { #ifdef XCODE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> n >> m >> k; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < k; i++) { for (int j = n - 1; j >= 0; j--) { dp[j + 1] = dp[j]; } dp[0] = i == 0 ? 0 : -linf; for (int j = 0; j < n; j++) { parent[j] = j; rank[j] = 0; } vector<pair<int64, int>> stack; for (int j = 0; j < n; j++) { pair<int64, int> curValue(dp[j] + 1ll * (i + 1) * a[j], j); while (len(stack) > 0 && stack.back().fs <= curValue.fs) { unite(stack.back().sc, curValue.sc); stack.pbk(); } value[findSet(curValue.sc)] = curValue.fs; stack.pb(curValue); dp[j] = value[findSet(max(0, j - m + 1))]; } } cout << *max_element(dp, dp + n) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | darinflar |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2450 Byte |
Status | AC |
Exec Time | 854 ms |
Memory | 2944 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:86:27: 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 | 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 | 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 | 62 ms | 512 KB |
subtask_1_3.txt | AC | 622 ms | 2944 KB |
subtask_1_4.txt | AC | 7 ms | 384 KB |
subtask_1_5.txt | AC | 28 ms | 2944 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 219 ms | 2944 KB |
subtask_1_8.txt | AC | 624 ms | 2944 KB |
subtask_1_9.txt | AC | 5 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 | AC | 3 ms | 256 KB |
subtask_2_6.txt | AC | 3 ms | 384 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 | 86 ms | 2944 KB |
subtask_3_2.txt | AC | 96 ms | 2944 KB |
subtask_3_3.txt | AC | 92 ms | 2944 KB |
subtask_3_4.txt | AC | 77 ms | 2432 KB |
subtask_3_5.txt | AC | 6 ms | 384 KB |
subtask_3_6.txt | AC | 57 ms | 2944 KB |
subtask_3_7.txt | AC | 82 ms | 2944 KB |
subtask_3_8.txt | AC | 11 ms | 512 KB |
subtask_3_9.txt | AC | 97 ms | 2944 KB |
subtask_4_1.txt | AC | 754 ms | 2944 KB |
subtask_4_10.txt | AC | 680 ms | 2944 KB |
subtask_4_11.txt | AC | 854 ms | 2944 KB |
subtask_4_12.txt | AC | 846 ms | 2944 KB |
subtask_4_13.txt | AC | 823 ms | 2944 KB |
subtask_4_2.txt | AC | 809 ms | 2944 KB |
subtask_4_3.txt | AC | 644 ms | 2944 KB |
subtask_4_4.txt | AC | 765 ms | 2944 KB |
subtask_4_5.txt | AC | 674 ms | 2944 KB |
subtask_4_6.txt | AC | 65 ms | 2944 KB |
subtask_4_7.txt | AC | 432 ms | 2944 KB |
subtask_4_8.txt | AC | 747 ms | 2944 KB |
subtask_4_9.txt | AC | 360 ms | 2944 KB |