제출 #1304585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304585		huyenphuong	Feast (NOI19_feast)	C++20	100 / 100	127 ms	8652 KiB

feast

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define bit(i, x) ((x >> i) & 1)
#define MAX(x, y) x = max(x, y)
#define MIN(x, y) x = min(x, y)
#define For(i, l, u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))

#define INF 1000000007
#define Task "ontap"
#define maxn 300002
using namespace std;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
const double eps = 1e-9;

int n, k, a[maxn];
ll sum[maxn];
pair<ll, int> f[maxn];
pair<ll, int> solve(ll lambda)
{
    f[0] = mp(0, 0);
    pair<ll, int> maxx = mp(0, 0);
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1];
        ll curf = sum[i] + maxx.F - lambda;
        int curg = maxx.S + 1;

        if (curf > f[i].F)
            f[i] = mp(curf, curg);
        else if (curf == f[i].F)
            MIN(f[i].S, curg);

        if (maxx.F < f[i].F - sum[i])
            maxx = mp(f[i].F - sum[i], f[i].S);
        else if (maxx.F == f[i].F - sum[i])
            MIN(maxx.S, f[i].S);
    }
    return f[n];
}
ll tinh()
{
    ll lo = -1, hi = 1e15;
    while (hi - lo > 1)
    {
        ll mid = (hi + lo)/2;
        auto [val, g] = solve(mid);
        if (g <= k) hi = mid;
        else lo = mid;
    }
    auto [val, g] = solve(hi);
    return val + 1LL * hi * k;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(Task".INP", "r"))
    {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    cout << tinh();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'int main()':
feast.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(Task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(Task".OUT", "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