oj.uz

Submission #1113197

# Submission time Handle Problem Language Result Execution time Memory
1113197 2024-11-16T03:29:39 Z HiepVu217 Feast (NOI19_feast) C++17
18 / 100
 74 ms 8700 KB 
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
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];
}
int 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 >> 1;
        if (calc(mid).second >= k)
        {
            l = mid;
            continue;
        }
        r = mid - 1;
    }
    long long ans = k * l + 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 'int main()':
feast.cpp:42:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         long long mid = l + r + 1 >> 1;
      |                         ~~~~~~^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 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 36 ms 7260 KB Output is correct
2 Correct 37 ms 8268 KB Output is correct
3 Correct 35 ms 7248 KB Output is correct
4 Incorrect 37 ms 8016 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 69 ms 7248 KB Output is correct
2 Correct 61 ms 7508 KB Output is correct
3 Correct 60 ms 7240 KB Output is correct
4 Correct 74 ms 7208 KB Output is correct
5 Correct 60 ms 7380 KB Output is correct
6 Correct 66 ms 8700 KB Output is correct
7 Correct 62 ms 7256 KB Output is correct
8 Correct 60 ms 7248 KB Output is correct
9 Correct 62 ms 7504 KB Output is correct
10 Correct 61 ms 7400 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

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