제출 #1146076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146076		mingga	Sightseeing in Kyoto (JOI22_kyoto)	C++20	10 / 100	16 ms	31816 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 sub1 {
	bool check() {
		return w <= 1000 and h <= 1000;
	}
	int f[1005][1005];
	void solve() {
		memset(f, 0x3f, sizeof f);
		for(int i = 1; i <= h; i++) {
			for(int j = 1; j <= w; j++) {
				if(i == 1 and j == 1) f[i][j] = 0;
				else {
					if(i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + b[j]);
					if(j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + a[i]);
				}
			}
		}
		cout << f[h][w] << ln;
	}
}

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[1005], c[1005];
	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;
	}
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task "1"
	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];
	 sub2::solve();
  cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}	

컴파일 시 표준 에러 (stderr) 메시지

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

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