akhauriyash/Code-Regression huggingface dataset:
change=list( map(int,input().split()))
change_after=list( map(int,input().split()))

def East(a,b,c,d,e,f):
    return [d, b, a, f, e, c]
def West(a,b,c,d,e,f):
    return [c, b, f, a, e, d]
def South(a,b,c,d,e,f):
    return [e, a, c, d, f, b]
def North(a,b,c,d,e,f):
    return [b, f, c, d, a, e]
def Rot(a,b,c,d,e,f):
    return [a,d,b,e,c,f]



flag=0
for idx in range(0, 5):
    change=South(*change)
    if change==change_after:
        flag=flag+1
    for idx2 in range(0,4):
        change=Rot(*change)
        if change==change_after:
           flag=1+flag
           
for idx in range(0, 5):
    change=West(*change)
    if change==change_after:
        flag=flag+1
    for idx2 in range(0,4):
        change=Rot(*change)
        if change==change_after:
           flag=1+flag
if flag==0:
    print("No")
else:
    print("Yes")


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

using namespace std;

const int max_n = 200222;
const long long inf = 1000111222000111222LL;

int n, a[max_n];
long long dp[max_n][5];

void upd(int a, int b, long long x) {
    dp[a][b] = min(dp[a][b], x);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < max_n; ++i) {
        for (int j = 0; j < 5; ++j) {
            dp[i][j] = inf;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
        upd(i + 1, 0, dp[i][0] + a[i]);
        upd(i, 1, dp[i][0]);
        upd(i + 1, 1, dp[i][1] + 2 * (a[i] == 0) + a[i] % 2);
        upd(i, 2, dp[i][1]);
        upd(i + 1, 2, dp[i][2] + 1 - a[i] % 2);
        upd(i, 3, dp[i][2]);
        upd(i + 1, 3, dp[i][3] + 2 * (a[i] == 0) + a[i] % 2);
        upd(i, 4, dp[i][3]);
        upd(i + 1, 4, dp[i][4] + a[i]);
    }
    long long ans = inf;
    for (int i = 0; i < 5; ++i) {
        ans = min(ans, dp[n][i]);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define INF 1145141919
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}
////////////////////////////////////////////////////////////////////
int main()
{
    ll N,K; cin >> N >> K;

    vector<pair<ll,ll>> pairs(N);
    REP(i,N){
        cin >> pairs[i].first >> pairs[i].second;
    }

    sort(pairs.begin(), pairs.end());

    ll res=0;

    REP(i,N){
        res+=pairs[i].second;
        if(res>=K){
            cout << pairs[i].first << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin>>k;
    int ans = 0;
    if(k % 2 == 0) ans = (k/2)*(k/2);
    else ans = (k/2)*(k/2+1);
    PUTS(ans);
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"reflect"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	sc.Split(bufio.ScanWords)
	defer out.Flush() // !!!!coution!!!! you must use Fprint(out, ) not Print()
	/* --- code --- */
	x, y, z := nextInt(), nextInt(), nextInt()
	fmt.Println(z, x, y)
}

// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func split(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}

func PrintOut(src interface{}, joinner string) {
	switch reflect.TypeOf(src).Kind() {
	case reflect.Slice:
		s := reflect.ValueOf(src)
		for idx := 0; idx < s.Len(); idx++ {
			fmt.Fprintf(out, "%v", s.Index(idx))
			if idx < s.Len()-1 {
				fmt.Fprintf(out, "%s", joinner)
			} else {
				fmt.Fprintln(out)
			}
		}
	default:
		fmt.Fprintln(out, "fuck")
	}
}

// -*-*-*-*-*-*-*-*-
// * tool snippets *
// -*-*-*-*-*-*-*-*-
func duplicate2Int(base [][]int) (ret [][]int) {
	ret = make([][]int, len(base))
	for i, v := range base {
		ret[i] = append([]int{}, v...)
	}
	return
}

// -*-*-*-*-*-*-*-*-*-*-*-*-*-
// * Algorithms Utility Zone *
// -*-*-*-*-*-*-*-*-*-*-*-*-*-

// -*-*-*-*-*-*-*-
// * 1. nibutan  *
// -*-*-*-*-*-*-*-
func lower_bound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := (l + r) / 2
		if arr[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	return l
}

func upper_bound(arr []int, target int) int {
	l, r := 0, len(arr)
	for l < r {
		mid := (l + r) / 2
		if target < arr[mid] {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
// * math flavor typical theories *
// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
func gcd(a, b int) int {
	if a > b {
		return gcd(b, a)
	}
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func pow(a, b int) (ret int) {
	ret = a
	// 10^2 = 100ってことは10に10を1回掛けることだね
	// なので初期値を含めると上限b-1未満
	for i := 0; i < b-1; i++ {
		ret *= a
	}
	return
}

func powMod(n, m, mod int) (ret int) {
	ret = 1
	for m > 0 {
		if m&1 == 1 {
			ret *= n
			ret %= mod
		}
		n *= n
		n %= mod
		m >>= 1
	}
	return ret
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N = 0;
    cin >> N;
    int C = 0;
    cin >> C;
    int D[C][C];
    int ans = 250000000;
    int i = 0,j=0,k=0;
    int X[C][3];
    for(i = 0;i<C;i++){
        X[i][0]=0;
        X[i][1]=0;
        X[i][2]=0;
        for(j=0;j<C;j++){
            cin >> D[i][j];
        }
    }
    int c[N][N];
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            cin >> c[i][j];
            for(k=0;k<C;k++){
                X[k][(i+j+2)%3] += D[c[i][j]-1][k];
            }
        }
    }
    int tmp = 0;
    for(i=0;i<C;i++){
        for(j=0;j<C;j++){
            for(k=0;k<C;k++){
                if(i!=j&&j!=k&&k!=i) {
                    tmp = X[i][0] + X[j][1] + X[k][2];
                    if (tmp < ans) {
                        ans = tmp;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1280
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#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 <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  if(a >= k){
    cout << k << endl;
  }else{
    k -= a;
    if(b >= k){
      cout << a << endl;
      return 0;
    }
    k -= b;
    cout << a - k << endl;
  }
}

Measured memory_bytes: 3632
#include <cstdio>
#include <string>
#include <vector>
#include <iostream>

const int N = 4e5 + 10, M = 1e5 + 10;

struct Node {
  Node* ch[26];
  int size;
  bool mark;
} pool[N], *root, *ptr;

int cnt[M][26][26];

void ins(int n, const char *s) {
  Node* p = root;
  for (int i = 0; i < n; ++i) {
    int o = s[i] - 'a';
    p->size++;
    if (!p->ch[o]) p->ch[o] = ptr++;
    p = p->ch[o];
  }
  p->size++;
  p->mark = 1;
}

void query(int label, int n, const char *s) {
  Node* p = root;
  for (int i = 0; i < n; ++i) {
    int o = s[i] - 'a';
    for (int c = 0; c < 26; ++c) if (c != o) {
      if (p->ch[c]) cnt[label][o][c] += p->ch[c]->size;
    }
    p = p->ch[o];
    if (p->mark) cnt[label][o][o] += 1;
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n, q;
  std::cin >> n;
  ptr = pool;
  root = ptr++;
  std::vector<std::string> s(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> s[i];
    ins(s[i].size(), s[i].data());
  }
  for (int i = 0; i < n; ++i) {
    query(i, s[i].size(), s[i].data());
  }
  std::cin >> q;
  for (int i = 0; i < q; ++i) {
    int k;
    std::string u;
    std::cin >> k >> u;
    int ret = 0;
    for (int j = 0; j < 26; ++j) {
      ret += cnt[k - 1][j][j];
      for (int t = 0; t < j; ++t) {
        ret += cnt[k - 1][u[j] - 'a'][u[t] - 'a'];
      }
    }
    printf("%d\n", ret);
  }
  return 0;
}


Measured memory_bytes: 297088
#include <iostream>
#include <vector>
#define MAX 12
using namespace std;

void colored_red(int row_col[MAX], int K, int black, int index, int limit,
		 int& cnt, bool color_map[MAX][MAX], vector<int> colored)
{
  if (index == limit){
    if (black == K)
      cnt++;
    return;
  }
  int temp = 0;
  for (int i = 0; i < colored.size(); i++)
    if (color_map[index][colored[i]])
      temp++;
  colored.push_back(index);
  colored_red(row_col, K, black - row_col[index] + temp, index + 1, limit, cnt
	      , color_map, colored);
  colored.erase(colored.end() - 1);
  colored_red(row_col, K, black, index + 1, limit, cnt, color_map, colored);
}

int main(void)
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W, K, row_col[MAX] = {0}, black = 0, cnt = 0;
  char c;
  bool color_map[MAX][MAX] = {{false}};
  cin >> H >> W >> K;
  for (int i = 0; i < H; i++)
    for (int j = 0; j < W; j++){
      cin >> c;
      if (c == '#'){
	row_col[i]++;
	row_col[H + j]++;
	color_map[i][H + j] = true;
	color_map[H + j][i] = true;
	black++;
      }
    }
  vector<int> colored;
  colored_red(row_col, K, black, 0, H + W, cnt, color_map, colored);
  cout << cnt << '\n';
  return 0;
}


Measured memory_bytes: 3580
// cities to vapori-
// corner cases // int vs ll // cin vs scanf // clear structures // statement // doublesz // math is your friend
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define sz(x) int(x.size())
#define fill(x,v) memset(x,v,sizeof(x))
#define REP(i,a,b) for(int i = int(a); i < int(b); ++i)
#define trace(x) cout << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int main(){

	fastio;
	ll x;
	cin >> x;

	cout << ((x/500*1000) + (x%500)/5*5) << endl;

	return 0;
}


Measured memory_bytes: 256
s = gets.to_s.chomp.bytes

m = 10 ** 9 + 7
a = ab = abc = 0
string_count = 1

s.each_with_index do |c, i|
  
  c -= 64 # p 'A'.ord #=> 65
  if c == 1
    a += string_count
  elsif c == 2
    ab += a
  elsif c == 3
    abc += ab
  else
    abc = abc * 3 + ab
    ab = ab * 3 + a
    a = a * 3 + string_count
    string_count *= 3
  end
  
  a %= m
  ab %= m
  abc %= m
  string_count %= m
end

puts abc

Measured memory_bytes: 2812
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<stdio.h>
#include<vector>
using namespace std;

int main(){
 
    
    int n;
    cin>>n;
    int v[n+1];
    int l[n+1];
    v[0]=0;
    l[0]=0;
    for(int i=1;i<n+1;i++){
        cin>>v[i];
        l[i]=v[i];
    }
    sort(v,v+n+1);
    //for(int i=0;i<n;i++){cout<<v[i];}
    int mid=v[n/2];
    //cout<<v[mid];
    for(int i=1;i<n+1;i++){
        int ans=0;
        if(mid<l[i]){
            ans=v[n/2];
        }else{
            ans=v[n/2+1];
        }
        cout<<ans<<endl;
    }
return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <array>

using namespace std;

#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define For(i, s, n) for(int i = s; i < (int)(n); ++i)

bool solve(array<int, 3> cards, int rest) {
  if (cards[0] < cards[1] && cards[1] < cards[2]) return true;
  if (rest == 0) return false;
  Rep(i, 3) {
    auto new_cards = cards;
    new_cards[i] *= 2;
    if (solve(new_cards, rest - 1)) return true;
  }
  return false;
}

int main() {
  array<int, 3> cards;
  int K;
  Rep(i, 3) cin >> cards[i];
  cin >> K;

  cout << (solve(cards, K) ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;
//string s;
#define rep2(x,from,to) for(long long x=from;x<to;x++)
#define rep(x,to) rep2(x,0,to)
int n;
int b[3];
string s;
int k;
int q;
int a[100006];
int wa[100006];
int main()
{
    cin>>n>>k>>q;
    rep(i,q)
    {
        cin>>a[i];
        wa[a[i]]++;
    }
    rep2(i,1,n+1)
    {
        if(k-(q-wa[i])<=0)
        {
            cout<<"No"<<endl;
        }
        else cout<<"Yes"<<endl;
    }
    return 0;
}

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

int main() {
    int x;
    cin >> x;
    queue<ll> q;
    for(int i = 1; i < 10; i++) {
        q.push(i);
    }
    if(x<10){
        cout << x << endl;
        return 0;
    }
    x -= 9;
    ll ans=0;
    while(1) {
        ll s=q.front();
        q.pop();
        int y=s%10;
        if(y==9) {
            x-=2;
            q.push(s*10+8);
            q.push(s*10+9);
            if(x==0){
                ans=s*10+9;
                break;
            }
            if(x==-1){
                ans=s*10+8;
                break;
            }
        }
        else if(y==0){
            x-=2;
            q.push(s*10);
            q.push(s*10+1);
            if(x==0){
                ans=s*10+1;
                break;
            }
            if(x==-1){
                ans=s*10;
                break;
            }
        }
        else {
            x-=3;
            q.push(s*10+y-1);
            q.push(s*10+y);
            q.push(s*10+y+1);
            if(x==0){
                ans=s*10+y+1;
                break;
            }
            if(x==-1){
                ans=s*10+y;
                break;
            }
            if(x==-2){
                ans=s*10+y-1;
                break;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4156
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

struct Info{
	char ch;
	int id;
};

int main(){

	int n,id;
	Info table[26];
	char buf[1100];

	scanf("%d",&n);

	for(int i=0; i < n; i++){
		for(int k=0; k < 26; k++){
			table[k].ch = 97 + k;
			table[k].id = 100;
		}

		id = 27;
		scanf("%s",buf);

		for(int k=0; buf[k] != '\0';k++){
			if(buf[k] >= 97 && buf[k] <= 122){
				if(table[buf[k]-97].id == 100){
					table[buf[k]-97].id = id;
				}
			}else{
				if(buf[k] == '>'){
					id++;
				}else if(buf[k] == '<'){
					id--;
				}
			}
		}

		for(int k=1; k <= 25; k++){
			for(int p=25; p >= k; p--){
				if(table[p].id < table[p-1].id)swap(table[p],table[p-1]);
			}
		}

		for(int i=0; i < 26; i++){
			if(table[i].id != 100)printf("%c",table[i].ch);
		}
		printf("\n");

	}

    return 0;
}

Measured memory_bytes: 2516
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;

signed main() {
	int H, W;
	cin >> H >> W;
	vector<string>a(H);
	rep(i, H)cin >> a[i];
	rep(i, W + 2)cout << '#';
	cout << endl;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (j == 0)cout << '#';
			cout << a[i][j];
			if (j == W - 1)cout << '#';
		}
		cout << endl;
	}
	rep(i, W + 2)cout << '#';
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
//const int MOD =  (int)1e9 + 7;
const int MOD =  998244353;
const double EPS = 1e-9;

int N;
int A[200010];
vector<int> G[200010];
int ANS[200010];
int DP[200010];
int lis;

void dfs(int idx,int par)
{
	ANS[idx]=lis;
	for(auto e:G[idx])
	{
		if(e==par)continue;
		int x=lower_bound(DP,DP+200010,A[e])-DP;
		int pre=DP[x];
		if(pre==INF)lis++;
		DP[x]=A[e];
		dfs(e,idx);
		DP[x]=pre;
		if(pre==INF)lis--;
	}
}
 
signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

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

	int x,y;
	rep(i,0,N-1)
	{
		cin>>x>>y;
		x--,y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	rep(i,0,200010)DP[i]=INF;

	DP[0]=A[0];
	lis=1;

	dfs(0,-1);

	rep(i,0,N)
	{
		cout<<ANS[i]<<endl;
	}
	
	return 0;
}

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

int main()
{
	int n;
	string s;
	cin>>n>>s;
	int ans = 1;
	if(n % 2 == 1)
	{
		ans = 0;
	}
	else
	{
		for(size_t i = 0; i<n/2; i++)
		{
			if(s[i]!=s[i+n/2])
			{
				ans = 0;
			}
		}
	}
	if(ans==0)
	{
		cout<<"No"<<endl;
	}
	else
	{
		cout<<"Yes"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b;
cin>>a>>b;
if(a==b){
for(int i=0; i<a;i++){
cout<<a;}}
else if(a>b){
for(int i=0; i<a;i++){
cout<<b;}}
else{
for(int i=0; i<b;i++){
cout<<a;}}}



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

S=sum(a)

table=[0]*(10**6)

for i in range(n):
    table[a[i]]+=1

for i in range(q):
    b, c=map(int, input().split())
    if table[b]!=0:
        cnt=table[b]
        table[c]+=cnt
        ans=S+(cnt*(c-b))

        print(ans)

        table[b]=0
        S=ans
    else:
        print(S)

Measured memory_bytes: 90576
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int A,B,K;
    cin >> K >> A >> B;
    if((B/K-A/K)!=0){
        cout << "OK" << endl;
    }else if((A%K==0) || (B%K==0)){
        cout << "OK" << endl;
    }else{
        cout << "NG" << endl;
    }
    
}


Measured memory_bytes: 3640
N=int(input())
h=list(map(int,input().split()))
cnt=0
anscnt=0
for i in range(N-1):
    if h[i]>=h[i+1]:
        cnt+=1
    else:
        cnt=0
    anscnt=max(anscnt,cnt)
print(anscnt)
        
        
    
    

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

char moji[] = "01+-*()=";
string s;
char cset[100];
int idx[100];
int length;
vector<int> perm;
int pos;
bool correct;
string currents;
char get(int i){
	if(i >= length){
		return '\0';
	}
	return currents[i];
}

bool Q();
int E();
int T();
int F();
int N();
int B(int cur);


bool Q(){
	int a = E();
	if(get(pos) != '='){
		correct  = false;
		return false;
	}
	pos++;
	int b = E();
	return a == b;
}

int E(){
	int t = T();
	while(get(pos) == '+' || get(pos) == '-'){
		if(get(pos) == '+'){
			pos++;
			t += T();
		}else{
			pos++;
			t -= T();
		}
	}
	return t;
}

int T(){
	int f = F();
	while(get(pos) == '*'){
		pos++;
		f *= F();
	}
	return f;
}

int F(){
	if(get(pos) == '-'){
		pos++;
		return - F();
	}
	if(get(pos) == '('){
		pos++;
		int e = E();
		if(get(pos) != ')'){
			correct = false;
		}
		pos++;
		return e;
	}

	return N();
}

int N(){
	if(get(pos) == '0'){
		pos++;
		return 0;
	}
	if(get(pos) == '1'){
		pos++;
		return B(1);
	}
	correct = false;
	return 0;
}

int B(int cur){
	if(get(pos) == '0'){
		pos++;
		return B(cur * 2);
	}
	if(get(pos) == '1'){
		pos++;
		return B(cur * 2 + 1);
	}
	return cur;
}


int main(){
	cin >> s;
	length = s.size();
	int si = 0;
	for(int i = 0; i < s.size(); i++){
		if(!(('a' <= s[i] && s[i] <= 'z') || ('A' <= s[i] && s[i] <= 'Z'))){
			idx[i] = s[i];
			continue;
		}
		int j;
		for(j = 0; j < si; j++){
			if(cset[j] == s[i]) break;
		}
		if(j == si){
			si++;
			if(si > 8){
				cout << 0 << endl;
				return 0;
			}
			cset[j] = s[i];
		}
		idx[i] = j;
	}
	
	for(int i = 0 ; i < 8; i++){
		perm.push_back(i);	
	}

	set<string> smap;

	do{
		string ns = s;
		for(int i = 0; i < ns.size(); i++){
			if(('a' <= s[i] && s[i] <= 'z') || ('A' <= s[i] && s[i] <= 'Z')){
				ns[i] = moji[perm[idx[i]]];
			}
		}
		smap.insert(ns);
	}while(next_permutation(perm.begin(), perm.end()));

	int ans = 0;
	for(string ss : smap){
		currents = ss;
		pos = 0;
		correct = true;
		if(Q() && correct && pos == ss.size()){
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 7584
from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


while True:
    n, p1, p2 = (int(s) for s in input().split())
    if (n, p1, p2) == (0, 0, 0):
        break

    p = p1 + p2
    tree = UnionFind(p * 2)
    unions = defaultdict(list)

    for i in range(n):
        xs, ys, a = input().split()
        x, y = int(xs) - 1, int(ys) - 1
        if a == 'yes':
            tree.unite(x, y)
            tree.unite(x + p, y + p)
        else:
            tree.unite(x, y + p)
            tree.unite(x + p, y)

    for i in range(p):
        unions[tree.find(i)].append(i)
    roots = []
    sides = []
    diffs = []
    rest = p1
    for i in range(p):
        if i in unions:
            member_len, backside_len = len(unions[i]), len(unions[i + p])
            if member_len == backside_len:
                rest = -1
                break
            elif member_len < backside_len:
                diff = backside_len - member_len
                rest -= member_len
                sides.append(0)
            else:
                diff = member_len - backside_len
                sides.append(1)
                rest -= backside_len
            roots.append(i)
            diffs.append(diff)
    if rest < 0:
        print('no')
        continue

    dp = [[1] + [0] * rest for i in range(len(roots) + 1)]

    for i in reversed(range(len(roots))):
        for j in range(1, rest + 1):
            if j < diffs[i]:
                if dp[i + 1][j]:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                if dp[i + 1][j] and dp[i + 1][j - diffs[i]]:
                    dp[i][j] = 3
                elif dp[i + 1][j - diffs[i]]:
                    dp[i][j] = 2
                elif dp[i + 1][j]:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0

    divines = []
    for i in range(len(roots)):
        if dp[i][rest] == 1:
            divines.extend(unions[roots[i] + p * sides[i]])
        elif dp[i][rest] == 2:
            divines.extend(unions[roots[i] + p * (1 - sides[i])])
            rest -= diffs[i]
        else:
            print('no')
            break
    else:
        divines.sort()
        for divine in divines:
            print(divine + 1)
        print('end')

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

using namespace std;
using ll = long long;

int main() {
    string S;
    vector<bool> abc(26,0);
    cin >> S;
    for(int i = 0; i < S.size(); i++) {
        if(abc.at(S.at(i) - 'a')) {
            cout << "no" << endl;
            return 0;
        } else {
            abc.at(S.at(i) - 'a') = 1;
        }
    }
    cout << "yes" << endl;

    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

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

void maxHeapify(vector<int>& as, int h, int H) {
    int l = 2 * h + 1;
    if (l >= H) l = h;
    int r = 2 * h + 2;
    if (r >= H) r = h;
    int i = h;
    if (as[l] > as[i]) {
        i = l;
    }
    if (as[r] > as[i]) {
        i = r;
    }

    if (i != h) {
        swap(as[i], as[h]);
        maxHeapify(as, i, H);
    }
}

void buildMaxHeap(vector<int>& as, int H) {
    for (int i = H / 2; i >= 0; --i) {
        maxHeapify(as, i, H);
    }
}

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

    int H;
    cin>>H;
    vector<int> as(H);
    rep(i, H) cin>>as[i];

    buildMaxHeap(as, H);
    rep(i, H) cout<<" "<<as[i];
    cout<<endl;
}


Measured memory_bytes: 4516
import java.util.Scanner;

public class Main {
    public long getDestination(long x, long k, long d) {
        long prevValue = 0;
        long prevPrevValue = 0;
        while (k > 0) {
            if (x == 0) {
                if (k % 2 == 0) {
                    return 0;
                } else {
                    return d;
                }
            } else {
                long jumpK = Math.abs(x) / d;
                jumpK = Math.max(jumpK, 1);
                jumpK = Math.min(jumpK, k);

                k -= jumpK;
                if (x > 0) {
                    x -= jumpK * d;
                } else {
                    x += jumpK * d;
                }

                if (prevPrevValue == x) {
                    if (k % 2 == 0) return Math.abs(x);
                    if (x > 0) return Math.abs(x - d);
                    if (x < 0) return Math.abs(x + d);
                }
                prevPrevValue = prevValue;
                prevValue = x;
            }
        }

        return Math.abs(x);
    }

    public static void main(String[] args) throws Exception {
        Main solution = new Main();

        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong();
        long k = scanner.nextLong();
        long d = scanner.nextLong();

        long answer = solution.getDestination(x, k, d);
        System.out.println(answer);
    }
}

Measured memory_bytes: 35748
def dice(d, i, n):
    if n == 1:
        return d[i][1] + d[i][2] + d[i][4] + d[i][3]
    if n == 2:
        return d[i][0] + d[i][3] + d[i][5] + d[i][2]
    if n == 3:
        return d[i][0] + d[i][1] + d[i][5] + d[i][4]
    if n == 4:
        return d[i][0] + d[i][4] + d[i][5] + d[i][1]
    if n == 5:
        return d[i][0] + d[i][2] + d[i][5] + d[i][3]
    if n == 6:
        return d[i][1] + d[i][3] + d[i][4] + d[i][2]

answer = 'Yes'
n = int(input())
d = [0]*n
for i in range(n):
    d[i] = input().split()
    
for j in range(n-1):
    for k in range(j+1, n):
        for l in range(6):
            if d[j][0]==d[k][l] and d[j][5]==d[k][5-l] and dice(d,k,l+1)in dice(d,j,1)*2:
                answer = 'No'
                
print(answer)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, FN) for(int i = 0; i < ( FN ); i++)
#define STATE 0
#define DIST 1
#define NOTYET 2
#define DONE 3

int h, w;
char grid[51][51];
int mymap[51][51][2];

int daik(int x = 1, int y = 1){
    int xloop[4] = {-1, 0, 0, 1};
    int yloop[4] = {0, 1, -1, 0};
    for(int i = 0; i < 4; i++) {
        int nx = x + xloop[i];
        int ny = y + yloop[i];
        if(nx >= 1 && nx <= h && ny >= 1 && ny <= w && grid[nx][ny] == '.') {
            if(mymap[nx][ny][DIST] > mymap[x][y][DIST] + 1) {
                mymap[nx][ny][DIST] = mymap[x][y][DIST] + 1;
            }
        }

    }

    int mindist = INT_MAX;
    int minx = -1, miny = -1;
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            if(mymap[i][j][STATE] == NOTYET && mymap[i][j][DIST] < mindist) {
                mindist = mymap[i][j][DIST];
                minx = i;
                miny = j;
            }
        }
    }
    if(minx == h && miny == w) return mymap[h][w][DIST];
    else if(minx != -1 || miny != -1) {
        mymap[minx][miny][STATE] = DONE;
        daik(minx, miny);
    }else {
        return -1;
    }
}

int main() {
    int white = 0, black = 0;
    cin >> h >> w;
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            char temp;
            cin >> temp;
            grid[i][j] = temp;
            if(temp == '.') white++;
            else black++;
        }
    }

    for(int i = 0; i <= 50; i++) {
        for(int j = 0; j <= 50; j++) {
            mymap[i][j][DIST] = INT_MAX;
            mymap[i][j][STATE] = NOTYET;
        }
    }

    mymap[1][1][DIST] = 0;
    mymap[1][1][STATE] = DONE;
    int distant = daik();
    if(distant == -1) cout << -1 << endl;
    else cout << white - (distant + 1) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

int main(){
  long long n;
  scanf("%lld",&n);
  long long a[n],b[n];
  for(int i=0;i<n;i++){
    scanf("%lld%lld",&a[i],&b[i]);
  }
  
  long long ans=0;

  for(long long i=n-1;i>=0;i--){
    
    while((a[i]+ans)%b[i]!=0){
      ans=ans+(b[i]-(a[i]+ans)%b[i]);
    }
  }

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

  return 0;
}
  
 


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
const int nax = 1005;
char s[nax][nax];
const int mod = 1e9+7;

void add_self(int &a, int b)
{
    a+=b;
    if(a >= mod)
    a-=mod;
}
int main()
{
    int h,w;
    cin >> h >> w;
    for(int row = 0; row < h; ++row)
    {
        cin >> s[row];
    }

    vector<vector<int>> dp(h,vector<int>(w));
    dp[0][0] = 1;
    for(int row = 0; row < h; ++row)
    {
        for(int col =0; col < w ; ++col)
        {
            for(int r2:{row,row+1})
            {
                int c2 = col;
                if(r2 == row)
                {
                    c2 = col + 1;
                }
                if(r2 < h && c2 < w && s[r2][c2] == '.')
                {
                    add_self(dp[r2][c2],dp[row][col]);
                }
            }
        }
    }

    cout << dp[h-1][w-1];
}

Measured memory_bytes: 5120
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

string a, b;

int main(){
	cin>>a>>b;
	
	int s1 = a.size(), s2 = b.size();
	
	if(s1 == s2){
		bool ans = false;
		
		for(register int i=0; i<s1; i++){
			bool flag = true;
			for(register int j=0; j<s1; j++){
				if(a[(i+j) % s1] != b[j]){
					flag = false;
					break;
				}
			}
			
			if(flag){
				ans = true;
				break;
			}
		}
		
		if(ans){
			printf("Yes\n");
			return 0;
		}
	}
	
	printf("No\n");
	return 0;
}


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

#define         ull             unsigned long long
#define         ll              long long
#define         inf             INT_MAX
#define         pi              acos(-1.0)
#define         vi              vector<int>
#define         vl              vector<long long>
#define         pii             pair<int,int>
#define         pll             pair<long long,long long>
#define         mp              make_pair
#define         mii             map<int,int>
#define         mll             map<int,int>
#define         mli             multimap<int,int>
#define         mlll            multimap<long long,long long>
#define         msi             multiset<int>
#define         msl             multiset<long long>
#define         si              set<int>
#define         sl              set<long long>
#define         FOR(I,A,B)      for(int I = (A); I < (B); I++)
#define         rev(I,A,B)      for(int I = A ; I >= B ; I--)
#define         mem(a, v)       memset(a, v, sizeof (a))
#define         mod             1000000007
#define         all(a)          a.begin(),a.end()
#define         rall(a)         a.rbegin(),a.rend()
#define         ff              first
#define         ss              second
#define         arsort(ar,n)    sort(ar,ar+n);
#define         vsort(v)        sort(v.begin(),v.end())
#define         vrev(v)         reverse(v.begin(),v.end())
#define         arrev(ar,n)     reverse(ar,ar+n)
#define         pb              push_back
#define         popb            pop_back
#define         booster()       ios_base::sync_with_stdio(0); cin.tie(0);
#define         read(f)         freopen(f, "r", stdin)


#define         min3(a,b,c)     min(a,min(b,c))
#define         max3(a,b,c)     max(a,max(b,c))
#define         min4(a,b,c,d)   min(min(a,b),min(c,d))
#define         max4(a,b,c,d)   max(max(a,b),max(c,d))
#define         max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define         min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))


#define         bitCheck(a,k)     ((bool)(a&(1<<(k))))
#define         bitOff(a,k)       (a&(~(1<<(k))))
#define         bitOn(a,k)        (a|(1<<(k)))
#define         bitFlip(a,k)      (a^(1<<(k)))


int fx[] = {-1,+0,+1,+0,+1,+1,-1,-1,+0};
int fy[] = {+0,-1,+0,+1,+1,-1,+1,-1,+0};
int day[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

using namespace std;

bool comp(int x, int y) { return x > y; }

int arr1[1000000],arr2[1000000];

/*********************** let the play begin() ***********************************/

int main()
{
    booster()
    int n,m,save=-1,save2=-5,flag=0;
    cin>>n>>m;
    int a,b;
    FOR(i,0,m)
    {
        cin>>a>>b;
        if(a==1)
        {
            arr1[b]++;
        }
        else if(b==1)
        {
           arr1[a]++;
        }
        else if(a==n)
        {
            arr2[b]++;
        }
        else if(b==n)
        {
            arr2[a]++;
        }
    }
    FOR(i,1,n+1)
    {
         if(arr1[i]>0&&arr2[i]>0)
         {
             flag=1;
             break;
         }
    }
    if(flag==1)
        cout<<"POSSIBLE";
    else cout<<"IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 5120
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

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

    if (a & 1 && b & 1)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

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

constexpr int INF = numeric_limits<int>::max();

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

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

	vector<int> dist(N, -1);
	int LS = 0;
	int StoLS = 0;
	int LStoLS = 0;
	int now_c = 0;
	int now_d = 0;
	while (true)
	{
		if (dist[now_c] != -1)
		{
			LS = now_c;
			StoLS = dist[now_c];
			LStoLS = now_d - StoLS;
			break;
		}

		dist[now_c] = now_d;
		++now_d;
		now_c = A[now_c];
	}

	int64_t T;
	if (K < static_cast<int64_t>(StoLS))
	{
		T = K;
		now_c = 0;
	}
	else
	{
		T = (K - static_cast<int64_t>(StoLS)) % static_cast<int64_t>(LStoLS);
	}
	while (T != 0)
	{
		now_c = A[now_c];
		--T;
	}

	cout << now_c + 1 << endl;

	return 0;
}

Measured memory_bytes: 4844
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
 
        long a = input.nextLong();
        long b = input.nextLong();
        long c = input.nextLong();
        long k = input.nextLong();
 
        long ans = 0;
 
		if (k % 2 == 0) {
			ans = a - b;
 
		} else {
			ans = b - a;
		}
 
		System.out.println(Math.pow(10, 18) < Math.abs(ans) ? "Unfair" : ans);
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ar[220000],v[220000];
int main()
{
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&ar[i]);
        v[ar[i]]++;
    }
    ll sum=0;
    for(int i=1;i<=n;i++) sum+=v[i]*(v[i]-1)/2;
    for(int i=1;i<=n;i++) v[i]=sum-v[i]*(v[i]-1)/2+(v[i]-1)*(v[i]-2)/2;
    for(int i=0;i<n;i++) printf("%lld\n",v[ar[i]]);
}


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

using namespace std;

const int N = 1e5;

vector <int> ad[2 * N];
int n, m;
void dfs(int v, int d)
{
	if(d == 0)
	{
		for(int i = 0; i <= ad[v].size(); i++)
		{
			dfs(ad[v][i], 1);	
		}
	}
	else
	{
		for(int i = 0; i < ad[v].size(); i++)
		{
			int u = ad[v][i];
			if(u == n)
			{
				cout << "POSSIBLE";
				exit(0);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	while(m-- > 0)
	{
		int x, y;
		cin >> x >> y;
		ad[x].push_back(y);
		ad[y].push_back(x);	
	}
	dfs(1, 0);
	cout << "IMPOSSIBLE";
	return 0;
}

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

typedef long long int ll;

int main(){
  ll N,T;
  cin >> N >> T;
  ll ans = 0;
  ll dup;
  vector<ll> time(N);
  for(int i = 0;i < N;i++)cin >> time[i];
  for(int i = 0;i < N-1;i++){
     if(time[i+1] - time[i] < T){
        ans += time[i+1] - time[i];
     }else{
        ans += T;
     }
  }
  cout << ans + T << endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int maxn = 303;
const long long inf = 1ll<<60;
long long f[maxn][maxn][maxn], a[maxn];
void amin(long long &p, long long v){
	p = min(p, v);
}
int main(){
	int n, K; cin >> n >> K; n++;
	for(int i = 1; i < n; i++) cin >> a[i];
	for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) f[i][j][k] = inf;
	f[1][0][0] = 0;
	for(int i = 1; i < n; i++){
		for(int j = 0; j <= K; j++){
			for(int k = 0; k < i; k++){
				amin(f[i+1][j][i], f[i][j][k] + max(a[i] - a[k], 0ll));
				if(j < K){
					amin(f[i+1][j+1][k], f[i][j][k]);
				}
			}
		}
	}
	long long ans = inf;
	for(int j = 0; j <= K; j++) for(int k = 0; k < n; k++) ans = min(ans, f[n][j][k]);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 217344
n=int(input())
a=[int(t)-1 for t in input()]
f=1
if 1 not in a:
	a=[x//2 for x in a]
	f=2
s=sum([x for i,x in enumerate(a) if (n-1)&i==i])
print(s%2*f)


"""
メモ
初めに各要素から1を差し引いても同じ
数列に1が存在する⇒答えは2になり得ない
⇒答えの偶奇を判定できればいい⇒各要素の寄与分を考える
「nCrの偶奇 == (n&r==r)」 の関係（Lucasの定理から導かれる）が利用できる！
数列が0,2のみの場合は2を1に読み替えて同様
参考： https://mathtrain.jp/lucastheorem
"""

Measured memory_bytes: 20452
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using vpii = vector<pii>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#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++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  vi P(N);
  rep(i,N) cin >> P[i];
  
  int ans=1,m=P[0];
  rep2(i,1,N) {
    if(m>=P[i]) ans++;
    m=min(m,P[i]);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 4020
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>


typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

using namespace std;

int main()
{
	ll n;
	bool flag = false;
	ll x[110000];
	ll y[110000];
	ll t[110000];
	
	x[0] = 0;
	y[0] = 0;
	t[0] = 0;

	cin >> n;
	for (ll i = 0; i < n; i++){
		cin >> t[i+1] >> x[i+1] >> y[i+1];
	}

	for (ll i = 0; i < n; i++) {
		ll dt = t[i + 1] - t[i];
		ll dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
		if (dt < dist) {
			flag = true;
			break;
		}
		if (dt%2 != dist%2) {
			flag = true;
			break;
		}
	}

	if (flag == false) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 2688
#include <iostream> 
#include <string>
using namespace std;
int main() {
	string number;
	int count;
	cin >> number;

	count = 0;

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

		if (number.at(i) == '1') {
			count++;
		}
	}

	cout << count << endl;
}

Measured memory_bytes: 3592
type ABC(stream:System.IO.TextReader) =
  member this.Scan1 f = stream.ReadLine() |> f
  member this.Scan2 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1]))
  member this.Scan3 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2]))
  member this.Scan4 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2], a.[3]))
  member this.ScanVecH f = stream.ReadLine().Split() |> Array.map f
  member this.ScanVecV n f = [| for i in 1..n -> stream.ReadLine() |> f |]
  member this.ScanMatrix n f  = [| for i in 1..n -> stream.ReadLine().Split() |> Array.map f |]
  member this.ScanCharMatrix n = [| for i in 1..n -> stream.ReadLine().ToCharArray() |]
  member this.Close () = stream.Close()

let util = ABC(stdin)

let n,d = util.Scan2 int

let M = util.ScanMatrix n int

let isOK xs ys =
  let zs = Array.map2 (fun x -> fun y -> x - y) xs ys
  let s2 = Array.fold (fun a -> fun x -> a + x * x) 0 zs
  let t = s2 |> float |> sqrt |> int |> fun x -> x * x
  t = s2


[
  for i in 0..n-1 do
  for j in i+1..n-1 do
    yield (i,j)
]
|> List.filter (fun (i,j) -> isOK M.[i] M.[j])
|> List.length
|> printfn "%d"

util.Close()


Measured memory_bytes: 14416
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let s: Vec<u8> = read::<String>().chars().map(|c| c as u8).collect();
    let mut k: usize = read();

    let len = s.len();
    let mut ans = vec![b' '; len];

    for (i, &s_i) in s.iter().enumerate() {
        if s_i != b'a' {
            if (b'z' - s_i + 1) as usize <= k {
                ans[i] = b'a';
                k -= (b'z' - s_i + 1) as usize;
            } else {
                ans[i] = s_i;
            }
        } else {
            ans[i] = b'a';
        }
    }

    ans[len - 1] += (k % 26) as u8;
    if ans[len - 1] > 122 {
        ans[len - 1] -= 26;
    }

    println!("{}", std::str::from_utf8(&ans).unwrap());
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<vector>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main(void) {
	while(true) {
		ll n, w, d;
		cin>>n>>w>>d;
		if(n == 0 && w == 0 && d == 0) break;
		vector<P> c;
		c.pb(P(w, d));
		REP(i, n) {
			ll p, s;
			cin>>p>>s;
			--p;
			P np = c[p];
			ll cnt = 0;
			while(true) {
				if(cnt % 2 == 0) s -= np.first;
				else s -= np.second;
				if(s <= 0) {
					if(cnt % 2 == 0) {
						P sone = P(s + np.first, np.second);
						P lone = P(-s, np.second);
						if(sone.first * sone.second > lone.first * lone.second) swap(sone, lone);
						c.pb(sone);
						c.pb(lone);
					} else {
						P sone = P(np.first, s + np.second);
						P lone = P(np.first, -s);
						if(sone.first * sone.second > lone.first * lone.second) swap(sone, lone);
						c.pb(sone);
						c.pb(lone);
					}
					break;
				}
				++cnt;
			}
			c.erase(c.begin() + p);
		}
		vector<ll> m(c.size());
		REP(i, c.size()) {
			m[i] = c[i].first * c[i].second;
		}
		sort(ALL(m));
		REP(i, m.size()) {
			cout<<m[i];
			if(i != m.size() - 1) cout<<" ";
			else cout<<endl;
		}
	}
}

Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
#define fine cout<<"fine"<<endl;
#define ll long long int
#define pb push_back
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
const ll inf=(ll)2e18;
const int mod=1e9+7;
bool overflow(ll a,ll b){
    if (a <= (inf+b-1)/b) return false;
    return true;
}
vector<vector<int> > vi(100005);
int distx[100005],disty[100005];
void dfs(int i,int parent,int dist,int arr[]){
    for(int j=0;j<vi[i].size();j++){
        if(vi[i][j]!=parent){
            dfs(vi[i][j],i,dist+1,arr);
        }
    }
    arr[i]=dist;
}
int main(){
FASTIO;
int n,u,v,x,y;
cin>>n>>u>>v;
for(int i=0;i<n-1;i++){
    cin>>x>>y;
    vi[x].pb(y);
    vi[y].pb(x);
}
dfs(u,-1,0,distx);
dfs(v,-1,0,disty);
int ans=0;
for(int i=1;i<=n;i++){
    if(distx[i]<=disty[i])
        ans=max(ans,disty[i]);
}
cout<<ans-1<<endl;
}


Measured memory_bytes: 12928