Submission #998195


Source Code Expand

#include<cstdio>
#include<deque>
#include<algorithm>

using namespace std;

typedef pair<long long, int> P;

const long long inf = 1e18;

int M, N;
int K;
int A[100100];

long long dp[100100][330];

long long solve(){
	for(int i = 0; i < N; ++i){
		dp[i][1] = A[i];
	}
	for(int j = 2; j <= K; ++j){
		deque<P> deq;
		if(dp[0][j - 1] != -inf) deq.push_front(P(dp[0][j - 1], 0));
		dp[0][j] = -inf;
		for(int i = 1; i < N; ++i){
			if(!deq.empty()){
			if(deq.front().first == -inf){
				dp[i][j] = -inf;
			}else{
				dp[i][j] = deq.front().first + (long long)A[i] * j;
			}
			while(!deq.empty()){
				if(deq.back().first < dp[i][j - 1]){
					deq.pop_back();
				}else break;
			}
			deq.push_back(P(dp[i][j - 1], i));
			if(deq.front().second == i - M){
				deq.pop_front();
			}
			}else{
				dp[i][j] = -inf;
				if(dp[i][j - 1] != -inf){
					deq.push_front(P(dp[i][j - 1], i));
				}
			}
		}
	}
	long long ans = -1;
	for(int i = 0; i < N; ++i){
	/*	for(int j = 0; j <= K; ++j){
			printf("%lld ", dp[i][j]);
		}
		printf("\n");*/
		ans = max(ans, dp[i][K]);
	}
	return ans;
}

void input(){
	scanf("%d%d%d", &N, &M, &K);
	for(int i = 0; i < N; ++i){
		scanf("%d", A + i);
	}
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User wo01
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1342 Byte
Status AC
Exec Time 931 ms
Memory 258560 KB

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:61:29: 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:63:21: 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
AC × 3
AC × 10
AC × 12
AC × 21
AC × 43
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 3 ms 640 KB
subtask_1_2.txt AC 85 ms 26112 KB
subtask_1_3.txt AC 868 ms 258432 KB
subtask_1_4.txt AC 17 ms 13184 KB
subtask_1_5.txt AC 259 ms 258432 KB
subtask_1_6.txt AC 3 ms 768 KB
subtask_1_7.txt AC 425 ms 258432 KB
subtask_1_8.txt AC 870 ms 258432 KB
subtask_1_9.txt AC 5 ms 1536 KB
subtask_2_1.txt AC 3 ms 1024 KB
subtask_2_2.txt AC 3 ms 1024 KB
subtask_2_3.txt AC 3 ms 1024 KB
subtask_2_4.txt AC 3 ms 768 KB
subtask_2_5.txt AC 2 ms 384 KB
subtask_2_6.txt AC 2 ms 256 KB
subtask_2_7.txt AC 3 ms 1024 KB
subtask_2_8.txt AC 3 ms 1024 KB
subtask_2_9.txt AC 3 ms 1024 KB
subtask_3_1.txt AC 310 ms 258432 KB
subtask_3_2.txt AC 312 ms 258432 KB
subtask_3_3.txt AC 308 ms 258432 KB
subtask_3_4.txt AC 251 ms 206848 KB
subtask_3_5.txt AC 17 ms 13184 KB
subtask_3_6.txt AC 284 ms 258432 KB
subtask_3_7.txt AC 311 ms 258560 KB
subtask_3_8.txt AC 33 ms 26112 KB
subtask_3_9.txt AC 289 ms 258432 KB
subtask_4_1.txt AC 839 ms 258432 KB
subtask_4_10.txt AC 847 ms 258432 KB
subtask_4_11.txt AC 904 ms 258432 KB
subtask_4_12.txt AC 913 ms 258432 KB
subtask_4_13.txt AC 931 ms 258432 KB
subtask_4_2.txt AC 892 ms 258432 KB
subtask_4_3.txt AC 839 ms 258432 KB
subtask_4_4.txt AC 861 ms 258432 KB
subtask_4_5.txt AC 777 ms 258432 KB
subtask_4_6.txt AC 295 ms 258432 KB
subtask_4_7.txt AC 604 ms 258432 KB
subtask_4_8.txt AC 829 ms 255232 KB
subtask_4_9.txt AC 539 ms 258432 KB