| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 418422 | EncryptingWolf | 모임들 (IOI18_meetings) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <iostream>
#include <queue>
typedef long long ll;
#define FOR(i,x,y) for (ll i = x; i<y; i++)
using namespace std;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
vector<ll> ou;
FOR(Z, 0, L.size())
{
vector<pair<ll, ll>> monSL;
vector<pair<ll, ll>> monSR;
vector<ll> distL;
vector<ll> distR;
vector<int> nH;
FOR(i, L[Z], R[Z] + 1)
{
nH.push_back(H[i]);
}
distL.resize(nH.size());
distR.resize(nH.size());
FOR(i, 0,nH.size())
{
while (true)
{
if (monSL.size() == 0)
break;
else
{
if (nH[i] < monSL[monSL.size() - 1].first)
{
break;
}
}
monSL.pop_back();
}
monSL.push_back({ nH[i],i });
if (monSL.size() == 1)
{
distL[i] = monSL[0].first*(i + 1);
}
else
{
distL[i] = monSL[monSL.size() - 1].first*(monSL[monSL.size() - 1].second - monSL[monSL.size() - 2].second) + distL[monSL[monSL.size() - 2].second];
}
}
reverse(nH.begin(),nH.end());
FOR(i, 0, nH.size())
{
while (true)
{
if (monSR.size() == 0)
break;
else
{
if (nH[i] < monSR[monSR.size() - 1].first)
{
break;
}
}
monSR.pop_back();
}
monSR.push_back({ nH[i],i });
if (monSR.size() == 1)
{
distR[i] = monSR[0].first*(i + 1);
}
else
{
distR[i] = monSR[monSR.size() - 1].first*(monSR[monSR.size() - 1].second - monSR[monSR.size() - 2].second) + distR[monSR[monSR.size() - 2].second];
}
}
reverse(nH.begin(), nH.end());
reverse(distR.begin(), distR.end());
ll mi = 1e9;
FOR(i, 0, nH.size())
mi = min(mi, distL[i] + distR[i]-nH[i]);
ou.push_back(mi);
}
FOR(i, 0, ou.size())
{
cout << ou[i] << ' ';
}
return ou;
}