akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
using namespace std;

bool comp_array(int *prev,int *fig,int size){
  for(int i=0;i<size;i++){
    if(prev[i] != fig[i]) return true;
  }
  return false;
}

int main(){
  int n;
  int prev[13],fig[13],tmp[13];
  while(cin >> n,n){
    int cont = 0;
    for(int i=0;i<n;i++) cin >> fig[i];
    while(comp_array(prev,fig,n)){
      cont++;
      copy(fig,fig+n,prev);
      for(int i=0;i<n;i++){
	int cnt = 0;
	for(int j=0;j<n;j++){
	  if(fig[i] == fig[j]) cnt++;
	}
	tmp[i] = cnt;
      }
      copy(tmp,tmp+n,fig);
    }
    cout << --cont << endl;
    for(int i=0;i<n;i++){
      cout << fig[i] << ((i == n-1)? "\n" : " ");
    }
  }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair <int,int> ii;
 
const int N = 1e6 + 5;
const int inf = 2e9;
const int SQ = 300;

ll n,a,b,c;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; cout.tie(NULL);
	cin >> a >> b >> c >> n;
	if (n % 2)
		cout << b - a << endl;
	else
		cout << a - b << endl;
}

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

int main(void) {
	uint64_t X;
	uint64_t ng, ok;
	if (scanf("%" SCNu64, &X) != 1) return 1;
	ng = 0;
	ok = X;
	while (ng + 1 < ok) {
		uint64_t mid = ng + (ok - ng) / 2;
		if (mid * (mid + 1) / 2 >= X) ok = mid; else ng = mid;
	}
	printf("%" PRIu64 "\n", ok);
	return 0;
}

/*
フルスピードで右に向かう
通り過ぎたなら、そこまでのなかでどれか1個のジャンプをスキップすればおｋ
*/


Measured memory_bytes: 128
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    ll res = pow(N / K, 3);
    if (K % 2 == 0 && K <= 2 * N) {
        res += pow((2 * N - K) / (2 * K) + 1, 3);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
ll MOD = 1000000007;

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

  while(1) {
    int n;
    cin >> n;
    if(n == 0) break;
    vector<string> s(n);
    REP(i, n) cin >> s[i];

    auto func = [](vector<char> v) {
      int cnt = 0, ret = 0;
      REP(i, v.size()) {
        if(v[i] == '1') {
          cnt++;
        } else {
          cnt = 0;
        }
        chmax(ret, cnt);
      }
      return ret;
    };

    int ret = 0;
    REP(i, n) {
      vector<char> v;
      REP(j, n) v.push_back(s[i][j]);
      chmax(ret, func(v));
    }
    REP(i, n) {
      vector<char> v;
      REP(j, n) v.push_back(s[j][i]);
      chmax(ret, func(v));
    }
    REP(i, n) {
      vector<char> v;
      int y = 0, x = i;
      while(IN(0,n,x) && IN(0,n,y)) {
        v.push_back(s[y][x]);
        y++, x--;
      }
      chmax(ret, func(v));
    }
    REP(i, n) {
      vector<char> v;
      int y = i, x = n-1;
      while(IN(0,n,x) && IN(0,n,y)) {
        v.push_back(s[y][x]);
        y++, x--;
      }
      chmax(ret, func(v));
    }
    REP(i, n) {
      vector<char> v;
      int y = 0, x = i;
      while(IN(0,n,x) && IN(0,n,y)) {
        v.push_back(s[y][x]);
        y++, x++;
      }
      chmax(ret, func(v));
    }
    REP(i, n) {
      vector<char> v;
      int y = i, x = 0;
      while(IN(0,n,x) && IN(0,n,y)) {
        v.push_back(s[y][x]);
        y++, x++;
      }
      chmax(ret, func(v));
    }
    cout << ret << endl;
  }

  return 0;
}



Measured memory_bytes: 3192
#include<iostream>
using namespace std;
int main(void){
  char s[3];
  for(int i(0);i<3;i++){
    cin>>s[i];
    if(s[i]=='1')s[i]='9';
    else s[i]='1';
    cout<<s[i];
  }
  return 0;
}

Measured memory_bytes: 256
// -*- coding:utf-8-unix -*-

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        x: usize,
    }
    let mut count = 1;
    let mut direction = x;
    while direction % 360 != 0 {
        count += 1;
        direction += x;
    }
    println!("{}", count);
}


Measured memory_bytes: 2196
#pragma comment (linker, "/STACK:526000000")
#define  _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()
unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(100);
}
#define int ll
int dp[200000];
void solve() {
    int h, n;
    cin >> h >> n;
    REP(i, 200000) {
        dp[i] = 1e18;
    }
    dp[0] = 0;
    REP(i, n) {
        int a, b;
        cin >> a >> b;
        REP(q, h) {
            dp[a + q] = min(dp[a + q], dp[q] + b);
        }
    }
    int ans = dp[h];
    for (int i = h; i < 200000; ++i) {
        ans = min(ans, dp[i]);
    }
    cout << ans << endl;
    return;
}
#undef int
int main() {
    init();
    solve();
}

Measured memory_bytes: 1792
// import chie template :) {{{
import std.stdio,
       std.algorithm,
       std.array,
       std.string,
       std.math,
       std.conv,
       std.range,
       std.container,
       std.bigint;
