oj.uz

Submission #1113200

# Submission time Handle Problem Language Result Execution time Memory
1113200 2024-11-16T03:39:19 Z HiepVu217 Feast (NOI19_feast) C++17
18 / 100
 51 ms 7496 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define int long long
using namespace std;
const int N = 3e5 + 17;
int n, k;
long long a[N];
pair <long long, int> f[N], m;
inline pair <long long, int> calc (long long c)
{
    f[0] = m = {0, 0};
    for (int i = 1; i <= n; ++i)
    {
        f[i] = f[i - 1];
        if (m.first + a[i] - c > f[i].first || (m.first + a[i] - c == f[i].first && m.second + 1 < f[i].second))
        {
            f[i].first = m.first + a[i] - c;
            f[i].second = m.second + 1;
        }
        if (f[i].first - a[i] > m.first || (f[i].first - a[i] == m.first && f[i].second < m.second))
        {
            m.first = f[i].first - a[i];
            m.second = f[i].second;
        }
    }
    return f[n];
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    long long l = 1, r = 3e14;
    while (l < r)
    {
        long long mid = l + r >> 1;
        m = calc (mid);
        if (m.second == k)
        {
            cout << mid * k + m.first;
            return 0;
        }
        if (m.second > k)
        {
            l = mid + 1;
            continue;
        }
        r = mid - 1;
    }
    long long ans = l * k + calc(l).first;
    cout << ans;
}

Compilation message

feast.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
feast.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
feast.cpp: In function 'int32_t main()':
feast.cpp:43:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         long long mid = l + r >> 1;
      |                         ~~^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 7248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7248 KB Output is correct
2 Correct 28 ms 7492 KB Output is correct
3 Correct 31 ms 7248 KB Output is correct
4 Incorrect 51 ms 7496 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 40 ms 7220 KB Output is correct
2 Correct 44 ms 7240 KB Output is correct
3 Correct 40 ms 7248 KB Output is correct
4 Correct 45 ms 7240 KB Output is correct
5 Correct 48 ms 7252 KB Output is correct
6 Correct 39 ms 7248 KB Output is correct
7 Correct 41 ms 7240 KB Output is correct
8 Correct 40 ms 7248 KB Output is correct
9 Correct 40 ms 7240 KB Output is correct
10 Correct 43 ms 7212 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 7248 KB Output isn't correct
2 Halted 0 ms 0 KB -