Submission #1107146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107146		trnthienphc2003	Stove (JOI18_stove)	C++17	100 / 100	37 ms	4688 KiB

stove

#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e6 + 7;
int n, k;
int t[maxn];

void input() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> t[i];
    }
}

namespace sub1 {
    bool check() {
        return n <= 20 && *max_element(t + 1, t + 1 + n) <= 20;
    }

    int backtrack(int last_seg, int num_seg) {
        if(last_seg == n) return 0;
        int ans = 0;
        if(num_seg < k) ans = max(ans, backtrack(last_seg + 1, num_seg + 1) + t[last_seg + 1] - t[last_seg] - 1);
        ans = max(ans, backtrack(last_seg + 1, num_seg));
        return ans;
    }

    int solve() {
        cout << t[n] + 1 - t[1] - backtrack(1, 1);
        return 0;
    }
}

namespace sub2 {
    bool check() {
        return n <= 5000;
    }

    int solve() {
        long long ans = t[n] + 1 - t[1];
        priority_queue <long long> pq;
        for(int i = 2; i <= n; ++i) {
            pq.push(t[i] - t[i - 1] - 1);
        }

        int cnt = 1;
        while(cnt < k && !pq.empty()) {
            ans -= pq.top();
            pq.pop();
            cnt++;
        }

        cout << ans;
        return 0;
    }
}

namespace sub3 {
    bool check() {
        return n <= 1e6;
    }

    int solve() {
        // cout << "sub3\n";
        long long ans = t[n] + 1 - t[1];
        priority_queue <long long> pq;
        for(int i = 2; i <= n; ++i) {
            pq.push(t[i] - t[i - 1] - 1);
        }

        int cnt = 1;
        while(cnt < k && !pq.empty()) {
            ans -= pq.top();
            pq.pop();
            cnt++;
        }

        cout << ans;
        return 0;
    }
}

#define NAME "test"
int main() {
    if(fopen(NAME".txt", "r")) {
        freopen(NAME".txt", "r", stdin);
    }

    input();

    if(sub1::check()) return sub1::solve();
    if(sub2::check()) return sub2::solve();
    if(sub3::check()) return sub3::solve();
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(NAME".txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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