akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

int main( void )
{
	int n;
	while ( cin >> n, n ) {
		int w, h;
		cin >> w >> h;
		
		VVI field( h, VI( w, 0 ) );
		
		for ( int i = 0; i < n; ++i ) {
			int x, y;
			cin >> x >> y;
			field[y - 1][x - 1] = 1;
		}

		int s, t, ans = 0;
		cin >> s >> t;
		
		for ( int y = 0; y + t <= h; ++y ) {
			for ( int x = 0; x + s <= w; ++x ) {
				int cnt = 0;
				for ( int dy = 0; dy < t; ++dy ) {
					for ( int dx = 0; dx < s; ++dx ) {
						cnt += field[y + dy][x + dx];
					}
				}
				ans = max( ans, cnt );
			}
		}
		
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp make_pair
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
template<class T> ostream& operator<<(ostream &o, const set<T> &v){o<<"[";for(auto t:v){o<<t<<",";}o<<"]";return o;}
template<class T,class U> ostream& operator<<(ostream &o, const map<T,U> &v){o<<"[";for(auto t:v){o<<t<<",";}o<<"]";return o;}

const long MOD = 998244353;
const long N = 300000;
long fact[N+5];
long finv[N+5];

long mod_pow(long x, long n, long p=MOD){
  if(x==0) return 0;
  long res=1;
  x %= p;
  while(n>0){
    if(n&1) res=res*x%p;
    x=x*x%p;
    n>>=1;
  }
  return res;
}
inline long mod_inv(long x, long p=MOD){ return mod_pow(x%p, p-2, p); }


int main(){
  long n,A,B,k;
  cin>>n>>A>>B>>k;

  fact[0] = 1;
  rep(i,N) fact[i+1] = (i+1)*fact[i] %MOD;
  finv[N] = mod_inv(fact[N]);
  for(int i=N; i>0; i--) finv[i-1] = finv[i]*i %MOD;

  // long ans = 0;
  // for(long a=0; a<=n; a++){
  //   if((k-a*A)%B != 0) continue;
  //   long b = (k-a*A)/B;
  //   if(b>n || b<0) continue;
  //
  //   long tmp = 0;
  //
  //   for(int ab=max<int>(a+b-n, 0); ab<=min(a,b); ab++){
  //     tmp += finv[a-ab] * finv[b-ab] %MOD * finv[n-a-b+ab] %MOD * finv[ab] %MOD;
  //   }
  //
  //   ans += tmp;
  // }
  // ans %= MOD;
  // ans = ans * fact[n] %MOD;

  long a2 = 0;
  for(long a=0; a<=n; a++){
    if((k-a*A)%B != 0) continue;
    long b = (k-a*A)/B;
    if(b>n || b<0) continue;

    a2 += fact[n] * fact[n] %MOD * finv[n-a] %MOD * finv[a] %MOD * finv[b] %MOD * finv[n-b] %MOD;
  }

  // dbg(ans,a2);

  cout << a2%MOD << endl;

  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>

#define mod 1000000007
#define REP(i,n) for(int i=0; i<n; i++)

using namespace std;
using ll = long long;

void solve() {
    int n, res = 1;
    cin >> n;
    int d[n];
    REP(i, n) cin >> d[i];

    sort(d, d+n);

    int temp = d[0];
    for(int i = 1; i < n; i++){
        if(temp < d[i]){
            res++;
            temp = d[i];
        }
    }
    cout << res << endl;
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define PB push_back
#define MP make_pair
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x, y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
/* (๑╹◡╹) */
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll 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;
}
/* (๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹)(๑╹◡╹) */
///////////////////////////////////////////////
const int MAX = 510000;
 
long long fac[MAX], finv[MAX], inv[MAX];
 



int main() {
	int ans = 0;
	int N; cin >> N;
	string a = "Yes";
	vector<pair<int,int> > saikyou(N);
	for (int i = 0; i < N; i++)
	{
		int a ,b; cin >> a >> b;
		saikyou[i].first = b;
		saikyou[i].second = a;
	}
	sort(ALL(saikyou));
	ll A = 0;
	ll B = 0;
	for (int i = 0; i < N; i++)
	{
		A += saikyou.at(i).second;
		B = saikyou.at(i).first;
		if(A>B){a = "No";break;}
	}
	
	
	cout << a << endl;
}


Measured memory_bytes: 1792
sa=list(input())
sb=list(input())
sc=list(input())
sa.reverse()
sb.reverse()
sc.reverse()
fst='a'
while True:
  if fst=='a':
    if len(sa)==0:
      print('A')
      break
    else:
      fst=sa.pop()
  if fst=='b':
    if len(sb)==0:
      print('B')
      break
    else:
      fst=sb.pop()
  if fst=='c':
    if len(sc)==0:
      print('C')
      break
    else:
      fst=sc.pop()

Measured memory_bytes: 38256
#!/usr/bin/env python3
import sys


def solve(K: int, X: int):
    ans = [i for i in range(max(-1000000, X-K+1),min(X+K, 1000000))]
    print(*ans)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(K, X)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll mod = 1000000007;
struct mint{
	ll x;
	mint(ll x = 0):x((x%mod+mod)%mod){}
	mint operator-() const{return mint(-x);}
	mint& operator+=(const mint a){
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if(!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if(t&1) a *= *this;
		return a;
	}
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
	bool operator==(const mint a){
		return x == a.x;
	}
};

//istream& operator>>(istream& is, const mint& a){return is >> a.x;}
//ostream& operator<<(ostream& os, const mint& a){return os << a.x;}

// 2^n
mint f(int n){
	if(n == 0) return 1;
	mint x = f(n/2);
	x *= x;
	if(n%2 == 1) x *= 2;
	return x;
}

// nCa
mint choose(int n, int a){
	mint x = 1, y = 1;
	rep(i,a){
		x *= n-i;
		y *= i+1;
	}
	return x / y;
}

struct Combination{
	vector<mint> fact, ifact;
	Combination(int n):fact(n+1),ifact(n+1){
		assert(n < mod);
		fact[0] = 1;
		for(int i = 1; i <= n; i++) fact[i] = fact[i-1]*i;
		ifact[n] = fact[n].inv();
		for(int i = n; i >= 1; i--) ifact[i-1] = ifact[i]*i;
	}
	mint operator()(int n, int k){
		if(k < 0 || k > n) return 0;
		return fact[n]*ifact[k]*ifact[n-k];
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	rep(i,n) cin >> a[i];
	sort(a.begin(), a.end());
	Combination comb(n+1);
	mint ans = 0;
	rep(i,n){
		ans += (mint)a[i] * comb(i, k-1);
		ans -= (mint)a[i] * comb(n-1-i, k-1);
		//cout << ans.x << endl;
	}
	cout << ans.x << endl;
	return 0;
}


Measured memory_bytes: 5568
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  vector<int> a(3);
  for (auto &i : a) cin >> i;
  sort(all(a));
  cout << a[2] * 10 + a[0] + a[1] << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


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

int main() {
  int N, A, B;
  
  cin >> N >> A >> B;
  int T = A * N;
  
  if (T <= B) {
    cout << T << endl;
  }
  else if (T >= B){
    cout << B << endl;
  }
}


Measured memory_bytes: 3552
S = input()
target = "AKIHABARA"
s = 0
for i in range(len(target)):
    if s < len(S):
        if S[s] != target[i]:
            if target[i] == "A":
                continue
            else:
                print("NO")
                break
        else:
            s += 1
    else:
        if target[i] == "A":
            continue
        else:
            print("NO")
            break
else:
    if s != len(S):
        print("NO")
    else:
        print("YES")


Measured memory_bytes: 3060
import Control.Applicative
import Control.Monad
import Data.List
import Data.Bool (bool)

main :: IO ()
main = do
  [n, w, h] <- f
  solve w h <$> replicateM n (g <$> f) >>= putStrLn
  where
    f = map read <$> words <$> getLine
    g [x, y, w] = ((x - w, x + w), (y - w, y + w))

solve :: Int -> Int -> [((Int, Int), (Int, Int))] -> String
solve w h ps = let xs = sort . map fst $ ps
                   ys = sort . map snd $ ps
               in bool "No" "Yes" $ f w 0 xs || f h 0 ys
  where
    f mx cp as
      | cp >= mx = True
      | null as = False
      | cp < up = False
      | vp < cp = f mx cp rs
      | otherwise = f mx vp rs
      where
        ((up, vp):rs) = as



Measured memory_bytes: 159788
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a,b,c,d;
	while(cin>>a>>b>>c>>d)
	{
		if(a*b>=c*d)
			cout<<a*b<<endl;
		else
			cout<<c*d<<endl;
	}
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
char s[1000001];
long long a=0,b=0;
int main()
{
    cin>>s;
    a=strlen(s)-2;
    for (int i=0,j=strlen(s)-1;i<j;i++,j--)
    {
        if (s[i]==s[j])
        b++;
    }
    if (b==(a+2)/2)
    cout<<"Second"<<endl;
    else
    {
    if (s[0]==s[strlen(s)-1])
    {
        a=a-1;
        if (a%2==0)
        cout<<"Second"<<endl;
        else
        cout<<"First"<<endl;
    }
    else
    {
    if (a%2==0)
    cout<<"Second"<<endl;
    else
    cout<<"First"<<endl;	
    }
    }
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <array>
#include <vector>
#include <cmath>

using namespace std;

static void printArray(int A[], int N) {
  for (int i = 0; i < N; i++) {
    cout << A[i] << endl;
  }
}

static void inputArray(int A[], int N) {
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
}

static int insersionSort(int A[], int N, int g) {
  int v, j, count = 0;
  for (int 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;
      count++;
    }
    A[j + g] = v;
  }
  return count;
}

static int shellSort(array<int, 1000000>& A,  int N) {
  array<int, 1000000> sortArray(A);
  int g = 1, startedIndex = 0, count = 0;
  vector<int> G = { 1 };
  for (; g < N; ) {
    G.push_back(g);
    g = 4 * g;
  }
  for (g = G.size() - 1;  g >= 0; g--) {
    if (G[g] * 2 > N) {
      continue;
    }
    if (startedIndex == 0) {
      startedIndex = g;
    }
    count += insersionSort(sortArray.data(), N, G[g]);
/* ★ここは不要？？
    if (count > pow(N, 1.5f)) {
      sortArray = A;
      continue;
    } 
*/
  }

  cout << startedIndex + 1 << endl;
  for (int i = startedIndex; i >= 0; i--) {
    cout << G[i];
    cout << ' ';
  }
  cout << endl;
  cout << count << endl;
  A = sortArray;
  return count;
}
  
int main() {
  int N;
  cin >> N;

  array<int, 1000000> A;
  inputArray(A.data(), N);

//  printArray(A.data(), N);

  shellSort(A, N);

  printArray(A.data(), N);
  
  return 0;
}



Measured memory_bytes: 10992
O = gets.chomp
E = gets.chomp
Oa = O.split("")
Ea = E.split("")
A = Array.new
lengO = O.length
lengE = E.length
if lengO == lengE
    for i in 0..lengO-1
        A[2 * i] = Oa[i]
        A[2 * i + 1] = Ea[i]
    end
else
    for i in 0..lengE-1
        A[2 * i] = Oa[i]
        A[2 * i + 1] = Ea[i]
    end
    A[2 * lengE] = Oa[lengO-1]
end
puts A.join('')


Measured memory_bytes: 1788
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, K; cin >> n >> K;
    string in; cin >> in;

    int m = 1;
    rep(i, 1, n){
        if(in[i] != in[i - 1]){
            m++;
        }
    }
    while(K > 0 and m > 2){
        K--;
        m -= 2;
    }
    if(K > 0){
        m = 1;
    }

    cout << n - m << endl;

    return 0;
}


Measured memory_bytes: 512
import java.util.*;

public class Main {

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		player playersArray[][]=new player[3][8];
		player threeArray[]=new player[3];
		for(int i=0;i<3;i++){
			for(int j=0;j<8;j++){
				playersArray[i][j]=new player(sc.nextInt(),sc.nextDouble());
			}
		}
		for(int i=0;i<3;i++){
			Arrays.sort(playersArray[i]);
		}
		for(int i=0;i<3;i++){
			threeArray[i]=playersArray[i][2];
		}
		Arrays.sort(threeArray);
		
		for(int i=0;i<3;i++){
			for(int j=0;j<2;j++){
				System.out.println(playersArray[i][j].number+" "+playersArray[i][j].time);
			}
		}
		System.out.println(threeArray[0].number+" "+threeArray[0].time);
		System.out.println(threeArray[1].number+" "+threeArray[1].time);
	}
	static class player implements Comparable<player>{
		int number;
		double time;
		player(int number,double time){
			this.number=number;
			this.time=time;
		}
		@Override
		public int compareTo(player obj){
			if(this.time<obj.time)return -1; //自分よりもobjが大きければ-1
			if(this.time>obj.time)return 1;//自分よりもobjが小さければ1
			return 0;//自分と同じならば0
		}
	}

}

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

int main(){
    string a, b, c;
    cin >> a;
    cin >> b;
    cin >> c;
    queue<char> a_q;
    queue<char> b_q;
    queue<char> c_q;

    for (int i=0;i<a.size();i++){
        a_q.push(a[i]);
    }
    for (int i=0;i<b.size();i++){
        b_q.push(b[i]);
    }
    for (int i=0;i<c.size();i++){
        c_q.push(c[i]);
    }

    char latest = a_q.front();
    a_q.pop();
    if (a_q.empty()){
        cout << "A" << endl;
        return 0;
    }
    while (true){
        if (latest == 'a'){
            if (a_q.empty()){
                cout << "A" << endl;
                return 0;
            }
            latest = a_q.front();
            a_q.pop();

        } else if (latest == 'b'){
            if (b_q.empty()){
                cout << "B" << endl;
                return 0;
            }
            latest = b_q.front();
            b_q.pop();
        } else {
            if (c_q.empty()){
                cout << "C" << endl;
                return 0;
            }
            latest = c_q.front();
            c_q.pop();
        }

    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n, prev, cur, next, ret=0;
    std::cin >> n;
    std::cin >>  prev >> cur >> next;
    if((prev<cur && cur<next) || (prev>cur && cur>next))
        ret++;
    for(int i=2; i<n; ++i){
        prev = cur;
        cur = next;
        std::cin >> next;
        if((prev<cur && cur<next) || (prev>cur && cur>next))
            ret++;
    }
    std::cout << ret << std::endl;
    return 0;
        
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 105;
int a[N];
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int sum = 0;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		sum += a[i];
	}

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

	int t = n - m + 1;
	if (a[t] * 4 * m < sum)
		puts("No");
	else
		puts("Yes");

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
    int N;
    int x = 0;
    int max = 0;
    string s;

    cin >> N >> s;

    for (int i = 0; i < N; i++) {
        if (s[i] == 'I') {
            x++;
        } else if (s[i] == 'D') {
            x--;
        }
        if (x >= max) {
            max = x;
        }
    }

    cout << max << endl;
}

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

int main() {
    int n, k, p = 1e9 + 7;
    cin >> n >> k;
    long r = 0;
    for(; k < n + 2; k++)
        (r += k * long(n + 1 - k) + 1) %= p;
    cout << r << endl;
    return 0;
}


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

int main()
{
	char n[3];
	scanf("%s", &n);
	if(strcmp(n, "MON") == 0) printf("6");
	else if(strcmp(n, "TUE") == 0) printf("5");
	else if(strcmp(n, "WED") == 0) printf("4");
	else if(strcmp(n, "THU") == 0) printf("3");
	else if(strcmp(n, "FRI") == 0) printf("2");
	else if(strcmp(n, "SAT") == 0) printf("1");
	else if(strcmp(n, "SUN") == 0) printf("7");
	return 0;
}


Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))

if N == 2:
  print(abs(h[1] - h[0]))
  exit()


DP = [0 for i in range(N)]

DP[1] = abs(h[1] - h[0])
DP[2] = abs(h[2] - h[0])

for i in range(1, N - 1):
  ###i+1について
  #現在値と|hi+1 - hi|を比較
  t = DP[i] + abs(h[i+1] - h[i])
  if DP[i+1] > t:
    #最小値を更新
    DP[i+1] = t
  if i != N - 2:
    ##i+2はそのまま更新
    DP[i+2] = DP[i] + abs(h[i+2] - h[i])

print(DP[N-1])

Measured memory_bytes: 13908
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<list>
#include<stack>
#include<map>
#include<set>
#include<string>
#include <sstream>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;

// sorting pairs

struct Point{
  int x;
  int y;

  bool operator<(const Point& another) const{
    if(x < another.x){
      return true;
    }
    if(x == another.x){
      if(y < another.y){
        return true;
      }
    }

    return false;
    
  }
  
};

int main(){
  long ii,jj,kk;
  vector<int> ret;
  int n;
  vector<Point> p;

  cin >> n;

  p.resize(n);

  for(ii=0;ii<n;ii++){
    cin >> p[ii].x >> p[ii].y;
  }
  
  sort(p.begin(),p.end());
  
  for(ii=0;ii<n;ii++){
    cout << p[ii].x << " " << p[ii].y << endl;
  }
  
  return 0;

}



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

int64_t gcd(int64_t p,int64_t q){
	if(p%q==0)return q;
	return gcd(q,p%q);
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	int64_t ans; cin>>ans;
	for(int i=1;i<n;++i){
		int64_t t; cin>>t;
		ans=ans/gcd(ans,t)*t;
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 256
var
  a,b:array[1..10000]of integer;
  n,i,j,k,l,x,y:integer;
begin
  readln(x,y);
  readln(n);
  k:=0;
  for i:=1 to n do
  begin
    read(b[i]);
    for j:=k+1 to k+b[i] do a[j]:=i;
    k:=k+b[i];
  end;
  for i:=1 to x do
  begin
    if (i mod 2=1) then
    begin
      for j:=1+y*(i-1) to y*i do  write(a[j],' ');
    end
    else  if (i mod 2=0) then
    begin
      for j:=y*i downto 1+y*(i-1) do write(a[j],' ');
    end;
  writeln;
  end;
end.

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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
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 (a>b) { a=b; return 1; } return 0; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<vector<int>>ship(n);
rep(i,m){
    int a,b;
    cin>>a>>b;
    a--,b--;
    ship[a].pb(b);
    ship[b].pb(a);
}
string ans="IMPOSSIBLE";
for(auto v:ship[0]){
    for(auto v2: ship[v]){
        if(v2==n-1){
            ans="POSSIBLE";
        }
    }
}

cout<<ans<<endl;

return 0;
}

Measured memory_bytes: 12016
#include<bits/stdc++.h>
using namespace std;
#define MAX 100001
#define inf 1<<30

int n,m,s;
vector<pair<int,int> > e[MAX];

void solve(){
    priority_queue<pair<int,int> > pq;
    int d[MAX];
    fill(d,d+MAX,inf);
    d[s] = 0;
    pq.push(make_pair(0,s));
    while(pq.size()){
        pair<int,int> state = pq.top();
        int v = state.second,cost = -state.first;
        pq.pop();
        if(d[v] < cost)continue;
        
        for(int i=0;i<e[v].size();i++){
            int u = e[v][i].first;
            int n_cost = cost+e[v][i].second;
            if(n_cost<d[u]){
                d[u] = n_cost;
                pq.push(make_pair(-n_cost,u));
            }
        }
    }
    for(int i=0;i<n;i++){
        if(d[i]==inf)cout<<"INF"<<endl;
        else         cout<<d[i]<<endl;
    }
}

int main(){
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[a].push_back(make_pair(b,c));
    }
    solve();
}


Measured memory_bytes: 13124
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

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

int main(){
    string O,E;
    cin >> O >> E;
    REP(i,E.length()){
        cout << O[i] << E[i];
    }
    if(E.length()!=O.length()){
        cout << O[O.length()-1];
    }
}

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

int main() {
  int w,h,n;
  int x[100],y[100],a[100];
  cin >> w >> h >> n;
  int x1 = 0, y1 = 0, x2 = w, y2 = h;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> a[i];
  }
  for (int i = 0; i < n; i++) {
    switch (a[i]) {
      case 1:
      x1 = max(x1,x[i]);
      break;
      case 2:
      x2 = min(x2,x[i]);
      break;
      case 3:
      y1 = max(y1,y[i]);
      break;
      case 4:
      y2 = min(y2,y[i]);
      break;
    }
  }
  int area;
  if (x1 >= x2 || y1 >= y2) {
    area = 0;
  } else {
    area = (x2 - x1) * (y2 - y1);
  }
  cout << area << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <queue>
#include <cstdio>
#include <numeric>


using namespace std;



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

    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<int> dist(N);

    for (int j = 0; j < N - 1; j++) dist[j] = A[j + 1] - A[j];
    dist[N-1] = A[0] + (K - A[N - 1]);

    sort(dist.begin(), dist.end(),greater<int>());
    dist.erase(dist.begin());

    accumulate(dist.begin(), dist.end(), 0);


    cout << accumulate(dist.begin(), dist.end(), 0) << endl;
  
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ll n;
    cin>>n;
    vector<ll> a(n,0);
    for(ll i=0;i<n;i++){cin>>a[i];a[i]=a[i]-i-1;}
    sort(a.begin(),a.end());
    ll b=a[n/2];
    ll ans=0;
    for(ll i=0;i<n;i++)ans+=abs(a[i]-b);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <unordered_map>
#include <unordered_set>
using namespace std;
    
#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define POW_10_9 1000000000
#define INF (numeric_limits<int>::max()/2)
#define int long long
    
typedef long long ll;
typedef pair<int,int> Pair;
    
string S;
int ans=0,zero=0,one=0;
    
signed main(){
    cin >> S;
    REP(i,S.size()){
        if(S[i] == '0') zero++;
        else one++;
    }
    ans = 2*MIN(zero,one);
    cout << ans << endl;
}

Measured memory_bytes: 512
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var (N, i) = Slice2<long>();
            WriteLine(N + 1 - i);
        }


        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

Measured memory_bytes: 27392
/*
Powered by 0736TuT
Code + Music + Games = Life
*/

#include<iostream>
#include<cstdio>
#define MAXN 110

typedef long long qwq;

using namespace std;

int scan(int *buf_tar)
{
    char buf_c=0; bool is_rev=0;
    while(buf_c!='-'&&(buf_c<'0'||buf_c>'9')) {buf_c=getchar(); if(buf_c==EOF) return EOF;}
    if(buf_c=='-') is_rev=1,buf_c=getchar();
    *buf_tar=0;
    while(buf_c>='0'&&buf_c<='9') {*buf_tar*=10; *buf_tar+=buf_c-'0'; buf_c=getchar();}
    if(is_rev) *buf_tar=-*buf_tar;
    return 0;
}

int n,Max;
int v[MAXN],w[MAXN];
int f[10010];

int main()
{
    scan(&n); scan(&Max);
    for(int i=1;i<=n;i++) {scan(&v[i]); scan(&w[i]);}
    for(int i=1;i<=n;i++) for(int j=w[i];j<=Max;j++) if(f[j]<f[j-w[i]]+v[i]) f[j]=f[j-w[i]]+v[i];
    printf("%d\n",f[Max]);
    return 0;
}

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

int main(){
  
  int n;
  cin >> n;
   vector<int> d(n);
   for(int i = 0; i < n; i++) cin >> d[i];
  int ans = 0;
  for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
          		ans += d[i] * d[j];
          
        }
  }
  
        cout << ans << endl;
}

  
  
  
   	

