akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<iostream>
#include<fstream>
#define ll long long
using namespace std;

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

    int ans = 0;
    int s = 0, e = S.length() - 1;
    while(e > s){
        cerr << S.substr(s, e-s+1) << endl;
        if(S[e]==S[s]){
            s++; e--;
        }else if(S[s]=='x'){
            s++;
            ans++;
        }else if(S[e]=='x'){
            e--;
            ans++;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
const ll mod = 1e9 + 7;

int main()
{
    ll n;
    cin >> n;
    ll ans = LLONG_MAX;
    for (ll i = 1; i <= sqrt(n); i++)
    {
        ll max = 0;
        if (n % i == 0)
        {
            if (i >= n / i)
                max = i;
            else
                max = n / i;
            ll count = 0;
            while (max > 0)
            {
                count++;
                max /= 10;
            }
            if (ans >= count)
                ans = count;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
// ConsoleApplication1.cpp : アプリケーションのエントリ ポイントを定義します。
//



#include <iostream>
#include <string>
#include <cmath>

//090 B

using namespace std;
int main()
{
	int A, B;
	int cnt = 0;
	cin >> A >> B;

	int a[5];

	for (int j = A; j <= B; j++) {
		int k = A;
		for (int i = 0; i < 5; i++) {
			a[i] = k % 10;
			k /= 10;
		}
		if (a[0] == a[4] && a[1] == a[3]) {
			cnt++;
		}
		A++;
	}

	cout << cnt << endl;
	return 0;
}



Measured memory_bytes: 256
N = int(input())
R = []
for _ in range(N):
    x, l = map(int, input().split())
    R.append([x-l, x+l])

R = sorted(R, key=lambda x: x[1])

ans = 0
tmp = -float('inf')
for l, r in R:
    if tmp <= l:
        ans += 1
        tmp = r
print(ans)


Measured memory_bytes: 63576
import java.util.Scanner;

public class Main {

	static boolean f(int w, int[] book, int n, int m) {
		int need = 1;
		int s = 0;
		for (int i = 0; i < m; i++) {
			if (book[i] > w) {
				return false;
			}
			if (s + book[i] > w) {
				need++;
				s = 0;
			}
			s += book[i];
		}
		return need <= n;
	}

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			if (n == 0 && m == 0)
				break;
			int[] book = new int[m];
			int sum = 0;
			for (int i = 0; i < m; i++) {
				book[i] = scanner.nextInt();
				sum += book[i];
			}
			int ave = sum / n;

			int l = ave;
			int r = sum;
			while (r - l >1) {
				int mid = (l + r) / 2;
				if (f(mid, book, n, m)) {
					r = mid;
				} else {
					l = mid;
				}
			}
			System.out.println(f(l, book, n, m) ? l : r);
		}

	}
}

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

int main(){

  int a,b,c;
 
  cin >>  a >> b >> c;
  
  if (a<=b && b<=c)  cout<<a<<" "<<b<<" "<<c<< '\n';
  else if (c<=b && b<=a)  cout<<c<<" "<<b<<" "<<a<<'\n';
  else if (b<=c && c<=a) cout <<b<<" "<<c<<" "<<a<<'\n'; 
  else if (b<=a && a<=c) cout << b<<" "<< a<<" "<< c <<'\n';
  else if (a<=c && c<=b) cout << a<<" "<< c<<" "<< b << '\n';
  else if (c<=a && a<=b) cout << c<<" "<< a<<" "<< b <<'\n';
  
return 0;

}

Measured memory_bytes: 1164
#include <stdio.h>
int main(void)
{
	int n, a[100];

	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = n - 1; i >= 0; --i) {
		printf("%d", a[i]);
		if (i != 0) {
			printf(" ");
		}
		else {
			printf("\n");
		}
	}

	return 0;
}



Measured memory_bytes: 2124
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        try{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int[] highs = new int[10];
            for(int i=0;i<highs.length;i++){
                highs[i] = Integer.parseInt(br.readLine());
            }
            Arrays.sort(highs);
            for(int i=highs.length-1;i>=highs.length-3;i--){
                System.out.println(highs[i]);
            }
        }
        catch(Exception e){
            e.printStackTrace();
        }
	}
}

Measured memory_bytes: 9184
#include <iostream>
#define ll long long int
using namespace std;

int main(){

    ll N,a,b,ret,_ret;
    cin >> N;

    a = N;
    b = 1;
    ret = a + 1 - 2;

    for (int i=1; i<=10000000; i ++){
        if(a%i == 0){
            _ret = (a/i) + (b*i) - 2;
            if(ret > _ret){
                ret = _ret;
            }
        }
    }

    cout << ret<< endl;


    return 0; 
}

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

