akhauriyash/Code-Regression huggingface dataset:
// Hack it and have it ;) //
/*author* Priyanshu Shrivastav (from IIT Palakkad) *
 * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
 * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
 * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
 * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
When I wrote this, only God and I understood what I was doing
 ** * * * * * * * Now, only God knows!* * * * * * */
#include      <bits/stdc++.h>
using namespace std;
#define IOS       ios_base::sync_with_stdio(false); cin.tie (nullptr)
#define PREC      cout.precision (10); cout << fixed
#ifdef CONVICTION
#include "/home/convict/Dropbox/myfiles/sport_coding/cplib/snippets/debug.h"
#else
#define debug(x...)
#endif
//Don’t practice until you get it right. Practice until you can’t get it wrong

const int Mod = (int)1e9 + 7;
inline int add (int x, int y) { return (1ll * x + y + (Mod << 1)) % Mod; }
inline int sub (int x, int y) { return (1ll * x - y + (Mod << 1)) % Mod; }
inline int mul (int x, int y) { return (int) (1ll*(x + Mod) * (y + Mod) % Mod); }
inline int pow (int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = mul(res, x);
    x = mul(x, x), y >>= 1;
  }
  return res;
}
inline int inv (int x) { return pow(x, Mod - 2); }
inline int dv (int x, int y) { return mul(x, inv(y)); }

const int MAXFAC = (int)2e6 + 10;
int fac[MAXFAC];
void init_fac (int maxn) {
  fac[0] = 1;
  for (int i = 1; i < maxn; ++i) fac[i] = mul(fac[i - 1], i);
}
inline int C(int n, int r) {
  return dv(fac[n], mul(fac[n-r], fac[r]));
}

void preproc()
{
   init_fac(MAXFAC);
}

void solve()
{
   int H, W, A, B;
   cin >> H >> W >> A >> B;

   int res = 0;
   // part I -> height -> H - A, width -> i
   // par II -> height -> A, width -> W - i + 1
   for (int i = B+1; i <= W; ++i) {
      int inc = mul(C(H - A + i - 2, i - 1), C(A + W - i - 1, A - 1));
      res = add(res, inc);
   }
   cout << res << '\n';
}

signed main()
{
  IOS; PREC;
  preproc();

  int tc = 1;
  // cin >> tc;
  for (int Tt = 1; Tt <= tc; ++Tt) {
    // cout << "Case #" << Tt << ": ";
    solve();
  }
  return EXIT_SUCCESS;
}


Measured memory_bytes: 11420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
int n, m;
ll a[maxx];

bool cmp(ll x, ll y) { return x > y; }

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> a[i];
	if(n >= m) {
		puts("0");
		return 0;
	}
	sort(a + 1, a + m + 1);
	ll sum = 0;
	int t = 0;
	ll b[maxx];
	for(int i = 2; i <= m; i++) {
		b[++t] = a[i] - a[i - 1];
		sum += b[t];
	}
	sort(b + 1, b + t + 1, cmp);
	for(int i = 1; i <= n - 1; i++) sum -= b[i];
	cout << sum << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <cmath>
#include<list>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 8;

int n,q,x,num;
int s[maxn],t[maxn];

