akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define LL long long
#define pii pair<int,int>
using namespace std;
const int inf = 2147483647;
const int N = 200001;

int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}
void put(LL x) {
	if(x < 0) putchar('-'), x = -x;
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

int s;
int a[N], b[N];
struct seg {
	int cnt, lc[N << 1], rc[N << 1], c[N << 1], p[N << 1];
	
	void bt(int l, int r) {
		int now = ++cnt;
		lc[now] = rc[now] = -1;
		if(l == r) {
			if(a[l] == b[l]) c[now] = 0;
			else c[now] = b[l];
			p[now] = l;
		}
		if(l < r) {
			int mid = (l + r) / 2;
			lc[now] = cnt + 1; bt(l, mid);
			rc[now] = cnt + 1; bt(mid + 1, r);
			if(c[lc[now]] > c[rc[now]]) c[now] = c[lc[now]], p[now] = p[lc[now]];
			else c[now] = c[rc[now]], p[now] = p[rc[now]];
		}
	}
	void change(int now, int l, int r, int P, int C) {
		if(l == r) {
			b[P] = C;
			if(b[P] < a[P]) {s = -1;}
			if(C == a[P]) {s++, c[now] = 0;
			} else c[now] = C, p[now] = P;
			return ;
		} int mid = (l + r) / 2;
		if(P <= mid) change(lc[now], l, mid, P, C);
		else change(rc[now], mid + 1, r, P, C);
		if(c[lc[now]] > c[rc[now]]) c[now] = c[lc[now]], p[now] = p[lc[now]];
		else c[now] = c[rc[now]], p[now] = p[rc[now]];
	}
} t; int n;

int pre(int x) {
	x--;
	return x == 0 ? n : x;
}
int nxt(int x) {
	x++;
	return x == n + 1 ? 1 : x;
}

int main() {
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= n; i++) b[i] = read(), s += a[i] == b[i];
	t.bt(1, n); LL ans = 0;
	while(1) {
		int hh = t.p[1];
		if(s == n) break;
		int c = b[pre(hh)] + b[nxt(hh)];
		if(c > b[hh]) {puts("-1"); return 0;}
		if((b[hh] - a[hh]) % c == 0) ans += (b[hh] - a[hh]) / c, t.change(1, 1, n, hh, a[hh]);
		else ans += b[hh] / c, t.change(1, 1, n, hh, b[hh] % c);
		if(s == -1) {puts("-1"); return 0;
		}
	} put(ans);
	return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
 
int main(){
  int A,B,X,Y;
  cin>>A>>B;
  X=B/0.1;
  Y=(B+1)/0.1;
  int Z,W;
  rep2(i,X,Y){
    Z=i*0.08;
    if(Z==A){
      W=i;
      break;
    }
    if(i==Y-1)
      W=-1;
  }
  cout << W << endl;
}


Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
// typedef tuple<int,int,int,int> tp;
// typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

//nCr mod m
#define MOD 1000000007
#define M 2200000
vector<ll> fact;
bool h=false;
void init(){
	h=true;
	fact=vector<ll>(M);
	fact[0]=fact[1]=1;
	loop(i,2,M)fact[i]=fact[i-1]*i%MOD;
}
// a^b mod MOD
ll powmod(ll a,ll b,ll m=MOD){
	ll out=1;
	ll p=a%m;
	while(b){
		if(b&1)out=out*p%m;
		p=p*p%m;
		b>>=1;
	}
	return out;
}
//nCr
ll nCr(ll n,ll r,ll m=MOD){
	if(!h)init();
	if(n<0||r<0||n<r)return 1;//??????
	ll out=fact[n]*powmod(fact[r]*fact[n-r]%m,m-2,m)%m;
	return out;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin>>n;
	int c=0,m=inf;
	rep(i,n){
		int a;cin>>a;
		if(m>a)c++;
		cmin(m,a);
	}
	cout<<c<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
制約のn*mとn,mを読み違えない
操作の逆順を考える
オーバーフローしないか確かめる
Codeforcesではscanfを使う
modの引き算には+modをする
エラー出力は消す
エラー出力を消せ！！！！！
数値の区切り位置を誤読しない
cout << fixed;
cout << setprecision(n) << ans;
 */

int main() {
    string s,t;
    cin >> s >> t;
    cout << t << s;



    
}

/*
りスタート
*/



Measured memory_bytes: 256
import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    
    r = D * 2 + 1
    q , mod = divmod(N, r)
    
    print(q if mod == 0 else q + 1)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
#include <stdio.h>

int main(void) {
    char buf[100], *csr;
    int si;
    double s[40], v;

    while (gets(buf) != NULL) {
        csr = buf;
        si = 0;
        while (*csr != '\0') {
            while (*csr == ' ') csr++;

            if (sscanf(csr, "%lf", &v) == 1) {
                while (*csr == '-' || ('0' <= *csr && *csr <= '9')) csr++;
                s[si++] = v;
            }
            else {
                si--;
                switch (*csr) {
                    case '+':
                        s[si-1] = s[si-1] + s[si]; break;
                    case '-':
                        s[si-1] = s[si-1] - s[si]; break;
                    case '*':
                        s[si-1] = s[si-1] * s[si]; break;
                    case '/':
                        s[si-1] = s[si-1] / s[si]; break;
                    default:
                        break;
                }
                csr++;
            }
        }
        printf("%.6lf\n", s[0]);
    }
    return 0;
}

Measured memory_bytes: 664
#include<iostream>
#include<vector>
#include<map>
using namespace std;

int main() {
    int N;
    cin >> N;
    map<int, int> mp;
    int cnt = 0;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        if(a / 400 >= 8) cnt++;
        else mp[a/400]++;
    }

    cout << max(1, (int)mp.size()) << " " << mp.size() + cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
using namespace std;
typedef long long Int;
typedef pair<double, double> P;
typedef pair<double, P> L;

Int n;
double a[108000], b[108000], c[108000];
Int bit[108000];
vector<L> lines;
Int cntbit(Int x){
	x++;
	Int res = 0;
	while(x){
		res += bit[x];
		x -= x & -x;
	}
	return res;
}

void addbit(Int x){
	x++;
	while(x < 108000){
		bit[x]++;
		x += x & -x;
	}
}

Int cnt(double p){
	vector<double>poInts;
	vector<double> query;
	for(Int i = 0;i < n;i++){
		bit[i+1] = 0;
		double a = lines[i].first;
		double b = lines[i].second.first;
		double c = lines[i].second.second;
		double y0 = (c - a*p) / b;
		poInts.push_back(y0);
		query.push_back(y0);
	}
	sort(poInts.begin(), poInts.end());
	poInts.erase(unique(poInts.begin(), poInts.end()), poInts.end());
	Int res = 0;
	for(Int i = 0;i < n;i++){
		Int pos = lower_bound(poInts.begin(), poInts.end(), query[i]) - poInts.begin();
		res += cntbit(pos);
		addbit(pos);
	}
	return res;
}

double solve(Int cp){
	lines.clear();
	for(Int i = 0;i < n;i++){
		lines.push_back(L(a[i]/b[i], P(1, c[i]/b[i])));
	}
	sort(lines.begin(), lines.end());
	
	double x = -1e10, y = 1e10;
	for(Int i = 0;i < 200;i++){
		double mid = (x+y) / 2;
		if(cnt(mid) <= cp)y = mid;
		else x = mid;
	}
	return y;
}

int main(){
	cin >> n;
	for(Int i = 0;i < n;i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	Int crosspoInt = n*(n-1)/2;
	double ansx = solve(crosspoInt/2);

	for(Int i = 0;i < n;i++)swap(a[i],b[i]);

	double ansy = solve(crosspoInt/2);
	printf("%.10lf %.10lf\n", ansx, ansy);
	return 0;
}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
int n,k,h[200005];
long long ans;
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>h[i];
	sort(h,h+n);
	k=n-k;
	for(int i=0;i<k;i++)
		ans+=h[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		long N = sc.nextInt();
		long M = sc.nextInt();
		char[] S = sc.next().toCharArray();
		char[] T = sc.next().toCharArray();
		long gcd = gcd(N, M);
		for (int i = 0; i < gcd; i++) {
			if (S[(int)(i * N / gcd)] != T[(int)(i * M / gcd)]) {
				System.out.println(-1);
				return;
			}
		}
		long lcm = N / gcd * M;
		System.out.println(lcm);
	}

	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
}


Measured memory_bytes: 26616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  rep(i,n) p[i]++;
  int mx = 0;
  int s = 0;
  queue<int> q;
  rep(i,n) {
    s += p[i];
    q.push(p[i]);
    if (q.size() > k) {
      s -= q.front(); q.pop();
    }
    if (q.size() == k) {
      mx = max(mx, s);
    }
  }
  double ans = mx;
  ans /= 2;
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int main()
{
	int i,j,n,a[100005],t[100005];
	cin >> n;
	memset(a,0,sizeof(a));
	memset(t,0,sizeof(t));
	for(i=0;i<n;i++)
	{
		cin >> j;
		a[j]+=1;
	}
	int max=a[0]+a[1]+a[2];
	for(i=0;i<100005;i++)
	{
		t[i]=a[i]+a[i+1]+a[i+2];
		if(t[i]>max)
		max=t[i];
	}
	printf("%d",max);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL a, b;
    cin >> a >> b;

    if(a > b){
        swap(a, b);
    }

    for(LL i = b;; i+=b){
        if(i % a == 0){
            cout << i << "\n";
            return 0;
        }
    }

}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int n;
int a[100001];
int b[100001];
int currXorA = 0;
int currXorB = 0;
map<int, int> mpA, mpB;
map<int, vector<int> > g, gr;
set<int> used;
vector<int> order;
vector<int> component;

void dfs1 (int v) {
	used.insert(v);
	for (int i=0; i<g[v].size(); ++i)
		if (!used.count(g[v][i]))
			dfs1(g[v][i]);
	order.push_back (v);
}
 
void dfs2 (int v) {
	used.insert(v);
	component.push_back (v);
	for (size_t i=0; i<gr[v].size(); ++i)
		if (!used.count(gr[v][i]))
			dfs2(gr[v][i]);
}

int get(vector<int>& com) {
	if (com.size() == 1) return 0;
	
	for (int x : com) {
		if (x == currXorA || x == currXorB) {
			return 0;
		} 
	}
	return 1;
}
 
int main() {
	ios_base::sync_with_stdio(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		currXorA ^= a[i];
	}
	a[n++] = currXorA;
	
	for (int i = 0; i < n - 1; i++) {
		cin >> b[i];
		currXorB ^= b[i];
	}
	b[n - 1] = currXorB;
	
	for (int i = 0; i < n; i++) {
		if (mpA.find(a[i]) == mpA.end()) mpA[a[i]] = 0;
		mpA[a[i]]++;
	}
	
	for (int i = 0; i < n; i++) {
		if (mpB.find(b[i]) == mpB.end()) mpB[b[i]] = 0;
		mpB[b[i]]++;
	}
	
	for (pair<int, int> curr : mpB) {
		int x = curr.first;
		int cnt = curr.second;
		if (mpA.find(x) == mpA.end()) {
			cout << -1;
			return 0;
		}
		if (cnt != mpA[x]) {
			cout << -1;
			return 0;
		}
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) {
			if (i != n - 1) ans++;
			gr[a[i]].push_back(b[i]);
			g[b[i]].push_back(a[i]);
		}
	}
	
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i] && !used.count(a[i])) {
			dfs1(a[i]);
		}
	}
	used.clear();
	for (int i=0; i<order.size(); ++i) {
		int v = order[order.size() - 1 - i];
		if (!used.count(v)) {
			dfs2(v);
			ans += get(component);
			component.clear();
		}
	}
	
	cout << ans;
	
	return 0;
}

