akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define NMAX 1000000
  
int cnt = 0;
int A[NMAX];
  
void insertionSort(int A[], int n, int g)
{
    int v;
    int i, j;
  
    for(i=g; i<n; i++) {
        v = A[i];
        j = i - g;
        while(j>=0 && A[j] > v) {
            A[j+g] = A[j];
            j = j - g;
            cnt++;
        }
        A[j+g] = v;
    }
}
  
void shellSort(int A[], int n)
{
    int i;
    int m = 13;
    int G[13] = {1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161};
    cnt = 0;
  
    while(G[m-1] > n) m--;
    printf("%d\n%d", m, G[m-1]);
    for(i=m-2; i>=0; i--) printf(" %d", G[i]);
    putchar('\n');
  
    for(i=m-1; i>=0; i--) {
        insertionSort(A, n, G[i]);
    }
}
  
int main()
{
    int i, n;
  
    scanf("%d", &n);
    for(i=0; i<n; i++) {
        scanf("%d", &A[i]);
    }
    shellSort(A, n);
    printf("%d\n", cnt);
    for(i=0; i<n; i++) printf("%d\n", A[i]);
    return 0;
}

Measured memory_bytes: 4508
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define f first
#define s second
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k;
	cin>>n>>k;
	set<int>s;
	for(int i=0;i<10;i++)
		s.insert(i);

	for(int i =0;i<k; i++)
	{
		int j;
		cin>>j;
		s.erase(j);
	}

	for(int i = n; ; i++)
	{
		int j = i;
		while(j)
		{
			int h = j%10;
			if(s.find(h)==s.end())
				break;
			j/=10;
		}
		if(!j)
		{
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

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

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////



int main() {

	string S;
	cin >> S;
	sort(S.begin(), S.end());

	if (S == "abc") { cout << "Yes"; }
	else { cout << "No"; }
	

	system("PAUSE");

	

}


Measured memory_bytes: 504
n=int(input())
a=[-1]*n
for i in range(n):
  a[i]=int(input())-1
  
reached=[False]*n

tar=0
cnt=0
suc=False
while reached[tar]==False:
  reached[tar]=True
  cnt+=1
  tar=a[tar]
  if tar==1:
    suc=True
    break
    
print((-1,cnt)[suc])


Measured memory_bytes: 7668
#N,Q =map(int,input().strip().split())
#=int(input().strip())
#=list(map(int,input().strip().split()))
S = input()

#for i in range(0,Q):


subs = []
tmp = []
for s in S:
    if "A" == s or "C" == s or "G"== s or "T" == s:
        tmp.append(s)
    else:
        subs.append(tmp)
        tmp = []

subs.append(tmp)
if len(subs) == 0:
    print("0")
    exit()

rs = sorted(subs,key=lambda x: len(x),reverse=True)
print(len(rs[0]))



Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;  

#define pb push_back
#define ll long long int
#define db double
#define SORTA(v) sort(v.begin(),v.end())
#define SORTD(v) sort(v.begin(),v.end(),greater<>())
#define endl '\n'
#define nod(N) floor(log10(N)) + 1
#define LB(a) lower_bound(a)
#define UB(a) upper_bound(a)
#define F first
#define S second
#define FOR(i,n) for(long long int i = 0;i<n;i++)
#define FOR1(i,n) for(long long int i=1;i<=n;i++)
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define REVERSE(s) reverse(s.begin(),s.end())
#define LBV(v,a) lower_bound(v.begin(),v.end(),a)
#define UBV(v,a) upper_bound(v.begin(),v.end(),a)
#define GCD(a,b) __gcd(a,b)
#define ITX(it,x1) for(auto it = x1.begin();it!=x1.end();it++)
#define I insert
#define VFIND(v1,val) find(v1.begin() , v1.end() , val )
#define VFILL(v1 , val)   std::fill(v1.begin(), v1.end(), val);
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define all(x) x.begin() , x.end() 

// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll mxm() {return LLONG_MIN;}
template<typename... Args>
ll mxm(ll a, Args... args) { return max(a,mxm(args...)); }
ll mnm() {return LLONG_MAX;}
template<typename... Args>
ll mnm(ll a, Args... args) { return min(a,mnm(args...)); }

const int MOD = 1e9 + 7;
long long int powxy(long long int x, long long int y) 
{
    if (y == 0) return 1;if (y%2 == 1) return (x*powxy(x, y-1))%MOD;
    long long int t = powxy(x, y/2);return (t*t)%MOD;
}
void DPM(map<ll,ll>m1)
{
    for(auto it = m1.begin();it!=m1.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
    cout<<endl;
}
void DPV(vector<ll>v)
{
    FOR(i,v.size())cout<<v[i]<<" ";cout<<endl;
}
void DPS(set<ll>s1)
{
    for(auto it =s1.begin();it!=s1.end();it++)cout<<*it<<" ";cout<<endl;
}
void DPA(ll arr[],ll n){FOR(i,n)cout<<arr[i]<<" ";cout<<endl;}



ll dx[4] = { 0,0,1,-1 };
ll dy[4] = { 1,-1,0,0 };
string pos = "RLDU";


int main()
{
    FAST;
    ll i ,j , T = 1;
    // cin>>T;
    while(T--)
    {
        i=0;j=0;
        
        ll n; cin>>n;

        vector<ll>v1(n);
        FOR(i,n)cin>>v1[i];
        
        ll ans = 1; bool flag = false; 
        
        FOR(i,n)
        {
            if(v1[i] == 0)flag = 1;
        }
        
        if(flag)cout<<"0"<<endl;
        else
        {
            flag = 1;
            
            FOR(i,n)
            {
                if( v1[i] > 0 && ans > (ll)1e18/ v1[i] ) {flag = 0 ; break; } 
                else ans = ans*v1[i];
            }
            if(flag)cout<<ans;
            else cout<<"-1";
            
        }
        
        
    }
}  



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

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define all(a) (a.begin(), a.end())

int main(){
    while(1){
        string s;
        cin >> s;
        
        if(s == "0")return 0;
        
        int sum = 0;
        rep(i,s.size())sum += (int)s[i] - 48;
        cout << sum << endl;
    }
}


Measured memory_bytes: 3172
#include <stdio.h>

int main()
{
    int x, y;

    scanf("%d %d", &x, &y);
    while ((x != 0) || (y != 0)) {
        if (x < y) {
            printf("%d %d\n", x, y);
        } else {
            printf("%d %d\n", y, x);
        }
        scanf("%d %d", &x, &y);
    }

    return 0;
}

Measured memory_bytes: 600
import collections

n=int(input())
lst=[]
for k in range(0,n):
  lst.append(input())
c0=collections.Counter(lst)
a,b=zip(*c0.most_common())
maxb=max(b)
op=[]
for sa,sb in zip(a,b):
  if sb==maxb:
    op.append(sa)
op.sort()
for ss in op:
  print(ss)


Measured memory_bytes: 59540
#include <stdio.h>
#include <string.h>

#define GIVEN_VALUE 7400000

char data[GIVEN_VALUE];

int main(void) {
	int m, n;
	while (scanf("%d%d", &m, &n) == 2 && (m > 0 || n > 0)) {
		int i, j;
		int left = n;
		memset(data, 0, sizeof(data));
		for (i = m; ; i++) {
			if (!data[i]) {
				if (left > 0) {
					left--;
					for (j = i; j < GIVEN_VALUE; j += i) data[j] = 1;
				} else {
					printf("%d\n", i);
					break;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 7832
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a[100005];
char s[100005];
int n;
int main(){
    scanf("%d%s",&n,s+1);
    int flag;
    for(int i=1;i<=2;i++){
        a[1]=i;
        for(int j=1;j<=2;j++){
            a[2]=j;
            flag=1;
            if(a[1]==1){
                if(s[1]=='o') a[n]=j;
                else a[n]=j%2+1;
            }
            else{
                if(s[1]=='x') a[n]=j;
                else a[n]=j%2+1;
            }
            for(int k=2;k<n-1;k++){
                if(a[k]==1){
                    if(s[k]=='o') a[k+1]=a[k-1];
                    else a[k+1]=a[k-1]%2+1;
                }
                else{
                    if(s[k]=='x') a[k+1]=a[k-1];
                    else a[k+1]=a[k-1]%2+1;
                }
            }
            int last;
            if(a[n-1]==1){
                if(s[n-1]=='o') last=a[n-2];
                else last=a[n-2]%2+1;
            }
            else{
                if(s[n-1]=='x') last=a[n-2];
                else last=a[n-2]%2+1;
            }
            if(last!=a[n]){
                flag=0;
            }
            if(a[n]==1){
                if(s[n]=='o')
                    if(a[1]!=a[n-1]) flag=0;
                if(s[n]=='x')
                    if(a[1]==a[n-1]) flag=0;
            }
            else{
                if(s[n]=='x')
                    if(a[1]!=a[n-1]) flag=0;
                if(s[n]=='o')
                    if(a[1]==a[n-1]) flag=0;
            }
            if(flag) break;
        }
        if(flag) break;
    }
    if(flag){
        for(int i=1;i<=n;i++){
            if(a[i]==1) printf("S");
            else printf("W");
        }
        printf("\n");
    }
    else printf("-1\n");
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 5;
int arr[MAX_N];
 
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    int res = 0;
    for (int i = 0; i < k; i++)
    {
        res += arr[i];
    }
    cout << res << "\n";
}

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

int main(){
  int i,j,cnt=0;
  ll n,k;
  cin>>n>>k;
  if(k%2==0)cout<<(n/k)*(n/k)*(n/k)+((2*n/k+1)/2)*((2*n/k+1)/2)*((2*n/k+1)/2);
  else cout<<(n/k)*(n/k)*(n/k);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int64_t N;
    cin >> N;
    vector<int64_t>vec(N);
    map<int, int>d;
    vector<bool>warikireru(1000001, true);
    vector<int64_t>keisan;
    for (int64_t i=0; i < N; i++) {
        cin >> vec.at(i);
        if (d.count(vec[i]) > 0) {
            warikireru[vec[i]] = false;
        } else {
            d[vec[i]] = 1;
            keisan.emplace_back(vec[i]);
        }
    }

    sort(keisan.begin(), keisan.end());
    int s = keisan.size();
    for (int i=0; i < s; i++) {
        int n = keisan[i];
        for (int k=n+n; k < 1000001; k = k + n) {
            warikireru[k] = false;
        }
    }

    int64_t sum = 0;
    for (int i=0; i < s; i++) {
        sum += warikireru[keisan[i]] ? 1 : 0;
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 15972
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll c[200010],sz[200010],ans[200010],ans2[200010],par[200010];
vector<int> G[200010],col[200010],v[200010];
int dfs(int s,int p){
    par[s] = p;
    int x = v[c[s]].back(),cnt = 1;
    col[x].push_back(s);
    for(int x:G[s]){
        if(x==p) continue;
        v[c[s]].push_back(x);
        cnt += dfs(x,s);
        v[c[s]].pop_back();
    }
    return sz[s] = cnt;
}

int main(){
    ll i,n;
    cin >> n;
    for(i=0;i<n;i++){
        cin >> c[i]; c[i]--;
    }
    for(i=0;i<n - 1;i++){
        int a,b; cin >> a >> b; a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    for(i=0;i<n;i++){
        v[i].push_back(0);
        ans2[i] = n;
    }
    dfs(0,-1);
    for(i=1;i<n;i++){
        ll num = sz[i];
        for(int x:col[i]){
            num -= sz[x];
        }
        ans[c[par[i]]] += num*(num + 1)/2;
    }
    for(int x:col[0]){
        int y = c[x];
        ans2[y] -= sz[x];
    }
    for(i=0;i<n;i++){
        cout << n*(n + 1)/2 - ans2[i]*(ans2[i] + 1)/2 - ans[i] << endl;
    }
}

Measured memory_bytes: 62000
#include<iostream>
#define F(i,n,a) for(int i=a;i<n;i++)
#define vi vector<int>
#define pb push_back
#define lli long long int
#define mod 1000000007
//realfuhrer10
using namespace std;


int main(){
    int n; cin>>n;
    n==0 ? cout<<"1" : cout<<"0";
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int h,w;
    int d[10][10];
    Rep(i,10){
        fill(d[i],d[i]+10,INF);
    }
    Scd2(h,w);
    Rep(i,10){
        Rep(j,10){
            Scd(d[i][j]);
        }
    }

    Rep(k,10){
        Rep(i,10){
            Rep(j,10){
                d[i][j] = min( d[i][j] , d[i][k] + d[k][j] );
            }
        }
    }
    int a;
    int ans = 0;
    Rep(i,h){
        Rep(j,w){
            Scd(a);
            if( a == -1 ) continue;
            ans += d[a][1];
        }
    }

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

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){
    long N, P, i, j, ans=0;

    cin >> N >> P;
    if (N==1) ans = P;
    else{
        for (i=1; i<=sqrt(P)+1; i++){
            j = pow(i, N);
            if (j <= P){
                if (!(P % j)) ans = i;
            }
            else break;
        }
    }


    cout << ans << '\n';

}

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

int main() {
  int n,a,fx;
  cin >> n;
  fx = 0;
  a = n;
  for (int i = 0; i<8; i++) {
    fx += (n%10);
    n /=10;
  }
  if (a%fx == 0 ) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
const long long INF = 1LL << 60;


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

class UnionFind {
	vector<int> data;
public:
	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)];
	}
};

int find(vector<long long> &arr, long long obj) {
	if (arr[arr.size() - 1] < obj)return arr.size()-1;
	if (arr[0] > obj)return -1;

	int min = 0; int max = arr.size() - 1;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[min+(max-min) / 2] > obj) {
			max = min + (max - min) / 2;
		}
		else {
			min = min + (max - min) / 2;
		}
		if (max - min == 1) {
			return min;
		}
	}


}

//約数求める //約数
void divisor(ll n,vector<ll> &ret) {
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(ret.begin(), ret.end());
	
}
//階乗
long long factorial(long long n, long long mod) {
	long long ret = 1;
	for (long long i = 1; i <= n; i++) {
		ret = (ret * i) % mod;
	}
	return ret;
}
//モジュラ逆数
long long inv_mod(long long n, long long mod) {
	long long a = n % mod, b = mod - 2, ret = 1;
	while (b > 0) {
		if (b & 1) ret = (ret * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ret;
}

long long nPr(long long n, long long r, long long mod) {
	long long ret = 1;
	for (long long i = n; i >= n - r + 1; i--) {
		ret = ret * (i % mod) % mod;
	}
	return ret;
}

long long nCr(long long n, long long r, long long mod) {
	return nPr(n, r, mod) * inv_mod(factorial(r, mod), mod) % mod;
}

ll gcd(ll m, ll n){
	if (n == 0)return m;
	return gcd(n, m%n);
}//gcd



int main() {
  int n,i;
  cin>>n>>i;
  cout<<n-i+1;
	return 0;
}


Measured memory_bytes: 256
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, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
    
    ($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")
    };
}

fn main() {
    input! {
        n: i32,
        mut a: [i32; n]
    }
    
    a.sort();
    a.reverse();
    
    let ans = a[0] / 2 + a.iter().skip(1).sum::<i32>();
    
    println!("{}", ans);
    
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
using ll = long long;

int main() {
    int n,q;
    string s;
    cin >> n >> q;
    cin >> s;
    vector<int> l(q);
    vector<int> r(q);
    for (int i=0;i<q;i++){
        cin >> l.at(i) >> r.at(i);
    }
    //累積和
    vector<int> sum(n+1);
    for (int i=1;i<n;i++){
        if(s[i-1]=='A' && s[i]=='C')
            sum[i+1] = sum[i]+1;
        else
            sum[i+1] = sum[i];
    }
    //クエリ
    for (int i=0;i<q;++i){
        int l_now = l.at(i);
        int r_now = r.at(i);
        cout << sum[r_now] - sum[l_now] <<endl;
    }

    
    return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <string>

using namespace std;
int main(){

    string n;
    cin>>n;
    if(n=="Sunny"){
    cout<<"Cloudy";
    }
    else if (n=="Cloudy"){
        cout<<"Rainy";
    }
else if (n=="Rainy"){
        cout<<"Sunny";
    }


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mkp make_pair
#define piii pair<int,pair<int,int> >
using namespace std;
int n,m,sx,sy,ex,ey,dist[1020][1020],nx,ny;
string grid[1020];
deque<piii> q;
int dx[24]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int dy[24]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
void addf(int dis,int x,int y){
	if(dist[x][y]<=dis) return;
	dist[x][y]=dis;
	q.push_front(mkp(dis,mkp(x,y)));
}
void addb(int dis,int x,int y){
	if(dist[x][y]<=dis) return;
	dist[x][y]=dis;
	q.push_back(mkp(dis,mkp(x,y)));
}
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>sx>>sy>>ex>>ey;
	for(int i=1;i<=n;i++){
		cin>>grid[i];
		grid[i]="?"+grid[i];
	}
	memset(dist,63,sizeof(dist));
	addb(0,sx,sy);
	int ds;
	while(q.size()){
		sx=q.front().second.first;
		sy=q.front().second.second;
		ds=q.front().first;
		q.pop_front();
		if(sx==ex&&sy==ey){
			cout<<ds<<endl;
			return 0;
		}
		if(dist[sx][sy]!=ds) continue;
		for(int i=0;i<24;i++){
			nx=sx+dx[i];
			ny=sy+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&grid[nx][ny]=='.'){
				if(abs(dx[i])+abs(dy[i])<=1)
					addf(ds,nx,ny);
				else
					addb(ds+1,nx,ny);
			}
		}
	}
	cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 8884
#include <stdio.h>
#include <stdlib.h>

int main(void){
    char n[3];
    scanf("%s",n);
    for(int i = 0;i < 3;i++){
        if(n[i] == '1'){
            n[i] = '9';
        } else {
            n[i] = '1';
        }
    }

    printf("%s",n);
}

Measured memory_bytes: 128
n = int(input())
v_list = list(map(int, input().split()))

dict1 = {}
dict2 = {}
flag = 1
for v in v_list:
  if flag > 0:
    if v in dict1:
      dict1[v] = dict1[v] + 1
    else:
      dict1[v] = 1
  else:
    if v in dict2:
      dict2[v] = dict2[v] + 1
    else:
      dict2[v] = 1
  flag = -1 * flag
list1 = list(dict1.items())
list2 = list(dict2.items())
list1_value = [t[0] for t in list1]
list1_num = [t[1] for t in list1]
list2_value = [t[0] for t in list2]
list2_num = [t[1] for t in list2]
list1_num_max = max(list1_num)
list2_num_max = max(list2_num)
if list1_value[list1_num.index(list1_num_max)] != list2_value[list2_num.index(list2_num_max)]:
  print(n - list1_num_max - list2_num_max)
else:
  ind1 = list1_num.index(list1_num_max)
  del list1_value[ind1]
  del list1_num[ind1]
  ind2 = list2_num.index(list2_num_max)
  del list2_value[ind2]
  del list2_num[ind2]
  list1_num_max_2nd = max(list1_num) if len(list1_num) > 0 else 0
  list2_num_max_2nd = max(list2_num) if len(list2_num) > 0 else 0
  if list1_num_max_2nd * list2_num_max_2nd > 0:
    print(min(n - list1_num_max - list2_num_max_2nd, 
             n- list2_num_max - list1_num_max_2nd))
  else:
    print(int(n/2))

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

int main(){
  int N, L;
  cin >> N >> L;
  vector<string> data(N);
  for(int i = 0; i < N; i++){
    cin >> data[i];
  }
  sort(data.begin(), data.end());
  for(int i = 0; i < N; i++){
    cout << data[i];
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    ll a, b, c;
    cin >> a >> b >> c;

    // a + b + 2sqrt(ab) < c
    // 2sqrt(ab) < c - (a + b)
    // 4ab < (a + b - c) ^ 2
    if (a + b > c) cout << "No" << endl;
    else if ((a + b - c) * (a + b - c) > 4 * a * b) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int main()
{
    int n, l;
    cin >> n >> l;
    vector<string> ss;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ss.push_back(s);
    }
    sort(ss.begin(), ss.end());
    for (int i = 0; i < ss.size(); i++) {
        cout << ss[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define REP(i, a, b) for (int i = (int)a; i <= (int)b; i++)
#define fi first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
 
using namespace std;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<int, int> pii;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const i64 MOD = 1000000007;
const int INF = 2000000000;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int n;
	cin >> n; 
 
    vector<double> a(n);

	REP(i, 0, n-1) {
		cin >> a[i];		
	}

	sort(all(a));

	double sum = (a[0] + a[1]) / 2;

	REP(i, 2, n-1) sum = (sum + a[i]) / 2;

	cout << sum << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,s=0,t=0,x;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>x;
    s+=x;
    t+=x*x;
  }
  x=s/N;
  cout<<min(N*x*x-2*s*x+t,N*(x+1)*(x+1)-2*s*(x+1)+t)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>
 
// #include <unordered_set>
// #include <unordered_map>
 
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
 
#define pb push_back
#define mp make_pair
 
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
 
typedef std::pair<int, std::pair<int,int> > P;
typedef long long ll;
typedef long double ld;
 
const int MOD = 1000000007;
const int INF = 1e9;
const ll LINF = INF * 1ll * INF;
const ld DINF = 1e200;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
using namespace std;
 
#define int long long
 
signed main(){

	int count=0;

	int a,b,c,d,e,f,g;
	cin>>a>>b;

	int tmp;

	for(int i=a;i<=b;i++){
		tmp=i;


		f=tmp/10000;
		g=(tmp-(f*10000))/1000;
		c=(tmp-(f*10000+g*1000))/100;
		d=(tmp-(f*10000+g*1000+c*100))/10;
		e=tmp-(f*10000+g*1000+c*100+d*10);

		// cout<<f<<g<<c<<d<<e<<endl;

		if(f==e&&d==g){
			count++;
		}

	}

	cout<<count<<endl;
}



Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/square.hpp
#ifndef SQUARE_HPP
#define SQUARE_HPP

/*
usage:

tools::square(5) => 25
*/

namespace tools {
  template <typename T>
  constexpr T square(const T x) {
    return x * x;
  }
}

#endif

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

bool is_square_number(const i64 x) {
  const i64 sqrt = static_cast<i64>(std::sqrt(x));
  return sqrt * sqrt == x;
}

bool is_valid_pair(const std::vector<i64>& X_i, const std::vector<i64>& X_j) {
  const i64 D = X_i.size();
  i64 squared_distance = 0;
  for (i64 d = 0; d < D; ++d) {
    squared_distance += tools::square(X_i[d] - X_j[d]);
  }
  return is_square_number(squared_distance);
}

int main() {
  i64 N, D;
  std::cin >> N >> D;
  std::vector<std::vector<i64>> X(N, std::vector<i64>(D));
  for (std::vector<i64>& X_i : X) {
    for (i64& X_ij : X_i) {
      std::cin >> X_ij;
    }
  }

  i64 answer = 0;
  for (i64 i = 0; i < N - 1; ++i) {
    for (i64 j = i + 1; j < N; ++j) {
      if (is_valid_pair(X[i], X[j])) ++answer;
    }
  }

  std::cout << answer << std::endl;
  return 0;
}

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

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,lessl<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define int long long
#define double long double

#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()

#define ff first
#define ss second
#define mp make_pair

#define pb push_back
#define endl "\n"

#define f(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)

#define bp __builtin_popcountll
#define inf 1e18

const int N = 1e5 + 5;
const int M = 1e9 + 7;

void solve()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a<=b*c)
		cout<<"Yes";
	else
		cout<<"No";
}

signed main()
{
	FAST

#ifndef ONLINE_JUDGE
	freopen("input_sublime.txt", "r", stdin);
	freopen("output_sublime.txt", "w", stdout);
#endif

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

#ifndef ONLINE_JUDGE
	cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
#endif
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


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

  if ( x < 1200 ) std::cout << "ABC" << std::endl;
  else std::cout << "ARC" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	long long under;

	while (scanf("%lld", &under), under){
		long long money, aizu, normal, limit;
		long long ac, nc;
		scanf("%lld %lld %lld %lld", &money, &aizu, &normal, &limit);

		ac = fmin(money / aizu, limit);
		money -= ac * aizu;
		nc = money / normal;
		money %= normal;


		if (ac == 0) puts("NA");
		else if (ac + nc < under){
			while (ac && ac + nc < under){
				ac--;
				money += aizu;
				nc += money / normal;
				money %= normal;
			}
			if (ac == 0) puts("NA");
			else printf("%lld %lld\n", ac, nc);
		}
		else printf("%lld %lld\n", ac, nc);
	}

	return (0);
}

Measured memory_bytes: 616
from enum import Enum
import sys
 
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
 
class Point():
    def __init__(self,arg_x,arg_y):
        self.x = arg_x
        self.y = arg_y
 
def calc_len(a,b):
    from math import sqrt
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
 
x1,y1,x2,y2 = map(float,input().split())
 
p1 = Point(x1,y1)
p2 = Point(x2,y2)
 
print("%.10f"%calc_len(p1,p2))


Measured memory_bytes: 6352
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

void	solve()
{
	int a, b, k;
	cin >> a >> b >> k;

	stack<int> st;
	vector<int> v;

	if (a == b) {
		cout << a << endl;
		return;
	}
	while (a <= b && k--)
	{
		v.push_back(a++);
		if (a > b) break;
		st.push(b--);
	}
	for (int x : v)
		cout << x << endl;
	while (!st.empty())
	{
		cout << st.top() << endl;
		st.pop();
	}

}

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

	solve();
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(br.readLine());
		}
		br.close();

		long ans = a[0] / 2;
		a[0] %= 2;
		for (int i = 1; i < n; i++) {
			int b = a[i - 1] + a[i];
			ans += b / 2;
			a[i] = Math.min(b % 2, a[i]);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 30804
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pl = pair<ll, ll>;
const ll INF = ll(1e18);
const ll mod = ll(1e9+7);
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll ans = 1;
    rep1(i, n){
        ans *= i;
        ans %= mod;
    }
    return ans;
}

ll power(ll a, ll b){
    ll ans = 1;
    a %= mod;
    while(b) {
        if(b & 1LL) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

//modの値の確認をすること
int main(){
    int a,b;
    cin >> a >> b;
    rep0(i, 100)rep0(j, 100)if(i + j == a && i * 2 + j * 4 == b){yes;return 0;}
    no;
    return 0;
}


Measured memory_bytes: 3636
#define B
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    static int d;
    static int[] c;
    static int[][] s;
    public static void Main()
    {
        d = int.Parse(Console.ReadLine());
        c = Console.ReadLine().Split().Select(int.Parse).ToArray();
        s = Enumerable.Repeat(0, d).Select(_ => Console.ReadLine().Split().Select(int.Parse).ToArray()).ToArray();
        var t = Enumerable.Repeat(0, d).Select(_ => int.Parse(Console.ReadLine()) - 1).ToArray();
        Score(t);
    }

    static int Score(int[] t)
    {
        int score = 0;
        int[] last = new int[26];
        for (int i = 0; i < t.Length; i++)
        {
            score += s[i][t[i]];
            last[t[i]] = i + 1;
            for (int j = 0; j < last.Length; j++)
                score -= (i - last[j] + 1) * c[j];
#if B
            Console.WriteLine(score);
#endif
        }
        return score;
    }
}



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

int main()
{
	int n; cin>>n; int a[n],b[n],c[n];
	for (int i=0; i<n; i++)
		cin>>a[i]>>b[i]>>c[i];
	for (int i=n-1; i>0; i--)
	{
		a[i-1] = max(b[i],c[i])+a[i-1];
		b[i-1] = max(a[i],c[i])+b[i-1];
		c[i-1] = max(a[i],b[i])+c[i-1];
	}
	cout<<max({a[0],b[0],c[0]});
	return 0;
}

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

using namespace std;

int N, M;
char S[100000], T[100000];

int main() {
  scanf("%d%d", &N, &M);
  scanf("%s%s", S, T);
  
  // 最大公約数を計算
  int g = __gcd(N, M);
  int stepS = N / g;
  int stepT = M / g;
  int i1 = 0;
  int i2 = 0;
  for (int i = 0; i < g; ++i, i1 += stepS, i2 += stepT) {
    if (S[i1] != T[i2]) {
      puts("-1");
      return 0;
    }
  }
  printf("%lld", 1ll * N / g * M);
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    ll a[n+2];
    rep(i,n+1) cin >> a[i];

    ll b[n];

    rep(i,n) cin >> b[i];

    ll monstercount = 0;
    // ll tmpmonstercount = 0;
    rep(i,n)
    {
        if (a[i] > b[i])
        {
            monstercount += b[i];
        }
        else
        {
            /* code */
            monstercount += a[i];
            b[i] -= a[i];
            if (a[i+1] > b[i])
            {
                monstercount += b[i];
                a[i+1] -= b[i];
            }
            else
            {
                monstercount += a[i+1];
                a[i+1] = 0;
                // b[i] = 0;
            }
            
        }
        
    }
    cout << monstercount << endl;

    // ll dp[100010][2];
    // dp[0][0] = 0;
    // dp[0][1] = 0;

    // rep(i,n)
    // {
    //     dp[i+1][0] = max(dp[i][0] + min(a[i], b[i+1]), dp[i][1] + min(a[i] - b[i] , b[i+1]));
    //     dp[i+1][1] = max(dp[i][0], dp[i][1]) + min(a[i+1], b[i+1]);

    //     cout << "dp" << i << ": " << endl;
    //     cout << dp[i+1][0] << endl;
    //     cout << dp[i+1][1] << endl;
    // }
    // cout << max(dp[n][0], dp[n][1]) << endl;
}


Measured memory_bytes: 1792
// 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(int 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(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
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> 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;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define int ll
int n,m;
vvi G;
vi used,in,tmp;
int dfs(int a,int b=0){
    tmp.pb(a);
    used[a]=b;
    rep(i,G[a].size()){
        int to=G[a][i];
        if(used[to]==2){
            if(!dfs(to,b^1))return 0;
        }else if(used[to]==b)return 0;
    }
    return 1;
}
signed main(){
    cin>>n>>m;
	vvi ee(n,vi(n));
	rep(i,m){
		int a,b;cin>>a>>b;a--;b--;
		ee[a][b]=ee[b][a]=1;
	}
    G=vvi(n);
	rep(i,n)loop(j,i+1,n)if(ee[i][j]==0){
		G[i].pb(j);
		G[j].pb(i);
	}
    used=vi(n,2);
    in=vi(n);
    ll sum=0;
    rep(i,n)if(used[i]==2){
        tmp=vi(0);
        if(!dfs(i)){
            cout<<-1<<endl;
            return 0;
        }
        ll co=0;
        rep(j,tmp.size())if(used[tmp[j]]==1)co++;else co--;
        in[abs(co)]++;
        sum+=abs(co);
    }
    vi dp(100010,-1);
	dp[0]=0;
    rep(i,n)if(in[i])rep(j,100010){
        if(dp[j]>=0)dp[j]=in[i];
        else if(j<i||dp[j-i]<=0)dp[j]=-1;
        else dp[j]=dp[j-i]-1;
    }
    ll t=inf;
    rep(i,100010)if(dp[i]>=0)t=min(t,abs(i-(sum-i)));
	t=(n+t)/2;
	cout<<t*(t-1)/2+(n-t)*(n-t-1)/2<<endl;
}






Measured memory_bytes: 5120
import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        char s[][] = new char[h + 2][w + 2];
        for (int i = 1; i < h + 1; i++) {
            String st = sc.next();
            for (int j = 1; j < w + 1; j++) {
                s[i][j] = st.charAt(j - 1);
            }
        }
        boolean pos = true;
        out: for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '#' && s[i - 1][j] != '#' && s[i + 1][j] != '#' && s[i][j - 1] != '#' && s[i][j + 1] != '#') {
                    pos = false;
                    break out;
                }
            }
        }
        if (pos) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

struct edge {
  ll to;
  int cost;
  edge(int to, ll cost) : to(to), cost(cost) {}
};

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> L(M), R(M), D(M);
  vector<vector<edge>> G(N);
  rep(i, M) {
    cin >> L[i] >> R[i] >> D[i];
    L[i]--;
    R[i]--;
    G[L[i]].pb(edge(R[i], D[i]));
    G[R[i]].pb(edge(L[i], -D[i]));
  }

  vector<ll> x(N, LINF);
  rep(i, N) {
    if (x[i] != LINF)
      continue;
    queue<int> q;
    q.push(i);
    x[i] = 0;

    while (!q.empty()) {
      int now = q.front();
      q.pop();

      for (edge& ed : G[now]) {
        if (x[ed.to] != LINF) {
          if (x[ed.to] != x[now] + ed.cost) {
            cout << "No" << endl;
            return 0;
          }
        } else {
          x[ed.to] = x[now] + ed.cost;
          q.push(ed.to);
        }
      }
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 18560
#include<iostream>
using namespace std;
int A[2005];
int n; 
bool solve(int i,int m)//在第i个元素后面有值为m的组合就返回true
{
	if(m==0)
		return true;
	if(i>=n)
		return false;
	if(solve(i+1,m)||solve(i+1,m-A[i]))
		return true;
	else return false;
		
} 
int main()
{
	//int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>A[i];
	}
	int q;
	cin>>q;
	while(q--)
	{
		int an;
		cin>>an;
		if(solve(0,an))
			cout<<"yes"<<endl;
		else
			cout<<"no"<<endl;
	} 
	return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<queue>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
using namespace std;
/****************************/
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define qi queue<int>
#define mii map<int,int>
#define msi map<string,int>
#define vs vector<string>
#define vc vector<char>
/****************************/
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define rep3(i,a,n) for(ll i=(a);i<(n);i++)
#define rep4(i,a,n) for(ll i=(n)-1;i>=a;i--)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define pi 3.1415926535897932384626433832795
#define zero(n) memset(n,0,sizeof(n));
#define SZ(n) n.size()
#define mod 1000000007
#define INF 1000000000000000000
/****************************/
int main()
{
	int a;
	cin>>a;
	ll ans;
	ans=a/500*1000;
	a%=500;
	ans+=a/5*5;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int f[1005][4105], a[1005], key[1005];
 
void cmin(int &x, int y) {x = x > y ? y : x;}
 
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int b; scanf("%d%d", &a[i], &b);
        while(b--)
        {
            int x; scanf("%d", &x);
            key[i] |= (1 << (x - 1));
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    int tot = (1 << n) - 1;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j <= tot; j++) f[i][j] = f[i - 1][j];
        for(int j = 0; j <= tot; j++) 
        cmin(f[i][j | key[i]], f[i - 1][j] + a[i]);
    }
    printf("%d\n", f[m][tot] != 0x3f3f3f3f ? f[m][tot] : -1);
    return 0;
}


Measured memory_bytes: 16384
#include<bits/stdc++.h>
using namespace std;
int main() {
  int A, B, C;
  cin >> A >> B >> C;
  int h = max({A, B, C});
  int d = 3*h - A - B - C;
  if(d&1) cout << (d/2)+2 <<endl;
  else    cout << d/2 <<endl;
}


Measured memory_bytes: 256