Submission #1864654


Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e15

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll ball[111111], dp[111111][333];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		cin >> ball[i];
		dp[i][1]=ball[i];
	}
	deque <ii> cur;
	for(int j = 2; j <= k; j++){
		cur.clear();
		for(int i = 1; i <= n; i++){
			if(i<j){
				dp[i][j]=-INF;
			}
			else{
				while(!cur.empty()&&i-cur[0].fi>m){
					cur.pop_front();
				}
				dp[i][j]=cur[0].se+j*ball[i];
				while(!cur.empty()){
					if(dp[i][j-1]>cur[cur.size()-1].se){
						cur.pop_back();
					}
					else{
						break;
					}
				}
			}
			cur.pb(mp(i,dp[i][j-1]));
		}
	}
	ll ans = -INF;
	for(int i = 1; i <= n; i++){
		ans=max(ans,dp[i][k]);
	}
	cout <<ans<<'\n';
	return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User ravenclaws1
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1444 Byte
Status WA
Exec Time 863 ms
Memory 263168 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 0 / 100 0 / 200 0 / 300 0 / 100
Status
AC × 3
AC × 7
WA × 3
AC × 10
WA × 2
AC × 19
WA × 2
AC × 41
WA × 5
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 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
subtask_1_1.txt WA 1 ms 512 KB
subtask_1_2.txt AC 69 ms 27008 KB
subtask_1_3.txt AC 705 ms 263168 KB
subtask_1_4.txt AC 8 ms 14592 KB
subtask_1_5.txt AC 73 ms 263168 KB
subtask_1_6.txt WA 2 ms 768 KB
subtask_1_7.txt AC 275 ms 263168 KB
subtask_1_8.txt AC 706 ms 263168 KB
subtask_1_9.txt WA 3 ms 1536 KB
subtask_2_1.txt AC 2 ms 1024 KB
subtask_2_2.txt AC 2 ms 1024 KB
subtask_2_3.txt AC 2 ms 1024 KB
subtask_2_4.txt AC 2 ms 768 KB
subtask_2_5.txt WA 1 ms 384 KB
subtask_2_6.txt WA 1 ms 384 KB
subtask_2_7.txt AC 2 ms 1024 KB
subtask_2_8.txt AC 2 ms 1024 KB
subtask_2_9.txt AC 2 ms 1024 KB
subtask_3_1.txt AC 127 ms 263168 KB
subtask_3_2.txt AC 136 ms 263168 KB
subtask_3_3.txt AC 132 ms 263168 KB
subtask_3_4.txt AC 106 ms 209792 KB
subtask_3_5.txt AC 8 ms 14592 KB
subtask_3_6.txt AC 98 ms 263168 KB
subtask_3_7.txt AC 127 ms 263168 KB
subtask_3_8.txt AC 14 ms 27008 KB
subtask_3_9.txt AC 134 ms 263168 KB
subtask_4_1.txt AC 745 ms 263168 KB
subtask_4_10.txt AC 704 ms 263168 KB
subtask_4_11.txt AC 775 ms 263168 KB
subtask_4_12.txt AC 774 ms 263168 KB
subtask_4_13.txt AC 773 ms 263168 KB
subtask_4_2.txt AC 810 ms 263168 KB
subtask_4_3.txt AC 735 ms 263168 KB
subtask_4_4.txt AC 863 ms 263168 KB
subtask_4_5.txt AC 651 ms 263168 KB
subtask_4_6.txt AC 119 ms 263168 KB
subtask_4_7.txt AC 447 ms 263168 KB
subtask_4_8.txt AC 709 ms 259072 KB
subtask_4_9.txt AC 378 ms 263168 KB