Measured memory_bytes: 45692
N, Y = (int(i) for i in input().split())
N1000 = Y // 1000
n10000 = N1000 // 10
r1 = N1000 % 10
n5000 = r1 // 5
n1000 = r1 % 5

if N1000 < N:
	print("-1 -1 -1")
	exit(0)

while n10000 >= 0:
	while n5000 >= 0:
		n = n10000 + n5000 + n1000
		if n == N:
			print(n10000, n5000, n1000)
			exit(0)
		n5000 -= 1
		n1000 += 5
	n5000 = (n1000-5) // 5
	n1000 = (n1000-5) % 5
	n10000 -= 1
	n5000 += 2

print("-1 -1 -1")

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,data,m,h,w,x,y,xcmp,ycmp,sum=0;

string s;

vector<int> z;

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);

       cin >> a >> b >> c >> d;
       cmp=max(a,c);
       cmpp=min(b,d);
       if(cmpp-cmp<0){
           Cout(0);
       }
       else{
           Cout(cmpp-cmp);
       }
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int input_n;
    int input_num[1000];
    int output_num[1000];

    scanf("%d", &input_n);
    for (int i = 0; i < input_n; i++) {
        scanf("%d", &input_num[i]);
    }

    for (int i = 0; i < input_n; i++) {
        output_num[i] = input_num[input_n - i - 1];
    } 

    for (int i = 0; i < (input_n - 1); i++) {
        printf("%d ", output_num[i]);
    }
    printf("%d\n", output_num[input_n -1]);
}


