Submission #602650

#	Time	Username	Problem	Language	Result	Execution time	Memory
602650		HamletPetrosyan	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	48 ms	34192 KiB

kyoto

/// #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[2005][2005];
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 <= min(max(w, h), 2004ll); 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

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60