// }}}

void main() {
  int n = readln.chomp.to!int;
  int[] c, s, f;
  foreach (i; 0 .. n - 1) {
    int[] t = readln.chomp.split.to!(int[]);
    c ~= t[0];
    s ~= t[1];
    f ~= t[2];
  }
  foreach (i; 0 .. n - 1) {
    int res = c[i] + s[i];
    foreach (j; (i + 1) .. n - 1) {
      res = max(res, s[j]) + (max(res, s[j]) % f[j] == 0 ? 0 : (f[j] - max(res, s[j]) % f[j])) + c[j];
    }
    writeln(res);
  }
  writeln(0);
}


Measured memory_bytes: 380
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

int b, c=0, n, k;
string s,t;
//cout<<<<endl;


int main()
{
	cin >> n;
	vector<int> a(n);
	rep(i, n)
		cin >> a[i];
	int x = 1;
	for (int i = 0; i < n; i++)
	{
		if (x == a[i])
			x++;
	}
	if (x != 1)
		cout << n - (x - 1) << endl;
	else
		cout << -1 << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll= long long ;
using P = pair<ll,ll>;
#define rep(i,n) for (ll i = 0; i<(ll)(n); i++)
#define mod 1000000007
#define pi 3.141592653589793
typedef vector<ll> vcl;

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t =rep_jijo(n,x/2);
        return t*t%mod;
  }
  return n*rep_jijo(n,x-1)%mod;
}
ll c2(ll n){
    return n*(n-1)/2;
}

int main(){
ll n,q;
cin>>n;
ll ans=0;
map<ll,ll> m;
rep(i,n){
    ll k;
    cin>>k;
    m[k]++;
    ans+=k;
}
cin>>q;
rep(i,q){
    ll b,c;
    cin>>b>>c;
   if(m[b]>0) {
       ans=ans-b*m[b]+m[b]*c;
       m[c]+=m[b];
       m[b]=0;
}

cout<<ans<<endl;
}
}


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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main() {

    string s; cin >> s;
    vector<char > S(s.length());
    S[0] = s[0];
    S[1] = s[1];
    S[2] = s[2];

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

    if(S[0] == 'a' && S[1] == 'b' && S[2] == 'c'){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    print(n-k+1)
    return

#B
def B():
    r,g,b,n = LI()
    ans = 0
    for i in range(n+1):
        x = r*i
        for j in range(n+1-x):
            y = g*j
            z = n-x-y
            if z%b != 0 or z < 0:continue
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    s = SR(n)
    f = [0 for i in range(n)]
    a = deque()
    b = deque()
    ba = deque()
    c = deque()
    l = 0
    for i in range(n):
        l += len(s[i])
        if s[i][-1] == "A":
            f[i] += 1
        if s[i][0] == "B":
            f[i] += 2
        if f[i] == 0:
            c.append(s[i])
        elif f[i] == 1:
            a.append(s[i])
        elif f[i] == 2:
            b.append(s[i])
        else:
            ba.append(s[i])
    ans = [None for i in range(l)]
    i = 0
    while a or b or c or ba:
        if a:
            x = a.popleft()
            for j in x:
                ans[i] = j
                i += 1
            while ba:
                x = ba.popleft()
                for j in x:
                    ans[i] = j
                    i += 1
            if b:
                x = b.popleft()
                for j in x:
                    ans[i] = j
                    i += 1
        elif b:
            x = b.popleft()
            for j in x:
                ans[i] = j
                i += 1
        elif c:
            x = c.popleft()
            for j in x:
                ans[i] = j
                i += 1
        while ba:
            x = ba.popleft()
            for j in x:
                ans[i] = j
                i += 1
    s = 0
    for i in range(l-1):
        if ans[i] == "A" and ans[i+1] == "B":
            s += 1
    print(s)
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()


Measured memory_bytes: 50352
use io::*;
use std::cmp;

fn main() {
    let input = read_string();
    let mut sc = Scanner::new(&input);
    let n: usize = sc.next();
    let mut k: usize = sc.next();
    let xs: Vec<i64> = sc.next_vec(n);
    let mut r: Vec<i64> = vec![0];
    let mut l: Vec<i64> = Vec::new();
    for i in 0..n {
        if xs[i] == 0 {
            k -= 1;
        } else if xs[i] > 0 {
            r.push(xs[i]);
        } else {
            l.push(-xs[i]);
        }
    }
    l.push(0);
    l.reverse();
    if k == 0 {
        println!("0");
        return;
    }
    let mut ans = i64::max_value();
    for i in cmp::max(0,k as i64 - r.len() as i64 + 1) as usize .. cmp::min(l.len(),k) {
        ans = cmp::min(ans, l[i] * 2 + r[k-i]);
    }
    for i in cmp::max(0,k as i64 - l.len() as i64 + 1) as usize .. cmp::min(r.len(),k) {
        ans = cmp::min(ans, r[i] * 2 + l[k-i]);
    }
    println!("{}",ans);
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }

        pub fn next_mat<T: FromStr>(&mut self, w: usize, h: usize) -> Vec<Vec<T>> {
            (0..h).map(|_| self.next_vec(w)).collect()
        }

        pub fn next_vec_char(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }

        pub fn next_mat_char(&mut self, n: usize) -> Vec<Vec<char>> {
            (0..n).map(|_| self.next_vec_char()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


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

int main() {
  int n;
  int ind = 1;
  int ans = 0;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v.at(i);
  }
  while(ans <= n) {
    ind = v.at(ind - 1);
    ans++;
    if (ind == 2) break;
  }
  if (ans > n) {
    cout << -1 << endl;
  }
  else {
    cout << ans << endl;
  }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int n,ct[1010101],nw[1010101],sum,al;
string s;
vector<pair<int,int> >v;
bool cmp(pair<int,int>a,pair<int,int>b)
{
	return min(a.second,a.first+b.second)>min(b.second,b.first+a.second);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		int a=0;
		for(int j=0;j<s.size();j++)
		{
			if(s[j]=='(')
			{
				a++;
			}
			else
			{
				a--;
			}
			nw[i]=min(nw[i],a);
		}
		ct[i]=a;
		sum+=a;
		v.push_back(make_pair(ct[i],nw[i]));
	}
	if(sum!=0)
	{
		cout<<"No"<<endl;
		return 0;
	}
	sort(v.begin(),v.end(),cmp);
	int nn=0;
	for(int i=0;i<n;i++)
	{
		if(nn<abs(v[i].second))
		{
			cout<<"No"<<endl;
			return 0;
		}
		nn+=v[i].first;
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 19000
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
#define MAX 1000000000000000
#define all(v) v.begin(),v.end()
#define rep(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revrep(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define se second
#define ll long long int
#define vi vector<ll>
ll modexp(ll a,ll b){ ll res = 1; while(b > 0){  if(b & 1) res = (res * a)%mod;  a = (a * a)%mod;  b/=2;  }  return res; }
#define rs resize
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cout << name << " : " << arg1 << endl;
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    }
#else
#define trace(...)
#endif

const ll N = 109;
ll i,n;
bool flag = 1;
set<string> g;
string s[N];
int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n;
    rep(i,0,n){
        cin>>s[i];
        if(i != 0){
            if(s[i - 1][s[i - 1].length() - 1] != s[i][0])
                flag = 0;
        }
        if(g.find(s[i]) != g.end())
            flag = 0;
        g.insert(s[i]);
    }
    cout<<(flag ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        String s=br.readLine();
        if(s.equals("ABC"))
        pw.println("ARC");
        else
        pw.println("ABC");
        pw.flush();
        pw.close();
    }
}

Measured memory_bytes: 32428
T = '#.'

while True:
    H, W = [int(n) for n in input().split()]
    n, r = divmod(W, 2)
    if H==W==0:
        break
    for i in range(H):
        if i%2==0:
            print(T*n + T[0]*r)
        else:
            print(T[::-1]*n + T[-1]*r)
    print()



Measured memory_bytes: 5616
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#define INF 1000000000
using namespace std;
int bfs(int x,int y);
int w,h;
int i,j;
int dy[4] = {1,0,-1,0}, dx[4] = {0,-1,0,1};
string map[100];
int dis[100][100];
queue<pair<int,int> > q;
int main(){
  while(1){
    cin >> w >> h;
    if(w == 0 && h == 0) break;
    w = 2*w -1;
    h = 2*h -1;
    cin.ignore();
    for(i = 0;i < h;i++){
      getline(cin,map[i]);
    }
    for(i = 0;i<100;i++){
      for(j = 0;j<100;j++){
	dis[i][j] = INF;
      }
    }
    dis[0][0] = 0;
    bfs(0,0);
    if(100000000 >  dis[h-1][w-1] ){
    cout << dis[h-1][w-1] +1<<endl;
    }else{
      cout << 0 <<endl;
    }
  }
  return 0;
}

int bfs(int x,int y){
  int i,j,k;
  pair<int,int> g;
  pair<int,int> tmp;
  g.first = h -1;
  g.second = w-1;
  for(k = 0;k < 4;k++){
    if(y +  dy[k] >-1 && y + dy[k] < h && x + dx[k] < w && x + dx[k] > -1){
      if(map[y + dy[k]][x + dx[k]] == '0' && dis[y + 2*dy[k]][x + 2*dx[k]] == INF){
	//cout << "x = " << x<<endl;
	//cout << "y = " << y<<endl;
	tmp.first = y + 2*dy[k];
	tmp.second = x + 2*dx[k];
	q.push(tmp);
	dis[y + 2*dy[k]][x + 2*dx[k]] = dis[y][x] + 1;
	//cout << "dis[y][x] = " << dis[y + 2*dy[k]][x + 2*dx[k]]<<endl;
      }
    }
  }
  while(q.size() != 0){
    tmp = q.front();
    q.pop();
    if(tmp == g){
      //cout<<"break"<<endl;
      break;
    }
    bfs(tmp.second,tmp.first);
  }
  return 0;
}

Measured memory_bytes: 1356
n,m=raw_input().split(' ')
n=int(n)
m=int(m)

students=[]
for _ in range(n):
    x,y=raw_input().split(' ')
    students.append((int(x),int(y)))

checkpoint=[]
for _ in range(m):
    x,y=raw_input().split(' ')
    checkpoint.append((int(x),int(y)))

for s in students:
    min_d=99999999999
    min_num=0
    for i,c in enumerate(checkpoint):
        if abs(c[0]-s[0])+abs(c[1]-s[1]) < min_d:
            min_d=abs(c[0]-s[0])+abs(c[1]-s[1])
            min_num=i

    print min_num+1
    



Measured memory_bytes: 2696
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int INF = -1;

int main(){
    int n;
    long long ans = 0;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
            ans += a[i][j];
        }
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            if(k == i || a[i][k] == INF) continue;
            for(int j = 0; j < n; j++){
                if(k == j || i == j || a[k][j] == INF) continue;
                if(a[i][k] + a[k][j] < a[i][j]){
                    cout << -1 << endl;
                    return 0;
                }else if(a[i][k] + a[k][j] == a[i][j]){
                    ans -= a[i][j];
                    a[i][j] = INF;
                }
            }
        }
    }
    cout << ans / 2 << endl;
    return 0;
}


