이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const ll INF = 1e17;
struct grp{
char ty;
vi pos;
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
int n = r.size(), m = b.size();
vector<grp> gps;
int api=0, bpi=0;
while(api < n || bpi < m) {
if(api < n && (bpi == m || r[api] < b[bpi])) {
gps.push_back({'r', {}});
while(api < n && (bpi == m || r[api] < b[bpi])) {
gps.back().pos.push_back(r[api]);
++api;
}
} else {
gps.push_back({'b', {}});
while(bpi < m && (api == n || r[api] > b[bpi])) {
gps.back().pos.push_back(b[bpi]);
++bpi;
}
}
}
int l = gps.size();
vi cnt(l);
forR(i, l) cnt[i] = gps[i].pos.size();
vvll dp(l);
forR(i, l) dp[i].resize(cnt[i] + 1);
forR(i, l) {
if(i == 0) {
forR(j, cnt[i]) dp[i][j] = INF;
dp[i][cnt[i]] = 0;
} else {
ll sam = INF;
multiset<ll> lav;
vector<ll> aCh(cnt[i-1] + 1);
forR(las, cnt[i-1] + 1) {
ll cTot = dp[i-1][las];
REP(j, cnt[i-1] - las, cnt[i-1]) cTot += gps[i-1].pos.back() - gps[i-1].pos[j];
cTot += (ll) las * (gps[i].pos.front() - gps[i-1].pos.back());
lav.insert(cTot);
aCh[las] = cTot;
}
forR(bck, cnt[i] + 1) {
if(bck <= cnt[i-1]) {
lav.erase(lav.find(aCh[bck]));
sam = min(sam, aCh[bck] - (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back()));
}
int fwd = cnt[i] - bck;
ll bckTot = 0;
forR(j, bck) bckTot += gps[i].pos[j] - gps[i].pos.front();
dp[i][fwd] = sam + bckTot + (ll) bck * (gps[i].pos.front() - gps[i-1].pos.back());
if(!lav.empty()) {
dp[i][fwd] = min(dp[i][fwd], *lav.begin() + bckTot);
}
}
}
}
return dp[l-1][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... |