Submission #544587

#	Time	Username	Problem	Language	Result	Execution time	Memory
544587		hollwo_pelw	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	47 ms	5604 KiB

kyoto

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen("kyoto.inp", "r")){
		freopen("kyoto.inp", "r", stdin);
		freopen("kyoto.out", "w", stdout);
	}
#else
	auto start = chrono::steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 1e5 + 5;

#define int long long

int n, m, a[N], b[N], extra, p[N], q[N], sa[N], sb[N];

bool check1(int x, int y, int z) { return (sa[z] - sa[y]) * (y - x) >= (sa[y] - sa[x]) * (z - y); }
bool check2(int x, int y, int z) { return (sb[z] - sb[y]) * (y - x) >= (sb[y] - sb[x]) * (z - y); }
bool check3(int x, int y, int z, int w){ return (sa[y] - sa[x]) * (w - z) >= (sb[w] - sb[z]) * (y - x); }

void Hollwo_Pelw(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++)
		cin >> b[i];
	
	extra += a[n] * (m - 1);
	extra += b[m] * (n - 1);
	for (int i = 1; i <= n; i++)
		a[i] -= a[n];
	for (int i = 1; i <= m; i++)
		b[i] -= b[m];
	-- n, -- m;

	// memset(dp, 0x3f, sizeof dp);
	// dp[0][0] = 0;
	// for (int i = 0; i <= n; i++)
	// 	for (int j = 0; j <= m; j++) {
	// 		if (i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[j + 1]);
	// 		if (j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i + 1]);
	// 	}

	// cout << dp[n][m] + extra;

	for (int i = 1; i <= n; i++) extra -= a[i];
	for (int i = 1; i <= m; i++) extra -= b[i];

	for (int i = 1; i <= n; i++) a[i] -= a[i + 1];
	for (int i = 1; i <= m; i++) b[i] -= b[i + 1];
	
	for (int i = 1; i <= n; i++) sa[i] = sa[i-1] + a[i];
	for (int i = 1; i <= m; i++) sb[i] = sb[i-1] + b[i];

	for(int i = 0; i <= n; p[++ p[0]] = i++)
		while(p[0] >= 2 && check1(p[p[0] - 1], p[p[0]], i)) -- p[0];

	for(int i = 0; i <= m; q[++ q[0]] = i++)
		while(q[0] >= 2 && check2(q[q[0] - 1], q[q[0]], i)) -- q[0];
	
	int ans = extra;
	for(int i = 1, j = 1, k = 1; i < p[0] || j < q[0]; )
		if(j == q[0] || (i < p[0] && check3(p[i], p[i + 1], q[j], q[j + 1])))
			for(int t = p[i++] + 1; t <= p[i]; ++ t, ++ k) ans += 1LL * a[t] * k;
		else 
			for(int t = q[j++] + 1; t <= q[j]; ++ t, ++ k) ans += 1LL * b[t] * k;
	cout << ans << endl;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen("kyoto.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen("kyoto.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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