Bedao Mini Contest 20 - SumRange

Xem dạng PDF
Gửi bài giải
Điểm: 0,38 (OI)
Giới hạn thời gian: 0.5s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho hai dãy ~a~ và ~b~ cùng có ~n~ phần tử nguyên. Ta định nghĩa hàm ~sum(x,y)~ ~(1 \le x,y \le n)~ như sau:

  • Nếu ~x \le y~ thì ~sum(x,y) = a_x + a_{x+1} + a_{x+2} + ... + a_y~.

  • Nếu ~x > y~ thì ~sum(x,y) = b_x + b_{x-1} + b_{x-2} + ... + b_y~.

Nhiệm vụ mà Lihwy đặt ra cho bạn là, hãy chọn ra hai đoạn ~[x,y]~ ~(1 \le x \le y \le n)~ và ~[c,d]~ ~(1 \le c \le d \le n)~ sao cho ~S = \sum sum(i,j)~ với mọi ~x \le i \le y~ và ~c \le j \le d~ là lớn nhất.

Input

  • Dòng đầu gồm số nguyên dương ~n~ (~1 \le n \le 400~).

  • Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a~ ~(-10^6 \le a_i \le 10^6)~.

  • Dòng thứ ba gồm ~n~ số nguyên miêu tả dãy ~b~ ~(-10^6 \le b_i \le 10^6)~.

Output

  • In ra ~S~ lớn nhất tìm được.

Scoring

Subtask Điểm Giới hạn
1 ~20~ ~n \le 20~
2 ~30~ ~n \le 50~
3 ~50~ Không có ràng buộc gì thêm

Sample Input 1

5
1 4 2 -1 -2
-2 -1 1 2 -1

Sample Output 1

45

Notes

Chọn đoạn ~[1,5]~ và ~[2,5]~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    Thien2009  đã bình luận lúc 24, Tháng 6, 2026, 3:00 ← chỉnh sửa

    xin chào các bạn, hôm nay mình muốn chia sẻ một lỗi khá nhỏ và dễ bị bỏ qua do thói quen code

    khi làm bài mình có thói quen khởi tạo Min là dương vô cùng, trong trường hợp của code dưới đây là chưa chính xác mà Min phải là 0

    #include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i,a,b,dif) for(int _a = (a), _b = (b), i = _a; abs(_a - _b) == abs(_a - i) + abs(_b - i) ; i += (dif))
#define name ""
using namespace std;
using ll = long long;
template <class X, class Y>
struct Prefix_sum_1D
{
    /// mang a danh so tu 1
    vector<X> sum;
    void pre(vector<Y> &a, X c)
    {
        int n = sz(a);
        sum.assign(n + 1, 0);
        sum[0] = c;
        for(int i = 0; i < n; ++ i)
            sum[i + 1] = sum[i] + a[i];
    }
    X get(int l, int r)
    {
        return sum[r] - sum[l - 1];
    }
};
int main ()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(name"out","w",stdout);
    int n;
    cin >> n;

    vector<int> a(n), b(n);

    for(int &i : a)
        cin >> i;

    for(int &i : b)
        cin >> i;

    Prefix_sum_1D<ll,int> A, B;
    A.pre(a, 0);
    B.pre(b,0);

    vector<vector<ll>> sum(n, vector<ll> (n));
    for(int i = 0; i < n; ++ i)
    {
        for(int j = 0; j < n; ++ j)
        {
            if(i <= j)
                sum[i][j] = A.get(i + 1, j +1);
            else
                sum[i][j] = B.get(j + 1, i + 1);
        }
    }

    ll ans = -1e18;
    for(int c = 0; c < n; ++ c)
    {
        vector<ll> x(n);
        for(int d = c; d < n; ++ d)
        {
            for(int i = 0; i < n; ++ i)
                x[i] += sum[d][i];

            ll Min = 0; /// o day ne
            /// o cho nay ne
            ll S = 0;
            for(ll i : x)
            {
                S += i;
                ans = max(ans, S - Min);
                Min = min(Min, S);
            }
        }
    }
    cout << ans;
}