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

View as PDF
Submit solution
Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout
Problem source:
Duyên hải 2021
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Comments

Please read the guidelines before commenting.


  • 1
    QDuckAcc2  commented on Jan. 19, 2026, 1:56 p.m. ← edited

    Gợi ý siêu đơn giản:

    Kanade + prefix sum + sàng nguyên tố


  • 1
    Dangcoder  commented on Dec. 9, 2025, 12:20 p.m.

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


  • 1
    vominhmanh10  commented on Nov. 12, 2025, 4:20 a.m. ← edit 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())

  • 0
    vjudgeonline  commented on Sept. 9, 2025, 4:30 p.m. ← edited

    💡 Ý 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

  • -3
    lvnhatquang1212  commented on Sept. 2, 2025, 8:50 a.m. ← edit 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  commented on Sept. 2, 2025, 8:00 a.m. ← edited
    • B *

  • -4
    toquyen260288  commented on Sept. 2, 2025, 7:38 a.m.

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


  • -3
    quan08  commented on Aug. 8, 2025, 8:59 a.m.

    dễ thật


  • -1
    quochung22022009  commented on March 24, 2025, 3:22 p.m.

    h


  • -11
    Trn115  commented on June 21, 2024, 3:37 a.m. ← edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 1
      melondepchai  commented on July 6, 2024, 7:43 a.m.

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


  • -8
    dangminh  commented on April 2, 2024, 1:11 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    nccuongtq2023  commented on March 14, 2024, 3:15 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -6
      apotocaplyse  commented on Feb. 23, 2025, 9:05 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -9
    nhanhtq2023  commented on March 14, 2024, 3:14 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    nhuttruong2k9  commented on Jan. 7, 2024, 8:08 a.m. ← edited

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


    • 7
      thanhhoang  commented on Jan. 23, 2024, 6:37 p.m.

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


  • -2
    tuanm123  commented on Sept. 6, 2023, 12:34 p.m.

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


  • 0
    khangnguyen1108  commented on March 23, 2023, 11:02 p.m.

    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  commented on Dec. 29, 2022, 3:37 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -16
    nguyenhainam1012cg  commented on Nov. 26, 2022, 8:34 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -6
      toidaidot  commented on July 13, 2023, 4:09 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


    • 5
      Thangdeptrai  commented on June 22, 2023, 9:34 a.m.

      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  commented on July 21, 2022, 4:25 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.