Submission #1146239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146239		mingga	Sightseeing in Kyoto (JOI22_kyoto)	C++20	0 / 100	2093 ms	584 KiB

kyoto

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 1e5 + 7;
int w, h, a[N], b[N];

namespace sub2 {
	bool check() {
		int mx = max(* max_element(a + 1, a + h + 1), * max_element(b + 1, b + w + 1));
		return mx <= 1000;
	}
	int r[N], c[N];
	int lef[N], rig[N];
	int f[2005][2005];
	void solve() {
		rig[h + 1] = lef[0] = inf;
		int n = 0, m = 0;
		for(int i = h; i > 0; i--) {
			rig[i] = min(rig[i + 1], a[i]);
		}
		for(int i = 1; i <= h; i++) {
			lef[i] = min(lef[i - 1], a[i]);
			if(a[i] >= lef[i - 1] and a[i] >= rig[i + 1]) continue;	
			r[++n] = i;
		}
		rig[w + 1] = lef[0] = inf;
		for(int i = w; i > 0; i--) {
			rig[i] = min(rig[i + 1], b[i]);
		}
		for(int i = 1; i <= w; i++) {
			lef[i] = min(lef[i - 1], b[i]);
			if(b[i] >= lef[i - 1] and b[i] >= rig[i + 1]) continue;	
			c[++m] = i;
		}
		memset(f, 0x3f, sizeof f);
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(i == 1 and j == 1) f[i][j] = 0;
				else f[i][j] = min(f[i - 1][j] + (r[i] - r[i - 1]) * b[c[j]],
													 f[i][j - 1] + (c[j] - c[j - 1]) * a[r[i]]);
			}
		}
		cout << f[n][m] << ln;
	}
}

namespace sub3 {
	int nxt[2][N], pre[2][N], d[2][N], lst[2];
	struct node {
		int dir, l, r;
		double w;
		node() {}
		node(int dir, int l, int r) : dir(dir), l(l), r(r) {
			w = (d[dir][r] - d[dir][l]) / (r - l);
		}
		bool operator < (const node& o) const {
			return w > o.w;
		}
	};
	void solve() {
		set<node> s;
		for(int i = 1; i <= h; i++) d[0][i] = a[i];
		for(int i = 1; i <= w; i++) d[1][i] = b[i];
		lst[0] = h - 1;
		lst[1] = w - 1;
		for(int i = 1; i < h; i++) {
			nxt[0][i] = i + 1;
			pre[0][i + 1] = i;
			s.insert(node(0, i, i + 1));
		}
		for(int i = 1; i < w; i++) {
			nxt[1][i] = i + 1;
			pre[1][i + 1] = i;
			s.insert(node(1, i, i + 1));
		}
		int ans = 0;
		int n[2];
		n[0] = h, n[1] = w;
		for(int i = 1; i <= h + w - 2; i++) {
			auto cur = * s.begin();
			s.erase(s.begin());
			int l = cur.l, r = cur.r, dir = cur.dir;
			// cerr << l << ' ' << r << ' ' << dir << ' ' << cur.w << ln;
			if(nxt[dir][r] == 0) {
				if(nxt[dir ^ 1][pre[dir ^ 1][n[dir ^ 1]]] == 0) {
					ans += d[dir][r] * (n[dir ^ 1] - lst[dir ^ 1]);
					n[dir ^ 1] = lst[dir ^ 1];
				} 
				lst[dir] = l;  
			} else if(s.find(node(dir, r, nxt[dir][r])) != s.end()) {
					s.erase(s.find(node(dir, r, nxt[dir][r])));
			}
			// cerr << n[0] << ' ' << n[1] << ln;
			// cerr << ans << ln;
			nxt[dir][l] = nxt[dir][r];
			pre[dir][nxt[dir][r]] = l;
			if(nxt[dir][l]) s.insert(node(dir, l, nxt[dir][l]));
		}
		if(n[0] == 1) {
			ans += (n[1] - 1) * a[1];
		} else ans += (n[0] - 1) * b[1];
		cout << ans << ln;
	}
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> h >> w;
	for(int i = 1; i <= h; i++) cin >> a[i];
	for(int j = 1; j <= w; j++) cin >> b[j];
	 sub3::solve();
  cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}	

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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