Measured memory_bytes: 2068
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define yes "Yes\n"
#define no "No\n"
//int m,n;
//int i,j,k,l;
int a,b,c,d,e,f,g;
//int sum,total;
//long long int ;
//float ;
//double ;
//char a[101],b[101],s[101],t[101],u[101];
int main(void){
    scanf("%d %d",&a,&b);
    if (a < 10 && b < 10)
    {
        printf("%d\n",a * b);
    } else
    {
        printf("-1\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int a[101];
	int n;
	int i;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	cout<<a[n-1];
	for(i=n-2;i>=0;i--){
		cout<<" "<<a[i];
	}
	cout<<endl;
	return 0;
}
	


Measured memory_bytes: 3100
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
int n,tot;
int a[1005][1005],b[1005][1005],d[1005][1005],bl[1005][1005];
int q[1005],cnt,q1[1005],cnt1,vis[1000005],vis1[1005][1005],vis2[1005];
struct op
{
    int x,y,xx,yy;
    inline int de(){return d[x][y]+d[xx][yy];}
}c[1000002];
int main()
{
    n=read();reg int i,j,to,too,gs=0;
    for(i=1;i<=n;++i)for(j=1;j<n;++j)
        a[i][j]=read(),b[i][a[i][j]]=j;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<n;++j)
        {
            d[i][j]=1;
            if(vis1[i][j])continue;
            to=a[i][j];too=b[to][i];vis1[to][too]=1;
            c[++tot]=(op){i,j,to,too};
            bl[i][j]=tot;bl[to][too]=tot;
        }
    }
    for(i=1;i<=n;++i)d[i][1]=0,d[i][n]=1;
    for(i=1;i<=tot;++i)
        if(c[i].de()==0)q[++cnt]=i;
    if(cnt==0){cout<<-1;return 0;}
    for(i=1;i<=1000000;++i)
    {
        cnt1=0;
        for(j=1;j<=cnt;++j)
        {
            d[c[q[j]].x][c[q[j]].y+1]=0;
            d[c[q[j]].xx][c[q[j]].yy+1]=0;
            if(!vis2[c[q[j]].x]&&d[c[q[j]].x][n]==0)
                gs++,vis2[c[q[j]].x]=1;
            if(!vis2[c[q[j]].xx]&&d[c[q[j]].xx][n]==0)
                gs++,vis2[c[q[j]].xx]=1;
            q1[++cnt1]=bl[c[q[j]].x][c[q[j]].y+1];
            q1[++cnt1]=bl[c[q[j]].xx][c[q[j]].yy+1];
            vis[bl[c[q[j]].x][c[q[j]].y+1]]=0;
            vis[bl[c[q[j]].xx][c[q[j]].yy+1]]=0;
        }
        cnt=0;
        for(j=1;j<=cnt1;++j)
        {
            if(vis[q1[j]])continue;vis[q1[j]]=1;
            if(q1[j]>0&&c[q1[j]].de()==0)q[++cnt]=q1[j];
        }
        if(cnt1==0){cout<<-1;return 0;}
        if(gs==n){cout<<i;return 0;}
    }
    cout<<-1;
    return 0;
}


