Bài dễ (DHBB 2021)

Xem PDF



Tác giả:
Dạng bài
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), một đoạn \(a_L, a_{L+1},..., a_R (1 \le L \le R \le N)\) được gọi là đoạn đẹp nếu \(L, R\) đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

  • Dòng đầu chứa số nguyên dương \(n (n \ge 2)\);
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (|a_i| \le 10^6)\)

Output

  • Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n \le 100\);
  • Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\);
  • Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^6\);

Example

Test 1

Input
6
9 5 -2 6 -1 1
Output
8

Bình luận


  • -3
    PY2GTranNguyenAnhKhoi 4:45 p.m. 14 Tháng 2, 2024

    sao t time limit, máy vẫn có kết quả đúng mà sao lại time nhỉ?


    • -5
      HoaBanMaTuy 2:51 p.m. 28 Tháng 11, 2023

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • 0
        datdoo1309 10:33 a.m. 2 Tháng 10, 2023
        #include <bits/stdc++.h>
        #define ll long long
        #define endl "\n"
        using namespace std;
        
        const int N = 10000000;
        bool prime[N + 1];
        
        void sieve()
        {
            memset(prime, true, sizeof(prime));
            prime[0] = prime[1] = false;
        
            for (int i = 2; i * i <= N; ++i)
            {
                if (prime[i])
                {
                    for (int j = i * i; j <= N; j += i)
                    {
                        prime[j] = false;
                    }
                }
            }
        }
        
        int main() 
        {
            ios_base::sync_with_stdio(false);
            cin.tie(NULL); cout.tie(NULL);
            sieve();
            int n; cin >> n;
        
            long long a, prefix_sum = 0;
            long long min_val = LLONG_MAX, ans = LLONG_MIN;
        
            for (int i = 0; i < n; ++i) 
            {
                cin >> a; prefix_sum += a;
                if (prime[i + 1]) ans = max(ans, prefix_sum - min_val);
                if (prime[i + 2]) min_val = min(min_val, prefix_sum);
            }
        
            cout << ans << endl;
        
            return 0;
        }
        

        ez


        • 1
          theanhy2007 8:05 a.m. 19 Tháng 9, 2022

          ai có thể giải thích test mẫu sao ra 8 được không ?

          1 phản hồi

          • 0
            VoBaThongL921 9:14 p.m. 14 Tháng 10, 2021 đã chỉnh sửa

            ...

            1 phản hồi