526互联

Educational Codeforces Round 126 (Rated for Div. 2)

发布时间 2023-11-09 20:40:32作者: gan_coder

https://codeforces.com/contest/1661/
B题数据很小，直接bfs预处理就行
C题随便猜了一下，设mx=\(max\{a_i\}\)最后的值应该是
mx,mx+1,mx+2,mx+3之类的吧
D题刚开始从前面考虑，陷入僵局，一度非常的困，学习凯库勒睡了一会，就突然想到了，前面不行，就从后面考虑，可以发现，从后面考虑的话，就非常简单，直接无脑贪就行。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const int inf=1<<30;
const int N=3e5+5;
ll a[N],n,k,b[N],s,t,z,ans;
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);

	scanf("%lld %lld",&n,&k);
	fo(i,1,n) scanf("%lld",&a[i]);
	
	fd(i,n,k+1) {
		
		z=0;
		t-=b[i];
		s-=t;
		a[i]-=s;
		if (a[i]>0) {
			if (a[i]%k) z=a[i]/k+1;
			else z=a[i]/k;
		}
		
		ans+=z;
		s+=z*k;
		t+=z;
		b[i-k-1]+=z;
	}
	fd(i,k,1) {
		z=0;
		t-=b[i];
		s-=t;
		a[i]-=s;
	}	
	
	ll mx=0;
	fo(i,1,k) {
		if (a[i]>0) {
			if (a[i]%i==0) mx=max(mx, a[i]/i);
			else mx=max(mx, a[i]/i+1);
		}
	}
	
	ans+=mx;
	printf("%lld",ans);

	return 0;
}