Measured memory_bytes: 256
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
    WRITER:kakitamasziru/OxOmisosiru
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
//#include <unordered_map> // unordered_map
//#include <unordered_set> // unordered_set
#include <bitset> // bitset
//#include <cctype> // isupper, islower, isdigit, toupper, tolower
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

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; }
const long long INF = 1001001001001001;
const int MOD = 1000000007;
typedef pair<long long,long long> P;
//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}



int main() {
    int N;cin >> N;
    int M;cin >> M;
    vector<P> student(N);
    vector<P> check(M);
    for(int i = 0;i<N;i++){
        cin >> student.at(i).first >> student.at(i).second;
    }
    for(int i = 0;i<M;i++) cin >> check.at(i).first >> check.at(i).second;
    int count = 0;
    long long dist;
    long long D = INF;
    vector<int> ans(N);
    for(int i = 0;i<N;i++){
        for(int j = 0;j<M;j++){
            dist = abs(student.at(i).first - check.at(j).first)+abs(student.at(i).second - check.at(j).second);
            if(D > dist) {
                D = dist;
                count = j+1;
            }
        }
        ans.at(i) = count;
        count = 0;
        D = INF;
    }

    for(int i = 0;i<N;i++) cout << ans.at(i) << endl;

    // PLEASE GIVE ME THE "ACCEPTED" !
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
using namespace std;

#define int long long
#define REP(i,n) for(int i=0;(i)<(n);(i)++)
#define ll long long

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

	int x = 1, y = 1;
	int t, a;
	int mal;
	REP(i, N) {
		cin >> t >> a;

		mal = max((x + t - 1) / t, (y + a - 1) / a);

		/*
		if (x > t) {
			mal = (x + t - 1) / t;
			t *= mal;
			a *= mal;
		}
		if (y > a) {
			mal = (y + a - 1) / a;
			t *= mal;
			a *= mal;
		}
		*/

		x = t * mal;
		y = a * mal;
	}

	cout << x + y << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MX = 100005;
#define rep(i,n) for(int i=0; i<(n); i++)
int n, q, k, tri[MX*4][26], nm[MX*4][26], v[MX][26][26], w[MX], e=1, ans;
string s[MX], p;
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	rep(l,2) rep(i,n){
		if(!l) cin >> s[i];
		for(int t=0,z=(int)s[i].size(),u=0,j=0; j<z; j++, t=tri[t][u]){
			u = s[i][j] - 'a';
			if(!l){
				if(!tri[t][u]) tri[t][u] = e++;
				nm[t][u]++;
			}else{
				rep(k,26) v[i][u][k] += nm[t][k];
				if(j==z-1) w[i] = nm[t][u];
			}
		}
	}
	cin >> q;
	rep(i,q){
		cin >> k >> p; k--;
		ans = w[k];
		rep(j,26) rep(l,j) ans += v[k][p[l]-'a'][p[j]-'a'];
		printf("%d\n", n - ans + 1);
	}
}

