oj.uz

Submission #888969

# Submission time Handle Problem Language Result Execution time Memory
888969 2023-12-18T13:46:22 Z Deaddog Stove (JOI18_stove) C++17
50 / 100
 141 ms 262144 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int INF =1e9;
signed main()
{
    int n, k;
    cin >> n >> k;
    vector <int> x(n);
    for(int i=0; i<n;i++)
    {
        cin >> x[i];
    }
    sort(x.begin(), x.end());
    vector<vector<int>>dp(n, vector<int>(k+1, INF));
    for(int i=0;i<n;i++)
    {
        dp[i][0] = INF;
    }
    dp[0][1] = 1;
    for(int i=1; i<n;i++)
    {
        for(int j=1;j<=k&&j<=i+1;j++)
        {
            dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+x[i]-x[i-1]);
        }
    }
    cout << dp[n-1][k];
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 14 ms 23896 KB Output is correct
13 Correct 26 ms 47452 KB Output is correct
14 Correct 34 ms 68700 KB Output is correct
15 Correct 35 ms 70604 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 14 ms 23896 KB Output is correct
13 Correct 26 ms 47452 KB Output is correct
14 Correct 34 ms 68700 KB Output is correct
15 Correct 35 ms 70604 KB Output is correct
16 Correct 37 ms 13716 KB Output is correct
17 Correct 78 ms 84048 KB Output is correct
18 Runtime error 141 ms 262144 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -