oj.uz

Submission #524425

# Submission time Handle Problem Language Result Execution time Memory
524425 2022-02-09T08:00:55 Z cqtshadow Stove (JOI18_stove) C++14
50 / 100
 157 ms 196408 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;
    }
}

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();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 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 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 79 ms 196184 KB Output is correct
11 Correct 82 ms 196292 KB Output is correct
12 Correct 108 ms 196408 KB Output is correct
13 Correct 140 ms 196296 KB Output is correct
14 Correct 154 ms 196312 KB Output is correct
15 Correct 157 ms 196292 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 320 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 79 ms 196184 KB Output is correct
11 Correct 82 ms 196292 KB Output is correct
12 Correct 108 ms 196408 KB Output is correct
13 Correct 140 ms 196296 KB Output is correct
14 Correct 154 ms 196312 KB Output is correct
15 Correct 157 ms 196292 KB Output is correct
16 Incorrect 10 ms 1632 KB Output isn't correct
17 Halted 0 ms 0 KB -