# 【Codeforces 799D】Field expansion

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int INF = 1e9;

int n,v[N],f[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline bool cmp(int a, int b) {
return a > b;
}

inline int solve(int a, int b, int h, int w) {
memset(f, 0, sizeof(f));
f[min(h, a)] = min(b, w);
int ans = 1;
for (int j=1;j<=n;j++,ans++) {
for (int i=a;i;i--) {
if (f[i]) {
int tt = min((LL)a, (LL)i * v[j]);
f[tt] = max(f[tt], f[i]);
if (tt == a && f[i] == b) {
return ans;
}
tt = min((LL)b, (LL)f[i] * v[j]);
f[i] = tt;
if (i == a && tt == b) {
return ans;
}
}
}
}
return INF;
}

int main() {
for (int i=1;i<=n;i++) {
}
sort(v+1, v+1+n, cmp);
n = min(n, 34);
if ((h >= a && w >= b) || (h >= b && w >= a)) {
puts("0");
exit(0);
}
int ans1 = solve(a, b, h, w);
int ans2 = solve(a, b, w, h);
if (ans1 >= INF && ans2 >= INF) {
puts("-1");
} else {
printf("%d\n",min(ans1, ans2));
}
return 0;
}


## 4 thoughts to “【Codeforces 799D】Field expansion”

1. Way cool, some valid points! I appreciate you making this article available, the rest of the site is also high quality. Have a fun.

2. Wow! Thank you! I always wanted to write on my blog something like that. Can I take a portion of your post to my site?

3. Does your site have a contact page? I’m having problems locating it but,
I’d like to send you an email. I’ve got some suggestions for your blog
you might be interested in hearing. Either way,
great blog and I look forward to seeing it grow over time.

4. I visited many sites but the audio feature for audio songs existing at
this web site is really wonderful.