比赛 20161114 评测结果 WAAWWAWWTT
题目名称 社长的qwa 最终得分 30
用户昵称 Tabing010102 运行时间 2.048 s
代码语言 C++ 内存使用 0.69 MiB
提交时间 2016-11-14 10:46:59
显示代码纯文本
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int maxn = 100000+10;
const LL INF = 900000000000000000ll;
FILE *fin, *fout;
int n, k, A[maxn];
struct SEG {
	LL sumv[maxn<<2];
	SEG(int n) {
		this->build(1, 1, n);
	}
	void build(int o, int L, int R) {
		if(L == R) {
			sumv[o] = A[L];
		} else {
			int lc=o*2, rc=o*2+1;
			int M = L + (R-L)/2;
			build(lc, L, M);
			build(rc, M+1, R);
			sumv[o] = sumv[lc]+sumv[rc];
		}
	}
	LL _sum, oL, oR;
	void qsum(int o, int L, int R) {
		if(L>=oL && R<=oR) {
			_sum += sumv[o];
		} else {
			int lc=o*2, rc=o*2+1;
			int M = L + (R-L)/2;
			if(M >= oL) qsum(lc, L, M);
			if(M < oR) qsum(rc, M+1, R);
		}
	}
	LL qsum(int l, int r) {
		_sum = 0;
		oL = l; oR = r;
		qsum(1, 1, n);
		return _sum;
	}
};
LL ans=INF;
int main() {
	fin = fopen("qwa.in", "r");
	fout = fopen("qwa.out", "w");
	fscanf(fin, "%d%d", &n, &k); n--,k--;
	if(n <= 0) { fprintf(fout, "0\n"); exit(0); }
	LL prev;
	fscanf(fin, "%lld", &prev);
	for(int i = 1; i <= n; i++) {
		int tmp;
		fscanf(fin, "%d", &tmp);
		A[i] = tmp-prev;
		prev += A[i];
	}
//	for(int i = 1; i <= n; i++) printf("%d ", A[i]); printf("\n");
	SEG *D = new SEG(n);
	for(int i = 1; i <= n-k+1; i++) {
		LL s=i, e=i+k-1;
		LL tans = 0;
		LL cc=1, last=0;
		while(s <= e) {
			LL tmp = cc*(k-cc+1)-last;
//			printf("cc=%I64d, last=%I64d, tmp=%I64d, ", cc, last, tmp);
			tans += D->qsum(s, e)*tmp;
//			printf("tans=%I64d\n", tans);
			cc++,s++,e--;
			last += tmp;
		}
//		printf("%I64d\n", tans);
		if(tans < ans) ans = tans;
	}
	fprintf(fout, "%lld\n", ans);
	return 0;
}