Submission #866057

#	Time	Username	Problem	Language	Result	Execution time	Memory
866057		farica	Homecoming (BOI18_homecoming)	C++14	0 / 100	32 ms	22100 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

const int MAX_N=2000000;
const int N=1000001;

long long sum_a[MAX_N], sum_b[MAX_N];
int n;

int distance(int l, int r) {
    if(l<=r) return (r-l+1);
    else return n-r+l+1;
}

int decrease(int i, int x) {
    if(i>=x) return i-x;
    return n-(x-i);
}

long long int prefix_suma(int l, int r) {
    if(l<=r) {
        int ret = sum_a[r];
        if(l) ret -= sum_a[l-1];
        return ret;
    }
    int ret=0;
    if(l) ret += sum_a[n-1] - sum_a[l-1];
    else ret += sum_a[n-1];
    ret += sum_a[r];
    return ret;
}

long long int prefix_sumb(int l, int r) {
    if(l<=r) {
        int ret = sum_b[r];
        if(l) ret -= sum_b[l-1];
        return ret;
    }
    int ret=0;
    if(l) ret += sum_b[n-1] - sum_b[l-1];
    else ret += sum_b[n-1];
    ret += sum_b[r];
    return ret;
}

long long int solve(int N, int K, int *A, int *B) {
    int a[n], b[n], k=K;
    n=N;
    for(int i=0; i<n; ++i) {
        a[i] = A[i];
        sum_a[i]=a[i];
        if(i) sum_a[i]+=sum_a[i-1];
    }
    for(int i=0; i<n; ++i) {
        b[i] = B[i];
        sum_b[i]=b[i];
        if(i) sum_b[i]+=sum_b[i-1];
    }
    long long ans=0;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            long long cnt = 0;
            if(distance(i, j)>=k) cnt += prefix_suma(i, decrease(j, k-1));
            cnt -= prefix_sumb(i, j);
            ans=max(ans, cnt);
        }
    }
    return ans;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38