Submission #64405218

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
ll a[200005],p[200005];
ll b[200005],q[200005];
void solve(){
	cin >> n >> k;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		p[i]=p[i-1]+a[i];
	}
	for(int i=1; i<=k-1 ;i++) b[i]=i;
	for(int i=k; i<=n ;i++){
		b[i]=b[i-k+1]*k;
		b[i]=min(b[i],(ll)2e9);
	}
	for(int i=1; i<=n ;i++){
		b[i]=min(b[i]-1,a[i]);
		q[i]=q[i-1]+b[i];
	}
	ll ans=0;
	ll b1=0;
	for(int i=k; i<=n ;i++){//
		ll b2=min(p[i]-p[i-k],1LL*k*(i-k+1)-1);
		ll b3=q[n]-q[i];
		ans=max(ans,b1+b2+b3);
		//cout << b1 << ' ' << b2 << ' ' << b3 << endl;
		b1+=min(a[i-k+1],(ll)i-k);
	}
	cout << ans << '\n';

}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--) solve();
}

Submission Info

Submission Time
Task D - Level K Terms
User mulgokizary
Language C++ 20 (gcc 12.2)
Score 1300
Code Size 769 Byte
Status AC
Exec Time 14 ms
Memory 9832 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 1
AC × 51
Set Name Test Cases
Sample 00_sample_01.txt
All 00_sample_01.txt, 01_random_case_01.txt, 01_random_case_02.txt, 01_random_case_03.txt, 01_random_case_04.txt, 01_random_case_05.txt, 01_random_case_06.txt, 01_random_case_07.txt, 01_random_case_08.txt, 01_random_case_09.txt, 01_random_case_10.txt, 01_random_case_11.txt, 01_random_case_12.txt, 01_random_case_13.txt, 01_random_case_14.txt, 01_random_case_15.txt, 01_random_case_16.txt, 01_random_case_17.txt, 01_random_case_18.txt, 01_random_case_19.txt, 02_max_case_01.txt, 02_max_case_02.txt, 02_max_case_03.txt, 02_max_case_04.txt, 02_max_case_05.txt, 02_max_case_06.txt, 02_max_case_07.txt, 02_max_case_08.txt, 02_max_case_09.txt, 02_max_case_10.txt, 02_max_case_11.txt, 02_max_case_12.txt, 02_max_case_13.txt, 02_max_case_14.txt, 02_max_case_15.txt, 02_max_case_16.txt, 02_max_case_17.txt, 02_max_case_18.txt, 02_max_case_19.txt, 02_max_case_20.txt, 03_check_maximum_01.txt, 03_check_maximum_02.txt, 03_check_maximum_03.txt, 03_check_maximum_04.txt, 03_check_maximum_05.txt, 03_check_maximum_06.txt, 03_check_maximum_07.txt, 03_check_maximum_08.txt, 04_handmade_01.txt, 04_handmade_02.txt, 04_handmade_03.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 1 ms 3472 KiB
01_random_case_01.txt AC 6 ms 3540 KiB
01_random_case_02.txt AC 5 ms 3520 KiB
01_random_case_03.txt AC 6 ms 3560 KiB
01_random_case_04.txt AC 7 ms 5540 KiB
01_random_case_05.txt AC 8 ms 5904 KiB
01_random_case_06.txt AC 7 ms 6356 KiB
01_random_case_07.txt AC 7 ms 5560 KiB
01_random_case_08.txt AC 6 ms 5796 KiB
01_random_case_09.txt AC 9 ms 6380 KiB
01_random_case_10.txt AC 8 ms 6116 KiB
01_random_case_11.txt AC 8 ms 6152 KiB
01_random_case_12.txt AC 7 ms 6132 KiB
01_random_case_13.txt AC 10 ms 6256 KiB
01_random_case_14.txt AC 11 ms 9624 KiB
01_random_case_15.txt AC 11 ms 9696 KiB
01_random_case_16.txt AC 11 ms 9704 KiB
01_random_case_17.txt AC 12 ms 9692 KiB
01_random_case_18.txt AC 11 ms 9620 KiB
01_random_case_19.txt AC 11 ms 9832 KiB
02_max_case_01.txt AC 11 ms 9708 KiB
02_max_case_02.txt AC 13 ms 9676 KiB
02_max_case_03.txt AC 12 ms 9760 KiB
02_max_case_04.txt AC 13 ms 9656 KiB
02_max_case_05.txt AC 12 ms 9564 KiB
02_max_case_06.txt AC 11 ms 9684 KiB
02_max_case_07.txt AC 11 ms 9648 KiB
02_max_case_08.txt AC 13 ms 9692 KiB
02_max_case_09.txt AC 11 ms 9764 KiB
02_max_case_10.txt AC 13 ms 9832 KiB
02_max_case_11.txt AC 11 ms 9764 KiB
02_max_case_12.txt AC 13 ms 9692 KiB
02_max_case_13.txt AC 11 ms 9692 KiB
02_max_case_14.txt AC 14 ms 9700 KiB
02_max_case_15.txt AC 11 ms 9640 KiB
02_max_case_16.txt AC 12 ms 9624 KiB
02_max_case_17.txt AC 11 ms 9704 KiB
02_max_case_18.txt AC 11 ms 9708 KiB
02_max_case_19.txt AC 11 ms 9680 KiB
02_max_case_20.txt AC 11 ms 9704 KiB
03_check_maximum_01.txt AC 11 ms 3576 KiB
03_check_maximum_02.txt AC 7 ms 4016 KiB
03_check_maximum_03.txt AC 7 ms 4040 KiB
03_check_maximum_04.txt AC 3 ms 4796 KiB
03_check_maximum_05.txt AC 5 ms 6016 KiB
03_check_maximum_06.txt AC 5 ms 5800 KiB
03_check_maximum_07.txt AC 8 ms 7284 KiB
03_check_maximum_08.txt AC 6 ms 6540 KiB
04_handmade_01.txt AC 1 ms 3432 KiB
04_handmade_02.txt AC 9 ms 9676 KiB
04_handmade_03.txt AC 8 ms 9704 KiB