This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// He was a moth to the flame
// She was holding the matches
// Soon, she's gonna find stealing other people's toys
// On the playground won't make you many friends
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;
const ll inf = 1e18;
const int maxn = 41;
// dp[vyska v ktorej som][pocet zadarmo hran][najmensie Ci][pocet tych, co prisli na tuto vysku zdola][najmensie Ci medzi nimi] = minimalna cena
ll dp[2][maxn][maxn][maxn];
void clear(int i)
{
for (int a = 0; a < maxn; a++) for (int b = 0; b < maxn; b++)
for (int c = 0; c < maxn; c++)
dp[i][a][b][c] = inf;
}
void upd(ll& a, ll b)
{
a = min(a, b);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
ll k;
cin >> n >> k;
vector<int> hi(n), ci(n);
vector<ll> cs;
for (int i = 0; i < n; i++) cin >> hi[i] >> ci[i], cs.push_back(ci[i]);
cs.push_back(inf);
sort(cs.begin(), cs.end());
for (int i = 0; i < n; i++) ci[i] = lower_bound(cs.begin(), cs.end(), ci[i]) - cs.begin();
int h = *max_element(hi.begin(), hi.end()) + n + 2;
vector<int> cnth(h);
vector<int> minc(h, n);
for (int i = 0; i < n; i++) cnth[hi[i]]++, minc[hi[i]] = min(minc[hi[i]], ci[i]);
ll ans = inf;
int mini = *min_element(hi.begin(), hi.end());
int maxi = *max_element(hi.begin(), hi.end());
clear(mini & 1);
dp[mini & 1][1][minc[mini]][cnth[mini] - 1] = ((ll)(cnth[mini] - 1)) * k;
for (int h2 = mini; h2 + 1 < h; h2++) // robime prechody na ten o jeden viac
{
int pv = h2 & 1, nw = (h2 + 1) & 1;
clear(nw);
for (int z = 0; z <= n; z++) for (int c = 0; c <= n; c++)
for (int up = 0; up <= n; up++) if (dp[pv][z][c][up] != inf)
{
int total = up + cnth[h2 + 1];
if (!total)
{
if (h2 >= maxi) upd(ans, dp[pv][z][c][up]);
upd(dp[nw][z][c][total], dp[pv][z][c][up]);
continue;
}
for (int stay = 1; stay <= total; stay++) // pocet tych co tu ostanu
{
int z2 = max(stay, z);
int c2 = min(c, minc[h2 + 1]);
int up2 = total - stay;
ll cena = dp[pv][z][c][up] + max(0ll, (ll)(stay - z)) * 1ll * cs[c] + ((ll)up2) * k;
upd(dp[nw][z2][c2][up2], cena);
}
}
}
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |