Submission #1311610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311610		jcasti	Feast (NOI19_feast)	C++17	0 / 100	67 ms	2716 KiB

feast

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define eat cin
#define big long long
#define endl "\n"

int n, K;
big A[300005];
tuple<int,int> solve_opt(big l) {
    // dp[i][bool] = max value of i if in subarray
    tuple<big, big> dp[2] = {make_tuple(0,0), make_tuple(A[0] - l,-1)};

    for (int i = 1; i < n; i++) {
        tuple<big,big> tmp = max(dp[0], dp[1]);
        tuple<big,big> tmp1 = max(
            make_tuple(get<0>(dp[0]) + A[i] - l, get<1>(dp[0]) - 1), //dp[0][0] + A[i] - l, dp[0][1] - 1
            make_tuple(get<0>(dp[1]) + A[i], get<1>(dp[1])) // dp[1][0] + A[i], dp[1][1]
        );

        dp[0] = tmp;
        dp[1] = tmp1;
    }
    return max(dp[0], dp[1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    eat.tie(NULL);

    eat >> n >> K;

    for (int i = 0; i < n; i++) {
        big ai;
        eat >> ai;
        A[i] = ai;
    }

    big lo = 0;
    big hi = 3e14 + 1;
    tuple<big,big> res;
    while (lo < hi) {
        big mid = lo + (hi -lo)/2;
        res = solve_opt(mid);
        big kp = -1*get<1>(res);
        if (kp > K) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    res = solve_opt(lo);
    cout << get<0>(res) + K*lo << endl; 

    return 0;
}

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