oj.uz

Submission #573591

# Submission time Handle Problem Language Result Execution time Memory
573591 2022-06-06T21:41:41 Z danikoynov Feast (NOI19_feast) C++14
63 / 100
 226 ms 17416 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);



    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 183 ms 13840 KB Output is correct
2 Correct 194 ms 16944 KB Output is correct
3 Correct 198 ms 17248 KB Output is correct
4 Correct 193 ms 17100 KB Output is correct
5 Correct 209 ms 17044 KB Output is correct
6 Correct 195 ms 16680 KB Output is correct
7 Correct 181 ms 16692 KB Output is correct
8 Correct 191 ms 17020 KB Output is correct
9 Correct 183 ms 16788 KB Output is correct
10 Correct 186 ms 16996 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 14032 KB Output is correct
2 Correct 141 ms 15408 KB Output is correct
3 Correct 148 ms 15224 KB Output is correct
4 Incorrect 152 ms 15284 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 14204 KB Output is correct
2 Correct 208 ms 16956 KB Output is correct
3 Correct 209 ms 17204 KB Output is correct
4 Correct 226 ms 16972 KB Output is correct
5 Correct 209 ms 17068 KB Output is correct
6 Correct 218 ms 17308 KB Output is correct
7 Correct 214 ms 17356 KB Output is correct
8 Correct 207 ms 17104 KB Output is correct
9 Correct 226 ms 17416 KB Output is correct
10 Correct 214 ms 17376 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 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 0 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 0 ms 212 KB Output is correct
16 Correct 1 ms 212 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 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 0 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 0 ms 212 KB Output is correct
16 Correct 1 ms 212 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 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 2 ms 340 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 183 ms 13840 KB Output is correct
2 Correct 194 ms 16944 KB Output is correct
3 Correct 198 ms 17248 KB Output is correct
4 Correct 193 ms 17100 KB Output is correct
5 Correct 209 ms 17044 KB Output is correct
6 Correct 195 ms 16680 KB Output is correct
7 Correct 181 ms 16692 KB Output is correct
8 Correct 191 ms 17020 KB Output is correct
9 Correct 183 ms 16788 KB Output is correct
10 Correct 186 ms 16996 KB Output is correct
11 Correct 140 ms 14032 KB Output is correct
12 Correct 141 ms 15408 KB Output is correct
13 Correct 148 ms 15224 KB Output is correct
14 Incorrect 152 ms 15284 KB Output isn't correct
15 Halted 0 ms 0 KB -