oj.uz

Submission #549672

# Submission time Handle Problem Language Result Execution time Memory
549672 2022-04-16T09:40:14 Z armashka Stove (JOI18_stove) C++17
50 / 100
 530 ms 262144 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define nano chrono::steady_clock::now().time_since_epoch().count()
#define uid uniform_int_distribution<int>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz() size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
    
const int N = 1e5 + 10;
const int M = 1e7 + 5;
const ll inf = 1e15;
ll mod = 1e9 + 7;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll random(ll l, ll r) { mt19937 rnd(nano); uid dist(l, r); return dist(rnd); }
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }                                   
bool even(ll n) { return (n % 2 == 0); }

ll n, k, a[5005], dp[5005][5005], mn[5005];

const void solve(/*Armashka*/) {
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    for (int i = 1; i <= n; ++ i) {
        for (int j = 2; j <= k; ++ j) dp[i][j] = inf;
        dp[i][1] = a[i] + 1 - a[1];
        mn[i] = inf;
    }
    mn[1] = dp[0][1] + 1 - a[1];
    for (int i = 2; i <= n; ++ i) {
        mn[1] = min(mn[1], dp[i - 1][1] - a[i] + 1);
        for (int j = 2; j <= k; ++ j) {
            mn[j] = min(mn[j], dp[i - 1][j] - a[i] + 1);
            dp[i][j] = min(dp[i][j], a[i] + mn[j - 1]);
        }
    }
    ll ans = inf;
    for (int i = 1; i <= k; ++ i) ans = min(ans, dp[n][i]);
    cout << ans;
}

signed main() {
    srand(time(NULL));
    fast;
    // file("");
    int tt = 1;

    // cin >> tt;
    for (int i = 1; i <= tt; ++ i) {
        solve();
    }        
}
// Jelbiretip kok tudy, boys in the hood
// Kim qandai juz, kimde qandai ru

Compilation message

stove.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 368 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 6 ms 12796 KB Output is correct
11 Correct 7 ms 14932 KB Output is correct
12 Correct 22 ms 36052 KB Output is correct
13 Correct 37 ms 59476 KB Output is correct
14 Correct 53 ms 80448 KB Output is correct
15 Correct 54 ms 82644 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 368 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 6 ms 12796 KB Output is correct
11 Correct 7 ms 14932 KB Output is correct
12 Correct 22 ms 36052 KB Output is correct
13 Correct 37 ms 59476 KB Output is correct
14 Correct 53 ms 80448 KB Output is correct
15 Correct 54 ms 82644 KB Output is correct
16 Runtime error 530 ms 262144 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -