/// #if (code == true)
#include <bits/stdc++.h>
using namespace std;
#define pll pair<long long, long long>
#define len(a) ((int)((a).size()))
#define all(a) a.begin(), a.end()
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second
const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 1e5 + 5;
ll h, w, a[N], b[N];
ll cnta[N], cntb[N], dp[1005][1005];
bool ss[N], cc[N];
void solve(){
cin >> h >> w;
for(int i = 1; i <= h; i++){
cin >> a[i];
}
for(int i = 1; i <= w; i++){
cin >> b[i];
}
for(int i = 1; i <= max({w, h, 3000ll}); i++){
dp[0][i] = dp[i][0] = INF;
}
if(h <= 1000 && w <= 1000){
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
if(i == j && i == 1) continue;
dp[i][j] = min(dp[i - 1][j] + b[j], dp[i][j - 1] + a[i]);
}
}
cout << dp[h][w] << "\n";
return;
}
for(int i = 1; i <= h; i++){
cnta[a[i]]++;
}
for(int i = 1; i <= w; i++){
cntb[b[i]]++;
}
vector<ll> na, nb, nad, nbd;
ll now = 0;
for(int i = 1; i <= h; i++){
if(!ss[a[i]]){
na.add(a[i]);
nad.add(now);
now = 0;
ss[a[i]] = 1;
}
else if(cnta[a[i]] == 1){
na.add(a[i]);
nad.add(now);
now = 0;
}
now++;
cnta[a[i]]--;
}
now = 0;
for(int i = 1; i <= w; i++){
if(!cc[b[i]]){
nb.add(b[i]);
nbd.add(now);
now = 0;
cc[b[i]] = 1;
}
else if(cntb[b[i]] == 1){
nb.add(b[i]);
nbd.add(now);
now = 0;
}
now++;
cntb[b[i]]--;
}
// for(int i = 0; i < len(na); i++){
// cout << na[i] << " ";
// }
// cout << endl;
// for(int i = 0; i < len(nad); i++){
// cout << nad[i] << " ";
// }
// cout << endl << endl;
//
// for(int i = 0; i < len(nb); i++){
// cout << nb[i] << " ";
// }
// cout << endl;
// for(int i = 0; i < len(nbd); i++){
// cout << nbd[i] << " ";
// }
// cout << endl << endl;
for(int i = 0; i < len(na); i++){
for(int j = 0; j < len(nb); j++){
if(i == j && i == 0) continue;
dp[i + 1][j + 1] = min(dp[i + 1][j] + na[i] * nbd[j], dp[i][j + 1] + nb[j] * nad[i]);
// cout << i << " " << j << " : " << na[i] << " " << nad[i] << " : " << nb[j] << " " << nbd[j] << " " << dp[i + 1][j] << " " << dp[i][j + 1] << endl;
}
}
// for(int i = 1; i <= len(na); i++){
// for(int j = 1; j <= len(nb); j++){
// cout << dp[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
cout << dp[len(na)][len(nb)] << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int _ = 1;
// cout << fixed;
// cout.precision(15);
// cin >> _ ;
while(_--) solve();
return 0;
}
/// #else
/// #include <bits/stdc++.h> using namespace std; int main() { cout << "Hello World!"; }
/// #endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
11816 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
11896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
11816 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