Measured memory_bytes: 294272
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<iomanip>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
int n;
ll temp,S[200005],la[200005];
int k;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>temp;
		S[i]=S[i-1]+temp;//s[]数组代表前n项和
		la[i]=((S[i]-i)%k+k)%k;//储存(s[i]-i)%k
	}
	ll ans=0;
	map<ll,ll> cnt;//cnt映射第一个ll代表0~k-1的某个值，第二个ll代表该值对应的个数
	cnt[0]=1;//对于la[0]=0的初始化
	for(int j=1;j<=n;j++)
	{
		if(j-k>=0)//当队列长度达到临界k
			cnt[la[j-k]]--;//队列最左侧出队
		ans+=cnt[la[j]];//记录答案
		cnt[la[j]]++;//队列最右侧入队
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 15872
n = int(input())
a = list(map(int, input().split()))

temp = sum(a) // n

ans = 10 ** 9 + 7
for i in range(-1, 2):
    target = temp + i
    cost = 0
    for n in a:
        cost += (target - n) ** 2
    ans = min(ans, cost)

print(ans)


Measured memory_bytes: 3060
#include<stdio.h>

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

  char s[101];
  scanf("%s", s);

  int ans = 0;

  for(int i=0; i<=n; i++){
    char moji[130] = {0};
    int shurui = 0;
    char s1[101] = {0};  
    char s2[101] = {0};
    for(int j=0; j<i; j++){
      s1[j] = s[j];
      moji[s1[j]] = 1;
    }
    for(int j=i; j<=n; j++){
      s2[j-i] = s[j];
      if( moji[s2[j-i]] == 1){
	moji[s[j]] = 2;
      }
    }
    for(int j=95; j<130; j++){
      if(moji[j] == 2) {
	shurui++;
      }
    }
    if(ans<shurui) ans = shurui;
    //    printf("(%s,%s) = %d\n", s1,s2, shurui);
  }

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

  return 0;
}


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

