Submission #602650

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602650	2022-07-23T09:50:28 Z	HamletPetrosyan	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	48 ms	34192 KB

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.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	2 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	12116 KB	Output is correct
10	Correct	9 ms	12116 KB	Output is correct
11	Correct	9 ms	12196 KB	Output is correct
12	Correct	8 ms	12116 KB	Output is correct
13	Correct	9 ms	12116 KB	Output is correct
14	Correct	12 ms	12116 KB	Output is correct
15	Correct	10 ms	12116 KB	Output is correct
16	Correct	11 ms	12116 KB	Output is correct
17	Correct	11 ms	12116 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 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	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	5 ms	7968 KB	Output is correct
4	Correct	36 ms	32548 KB	Output is correct
5	Correct	11 ms	10832 KB	Output is correct
6	Correct	6 ms	8964 KB	Output is correct
7	Correct	41 ms	34136 KB	Output is correct
8	Correct	42 ms	34124 KB	Output is correct
9	Correct	41 ms	34120 KB	Output is correct
10	Correct	41 ms	34192 KB	Output is correct
11	Correct	48 ms	34024 KB	Output is correct
12	Correct	44 ms	33996 KB	Output is correct
13	Correct	41 ms	33968 KB	Output is correct
14	Correct	42 ms	34160 KB	Output is correct
15	Correct	17 ms	10936 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	1 ms	328 KB	Output is correct
19	Correct	1 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	1 ms	340 KB	Output is correct
23	Correct	1 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	0 ms	340 KB	Output is correct

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	2 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	12116 KB	Output is correct
10	Correct	9 ms	12116 KB	Output is correct
11	Correct	9 ms	12196 KB	Output is correct
12	Correct	8 ms	12116 KB	Output is correct
13	Correct	9 ms	12116 KB	Output is correct
14	Correct	12 ms	12116 KB	Output is correct
15	Correct	10 ms	12116 KB	Output is correct
16	Correct	11 ms	12116 KB	Output is correct
17	Correct	11 ms	12116 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 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	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	5 ms	7968 KB	Output is correct
32	Correct	36 ms	32548 KB	Output is correct
33	Correct	11 ms	10832 KB	Output is correct
34	Correct	6 ms	8964 KB	Output is correct
35	Correct	41 ms	34136 KB	Output is correct
36	Correct	42 ms	34124 KB	Output is correct
37	Correct	41 ms	34120 KB	Output is correct
38	Correct	41 ms	34192 KB	Output is correct
39	Correct	48 ms	34024 KB	Output is correct
40	Correct	44 ms	33996 KB	Output is correct
41	Correct	41 ms	33968 KB	Output is correct
42	Correct	42 ms	34160 KB	Output is correct
43	Correct	17 ms	10936 KB	Output is correct
44	Correct	0 ms	340 KB	Output is correct
45	Correct	0 ms	340 KB	Output is correct
46	Correct	1 ms	328 KB	Output is correct
47	Correct	1 ms	340 KB	Output is correct
48	Correct	1 ms	340 KB	Output is correct
49	Correct	1 ms	340 KB	Output is correct
50	Correct	1 ms	340 KB	Output is correct
51	Correct	1 ms	340 KB	Output is correct
52	Correct	1 ms	340 KB	Output is correct
53	Correct	0 ms	340 KB	Output is correct
54	Correct	0 ms	340 KB	Output is correct
55	Runtime error	47 ms	19164 KB	Execution killed with signal 11
56	Halted	0 ms	0 KB	-

Submission #602650

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 30.0 / 30.0

Subtask #3 0 / 60.0

Subtask #1
10.0 / 10.0

Subtask #2
30.0 / 30.0

Subtask #3
0 / 60.0