bool if_find(int x)
{
    s[n] = x;
    int i = 0;
    while(i != n){
        if(s[i] == x) return true;
        i++;
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    num = 0;
    for(int i = 0; i < n; ++i) scanf("%d",&s[i]);
    scanf("%d",&q);
    for(int i = 0; i < q; ++i){
        scanf("%d",&x);
        if(if_find(x)){
            num++;
        }
    }
    printf("%d\n",num);
    return 0;
}

Measured memory_bytes: 3236
#include<bits/stdc++.h>
using namespace std;

int main(){
  int N; cin>>N;
  vector<long long>A(N); for(int i=0;i<N;i++) cin>>A.at(i);
  
  sort(A.begin(),A.end());
  
  vector<long long>side(N);
  int j=0;
  
  for(int i=0;i<N-1;i++){
    if(A.at(i)==A.at(i+1)){
      side.at(j)=A.at(i);
      j++;
      i++;
    }
  }
  
  sort(side.begin(),side.end());
  reverse(side.begin(),side.end());
  
  cout<<side.at(0)*side.at(1);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
/*
ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=2000005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

ll nPk(ll n,ll k){
	return nCk(n,k)*F[k]%mod;
}*/

int a,b,c,d,k;

int main(){
	cin>>a>>b>>c>>d>>k;
	int l=a*60+b,r=c*60+d;
	cout<<r-l-k<<endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll N,M;

class DisjointSet{
public:
  vector<int> rank,p;
  vector<int> sz;

  DisjointSet(){}
  DisjointSet(int size){
    rank.resize(size,0);
    p.resize(size,0);
    sz.resize(size,0);
    for(int i=0;i<size;i++) makeSet(i);
  }

  void makeSet(int x){
    p[x]=x;
    rank[x]=0;
    sz[x]=1;
  }

  bool same(int x,int y){
    return findSet(x)==findSet(y);
  }

  void unite(int x,int y){
    link(findSet(x),findSet(y));
  }

  void link(int x,int y){
    if(rank[x]>rank[y]){
      p[y]=x;
      sz[x]+=sz[y];
    }else{
      p[x]=y;
      sz[y]+=sz[x];
      if(rank[x]==rank[y]){
        rank[y]++;
      }
    }
  }

  int findSet(int x){
    if(x!=p[x]){
      p[x]=findSet(p[x]);
    }
    return p[x];
  }

  int findSize(int x){
    return sz[findSet(x)];
  }
};

int main(){
  cin>>N>>M;
  int a[M+1]={},b[M+1]={};
  for(int i=M-1;i>=0;i--){
    cin>>a[i]>>b[i];
  }

  vector<ll> ans;
  DisjointSet us(N+1);
  ans.push_back(0);
  ll ma=N*(N-1)/2;
  for(int i=0;i<M;i++){
    if(us.same(a[i],b[i])){
      ans.push_back(ans[i]);
      continue;
    }
    ll x=us.findSize(a[i]);
    ll y=us.findSize(b[i]);
    ans.push_back(ans[i]+x*y);
    us.unite(a[i],b[i]);
  }
  reverse(ans.begin(),ans.end());
  for(int i=1;i<=M;i++) cout<<ma-ans[i]<<endl;

  return 0;
}


Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    string beg, state;
    int n; cin >> n;

    cout << 0 << endl; cin >> beg;

    if(beg == "Vacant") return 0;

    int mid, left = 0, right = n;

    for(int i = 0; i < 20; ++i){
        mid = (left + right) >> 1;
        cout << mid << endl;
        cin >> state;
        if(state == "Vacant") break;
        if(mid % 2 == 0){
            if(state == beg)
                left = mid;
            else
                right = mid;
        } else {
            if(state != beg)
                left = mid;
            else
                right = mid;
        }
    }
    return 0;
}

Measured memory_bytes: 852
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

// 1 3 5 8 9 10
//1:1 1 1 1 1
//2:1 2 2 2 1
//3:1 2 3 2 1
//4:1 2 2 2 1
//5:1 1 1 1 1
ll cal_dim(vector<ll>& arr) {
    sort(arr.begin(), arr.end());
    vector<ll> diff;
    for(int i = 1; i < arr.size(); i++)
        diff.push_back(arr[i]-arr[i-1]);
    int n = arr.size()-1;
    vector<ll> mul(n, n);
    int l = 1, r = mul.size()-2;
    while (l <= r) {
        ll tmp = mul[l-1] + (n-l*2);
        mul[l++] = mul[r--] = tmp;
    }
    ll ans = 0, mod = 1e9+7;
    for(int i = 0; i < n; i++) {
        ans += mul[i] * diff[i];
        ans %= mod;
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> xs(n, 0);
    vector<ll> ys(m, 0);
    for(ll& val: xs)
        cin >> val;
    for(ll& val: ys)
        cin >> val;
    ll mod = 1e9 + 7;
    ll x = cal_dim(xs);
    ll y = cal_dim(ys);
    cout << (x*y) % mod << endl;
    return 0;
}




Measured memory_bytes: 3668
N = int(input())
a = [int(c) for c in input().split()]

dp = [[-1] * N for _ in range(N)]
for L in range(N, -1, -1):
    for R in range(L, N):
        if L == R:
            dp[L][R] = a[L]
        else:
            dp[L][R] = max(a[L] - dp[L+1][R], a[R] - dp[L][R-1])


print(dp[0][N-1])


Measured memory_bytes: 111836
#include<bits/stdc++.h>
using namespace std;
int dp[10000][10000],c[10000],d[10000],g;
int main(){
    int N,W;
    cin>>N>>W;
    for(int i=1;i<N+1;i++){
        cin>>c[i]>>d[i];
    }
    for(int i=0;i<10000;i++){
        dp[0][i]=-998648;
    }
    dp[0][0]=0;
    for(int i=1;i<N+1;i++){
        for(int j=W;j>=0;j--){
            //dp[i][j]=max(dp[i-1][j],dp[i-1][j-d[i]]+c[i]);
            dp[i][j] = dp[i - 1][j];
            if(j - d[i] >= 0)dp[i][j] = max(dp[i][j],dp[i - 1][j - d[i]] + c[i]);
        }
    }

   

    for(int i=0;i<=W;i++){
        g=max(dp[N][i],g);
    }
    cout<<g<<endl;

}

Measured memory_bytes: 7052
#include <bits/stdc++.h>

using namespace std ;

int main()
{
    string a , b ;
    cin >> a >> b ;

    if(a[1] == b[1] && a[0] == b[2] && a[2] == b[0])
        cout << "YES" ;
    else cout << "NO" ;

    return 0 ;
}


Measured memory_bytes: 256
// AOJ GRL_1_C All Pairs Shortest Path
// 2018.4.26 bal4u

#include <stdio.h>
#include <string.h>

#define MAX_V 102

#define INF 0x7f7f7f7f
int V;
int d[MAX_V][MAX_V];

int warshall_floyd()
{
	int i, j, k, x;

	for (k = 0; k < V; k++) {
		for (i = 0; i < V; i++) if (d[i][k] != INF) {
			for (j = 0; j < V; j++) if (d[k][j] != INF) {
				x = d[i][k] + d[k][j];
				if (d[i][j] > x) d[i][j] = x;
			}
		}
	}
	for (i = 0; i < V; i++) if (d[i][i] < 0) return -1;
	return 0;
}

// バッファを経ずstdinから数値を得る(マイナス値の入力に対応)
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	if (c == '-') {	c = getchar_unlocked();
		do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

int main()
{
	int E, s, t;

	V = in(), E = in();
	memset(d, INF, sizeof(d));
	for (s = 0; s < V; s++) d[s][s] = 0;
	while (E--) {
		s = in(), t = in();
		d[s][t] = in();
	}
	if (warshall_floyd() < 0) puts("NEGATIVE CYCLE");
	else {
		for (s = 0; s < V; s++) {
			printf(d[s][0] >= INF? "INF": "%d", d[s][0]);
			for (t = 1; t < V; t++) {
				printf(d[s][t] >= INF? " INF": " %d", d[s][t]);
			}
			putchar('\n');
		}
	}
	return 0;
}



Measured memory_bytes: 2100
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
    
    ll n,k;
    cin>>n>>k;
    ll arr[n]={0},dp[n]={0};
    for (int i = 0; i < n; i++) {
        cin>>arr[i];
    }
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(ll i=2;i<n;i++)
    {
        ll myArr[k];
        for(ll j=0;j<min(i,k);j++)
        {
            myArr[j]=abs(arr[i-j-1]-arr[i])+dp[i-j-1];
            
        }
    
        dp[i]=*min_element(myArr,myArr+min(i,k));

    }
   
    cout<<dp[n-1]<<endl;
    return 0;
    
}

Measured memory_bytes: 1792
import std.algorithm;
import std.array;
import std.math;
import std.random;
import std.range;
import std.stdio;
import std.typecons;

immutable int nil = 0;

alias Point = Tuple !(int, q{x}, int, q{y});

struct Node
{
	int coord;
	int value;
	int best;
	int num;
	int left;
	int right;

	this (int coord_)
	{
		coord = coord_;
		value = 1;
		best = value;
		num = 1;
		left = nil;
		right = nil;
	}
}

Node [] t;
int nodes;
int root;

void tRecalc (int v)
{
	t[v].best = max (t[v].value, t[t[v].left].best, t[t[v].right].best);
	t[v].num = 1 + t[t[v].left].num + t[t[v].right].num;
}

int [2] tSplit (int v, int x)
{
	if (v == nil)
	{
		return [nil, nil];
	}
	if (t[v].coord < x)
	{
		auto temp = tSplit (t[v].right, x);
		t[v].right = temp[0];
		tRecalc (v);
		return [v, temp[1]];
	}
	else
	{
		auto temp = tSplit (t[v].left, x);
		t[v].left = temp[1];
		tRecalc (v);
		return [temp[0], v];
	}
}

int tMerge (int u, int v)
{
	if (u == nil)
	{
		return v;
	}
	if (v == nil)
	{
		return u;
	}
	if (uniform (0, t[u].num + t[v].num) < t[u].num)
	{
		t[u].right = tMerge (t[u].right, v);
		tRecalc (u);
		return u;
	}
	else
	{
		t[v].left = tMerge (u, t[v].left);
		tRecalc (v);
		return v;
	}
}

void main ()
{
	rndGen.seed (12125);

	int x1, y1, x2, y2;
	while (readf (" %s %s %s %s", &x1, &y1, &x2, &y2) > 0)
	{
		int n;
		readf (" %s", &n);
		auto p = new Point [n];
		foreach (i; 0..n)
		{
			readf (" %s %s", &p[i].x, &p[i].y);
		}
		if (x1 > x2)
		{
			x1 = -x1;
			x2 = -x2;
			foreach (ref c; p)
			{
				c.x = -c.x;
			}
		}
		if (y1 > y2)
		{
			y1 = -y1;
			y2 = -y2;
			foreach (ref c; p)
			{
				c.y = -c.y;
			}
		}
		if (x2 - x1 < y2 - y1)
		{
			swap (x1, y1);
			swap (x2, y2);
			foreach (ref c; p)
			{
				swap (c.x, c.y);
			}
		}
		auto q = p.filter !(c => x1 <= c.x && c.x <= x2 &&
		    y1 <= c.y && c.y <= y2).array;
		sort (q);
		real res = ((x2 - x1) + (y2 - y1)) * 100.0;
		t = new Node [q.length + 1];
		nodes = 1;
		root = nil;
		foreach (ref c; q)
		{
			debug {writeln (c.x, " ", c.y);}
			t[nodes] = Node (c.y);
			auto temp = tSplit (root, c.y);
			debug {writeln (temp[0], " : ", temp[1]);}
			t[nodes].value = t[temp[0]].best + 1;
			tRecalc (nodes);
			temp[0] = tMerge (temp[0], nodes);
			root = tMerge (temp[0], temp[1]);
			nodes += 1;
		}
		debug
		{
			foreach (i; 0..nodes)
			{
				writeln (t[i]);
			}
                }
		int best = t[root].best;
		debug {writeln ("best = ", best, ", diff = ", y2 - y1);}
		if (best > y2 - y1)
		{
			res += PI * 10.0 - 20.0;
			best -= 1;
		}
		res += best * (PI * 5.0 - 20.0);
		writefln ("%.20f", res);
	}
}


Measured memory_bytes: 10620
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
  int n,l;
  cin >> n >> l;
  string s[n];
  rep(i,n)cin >> s[i];

  sort(s,s+n);
  
  string ret="";
  rep(i,n)ret+=s[i];
  cout << ret << endl;
}

Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int main(void){
  int N,k;
  cin >> N >> k;
  if(N % k == 0){
    cout << 0 << endl;
  } else {
    cout << 1 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, k;
  cin >> a >> b >> k;
  vector<int> comdiv(0);
  int m = min(a, b);
  for(int i = m; i > 0; i--) {
    if (a % i == 0 && b % i == 0) {comdiv.push_back(i);}
  }
  cout << comdiv.at(k - 1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back


int main()
{
    ll a, b;
    cin >> a >> b;
     double aa = a * 1.00000;
    double ans =  aa / b;
    printf("%.10lf\n", ans);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)

int main() {
    int N;
    string S;
    cin>>N>>S;
    int count = N;
    REP(i, 0, N-1){
        if(S[i] == S[i+1]) count--;
    }
    cout << count << endl;
}

Measured memory_bytes: 512
N = int(input())
a = list(map(int,input().split()))
a.append(0)
ans = 0
count = 1
nm = a[0]
for i in range(1,N+1):
    if nm == a[i]:
        count += 1
    else:
        nm = a[i]
        ans += count//2
        count = 1

print(ans)

Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Math;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var targets = new List<Vector2>();
            for(int i=0;i<n;i++)
            {
                var xy = Console.ReadLine().Split().Select(int.Parse).ToArray();
                targets.Add(new Vector2(xy[0],xy[1]));
            }

            if(n == 2)
            {
                Console.WriteLine(Distance(targets.First(), targets.Last()));
            }
            else
            {
                var edges = n+n*(n-3)/2;
                var distSum = DistSum(targets);
                var ans = distSum *(n-1) /((n + (n*(n-3)/2))*2); 
                // var ans = distSum * (n-1) / (nPr(edges, n-1));

                Console.WriteLine(ans);
            }
        }

        public static int Factorial(int x)
        {
            if(x > 1) return x*(Factorial(x-1));
            else return 1;
        }

        public static int nPr(int n, int r)
        {
            return (Factorial(n)/Factorial(n-r));
        }

        public static double Distance(Vector2 A, Vector2 B)
        {
            return Sqrt(Pow(A.X - B.X,2) +Pow(A.Y - B.Y, 2));
        }

        public static double DistSum(List<Vector2> points)
        {
            double dist=0;

            foreach(var item in points)
            {
                dist += points.Select(x => Distance(item,x)).ToList().Sum();
            }
            return dist;

        }
    }
}


Measured memory_bytes: 13396
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int,
                                 input().split())) for i in range(d)][::-1]
