Duyên Hải 2021 - Khối 10 - Bài 1 - Bài dễ

Điểm: 0,30 (OI)

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

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Nguồn bài:

Duyên hải 2021

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

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

0

Dangcoder đã bình luận lúc 9, Tháng 12, 2025, 12:20

Bài này test 1 ra -1 nha mọi người, tôi không hiểu tại sao luôn

vominhmanh10 đã bình luận lúc 12, Tháng 11, 2025, 4:20 ← sửa 6 →

sàng, mảng cộng dồn rồi duyệt (l, r) nguyên tố là chưa đủ, ta sẽ dùng cách duyệt khác
khi duyệt r nguyên tố, tính minpre = min(pre[r - 1], minpre) nhỏ nhất tìm thấy hiện tại, như vậy res = max(res, pre[r] - minpre) sẽ là lớn nhất sau khi duyệt hết
do python tính sàng thông thường sẽ bị TLE nên đã duyệt trước bội 2 rồi tính sàng lẻ để giảm thời gian tính sàng xuống còn một nửa

import sys
input = sys.stdin.read

def sieve():
    primes[0] = primes[1] = False
    k = int(n ** 0.5)
    for i in range(4, n + 1, 2): primes[i] = False
    for i in range(3, k + 1, 2):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
def main():
    sieve()
    min_pre = 10**18
    res = -10**18
    s = 0
    for i in range(1, n + 1):
        if primes[i]:
            min_pre = min(s, min_pre)
            res = max(res, s + a[i - 1] - min_pre)
        s += a[i - 1]
    return res



data = input().split()
n = int(data[0])
a = list(map(int, data[1:]))
primes = [True] * (n + 1) 
print(main())

vjudgeonline đã bình luận lúc 9, Tháng 9, 2025, 16:30 ← chỉnh sửa →

💡 Ý tưởng nhỏ của tôi

Ban đầu ai cũng nghĩ sẽ đi sàng rồi duyệt l r là các số nguyên tố NHƯNG nó có thể TLE nếu tối ưu không khéo.

Ở đây chúng ta vẫn có prefix và sàng nhưng ta chỉ duyệt 1 for chạy i.
Ta có thêm biến min=inf để mỗi lần lấy min prefix i đã xét trước đó.
res update sẽ là pre[i] - min.
Code định nghĩa macro + main:
#define BUILD int main(){ios::sync_with_stdio(0);cin.tie(0);int n;cin>>n;const int N=1000005;static bool isPrime[N];static ll a[N],ps[N];
Khởi tạo mảng sàng:
fill(isPrime,isPrime+n+1,true);
isPrime[0]=isPrime[1]=false;
Sàng nguyên tố + prefix sum:
for(int i=2;i*i<=n;i++)
    if(isPrime[i])
        for(int j=i*i;j<=n;j+=i) isPrime[j]=false;
for(int i=1;i<=n;i++) cin>>a[i];
ps[0]=0;
for(int i=1;i<=n;i++) ps[i]=ps[i-1]+a[i];
Tính kết quả cuối:
ll ans=LLONG_MIN,best=LLONG_MAX;
for(int i=2;i<=n;i++) if(isPrime[i]){
    if(best!=LLONG_MAX) ans=max(ans,ps[i]-best);
    best=min(best,ps[i-1]);
}
cout<<ans<<"\n";}
Macro BUILD:
BUILD

-4

lvnhatquang1212 đã bình luận lúc 2, Tháng 9, 2025, 8:50 ← sửa 9 →

Hint :

Sieve of Eratosthenes ( sàng nguyên tố ) + Mảng cộng dồn + ...

Code mảng cộng dồn:

https://ideone.com/LAAPwq

Code sàng nguyên tố:

https://ideone.com/8gI2z6

1
nhatquangnguyen123abc đã bình luận lúc 2, Tháng 9, 2025, 8:00 ← chỉnh sửa →
B *

-2

toquyen260288 đã bình luận lúc 2, Tháng 9, 2025, 7:38