using namespace std;

int main() {
  string s, t;
  cin >> s >> t;
  int n = s.size(), m = t.size();
  vector<vector<int>> dp(n+1, vector<int> (m+1));
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      if (s[i-1] == t[j-1])
        dp[i][j] = 1 + dp[i-1][j-1];
      else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
   }
  string res;
  int len = dp[n][m];
  while (len) {
    if (s[n-1] == t[m-1]) {
      res.push_back(s[n-1]);
      --n; --m; --len;
    }
    else if (dp[n-1][m] > dp[n][m-1]) {
      --n;
    }
    else
      --m;
  }
  reverse(res.begin(), res.end());
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 35584
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int k, x;
    cin >> k >> x;
    vector<int> ans;
    for (int i = -1000000; i <= 1000000; ++i) {
        if(abs(i-x) < k) ans.emplace_back(i);
    }
    for (int i = 0; i < ans.size(); ++i) {
        if(i) cout << " ";
        cout << ans[i];
    }
    puts("");
    return 0;
}

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

class MyClass
{
    static void Main(string[] args)
    {
        string str = "";
        while ((str = Console.ReadLine()) != null)
        {
            int a = int.Parse(str.Split(' ')[0]);
            int b = int.Parse(str.Split(' ')[1]);
            Console.WriteLine(a + b);
        }
    }
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main()
{
    int q; cin >> q;
    set<int> S;
    rep(i,q){
        int query; cin >> query;
        if(query == 0){
            int x; cin >> x;
            S.insert(x);
            cout << S.size() << endl;
        }else if(query == 1){
            int x; cin >> x;
            cout << S.count(x) << endl;
        }else if(query == 2){
            int x; cin >> x;
            S.erase(x);
        }else if(query == 3){
            int L,R; cin >> L >> R;
            auto it = S.lower_bound(L);
			while (it != S.end() && *it <= R) {
				printf("%d\n", *it); ++it;
			}
        }
        
    }
}


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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define CEIL(n, m) ceil(n/pow(10.0, m))*pow(10.0, m)
#define FLOOR(n, m) floor(n/pow(10.0, m))*pow(10.0, m)
#define ROUND(n, m) round(n/pow(10.0, m))*pow(10.0, m)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

typedef long long ll;
const int mod = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

void solve()
{
  int ans=0;

  int n; cin >> n;
  vector<int> a(n); REP(i, n) cin >> a[i];
  map<int, int> cnt;
  for (int i=0; i<n; i++) {
    cnt[a[i]]++;
  }
  for (auto p: cnt) {
    int x = p.first;
    int n = p.second;
    if (n < x) {
      ans += n;
    } else {
      ans += n - x;
    }
  }

  cout << ans << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans=inf;
int sz[MAXN], sum[MAXN], dp[MAXN];
string S;
vector<int> G[MAXN];

void dfs(int node, int par){
	for (int v:G[node]) if (v!=par){
		dfs(v, node);
		sz[node]+=sz[v];
		sum[v]+=sz[v];
		dp[v]+=sz[v];
		sum[node]+=sum[v];
	}
	if (!sum[node]) return ;
	dp[node]=sum[node]%2;
	
	int tmp=0, val=0, mx=0, ted=0, mx2=0;
	for (int v:G[node]) if (v!=par && sum[v]>sum[mx]) mx=v;
	for (int v:G[node]) if (v!=par && v!=mx && sum[v]>=dp[mx]) mx2=v, ted++;
	if (ted>=2) return ;
	if (ted){
		tmp=(dp[mx]-dp[mx2])%2;
		val=max(dp[mx2], dp[mx])+tmp;
	}
	else val=tmp=dp[mx];
	for (int v:G[node]) if (v!=par && v!=mx && v!=mx2) tmp-=sum[v];
	dp[node]=max(dp[node], tmp);
}

int Solve(int root){
	for (int i=1; i<=n; i++) sz[i]=(S[i-1]=='1'), dp[i]=sum[i]=0;
	dfs(root, 0);
	if (dp[root]) return inf;
	return sum[root]/2;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>S;
	for (int i=1; i<n; i++){
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	for (int i=1; i<=n; i++) ans=min(ans, Solve(i));
//	debug(Solve(6));
//	debug2(dp[6], sum[6])
//	debug2(dp[7], sum[7])
//	debug2(dp[1], sum[1])
	
	
	if (ans==inf) ans=-1;
	cout<<ans<<"\n";
	
	return 0;
}


Measured memory_bytes: 6196
import sys
import random


test =False
debug = False
loop = False

def main(N, items):
    counter = 0
    i = 0
    if test:
        print N, items
    if debug:
        print items
    while i < N - 1:
        if i + 1 == items[i]:
            tmp = items[i+1]
            items[i+1] = items[i]
            items[i] = tmp
            counter += 1
            if debug:
                print items
        i += 1
    assert i == N - 1
    if items[i] == N:
        tmp = items[i]
        items[i] = items[i-1]
        items[i-1] = tmp
        counter += 1
        if debug:
            print items
    print counter

if __name__ == "__main__":
    if test:
        if loop:
            while True:
                N = random.randint(2, 10)
                items = range(1, N + 1)
                assert len(items) == N
                random.shuffle(items)
                main(N, items)
        else:
            N = 4
            items = [3,2,1,4]
            main(N, items)
    else:
        N = int(raw_input())
        items = raw_input().split()
        items = [int(item) for item in items]
        main(N, items)


Measured memory_bytes: 11588
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout]
fn main() {
    input! {
        n: usize, x: usize, t: usize,
    }
    let ans = (n + x - 1) / x * t;
    println!("{}", ans);
}


Measured memory_bytes: 2144
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#define INT_MAX 2147483647
#define LLINT_MAX 9223372036854775807
#define mod 1000000007
using namespace std;

int main() {
	int n, m;
	int a[50], b[50], c[50], d[50];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i] >> b[i];
	for (int i = 0; i < m; i++)
		cin >> c[i] >> d[i];
	for (int i = 0; i < n; i++) {
		int min = INT_MAX;
		int mem;
		for (int j = 0; j < m; j++) {
			if (min > abs(a[i] - c[j]) + abs(b[i] - d[j])) {
				min = abs(a[i] - c[j]) + abs(b[i] - d[j]);
				mem = j + 1;
			}
		}
		cout << mem << endl;
	}
	return 0;
}

Measured memory_bytes: 892
#include<iostream>
#include<set>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
using namespace std;

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

