Submission #2423427
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;
const double eps = 1e-6;
template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}
const int64 mod = 1e9+7;
/*
int main(void){
int32 N;
cin >> N;
vector<int64> v(N);
REP(i, N) cin >> v[i];
int64 maxi = 0;
int64 res = 0;
REP(i, N){
int64 cnt = (v[i]-1)/(maxi+1);
if(cnt){ res += cnt; chmax(maxi, 1); }
else maxi = v[i];
}
cout << res << endl;
}
*/
int main(void){
int32 M, N, K;
scanf("%d %d %d", &N, &M, &K);
int64 A[112345];
deque<PLL> deq[301];
REP(i, N) scanf("%lld", &A[i]);
REP(i, N){
for(int32 j = K-1;j >= 1;j--){
while(deq[j-1].size() && i-deq[j-1].front().sc > M) deq[j-1].pop_front();
if(deq[j-1].empty()) continue;
int64 val = deq[j-1].front().fs+A[i]*(j+1);
while(deq[j].size() && val > deq[j].back().fs) deq[j].pop_back();
deq[j].push_back(PLL(val, i));
}
while(deq[0].size() && A[i] > deq[0].back().fs) deq[0].pop_back();
deq[0].push_back(PLL(A[i], i));
}
cout << deq[K-1].front().fs << endl;
}
Submission Info
Submission Time
2018-04-28 04:22:45+0900
Task
A - Struck Out
User
maze1230
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
1570 Byte
Status
AC
Exec Time
375 ms
Memory
1280 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:47:30: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘int32* {aka long int*}’ [-Wformat=]
scanf("%d %d %d", &N, &M, &K);
^
./Main.cpp:47:30: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘int32* {aka long int*}’ [-Wformat=]
./Main.cpp:47:30: warning: format ‘%d’ expects argument of type ‘int*’, but argument 4 has type ‘int32* {aka long int*}’ [-Wformat=]
./Main.cpp:50:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64* {aka long int*}’ [-Wformat=]
REP(i, N) scanf("%lld", &A[i]);
^
./Main.cpp:47:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &M, &K);
^
./Main.cpp:50:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with ...
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
1 ms
512 KB
sample_2.txt
AC
1 ms
512 KB
sample_3.txt
AC
1 ms
512 KB
subtask_1_1.txt
AC
1 ms
512 KB
subtask_1_2.txt
AC
30 ms
512 KB
subtask_1_3.txt
AC
297 ms
1280 KB
subtask_1_4.txt
AC
3 ms
512 KB
subtask_1_5.txt
AC
18 ms
1280 KB
subtask_1_6.txt
AC
1 ms
512 KB
subtask_1_7.txt
AC
104 ms
1280 KB
subtask_1_8.txt
AC
297 ms
1280 KB
subtask_1_9.txt
AC
2 ms
512 KB
subtask_2_1.txt
AC
1 ms
512 KB
subtask_2_2.txt
AC
1 ms
512 KB
subtask_2_3.txt
AC
1 ms
512 KB
subtask_2_4.txt
AC
1 ms
512 KB
subtask_2_5.txt
AC
1 ms
512 KB
subtask_2_6.txt
AC
1 ms
512 KB
subtask_2_7.txt
AC
1 ms
512 KB
subtask_2_8.txt
AC
1 ms
512 KB
subtask_2_9.txt
AC
1 ms
512 KB
subtask_3_1.txt
AC
41 ms
1280 KB
subtask_3_2.txt
AC
42 ms
1280 KB
subtask_3_3.txt
AC
40 ms
1280 KB
subtask_3_4.txt
AC
34 ms
1152 KB
subtask_3_5.txt
AC
3 ms
512 KB
subtask_3_6.txt
AC
31 ms
1280 KB
subtask_3_7.txt
AC
41 ms
1280 KB
subtask_3_8.txt
AC
5 ms
512 KB
subtask_3_9.txt
AC
48 ms
1280 KB
subtask_4_1.txt
AC
297 ms
1280 KB
subtask_4_10.txt
AC
354 ms
1280 KB
subtask_4_11.txt
AC
373 ms
1280 KB
subtask_4_12.txt
AC
375 ms
1280 KB
subtask_4_13.txt
AC
374 ms
1280 KB
subtask_4_2.txt
AC
361 ms
1280 KB
subtask_4_3.txt
AC
299 ms
1280 KB
subtask_4_4.txt
AC
296 ms
1280 KB
subtask_4_5.txt
AC
259 ms
1280 KB
subtask_4_6.txt
AC
34 ms
1280 KB
subtask_4_7.txt
AC
194 ms
1280 KB
subtask_4_8.txt
AC
298 ms
1280 KB
subtask_4_9.txt
AC
151 ms
1280 KB