oj.uz

Submission #602615

# Submission time Handle Problem Language Result Execution time Memory
602615 2022-07-23T09:31:00 Z HamletPetrosyan Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 19 ms 10900 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 = 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, 1000ll}); 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 2 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4564 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 9 ms 8148 KB Output is correct
10 Correct 8 ms 8148 KB Output is correct
11 Correct 10 ms 8144 KB Output is correct
12 Correct 8 ms 8240 KB Output is correct
13 Correct 9 ms 8148 KB Output is correct
14 Correct 8 ms 8148 KB Output is correct
15 Correct 9 ms 8144 KB Output is correct
16 Correct 8 ms 8180 KB Output is correct
17 Correct 9 ms 8176 KB Output is correct
18 Correct 2 ms 4308 KB Output is correct
19 Correct 2 ms 4308 KB Output is correct
20 Correct 2 ms 4308 KB Output is correct
21 Correct 3 ms 4308 KB Output is correct
22 Correct 2 ms 4292 KB Output is correct
23 Correct 2 ms 4300 KB Output is correct
24 Correct 3 ms 4308 KB Output is correct
25 Correct 2 ms 4308 KB Output is correct
26 Correct 3 ms 4296 KB Output is correct
27 Correct 2 ms 4308 KB Output is correct
28 Correct 3 ms 4308 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Runtime error 19 ms 10900 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 3 ms 4308 KB Output is correct
4 Correct 3 ms 4564 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 9 ms 8148 KB Output is correct
10 Correct 8 ms 8148 KB Output is correct
11 Correct 10 ms 8144 KB Output is correct
12 Correct 8 ms 8240 KB Output is correct
13 Correct 9 ms 8148 KB Output is correct
14 Correct 8 ms 8148 KB Output is correct
15 Correct 9 ms 8144 KB Output is correct
16 Correct 8 ms 8180 KB Output is correct
17 Correct 9 ms 8176 KB Output is correct
18 Correct 2 ms 4308 KB Output is correct
19 Correct 2 ms 4308 KB Output is correct
20 Correct 2 ms 4308 KB Output is correct
21 Correct 3 ms 4308 KB Output is correct
22 Correct 2 ms 4292 KB Output is correct
23 Correct 2 ms 4300 KB Output is correct
24 Correct 3 ms 4308 KB Output is correct
25 Correct 2 ms 4308 KB Output is correct
26 Correct 3 ms 4296 KB Output is correct
27 Correct 2 ms 4308 KB Output is correct
28 Correct 3 ms 4308 KB Output is correct
29 Correct 2 ms 4308 KB Output is correct
30 Correct 2 ms 4308 KB Output is correct
31 Runtime error 19 ms 10900 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -