oj.uz

Submission #1116839

# Submission time Handle Problem Language Result Execution time Memory
1116839 2024-11-22T13:12:32 Z vjudge1 Stove (JOI18_stove) C++17
50 / 100
 270 ms 262144 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

# pragma GCC optimize("O2")
//pragma GCC optimize("my solution")

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 1e9 + 7; //[998244353, 1e9 + 7, 1e9 + 13]

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}

vector<ll> v;
vector<vector<ll>> memo;

ll dp(int i, int k) {
        if (i == v.size() - 1) 
                return 1;

        if (memo[i][k] != -1) 
                return memo[i][k];

        ll ans = INF;
        if (k > 1) 
                ans = min(ans, dp(i + 1, k - 1) + 1);
        ans = min(ans, dp(i + 1, k) + v[i + 1] - v[i]);

        return memo[i][k] = ans;
}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n, k;
        cin >> n >> k;

        v.resize(n + 1);
        memo.resize(n + 1, vector<ll> (k + 1, -1));

        for (int i = 1; i <= n; i ++) 
                cin >> v[i];

        cout << dp(1, k) << "\n";

        return 0;
}

Compilation message

stove.cpp: In function 'long long int dp(int, int)':
stove.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (i == v.size() - 1)
      |             ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 1 ms 336 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 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 1 ms 336 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 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 6 ms 2896 KB Output is correct
12 Correct 52 ms 24028 KB Output is correct
13 Correct 90 ms 47688 KB Output is correct
14 Correct 108 ms 68680 KB Output is correct
15 Correct 111 ms 70960 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 420 KB Output is correct
3 Correct 1 ms 336 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 1 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 848 KB Output is correct
11 Correct 6 ms 2896 KB Output is correct
12 Correct 52 ms 24028 KB Output is correct
13 Correct 90 ms 47688 KB Output is correct
14 Correct 108 ms 68680 KB Output is correct
15 Correct 111 ms 70960 KB Output is correct
16 Correct 32 ms 17508 KB Output is correct
17 Correct 270 ms 87984 KB Output is correct
18 Runtime error 175 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -