oj.uz

Submission #735048

# Submission time Handle Problem Language Result Execution time Memory
735048 2023-05-03T12:16:37 Z snowman Stove (JOI18_stove) C++17
50 / 100
 122 ms 262144 KB 
#include <bits/stdc++.h>
//Soltan Cristian
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
using ml = map<ll, ll>;
using vii = vector<vector<int>>;
using vll = vector<vector<ll>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T>void print(T n, T m, vector<vector<T>> &dp){fri(0, n){ct('\n');frj(0, m){ct(setw(5));cts(dp[i][j]);}}}



const int mxa = 1e9 + 1;
// string __fname = "exclusiv";  
// ifstream in(__fname + ".in"); 
// ofstream out (__fname + ".out"); 
// #define cin in 
// #define cout out


void solve(){
	ll n, k;
    cin >> n >> k;
    vl a(n);
    fri(0, n){
        cin >> a[i];
    }
    vll dp(n + 1, vl(k + 1));
    dp[1][1] = 1;
    fri(2, n + 1){
        dp[i][1] = a[i - 1] - a[0] + 1; 
    }
    fri(1, k + 1){
        dp[1][i] = 1;
    }
    fri(2, n + 1){
        frj(2, k + 1){
            dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i- 1][j] + a[i - 1] - a[i - 2]);
        }
    }
    cout << dp[n][k] << '\n';

}


int main()
{   
    ios_base::sync_with_stdio(0); cin.tie(0); ct(fixed); ct(setprecision(10)); 
    // int t;
    // cin >> t;
    // while(t--)
        solve();
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 15 ms 23884 KB Output is correct
13 Correct 33 ms 47396 KB Output is correct
14 Correct 39 ms 68628 KB Output is correct
15 Correct 40 ms 70620 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 15 ms 23884 KB Output is correct
13 Correct 33 ms 47396 KB Output is correct
14 Correct 39 ms 68628 KB Output is correct
15 Correct 40 ms 70620 KB Output is correct
16 Correct 21 ms 13760 KB Output is correct
17 Correct 63 ms 84164 KB Output is correct
18 Runtime error 122 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -