stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

	double a,b,c,d;

	cin>>a>>b>>c>>d;

	int x=ceil(a/d);

	int y=ceil(c/b);

	if(y>x)cout<<"No"<<endl;

	else cout<<"Yes"<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.357823919204202x):
 #include<stdio.h>

 int main()

 {

          int a,b,c,d,x,y;

          scanf("%d%d%d%d",&a,&b,&c,&d);

          x=(a+d-1)/d;

          y=(c+b-1)/b;

          if(x>=y)

                    printf("Yes\n");

          else

                    printf("No\n");

 return 0;

 }
// Slower C++ solution:
#include<iostream>



using namespace std;



int main()

{

    int a, b, c, d;

    int cnt1, cnt2;

    while(cin >> a >> b >> c >> d) {

        if(a%d)

            cnt1 = a/d+1;

        else

            cnt1 = a/d;

        if(c%b)

            cnt2 = c/b+1;

        else

            cnt2 = c/b;

        if(cnt1 >= cnt2)

            cout << "Yes" << endl;

        else

            cout << "No" << endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.306603607111441x):
 #include<stdio.h>

 int main()

 {

          int a,b,c,d,x,y;

          scanf("%d%d%d%d",&a,&b,&c,&d);

          x=(a+d-1)/d;

          y=(c+b-1)/b;

          if(x>=y)

                    printf("Yes\n");

          else

                    printf("No\n");

 return 0;

 }
// Slower C++ solution:
 #include<iostream>

 using namespace std;



 int main(){

 int A,B,C,D,X,Y;

        cin>>A>>B>>C>>D;

 X=(A+D-1)/D;

 Y=(C+B-1)/B;

                   cout<<(X>=Y?"Yes":"No")<<"\n";

 }


// Faster C++ solution for the same problem (measured speedup: 5.294765993744783x):
 #include<stdio.h>

 int main()

 {

          int a,b,c,d,x,y;

          scanf("%d%d%d%d",&a,&b,&c,&d);

          x=(a+d-1)/d;

          y=(c+b-1)/b;

          if(x>=y)

                    printf("Yes\n");

          else

                    printf("No\n");

 return 0;

 }
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

  int A,B,C,D,x,y;

  cin>>A>>B>>C>>D;

  x=A/D;if(A%D>0)x++;y=C/B;if(C%B>0)y++;

  return cout<<((x>=y)?"Yes":"No")<<endl,0;

}

// Faster C++ solution for the same problem (measured speedup: 5.313878406868328x):
#include<stdio.h>

int main(void)

{

  int A,B,C,D,x;

  x=scanf("%d %d %d %d",&A,&B,&C,&D);

  while(!0)

  {

    C-=B;if(C<=0)return printf("Yes"),0;

    A-=D;if((A<=0))return printf("No"),0;

  }

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

  int A,B,C,D,x,y;

  cin>>A>>B>>C>>D;

  x=A/D;if(A%D>0)x++;y=C/B;if(C%B>0)y++;

  return cout<<((x>=y)?"Yes":"No")<<endl,0;

}

// Faster C++ solution for the same problem (measured speedup: 5.313878406868328x):
#include<stdio.h>

int main(void)

{

  int A,B,C,D;

  int x=scanf("%d %d %d %d",&A,&B,&C,&D);

  while(!0)

  {

    C-=B;if(C<=0)return printf("Yes"),0;

    A-=D;if((A<=0))return printf("No"),0;

  }

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main()

{

  int A,B,C,D,x,y;

  cin>>A>>B>>C>>D;

  x=A/D;if(A%D>0)x++;y=C/B;if(C%B>0)y++;

  return cout<<((x>=y)?"Yes":"No")<<endl,0;

}

// Faster C++ solution for the same problem (measured speedup: 5.314685449120601x):
#include<stdio.h>

int main(void)

{

  int A,B,C,D,x;

  x=scanf("%d %d %d %d",&A,&B,&C,&D);

  while(x)

  {

    C-=B;if(C<=0)return printf("Yes"),0;

    A-=D;if((A<=0))return printf("No"),0;

  }

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define p_ pair<int,int>

#define mp_ make_pair

#define ll long long

#define pb push_back

#define fi first

#define se second

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define show1(a) cout<<#a<<" = "<<a<<endl

#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl

using namespace std;

const ll INF = 1LL<<60;

const int inf = 1<<30;

const int maxn = 2e5+5;

inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

int n,m,a[maxn];

vector<int> g[maxn];

int main()

{

    fastio();

    cin>>n>>m;

    rep(i,1,n) cin>>a[i];

    rep(i,1,m) {int u,v;cin>>u>>v;g[u].pb(v),g[v].pb(u);}

    int ans = 0;

    rep(i,1,n){

        int sz = g[i].size();

        int flag = 1;

        for(int v:g[i]) if(a[v]>=a[i]) {flag=0;break;}

        if(flag) ans++;

    }

    cout<<ans<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 33.84584333306667x):
#include<stdio.h>

const int maxn = 1e5+5;



int a[maxn];

int can[maxn];



int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);can[i]=1;}



    for(int i=1;i<=m;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        if(a[u]>=a[v]) can[v] = 0;

        if(a[v]>=a[u]) can[u] = 0;

    }

    int ans = 0;

    for(int i=1;i<=n;i++) if(can[i]) ans++;

    printf("%d\n",ans);

    return 0;

}
// Slower C++ solution:
#pragma region 

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<cstring>

#include<string>

typedef long long ll;

template <typename T>void read(T &x){x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}

#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;

#pragma endregion

const int maxn = 1e5 + 5;

int h[maxn];

vector<int> g[maxn];



int main() {

    IO;

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= n;++i)

        cin >> h[i];

    while (m--) {

        int x, y;

        cin >> x >> y;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    int ans = 0;

    for (int i = 1; i <= n;++i) {

        int flag = 1;

        for (auto v:g[i]) {

            if (h[i]<=h[v]) {

                flag = 0;

                break;

            }

        }

        ans += (flag == 1);

    }

    cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 3.5141832561055137x):
/*

         ██╗ ██████╗ ██╗███╗   ██╗    ██╗   ██╗███████╗

         ██║██╔═══██╗██║████╗  ██║    ██║   ██║██╔════╝

         ██║██║   ██║██║██╔██╗ ██║    ██║   ██║███████╗

    ██   ██║██║   ██║██║██║╚██╗██║    ██║   ██║╚════██║

    ╚█████╔╝╚██████╔╝██║██║ ╚████║    ╚██████╔╝███████║

     ╚════╝  ╚═════╝ ╚═╝╚═╝  ╚═══╝     ╚═════╝ ╚══════╝

*/

//password:+BdCHpO8dQvpo5fnV3/u

#include<bits/stdc++.h>



using namespace std;

typedef long long ll;

const int maxn = 5e5 + 5;

const int inf = 0x3f3f3f3f;





int main() {

    int n,m;

    cin>>n>>m;

    vector<int>h(n+1);

    for(int i=1;i<=n;i++) cin>>h[i];

    vector<int>good(n+1,1);

    map<pair<int,int>,int>qaq;

    for(int i=1;i<=m;i++)

    {

        int x,y;

        cin>>x>>y;

        qaq[make_pair(x,y)]++;

        qaq[make_pair(y,x)]++;

    }

    for(auto it:qaq) {

            if(h[it.first.first]>h[it.first.second]) good[it.first.second]=0;

            else if(h[it.first.first]<h[it.first.second]) good[it.first.first]=0;

            else good[it.first.first]=0,good[it.first.second]=0;

    }

    int ans=0;

    for(int i=1;i<=n;i++){

        if(good[i]) ans++;

    }

    cout<<ans;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<n;i++)

#define REP(i,n) for(int i=1;i<n;i++)

#define all(v) v.begin(),v.end()

#define P pair<int,int>

#define len(s) (int)s.size()

#define pb push_back



template<class T> inline bool chmin(T &a, T b) {

	if (a > b) {

		a = b;

		return true;

	}

	return false;

}

template<class T> inline bool chmax(T &a, T b) {

	if (a < b) {

		a = b;

		return true;

	}

	return false;

}

void cmps(vector<int>&v,int &i){

	i=lower_bound(all(v),i)-v.begin();

}

constexpr int mod = 1e9+7;

constexpr int inf = 3e18;



int N,M;

int A[100005];

vector<int>G[100005];

signed main(){

	cin>>N>>M;

	rep(i,N)cin>>A[i];

	rep(i,M){

		int a,b;cin>>a>>b;a--;b--;

		G[a].pb(b);G[b].pb(a);

	}

	int ans=0;

	rep(i,N){

		bool flag=true;

		for(int j:G[i]){

			if(A[i]<=A[j])flag=false;

		}

		if(flag)ans++;

	}

	cout<<ans<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 3.537978922872417x):
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<n;i++)

#define REP(i,n) for(int i=1;i<n;i++)

#define rev(i,n) for(int i=n-1;i>=0;i--)

#define all(v) v.begin(),v.end()

#define P pair<int,int>

#define len(s) (int)s.size()

#define pb push_back



template<class T> inline bool chmin(T &a, T b){

	if(a>b){a=b;return true;}

	return false;

}

template<class T> inline bool chmax(T &a, T b){

	if(a<b){a=b;return true;}

	return false;

}

constexpr int mod = 1e9+7;

constexpr int inf = 3e18;



int N,M,H[100005];

bool bad[100005];

signed main(){

	cin>>N>>M;

	rep(i,N)cin>>H[i];

	while(M--){

		int a,b;cin>>a>>b;a--;b--;

		if(H[a]<=H[b])bad[a]=true;

		if(H[a]>=H[b])bad[b]=true;

	}

	int ans=0;

	rep(i,N)ans+=!bad[i];

	cout<<ans<<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

 

#define rep(i,n) for(int i=0;i<(n);i++)

#define reps(i,n) for(int i=1;i<=(n);i++)

#define lol long long

#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式

#define mp make_pair

#define fi first

#define se second

#define pu push_back

#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する

#define abs(x,y) max(x,y)-min(x,y)

#define all(v) v.begin(),v.end()

#define UPDight(a,b) (a+b-1)/b //小数点切り上げ 

const int INF = 0x3f3f3f3f;

const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

const int MOD=int(1e9)+7; 

using namespace std;

using pii = pair<int, int>;

typedef vector<int> vit;



//最大公約数

lol gcd(lol x, lol y){

  if(x < y) swap(x, y);

  lol r = x % y;

  while(r != 0){

    x = y;

    y = r;

    r = x % y;

  }

  return y;

}



//最小公倍数

lol lcm(lol x, lol y){

  lol a = x * y;

  return (a / gcd(x, y));

}



signed main(void){

  cin.tie(nullptr);

  ios_base::sync_with_stdio(false);



  int n, m;

  lol h[100005];

  cin >> n >> m;

  reps(i, n){

    cin >> h[i];

  }

  vit road[100005];

  int a, b;

  rep(i, m){

    cin >> a >> b;

    road[a].pu(b);

    road[b].pu(a);

  }

  bool out[100005] = {false};

  lol ans = 0;

  reps(i, n){

    if(out[i] == false){

      rep(j, road[i].size()){

	if(h[i] > h[road[i][j]]){

	  out[road[i][j]] = true;

	} else {

	  out[i] = true;

	}

      }

    }

  }

  int nasu = 0;

  reps(i, n){

    if(!out[i]){

      nasu ++;

    }

  }

  cout << nasu << '\n';

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.654932267126157x):
#include <bits/stdc++.h>



#define rep(i, x, n) for(int i=(x);i<(n);i++)

#define reps(i, x, n) for(int i=(x);i<=(n);i++)

#define lol long long

#define SUM(n) ((n)+1)*(n)/2 //1〜nまでの総和を求める式

#define mp make_pair

#define fi first

#define se second

#define pu push_back

#define SYOU(x) fixed<<setprecision(x+1) //小数点桁数を指定する

#define abs(x,y) max(x,y)-min(x,y)

#define all(v) v.begin(),v.end()

#define UPDigit(a,b) (a+b-1)/b //小数点切り上げ

const int INF = 0x3f3f3f3f;

const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

const int MOD=int(1e9)+7; 

using namespace std;

using pii = pair<int, int>;

typedef vector<int> vit;

//八方向を見るのに使うと便利(楽)

const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};



signed main(void){

  cin.tie(nullptr);

  ios_base::sync_with_stdio(false);

  int n, m;

  cin >> n >> m;

  int h[n + 5], highest[n + 5] = {};

  reps(i, 1, n){

    cin >> h[i];

  }

  int a, b;

  rep(i, 0, m){

    cin >> a >> b;

    highest[a] = max(highest[a], h[b]);

    highest[b] = max(highest[b], h[a]);

  }

  int ans = 0;

  reps(i, 1, n){

    if(highest[i] < h[i]){

      ans ++;

    }

  }

  cout << ans << '\n';

  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define int long long

using namespace std;



int a[100001];



vector<int> e[100001];



signed main()

{

	int n,m;

	cin>>n>>m;

	

	for(int i=1;i<=n;i++)

		cin>>a[i];

	

	int x,y;

	for(int i=1;i<=m;i++)

	{

		cin>>x>>y;

		e[x].push_back(y);

		e[y].push_back(x);

	}



	int cnt=0;

	bool f;

	for(int i=1;i<=n;i++)

	{

		f=true;

		for(int j=0;j<e[i].size();j++)

			if(a[i]<=a[e[i][j]])

				f=false;

		if(f) cnt++;

	}

		

	cout<<cnt<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.5349391202939717x):
#include <bits/stdc++.h>

using namespace std;



int a[100001],b[100001];



int main()

{

	int n,m;

	cin>>n>>m;

	

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

		b[i]=0;

	}

	for(int i=0;i<m;i++)

	{

		int x,y;

		cin>>x>>y;

		b[x]=max(b[x],a[y]);

		b[y]=max(b[y],a[x]);

	}

	

	int ans=0;

	for(int i=1;i<=n;i++)

		if(a[i]>b[i])

			ans++;

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for (int i=0; i< int (n); i++)

using namespace std;

typedef long long ll;



int main(){



int n, m;

cin >> n >> m;

int h[1000000]={0};

rep(i,n) cin >> h[i+1];

int good[1000000]={0};

for(int i=1; i<=m; i++) {

    int a, b;

    cin >> a >> b;

    if(h[a]<=h[b]) good[a]++;

    if(h[b]<=h[a]) good[b]++;

}

int ans=0;

for(int i=1; i<=n; i++){

    if(good[i]==0) ans++;

}



cout << ans << endl;



}

// Faster C++ solution for the same problem (measured speedup: 9.391262220216582x):
#include<iostream>

#include<algorithm>

 using namespace std;

 #define N 100010

 int main(){

   //速さ比べ

 int n,m,h[N],ma[N];

 cin>>n>>m;

 for(int i=1;i<=n;i++){

 cin>>h[i];

 ma[i]=0;

 }

 for(int i=0;i<m;i++){

int a,b;

 cin>>a>>b;

 ma[a]=max(ma[a],h[b]);

 ma[b]=max(ma[b],h[a]);

 }

 int ans=0;

 for(int i=1;i<=n;i++){

 ans+=h[i]>ma[i];

 }

 cout<<ans<<endl;

 }
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for (int i=0; i< int (n); i++)

using namespace std;

typedef long long ll;



int main(){



int n, m;

cin >> n >> m;

int h[1000000]={0};

rep(i,n) cin >> h[i+1];

int good[1000000]={0};

for(int i=1; i<=m; i++) {

    int a, b;

    cin >> a >> b;

    if(h[a]<=h[b]) good[a]++;

    if(h[b]<=h[a]) good[b]++;

}

int ans=0;

for(int i=1; i<=n; i++){

    if(good[i]==0) ans++;

}



cout << ans << endl;



}

// Faster C++ solution for the same problem (measured speedup: 5.283957376591089x):
#include <bits/stdc++.h>

#define rep(i,n) for (int i=0; i<int(n);i++)

using namespace std;

int main(){

int n, m;

cin >> n >> m;

int h[100010]={0};

rep(i,n) cin >> h[i+1];

int good[100010]={0};

for(int i=1; i<=m; i++) {

    int a, b;

    cin >> a >> b;

    if(h[a]<=h[b]) good[a]++;

    if(h[b]<=h[a]) good[b]++;

}

int ans=0;

for(int i=1; i<=n; i++) if(good[i]==0) ans++;

cout << ans << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;



const int maxn=1e5+5;



int n,m;

ll pos[maxn],maxx[maxn];//记录本身权值和该点与相邻节点的最大权值 



signed main()

{

	while(cin>>n>>m){

		memset(pos,0,sizeof pos);

		memset(maxx,0,sizeof maxx);

		for(int i=1;i<=n;i++)

		cin>>pos[i];

		ll x,y;

		for(int i=1;i<=m;i++){

			cin>>x>>y;

			maxx[x]=max(maxx[x],pos[y]);

			maxx[y]=max(maxx[y],pos[x]);

		}

		int cnt=0;

		for(int i=1;i<=n;i++)

		if(maxx[i]<pos[i])cnt++;

		cout<<cnt<<endl;

	}

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.857976250093045x):
#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;



int n, m;

int height[N];

int maxHeight[N];



int main() {

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) scanf("%d", &height[i]);

    for (int i = 1; i <= m; ++i) {

        int u, v;

        scanf("%d %d", &u, &v);

        maxHeight[u] = max(maxHeight[u], height[v]);

        maxHeight[v] = max(maxHeight[v], height[u]);

    }

    int cnt = 0;

    for (int i = 1; i <= n; ++i) {

        if (height[i] > maxHeight[i]) ++cnt;

    }

    printf("%d\n", cnt);

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long int

using namespace std;

ll a[200010], ans;

bool visited[200010];

vector<int>node[200010];

queue<int>qu;

map<pair<int,int>, bool>taken;

int main()

{

    int i, j, v, u, edges, nodes;

    cin  >> nodes >> edges;

    for(i=1;i<=nodes;i++)

    {

        cin >> a[i];

        visited[i] = true;

    }

    for(i=1;i<=edges;i++)

    {

        cin >> u >> v;

        if(a[u]==a[v])

        {

            visited[u] = false;

            visited[v] = false;

        }

        else if(a[u]>a[v])

        {

            visited[v] = false;

        }

        else{

            visited[u] = false;

        }

    }

    for(i=1;i<=nodes;i++)

        ans += visited[i];

    cout << ans << endl;

    return 0;

}

/*8 9

1 2

1 3

2 5

2 4

4 5

5 6

6 8

6 7

3 7*/


// Faster C++ solution for the same problem (measured speedup: 6.460539740186859x):
#include<bits/stdc++.h>

#define ll long long int

using namespace std;

ll a[200010], ans;

bool visited[200010];

int main()

{

    int i, v, u, edges, nodes;

    cin  >> nodes >> edges;

    for(i=1;i<=nodes;i++)

    {

        cin >> a[i];

        visited[i] = true;

    }

    for(i=1;i<=edges;i++)

    {

        cin >> u >> v;

        if(a[u]==a[v])

        {

            visited[u] = false;

            visited[v] = false;

        }

        else if(a[u]>a[v])

        {

            visited[v] = false;

        }

        else{

            visited[u] = false;

        }

    }

    for(i=1;i<=nodes;i++)

        ans += visited[i];

    cout << ans << endl;

    return 0;

}

/*8 9

1 2

1 3

2 5

2 4

4 5

5 6

6 8

6 7

3 7*/
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main(){

	int n,m,a,b;

	int h[100010];

	set<int > v[100010];

	cin >> n >> m;

	for(int i = 1; i <= n; i++){

		cin >> h[i];

	}

	for(int i = 0; i < m; i++){

		cin >> a >> b;

		v[a].insert(b);

		v[b].insert(a);

	}

	int cnt = 0;

	for(int i = 1; i <= n; i++){

		if(v[i].empty()){

			cnt++;

		}else{

			int flag = 1;

			for(auto x:v[i]){

				if(h[x] >= h[i]){

					flag = 0;

					break;

				}

			}

			if(flag)

				cnt++;

		}

	}

	cout << cnt << endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.8028867416947976x):
#include <bits/stdc++.h>

using namespace std;

int main(){

	int n,m,a,b;

	int h[100010];

	vector<int > v[100010];

	cin >> n >> m;

	for(int i = 1; i <= n; i++){

		cin >> h[i];

	}

	for(int i = 0; i < m; i++){

		cin >> a >> b;

		v[a].push_back(b);

		v[b].push_back(a);

	}

	int cnt = 0;

	for(int i = 1; i <= n; i++){

		if(v[i].empty()){

			cnt++;

		}else{

			int flag = 1;

			for(auto x:v[i]){

				if(h[x] >= h[i]){

					flag = 0;

					break;

				}

			}

			if(flag)

				cnt++;

		}

	}

	cout << cnt << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define chmin(a, b) (a = min(a, b))



const int INF = 1e9 + 10;



int n;

int a[10010];

int dp[2][5010][3];



int main()

{

	cin >> n;

	for (int i = 0; i < n - 1; i++){

		cin >> a[i];

	}

	

	fill_n(**dp, 2 * 5010 * 3, INF);

	dp[0][0][0] = 0;

	for (int i = 0; i < n; i++){

		int s = i & 1;

		int t = s ^ 1;

		fill_n(*dp[t], 5010 * 3, INF);

		for (int j = 0; j <= n / 2; j++){

			chmin(dp[t][j + 1][0], dp[s][j][0] + a[i]);

			chmin(dp[t][j][0], dp[s][j][0] + a[i]);

			chmin(dp[t][j + 1][0], dp[s][j][1] + a[i]);

			chmin(dp[t][j][0], dp[s][j][2] + a[i]);

			chmin(dp[t][j + 1][1], dp[s][j][0]);

			chmin(dp[t][j + 1][1], dp[s][j][1]);

			chmin(dp[t][j][2], dp[s][j][0]);

			chmin(dp[t][j][2], dp[s][j][2]);

		}

	}



	cout << dp[n & 1][n / 2][0] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1733855670707314x):
#include <bits/stdc++.h>

using namespace std;



#define chmin(x, y) (x = min(x, y))



int n;

int a[10000];

int dp[2][5010][2];



int main()

{

	scanf("%d", &n);

	for (int i = 0; i < n - 1; i++){

		scanf("%d", a + i);

	}



	for (int i = 1; i <= n / 2; i++){

		dp[0][i][0] = dp[0][i][1] = 1e9;

	}

	for (int i = 0; i < n; i++){

		auto &src = dp[i & 1], &dst = dp[~i & 1];

		for (int j = 0; j <= n / 2; j++){

			dst[j][0] = dst[j][1] = 1e9;

		}

		for (int j = 0; j <= n / 2; j++){

			chmin(dst[j + 1][0], src[j][0]);

			chmin(dst[j + 1][1], src[j][0] + a[i]);

			chmin(dst[j][1], src[j][1]);

			chmin(dst[j][0], src[j][1] + a[i]);

		}

	}



	int res = min(dp[n & 1][n / 2][0], dp[n & 1][n / 2][1]);

	printf("%d\n", res);

}
// Slower C++ solution:
//Bokan ga bokka--nn!!

//Daily Lunch Special Tanoshii !!

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <ctime>

#include <cassert>

#include <string>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

#include <functional>

#include <iostream>

#include <map>

#include <set>

using namespace std;

typedef pair<int,int> P;

typedef pair<int,P> P1;

typedef pair<P,P> P2;

typedef long long ll;

#define pu push

#define pb push_back

#define mp make_pair

#define eps 1e-7

#define INF 2000000000

#define f first

#define s second

#define rep(i,x) for(int i=0;i<x;i++)

int cut[10005];

int dp[2][5005][2];

int main()

{

	srand((unsigned int)time(NULL));

	int n; scanf("%d",&n);

	for(int i=1;i<n;i++) scanf("%d",&cut[i]);

	for(int i=0;i<2;i++)for(int j=0;j<5005;j++)for(int k=0;k<2;k++)dp[i][j][k]=1e8;

	dp[0][1][0]=0; int cur=0,nxt=1;

	for(int i=1;i<n;i++)

	{

		for(int j=0;j<5005;j++)for(int k=0;k<2;k++) dp[nxt][j][k]=1e8;

		for(int j=0;j<=n/2;j++)

		{

			dp[nxt][j+1][0]=min(dp[nxt][j+1][0],dp[cur][j][0]);

			dp[nxt][j][1]=min(dp[nxt][j][1],dp[cur][j][0]+cut[i]);

			dp[nxt][j][1]=min(dp[nxt][j][1],dp[cur][j][1]);

			dp[nxt][j+1][0]=min(dp[nxt][j+1][0],dp[cur][j][1]+cut[i]);

		}

		swap(cur,nxt);

	}

	printf("%d\n",min(dp[cur][n/2][0],dp[cur][n/2][1]));

}

// Faster C++ solution for the same problem (measured speedup: 4.050430466083093x):
#include <cstdio>

#include <algorithm>

using namespace std;

#define x 10001

int dp[x][2],num[x];

int main()

{

  int n;

  scanf("%d",&n);

  for(int i=1;i<n;i++)

  {

    scanf("%d",&num[i]);

  }

  for(int i=0;i<x;i++)

  {

    dp[i][0]=x*x;

    dp[i][1]=x*x;

  }

  dp[1][0]=0;

  for(int i=1;i<n;i++)

  {

    for(int j=n/2;j>=1;j--)

    {

      dp[j][1]=min(dp[j][1],dp[j][0]+num[i]);

      dp[j][0]=min(dp[j-1][0],dp[j-1][1]+num[i]);

    }

  }

  printf("%d\n",min(dp[n/2][0],dp[n/2][1]));

  return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

#include <algorithm>



#pragma warning(disable : 4996)



#define INF (1 << 25)



using namespace std;



int main()

{

	int N;



	scanf("%d", &N);



	vector<int> D(N - 1);



	for (int i = 0; i < N - 1; i++)

	{

		scanf("%d", &D[i]);

	}



	vector<vector<vector<int> > > dp(2, vector<vector<int> >(N / 2 + 1, vector<int>(2, INF)));



	dp[0][0][0] = 0;



	for (int i = 1; i < N; i++)

	{

		for (int j = 0; j <= N / 2; j++)

		{

			dp[i % 2][j][0] = min(dp[(i - 1) % 2][j][0], dp[(i - 1) % 2][j][1] + D[i - 1]);

			

			if (j != 0)

			{

				dp[i % 2][j][1] = min(dp[(i - 1) % 2][j - 1][1], dp[(i - 1) % 2][j - 1][0] + D[i - 1]);

			}

		}

	}



	printf("%d\n", min(dp[1][N / 2][0], dp[1][N / 2][1]));



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.222623689736974x):
#include <cstdio>

#include <algorithm>

using namespace std;

int n, a[10009], dp[5009][2];

int main() {

	scanf("%d", &n);

	for (int i = 0; i < n - 1; i++) scanf("%d", &a[i]);

	for (int i = 0; i <= n >> 1; i++) dp[i][0] = dp[i][1] = 999999999;

	dp[0][0] = dp[1][1] = 0;

	for (int i = 0; i < n - 1; i++) {

		for (int j = n >> 1; j >= 0; j--) {

			dp[j][0] = min(dp[j][0], dp[j][1] + a[i]);

			dp[j][1] = (j ? min(dp[j - 1][1], dp[j - 1][0] + a[i]) : 999999999);

		}

	}

	printf("%d\n", dp[n >> 1][0]);

	return 0;

}