  set<string> d;
  string w, prev, ans = "Yes";
  cin >> prev;
  d.insert(prev);
  rep(i,1,N-1) {
    cin >> w;
    if (d.count(w) != 0 || prev[prev.size()-1] != w[0]) {
      ans = "No";
    }
    prev = w;
    d.insert(prev);
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

int H  = sc.nextInt();
int W  = sc.nextInt();
int cnt=0;
int s[][] = new int [H+2][W+2];
for(int i=1; i<=H; i++){
		String HW=sc.next();
		for(int j=1; j<=W;j++){
				if(HW.charAt(j-1)=='.'){
				s[i][j]=0;
			}else{
				s[i][j]=1;
			}
		}
}
for(int i=1; i<=H; i++){
		for(int j=1; j<=W;j++){
				if(s[i][j]==1 && s[i-1][j]!=1 && s[i+1][j]!=1 && s[i][j-1]!=1 && s[i][j+1]!=1){
					cnt=cnt+1;
					break;
				}
		}
}
if(cnt>0){
	System.out.println("No");
}else{
	System.out.println("Yes");
}

}
}


Measured memory_bytes: 22100
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


ll A[200010];
ll B[200010];

int main() {
  int N;
  cin >> N;
  rep(i,N) {
    ll id = i+1;
    ll val;cin >> val;
    A[i] = val - id;
    B[i] = -val - id;
  }
  sort(A,A+N);
  sort(B,B+N);
  ll ans = 0;
  rep(i,N) {
    ll key = B[i];
    ans += upper_bound(A,A+N,key) - lower_bound(A,A+N,key);
    // cout << key << " : " << upper_bound(A,A+N,key) - lower_bound(A,A+N,key) << endl;
  }
  cout << ans << endl;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N, M;
    cin >> N >> M;
    vector<P> items(M);
    rep(i, M) {
        ll a, b;
        cin >> a >> b;
        ll t = 0;
        rep(i, b) {
            int c;
            cin >> c;
            c--;
            t |= 1 << c;
        }
        items[i] = make_pair(a, t);
    }
    vector<vector<ll>> dp(M + 1, vector<ll>(1 << N, INF));
    rep(i, M + 1) {
        dp[i][0] = 0;
    }
    rep(i, M) {
        P p = items[i];
        rep(j, (1 << N)) {
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
            dp[i + 1][j | p.second] = min(dp[i + 1][j | p.second], dp[i][j] + p.first);
        }
    }
    if (dp[M][(1 << N) - 1] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dp[M][(1 << N) - 1] << '\n';
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

int main() {
  int a, b, c;
  b=0;
  cin >> a;
  if (a / 100 != 0) {
	b++;
	a-=100;
  }
  if (a / 10 != 0) {
    b++;
    a-= 10;
  }
  if (a == 1) {
    b++;
  }

  cout << b << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	const int sizes[] = {60,80,100,120,140,160};
	const int weights[] = {2,5,10,15,20,25};
	const int fee[] = {600,800,1000,1200,1400,1600};
	while(true){
		long long int ans=0;
		int n;
		scanf("%d", &n);
		if( n == 0 )
			break;
		for(int i = 0; i < n; ++i){
			int x,y,h,w;
			int size;
			scanf("%d%d%d%d", &x, &y, &h, &w);
			size = x + y + h;
			for(int k = 0; k < sizeof(sizes)/sizeof(*sizes); ++k){
				if( size <= sizes[k] && w <= weights[k] ){
					ans += fee[k];
					break;
				}
			}
		}
		printf("%lld\n", ans);
	}
}

Measured memory_bytes: 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer N = Integer.valueOf(br.readLine());
		String[] A = br.readLine().split(" ");
		ArrayList<Integer> list = new ArrayList<Integer>();
		int i, count = 0;
		for(i=0;i<N;i++) list.add(Integer.valueOf(A[i]));
		loop:
		while(true) {
			for(i=0;i<list.size();i++) {
				if(list.get(i) % 2 != 0) break loop;
				list.set(i, (list.get(i) / 2));
			}
			count++;
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 21332