Món quà của thầy Kiên - LCOJ: Luyện Code Online Judge

KSUM - Món quà của thầy Kiên

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Trong lớp học của thầy Kiên, Bờm là một học sinh vô cùng xuất sắc. Hôm nay, Bờm lại tiếp tục đứng nhất trong một Contest giữa các trường, vì thế thầy Kiên quyết định sẽ tặng Bờm một ít kẹo xem như phần thưởng.

Thầy Kiên có ~n~ viên kẹo được đánh số lần lượt từ ~1~ đến ~n~. Viên kẹo thứ ~i~ có độ ngon ~w_i~. Hôm nay, thầy quyết định tặng Bờm ~k~ viên kẹo liên tiếp ~(1 ≤ k ≤ n)~ trong ~n~ viên kẹo. Mặc khác, vì Bờm rất xuất sắc nên thầy Kiên muốn tổng độ ngon của những viên kẹo Bờm nhận được là lớnnhất. Bạn hãy giúp thầy Kiên tính toán tổng độ ngon của những viên kẹo mà Bờm sẽ nhận được nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~k~ ~(k ≤ n ≤ 10^5)~ là số lượng kẹo của thầy Kiên;
Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa duy nhất một số nguyên ~w_i~ là độ ngon của viên kẹo thứ ~i~ ~(1 ≤ w_i ≤ 10^9)~.

Giới hạn:

~40\%~ số test có ~k ≤ n ≤ 10000~;
~60\%~ số test còn lại không có giới hạn gì thêm.

Output

Đưa ra kết quả bài toán trên một dòng.

Sample

Input #1

Output #1

Hint

Thầy Kiên cần chọn ~2~ viên kẹo liên tiếp sao cho tổng độ ngon là lớn nhất, vì thế thầy sẽ chọn viên kẹo thứ ~3~ và viên kẹo thứ ~4~.

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

 #include<bits/stdc++.h>
using namespace std;
long long n,m,k,cnt=0,a[1000000],maxsum=0,sum=0;        
main()
{
  cin>>n>>k;
  for(int i=1;i<=n;i++)
     cin>>a[i];
    for(int i=1;i<=k;i++)
    sum+=a[i];
    maxsum=sum;
    for(int i=k+1;i<=n;i++){
            sum=sum-a[i-k]+a[i];
            maxsum=max(maxsum,sum);
        }
        cout<<maxsum;
}

include <bits/stdc++.h>

using namespace std; using ll = long long;

int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

int n, k;
cin >> n >> k;
vector<ll> prefix(n+1, 0);
for (int i = 1; i <= n; i++) {
    ll x;
    cin >> x;
    prefix[i] = prefix[i-1] + x;
}

ll ans = LLONG_MIN;
for (int i = k; i <= n; i++) {
    ll cur = prefix[i] - prefix[i-k];
    ans = max(ans, cur);
}

cout << ans << "\n";
return 0;

}

-1

dona10khoa_nhd đã bình luận lúc 3, Tháng 8, 2025, 14:38 ← sửa 2 →

Bài này sử dụng prefix sum!

Trước tiên hãy tạo mảng prefix sum, sau đó chạy con trỏ từ k đến n, cập nhật ans = max(ans, pre[i] - pre[i - k]) rồi xuất ans

-2

0988440189 đã bình luận lúc 19, Tháng 4, 2025, 10:44

LƯU Ý :Là không được thay đổi mảng đâu nhé , bài bắt mình tính tổng các phần trong đoạn con có K phần tử nhé .Thì mình làm theo tư tưởng preFixSum thôi . Trước hết là lưu giá trị của S[i] từ i=1 đến n , S[i]=S[i-1]+a[i-1 ],sét S[0]=0 nhé (công thức tính tổng các phần tử trong mảng của đoạn từ [0,i]) =>ta sẽ được mảng S{0,4,7,9,15,16} ... sau đó mình so sánh khoảng cách giữa các S[i]-S[i-k] với i chạy từ k đến n Fan MU Mãi ĐỈnh///