Measured memory_bytes: 640
unittest
{
	assert( [ "4 3 1", "1 2", "2 3", "3 4", "2 3" ].parse.expand.solve == "1 2 2 1" );
	assert( [ "4 2 2", "1 2", "2 3", "1 4", "2 3" ].parse.expand.solve == "1 2 2 1" );
	assert( [ "7 4 4", "1 2", "2 3", "2 5", "6 7", "3 5", "4 5", "3 4", "6 7" ].parse.expand.solve == "1 1 2 1 2 2 2" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nkl = input.front.split.to!( long[] );
	auto pqs = new long[ 2 ][ nkl[ 1 ] ];
	foreach( ref pq; pqs )
	{
		input.popFront;
		pq = input.front.split.to!( long[] );
		pq[] -= 1;
	}
	auto rss = new long[ 2 ][ nkl[ 2 ] ];
	foreach( ref rs; rss )
	{
		input.popFront;
		rs = input.front.split.to!( long[] );
		rs[] -= 1;
	}
	return tuple( nkl[ 0 ], pqs, rss );
}

auto solve( long n, long[ 2 ][] pqs, long[ 2 ][] rss )
{
	// 道路グループを判定
	auto uft_a = UnionFindTree( n );
	foreach( pq; pqs )
	{
		uft_a.unite( pq[ 0 ], pq[ 1 ] );
	}
	
	// 鉄道グループを判定
	auto uft_b = UnionFindTree( n );
	foreach( rs; rss )
	{
		uft_b.unite( rs[ 0 ], rs[ 1 ] );
	}
	
	// 道路グループの根と鉄道グループの根のペアを作成して同じペアをカウント（＝道路と鉄道の両方で接続されている都市の数）
	auto ps = new long[ 2 ][ n ];
	long[ long[ 2 ] ] cs;
	foreach( i, ref p; ps )
	{
		p = [ uft_a.root( i ), uft_b.root( i ) ];
		cs[ p ]++;
	}
	auto anss = new long[ n ];
	foreach( ref ans, p; lockstep( anss, ps ) )
	{
		ans = cs[ p ];
	}
	return anss.to!( string[] ).join( " " );
}

// UnionFind木
struct UnionFindTree
{
	private long[] ps;
	private long[] rs;
	
	public this( long n )
	{
		ps.length = n;
		ps[] = -1;
		rs.length = n;
	}
	
	public long root( long i )
	{
		if( ps[ i ] < 0 ) return i;
		else              return ps[ i ] = root( ps[ i ] );
	}
	
	public bool same( long i, long j )
	{
		return root( i ) == root( j );
	}
	
	public void unite( long i, long j )
	{
		i = root( i );
		j = root( j );
		if( i == j ) return;
		if( rs[ i ] < rs[ j ] )
		{
			ps[ j ] += ps[ i ];
			ps[ i ] = j;
		}
		else
		{
			ps[ i ] += ps[ j ];
			ps[ j ] = i;
			if( rs[ i ] == rs[ j ] ) rs[ i ]++;
		}
	}
}


Measured memory_bytes: 42876
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll MOD = 1000000007;
const ll MAXN = 10010; ll fact[MAXN], finv[MAXN];
ll mod_pow(ll n, ll k) { return k ? mod_pow(n*n%MOD, k/2) * ((k&1)?n:1) % MOD : 1; }
void init() {
    fact[0] = 1;
    for(int i=1; i<MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    finv[MAXN-1] = mod_pow(fact[MAXN-1], MOD-2);
    for(int i=MAXN-2; i>=0; i--) finv[i] = finv[i+1] * (i+1) % MOD;
}

ll nCr(ll n, ll r) {
    return (n < r or r < 0) ? 0 : fact[n] * finv[r] % MOD * finv[n-r] % MOD;
}
ll nHr(ll n, ll r) {
    return (n == 0 and r == 0) ? 1 : nCr(n+r-1, r);
}

int main() {
    init();
    int N, A, B, C; cin >> N >> A >> B >> C;
    if(B % 2) return !printf("0\n");
    
    ll ans = 0;
    for(int q=0; 3*q<=C; q++) {
        for(int s=0; 3*q+s<=C and s<=A; s++) {
            int x = C - 3*q - s;
            int p = A - s;
            int r = B / 2;
            
            ll add = 1;
            (add *= nHr(q+1, p)) %= MOD;
            (add *= nHr(p+q+1, s)) %= MOD;
            (add *= nHr(p+q+s+1, r)) %= MOD;
            (add *= nHr(r, x)) %= MOD;
            (ans += add) %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
import itertools

N,M,Q = map(int,input().split())
X = [ list(map(int,input().split())) for i in range(Q) ]

L = list(itertools.combinations_with_replacement(range(1,M+1), N))
p_list =  []

for l in L :
    point = 0
    for x in X :
        if l[x[1]-1] - l[x[0]-1] == x[2] :
            point += x[3]
            
    p_list.append(point)

# print(X)
# print(L)
# print(p_list)
print(max(p_list))

Measured memory_bytes: 25032
import bisect
N = int(input())
J = list(map(int,input().split()))
K = list(map(int,input().split()))
L = list(map(int,input().split()))
J.sort()
K.sort()
L.sort()
S = 0
for i in range(N):
  k = bisect.bisect_left(J,K[i])
  l = N - bisect.bisect_right(L,K[i])  
  S += k*l
print(S)

Measured memory_bytes: 23360
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>

const long INF = 1123456789012345678;

std::string b;

int main(){
	std::cin >> b;
	for(int i = 0; i < b.length(); i++){
		if(b[i] == 'A'){
			printf("T");
		}else if(b[i] == 'T'){
			printf("A");
		}else if(b[i] == 'C'){
			printf("G");
		}else{
			printf("C");
		}
	}
	printf("\n");
}


Measured memory_bytes: 256
// ABC 52 B

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

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;

int main()
{
  int x = 0;
  int n;
  cin >> n;
  string s;
  cin >> s;

  int ans = 0;
  rep(i, n) {
    if (s[i] == 'I') {
      x++;
    } else if (s[i] == 'D') {
      x--;
    }
    chmax(ans, x);
  }

  cout << ans << endl;

  return 0;
}


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

int main(void) {
  char str[10];
  scanf("%s", str);
  if ( !strcmp(str, "A") ) {
    printf("T\n");
  }
  else if ( !strcmp(str, "T") ) {
    printf("A\n");
  }
  else if ( !strcmp(str, "C") ) {
    printf("G\n");
  }
  else if ( !strcmp(str, "G") ) {
    printf("C\n");
  }
  return 0;
}

Measured memory_bytes: 128
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def factorial(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
  
n=inp[0]
p (2).lcm(n)

Measured memory_bytes: 1788
// AOJ DPL_5_I: Balls and Boxes 9
// n 個の区別できるボールを k 個の区別できない箱に入れる
// とき、可能な入れ方の総数を求めてください。
// ただし、
//    どのボールも、必ずいずれかの箱に入れる。
//    どの箱にも、1つ以上のボールを入れる。
// 答えは第2種スターリング数 stirling2(n, k)
// 2019.3.11 bal4u

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007
int tbl[1001][1001];

int stirling2(int n, int k)
{
	int ans;

	if (k == 0) return 0;
	if (tbl[n][k]) return tbl[n][k];
	if (k == 1 || k == n) ans = 1;
	else ans = (((long long)k * stirling2(n - 1, k)) % MOD)
		+ stirling2(n - 1, k - 1);
	return tbl[n][k] = ans % MOD;
}

int main()
{
	int n, k;

	scanf("%d%d", &n, &k);
	if (n < k) puts("0");
	else printf("%d\n", stirling2(n, k));
	return 0;
}


Measured memory_bytes: 5668
import java.util.*;
import java.io.*;
 
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static final long mod=1000000007;
    
    public  static void main(String[] args)   throws Exception, IOException{
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        // int n=sc.nextInt();
        // char c[][] = new char[h][w];
        // char c[]=sc.nextString().toCharArray();
        // int d[]=new int[n];
        // for(int i=0; i<n; i++) {d[i]=sc.nextInt();}

        int n=sc.nextInt();
        int a=sc.nextInt();
        int b=sc.nextInt();
        int pre=sc.nextInt();
        long ans=0;
        for(int i=1; i<n; i++) {
            int c=sc.nextInt();
            ans+=min(b,(long)a*(c-pre));
            pre=c;
        }
    

        out.println(ans);
        out.flush();
    }


    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }  
}

class P implements Comparable<P>{
    int id, d;
    P(int  id, int d) {
        this.id=id;
        this.d=d;
    }
    public int compareTo(P p){
        return d-p.d; //des
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


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

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

inline void Main() {
  // code
  int x;
  string s;
  cin >> s;
  x = s[s.length()-1] - '0';
  switch (x)
  {
  case 3:
    cout << "bon" << endl;
    break;
  case 0:
    cout << "pon" << endl;
    break;
  case 1:
    cout << "pon" << endl;
    break;
  case 6:
    cout << "pon" << endl;
    break;
  case 8:
    cout << "pon" << endl;
    break;
  default:
    cout << "hon" << endl;
    break;
  }
}

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


Measured memory_bytes: 3644
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
using namespace std;

using int64 = long long;

#define repeat(i, n) for (auto i = decltype(n)(); (i) < (n); (i)++)

struct UnionFindTree {
  int size; 
  std::vector<int> parent;
  std::vector<int64> x;
  std::vector<int> edges;

  UnionFindTree() = default;
  UnionFindTree(int size): size(size), parent(size, -1) {}
  UnionFindTree(vector<int64>& x):
    size(x.size()), parent(x.size(), -1), x(x), edges(x.size(), 0) {}
  
  int Size() const { return size; }
  int Size(int e) { return -parent[Root(e)]; }

  bool Same(int e1, int e2) { return Root(e1) == Root(e2); }

  void Unite(int e1, int e2) {
    if ((e1 = Root(e1)) != (e2 = Root(e2))) {
      if (Size(e1) < Size(e2)) {
        std::swap(e1, e2);
      }
      // e1の属する集合にe2の属する集合を併合
      parent[e1] += parent[e2];
      x[e1] += x[e2];
      parent[e2] = e1;
      size--;
      edges[e1] += edges[e2];
    }
    edges[e1]++;
  }

  int Edges(int e) {
    e = Root(e);
    return edges[e];
  }

  void Kill(int e) {
    e = Root(e);
    edges[e] = 0;
  }

  int64 Weight(int e) {
    e = Root(e);
    return x[e];
  }

  int Root(int e) { 
    if (parent[e] < 0) return e;
    parent[e] = Root(parent[e]);
    return parent[e];
  }
};

struct Edge {
  using Weight = int64;

  int end1, end2;
  Weight weight;

  Edge() = default;
  Edge(int end1, int end2, Weight weight): end1(end1), end2(end2), weight(weight) {}

  bool operator<(const Edge& e) const {
    return weight < e.weight;
  }
};

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

  int n, m;
  cin >> n >> m;

  vector<int64> x(n);
  repeat (i, n) {
    cin >> x[i];
  }

  vector<Edge> edges;
  repeat (i, m) {
    int a, b, y;
    cin >> a >> b >> y;
    a--; b--;

    edges.emplace_back(a, b, y);
  }
  sort(begin(edges), end(edges));

  UnionFindTree union_find(x);

  int ans = m;

  repeat (i, m) {
    Edge& e = edges[i];

    union_find.Unite(e.end1, e.end2);

    if (union_find.Weight(e.end1) >= e.weight) {
      ans -= union_find.Edges(e.end1);
      union_find.Kill(e.end1);
    }
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 4208
#include <iostream>
#include<vector>
#include<map>
#include<string>
#include<stdio.h>
#include<math.h>
#include <algorithm>

#define PI		3.14159265358979
#define IMAX	2147483647

using namespace std;

int main(void) {

	int ans = IMAX;

	int n, l;
	cin >> n >> l;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int tmp = l + i;
		sum += tmp;
		if (abs(ans) > abs(tmp)) ans = tmp;
	}
	ans = sum - ans;
	cout << ans << endl;

	return 0;
}

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

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

using namespace std;
typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <class F,class ...S> void dbg(const F& f, const S&...s){cerr <<f <<": "; dbg(s...);}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, ans=0;
	cin >>n;
	
	if(n>=30) puts("Yes");else puts("No");
	return 0;
}



Measured memory_bytes: 3640
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int N_max = 1e5;
vector<vector<pair<int, int>>> graph(N_max);
vector<bool> black(N_max, false);
vector<bool> checked(N_max, false);

void explore(int now, bool now_black)
{
    for (int i = 0; i < graph[now].size(); i++)
    {
        int v = graph[now][i].first;
        int l = graph[now][i].second;
        if (!checked[v])
        {
            if (l % 2 == 0)
            {
                black[v] = now_black;
            }
            else
            {
                black[v] = !now_black;
            }
            checked[v] = true;
            explore(v, black[v]);
        }
    }
}

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

    black[0] = true;
    checked[0] = true;

    for (int i = 0; i < N - 1; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        graph[u].push_back(pair<int, int>(v, w));
        graph[v].push_back(pair<int, int>(u, w));
    }

    explore(0, true);

    for (int i = 0; i < N; i++)
    {
        if (black[i])
        {
            cout << 1 << endl;
        }
        else
        {
            cout << 0 << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 8064
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter,mul
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
#from math import factorial,hypot
#import sys
#from fractions import gcd
setrecursionlimit(10**6)
input=stdin.readline

def main():
    v,e=map(int,input().split())
    INF=2<<31
    d=[[INF]*v for _ in range(v)]
    for _ in range(e):
        s,t,c=map(int,input().split())
        d[s][t]=c
    r=range(v)
    for i in r:d[i][i]=0
    for i in r:
        for j in r:
            for k in r:
                if d[j][i]==INF or d[i][k]==INF:continue
                d[j][k]=min(d[j][k],d[j][i]+d[i][k])

    #for i in d: print(*i)

    for i in r:
        if d[i][i]<0:
            print("NEGATIVE CYCLE")
            exit()

    for i in r:
        for j in r:
            #print(d[i][j],INF,d[i][j]==INF)
            if d[i][j]==INF: d[i][j]="INF"

    for i in d: print(*i)

if __name__=="__main__":main()


Measured memory_bytes: 6280
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import Debug.Trace
import Data.List
import Data.Ord
import Control.Monad


r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine

main :: IO ()
main = do
    n <- readLn
    print $ length $ filter (<=n) $ kouho (length $ show n)

kouho :: Int -> [Int]
kouho d
    | d < 3 = []
    | otherwise = kouho (d-1) ++ (map toNumber $ filter ((==[3,5,7]).sort.nub) $ forM [1..d] (\_ -> [3,5,7]))

toNumber :: [Int] -> Int
toNumber = read.concat.map show


Measured memory_bytes: 2428
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    string s;
    cin>>s;

    int n=s.size();
    vector<int> ans(n,0);
    int ind,m0=0,m1=0;
    rep(i,n-1){
        if(s[i]=='R' && s[i+1]=='L'){
            ind=i;
            if(i%2==0) m0++;
            else m1++;
        }
        else if(s[i]=='L' && s[i+1]=='R'){
            if(i%2==0) m0++;
            else m1++;
            if(ind%2==0){
                ans[ind]=m0;
                ans[ind+1]=m1;
            }
            else{
                ans[ind]=m1;
                ans[ind+1]=m0;
            }
            m1=0,m0=0;
        }
        else{
            if(i%2==0) m0++;
            else m1++;
        }

        if(i==n-2){
            if((n-1)%2==1) m1++;
            else m0++;
            if(ind%2==0){
                ans[ind]=m0;
                ans[ind+1]=m1;
            }
            else{
                ans[ind]=m1;
                ans[ind+1]=m0;
            }
        }
    }

    rep(i,n) cout<<ans[i]<<" ";
    cout<<endl;
}



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

int cuts(ll L,ll x){
  //minimum n s.t. L/n<=x
  int ans = (L-1)/x + 1;
  return ans-1;
}

int main(){
  int N;cin >> N;
  int K;cin >> K;
  vector<ll> A(N);
  ll Amax=0;
  for(int i=0;i<N;i++){
    cin >> A[i];
    Amax = max(Amax,A[i]);
  }
  sort(A.begin(),A.end());
  reverse(A.begin(),A.end());
  ll U = 0,L = Amax;
  while(1<L-U){
    ll M = (U+L)/2;
    //cout << U << " " << M << " " << L;
    int cnt = 0;
    for(int i=0;i<N;i++){
      if(A[i]<=M){
        break;
      }else{
        cnt += cuts(A[i],M);
      }
    }
    //cout << " # " << cnt << endl;
    if(cnt>K){
      U = M;
    }else{
      L = M;
    }
  }
  //cout << U << " " <<  L << endl;
  cout << L << endl;
}

Measured memory_bytes: 4744
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 100005
#define NIL -1

/*
p: parent
l: left-child
r: right sibling
*/
struct Node{ int p, l, r; };
struct Node T[MAX]; // Tree

void pre(int u){
printf(" %d",u);
	if (T[u].l != -1)
		pre(T[u].l);
	if (T[u].r != -1)
		pre(T[u].r);
}
void in(int u){
	if (T[u].l != -1)
		in(T[u].l);
	printf(" %d", u);
	if (T[u].r != -1)
		in(T[u].r);
}
void pos(int u){
	if (T[u].l != -1)
		pos(T[u].l);
	if (T[u].r != -1)
		pos(T[u].r);
	printf(" %d", u);
}

main(){
	int i, d, v, c, n,l,j;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		T[i].p = T[i].l = T[i].r = NIL;
	}

	for (i = 0; i < n; i++){
		scanf("%d %d %d", &v, &d, &c);
		T[v].l = d;
		T[v].r = c;
		T[d].p = T[c].p = v;
		if (i == 0)l = v;
	}
	for (i = 0; i < n;i++){
		if (T[i].p == -1){ l = i; }
	}
	printf("Preorder\n");
	pre(l);
	printf("\nInorder\n");
	in(l);
	printf("\nPostorder\n");
	pos(l);
	printf("\n");
	return 0;
}

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

ans = 0

for i in range(n-1):
    if a[i]+a[i+1] > x:
        ans += a[i] + a[i+1] - x
        if a[i] > x:
            a[i+1] = 0
        else:
            a[i+1] -= a[i] + a[i+1] - x

print(ans)


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

int main()
{
	string s;
	cin >> s;
	int i=0, j=s.size()-1, t=0;
	
	while (i<j)
	{
		if (s[i]==s[j])
		{
			i++;
			j--;
		}
		else{
			t++;
			i++;
			j--;
		}	
	}
	
	cout << t;
	return 0;
}

Measured memory_bytes: 256
import sys
n_shops, n_drinks = map(int, input().split())
shop_info = sorted([tuple(map(int, line.split())) for line in sys.stdin.readlines()])
cost = 0
purchased_n_drinks = 0
for _ in range(len(shop_info)):
    info = shop_info.pop(0)
    if (purchased_n_drinks + info[1]) >= n_drinks:
        cost += ( n_drinks - purchased_n_drinks) * info[0]
        break
    purchased_n_drinks += info[1]
    cost += info[0] * info[1]
print(cost)

Measured memory_bytes: 24444
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      int sum = 0;
      int k = 0;
      int sum2 = 0;
      for(int i = 0;i < n;i++){
        a[i]=sc.nextInt();
        sum += a[i];
        sum2 += a[i]*a[i];
      }
      if((double)sum/n-sum/n >= sum/n+1-(double)sum/n)k = sum/n+1;
      else k=sum/n;
      System.out.println(n*k*k-2*k*sum+sum2);
    }
}

Measured memory_bytes: 22740
import sys
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


n = int(input())
l = map(int, input().split())

four_count = 0
two_count = 0
for v in l:
    if v % 4 == 0:
        four_count += 1
    elif v % 2 == 0:
        two_count += 1

if two_count > 0:
    if n - two_count - four_count <= four_count:
        print("Yes")
    else:
        print("No")
else:
    if n - four_count - 1 <= four_count:
        print("Yes")
    else:
        print("No")


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

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

int n, s;
ll dp[110][10][1010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> n >> s, n) {
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 0; i <= 100; i++) {
      dp[i][1][0] = 1;
      if (i == 0) continue;
      for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= s; k++) {
          dp[i][j][k] = dp[i - 1][j][k];
          if (j > 0 && k - i >= 0) {
            dp[i][j][k] += dp[i - 1][j - 1][k - i];
          }
        }
      }
    }
    cout << dp[100][n][s] << endl;
  }

  return 0;
}


