الزراعة

الزراعة

الأولمبياد الوطني للبرمجة 2026 - المسابقة التجريبية

الزمن المحدد: 1 ثانية
الذاكرة المحددة: 256 ميجابايت

توجد مزرعة على شكل شبكة مربعة بحجم \(N\times N\). تحتوي الخلية \((i,j)\) على محاصيل قيمتها \(G_{i,j}\). إذا كانت \(G_{i,j}\) سالبة فالمحاصيل فاسدة.

يريد عبدالعزيز والمثنى حصاد شبكتين فرعيتين، حجم كل منهما \(K\times K\)، ولا يجوز أن تتقاطعا. ساعدهما في اختيار الشبكتين بحيث يكون مجموع قيمتيهما أكبر ما يمكن.

ملاحظة 1: الشبكة الفرعية مستطيل فرعي من الشبكة الأصلية.
ملاحظة 2: ستُختار شبكتان بحجم \(K\times K\) لا تتقاطعان.

المدخلات

يحتوي السطر الأول على \(N\) و\(K\)، حيث \(1 \le 2K \le N \le 500\). يحتوي كل من الأسطر \(N\) التالية على \(N\) عددًا يمثل قيم المحاصيل، حيث \(-10^9 \le G_{i,j} \le 10^9\).

المخرجات

اطبع أكبر مجموع ممكن لقيمتي الشبكتين الفرعيتين.

التقييم

المجموعة	القيود	النقاط
\(1\)	\(N=2\)	\(25\)
\(2\)	جميع قيم \(G_{i,j}\) متساوية	\(25\)
\(3\)	\(N=10\)	\(25\)
\(4\)	لا توجد قيود إضافية	\(25\)

أمثلة

المدخلات

2 1
3 1
2 4

المخرجات

7

المدخلات

5 2
1 2 3 4 5
5 4 2 1 3
2 3 1 4 5
4 1 5 2 3
3 5 4 1 2

المخرجات

29

الحل

احسب مجموع كل شبكة فرعية \(K\times K\) باستخدام المجاميع التراكمية ثنائية الأبعاد. لا بد أن تفصل بين مستطيلين غير متقاطعين جهة أفقية أو رأسية. خزّن أفضل شبكة تبدأ في كل صف، ثم استخدم أكبر القيم التراكمية من البداية والنهاية لإيجاد أفضل زوج لا تتداخل فترتا صفوفه. كرر الفكرة للأعمدة. التعقيد الزمني والذاكرة \(O(N^2)\).

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
        int n, k;
        cin >> n >> k;

        vector<vector<long long>> prefix(n + 1, vector<long long>(n + 1));

        for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                        long long x;
                        cin >> x;
                        prefix[i][j] = x + prefix[i - 1][j] + prefix[i][j - 1]
                                                        - prefix[i - 1][j - 1];
                }
        }

        int m = n - k + 1;
        const long long NEG = -(1LL << 62);
        vector<long long> rowBest(m, NEG), colBest(m, NEG);

        for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                        int bottom = i + k;
                        int right = j + k;
                        long long sum = prefix[bottom][right] - prefix[i][right]
                                                    - prefix[bottom][j] + prefix[i][j];
                        rowBest[i] = max(rowBest[i], sum);
                        colBest[j] = max(colBest[j], sum);
                }
        }

        auto bestSeparated = [&](const vector<long long>& best) {
                vector<long long> pref(m), suff(m);
                pref[0] = best[0];
                for (int i = 1; i < m; i++) {
                        pref[i] = max(pref[i - 1], best[i]);
                }

                suff[m - 1] = best[m - 1];
                for (int i = m - 2; i >= 0; i--) {
                        suff[i] = max(suff[i + 1], best[i]);
                }

                long long answer = NEG;
                for (int i = 0; i + k < m; i++) {
                        answer = max(answer, pref[i] + suff[i + k]);
                }
                return answer;
        };

        cout << max(bestSeparated(rowBest), bestSeparated(colBest)) << '\n';
}