cảm ơn AI đã giúp mik AC bài này

-2

quan08 đã bình luận lúc 8, Tháng 8, 2025, 8:59

dễ thật

-1

quochung22022009 đã bình luận lúc 24, Tháng 3, 2025, 15:22

h

-11

Trn115 đã bình luận lúc 21, Tháng 6, 2024, 3:37 ← sửa 2 →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

2

melondepchai đã bình luận lúc 6, Tháng 7, 2024, 7:43

Chắc chắn có mà ông, n>=2 mà 2 là số nguyên tố rồi

-9

dangminh đã bình luận lúc 2, Tháng 4, 2024, 13:11 ← chỉnh sửa →

cho e hỏi em code nnay nó bị rte segment fault là s ạ

include <bits/stdc++.h>

using namespace std;

define fu(i,a,b) for(int i=a;i<=b;i++)

const int maxn=1e6; bool isPrime[maxn+10]; int n,res[maxn+10],l,a[maxn+10];

void prefixSum(){ fu(i,1,n) a[i]+=a[i-1]; }

void sieve() { isPrime[0] = true; isPrime[1] = true; for(int i=2; i<=n; ++i){ if(!isPrime[i]){ res[l]=i; l++; for(int j=i*i; j<=n; j+=i) isPrime[j] = true; } } } int main(){ iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; int m=-maxn-100; fu(i,1,n){ cin >> a[i]; } prefixSum(); sieve(); fu(i,0,l-1) fu(j,i,l-1) m=max(m,a[res[j]]-a[res[i]-1]); cout << m; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

nccuongtq2023 đã bình luận lúc 14, Tháng 3, 2024, 3:15

6 bài đầu biết test làm vậy ngầu quá ha lấy top 1 bài giải bằng cách biết test xong in ra các bạn làm vậy có hơi kém ý thức của 1 con người không

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

apotocaplyse đã bình luận lúc 23, Tháng 2, 2025, 9:05

trẩu cay à=))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-10

nhanhtq2023 đã bình luận lúc 14, Tháng 3, 2024, 3:14

1 đấm AC

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

0

nhuttruong2k9 đã bình luận lúc 7, Tháng 1, 2024, 8:08 ← chỉnh sửa →

Đoạn [L..R] có tổng lớn nhất là: [2..5] -> Tổng: 5 + (-2) + 6 + (-1) = 8.

7

thanhhoang đã bình luận lúc 23, Tháng 1, 2024, 18:37

Đoạn [L..R] có tổng lớn nhất là: [2..5] -> Tổng: 5 + (-2) + 6 + (-1) = 8.

-2

tuanm123 đã bình luận lúc 6, Tháng 9, 2023, 12:34

wa test 1 là sai trường hợp nào vậy ạ

0

khangnguyen1108 đã bình luận lúc 23, Tháng 3, 2023, 23:02

mình dùng mảng cộng với sàng ngto mà vẫn bị TLE 3 test cuối , ai cho mình xin hướng với

-19

hungcoder đã bình luận lúc 29, Tháng 12, 2022, 3:37 ← chỉnh sửa →

bai nay dung mang cong la full

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-16

nguyenhainam1012cg đã bình luận lúc 26, Tháng 11, 2022, 8:34

ai ac rồi cho mình xin thuật được ko

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

toidaidot đã bình luận lúc 13, Tháng 7, 2023, 4:09

no

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

5

Thangdeptrai đã bình luận lúc 22, Tháng 6, 2023, 9:34

sàng, mảng cộng dòn, min[i] (min 1 -> i) max(i) (max n -> i) for 1 -> n maximize(ans, max[i + 1] - min[i])

-37

thanh20092007 đã bình luận lúc 21, Tháng 7, 2022, 16:25

kho qua

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

Duyên Hải 2021 - Khối 10 - Bài 1 - Bài dễ

Bình luận

include <bits/stdc++.h>

define fu(i,a,b) for(int i=a;i<=b;i++)