oj.uz

답안 #601038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601038 2022-07-21T10:23:58 Z pakhomovee Stove (JOI18_stove) C++17
100 / 100
 795 ms 8948 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define int long long
const int maxn = 100'001;
const int inf = 1e18;
int dp[maxn];
int dp1[maxn];

pair<int, int> eval(int lambda, vector<int> &t) {
    const int n = t.size();
    fill(dp, dp + maxn, inf);
    fill(dp1, dp1 + maxn, inf);
    dp[0] = 0;
    dp1[0] = 0;
    set<pair<int, int>> s;
    for (int i = 1; i <= n; ++i) {
        s.insert({ dp[i - 1] - t[i - 1] + 1 + lambda, dp1[i - 1] });
        auto [val, cnt] = *s.begin();
        dp[i] = val + t[i - 1];
        dp1[i] = cnt + 1;
    }
    return { dp[n], dp1[n] };
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> t(n);
    for (int& i : t) {
        cin >> i;
    }
    int l = -1, r = 2e9;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (eval(m, t).second > k) {
            l = m;
        } else {
            r = m;
        }
    }
    auto [a, b] = eval(r, t);
    cout << a - k * r;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 4 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 3 ms 1876 KB Output is correct
5 Correct 3 ms 1876 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 4 ms 1876 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 4 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 3 ms 1876 KB Output is correct
5 Correct 3 ms 1876 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 4 ms 1876 KB Output is correct
10 Correct 17 ms 2096 KB Output is correct
11 Correct 15 ms 2096 KB Output is correct
12 Correct 16 ms 2100 KB Output is correct
13 Correct 16 ms 2004 KB Output is correct
14 Correct 13 ms 2100 KB Output is correct
15 Correct 13 ms 2004 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 4 ms 1876 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 3 ms 1876 KB Output is correct
5 Correct 3 ms 1876 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 4 ms 1876 KB Output is correct
10 Correct 17 ms 2096 KB Output is correct
11 Correct 15 ms 2096 KB Output is correct
12 Correct 16 ms 2100 KB Output is correct
13 Correct 16 ms 2004 KB Output is correct
14 Correct 13 ms 2100 KB Output is correct
15 Correct 13 ms 2004 KB Output is correct
16 Correct 795 ms 8564 KB Output is correct
17 Correct 684 ms 8656 KB Output is correct
18 Correct 671 ms 8900 KB Output is correct
19 Correct 660 ms 8816 KB Output is correct
20 Correct 624 ms 8948 KB Output is correct
21 Correct 536 ms 8928 KB Output is correct
22 Correct 598 ms 8924 KB Output is correct
23 Correct 611 ms 8824 KB Output is correct
24 Correct 573 ms 8924 KB Output is correct