# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1107145 | 2024-10-31T17:53:33 Z | trnthienphc2003 | Stove (JOI18_stove) | C++17 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 | - |