oj.uz

Submission #524487

# Submission time Handle Problem Language Result Execution time Memory
524487 2022-02-09T09:35:43 Z cqtshadow Stove (JOI18_stove) C++14
100 / 100
 161 ms 196420 KB 
#include <bits/stdc++.h>
#define MASK(x) (1LL << x)
#define GETBIT(mask, x) ((mask >> (x))&1)
#define ONBIT(mask, x) (mask | (1LL << (x)))
#define Each(type, i, a, b) for(type i = (a) ; i <= (b) ; ++i)
#define REach(type, i, a, b) for(type i = (a) ; i >= (b) ; --i)
using namespace std;

typedef long long ll;

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const double eps = 1e-9;
const ll oo = 4e18;

template<class X> bool maximize(X &x, X y) {return (x + eps < y ? x = y, true : false);}
template<class X> bool minimize(X &x, X y) {return (x > y + eps ? x = y, true : false);}

void add(int &x, int y) {x += y; if(x >= MOD) x -= MOD;}
void sub(int &x, int y) {x -= y; if(x < 0) x += MOD;}
int radd(int x, int y) {add(x, y); return x;}
int rsub(int x, int y) {sub(x, y); return x;}

string to2(int val) {bitset<10> temp(val); return temp.to_string();}

int n, k;
int t[N];

namespace SUB1 {
    int f[21][21];

    int dp(int pos, int cnt) {
        if(pos > n) return 0;
        if(cnt >= k) return INF;

        int &res = f[pos][cnt];
        if(res != -1) return res;

        res = INF;
        Each(int, i, pos, n)
            minimize(res, dp(i + 1, cnt + 1) + t[i] + 1 - t[pos]);

        return res;
    }

    void solve() {
        memset(f, -1, sizeof f);
        cout << dp(1, 0);
        exit(0);
    }
}

namespace SUB2 {
    ll f[5001][5001];

    ll dp(int pos, int cnt) {
        if(pos > n) return 0;

        ll &res = f[pos][cnt];
        if(res != -1) return res;

        res = dp(pos + 1, cnt) + t[pos] - t[pos - 1];

        if(cnt + 1 <= k)
            minimize(res, dp(pos + 1, cnt + 1) + 1);

        return res;
    }

    void solve() {
        memset(f, -1, sizeof f);
        cout << dp(2, 1) + 1;
        exit(0);
    }
}

namespace SUB3 {
    int a[N];

    void solve() {
        Each(int, i, 1, n - 1)
            a[i] = t[i + 1] - t[i];
        ll ans = t[n] - t[1] + k;
        sort(a + 1, a + n, greater<int>());
        Each(int, i, 1, k - 1)
            ans -= a[i];
        cout << ans;
    }
}

int main() {
//    #ifndef ONLINE_JUDGE
//        freopen("JOI18_stove.inp", "r", stdin);
//        freopen("JOI18_stove.out", "w", stdout);
//    #endif
    ios::sync_with_stdio(false);cin.tie(nullptr);

    cin >> n >> k;
    Each(int, i, 1, n) cin >> t[i];

    if(n <= 20) SUB1::solve();
    if(n <= 5000) SUB2::solve();
    SUB3::solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 70 ms 196260 KB Output is correct
11 Correct 81 ms 196420 KB Output is correct
12 Correct 109 ms 196220 KB Output is correct
13 Correct 140 ms 196228 KB Output is correct
14 Correct 161 ms 196180 KB Output is correct
15 Correct 160 ms 196244 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 70 ms 196260 KB Output is correct
11 Correct 81 ms 196420 KB Output is correct
12 Correct 109 ms 196220 KB Output is correct
13 Correct 140 ms 196228 KB Output is correct
14 Correct 161 ms 196180 KB Output is correct
15 Correct 160 ms 196244 KB Output is correct
16 Correct 16 ms 1988 KB Output is correct
17 Correct 17 ms 1988 KB Output is correct
18 Correct 17 ms 1964 KB Output is correct
19 Correct 19 ms 2040 KB Output is correct
20 Correct 18 ms 1988 KB Output is correct
21 Correct 17 ms 2008 KB Output is correct
22 Correct 16 ms 1988 KB Output is correct
23 Correct 17 ms 1988 KB Output is correct
24 Correct 18 ms 1968 KB Output is correct