l0 = [a * p + c for a, p, c in ls]

res = float('inf')
for index in range(2**d):
    cs = '{:b}'.format(index)
    cs = '0' * (d - len(cs)) + cs
    count = 0
    s = 0
    for i, c in enumerate(cs):
        if c == '1':
            count += ls[i][1]
            s += l0[i]
    if s < g:
        for i, c in enumerate(cs):
            if c == '0' and s + ls[i][0] * ls[i][1] >= g:
                n = math.ceil((g - s) / ls[i][0])
                count += n
                s += ls[i][0] * n
                break
    if s >= g:
        res = min(res, count)
print(res)

Measured memory_bytes: 3064
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
ans = 10**11

for i in range(2 ** N):
    B = ""
    lenB = 0
    for j in range(N):
        if (i >> j) & 1:
            B += "1"
            lenB += 1
        else:
            B += "0"
    if lenB == K:
        s = 0
        cur = A[0]
        for k in range(1, N):
            if B[k] == "1" and A[k] <= cur:
                s += cur - A[k] + 1
                cur += 1
            else:
                cur = max(cur, A[k])
        #print(B, s)
        ans = min(ans, s)
print(ans)


Measured memory_bytes: 74244
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i= 0;i<n;i++)
#define ll long long

int main(){
    int n, w;
    cin >> n >> w;

    vector<vector<ll>> wv(n+1, vector<ll>(2));
    rep(i, n){
        cin >> wv[i+1][0] >> wv[i+1][1];
    } 

    vector<vector<ll>> sack(n+1, vector<ll>(w+1, -1));

    rep(i, n) sack[i][0] = 0;

    for(int i=1;i<=n;i++){
        for(int j = 0;j<=w;j++){
            if(sack[i-1][j] != -1){
                if(j+wv[i][0] <= w) sack[i][j + wv[i][0]] = sack[i-1][j] + wv[i][1];
            }
            if(sack[i-1][j] > sack[i][j]) sack[i][j] = sack[i-1][j];
        }
    }

    ll ans = 0;

    rep(i, w) ans = max(ans, sack[n][i+1]);

    cout << ans << endl;

    /*
    for(int i=0;i<=n;i++){
        for(int j=0;j<=w;j++){
            cout << sack[i][j] << "   ";
        }
        cout << endl;
    }
    */

    return 0;
}