Measured memory_bytes: 33408
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] tmp = new int[n+1];
        
        for(int i=1; i<=n; i++){
            int a = sc.nextInt();
            tmp[a] = i;
        }
        
        for(int i=1; i<=n; i++){
            System.out.print(tmp[i] + " ");
        }
    }
}

Measured memory_bytes: 63172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
struct edge{
	int to,nxt; 
}e[maxn];
int head[maxn],tot;
void add(int x,int y){
	e[++tot].to=y;
	e[tot].nxt=head[x];
	head[x]=tot;
}
int n,X,d;
struct goods{
	ll cost;int val,id;
}a[maxn];
bool operator<(goods a,goods b){return a.val*b.cost>b.val*a.cost; }
ll dp[maxn*maxn*maxn];
void dfs(int x){
    a[x].val=1,a[x].id=x;
    for(int i=head[x];i;i=e[i].nxt){
    	int y=e[i].to;
    	dfs(y);
    	a[x].cost+=a[y].cost;
    	a[x].val+=a[y].val;
    }
}
int main(){
    cin>>n>>X>>d;//n个物品  
    cin>>a[1].cost;
    for(int i=2,x;i<=n;++i)
        cin>>a[i].cost>>x,add(x,i);
    dfs(1); 
	int N=n*n*n,L=min(n,d);//每个物品拿出L个 
    memset(dp,0x3f,sizeof(dp)),dp[0]=0;//dp[i]表示收益为i时最少需要多少代价 
    //先把每个物品拿出来min(n,d)个出来dp 
	for(int i=1;i<=n;++i){
        int x=L;
        for(int j=0;1<<j<=x;++j){//倍增地选第i个物品 
            int val=a[i].val*(1<<j);ll cost=a[i].cost*(1<<j);
            for(int k=N;k>=val;--k)dp[k]=min(dp[k],dp[k-val]+cost);
            x-=1<<j;
        }
        if(x){//还有剩余 
            int val=a[i].val*x; 
			ll cost=a[i].cost*x;
            for(int j=N;j>=val;--j)dp[j]=min(dp[j],dp[j-val]+cost);
        }
    }
    sort(a+1,a+n+1);
    while(a[n].id!=1)--n;//比a[1]性价比还低的可以直接排除 
    ll ans=0;
    for(int i=0;i<=N;++i){
        if(dp[i]>X)continue;
        ll val=i,cost=dp[i];
        for(int j=1;j<n;++j){//性价比从高到低选 每个都尽量选完 
            ll c=min((ll)d-L,(X-cost)/a[j].cost);
            val+=c*a[j].val,cost+=c*a[j].cost;
        }
        ll c=(X-cost)/a[n].cost;//最后如果还有余量 可以选a[1] 
        val+=c*a[n].val,cost+=c*a[n].cost;
        ans=max(ans,val);
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n;
  R n;
  ll a[n];
  rep(i,n) R a[i];
  ll ans=0;
  rep(i,n) {
    while(a[i]%2==0) {
      a[i]/=2;
      ans++;
    }
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 384
import java.io.*;

public class Main {

    public static void main(String[] args){
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try{
            String st = br.readLine();
            String[] s = st.split(" ", 0);
            int k = Integer.parseInt(s[0]);
            int maxk = k/2;
            int t = Integer.parseInt(s[1]);
            st = br.readLine();
            s = st.split(" ", 0);
            int maxa = 0;
            for(int i = 0; i < t;i++){
                int a = Integer.parseInt(s[i]);
                if(maxa<a){
                    maxa = a;
                }
            }
            int x = maxa - maxk;
            if(x<=0||(x==1&&(k%2)==1)){
                System.out.println("0");
            }else{
                System.out.println(1+(x-1)*2);
            }
        }catch(IOException ex){
        }
    }
}

Measured memory_bytes: 8272
import java.util.*;
import java.lang.Math.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) a[i] = sc.nextInt();
		int m = sc.nextInt();
		int[] b = new int[m];
		for(int i = 0; i < m; i++) b[i] = sc.nextInt();
		boolean flag = true;
		for(int i = 0; i < Math.min(n, m); i++){
			if(a[i] < b[i]){
				System.out.println(1);
				return;
			}
			if(a[i] > b[i]){
				System.out.println(0);
				return;
			}
		}
		if(m > n) System.out.println(1);
		else System.out.println(0);
	}
}



Measured memory_bytes: 32352
#include <bits/stdc++.h>
using namespace std;
#define lint long long
//#define P pair<int, int>

int main(){
    int A, B, C, D, E, F;
    
    cin >> A >> B >> C >> D >> E >> F;
    
    int mA = F / (100 * A), mB = F / (100 * B);
    
    float ans = -1;
    int As = 0;
    int Aw = 0;
    
    for(int a = 0; a <= mA; ++a){
        for(int b = 0; b <= mB; ++b){
            int water = 0;
            water = 100 * (A * a + B * b);
            if(water >= F || water == 0){
                continue;
            }
            int S = min(water * E / 100, F - water);
            int mC = S / C;
            int mD = S / D;
            
            for(int c = 0; c <= mC; ++c){
                for(int d = 0; d <= mD; ++d){
                    int sugar = c * C + d * D;
                    if((sugar + water) > F || water * E / 100 < sugar){
                        continue;
                    }
                    
                    
//                    cout << water << " " << sugar << endl;
                    if(ans < ((float)100 * sugar) / (water + sugar)){
                        ans = (float)(100 * sugar) / (water + sugar);
                        As = sugar;
                        Aw = water;
                    }
                }
            }
        }
    }
    
    cout << Aw + As << " " << As << endl;
    
    
}

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

