oj.uz

Submission #735055

# Submission time Handle Problem Language Result Execution time Memory
735055 2023-05-03T12:43:29 Z snowman Stove (JOI18_stove) C++17
50 / 100
 1000 ms 2664 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, 1), dp2(n + 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 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 12 ms 392 KB Output is correct
14 Correct 15 ms 340 KB Output is correct
15 Correct 13 ms 340 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 12 ms 392 KB Output is correct
14 Correct 15 ms 340 KB Output is correct
15 Correct 13 ms 340 KB Output is correct
16 Correct 15 ms 2644 KB Output is correct
17 Correct 24 ms 2644 KB Output is correct
18 Correct 177 ms 2664 KB Output is correct
19 Execution timed out 1069 ms 2652 KB Time limit exceeded
20 Halted 0 ms 0 KB -