제출 #1271782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271782		cbnk32_tuandung	Feast (NOI19_feast)	C++17	22 / 100	24 ms	3912 KiB

feast

#include <bits/stdc++.h>
using namespace std;

/*
run
 g++ FEAST.cpp -std=c++1y -o run.exe && ./run.exe
*/

// CONSTANTs

constexpr int MAX_N = 300000 + 5;

// GIVEN

int N, K;
int A[MAX_N];

// VARIABLEs

// FUNCTIONs

// SUBTASKs

bool checkSub1 = true;
int cntNeg = 0;
bool allNeg = true;

namespace sub1 {
    bool checkInput() {
        return (checkSub1);
    }

    int solve() {
        long long res = 0;
        for (int i = 1; i <= N; ++i) {
            res += A[i];
        }
        cout << res;
        return 0;
    }
}

namespace sub2 {
    bool checkInput() {
        return (cntNeg < 2);
    }
    int solve() {
        long long res = 0;
        for (int i = 1; i <= N; ++i) {
            if (A[i] > 0) res += A[i];
        }
        cout << res;
        return 0;
    }
}

namespace sub3 {
    bool checkInput() {
        return (K == 1);
    }

    long long pre[MAX_N];

    int solve() {
        pre[0] = 0;
        for (int i = 1; i <= N; ++i) {
            pre[i] = pre[i - 1] + A[i];
        }
        long long res = 0;
        long long minPre = 0;
        for (int i = 1; i <= N; ++i) {
            res = max(res, pre[i] - minPre);
            minPre = min(minPre, pre[i]);
        }

        cout << res;

        return 0;
    }
}

// namespace sub45 {
//     bool checkInput() {
//         return (max(K, N) <= 300);
//     }
//     long long dp[309][309];
//     int solve() {
//         for (int i = 1; i <= N; ++i) {
//             dp[i][1] = dp[i - 1][1] + A[i];
//             for (int j = 1; j <= min(K, N); ++j) {

//                 for (int k = 1; k <= )
//             }
//         }
//         return 0;
//     }
// }

// MAIN

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    //freopen("FEAST.INP", "r", stdin);
    //freopen("FEAST.OUT", "w", stdout);

    cin >> N >> K;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        checkSub1 = checkSub1 && (A[i] >= 0);
        if (A[i] < 0) {
            ++cntNeg;
        }
        allNeg = allNeg && (A[i] <= 0);
    }

    if (sub1::checkInput()) return sub1::solve();
    if (sub2::checkInput()) return sub2::solve();
    if (sub3::checkInput()) return sub3::solve();
    if (allNeg) {
        cout << 0;
        return 0;
    }
    // if (sub45::checkInput()) return sub45::solve();
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29