Measured memory_bytes: 11848
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <list>
#include <cstring>
#include <map>
#include <queue>
#include <ctime>
#include <set>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <climits>

#define pb push_back
#define mp make_pair
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ull unsigned long long
#define rep(i,a,b) for(ll i = a; i < b; ++i)
#define sz(a) int((a).size()) 
#define pb push_back 
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(typeofa((c).begin() i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end()) 
#define p(a) cout << a << "\n";
#define p1(a) cout << a << " ";

#define PI 3.141592653589793
#define MOD (ll)(1e9 + 7)

using namespace std;
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 

map<ll, int> m;
void solve()
{
	int n;
	cin >> n;
	ll a, ans = 0;	
	rep(i,0,n)
	{
		cin >> a;
		if(m[a] == 0)
		{
			m[a] = 1;
			++ans;
		}
		else
		{
			m[a] = 0;
			--ans;
		}
	}
	p(ans)
}
int main()
{
	bool testing = false;
	IOS
	if(testing)
	{
		freopen("test.txt","rt",stdin);
		int start = clock();
		solve();
		int end = clock();
		cout << "time: " << (end - start)/(double)(CLOCKS_PER_SEC)*1000 << " milliseconds\n";
	}
	else
	{
		solve();
	}
} 

Measured memory_bytes: 6528
n = int(input())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))

