#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define opa(x) cout << #x << " = " << x << ", ";
#define op(x) cout << #x << " = " << x << endl;
#define ops(x) cout << x;
#define entr cout << endl;
#define spac cout << ' ';
#define all(x) (x).begin(), (x).end()
#define STL(x) cout << #x << " : "; for(auto &qwe:x) cout << qwe << ' '; cout << endl;
#define arr(x, n) cout << #x << " : "; loop(qwe,0,n) cout << x[qwe] << ' '; cout << endl;
#define deb1 cout << "deb1" << endl;
#define deb2 cout << "deb2" << endl;
#define deb3 cout << "deb3" << endl;
#define deb4 cout << "deb4" << endl;
#define deb5 cout << "deb5" << endl;
using namespace std;
typedef long long ll;
const int mxn = 1024000;
ll dp[mxn];
int a_in[100005], b_in[100005];
vector<int> a, b;
vector<int> mul_a, mul_b;
const ll INF = 1e18;
vector<pii> E[mxn];
inline int hsh(int i, int j){ return (i << 10) + j; }
inline int get_i(int x){ return x >> 10; }
inline int get_j(int x){ return x & 1023; }
void solve(){
int n, m; cin >> n >> m;
loop(i,0,n){
cin >> a_in[i];
}
loop(j,0,m){
cin >> b_in[j];
}
a.pb(a_in[0]);
int now_mul = 1;
loop(i,1,n-1){
if(a_in[i] >= a_in[i-1] && a_in[i] >= a_in[i+1]){
a_in[i] = a_in[i-1];
now_mul++;
}
else{
a.pb(a_in[i]);
mul_b.pb(now_mul);
now_mul = 1;
}
}
a.pb(a_in[n-1]);
mul_b.pb(now_mul);
n = a.size();
now_mul = 1;
b.pb(b_in[0]);
loop(i,1,m-1){
if(b_in[i] >= b_in[i-1] && b_in[i] >= b_in[i+1]){
b_in[i] = b_in[i-1];
now_mul++;
}
else{
b.pb(b_in[i]);
mul_a.pb(now_mul);
now_mul = 1;
}
}
b.pb(b_in[m-1]);
mul_a.pb(now_mul);
m = b.size();
loop(i,0,n){
loop(j,0,m){
dp[hsh(i, j)] = INF;
}
}
loop(i,0,n){
loop(j,0,m-1){
E[hsh(i, j)].pb({hsh(i, j+1), a[i] * mul_a[j]});
}
}
loop(j,0,m){
loop(i,0,n-1){
E[hsh(i, j)].pb({hsh(i+1, j), b[j] * mul_b[i]});
}
}
dp[0] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, 0});
while(!pq.empty()){
ll dis = pq.top().ff;
int now = pq.top().ss;
// opa(dis) op(now);
pq.pop();
if(dis != dp[now]) continue;
for(auto &i:E[now]){
ll nxt_dis = dis + i.ss;
int nxt = i.ff;
if(dp[nxt] > nxt_dis){
dp[nxt] = nxt_dis;
pq.push({nxt_dis, nxt});
}
}
}
cout << dp[hsh(n-1, m-1)] << '\n';
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
// freopen("test_input.txt", "r", stdin);
int t = 1;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
27492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
38988 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27224 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
27492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
