oj.uz

Submission #1107145

# Submission time Handle Problem Language Result Execution time Memory
1107145 2024-10-31T17:53:33 Z trnthienphc2003 Stove (JOI18_stove) C++17
50 / 100
 29 ms 4552 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Incorrect 29 ms 4552 KB Output isn't correct
17 Halted 0 ms 0 KB -