Submission #1356176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356176		pqhxapple	Stove (JOI18_stove)	C++20	50 / 100	132 ms	196532 KiB

stove

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b)        for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b)       for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n)           for (int i = (0), _n = (n); i < _n; ++i)
#define MASK(x)             (1LL << (x))
#define ON(mask, i)         (((mask) >> (i)) & (1LL))
#define ALL(x)              begin(x), end(x)
#define el                  cout << '\n'

template <class X, class Y> inline bool maximize(X &x, const Y &y) { return (x < y) ? x = y, 1 : 0; }
template <class X, class Y> inline bool minimize(X &x, const Y &y) { return (x > y) ? x = y, 1 : 0; }

constexpr int MAXN = 1e5 + 10;
int n, k;
int a[MAXN];

void load_input(void)
{
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
}

namespace subtask2
{
    long long dp[5005][5005];

    void solve(void)
    {
        if (!(n <= 5e3)) return;

        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;

        FOR(z, 1, k)
        {
            long long cur = -a[1];
            FOR(i, 1, n)
            {
                minimize(dp[i][z], cur + a[i] + 1);
                minimize(cur, dp[i][z - 1] - a[i + 1]);
            }
        }

        cout << dp[n][k] << '\n';

        cerr << "[2]\n";
        exit(0);
    }
}

void process(void)
{

    subtask2::solve();
}

signed main(void)
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);

    #define task "A"
    if (fopen(task".INP", "r"))
    {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int testcase = 1;
    while (testcase--)
    {
        load_input();
        process();
    }

    return 1 ^ 1;
}

Compilation message (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50