logoChat01.ai

Domanda

image.png
image.png
image.png
image.png
image.png

code in cpp

Python

python
import random

def brute(k,segs):
    maxR=max(r for l,r,c in segs)
    best=0; bx=None
    for x in range(1,maxR+2):
        s=0
        e=x+k-1
        for l,r,c in segs:
            a=max(l,x); b=min(r,e)
            if a<=b: s+=(b-a+1)*c
        if s>best:
            best=s; bx=x
    return best,bx

def cand(k,segs):
    starts={1}
    for l,r,c in segs:
        starts.add(l)
        if r-k+1>=1: starts.add(r-k+1)
        else: starts.add(1)
    best=0; bx=None
    for x in starts:
        s=0; e=x+k-1
        for l,r,c in segs:
            a=max(l,x); b=min(r,e)
            if a<=b: s+=(b-a+1)*c
        if s>best:
            best=s; bx=x
    return best,bx,starts

def gen():
    # random non-overlap intervals in [1,30]
    positions=list(range(1,31))
    segs=[]
    cur=1
    # create random values piecewise maybe
    while cur<=30:
        if random.random()<0.5:
            cur+=random.randint(1,3)
        else:
            l=cur
            r=random.randint(l,min(30,l+random.randint(0,5)))
            c=random.randint(1,10)
            segs.append((l,r,c))
            cur=r+random.randint(1,3)
    if not segs:
        segs=[(random.randint(1,30), random.randint(1,30), random.randint(1,10))]
        if segs[0][0]>segs[0][1]: segs=[(segs[0][1],segs[0][0],segs[0][2])]
    return segs

for n in range(10000):
    segs=gen()
    k=random.randint(1,20)
    b,bx=brute(k,segs)
    c,cx,ss=cand(k,segs)
    if b!=c:
        print("counter",k,segs,b,bx,c,cx,sorted(ss))
        break
else:
    print("no counter")

Pensiero

Preparing final function code

The candidate set looks good, and I’m now thinking about delivering just the function, as that’s the user’s request. Given that values are positive with no intersections, I'll add the necessary logic inside the function. Since this is for C++, the constraints require using long long and returning modulo 1e9+7. Let's write the function with code and explanation.

Thought for 59s

Risposta

Paste this C++ code in the function:

cpp
int calculateMaximumConsecutiveSum(int k, vector<vector<int>> segment) {
    const long long MOD = 1000000007LL;

    sort(segment.begin(), segment.end());

    int n = segment.size();
    vector<long long> L(n), R(n), C(n), pref(n + 1, 0);

    for (int i = 0; i < n; i++) {
        L[i] = segment[i][0];
        R[i] = segment[i][1];
        C[i] = segment[i][2];

        pref[i + 1] = pref[i] + (R[i] - L[i] + 1) * C[i];
    }

    long long K = k;

    auto windowSum = [&](long long start) -> long long {
        long long end = start + K - 1;

        int left = lower_bound(R.begin(), R.end(), start) - R.begin();
        int right = upper_bound(L.begin(), L.end(), end) - L.begin() - 1;

        if (left >= n || right < left) return 0LL;

        long long sum = pref[right + 1] - pref[left];

        if (start > L[left]) {
            sum -= (start - L[left]) * C[left];
        }

        if (end < R[right]) {
            sum -= (R[right] - end) * C[right];
        }

        return sum;
    };

    long long best = 0;

    auto check = [&](long long start) {
        if (start < 1) start = 1;
        best = max(best, windowSum(start));
    };

    check(1);

    for (int i = 0; i < n; i++) {
        check(L[i]);              // window starts at segment start
        check(R[i] - K + 1);      // window ends at segment end
    }

    return (int)(best % MOD);
}

This runs in O(n log n) and works for large k and bag indices up to 10^9.

Condividi questa Q&A