Submission #1270990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270990		quangminh412	Feast (NOI19_feast)	C++17	100 / 100	606 ms	20388 KiB

feast

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

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

#define ll long long
#define ldb long double

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 3e5 + 1;

int a[maxn];
int n, k;

pair<ldb, int> compute(ldb pen)
{
    pair<ldb, int> dp[2][n + 1];
    dp[0][1] = {0, 0};
    dp[1][1] = {a[1] - pen, 1};
    for (int i = 2; i <= n; i++)
    {
        dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
        pair<ldb, int> c1, c2;
        c1 = make_pair(dp[0][i - 1].first + a[i] - pen, dp[0][i - 1].second + 1);
        c2 = make_pair(dp[1][i - 1].first + a[i], dp[1][i - 1].second);
        dp[1][i] = max(c1, c2);
    }
    return max(dp[0][n], dp[1][n]);
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    ldb l = 0, r = 3e14;
    for (int i = 0; i < 100; i++)
    {
        ldb mid = (l + r) / 2;
        if (compute(mid).second < k)
            r = mid;
        else
            l = mid;
    }

    ldb pen = l;
    cout << (ll)round(pen * k + compute(pen).first) << '\n';
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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