Submission #2195219


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

ll dp[301][100000];
ll a[100000];

signed main(){
	int n,m,k;scanf("%d%d%d",&n,&m,&k);
	rep(i,n){
		scanf("%lld",&a[i]);
		dp[0][i]=a[i];
	}
	for(int i=1;i<k;i++){
		deque<ll>que;
		for(int j=1;j<n;j++){
			while(!que.empty()&&que.front()<j-m)que.pop_front();
			if(dp[i-1][j-1]){
				while(!que.empty()&&dp[i-1][que.back()]<=dp[i-1][j-1])que.pop_back();
				que.push_back(j-1);
			}
			if(!que.empty())dp[i][j]=dp[i-1][que.front()]+(i+1)*a[j];
		}
	}
	ll Max=0;
	rep(i,n)Max=max(Max,dp[k-1][i]);
	cout<<Max<<endl;
}

Submission Info

Submission Time
Task A - Struck Out
User autumn_eel
Language C++14 (GCC 5.4.1)
Score 700
Code Size 779 Byte
Status AC
Exec Time 467 ms
Memory 235904 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:15:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int n,m,k;scanf("%d%d%d",&n,&m,&k);
                                    ^
./Main.cpp:17:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&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 × 46
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 2304 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 2 ms 2304 KB
subtask_1_1.txt AC 6 ms 24832 KB
subtask_1_2.txt AC 83 ms 233984 KB
subtask_1_3.txt AC 438 ms 235776 KB
subtask_1_4.txt AC 8 ms 24960 KB
subtask_1_5.txt AC 20 ms 6400 KB
subtask_1_6.txt AC 32 ms 155904 KB
subtask_1_7.txt AC 155 ms 80128 KB
subtask_1_8.txt AC 439 ms 235776 KB
subtask_1_9.txt AC 48 ms 233728 KB
subtask_2_1.txt AC 6 ms 22784 KB
subtask_2_2.txt AC 3 ms 8448 KB
subtask_2_3.txt AC 4 ms 14592 KB
subtask_2_4.txt AC 6 ms 22784 KB
subtask_2_5.txt AC 6 ms 22784 KB
subtask_2_6.txt AC 6 ms 22784 KB
subtask_2_7.txt AC 6 ms 22784 KB
subtask_2_8.txt AC 6 ms 22784 KB
subtask_2_9.txt AC 5 ms 16640 KB
subtask_3_1.txt AC 55 ms 24832 KB
subtask_3_2.txt AC 55 ms 24832 KB
subtask_3_3.txt AC 56 ms 24832 KB
subtask_3_4.txt AC 45 ms 24448 KB
subtask_3_5.txt AC 8 ms 22912 KB
subtask_3_6.txt AC 35 ms 14592 KB
subtask_3_7.txt AC 55 ms 24832 KB
subtask_3_8.txt AC 11 ms 23040 KB
subtask_3_9.txt AC 58 ms 24832 KB
subtask_4_1.txt AC 440 ms 235776 KB
subtask_4_10.txt AC 234 ms 235776 KB
subtask_4_11.txt AC 465 ms 235776 KB
subtask_4_12.txt AC 467 ms 235776 KB
subtask_4_13.txt AC 462 ms 235776 KB
subtask_4_2.txt AC 462 ms 235904 KB
subtask_4_3.txt AC 440 ms 235776 KB
subtask_4_4.txt AC 440 ms 235776 KB
subtask_4_5.txt AC 376 ms 200960 KB
subtask_4_6.txt AC 45 ms 20736 KB
subtask_4_7.txt AC 250 ms 125184 KB
subtask_4_8.txt AC 434 ms 235776 KB
subtask_4_9.txt AC 204 ms 104704 KB