Submission #1247257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247257		fifekkk	Feast (NOI19_feast)	C++20	100 / 100	113 ms	14116 KiB

feast

#include <cstdlib>
#include <bitset>
#include <functional>
#include <utility>
#include <chrono>
#include <tuple>
#include <new>
#include <memory>
#include <climits>
#include <cfloat>
#include <cinttypes>
#include <exception>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>
#include <valarray>
#include <ios>
#include <istream>
#include <ostream>
#include <iostream>
#include <fstream>
#include <streambuf>
#include <cstdio>
#include <thread>
// #include <bits/stdc++.h>
using namespace std;

long long wartosci[1000005];
int n, k;
int licz;
long long akt_wyn;
pair<long long, int> dynamik[2][1000005]; // 0 nie wzialem, 1 wzialem

pair<long long, int> policz_dla_m(long long m)
{
    dynamik[1][0] = {-1e18, 0};
    for (int i = 1; i <= n; i++)
    {
        if (dynamik[0][i - 1].first > dynamik[1][i - 1].first)
            dynamik[0][i] = dynamik[0][i - 1];
        else if (dynamik[0][i - 1].first < dynamik[1][i - 1].first)
            dynamik[0][i] = dynamik[1][i - 1];
        else
            dynamik[0][i] = (dynamik[0][i - 1].second > dynamik[1][i - 1].second ? dynamik[0][i - 1] : dynamik[1][i - 1]);

        dynamik[1][i] = dynamik[0][i - 1];
        dynamik[1][i].second++;
        dynamik[1][i].first -= m;

        if (dynamik[1][i - 1].first > dynamik[1][i].first || (dynamik[1][i - 1].first == dynamik[1][i].first && dynamik[1][i - 1].second > dynamik[1][i].second))
            dynamik[1][i] = dynamik[1][i - 1];

        dynamik[1][i].first += wartosci[i];
    }

    if (dynamik[0][n].first > dynamik[1][n].first)
        return dynamik[0][n];
    else if (dynamik[0][n].first < dynamik[1][n].first)
        return dynamik[1][n];
    else
        return (dynamik[0][n].second > dynamik[1][n].second ? dynamik[0][n] : dynamik[1][n]);



}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> wartosci[i];

    long long l, p;

    l = 0;
    p = 1e17;

    while (l < p)
    {
        long long akt_m = ((l + p) / 2) + 1;

        auto para = policz_dla_m(akt_m);
        tie(akt_wyn, licz) = para;

        if (licz >= k)
            l = akt_m;
        else
            p = akt_m - 1;
    }

    auto para = policz_dla_m(l);
    tie(akt_wyn, licz) = para;

    akt_wyn += ((long long)licz) * l;
    cout << akt_wyn;
}

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