oj.uz

Submission #573593

# Submission time Handle Problem Language Result Execution time Memory
573593 2022-06-06T21:44:22 Z danikoynov Feast (NOI19_feast) C++14
63 / 100
 225 ms 14832 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10;

int n;
ll k, a[maxn], dp[maxn][2], cnt[maxn][2], par[maxn];

pair < ll, int > calc(ll cost)
{
    dp[0][1] = -1e18;
    for (int i = 1; i <= n; i ++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = max(dp[i - 1][0] - cost, dp[i - 1][1]) + a[i];
        cnt[i][1] = cnt[i][0] = 0;
        if (dp[i - 1][0] == dp[i][0])
            cnt[i][0] = max(cnt[i][0], cnt[i - 1][0]);
        if (dp[i - 1][1] == dp[i][0])
            cnt[i][0] = max(cnt[i][0], cnt[i - 1][1]);
        if (dp[i - 1][0] - cost + a[i] == dp[i][1])
            cnt[i][1] = max(cnt[i][1], cnt[i - 1][0] + 1);
        if (dp[i - 1][1] + a[i] == dp[i][1])
            cnt[i][1] = max(cnt[i][1], cnt[i - 1][1]);
    }

    //for (int i = 1; i <= n; i ++)
       // cout << dp[i][0] << " - " << dp[i][1] << endl;
        pair < ll, int > ans = {dp[1][0], cnt[1][0]};
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < 2; j ++)
        if (make_pair((ll)dp[i][j], (int)cnt[i][j]) > ans)
            ans = {dp[i][j], cnt[i][j]};
    return ans;
    /**for (int i = 1; i <= n; i ++)
    {
        dp[i] = dp[i - 1];
        cnt[i] = cnt[i - 1];
        for (int j = 1; j <= i; j ++)
        {
            ll sum = dp[j - 1] - cost + par[i] - par[j - 1];
            if (sum > dp[i])
                dp[i] = sum;
            if (sum == dp[i])
                cnt[i] = max(cnt[i], cnt[j - 1] + 1);
        }
    }
    pair < ll, int > ans = {dp[1], cnt[1]};
    for (int i = 2; i <= n; i ++)
        if (make_pair((ll)dp[i], (int)cnt[i]) > ans)
            ans = {dp[i], cnt[i]};
    return ans;*/
}
void solve()
{
    cin >> n >> k;

    ll cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if (a[i] >= 0)
            cnt ++;
        par[i] = par[i - 1] + a[i];
    }
    k = min(cnt, k);

    if (k == 2)
    {
        ll f1 = 0, f2 = 0, pos = -1;
        for (int i = 1; i <= n; i ++)
        {
            if (a[i] < 0)
            {
                pos = i;
                break;
            }
            f1 += a[i];
        }

        for (int i = n; i > 0; i --)
        {
            if (a[i] < 0)
            {
                pos = i;
                break;
            }
            f2 += a[i];
        }

        if (pos == -1)
        {
            cout << f1 << endl;
        }
        else
        {
            if (k == 2)
            cout << f1 + f2 << endl;
            else
                cout << max(f1, max(f2, f1 + f2 + a[pos]));
        }
        return;
    }

    ll lf = 0, rf = 1e12;
    while(lf <= rf)
    {
        ll mf = (lf + rf) / 2;
        pair < double, int > cur = calc(mf);
        if (cur.second >= k)
            lf = mf + 1;
        else
            rf = mf - 1;
    }

    double p1 = lf - 1, p2 = lf;
    pair < ll, int > cur1 = calc(p1), cur2 = calc(p2);
    cur1.first = cur1.first + cur1.second * p1;
    cur2.first = cur2.first + cur2.second * p2;
    double part = 1.0 - (double)(cur1.second - k) / (double)(cur1.second - cur2.second);
    double slope = (cur1.first - cur2.first);
    double ans = cur2.first + slope * part;
    ///cout << cur1.second << " " << cur2.second << " " << part << " " << cur1.second - k << " " << k << endl;
    if (cur1.second == cur2.second)
    {
        cout << cur1.first << endl;
        return;
    }
    cout << (ll)round(ans) << endl;
}

int main()
{
    solve();
    return 0;
}
/**
7 1
3 4 -1 2 3 -5 1
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 14156 KB Output is correct
2 Correct 179 ms 14584 KB Output is correct
3 Correct 225 ms 14744 KB Output is correct
4 Correct 190 ms 14604 KB Output is correct
5 Correct 185 ms 14580 KB Output is correct
6 Correct 195 ms 14304 KB Output is correct
7 Correct 186 ms 14284 KB Output is correct
8 Correct 183 ms 14624 KB Output is correct
9 Correct 194 ms 14356 KB Output is correct
10 Correct 190 ms 14508 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 14372 KB Output is correct
2 Correct 167 ms 14740 KB Output is correct
3 Correct 145 ms 14396 KB Output is correct
4 Incorrect 140 ms 14528 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 14540 KB Output is correct
2 Correct 205 ms 14516 KB Output is correct
3 Correct 214 ms 14664 KB Output is correct
4 Correct 206 ms 14520 KB Output is correct
5 Correct 209 ms 14472 KB Output is correct
6 Correct 207 ms 14764 KB Output is correct
7 Correct 209 ms 14668 KB Output is correct
8 Correct 208 ms 14652 KB Output is correct
9 Correct 209 ms 14832 KB Output is correct
10 Correct 207 ms 14668 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 324 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 352 KB Output is correct
26 Correct 2 ms 452 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 340 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 14156 KB Output is correct
2 Correct 179 ms 14584 KB Output is correct
3 Correct 225 ms 14744 KB Output is correct
4 Correct 190 ms 14604 KB Output is correct
5 Correct 185 ms 14580 KB Output is correct
6 Correct 195 ms 14304 KB Output is correct
7 Correct 186 ms 14284 KB Output is correct
8 Correct 183 ms 14624 KB Output is correct
9 Correct 194 ms 14356 KB Output is correct
10 Correct 190 ms 14508 KB Output is correct
11 Correct 140 ms 14372 KB Output is correct
12 Correct 167 ms 14740 KB Output is correct
13 Correct 145 ms 14396 KB Output is correct
14 Incorrect 140 ms 14528 KB Output isn't correct
15 Halted 0 ms 0 KB -