// definitions
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i, l, r) for (long long i = (l); i < (long long)(r); i++)
#define repb(i, r, l) for (long long i = (r); i > (long long)(l); i--)
#define pb push_back
#define mod1 998244353
#define mod 1000000007
#define MAX_CHAR 256

using namespace std;
typedef vector<long long> vl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector< pair<long long, long long> > vp;
typedef vector<tuple<long long , long long , long long> > vtup;
typedef deque <long long> dq;
typedef long long int lli;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;


// standard functions
ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 
 


ll modexp(ll x, ll ex, ll modp) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x)%modp;
        ex >>= 1ll;
        x = (x * x)%modp;
    }
    return ans;
} 
 
ll nCrModp(ll n, ll r, ll p) 
{ 
    ll C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; 
    for (ll i = 1; i <= n; i++) 
    { 
        for (ll j = min(i, r); j > 0; j--) 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
}
 
bool isPrime(ll n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true;  
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
 
vl countFreq(ll arr[], ll n) 
{ 
    unordered_map<ll, ll> mp; 
    vector <ll> v;
    
    for (ll i = 0; i < n; i++) 
        mp[arr[i]]++; 
   
    for (auto x : mp) 
        v.pb(x.second);
    
    return v;
}

ll binarySearch(ll arr[], ll l, ll r, ll x) 
{ 
    while (l <= r) 
    { 
        ll m = l + (r - l) / 2; 
        if (arr[m] == x) 
            return m; 
        if (arr[m] < x) 
            l = m + 1; 
        else
            r = m - 1; 
    }
    return -1; 
}

const ll MAXSIEVE=(1e3);
ll spf[MAXSIEVE];
void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2; i<MAXSIEVE; i++) 
        spf[i] = i; 

    for (ll i=4; i<MAXSIEVE; i+=2) 
        spf[i] = 2; 
  
    for (ll i=3; i*i<MAXSIEVE; i++) 
    { 
        if (spf[i] == i) 
        { 
            for (ll j=i*i; j<MAXSIEVE; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
}

// code beigns in main
int main()
{
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    
    while(t--)
    {
        ll n,m;
        cin >> n >>m;

        ll arr[m];
        ll sum=0;
        rep(i,0,m)
        {
            cin >> arr[i];
            sum+=arr[i];
        }

        if(n-sum<0)
        cout << -1 << endl;
        else
        cout << n-sum << endl;
    }
}



Measured memory_bytes: 3724
//By Zank100
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define din(t) long long t;cin>>t;
#define in(t) cin>>t;
#define full(t) t.begin(),t.end()
ll mul(ll a, ll b)
{
    return(((a%mod)*(b%mod))%mod);
}
ll modexp(ll b, ll e){
	ll res = 1;
	for(; e; b = b * b % mod, e >>= 1) if(e & 1) res = res * b % mod;
	return res;
}
ll modinv(ll a){
    ll x=mod-2;
	return modexp(a,x);
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	din(n);
	ll a[n];
	for(ll i=0;i<n;i++)in(a[i]);
	ll ans=0;
	for(ll i=0;i<n;i++)if((i+1)%2==1&&a[i]%2==1)ans++;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3640
x,l=int(input()),[0]*1001;l[1]=1
for i in range(2,int(x**0.5)+1):
  if l[i]==0:j=i*i
  while 1:
    if j>x:break
    else:l[j]=1;j*=i
for i in range(x,-1,-1):
  if l[i]==1:print(i);break

Measured memory_bytes: 9228
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 998244353;


     signed main(){
         cout << std::fixed << std::setprecision(15);
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
if(a[0]==0){
     cout<<0<<endl;
     return 0;
}
for(int i=1;i<n;i++){
     if(a[i]>1000000000000000000ll/a[i-1]){
          cout<<-1<<endl;
          return 0;
     }
     a[i]*=a[i-1];
}
cout<<a[n-1]<<endl;






 }

 


 






    





      

        


Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x,long long int y) 
{ 
    long long int res = 1;     // Initialize result 
  // x=x;
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x); 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x);  // Change x to x^2 
    } 
    return res; 
}
long long int power(long long int x,long long int y,long long int m) 
{ 
    long long int res = 1;     // Initialize result 
   x=x%m;
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x)%m; 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x)%m;  // Change x to x^2 
    } 
    return res; 
}

long long int gcd(long long int a, long long int b){ 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
 } 
 long long int lcm(long long int a, long long int b)  
 { 
     long long int temp;
    
    return (a*b)/gcd(a, b);  
 }
 
