Codeforces 961B Lecture Sleep

2018-4-23 created by AD1024

题目链接: CF961B

问题描述

Your friend Mishka and you attend a calculus lecture. Lecture lasts n minutes. Lecturer tells ai theorems during the $i$-th minute.

Mishka is really interested in calculus, though it is so hard to stay awake for all the time of lecture. You are given an array t of Mishka’s behavior. If Mishka is asleep during the $i$-th minute of the lecture then ti will be equal to $0$, otherwise it will be equal to $1$. When Mishka is awake he writes down all the theorems he is being told — ai during the $i$-th minute. Otherwise he writes nothing.

You know some secret technique to keep Mishka awake for $k$ minutes straight. However you can use it only once. You can start using it at the beginning of any minute between 1 and $n - k + 1$. If you use it on some minute $i$ then Mishka will be awake during minutes $j$ such that $j \in [i, i+k-1]$ and will write down all the theorems lecturer tells.

You task is to calculate the maximum number of theorems Mishka will be able to write down if you use your technique only once to wake him up.

题意

给定一个长度为$n$数组$a$和$s$，其中$s$中元素的值是$0$或$1$，求最大的区间$[i, i+k-1]$使得$\sum_i^{i+k-1} a[i]\times s[i]$最大。

思路

线段树，建立的时候只存入对应$s$上是$0$的$a_i$，然后遍历所有区间求区间和。

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define rson(x) x << 1 | 1
#define lson(x) x << 1
#define fa(x) x >> 1
#define Mid(x, y) (x + y) >> 1 

struct Node {
    int lson, rson, sum;
};

int a[101000], s[101000];
Node tree[101000 << 4];
int N, K;

inline void maintain(int rt) {
    tree[rt].sum = tree[rson(rt)].sum + tree[lson(rt)].sum;
}

void build(int rt, int l,int r) {
    tree[rt].lson = l;
    tree[rt].rson = r;
    if(l == r) {
        if(s[l] == 0) {
            tree[rt].sum = a[l];
        }
    } else {
        int mid = Mid(l, r);
        build(lson(rt), l, mid);
        build(rson(rt), mid + 1, r);
        maintain(rt);
    }
}

inline int query(int rt,int l, int r) {
    if(tree[rt].lson == l && tree[rt].rson == r) {
        return tree[rt].sum;
    } else {
        int mid = Mid(tree[rt].lson, tree[rt].rson);
        if(r <= mid) {
            return query(lson(rt), l, r);
        } else if(l > mid) {
            return query(rson(rt), l, r);
        } else {
            return query(lson(rt), l, mid) + query(rson(rt), mid + 1, r);
        }
    }
}

int ans = 0;

inline int read() {
    char ch = getchar();
    int a = 0;
    while(ch > '9' || ch < '0') ch = getchar();
    while(ch >= '0' && ch <= '9') {
        a = a * 10 + ch - '0';
        ch = getchar();
    }
    return a;
}

int main() {
    scanf("%d%d", &N, &K);
    for(int i=1;i<=N;++i) a[i] = read();
    for(int i=1;i<=N;++i) {
        s[i] = read();
        if(s[i]) {
            ans += a[i];
        }
    }
    build(1, 1, N);
    int maxn = -0x3f3f3f3f;
    int p;
    for(int i=1;i<=N - K + 1;++i) {
        p = query(1, i, i + K - 1);
        if(maxn < p) {
            maxn = p;
        }
    }
    ans += maxn;
    printf("%d\n", ans);
    return 0;
}