| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 673250 | abysmal | Sightseeing in Kyoto (JOI22_kyoto) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;
const int64_t INF = 1e18;
const int64_t mINF = 1e9;
const int64_t MOD = 998244353;
const int nbit = 11;
const int ndig = 10;
const int nchar = 26;
const int D = 4;
int dr[D] = {0, 1, 0, -1};
int dc[D] = {1, 0, -1, 0};
struct Monsta
{
int64_t h;
int64_t p;
Monsta(int64_t h_, int64_t p_) : h(h_), p(p_) {}
bool operator < (const Monsta& o)
{
return p < o.p;
}
};
struct Solution
{
Solution() {}
void solve()
{
int nr;
int nc;
cin >> nr >> nc;
vector<pair<int, int> > a;
vector<pair<int, int> > b;
for(int i = 0; i < nr; i++)
{
int val;
cin >> val;
int k = a.size();
while(k > 1)
{
int last = a[k - 1].first;
int prev = a[k - 2].first;
if(prev <= last && last >= val) a.pop_back();
else break;
k--;
}
a.push_back(make_pair(val, i));
}
for(int i = 0; i < nc; i++)
{
int val;
cin >> val;
int k = b.size();
while(k > 1)
{
int last = b[k - 1].first;
int prev = b[k - 2].first;
if(prev <= last && last >= val) b.pop_back();
else break;
k--;
}
b.push_back(make_pair(val, i));
}
nr = a.size(); nc = b.size();
vector<vector<int64_t> > dp(nr, vector<int64_t>(nc, INF));
dp[0][0] = 0;
for(int i = 0; i < nr; i++)
{
for(int j = 0; j < nc; j++)
{
if(j < nc - 1)
{
int64_t len = b[j + 1].second - b[j].second;
dp[i][j + 1] = min(dp[i][j + 1], 1LL * a[i].first * len + dp[i][j]);
}
if(i < nr - 1)
{
int64_t len = a[i + 1].second - a[i].second;
dp[i + 1][j] = min(dp[i + 1][j], 1LL * b[j].first * len + dp[i][j]);
}
}
}
cout << dp[nr - 1][nc - 1] << "\n";
}
int modsub(int t1, int t2)
{
int res = t1 - t2;
if(res < 0) res += MOD;
return res;
}
int modadd(int t1, int t2)
{
int res = t1 + t2;
if(res >= MOD) res -= MOD;
return res;
}
int modmul(int t1, int t2)
{
int64_t res = 1LL * t1 * t2;
return (res % MOD);
}
bool BIT(int& mask, int& j)
{
return (mask & MASK(j));
}
int MASK(int j)
{
return (1 << j);
}
};
void __startup()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
}
int main()
{
__startup();
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
Solution().solve();
}
return 0;
}