int main() {
    
        
        long long int n,m,o=0,l,d=1,i,j,p=0,k,f;
       double pie=3.141592653589793238;
    long long int MOD=1000000007;
    cin>>n;
    long long int a[n];
   cout<<(((n-1)*n)/2);
 return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program {
    static void Main(string[] args) {
        //入力
        string s = Console.ReadLine();
        int N = int.Parse(s.Split(' ')[0]);
        int M = int.Parse(s.Split(' ')[1]);

        int[] L = new int[M];
        int[] R = new int[M];

        //変数の割り当て
        for (int i = 0; i < M; i++) {
            string t = Console.ReadLine();
            L[i] = int.Parse(t.Split(' ')[0]);
            R[i] = int.Parse(t.Split(' ')[1]);
        }

        //検証
        //Lの中の最大値と、Rの中の最小値を求める
        int L_max = L.Max();
        int R_min = R.Min();


        //出力
        if (L_max > R_min) {
            Console.WriteLine(0);
        } else {
            Console.WriteLine(R_min - L_max + 1);
        }
    }
}

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

int main() {
  int N;
  int m=1000000001;
  int M=0;
  int A;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A;
    m=min(m,A);
    M=max(M,A);
  }
  cout<<M-m<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define Max 100001
#define inf 1000000000000000
using namespace std;
int n,m,flag;
int first[Max * 2],nextv[Max * 2],u[Max * 2],v[Max * 2],s[Max * 2];
long long vis[2][Max],l = 0,r = inf,ans;
void dfs(int from,int tag,long long va) {
    if(flag)return;
    int k = first[from];
    while(k != -1) {
        if(flag)return;
        int vtag = (tag == 1);
        int to = v[k];
        long long lva = s[k] - va;
        if(vis[vtag][to] != inf) {
            if(vis[vtag][to] == lva) {
                k = nextv[k];
                continue;
            }
            else {
                flag = 1;
                return;
            }
        }
        vis[vtag][to] = lva;
        if(vtag)r = min(r,lva);
        else l = max(l,-lva);
        if(r - l <= 1){
            flag = 1;
            return;
        }
        dfs(to,-tag,lva);
        k = nextv[k];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    memset(first,-1,sizeof(first));
    for(int i = 1;i <= n;i ++) {
        vis[0][i] = vis[1][i] = inf;
    }
    for(int i = 0;i < m;i ++) {
        scanf("%d%d%d",&u[i],&v[i],&s[i]);
        u[i + m] = v[i];
        v[i + m] = u[i];
        s[i + m] = s[i];
        nextv[i] = first[u[i]];
        first[u[i]] = i;
        nextv[i + m] = first[u[i + m]];
        first[u[i + m]] = i + m;
    }
    dfs(1,1,0);///dfs遍历所有点和第一个点的关系，如果有冲突flag为1 冲突就是说得到于同一点的同一关系的值不同比如a1 + a2 = 3 和 a1 + a2 = 4
    if(!flag) {///遍历后无冲突
        long long temp = -1;
        for(int i = 1;i <= n;i ++) {
            if(vis[0][i] != inf && vis[1][i] != inf) { ///可以确定a1
                long long d = vis[1][i] - vis[0][i];
                if(d % 2) {
                    flag = 1;
                    break;
                }
                temp = d / 2;
            }
        }
        if(!flag) {
            if(temp != -1) {///不能直接求出a1
                if(temp > l && temp < r)ans = 1;
            }
            else if(r - l - 1 > 0)ans = r - l - 1;
        }
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 15872
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0)
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define int long long
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int gcd(int n, int m)
{
    if(n == 0)
        return m;
    else
        return gcd(m % n, n);
}
int32_t main()
{
    IOS;
    int n;
    cin >> n;
    int a[n + 5];
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if(i % 2 == 1 && a[i] % 2 == 1)
            cnt++;
    }
    cout << cnt << endl;
}

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

int gcd(int x,int y){
	while(x != y){
		if(x > y) x -= y;
		else y -= x;
	}
	return x;
}

int main(){
	int a,b;
	cin >> a >> b;
	cout << gcd(a,b) << endl;
	return 0;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
//typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back     
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
const int mod=1e9+7;         
const int N=1e6+4;
 
int main()
{	
	int n; scn(n);

	int a[n],b[n];

	rep(i,0,n)
	scn(a[i]),scn(b[i]);

	sort(a,a+n); sort(b,b+n);

	int ans;

	if(n&1)
	ans=b[n/2]-a[n/2]+1;
	else
	ans=(b[(n/2)-1]+b[n/2])-(a[(n/2)-1]+a[n/2])+1;
    
	pri(ans);
	
    return 0;
}

Measured memory_bytes: 5332
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4,sse4.1,sse4.2,avx,avx2,tune=native")
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amax(T& a,T b){ if(a>b) a=b;}


int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, m;
	cin >>n  >>m;
	VI d(m);
	rep(i, m){
		int k; cin >>k;
		rep(j, k){
			int s; cin >>s;
			d[i] |= 1<<(s-1);
		}
	}
	VI p(m);
	rep(i, m) cin >>p[i];
	int ans =0;
	rep(i, 1<<n){
		bool ng = 0;
		rep(j, m){
			int c = __builtin_popcount( d[j] & i );
			if(c % 2 != p[j]) ng=1;
		}
		if(!ng) ans++;
	}
	
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;
typedef long long ll;

int main() {
    double a, b, v, pi = 3.14159265358979;

    cin >> a >> b >> v;
    if (v == a * a * b) cout << 0 << endl;
    else if (v <= a * a * b / 2) { // 底面は三角形
        double x = 2 * v / a / b;
        double theta = atan(b / x) * 180 / pi;
        cout << setprecision(12) << theta << endl;
    }
    else { // 底面は大経
        double y = 2 * v / a / a - b;
        double theta = atan((b - y) / a) * 180 / pi;
        cout << setprecision(12) << theta << endl;
    }

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
template <class Key, class Compare = less<Key>>
using Tree = __gnu_pbds::tree<Key, __gnu_pbds::null_type, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;






void Main() {
  int n;
  cin >> n;
  static double p[3000];
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  // dp[i][h] = probability of having h heads after throwing coins [0..i-1]
  static double dp[3000][3000];
  dp[0][0] = 1.0;
  for (int i = 0; i < n; ++i) {
    for (int h = 0; h <= i; ++h) {
      dp[i+1][h+1] += p[i]       * dp[i][h];
      dp[i+1][h]   += (1 - p[i]) * dp[i][h];
    }
  }
  double ans = 0;
  for (int h = n / 2 + (n % 2); h <= n; ++h) {
    ans += dp[n][h];
  }
  cout << setprecision(15) << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
//  cin.tie(nullptr);
  #ifdef _DEBUG
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  #endif
  Main();
  return 0;
}


Measured memory_bytes: 68992
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pi pair<int,int>
#define ff first
#define ss second
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#include "string"

const int N =  2e5 + 5;
int xx[4]={0,0,1,-1};
int yy[4] ={1,-1,0,0};

int32_t main(){
   boost;
   int n,m,k;
   cin>>n>>m>>k;
   int x1,y1,x2,y2;
   cin>>x1>>y1>>x2>>y2;
   char c[n+1][m+1];
   for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++)
         cin>>c[i][j];
   }
   int dp[n+1][m+1];
   memset(dp,1,sizeof dp);
   dp[x1][y1] = 0;
   queue<array<int,2>>q;
   q.push({x1,y1});
   while(!q.empty()) {
      array<int,2> p = q.front();
      q.pop();
      if(p[0]==x2 && p[1]==y2)
         break;
      for(int i=0;i<4;i++){
         for(int j=1;j<=k;j++){
            int x = p[0] + xx[i]*j;
            int y = p[1] + yy[i]*j;
            if(x<1 or x>n or y<1 or y>m or c[x][y]=='@')
               break;
            if(dp[x][y] > dp[p[0]][p[1]]+1){
               dp[x][y] = dp[p[0]][p[1]]+1;
               q.push({x,y});
            }
            else if(dp[x][y] == dp[p[0]][p[1]])
               break;
         }
      }
   }
   if(dp[x2][y2] == dp[0][0])
      cout<<-1<<endl;
   else
      cout<<dp[x2][y2]<<endl;
}



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

#define MAX 1000000

int H, A[MAX+1];

void MaxHeapify(int i);

int main() {
    cin >> H;
    
    for ( int i = 1; i <= H; i++ ) cin >> A[i];
    
    for ( int i = H/2; i >= 1; i-- ) MaxHeapify(i);
    
    for ( int i = 1; i <= H; i++ ) {
        cout << " " << A[i];
    }
    cout << endl;
    
    return 0;
}

void MaxHeapify(int i) {
    int L = 2 * i;
    int R = 2 * i + 1;
    
    int largest;
    // ?????????????????¨?????????????,??????????????¶??£?¶???¢??¬??????????????¶??¶?????????????£
    if ( L <= H && A[L] > A[i] ) {
        largest = L;
    } else {
        largest = i;
    }
    if ( R <= H && A[R] > A[largest] ) largest = R;
    
    if ( i != largest ) {
        swap(A[i], A[largest]);
        MaxHeapify(largest);
    }
}

/*
10
4 1 3 2 16 9 10 14 8 7
 */

Measured memory_bytes: 4932
// Problem : H - Grid 1
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_h
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize("O3")  
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define pii pair<int,int>
#define S second
#define endl "\n"
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define mem(z,i) memset(z,i,sizeof(z))
#define eps 1e-7
#define I (int)
#define mod 1000000007
#define pb push_back
const long long INF = 1000000000000000000LL;
//const int WASTE=∞
const int N=1e5+5;
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  	// cout<<fixed;
  	// cout.precision(10);
   	int r,c;
   	cin>>r>>c;
   	char a[r][c];
   	for(int x=0;x<r;x++) for(int y=0;y<c;y++) cin>>a[x][y];
   	int dp[r][c]; mem(dp,0);
   	dp[0][0]=1;
   	for(int x=0;x<r;x++){
   		for(int y=0;y<c;y++){
   			if(a[x][y]=='.'){
   				if(y-1>=0) dp[x][y]=(dp[x][y-1])%mod;
   				if(x-1>=0) dp[x][y]=(dp[x][y]+dp[x-1][y])%mod;
   			}
   		}
   	}
   	cout<<dp[r-1][c-1];
   	
   	
   	
   	
   	
   	
   	
   	
   	
   	
  	return 0;
}



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

int main(){
	int N;
  	cin >> N;
	int cnt = 0;
	for(int i = 1; i <= N; i++){
		int a;
		cin >> a;
		if(a != i) cnt++;
	}
	if(cnt == 0 || cnt == 2) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>

using namespace std;

int main(){
    string S;
    cin>>S;
    
    int zerostart=0,onestart=0;

    for(int i=0;i<S.size();i++){
        if(i%2==0){
            if(S[i]=='0') onestart++;
            else zerostart++;
        }else{
            if(S[i]=='0') zerostart++;
            else onestart++;
        }
    }
    cout<<min(zerostart,onestart)<<endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int sumso=0,sumnum=0,co=0,strs=0,ko=0;
    double sob[2]={0,0},n;
    string str;
    while(cin>>str){
        n=str.size();
        for(int i=0;i<=n;i++){
            if(str[i]==','||str[i]=='\0'){
                for(int j=strs;j<i;j++)sob[co]+=(str[j]-'0')*pow(10,i-j-1);
                co++;
                strs=i+1;
            }
        }
    sumso+=sob[0]*sob[1];
    sumnum+=sob[1];
    ko++;
    for(int i=0;i<2;i++)sob[i]=0;
    co=0;strs=0;
    }
    if(sumnum&ko!=0)co=1;
    cout<<sumso<<endl<<sumnum/ko+co<<endl;
}

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


int main() {
    double a,b,x,ans;
    cin >> a >> b >> x;
    if(x < a*a*b/2){
        ans = atan(a*b*b/2/x);
    } else ans = atan(2*(a*a*b-x)/a/a/a);

    double pi = acos(-1.0);
    ans = ans * 180 / pi;
    cout << fixed << setprecision(11) << ans << endl;
}


Measured memory_bytes: 4044
import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # 全ての長方形候補に対して、2次元累積和を使って内部の点の個数を算出する
    x_coord = [i[0] for i in xy]
    x_coord.sort()
    x_val_num = {x_coord[i]: i for i in range(N)}
    y_coord = [i[1] for i in xy]
    y_coord.sort()
    y_val_num = {y_coord[i]: i for i in range(N)}

    # 2次元累積和の計算
    xy_cnt = [[0] * N for _ in range(N)]
    for x, y in xy:
        xy_cnt[y_val_num[y]][x_val_num[x]] = 1
    # for i in xy_cnt:
    #     print(i)
    xy_acm = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            xy_acm[i+1][j+1] = xy_cnt[i][j] + xy_acm[i+1][j] + xy_acm[i][j+1] - xy_acm[i][j]
    # for i in xy_acm:
    #     print(i)

    ans = INF
    for yl, yu in itertools.combinations(range(N + 1), 2):
        for xl, xu in itertools.combinations(range(N + 1), 2):
            cnt = xy_acm[yu][xu] - xy_acm[yu][xl] - xy_acm[yl][xu] + xy_acm[yl][xl]
            # print(cnt, yl, yu, xl, xu)
            if cnt >= K:
                ans = min((x_coord[xu-1] - x_coord[xl]) * (y_coord[yu-1] - y_coord[yl]), ans)

    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9392
import java.io.*;
import java.util.*;
 
 class Main {
 
	static long[][] dp;
 
	public static void main(String[] args)  {
 
		Scanner scn = new Scanner(System.in);
 
		int n = scn.nextInt();
 
		int[] a = new int[n];
 
		for (int i = 0; i < n; i++)
			a[i] = scn.nextInt();
 
		long[] dp = new long[n];
 
		dp[n - 1] = 0;
		dp[n - 2] = Math.abs(a[n - 2] - a[n - 1]);
 
		for (int i = n - 3; i >= 0; i--) {
 
			dp[i] = Math.min(dp[i + 1] + Math.abs(a[i] - a[i + 1]), dp[i + 2] + Math.abs(a[i] - a[i + 2]));
		}
 
		System.out.println(dp[0]);
 
	}
 
}
 
 


Measured memory_bytes: 50148
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: Allen
 *
 * Created on January 12, 2019, 5:56 PM
 */

#include <cstdlib>
#include <iostream>
#include <stdio.h>
using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    int n;
    cin>>n;
    double prob[n+1];
    for(int i=1;i<=n;i++){
        cin>>prob[i];
    }
    double dp[n+1];
    for(int i=0;i<=n;i++){
        dp[i]=0;
    }
    dp[0]=1;
    for(int i=1;i<=n;i++){    
        for(int j=i;j>=1;j--){
            dp[j]=prob[i]*dp[j-1]+((1-prob[i])*dp[j]);
        }
        dp[0]*=(1-prob[i]);
    }
    double ans=0;
    for(int i=n/2+1;i<=n;i++){
        ans+=dp[i];
    }
    printf("%.10f\n",ans);
    return 0;
}



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

using namespace std;
int INF = 1e9+5;
int main(){
    int n;
    cin>>n;
    vector<int> H(n);
    for(int i=0; i<n; ++i){
        cin>>H[i];
    }
    vector<int> dp(n, INF);
    dp[0]=0;
    for(int i=0; i<n; ++i){
        for(auto k : {i+1,i+2}){
            if(k<n){
            dp[k]=min(dp[i]+abs(H[i]-H[k]), dp[k]);
            }
        }
    }
    cout<<dp[n-1]<<"\n";
}

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

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

using namespace std;

class mint{
	static const int MOD=1e9+7; // 998244353;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint pow(mint m,long long k){
	mint res=1;
	for(;k>0;k>>=1,m*=m) if(k&1) res*=m;
	return res;
}

map<long long,int> prime_factorize(long long a){
	map<long long,int> res;
	if(a%2==0){
		int cnt=0;
		do{ cnt++; a/=2; }while(a%2==0);
		res.emplace(2,cnt);
	}
	for(long long p=3;p*p<=a;p+=2) if(a%p==0) {
		int cnt=0;
		do{ cnt++; a/=p; }while(a%p==0);
		res.emplace(p,cnt);
	}
	if(a>1) res.emplace(a,1);
	return res;
}

int main(){
	int n; scanf("%d",&n);
	vector<int> a(n);
	rep(i,n) scanf("%d",&a[i]);

	map<long long,int> pf;
	rep(i,n){
		for(auto q:prime_factorize(a[i])){
			pf[q.first]=max(pf[q.first],q.second);
		}
	}

	mint L=1;
	for(auto q:pf) L*=pow(mint(q.first),q.second);

	mint ans=0;
	rep(i,n) ans+=L/a[i];
	cout<<ans<<'\n';

	return 0;
}


Measured memory_bytes: 896