def dist(x,y,p):
    val = 0
    for xi,yi in zip(x,y):
        val += (abs(xi-yi))**p
    return val**(1/p)
    
def cheb(x,y):
    val = 0
    for xi,yi in zip(x,y):
        val_tmp = abs(xi-yi)
        if val_tmp>val:
            val = val_tmp
    return val
    
print(dist(X,Y,p=1))
print(dist(X,Y,p=2))
print(dist(X,Y,p=3))
print(cheb(X,Y))


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

template <typename T>
class FenwickTree {
	const ll n;
	unordered_map<ll, T> data;
public:
	FenwickTree(ll n_, int pmax = 1e6) : n(n_), data(pmax) {}
	T find(ll p) {
		T res = 0;
		while (p >= 0) {
			res += data[p];
			p = (p & (p + 1)) - 1;
		}
		return res;
	}
	void add(ll p, T val) {
		while (p < n) {
			data[p] += val;
			p |= p + 1;
		}
	}
};

template <typename T>
class RARS {
	const ll n;
	FenwickTree<T> bit0, bit1;
public:
	RARS(ll n_) : n(n_), bit0(n), bit1(n) {}
	T find(ll p) {
		return bit1.find(p) * (p + 1) + bit0.find(p);
	}
	T find(ll l, ll r) {
		return find(r) - find(l - 1);
	}
	void add(ll l, ll r, T val) {
		bit0.add(l, -val * l);
		bit1.add(l, val);
		bit0.add(r + 1, val * (r + 1));
		bit1.add(r + 1, -val);
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	RARS<ll> rars(n);
	for (int i = 0, type, s, t, x; i < q; i++) {
		cin >> type >> s >> t; s--; t--;
		if (type) {
			printf("%lld\n", rars.find(s, t));
		}
		else {
			cin >> x;
			rars.add(s, t, x);
		}
	}
	return 0;
}



Measured memory_bytes: 25308
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#define int long long
#define mod 1000000007
using namespace std;
int d, n, t[250], a[250], b[250], c[250], dp[250][250], ans;
signed main() {
	cin >> d >> n;
	for (int i = 1; i <= d; i++) cin >> t[i];
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
	for (int i = 1; i <= n; i++)if (t[1] < a[i] || b[i] < t[1])dp[1][i] = -100000000;
	for (int i = 2; i <= d; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = -100000000;
			if (a[j] <= t[i] && t[i] <= b[j])
				for (int k = 1; k <= n; k++) {
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + abs(c[k] - c[j]));
				}
			if (i == d)ans = max(ans, dp[i][j]);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3484