Measured memory_bytes: 80256
import java.util.*;

class Main {
	Scanner sc;
	int N;
	int[] C;
	static final int MOD = 1000_000_007;
	
	private void calc() {
		sc = new Scanner(System.in);
		N = sc.nextInt();
		C = new int[N];
		for (int i = 0; i < N; i++) C[i] = sc.nextInt();
		Arrays.sort(C);
		long p = 1;
		for (int i = 0; i < N-1; i++) p = p * 2 % MOD;
		long pp = p * 2 % MOD;
		
		long a = p;
		long sum = 0;
		long d = (p%2==0)?p/2:(p+MOD)/2%MOD;
		for (int i = 0; i < N; i++) {
			sum = (a*C[N-1-i]%MOD + sum)%MOD;
			a = (a + d)%MOD;
		}
		sum = sum * pp % MOD;
		
		System.out.println(sum);
	}
	
	public static void main(String[] args) {
		new Main().calc();
	}
}


Measured memory_bytes: 64288
#include <stdio.h>
typedef long long ll;
int a[100000], cnt[100010] = {0};
int main() {
	int n;
	ll sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		cnt[a[i]]++;
		sum += a[i];
	}
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		int b, c;
		scanf("%d%d", &b, &c);
		sum -= (ll)cnt[b] * b;
		sum += (ll)cnt[b] * c;
		cnt[c] += cnt[b];
		cnt[b] = 0;
		printf("%lld\n", sum);
	}
	return 0;
}

Measured memory_bytes: 2508
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){

ll n=0;
cin>>n;

ll h=0;
// cin>>h;

ll ans =0;

for(ll i=0;i<n;i++){
    ll temp=0;
    cin>>temp;

    if(temp<h)
        ans =  ans + (ll)abs(h-temp);
    else h = temp;

}
cout<<(ll)ans;
return 0;

}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;

int main(){
    int n;
    cin>>n;
    vector<int>x(n),y(n),h(n);
    rep(i,n)cin>>x[i]>>y[i]>>h[i];
    rep(dy,101){
        rep(dx,101){
            int nh=-1;
            rep(i,n){
                if(h[i]>0){
                    int tmp=h[i]+abs(dy-y[i])+abs(dx-x[i]);
                    if(nh==-1)nh=tmp;
                    else{
                        if(nh!=tmp){
                            nh=-2;
                            break;
                        }
                    }
                }
            }
            if(nh==-2)continue;
            rep(i,n){
                if(h[i]==0){
                    int dist=abs(dy-y[i])+abs(dx-x[i]);
                    if(nh>dist){
                        nh=-2;
                        break;
                    }
                }
            }
            if(nh==-2)continue;
            cout<<dx<<" "<<dy<<" "<<nh<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

int solve(int n, int k) {
  if (n < k) return 0;
  if (!(n % k)) return n / k;
  return solve(n - (n - n / k * (k - 1)) / (n / k + 1) * (n / k + 1), k);
}

int main() {
  int n, ans = 0; std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    int a, k; std::cin >> a >> k;
    ans ^= solve(a, k);
  }
  puts(ans ? "Takahashi" : "Aoki");
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;

int tax(int rate,int before);

//実践的プログラミング感想
//Cしか触ったことなかったので入出力でまず苦労した。
//アルゴリズム自体は非常に単純な物だったので次回からは挑戦的な問題もやる

int main(void){
    int  X,Y,S;
    
    while(1){
    
        cin >> X;
        cin >> Y;
        cin >> S;
    
        if(X == 0 and Y == 0 and S ==00)
            break;
    
        int maximum = 0;
        for (int i = 1; i < S ; ++i)
            for (int j = i ; j <S ; ++j)
                if(tax(X,i)+tax(X,j) == S)
                    maximum = max(maximum, tax(Y,i) + tax(Y,j));
    
        cout << maximum << endl;
    }
}

int tax(int rate,int before){
    //cout << before << endl;
    return before * ( 100 + rate )/100;
}



Measured memory_bytes: 3056
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = ((int)(n) - 1); i >= 0; i--)
#define repn(i, n) for(int i = 1; i <= (int)(n); i++)
#define reprn(i, n) for(int i = ((int)(n)); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LARGE_PRIME_NUM (1e9+7)
typedef long long ll;

#include <iostream>
#include <array>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <numeric>
#include <cmath>

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	t.pop_back();
	string ans = (s == t ? "Yes" : "No");
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD  (ll)998244353

ll moddiv(ll a,ll b){
    a %= MOD;
    b %= MOD;
    for(ll m=MOD-2;m>0;m/=2){
        if(m&1){
            a=a*b%MOD;
        }
        b=b*b%MOD;
    }
    return a;
}

ll Fa[10101010], iFa[10101010];
ll p2[10101010];
ll C(ll a,ll b){
    return Fa[a] * iFa[b] % MOD * iFa[a - b] % MOD;
}

ll N;
ll i, j, k,ans;


int main(){
    scanf("%lld",&N);
    Fa[0] = 1;
    p2[0] = 1;
    fornum(i,0,N){
        Fa[i + 1] = Fa[i] * (i + 1) % MOD;
        p2[i + 1] = p2[i] * 2 % MOD;
    }
    iFa[N] = moddiv(1, Fa[N]);
    for (i = N; i > 0;i--)
    {
        iFa[i - 1] = iFa[i] * i % MOD;
    }

    ans = 1;
    fornum(i,0,N){
        ans = ans * 3 % MOD;
    }
    fornum(i,N/2+1,N+1){
        ans = ans + (MOD - C(N, i) * p2[N - i]) * 2 % MOD;
        ans %= MOD;
    }

    printf("%lld", ans);

    return 0;
}

Measured memory_bytes: 234752
fun main(args: Array<String>) {
    val n = readLine()?.toInt() ?: return
    val list = (0 until n).map {
        val (l, r) = readLine()?.split(" ")?.map { it.toInt() }!!
        l to r
    }
    val result = list.map { it.second - it.first + 1 }.sum()
    println(result)
}

Measured memory_bytes: 36384
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 100100;
int a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    int last = 1;
    while (last + 1 <= n) {
        if (a[last + 1] >= last + 1) {
            last++;
        } else {
            break;
        }
    }

    int need1 = a[last] - last;
    int right = last;
    while (right + 1 <= n && a[right + 1] == last) {
        right++;
    }
    int need2 = right - last;
    //cerr << last << ' ' << need1 << ' ' << need2 << '\n';
    if ((need1 & 1) || (need2 & 1)) {
        cout << "First\n";
    } else {
        cout << "Second\n";
    }

    return 0;
}

Measured memory_bytes: 640
N = int(input())
X = list(map(int, input().split()))
sav = float("inf")
for i in range(min(X), max(X)+1):
    Xe = map(lambda x:abs(x-i)**2,X)
    health = sum(Xe)
    if sav > health:
        sav = health

print(sav)


Measured memory_bytes: 40432
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(9); cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    double p = 1.08;

    int a1 = int(ceil((double)n / p));
    int a2 = int(floor((double)n / p));

    if (floor((double)a1 * p) == n) cout << a1 << '\n';
    else if (floor((double)a2 * p) == n) cout << a2 << '\n';
    else cout << ":(\n";

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

int main()
{
    char a;
    cin >> a;

    if('a' <= a && a <= 'z')
    {
        cout << 'a' << endl;
    }
    else if('A' <= a && a <= 'Z')
    {
        cout << 'A' << endl;
    }

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
 
using namespace std;
 
int main ()
{
  int N,M;
  cin>>N>>M;
  for(int i=0;i<M;i++)
  {
    int A;
    cin>>A;
    N-=A;
  }
  if(N>=0)
  {
    cout<<N<<endl;
  }
  else
  {
    cout<<-1<<endl;
  }
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;

int main() {
  //vector<int> b(101);
  //b.at(0)=1;
  int N, M, MM;
  long int A, S, a=1000000000;
  cin >> N;
  int i;
  int z=0;
  int o=0;
  for (i=0, S=0; i<N; i++) {
    cin >> A;
    if (A == 0) z=1;
    else if (A>0) S+=A;
    else {
      S-=A;
      o++;
    }
    a=min(a, abs(A));
  }
  o=o % 2;
  if ((z==0) && (o==1)) {
    S-=2*a;
  }
  cout << S << endl;
  return 0;
}


Measured memory_bytes: 256
n = gets.chomp.to_i
s = gets.chomp.split("")
opens = 0
closes = 0

s.each do |i|
    if i == "(" then
        opens += 1
    else
        opens -= 1 if opens > 0
    end
end

s.reverse!

s.each do |i|
    if i == ")" then
        closes += 1
    else
        closes -= 1 if closes > 0
    end
end

s.reverse!

puts "(" * closes + s.join("") + ")" * opens

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
  ll n,m,ans=0;cin>>n>>m;
  vector<bool> red(n,false);red[0]=true;
  vector<int> v(n,1);

  rep(i,m){
    ll a,b;cin>>a>>b;a--;b--;
    if(red[a]){
      red[b]=true;
      if(v[a]==1)red[a]=false;
    }
    v[a]--;
    v[b]++;
  }

  rep(i,n){
    if(red[i])ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<cmath>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const double PI=acos(-1.0);
const int INF=1e9;
const double EPS=1e-10;
const ll MOD=1e9+7;


int main(){
string s;
cin>>s;
int cnt=0;
REP(i,s.size()){
if(s[i]=='0'&s[i+1]=='0'){
s[i+1]='1';
cnt++;
}
else if(s[i]=='1'&s[i+1]=='1'){
s[i+1]='0';
cnt++;
}
}
cout<<cnt<<endl;

return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>

//    int n=132;
//    bitset<16>binar(n);
//    int a = bitset<16>(binar).to_ulong();
//    cout<<a;

#define int long long
#define pb push_back
#define rep(i,a,b) for ( int i = a; i < b; i++)
#define all(c) (c).begin(),(c).end()

using namespace std;

signed main()
{
   string s;
   cin>>s;
   if(s=="ABC"){
   	cout<<"ARC";
   }
   else{
   	cout<<"ABC";
   }
}
        
        
    

    





Measured memory_bytes: 3548
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans = 0;
		for(int i = 1; i<=n;i++) {
			for(int j = 1;j<=n;j++) {
				for(int k =1;k<=n;k++) {
					ans +=gcd(gcd (i,j),k);
				}
			}
		}
		System.out.println(ans);

	}
	public static int gcd(int a,int b) {
		
		if(b==0) {
			return a;
		}
		return gcd (b,a%b);
	}
	

}


Measured memory_bytes: 35900
#include <stdio.h>
int main() {
	char str[50];
	int i;

	scanf("%s",str);
	i=0;
	if(str[i]=='A'){
		i++;
	}
	if(str[i]=='K'&&str[i+1]=='I'&&str[i+2]=='H'){
		i+=3;
	}else{
		printf("NO");
		return 0;
	}
	if(str[i]=='A'){
		i++;
	}
	if(str[i]=='B'){
	i++;
	}else{
		printf("NO");
		return 0;
	}
	if(str[i]=='A'){
		i++;
	}
	if(str[i]=='R'){
		i++;
	}else{
		printf("NO");
		return 0;
	}
	if(str[i]=='A'){
		i++;
	}
	if(str[i]=='\0'){
		printf("YES");
	}else{
		printf("NO");
	}
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>

using namespace std;
typedef long long ll;
int MAX_N = 50;
int MAX_M = 50;
int N,M;
vector<vector<int>> eg(MAX_N,vector<int>(MAX_N));
vector<int> A(MAX_M),B(MAX_M);
set<int> se;
bool res;

bool dfs(int u){
    if(se.size()==N) {
        return true;
    }

    for(int v=0;v<N;v++){
        if(eg[u][v]==1 && se.count(v)==0) {
            se.insert(v);
            res = dfs(v);
        }
    }
    return res;
}

int main() {

    cin >> N >> M;
    vector<int> ct(N);
    for(int i=0;i<M;i++){
        cin >> A[i] >> B[i];
        A[i]--,B[i]--;
        ct[A[i]]++,ct[B[i]]++;
        eg[A[i]][B[i]] = 1;
        eg[B[i]][A[i]] = 1;
    }
    int st=0;
    for(int i=0;i<N;i++){
        if(ct[i]==1){
            st=i;
            break;
        }
    }
    int ans=0;
    for(int i=0;i<M;i++){
        eg[A[i]][B[i]]=0;
        eg[B[i]][A[i]]=0;
        bool jg=false;
        se.erase(se.begin(),se.end());
        se.insert(st);
        res=false;
        jg=dfs(st);
        if(!jg) ans++;
        eg[A[i]][B[i]]=1;
        eg[B[i]][A[i]]=1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var S string
	fmt.Scan(&S)
	n := len(S)
	var r int
	for i := 0; i < 1<<uint(n-1); i++ {
		sm := 0
		a, _ := strconv.Atoi(S[0:1])
		for j := 0; j < n-1; j++ {
			//fmt.Printf("i:%d j:%d x:%d\n", i, j, i&(1<<uint(j)))
			if (i & (1 << uint(j))) > 0 {
				sm += a
				a = 0
			}
			s, _ := strconv.Atoi(S[j+1 : j+1+1])
			a = a*10 + s
		}
		sm += a
		r += sm
	}
	fmt.Println(r)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pf push_front
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
typedef pair<ii, ii> pii;

int main(int argc, char** argv) {
	ll N, D, x, y, ans = 0;
	cin >> N >> D; D *= D;
	rep(i, 0, N) {
		cin >> x >> y;
		ans += (x*x+y*y <= D);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_set>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};
vector<ll> g[110000], in(110000);
UnionFind u(210000);
vector<ll> out;
int main() {
	ll n, m, k;
	cin >> n >> m >> k;
	REP(i, m) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		u.unionSet(a, b);
		in[a]++;
		in[b]++;
	}
	REP(i, k) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	REP(i, n) {
		ll ans = u.size(i);
		ans -= in[i];
		REP(j, g[i].size()) {
			if (u.findSet(i, g[i][j]))ans--;
		}
		out.push_back(ans - 1);
	}
	REP(i, n) {
		if (i != 0)cout << " ";
		cout << out[i];
	}
	cout << endl;
}



Measured memory_bytes: 9460
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

int main() {
    int N;
    cin >> N;

    string W[N];
    REP(0, i, N) {
        cin >> W[i];
    }

    REP(1, i, N) {
        if (W[i - 1][W[i - 1].size() - 1] != W[i][0]) {
            // cout << "W[i]="<< W[i] << endl;
            cout << "No" << endl;
            return 0;
        }
    }

    sort(W, W + N);

    REP(1, i, N) {
        if (W[i - 1] == W[i]) {
            // cout << "W[i]="<< W[i] << endl;
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace competitive_programming
{
    class Program
    {
        static void Main(string[] args)
        {
            var main = new Program();
            main.solve();
        }

        void solve()
        {
            string S = Console.ReadLine();
            int Q = int.Parse(Console.ReadLine());

            //0:forward 1:backward
            int dir = 0;
            List<char> front = new List<char>();
            List<char> back = new List<char>();

            for(int i = 0;i < Q;i++)
            {
                var query = Console.ReadLine().Split(' ');

                if (query.Length == 1)
                {
                    //1
                    dir = dir == 0 ? 1 : 0;
                }
                else
                {
                    //2
                    if(query[1] == "1")
                    {
                        if(dir == 0)
                        {
                            front.Add(query[2][0]);
                        }
                        else
                        {
                            back.Add(query[2][0]);
                        }
                    }
                    else
                    {
                        if(dir == 0)
                        {
                            back.Add(query[2][0]);
                        }
                        else
                        {
                            front.Add(query[2][0]);
                        }
                    }
                }
            }
            front.Reverse();

            S = new string(front.ToArray()) + S + new string(back.ToArray());

            if(dir == 1)
            {
                S = new string(S.Reverse().ToArray());
            }

            Console.WriteLine(S);
        }
    }

    struct Vector2
    {
        public Vector2(int x,int y)
        {
            this.x = x;
            this.y = y;
        }
        public int x;
        public int y;
    }

    struct Vector3
    {
        public int x;
        public int y;
        public int z;
    }
}


Measured memory_bytes: 22964
#include<iostream>
#include<string.h>
#include<algorithm>
#include<functional>
using namespace std;

int main(){
    int ans=1;
    int N;
    cin>>N;
    while(1){
        if(ans>N){
            ans/=2;
            break;
        }
        ans*=2;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	int t[110000], x[110000], y[110000];
	cin >> n;
	t[0] = x[0] = y[0] = 0;
	for(int i = 0; i < n; ++i) cin >> t[i + 1] >> x[i + 1] >> y[i + 1];


	bool can = true;
	for( int i = 0; i < n; ++i ){
		int dt = t[i + 1] - t[i];
		int dist = abs(x[i+1] - x[i] ) + abs(y[i+1] - y[i]);
		if( dt < dist ) can = false;
		if( dist % 2 != dt % 2 ) can = false;
	}
	if(can) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		long n = sc.nextInt();
		long ans = 0;
		for (int i = 0; i < n; i++) {
			long a = sc.nextInt();
			int c = i + 1;
			if (c % 2 != 0 && a % 2 != 0) {
				ans++;
			}

		}

		System.out.println(ans);

	}

}


Measured memory_bytes: 27084
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=1e9;
const double PI=acos(-1);


int main() {
    ios_base::sync_with_stdio(false); 

    int h,w,a,b;
    cin >> h >> w >> a >> b;
    rep(i,h) {
        rep(j,w) {
            bool flag=(i<b)^(j<a);
            if (flag) cout << '0';
            else cout << '1';
        }
        cout << endl;
    } 
    
    

    return 0;
}


Measured memory_bytes: 3544
///              B I S M I L L A H I R  R A H M A N I R  R A H I M

#include<bits/stdc++.h>
using namespace std;
typedef bool                   boo;
typedef int                    li;
typedef long                   il;
typedef unsigned long          ul;
typedef long long int          ll;
typedef unsigned long long     ull;
typedef double                 dd;
typedef string                 str;
#define vli                    vector<li>
#define vll                    vector<ll>
#define sli                    set<li>
#define sll                    set<ll>
#define pli                    pair<li, li>
#define pll                    pair<ll, ll>
#define vpi                    vector<pair<li, li>>
#define vpl                    vector<pair<ll, ll>>
#define mpl                    map<ll, ll>
#define wt                     ll t; cin>>t; while(t--)
#define input(a,n)             for(int i=0;i<n;i++) cin>>a[i];
#define lp(a, i, b)            for(ll i=a; i<b; i++)
#define rlp(a, i, b)           for(ll i=a; i>=b; i--)
#define sz(x)                  x.size()
#define len(z)                 z.begin(), z.end()
#define ci(x)                  cin>>x;
#define co(x)                  cout<<x nl
#define mem(z, l)              memset(z, l, sizeof(z))
#define MP                     make_pair
#define pb                     push_back
#define F                      first
#define S                      second
#define nl                     <<endl
#define nll                    cout<<endl
#define sp                     <<" "<<
#define sl                     <<" "
#define cy                     cout<<"YES"<<nl
#define cn                     cout<<"NO"<<nl
#define rn                     return
#define good_bye               return 0
#define PI                     3.1415926536
#define gcd(a,b)               __gcd(a,b)
#define lcm(a,b)               (a*(b/gcd(a,b)))
#define faster                 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define input_txt()            freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
const double eps=              1e-9;
const int inf=                 2000000000;
const ll infLL=                9000000000000000000;
//ll Pow(ll P, ll Q)           { ll R=1; for(ll I=1; I<=Q; I++) R*=P; rn R; }
//void dfs(ll K)               { vis[K]=true; for(auto J: v[K]) { if(!vis[J]) dfs(J); } }
//void seive(ll MX)            { S.pb(2); for(ll I=3; i<=MX; i+=2) { if(!vis[I]) { S.pb(I); for(ll J=I*I; j<=MX; J+=(2*I)) vis[J]=false; } } }
//bool isPrime(ll n)           { if(n%2==0) rn false; for(ll i=3; i*i<=n; i+=2) { if(n%i==0) rn false; } rn true; }
//----------------------------------------LET'S BEGIN-----------------------------------------------------------------------
const int mX = 1e6+123;
ll n, k;

void case_i()
{
    ci(n>>k);
    if(k%n) cout<<k-n nl; else cout<<k+n nl;
}

int main()
{
    faster;
//    input_txt();
//    wt
      case_i();
    good_bye;
}
///           _5_4_8_8_1_9_                ///



Measured memory_bytes: 3608
/* {{{ */
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
/* }}} */

pub fn divisor(n: u64) -> Vec<u64> {
    let mut res = Vec::new();
    for i in (1..).take_while(|x| x * x <= n) {
        if n % i == 0 {
            res.push(i);
            if i != n / i {
                res.push(n / i);
            }
        }
    }
    res.sort();
    res
}

fn main() {
    input! {
        n: u64
    }
    let d = divisor(n);
    let i = d.len() / 2;
    println!("{}", d[i] + n/d[i] - 2);
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vector<int> a(n+1), b(n+1);
  a[0] = 0;
  b[0] = 0;
  REP(i, 1, n) cin >> a[i];
  REP(i, 1, n) cin >> b[i];

  vector<int> sum_a(n+1), sum_b(n+1);
  sum_a[0] = 0;
  sum_b[0] = 0;
  REP(i, 1, n){
    sum_a[i] = sum_a[i-1] + a[i];
    sum_b[i] = sum_b[i-1] + b[i];
  }

  int res = 0;
  REP(i, 1, n){
    chmax(res, sum_a[i] + (sum_b[n] - sum_b[i-1]));
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

auto clk=clock();
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define Mod 1000000007
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define all(x) x.begin(),x.end()

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b; cin>>a>>b;
    cout<<max(0,a-2*b);
    cerr<<"\n"<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<"\n";
    return 0;
}


Measured memory_bytes: 256
s = input()
n = len(s)
r,ans=0,0
for l in range(n):
    while r<n and (s[r]=="A" or s[r]=="T" or s[r]=="G" or s[r]=="C"):
        r+=1
    ans = max(ans,r-l)
    if r==l: r+=1
print(ans)

Measured memory_bytes: 3060
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

const ll mod=1e9+7;

int main(){
    ll n,m;
    cin >> n >> m;
    if(abs(n-m)>=2){
        cout << 0 << endl;
        return 0;
    }
    ll p=max(n,m);
    ll q=min(n,m);
    ll ans=1;
    if(p==q) ans*=2;
    ll r=1,s=1;
    while(p){
        r*=p;
        r%=mod;
        p--;
    }
    while(q){
        s*=q;
        s%=mod;
        q--;
    }
    ans*=(r*s)%mod;
    ans%=mod;
    cout << ans << endl;
    return 0;
} 

Measured memory_bytes: 3624
#include<iostream>
#include <string>
#include <algorithm>
#include <math.h>
#define MOD 1000000007
using namespace std;

int main()
{
	long long int n, a, ans = 0;
	int x[51];
	long long int i, j, k;
	cin >> n >> a;
	for (i = 0; i < n; i++){
		cin >> x[i];
	}
	long long int dp[51][51][2502] = {};
	dp[0][0][0] = 1;
	for (i = 0; i < n; i++){
		for (j = 0; j < i + 2; j++){
			for (k = 0; k < 50 * j+1; k++){
				if (j == 0 && k == 0){
					dp[i + 1][0][0] = 1;
				}
				else{
					if (k - x[i] >= 0){
						dp[i + 1][j][k] = dp[i][j][k] + dp[i][j - 1][k - x[i]];
					}
					else {
						dp[i + 1][j][k] = dp[i][j][k];
					}
				}
			}
		}
	}
	for (i = 0; i < n; i++){
		ans += dp[n][i+1][i*a + a];
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 51072