oj.uz

Submission #602543

# Submission time Handle Problem Language Result Execution time Memory
602543 2022-07-23T07:55:28 Z HamletPetrosyan Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 76 ms 46320 KB 
/// #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 = 5e5 + 5;

ll h, w, a[N], b[N];
ll cnta[N], cntb[N], dp[5005][5005];
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); 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 9 ms 12244 KB Output is correct
10 Correct 10 ms 12148 KB Output is correct
11 Correct 9 ms 12244 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 9 ms 12244 KB Output is correct
14 Correct 9 ms 12172 KB Output is correct
15 Correct 9 ms 12244 KB Output is correct
16 Correct 12 ms 12204 KB Output is correct
17 Correct 11 ms 12192 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 7 ms 8020 KB Output is correct
4 Runtime error 76 ms 46320 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 9 ms 12244 KB Output is correct
10 Correct 10 ms 12148 KB Output is correct
11 Correct 9 ms 12244 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 9 ms 12244 KB Output is correct
14 Correct 9 ms 12172 KB Output is correct
15 Correct 9 ms 12244 KB Output is correct
16 Correct 12 ms 12204 KB Output is correct
17 Correct 11 ms 12192 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 7 ms 8020 KB Output is correct
32 Runtime error 76 ms 46320 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -