제출 #602493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602493		HamletPetrosyan	Sightseeing in Kyoto (JOI22_kyoto)	C++17	10 / 100	10 ms	12244 KiB

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 = 2e5 + 5;

ll h, w, a[N], b[N];
ll cnt[N], dp[2005][2005];

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); 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;
	}
}

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 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60