Submission #226625

#	Time	Username	Problem	Language	Result	Execution time	Memory
226625		Nayna	Stove (JOI18_stove)	C++14	20 / 100	1081 ms	196500 KiB

stove

#include <bits/stdc++.h>

using namespace std;

const int mxn = 5e3+5;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

#define  sf scanf
#define  pf printf

#define  input freopen("in.txt","r",stdin)
#define  output freopen("out.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))


int  Set(int N,int pos){return N=N | (1<<pos);}
int  reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}


ll dp[mxn][mxn];
ll arr[mxn];
ll n;

ll solve(int pos, int k)
{
    if(!k)
    {
        if(pos<n) return inf;
        if(pos>=n) return 0;
    }
    if(pos>=n) return 0;
    if(dp[pos][k]!=-1) return dp[pos][k];
    ll res = inf;
    for(int i = pos+1; i <= n; i++) res = min(res, solve(i, k-1)+arr[i]+1-arr[pos+1]);
    return dp[pos][k] = res;
}
int main()
{
    ll k;
    cin >> n >> k;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    memset(dp, -1, sizeof dp);
    ll ans = solve(0, k);
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50