oj.uz

Submission #735052

# Submission time Handle Problem Language Result Execution time Memory
735052 2023-05-03T12:41:22 Z snowman Stove (JOI18_stove) C++17
50 / 100
 1000 ms 3632 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];
    }
    vl dp1(n + 1), dp2(n + 1);
    fri(1, k + 1){
        dp1[i] = 1;
    }
    fri(2, n + 1){
        dp2[1] = a[i - 1] - a[0]  + 1;
        frj(2, k + 1){
            dp2[j] = min(dp1[j - 1] + 1, dp1[j] + a[i - 1] - a[i - 2]);
        }
        swap(dp2, dp1);
    }
    cout << dp1[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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 396 KB Output is correct
13 Correct 11 ms 392 KB Output is correct
14 Correct 11 ms 392 KB Output is correct
15 Correct 13 ms 388 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 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 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 396 KB Output is correct
13 Correct 11 ms 392 KB Output is correct
14 Correct 11 ms 392 KB Output is correct
15 Correct 13 ms 388 KB Output is correct
16 Correct 18 ms 2652 KB Output is correct
17 Correct 38 ms 2644 KB Output is correct
18 Correct 149 ms 3632 KB Output is correct
19 Execution timed out 1069 ms 3524 KB Time limit exceeded
20 Halted 0 ms 0 KB -