oj.uz

Submission #545505

# Submission time Handle Problem Language Result Execution time Memory
545505 2022-04-04T16:35:44 Z MohamedAliSaidane Stove (JOI18_stove) C++14
50 / 100
 124 ms 100172 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

#define pb push_back
#define popb pop_back
#define pf push_front
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second

int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
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);}

const int MAX_N = 5004;
int n, k;
vll A;
int dp[MAX_N][MAX_N];
int f(int i, int j)
{
    if(dp[i][j] != -1)
        return dp[i][j];
    if(i == n-1)
        return dp[i][j] = 0;
    int ans = f(i+1,j) + A[i+1] - A[i];
    if(j > 0)
        return dp[i][j] = min(ans,f(i+1,j-1)+1);
    return dp[i][j] = ans;
}
void solve()
{
    memset(dp,-1,sizeof(dp));
    cin >> n >> k;
    A.assign(n,0);
    for(int i = 0; i < n ; i ++)
        cin >> A[i];
    sort(all(A));
    cout << f(0,k-1) + 1;

}

int main()
{
    ios::sync_with_stdio(false);
    int tt  = 1;
    while(tt--)
        solve();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98260 KB Output is correct
2 Correct 40 ms 98236 KB Output is correct
3 Correct 41 ms 98260 KB Output is correct
4 Correct 46 ms 98200 KB Output is correct
5 Correct 37 ms 98252 KB Output is correct
6 Correct 37 ms 98248 KB Output is correct
7 Correct 37 ms 98280 KB Output is correct
8 Correct 36 ms 98276 KB Output is correct
9 Correct 37 ms 98240 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98260 KB Output is correct
2 Correct 40 ms 98236 KB Output is correct
3 Correct 41 ms 98260 KB Output is correct
4 Correct 46 ms 98200 KB Output is correct
5 Correct 37 ms 98252 KB Output is correct
6 Correct 37 ms 98248 KB Output is correct
7 Correct 37 ms 98280 KB Output is correct
8 Correct 36 ms 98276 KB Output is correct
9 Correct 37 ms 98240 KB Output is correct
10 Correct 39 ms 98444 KB Output is correct
11 Correct 43 ms 98384 KB Output is correct
12 Correct 70 ms 98456 KB Output is correct
13 Correct 124 ms 98500 KB Output is correct
14 Correct 101 ms 98440 KB Output is correct
15 Correct 101 ms 98372 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 98260 KB Output is correct
2 Correct 40 ms 98236 KB Output is correct
3 Correct 41 ms 98260 KB Output is correct
4 Correct 46 ms 98200 KB Output is correct
5 Correct 37 ms 98252 KB Output is correct
6 Correct 37 ms 98248 KB Output is correct
7 Correct 37 ms 98280 KB Output is correct
8 Correct 36 ms 98276 KB Output is correct
9 Correct 37 ms 98240 KB Output is correct
10 Correct 39 ms 98444 KB Output is correct
11 Correct 43 ms 98384 KB Output is correct
12 Correct 70 ms 98456 KB Output is correct
13 Correct 124 ms 98500 KB Output is correct
14 Correct 101 ms 98440 KB Output is correct
15 Correct 101 ms 98372 KB Output is correct
16 Incorrect 52 ms 100172 KB Output isn't correct
17 Halted 0 ms 0 KB -