int main(){
  int A, B;  //5ケタ
  cin>>A>>B;
  int count=0;
  vector<int> N(4);
  for(int i=A; i<=B; i++){
    N.at(0)=i%10; //1
    N.at(1)=(i/10)%10; //10
    N.at(2)=(i/1000)%10; //1000, 100は飛ばし
    N.at(3)=(i/10000)%10; //10000
    if(N.at(0)==N.at(3) && N.at(1)==N.at(2)) count++;
  }
  cout<<count<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;

#define M 1000000 
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define fill(a,x) memset(a,x,sizeof(a))
#define F first
#define S second
#define FOR(i,a,b) for(ll i = a; i<=b; ++i)
#define NFOR(i,a,b) for(ll i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const ll N = 2e5 + 10;
inline ll add(ll x,ll y){
  x += y;
  if(x >= mod) x -= mod;
  return x;
}
inline ll mul(ll x,ll y){
  x = (1LL * x * y) % mod;
  return x;
}
int n; 
int a[17][17];
ll cal[1<<17];

ll calc(int mask){
  if(cal[mask]!=-INF)return cal[mask];
  vector<int>vv;
  FOR(i,0,n-1){
    if(mask&(1<<i))vv.pb(i);
  }
  ll val = 0;
  for(int i = 0;i<vv.size();i++){
    for(int j = i+1;j<vv.size();j++){
      val = val + a[vv[i]][vv[j]];
    }
  }
  cal[mask] = val;
  return cal[mask];
}

int main(int argc, char const *argv[])
{    
  #ifdef LOCAL_TEST
  freopen("in.txt","r",stdin);
  //freopen("out.txt", "w", stdout);
  #else
  ios_base::sync_with_stdio(false);cin.tie(NULL);
  #endif
    
  cin >> n;

  FOR(i,0,n-1)FOR(j,0,n-1)cin >> a[i][j];

  ll dp[1<<n]; 
  FOR(i,0,1<<n)cal[i] = -INF;
  dp[0] = 0;
  FOR(mask , 0, (1<<n)-1){
    dp[mask] = 0;
    for(int i = mask;i>0;i=(i-1)&mask){
      dp[mask] = max(dp[mask],calc(i) + dp[mask^i]);
    }
  }

  cout << dp[(1<<n)-1];

  return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 200010;

int main() {
    ll n;
    cin >> n;
 
    vl c(MAX_N);
    exrep(i, 1, n) {
        cin >> c[i];
    }
 
    vl dp(MAX_N);  // dp[i] : 最初からi個(iは1-index)の石の場合の数
    vl v(MAX_N);  // v[i] : j < i かつ c[j] = c[i] となる最大のj (存在しないときは0)
    vl w(MAX_N);  // vを埋めるための補助的なvector
 
    exrep(i, 1, n) {
        v[i] = w[c[i]];
        w[c[i]] = i;
    }
 
    dp[0] = 1;
    exrep(i, 1, n) {
        dp[i] = dp[i-1];  // i個目の石に操作をしない場合の数はdp[i-1]通り
        if(v[i] != 0 && v[i] != i-1) {  // j < i かつ c[j] = c[i] となるjが存在して、c[i-1] != c[i] のとき
            dp[i] += dp[v[i]];  // i個目とv[i]個目の石に対して操作を行うときの場合の数はdp[v[i]]通り
            dp[i] %= mod;
        }
    }
 
    out(dp[n]);
    re0;
}

Measured memory_bytes: 6528
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = Integer.parseInt(scanner.nextLine());
        String[] board = new String[N];
        for (int i = 0; i < N; ++i) {
            board[i] = scanner.nextLine();
        }
        int count = 0;
        for (int a = 0; a < N; ++a) {
            if (check(board, N, a)) {
                ++count;
            }
        }
        System.out.println(count * N);
    }

    private static boolean check(String[] board, int N, int a) {
        for (int y = 0; y < N; ++y) {
            for (int x = 0; x < N; ++x) {
                int y2 = x - a;
                int x2 = y + a;
                if (y2 < 0) {
                    y2 += N;
                }
                if (x2 >= N) {
                    x2 -= N;
                }
                if (y2 != x2) {
                    if (board[y].charAt(x) != board[y2].charAt(x2)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

Measured memory_bytes: 26420
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(int)(b); i++)
#define PPC(x) __builtin_popcountll((x))
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
using namespace std;

const int maxN = 200042, E = 400;
char in[maxN];
pair <char, int> qs[maxN];

int n, q;

int sym(int i)
{
	FOR(j, 0, q)
		if (qs[j].first == in[i])
			i += qs[j].second;
	return i;
}

int main()
{
	scanf ("%d%d", &n, &q);
	scanf ("%s", in + 1);
	FOR(i, 0, q)
	{
		char buf[42];
		scanf ("%s", buf);
		scanf ("%s", buf+5);
		qs[i].first = buf[0];
		qs[i].second = buf[5] == 'L' ? -1 : 1;
	}
		
	int bg = 0, ed = n+1;
	while (ed - bg > 1)
	{
		int mid = (bg + ed) / 2;
		sym(mid) == 0 ? bg = mid : ed = mid;
	}
	
	int lastLeft = bg;
	
	bg = 0, ed = n+1;
	while (ed - bg > 1)
	{
		int mid = (bg + ed) / 2;
		sym(mid) == n+1 ? ed = mid : bg = mid;
	}
	
	int firstRight = ed;
	
	int res = (firstRight - 1) - lastLeft;
	printf("%d\n", res);
	return 0;
}	


Measured memory_bytes: 2048
#include<bits/stdc++.h>
#define ll long long

const int N = 200010;

inline int lowbit(int n){return n & (-n);}

std::vector <ll> vec;
int n, k;
int a[N];
ll pre[N];
int c[N];

int getsit(ll n){
	return std::lower_bound(vec.begin(), vec.end(), n) - vec.begin() + 1;
}

int add(int sit, int value){
	for ( ; sit < N; sit += lowbit(sit)){
		c[sit] += value;
	}
}

int query(int sit){
	int ret = 0;
	for ( ; sit; sit -= lowbit(sit)){
		ret += c[sit];
	}
	return ret;
}

int main(){
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
		a[i] -= k;
	}
	for (int i = 1; i <= n; ++ i){
		pre[i] = pre[i - 1] + a[i];
	}
	for (int i = 0; i <= n; ++ i){
		vec.push_back(pre[i]);
	}
	std::sort(vec.begin(), vec.end());
	vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
	long long ans = 0;
	add(getsit(0), 1);
	for (int i = 1;i <= n; ++ i){
		int sit = getsit(pre[i]);
		ans += query(sit);
		add(sit, 1);
	}
	return printf("%lld\n", ans), 0;
}

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

bool check(string s){
	int len=s.length();
	char cur=s[0];
	bool ok=true;
	for(int i=0;i<len;i++)
		if(s[i]!=cur)
			ok=false;	
	return ok;
}

int main(){
	string ms;
	cin >> ms;
	int ans=INT_MAX;
	for(int i=0;i<26;i++){
		int cnt=0;
		string s=ms;
		while(true){
			if(check(s)){
				ans=min(ans,cnt);
				break;
			}
			cnt++;
			string ts="";
			int len=s.length();
			for(int j=0;j<len-1;j++){
				if(s[j]=='a'+i || s[j+1]=='a'+i)
					ts+='a'+i;
				else
					ts+=s[j];
			}
			s=ts;
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream> 
#include<string>
#include<bits/stdc++.h>
using namespace std;
int main(){	
	int k,x;
	cin>>k>>x;
	for(int i=0;i<2*k-1;i++){
		cout<<x-k+1+i<<" ";
	}
    return 0;
} 

Measured memory_bytes: 256
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        xy: [(f64, f64); 3],
    }
    let a = ((xy[0].0 - xy[1].0).powf(2f64) + (xy[0].1 - xy[1].1).powf(2f64)).sqrt();
    let b = ((xy[1].0 - xy[2].0).powf(2f64) + (xy[1].1 - xy[2].1).powf(2f64)).sqrt();
    let c = ((xy[2].0 - xy[0].0).powf(2f64) + (xy[2].1 - xy[0].1).powf(2f64)).sqrt();

    let M = if a > b && a > c {
        a
    } else if b > a && b > c {
        b
    } else {
        c
    };

    let s = (a + b + c) / 2.;
    let S = (s * (s - a) * (s - b) * (s - c)).sqrt();

    let r = (2. * S) / (a + b + c);

    println!("{}", r * M / (2. * r + M));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
const int inf = 10234567;

int n; 
int P[200055];
int value[200055];
int totalPhigh = 0;

struct state{ int maxX, maxY, highX, highY; };
state cur = {0,0,0,0};

struct segment{
	int tree[400105];
	int N;
	
	void init(int _N){
		N = _N;
		for(int i = 0;i <= 2*N;i++) tree[i] = -inf;
	}
	
	void update(int i, int x){
		i += N;
		tree[i] = x;
		i >>= 1;
		while(i > 0){
			tree[i] = max(tree[i<<1], tree[i<<1|1]);
			i >>= 1;
		}
	}
	
	int query(int l, int r){
		int res = -inf;
		for(l += N, r += N;l < r;l >>= 1, r >>= 1){
			if(l&1) res = max(res, tree[l++]);
			if(r&1) res = max(res, tree[--r]);
		}
		return res;
	}
} odd, even;

bool verify(state S){
	
	///let a be all Phigh
	int target = totalPhigh + S.highX - S.highY;
	if(target >= 0){ ///IMPT
		int best; ///look for best with same parity as target
		if(target % 2 == 0) best = even.query(S.maxY, n+1);
		else best = odd.query(S.maxY, n+1);
		if(best >= target) return true;
	}
	
	///let b be all Phigh
	target = totalPhigh - S.highX + S.highY;
	if(target >= 0){ ///IMPT
		int best; ///look for best with same parity as target
		if(target % 2 == 0) best = even.query(S.maxX, n+1);
		else best = odd.query(S.maxX, n+1);
		if(best >= target) return true;
	}
	
	return false;
}

state addTo(state ori, int value, bool isX){ ///function to transition from one state to another
	state nxt = ori; 
	if(isX){
		if(value > nxt.maxX){
			nxt.maxX = value;
			nxt.highX++;
		}
	}
	else{
		if(value > nxt.maxY){
			nxt.maxY = value;
			nxt.highY++;
		}
	}
	return nxt;
}

	
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> P[i];
	P[0] = 0;
	
	int maxValue = 0;
	for(int i = 0;i <= n;i++){
		if(maxValue < P[i]){
			maxValue = P[i];
			value[i] = 2;
			totalPhigh++;
		}
		else value[i] = 1;
	}
	
	odd.init(n+2); even.init(n+2);
	
	///do LDS from the back (LIS in left to right)
	for(int i = n;i >= 1;i--){
		int best1 = odd.query(P[i]+1, n+1) + value[i]; ///take from odd
		int best2 = even.query(P[i]+1, n+1) + value[i]; ///take from even
		int best3 = value[i]; ///take for first time
		
		int bestOdd = -inf, bestEven = -inf;
		
		if(best1 % 2 == 0) bestEven = max(bestEven, best1);
		else bestOdd = max(bestOdd, best1);
		
		if(best2 % 2 == 0) bestEven = max(bestEven, best2);
		else bestOdd = max(bestOdd, best2);
		
		if(best3 % 2 == 0) bestEven = max(bestEven, best3);
		else bestOdd = max(bestOdd, best3);
		
		even.update(P[i], bestEven);
		odd.update(P[i], bestOdd);
	}
		
		

	string ans = "";
	for(int i = 1;i <= n;i++){
		///we undo the dp table (stored in segment tree)
		odd.update(P[i], -inf);
		even.update(P[i], -inf);
		
		if(value[i] == 2) totalPhigh--; 
		
		if(P[i] < cur.maxX && P[i] < cur.maxY){ ///IMPT
			ans += '0';
			continue;
		}
		
		///try to add to X
		state nxt = addTo(cur, P[i], true);
		
		if(verify(nxt)){ ///check if can be done
			ans += '0';
			cur = nxt;
		}
		else{
			ans += '1';
			cur = addTo(cur, P[i], false);
		}
	}
	
	if(cur.highX != cur.highY) ans = "-1";
	cout << ans;
}


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

priority_queue<pair<int,int> > s1,s0;

int num[111111][2];
int n;

int main()
{
	cin>>n;
	int M=-1;
	int x;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		M=max(M,x);
		num[x][(i&1)^1]++;
	}
	for(int i=1;i<=M;i++)
	{
		if(num[i][1])
			s1.push(make_pair(num[i][1],i));
		if(num[i][0])
			s0.push(make_pair(num[i][1],i));
	}
	vector<int> v1,v0;
	while(!s1.empty())
	{
		v1.push_back(s1.top().second);
		s1.pop();
	}
	while(!s0.empty())
	{
		v0.push_back(s0.top().second);
		s0.pop();
	}
	int maxx=-1221;
	int l1=min((int)v0.size(),30000),l2=min((int)v1.size(),30000);
	for(int i=0;i<l1;i++)
	for(int j=0;j<l2;j++)
	{
		if(v0[i]!=v1[j])
			maxx=max(maxx,num[v0[i]][0]+num[v1[j]][1]);
	}
	if(maxx==-1221)
		cout<<min(n/2,(n+1)/2)<<endl;
		
	else	cout<<n-maxx<<endl;
	return 0;
}

Measured memory_bytes: 2440
#include<cstdio>
#include<algorithm>
#include <utility>
using namespace std;

const int MAX_N = 100000;
pair<int, int> r[MAX_N];

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=0;i<m;i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		r[i].first = a;
		r[i].second = b;
	}
	sort(r, r+m);
	int ans = 0;
	for(int i=0;i<m;) {
		int minb = n+1;
		while(i<m && r[i].first < minb) {
			if(r[i].second < minb) minb = r[i].second;
			i++;
		}
		if(minb < n+1) ans++;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 896
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    String s;
    int i;
    boolean a, b, c, d;
    a = false; b = false; c = false; d = false;
    s = sc.next();
    if(s.length() > 5)a = true;
    for(i = 0;i < s.length();i++){
      if(s.charAt(i) >= '0' && s.charAt(i) <= '9')b = true;
      if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')c = true;
      if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z')d = true;
    }
    if(a && b && c && d)out.println("VALID");
    else out.println("INVALID");

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 26300
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    ll ans = INT_MAX;
    for (ll i = -100; i <= 100; i++) {
        //iに書き換える
        ll tmp = 0;
        for (ll j = 0; j < N; j++) {
            tmp += (i - a[j]) * (i - a[j]);
        }
        ans = min(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    string s;
    cin >> s;
    rep(i, n-2){
        if(s.at(i) == 'A' && s.at(i+1) == 'B' && s.at(i+2) == 'C'){
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#if __has_include("noamoa_atcoder_lib.h")
#include "noamoa_atcoder_lib.h"
#else
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define endl '\n'
#define all(x) (x).begin(),(x).end()
namespace atcoder {
	using namespace std;
	using ll = long long;
	using llv = vector<ll>;
	using intv = vector<int>;
	using charv = vector<char>;
	using boolv = vector<bool>;
	using floatv = vector<float>;
	using doublev = vector<double>;
	using stringv = vector<string>;

	constexpr ll MOD7 = 1000000007;
	constexpr ll MOD9 = 1000000009;

	template<typename T>
	void init(vector<T>& v, T initVal = T()){
		for(auto& e : v){
			e = initVal;
		}
	}

	template<typename T>
	void sort(vector<T>& v){
		sort(all(v));
	}
	template<typename T>
	void sortInv(vector<T>& v){
		sort(all(v), greater<T>());
	}

	template<typename T>
	void reverse(vector<T>& v){
		reverse(all(v));
	}

	template<typename T>
	T sum(const vector<T>& v){
		T ret = 0;
		for(const auto& e : v) ret += e;
		return ret;
	}

	template<typename T>
	inline vector<T>& operator+=(vector<T>& v, const T& e){
		v.push_back(e);
		return v;
	}

	template<typename T1, typename T2>
	inline vector<T1>& operator+=(vector<T1>& v1, const vector<T2>& v2){
		for(const auto& e : v2) v1.push_back(e);
		return v1;
	}

	template<typename T>
	void in(vector<T>& v){
		for(auto& e : v) cin >> e;
	}

	template<typename T1, typename T2>
	void in(vector<T1>& v1, vector<T2>& v2){
		for(int i=0;i<v1.size();i++)
			cin >> v1[i] >> v2[i];
	}
	template<typename T1, typename T2, typename T3>
	void in(vector<T1>& v1, vector<T2>& v2, vector<T3>& v3){
		for(int i=0;i<v1.size();i++)
			cin >> v1[i] >> v2[i] >> v3[i];
	}
	template<typename T1, typename T2, typename T3, typename T4>
	void in(vector<T1>& v1, vector<T2>& v2, vector<T3>& v3, vector<T4>& v4){
		for(int i=0;i<v1.size();i++)
			cin >> v1[i] >> v2[i] >> v3[i] >> v4[i];
	}

	template<typename T>
	istream& operator>>(istream &stream, vector<T>& v){
		for(auto& e : v) stream >> e;
		return stream;
	}

	template<typename T>
	void out(const vector<T>& v){
		for(const auto& e : v) cout << e << ' ';
		cout << endl;
	}

	template<typename T>
	void outln(const vector<T>& v){
		for(const auto& e : v) cout << e << endl;
	}

	constexpr ll modPow(ll x, ll n, ll m){ // O(logn)
		if(n == 0) return 1;
		else if(n % 2 == 0) return modPow((x * x) % m, n / 2, m);
		else return x * modPow(x, n - 1, m) % m;
	}
}
using namespace atcoder;
#endif

int main(){
	cout << fixed << setprecision(15);

	string s;cin>>s;
	cout<<(s=="ABC"?"ARC":"ABC");
}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <map>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <cmath>
#define read(X) scanf("%d",&X);
#define readLL(X) cin>>X;
#define readN(N,a) for(int i=0;i<N;i++)scanf("%lld",&a[i]);
#define LL long long
#define FOR(x,a,b) for(int x=a;x<b;x++)
#define pii pair<int,int>
#define INF 3000000
using namespace std;

long long mons[100005];
int N,A,B,dmg;
bool valid(long long attmp){
	long long at=0;
	long long dealt = attmp * (long long) B;
	for (int i=0;i<N;i++){
		if (mons[i] <= dealt) continue;
		at += (mons[i] - dealt + dmg - 1) / dmg;
	}
	if (at > attmp) return false;
	return true;
}

int main(){
	cin>>N>>A>>B;
	dmg = A - B;
	long long res = 0;
	
	readN(N,mons);


	long long lo = 1LL;
	long long hi = 1000000000LL;
	while (lo < hi){
		long long mid = (lo + hi) / 2;
		if (valid(mid)) hi = mid;
		else lo = mid+1;
	}
	cout<<lo<<endl;

}

Measured memory_bytes: 1024
#include<stdio.h>
#include<math.h>
#define N 10000
int hantei (int);

int main(){
  int a[N];
  int i=0,j,l,num=0,count=0;


  while(i<N){
    if(scanf("%d",&a[i])==EOF)break;
    i++;
    num++;
  }
  for(j=0;j<num;j++){
    l=hantei(a[j]);
  if(l==1)count++;
  }
  printf("%d\n",count);
  return 0;
}


int hantei (int x){
  int k;
    if(x==2)return 1;
    if(x<2 || x%2==0)return 0;
    
    k=3;
    while(k<=sqrt((double)x)){
      if(x%k == 0)return 0;
      k=k+2;
    }
    return 1;
}



Measured memory_bytes: 2044
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(int, x, y, z);
    print(z, x, y);

    return 0;
}


Measured memory_bytes: 256
import numpy as np
N,D= map(int, input().split())
#2次元配列
X=[[int(j) for j in input().split()] for i in range(N)]
d=0
ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        for k in range(0,D):
            d=d+(X[i][k]-X[j][k])**2
        if d==(int(np.sqrt(d)))**2:
            ans=ans+1
        d=0
print(ans)

Measured memory_bytes: 12496
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    vector<vector<int>> U(H, vector<int>(W, 0)), D(U), L(U), R(U);
    for (int i = 0; i < H; i++) {
        cin >> S[i];
        if (S[i][0] == '.') L[i][0] = 1;
        if (S[i][W - 1] == '.') R[i][W - 1] = 1;
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '.') {
                U[i][j] = i == 0 ? 1 : U[i - 1][j] + 1;
                if (j > 0) L[i][j] = L[i][j - 1] + 1;
            }
            if (j > 0 && S[i][W - 1 - j] == '.') R[i][W - 1 - j] = R[i][W - j] + 1;
        }
    }
    for (int i = H - 1; i >= 0; i--) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '.') D[i][j] = i == H - 1 ? 1 : D[i + 1][j] + 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (S[i][j] == '#') continue;
            auto t = U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3;
            if (t > ans) ans = t;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 67200
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const N = Number(input[0][0]);

  const digitSum = N.toString()
    .split("")
    .map(Number)
    .reduce((sum, cur) => sum + cur);

  return N % digitSum === 0 ? "Yes" : "No";
};

console.log(main(read()));


Measured memory_bytes: 29736
#include<bits/stdc++.h>
using namespace std;
#define loop(i,x,z) for (int i=x;i<z;i++)
using ll = long long;
const int M = 1000000007;
int n, w;
ll dp[1002][1002];
bool A[1002][1002];
ll travel(int x,int y)
{
	if (x > n || y > w) return 0;
	//cout << "yup";
	if (dp[x][y] >= 0 || !A[x][y])
	{
		if (dp[x][y] >= 0)
			return dp[x][y];
		else return 0;
	}
	//cout << "yup";
	dp[x][y] = (travel(x + 1, y) + travel(x, y + 1)) % M;
	return dp[x][y];
}
int main()
{
	cin >> n >> w;
	memset(dp, -1, sizeof(dp));
	loop(i,1,n+1)
		loop(j, 1, w + 1)
			{
				char a;
				cin >> a;
				if (a == '.') A[i][j] = 1;
			}
	dp[n][w] = 1;
	cout << travel(1,1);
}

Measured memory_bytes: 9216
c = [list(map(int,input().split())) for _ in range(3)]
for i in range(2):
    x = c[0][i] - c[0][i+1]
    y = c[1][i] - c[1][i+1]
    z = c[2][i] - c[2][i+1]
    if not (x==y and y==z and z==x):
        print('No')
        exit()
for i in range(2):
    x = c[i][0] - c[i+1][0]
    y = c[i][1] - c[i+1][1]
    z = c[i][2] - c[i+1][2]
    if not (x==y and y==z and z==x):
        print('No')
        exit()
print('Yes')


Measured memory_bytes: 3188
/*---------------------------------------------------------------------*/
/*                   -------------------------------------             */
/*                   -----------MEHEDI HASAN--------------             */
/*                   -----CSE,JAHANGIRNAGAR UNIVERSITY----             */
/*                   -------------------------------------             */
/*---------------------------------------------------------------------*/
#include<bits/stdc++.h>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
/*---------------------------------------------------------------------*/
#define FAST        ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define cc(x)       cout<<#x<<"="<<x<<" ";
#define ccc(x)      cout<<#x<<"="<<"("<<x.ff<<" "<<x.ss<<") ";
#define CC(x)       cout<<"["<<#x<<"] = ";for(auto xx: x) cout<<xx<<" ";
#define CCC(x)      cout<<"["<<#x<<"] = ";for(auto xx: x) cout<<"("<<xx.ff<<" "<<xx.ss<<") ";
#define mark(x)     cout<<x<<" ";
#define ee          cout<<"\n";
#define OK          cout<<"Ok"<<"\n";
/*---------------------------------------------------------------------*/
#define ff          first
#define ss          second
#define ll          long long
#define ull         unsigned long long
#define pii         pair<int,int>
#define mp          make_pair
#define ps          push
#define psb         push_back
#define psf         push_front
#define pp          pop
#define ppb         pop_back
#define ppf         pop_front
#define all(x)      x.begin(),x.end()
#define TESTS       int t;cin>>t;for(int tcase=1;tcase<=t;tcase++)
#define ordered_set tree< int, null_type, less_equal< int >, rb_tree_tag, tree_order_statistics_node_update>
/*---------------------------------------------------------------------*/
#define MAX (ll)(2e5+9)
#define MOD (ll)(1e9+7)

int main()
{
    FAST
    int x,y,z;
    cin>>x>>y>>z;
    swap(x,y);
    swap(x,z);
    cout<<x<<" "<<y<<" "<<z<<endl;


    return 0;
}

/*--------------------------------------------------------------------*/
/*
>Check Corner Cases (n==1 or T==1)
>Overflow issues?
>LB / UB !!not found!! check?
*/
/*--------------------------------------------------------------------*/
/* ---INPUT---
--------(1)------


-------(2)-------


-------(3)-------


-------(4)-------



--------------
*/
/*--------------------------------------------------------------------*/




Measured memory_bytes: 256
N=int(input())
S=list(input())
cnt=0
maxcnt=0
for i in range(N):
    if i==0:
        if S[0] in S[1:N]:
            cnt+=1
        if maxcnt<cnt:
            maxcnt=cnt
    elif i == N-1:
        if S[N-1] in S[0:N]:
            cnt-=1
    else:
        if S[i] not in S[0:i] and S[i] in S[i+1:N]:
            cnt+=1
            if maxcnt<cnt:
                maxcnt=cnt
        elif S[i] in S[0:i] and S[i] not in S[i+1:N]:
            cnt-=1
        else:
            pass
print(maxcnt)

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

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

  int a=0;
  rep(i,s.size()){
    if(s.at(i)!= t.at(i)) a++;
  }
  if(t.size() == s.size() +1 && a == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
using namespace std;
inline int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int M=1e5+10,mod=1e9+7;
LL fast(LL x,LL p){
	LL ret=1;
	for (;p;p>>=1,x=x*x%mod) if (p&1) ret=ret*x%mod;
	return ret;
}
int f[M],s[M],si[M],n;
bool vis[M];
LL Fd(int x){
	if (f[x]==x) return x;
	return f[x]=Fd(f[x]);
}
int dp[M],a[M],ct,cs;
int main(){
	n=read();
	F(i,1,n) f[i]=i; 
	F(i,1,n){
		a[i]=read();
		if (a[i]!=-1) {
			int u=Fd(i),v=Fd(a[i]);
			if (u!=v) f[u]=v; 
		}
	}
	F(i,1,n){
		if (!s[Fd(i)]) ct++; 
		s[Fd(i)]++;
		if (a[i]==-1) si[Fd(i)]++,cs++;
	}
	int block=ct-cs;
	LL tot=fast(n-1,cs),ans=1ll*tot*n%mod,tbl=1ll*block*tot%mod,sv=0; 
	dp[0]=1;
	F(i,1,n){
		if (vis[Fd(i)] || !si[Fd(i)]) continue;
		int x=Fd(i); vis[x]=1; sv=(sv+(s[x]-1)*fast(n-1,cs-1))%mod;
		DF(i,n,1){
			dp[i]=(dp[i]+1ll*dp[i-1]*s[x])%mod;
		}
	}
	LL fac=1;
	F(i,2,cs){
		fac=1ll*fac*(i-1)%mod;
		sv=(sv+1ll*dp[i]*fac%mod*fast(n-1,cs-i))%mod; 
	}
//	cout<<tot<<" "<<sv<<" "<<tbl<<"   sb250\n";
	cout<<(ans-tbl-sv+mod)%mod<<"\n";
	return 0;
}




Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple
int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	int n; cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int t1=a[n/2 - 1], t2=a[n/2];
	cout<<t2-t1;
	return 0;
}


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

using namespace std;
typedef long long ll;
const int N = 200010;
int _w;

int l, n, x[N];
ll pf[N], sf[N];
ll ans;

int main() {
	_w = scanf( "%d%d", &l, &n );
	for( int i = 1; i <= n; ++i )
		_w = scanf( "%d", x+i );
	ans = max( x[n], l-x[1] );
	for( int i = 1; i <= n; ++i )
		pf[i] = pf[i-1] + x[i];
	for( int i = n; i >= 1; --i )
		sf[i] = sf[i+1] + l - x[i];
	for( int L = 1; L < n; ++L ) {
		int R = n-L;
		if( L < R ) {
			ll now = pf[L] * 2 + (sf[L+1] - sf[L+L+1]) * 2 - min(x[L], l-x[L+1]);
			now = max(now, pf[L] * 2 + (sf[L+2] - sf[L+L+2]) * 2 + (l-x[L+1]));
			ans = max(ans, now);
		} else if( L == R ) {
			ll now = pf[L] * 2 + sf[L+1] * 2 - min(x[L], l-x[L+1]);
			ans = max(ans, now);
		} else {
			ll now = (pf[L] - pf[L-R]) * 2 + sf[L+1] * 2 - min(x[L], l-x[L+1]);
			now = max(now, (pf[L-1] - pf[L-R-1]) * 2 + sf[L+1] * 2 + x[L]);
			ans = max(ans, now);
		}
	}
	cout << ans << endl;
	return 0;
}


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

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 32; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}
long long Div(long long p, long long q, long long m) {
	return (p * modpow(q, m - 2, m)) % m;
}

long long N, A[100009], mod = 1000000007;
long long fact[100009], division[100009];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	fact[0] = 1; for (int i = 1; i <= N; i++) fact[i] = (fact[i - 1] * i) % mod;
	for (int i = 1; i <= N; i++) division[i] = Div(fact[N], i, mod);

	long long sum = 0, ans = 0;
	for (int i = 1; i <= N; i++) { sum += division[i]; sum %= mod; }

	for (int i = 1; i <= N; i++) {
		ans += (A[i] * sum); ans %= mod;
		sum -= division[N + 1 - i]; sum += division[i + 1]; sum += mod * mod; sum %= mod;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560
using System;

class Program
{
    static void Main()
    {
        //読み込む、チェック、0でなければ出力
        //読み込む、チェック、0だったら出力せず終了
        string str;
        for (var i = 1; ; i++)
        {
            str = Console.ReadLine();
            if (int.Parse(str) != 0) Console.WriteLine("Case {0}: {1}", i, str);
            else break;
        }
    }
}


Measured memory_bytes: 9896
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <queue>
#include <cctype>
#include <climits>
#include <stack>
using namespace std;
 
int n,m,r;
const int INF=1e7;
int d[2][200][200];
int dp[1001][200];
typedef pair<int,int> P;
 
int main(){
 
 
    while(scanf("%d %d",&n,&m),n){
	    
	   for(int i=0;i<n;i++){
		  for(int j=0;j<n;j++) d[0][i][j]=d[1][i][j]=INF;
		  d[0][i][i]=d[1][i][i]=0;
	   }
	    
	   for(int i=0;i<m;i++){
		  int x,y,t;
		  char c;
		  scanf("%d %d %d %c",&x,&y,&t,&c);
		  x--; y--;
		  
		  d[c=='L'][x][y]=min(d[c=='L'][x][y],t);
		  d[c=='L'][y][x]=min(d[c=='L'][y][x],t);
	   }
	    
	   for(int k=0;k<n;k++){
		  for(int i=0;i<n;i++){
			 for(int j=0;j<n;j++){
				d[0][i][j]=min(d[0][i][j],d[0][i][k]+d[0][k][j]);
				d[1][i][j]=min(d[1][i][j],d[1][i][k]+d[1][k][j]);
			 }
		  }
	   }
	   
	   int now,z;
	   scanf("%d",&r);
	   scanf("%d",&now); now--;

	   fill(dp[0],dp[1001],INF);
	   dp[0][now]=0;
	    
	   for(int i=0;i<r-1;i++){
		   scanf("%d",&z); z--;
		   
		   for(int j=0;j<n;j++){
			   dp[i+1][j]=min(dp[i+1][j],dp[i][j]+d[1][now][z]);
			   for(int k=0;k<n;k++){
				   // 
				   dp[i+1][k]=min(dp[i+1][k],dp[i][j]+d[1][now][j]+d[0][j][k]+d[1][k][z]);
			   }
			   
			   
		   }
		   now=z;
	   }


/*
	   //int res=INF;
	   for(int i=1;i<r;i++){
		  for(int j=0;j<n;j++){
						    
			 for(int k=0;k<n;k++){
				dp[i][k]=min(dp[i][k],dp[i-1][j]+d[1][z[i-1]][j]+d[0][j][k]+d[1][k][z[i]]);
				//if(i==r-1 && res>dp[i][k]) res=dp[i][k];
			 }
			 dp[i][j]=min(dp[i][j],dp[i-1][j]+d[1][z[i-1]][z[i]]);
			 //if(i==r-1 && res>dp[i][j]) res=dp[i][j];
		  }
	   }
*/
	   printf("%d\n",*min_element(dp[r-1],dp[r]));
	    
    }
}

Measured memory_bytes: 4228
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=4005,lim=4000,mod=1e9+7;
int f[N][N],C[N][N],a[2000005],b[2000005],n,ans;

void add(int &x,int y){
	x=(x+y>=mod?x+y-mod:x+y);
}

int main(){
	read(n);
	rep(i,1,n){
		read(a[i]),read(b[i]);
		f[lim/2-a[i]][lim/2-b[i]]++;
	}
	C[0][0]=1;
	rep(i,0,lim) rep(j,0,lim){
		if(i){
			add(f[i][j],f[i-1][j]);
			add(C[i][j],C[i-1][j]);
		}
		if(j){
			add(f[i][j],f[i][j-1]);
			add(C[i][j],C[i][j-1]);
		}
	}
	rep(i,1,n) add(ans,f[lim/2+a[i]][lim/2+b[i]]);
	rep(i,1,n) ans=(ans+mod-C[a[i]+a[i]][b[i]+b[i]])%mod;
	ans=(ll)ans*(mod/2+1)%mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 131712
#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 x;
    cin >> x;

    cout << !x << endl;
}


Measured memory_bytes: 3628
#include <stdio.h>
int main(void){
    int N,a,b,c,i;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d %d %d",&a,&b,&c);
        if(a*a+b*b==c*c || b*b+c*c==a*a || c*c+a*a==b*b){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}


Measured memory_bytes: 2028
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int a[maxn];

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int main(){
	int n=read(),k=read();
	printf("%d\n",k==1?0:n-k);
}

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

int main() {
	int n; cin >> n;
	int64_t x[n], y[n];
	for(int i = 0; i < n; ++i) cin >> x[i] >> y[i];
	int64_t ans;
	// ちがう
	{
		int64_t rmax = 0, rmin = 1e9, bmax = 0, bmin = 1e9;
		for(int i = 0; i < n; ++i) {
			rmax = max(rmax, min(x[i], y[i]));
			rmin = min(rmin, min(x[i], y[i]));
			bmax = max(bmax, max(x[i], y[i]));
			bmin = min(bmin, max(x[i], y[i]));
		}
		ans = (rmax - rmin) * (bmax - bmin);
	}
	// おなじ
	{
		int64_t rmax = 0, rmin = 1e9;
		pair<int64_t, int64_t> p[n];
		multiset<int64_t> b;
		for(int i = 0; i < n; ++i) {
			p[i] = {min(x[i], y[i]), max(x[i], y[i])};
			b.insert(min(x[i], y[i]));
			rmax = max(rmax, max(x[i], y[i]));
			rmin = min(rmin, min(x[i], y[i]));
		}
		sort(p, p + n);
		int64_t bdiff = *b.rbegin() - *b.begin();
		for(int i = 0; i < n; ++i) {
			int64_t xx, yy; tie(xx, yy) = p[i];
			int64_t bmax = *b.rbegin();
			// 絶対変える
			if(yy <= bmax) {
				b.erase(b.find(xx));
				b.insert(yy);
				int64_t bmin = *b.begin();
				bdiff = (bmax - bmin);
			// 変えないかも
			} else {
				bmax = yy;
				b.erase(b.find(xx));
				b.insert(yy);
				int64_t bmin = *b.begin();
				// 変える
				if((bmax - bmin) < bdiff) {
					bdiff = (bmax - bmin);
				// 変えない
				} else {
					b.erase(b.find(yy));
					b.insert(xx);
				}
			}
		}
		ans = min(ans, (rmax - rmin) * bdiff);
	}
	cout << ans << '\n';
	return 0;
}



Measured memory_bytes: 15872
#include <iostream>

using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;
    int left=n%k;
    if(left==0)
    {
        cout<<0;
        return 0;
    }
    cout<<1;
    /*
    int distro=n/k;
    left=k-left;
    distro++;
    cout<<abs(distro-left);*/
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

var (
	finv, inv, fac [MAX]int
)

func COM(n, k int) int {
	if n < k {
		return 0
	}
	if n < 0 || k < 0 {
		return 0
	}
	return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
}

func init() {
	fac[0] = 1
	fac[1] = 1
	finv[0] = 1
	finv[1] = 1
	inv[1] = 1
	for i := 2; i < MAX; i++ {
		fac[i] = fac[i-1] * i % MOD
		inv[i] = MOD - inv[MOD%i]*(MOD/i)%MOD
		finv[i] = finv[i-1] * inv[i] % MOD
	}
}

const (
	MOD = 1000000007
	MAX = 510000
)

func ModAdd(a, b int64) int64 {
	return (a + b) % MOD
}

func ModMul(a, b int64) int64 {
	return a * b % MOD
}

func ModSub(a, b int64) int64 {
	r := (a%MOD - b%MOD) % MOD
	if r < 0 {
		r += MOD
	}
	return r
}

func ModDiv(a, b int64) int64 {
	return a % MOD * ModInv(b) % MOD
}

func ModPow(a, n int64) int64 {
	var r int64 = 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return r
}

func ModInv(a int64) int64 {
	var b, u, v int64 = MOD, 1, 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= MOD
	if u < 0 {
		u += MOD
	}
	return u
}

type Q struct {
	value int
	index int
	A, B  int
}

type QS []*Q

func (p QS) Len() int           { return len(p) }
func (p QS) Less(i, j int) bool { return p[i].value > p[j].value }
func (pq QS) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *QS) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Q)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *QS) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func FactoredPrimeNumber(num int) map[int]int {
	m := map[int]int{}
	return factor(m, num, 2)
}

func factor(result map[int]int, num, pnum int) map[int]int {
	if pnum*pnum > num {
		if num != 1 {
			result[num] += 1
		}
		return result
	}

	if num%pnum == 0 {
		num /= pnum
		result[pnum]++
	} else {
		pnum++
	}
	return factor(result, num, pnum)
}

func GCD(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func LCM(a, b int64) int64 {
	return a * b / GCD(a, b)
}

type Po struct {
	i       int
	cnt     int
	counter int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	N, _ := strconv.Atoi(sc.Text())
	B := make([]int, N)
	BM := make(map[int]int)

	for i := 0; i < N; i++ {
		sc.Scan()
		s := strings.Split(sc.Text(), " ")
		a, _ := strconv.Atoi(s[0])
		b, _ := strconv.Atoi(s[1])
		B[i] = b
		BM[b] += a
	}
	sort.Ints(B)
	ok := true
	sum := 0
	for _, b := range B {
		tasks := BM[b]
		sum += tasks
		if sum > b {
			ok = false
			break
		}
		delete(BM, b)
	}
	if ok {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func Reverse(runes []rune) []rune {
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return runes
}


Measured memory_bytes: 26368
#include <cstdio>
using namespace std;

#define LV(x) (17*(x%2)+3*(x%3)+19)

int main()
{
	int t[100],tb[17],sn=0,time=0;
	for(int i=0; i<17; i++) tb[i]=-1;
	for(int i=0; i<100; i++) t[i]=-1;
	

	while(sn<=100)
	{
		for(int i=0; i<17; i++)
		{
			if(tb[i]==-1) continue;
			if(time>=LV(tb[i])+t[tb[i]]) tb[i]=-1;
		}
		for(int i=sn; i<=time/5; i++)
		{
			int sp=-1,cnt=0;
			for(int j=0; j<17; j++)
			{
				if(tb[j]==-1)
				{
					if(sp==-1) sp=j;
					cnt++;
				}
				else
				{
					if(i%5==1&&cnt>=5) break;
					if(i%5!=1&&cnt>=2) break;
					
					cnt=0;
					sp=-1;
				}
			}
			
			if(i%5==1&&cnt>=5)
			{
				for(int j=0; j<5; j++)
					tb[sp+j]=i;
					
				t[i]=time;
				sn++;
			}
			else if(i%5!=1&&cnt>=2)
			{
				for(int j=0; j<2; j++)
					tb[sp+j]=i;
					
				t[i]=time;
				sn++;
			}
			else break;
		}
		time++;
	}
	
	int N;
	while(scanf("%d", &N) != EOF)
		printf("%d\n", t[N]-5*N);
}

Measured memory_bytes: 0
#include <stdio.h>
int main(){
  int a,i;
  long long b,c,d,j;
  scanf("%d",&a);
  if(a==2){
    scanf("%lld %lld",&b,&c);
    if(b>c)i=c;
    else i=b;
    for(j=1;j<=i;j++)if(b%j==0&&c%j==0)printf("%lld\n",j);
  }else {
    scanf("%lld %lld %lld",&b,&c,&d);
    if(b<c&&b<d)i=b;
    if(c<b&&c<d)i=c;
    if(d<c&&d<b)i=d;
    for(j=1;j<=i;j++)if(b%j==0&&c%j==0&&d%j==0)printf("%lld\n",j);
  }
  return 0;
}

Measured memory_bytes: 1028