比赛 |
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;
}