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

int N, M, K;
vector<vector<vector<int>>> rV;
int utod[100];
int sD[100];
int dist[1<<16];

int bfs(){
    memset(dist, -1, sizeof(dist));
    queue<int> que;
    
    dist[0] = 0;
    que.push(0);
    
    while(!que.empty()){
        int s = que.front(); que.pop();
        if(s == (1<<M)-1)
            return dist[s];
        
        for(int i=0; i<K; i++){
            int t = 0;
            for(int u=0; u<N; u++){
                if(!sD[u]){
                    // light
                    for(auto v: rV[u][i])
                        t |= 1<<v;
                }else{
                    // dark
                    if(((s>>utod[u]) & 1) == 0)
                        continue;
                    for(auto v: rV[u][i])
                        t |= 1<<v;
                }
            }
            if(dist[t] == -1){
                dist[t] = dist[s] + 1;
                que.push(t);
            }
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M >> K;
    
    for(int i=0; i<M; i++){
        int d;
        cin >> d; d--;
        utod[d] = i;
        sD[d] = true;
    }
    rV.resize(N);
    for(int i=0; i<N; i++)
        rV[i].resize(K);
    
    for(int i=0; i<N; i++){
        for(int j=0; j<K; j++){
            int v;
            cin >> v; v--;
            if(!sD[i])
                continue;
            rV[v][j].push_back(utod[i]);
        }
    }
    
    cout << bfs() << endl;
    return 0;
}

Measured memory_bytes: 3700
if __name__ == "__main__":
    x, y = map(int, input().split())

    if x == 1 and y == 1:
        print(1000000)
    else:
        xc = 400000 - x * 100000 if x <= 3 else 0
        yc = 400000 - y * 100000 if y <= 3 else 0
        print(xc + yc)


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	cout << *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end()) << endl;
}

Measured memory_bytes: 256
def count(s,n,i,j):
    if s[i][j]=='#':
        n[i][j]='#'
    else:
        count=0
        for a in range(3):
            for b in range(3):
                if (0<=i-1+a<=h-1)and(0<=j-1+b<=w-1):
                    if s[i-1+a][j-1+b]=='#':
                        count+=1
        n[i][j]=str(count)


h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))
n=s
for i in range(h):
    for j in range(w):
        count(s,n,i,j)
for i in range(h):
    print(''.join(s[i]))

            


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

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

int n,m,x;
int v[12][12];
int c[12];

int Rec(int i,int j,int w[]){
  if(i == n){
    for(int k = 0; k < m; ++k){
      if(w[k] < x) return 1001001001;
    }
    return j;
  }
  int ret = 1001001001;
  for(int k = 0; k < m; ++k){
    w[k] += v[i][k];
  }
  ret = min(ret,Rec(i+1,j+c[i],w));
  for(int k = 0; k < m; ++k){
    w[k] -= v[i][k];
  }
  ret = min(ret,Rec(i+1,j,w));
  return ret;
}

int main(){
  cin >> n >> m >> x;
  for(int i = 0; i < n; ++i){
    cin >> c[i];
    for(int j = 0; j < m; ++j){
      cin >> v[i][j];
    }
  }
  int w[12] = {};
  int ans = Rec(0,0,w);
  if(ans == 1001001001)ans = -1;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

ll A[100000];
int bitcount[40];

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

	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		for (int j = 0; j < 40; j++)
		{
			if (A[i] & (1LL << j)) bitcount[j]++;
		}
	}

	ll ans = 0;
    bool f = true;
	for (int i = 39; i >= 0; --i)
	{
        if (f)
        {
          if (K & (1LL << i))
          {
              if (bitcount[i] * 2 < N) 
                ans += (1LL << i);
              else
                f = false;              
          }
        }
        else
        {
              if (bitcount[i] * 2 < N) ans += (1LL << i);
        }
	}

	ll ret = 0;
	for (int i = 0; i < N; i++)
	{
		ret += (ans ^ A[i]);
	}

	cout << ret << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
signed main(){
    int n,k;
    cin>>n>>k;
    double ans=0;
    for(int i=0;i<n;i++){
        double l=(double)1/n;
        int c=i+1;
        while(1){
            if(c>=k)break;
            c*=2;
            l*=(double)1/2;
        }
        ans+=l;
    }
    printf("%.15f",ans);
    return 0;
}









Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define REP(n) for(int i = 0; i < n; i++)
#define all(p) p.begin(), p.end()
#define count_1(p) __builtin_popcountll(p)
#define count_0(p) __builtin_ctzll(p)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
template<class X=int>inline X min(X a,X b,X c){return min(min(a,b),c);}
template<class X=int>inline X min(X a,X b,X c,X d){return min(min(a,b,c),d);}
template<class X=int> inline X max(X a,X b,X c){return max(max(a,b),c);}
template<class X=int> inline X max(X a,X b,X c,X d){return max(max(a,b,c),d);}
template<class X=int> inline X mid(X s,X e){return (s+(e-s)/2);}
template<class X=int> inline X len(X s,X e){return (e-s+1);}
const int MOD = 1e9 + 7;
const int INF = 987654321;
const bool TESTCASES = 0;
const bool CODEJAM = 0;

void solve() {
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(s[i - 1] == t[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	string ans;
	int i = n, j = m;
	while(i > 0 and j > 0) {
		if(s[i - 1] == t[j - 1]) {
			ans += s[i - 1];
			i--; j--;
		}
		else {
			if(dp[i - 1][j] > dp[i][j - 1])
				i--;
			else
				j--;
		}
	}
	reverse(all(ans));
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int T = 1;
	if(TESTCASES) cin >> T;
	for(int t = 1; t <= T; t++) {
		if(CODEJAM) cout << "Case #" << t << ": ";
		solve();
	}
	return 0;
}


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

int main()
{
	int i, ret;
	int N, M;
	int *H;
	int *pair_max;
	int A;
	int B;
	int count;

	ret = scanf("%d %d", &N, &M);

	H = (int *) malloc(sizeof(int)*N);
	pair_max = (int *) malloc(sizeof(int)*N);

	for (i = 0; i < N; i++)
		pair_max[i] = 0;
	
	for (i = 0; i < N; i++) {
		ret = scanf(" %d", &H[i]);
		// fprintf(stderr, "%d ", H[i]);
	}
	// fprintf(stderr, "\n");
	
	for (i = 0; i < M; i++) {
		ret = scanf(" %d %d\n", &A, &B);
		// fprintf(stderr, "%d %d\n", A, B);
		pair_max[A-1] = (pair_max[A-1] < H[B-1])? H[B-1]:pair_max[A-1];
		pair_max[B-1] = (pair_max[B-1] < H[A-1])? H[A-1]:pair_max[B-1];
	}
	count = 0;
	for (i = 0; i < N; i++) {
		//fprintf(stderr, "H[%d]: %d pair_max[%d]: %d\n", i, H[i], i, pair_max[i]);
		if (H[i] > pair_max[i]) {
			count++;
			//	fprintf(stderr, "i: %d \n", i);
		}
	}
	printf("%d\n",count);
	fflush(stdout);
	free(H);
	free(pair_max);
	return EXIT_SUCCESS;
}


Measured memory_bytes: 2228
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> a(3 * n);
    for (int i = 0; i < 3 * n; i++)cin >> a[i];

    vector<ll> front(3 * n);
    priority_queue<int, vector<int>, greater<>> frontQue;
    for (int i = 0; i < 3 * n; i++) {
        if (i > 0)front[i] = front[i - 1];
        front[i] += a[i];

        frontQue.push(a[i]);
        if (i >= n) {
            front[i] -= frontQue.top();
            frontQue.pop();
        }
    }
    vector<ll> back(3 * n);
    priority_queue<int> backQue;
    for (int i = 3 * n; i > 0; i--) {
        if (i < 3 * n)back[i - 1] = back[i];
        back[i - 1] += a[i - 1];

        backQue.push(a[i - 1]);
        if (i <= 2 * n) {
            back[i - 1] -= backQue.top();
            backQue.pop();
        }
    }

    ll ret = -1145141919810364364;
    for (int i = n; i <= 2 * n; i++) ret = max(ret, front[i - 1] - back[i]);
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 7288
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(i,x) for(auto &i:x)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define pii pair<int,int>
#define fi first
#define se second
#define batbit(i,x) (x|(1ll<<i))
#define getbit(i,x) ((x>>i)&1)

const int mn=200010;
int n,a[mn],s[mn],s1[mn],res=LLONG_MAX;

main()
{
    cin >> n;
    forinc(i,1,n) cin >> a[i];
    forinc(i,1,n) s[i]=s[i-1]+a[i];
    fordec(i,n,1) s1[i]=s1[i+1]+a[i];
    forinc(i,1,n-1)
    {
        res=min(res,abs(s[i]-s1[i+1]));
    }
    cout << res;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,l;
  cin >> n >> l;
  string a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a,a+n);
  for(int i = 0; i < n; i++) {
    cout << a[i];
  }
  cout << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1), c(n);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i < n; i++) cin >> c[i];

    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans += b[a[i]];
        if(i-1 >= 0 && a[i-1]+1 == a[i]) ans += c[a[i-1]];
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
   int n;
   int temp=0;
   int co = 0;
   cin>>n;
 for(int i=0;i<n;++i){
       cin>>temp;
       if(temp%2==1&&i%2==0){
           co++;
       }
 }
 cout<<co;
    return 0;
}

Measured memory_bytes: 3584
import sys
N, M = map(int, input().split())

WA_counts = [0] * N
AC_list = [False] * N
for i in sys.stdin:
    p, S = i.split()
    p = int(p) - 1
    if S == 'WA' and not AC_list[p]:
        WA_counts[p] += 1
    elif S == 'AC':
        AC_list[p] = True
for i in range(len(AC_list)):
    if not AC_list[i]:
        WA_counts[i] = 0

print('{} {}'.format(sum(AC_list), sum(WA_counts)))

Measured memory_bytes: 4724
use std::cmp::max;
use std::collections::VecDeque;
use std::cmp::min;
use core::ops::Bound::Excluded;
use core::ops::Bound::Included;
use std::collections::BTreeSet;
use std::cmp::Ordering;
use std::fmt::Debug;

fn read_line() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).expect("No Line");
    buffer
}
fn read_lines<R, T: Fn(&str)->R> (count: usize, transformer: T) -> Vec<R> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(transformer(buffer.trim()));
        buffer.clear();
    }
    vec
}
fn read_value<T: std::str::FromStr>() -> T {
    read_line().trim().parse().ok().unwrap()
}
fn read_values<T: std::str::FromStr>() -> Vec<T> {
    read_line().trim().split(' ').map(|x| x.parse().ok().expect("Can't Parse")).collect::<Vec<T>>()
}
fn read_tabulate<T: std::str::FromStr>(count: usize) -> Vec<T> {
    let mut buffer = String::new();
    let mut vec = Vec::with_capacity(count);
    for _ in 0 .. count {
        std::io::stdin().read_line(&mut buffer).expect("No Line");
        vec.push(buffer.trim().parse().ok().expect("Can't Parse"));
        buffer.clear();
    }
    vec
}
macro_rules! define {
    () => {};
    ($($token:tt)*) => {
        let mut iter = read_values::<String>().into_iter();
        define_iter!(iter, $($token)*);
    };
}
macro_rules! define_iter {
    ($iter:expr) =>{};
    ($iter:expr,) =>{};
    ($iter:expr, $id:ident:$t:tt $($tail:tt)*) => {
        let $id: $t = $iter.next().unwrap().parse().ok().expect("Can't Parse");
        define_iter!($iter, $($tail)*);
    };
    ($iter:expr, mut $id:ident:$t:tt $($tail:tt)*) => {
        let mut $id: $t = $iter.next().unwrap().parse().ok().expect("Can't Parse");
        define_iter!($iter, $($tail)*)
    };
}
macro_rules! freeze {
    ($($id:ident), *) => {
        $(let $id = $id;)*
    };
}
struct KeyValue<K, V> {
    key: K,
    value: V
}
impl <K: PartialOrd, V> PartialEq for KeyValue<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.key.eq(&other.key)
    }
}
impl <K: PartialOrd, V> Eq for KeyValue<K, V> {}
impl <K: PartialOrd, V> PartialOrd for KeyValue<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.key.partial_cmp(&other.key)
    }
}
impl <K: PartialOrd, V> Ord for KeyValue<K, V> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.key.partial_cmp(&other.key).ok_or("Can't Compare").unwrap()
    }
}
fn main() {
    define! {
        n: usize
    }
    let cards = read_values::<usize>();
    let mut count = vec![0; 100001];
    for c in cards {
        count[c] += 1;
    }
    let mut doubled = 0;
    for c in count {
        if c > 0 {
            doubled += c - 1;
        }
    }
    println!("{}", n - (doubled + (doubled & 1)));
}


Measured memory_bytes: 3540
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
s = "abcdefghijklmnopqrstuvwxyz"

val = [-1]*100

i = 0
tmp = n - 1
while(True):
    val[i] = tmp % 26
    tmp = tmp // 26
    tmp = tmp - 1
    i += 1
    if(tmp < 0):
        break

result = ''
i = 0
while(val[i] >= 0):
    if(i == 0):
        result += s[val[i]]
    else:
        result += s[val[i]]
    i += 1

result = result[::-1]
print(result)

Measured memory_bytes: 61980
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  string s;
  cin >> s;
  int l=0;int r=s.size()-1;
  int ans = 0;
  while(l<r){
    if(s.at(l) == s.at(r)){
      ++l; --r;
    }else{
      if(s.at(l) != 'x' && s.at(r) != 'x'){
        ans = -1;
        break;
      }else if(s.at(l) == 'x'){
        ans ++; 
        l++;
      }else{
        ans ++; 
        r--;
      }
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int y = sc.nextInt();
		y= y/1000;
		int a=0;
		int b=0;
		int c=0;
		int flag=0;
		int result=0;
		for(a=y/10; a>=0; a--) {
			for(b=y/5; b>=0; b--) {
				c=n-a-b;
				if(c<0) {
					continue;
				}
				result = 10*a + 5*b +c;
				if(result==y) {
					flag=1;
					break;
				}
			}
			if(flag==1) {
				break;
			}
		}
			if(flag==0) {
				a=-1;
				b=-1;
				c=-1;
			}
			System.out.println(a+" "+b+" "+c);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

signed main() {
  int K, S; cin >> K >> S;
  
  int ans = 0;
  rep(x, K+1) rep(y, K+1) {
    int z = S-x-y;
    if(z >= 0 && z <= K) ans++;
  }
  cout << ans << endl;
  


}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
long long N;
int main(){
	cin>>N;
	int tmp=N%10;
	if(tmp==2||tmp==4||tmp==5||tmp==7||tmp==9){
		cout<<"hon"<<'\n';
	}else if(tmp==3){
		cout<<"bon"<<'\n';
	}else if(tmp==0||tmp==1||tmp==6||tmp==8){
		cout<<"pon"<<'\n';
	}
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

class UnionFind{
private:
  vector<ll> Parent; 
 public:
  UnionFind(ll N){
    Parent = vector<ll>(N, -1);
  }
  
  ll root(ll A){
    if(Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }
  
  ll size(ll A){
    return -Parent[root(A)]; 
  }
  
  bool connect(ll A, ll B){
    A = root(A);
    B = root(B);
    if(A == B){
      return false;
    }
    if(size(A) < size(B)) swap(A, B);
    Parent[A] += Parent[B];
    Parent[B] = A;
    return true;
  }
  
  bool isSame(ll A, ll B){
    return root(A) == root(B);
  }
};

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  vll p(n);
  rep(i,n) cin>>p[i], p[i]--;
  UnionFind uf(n);
  rep(i,m){
    ll a,b; cin>>a>>b;
    a--,b--;
    uf.connect(a,b);
  }
  ll ans=0;
  rep(i,n){
    if(uf.isSame(p[i],p[p[i]])) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]

class Util():
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)

N,X = cin.mapInt()
A = cin.mapInt()
A.append(X)

def solve():
    A.sort()
    subs = [0] * (N)
    for i in range(N):
        subs[i] = A[i + 1] - A[i]
    ans = subs[0]
    for i in range(1,N):
        ans = Math.gcd(ans,subs[i])
    return ans
print(solve())


Measured memory_bytes: 62576
s=input()
if s=="SUN":
  print(7)
elif s=="MON":
  print(6)
elif s=="TUE":
  print(5)
elif s=="WED":
  print(4)
elif s=="THU":
  print(3)
elif s=="FRI":
  print(2)
elif s=="SAT":
  print(1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >>N;
  string S;
  cin >>S;
  int count=1;
  for(int i=0;i<N-1;i++){
    if(S[i]!=S[i+1])count++;
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <map>
#include <cmath>
#include <bitset>
#include <deque>
#define MAX_N 100
#define MAX_T 200
#define INF (1LL<<31)
#define fst first
#define snd second
typedef long long ll;
typedef std::pair<int,int> ii;
using namespace std;

ll gcd(ll x,ll y){
  if(y>x)swap(x,y);
  if(y==0)return x;
  else return gcd(y,x%y);
}
int main(){
  ll n;
  ll T, t;
  cin>>n;
  cin>>T;
  for(int i=1;i<n;i++){
    cin>>t;
    t/=gcd(T,t);
    T*=t;
  }
  cout<<T<<endl;
  return 0;
}


Measured memory_bytes: 256
#[test]
fn test_solve() {
    assert_eq!(solve("6 1 2 2\n2 1 1 3 0 2\n"), "5\n");
    assert_eq!(solve("6 1 5 2\n2 1 1 3 0 2\n"), "3\n");
    assert_eq!(solve("10 4 8 5\n7 2 3 6 1 6 5 4 6 5\n"), "8\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let m: usize = sc.read();
    let v: usize = sc.read();
    let p: usize = sc.read();
    let mut a: Vec<usize> = (0..n).map(|_| sc.read()).collect();
    a.sort_by(|a, b| b.cmp(a));

    let border = a[p - 1];
    let ans = if v <= p {
        a.iter().take_while(|&a| a + m >= border).count()
    } else {
        let v = v - p;
        1 + bis_usize(p - 1, n, |i| {
            let ceiling = a[i] + m;
            if ceiling < border {
                return false;
            }
            let mut cnt = m * v;
            for j in p-1..n {
                if j == i || a[j] > ceiling {
                    continue;
                }
                let d = if ceiling - a[j] < m {
                    ceiling - a[j]
                } else {
                    m
                };
                if d >= cnt {
                    return true;
                }
                cnt -= d;
            }
            false
        })
    };

    format!("{}\n", ans)
}

fn bis_usize<P>(t: usize, f: usize, eval: P) -> usize
where
    P: Fn(usize) -> bool,
{
    if t > f {
        if t - f == 1 {
            return t;
        }
    } else if f - t == 1 {
        return t;
    }
    let m = (t + f) >> 1;
    if eval(m) {
        bis_usize(m, f, eval)
    } else {
        bis_usize(t, m, eval)
    }
}

fn main() {
    let mut buf = String::new();
    use std::io;
    use std::io::{Read, Write};
    io::stdin().read_to_string(&mut buf).unwrap();
    io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}

struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.get().chars().collect()
    }
}


Measured memory_bytes: 6396
#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset> 
using namespace std;
typedef long long ll;
ll k,n,a[200005];
ll mod=1000000000+7;
int main(void)
{
	scanf("%lld%lld",&n,&k);
	ll a0=0,a1=0,a2=0;
	for(ll i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		if(a[i]<0) a0++;
		else if(a[i]==0) a1++;
		else a2++;
	}
	sort(a,a+n);
	ll ans=1;
//	printf("%lld %lld %lld\n",a0,a1,a2);
	if(k%2==1)
	{
		if(a2==0)
		{
			for(ll i=0;i<k;i++)
			{
				ans*=a[n-i-1];
				ans%=mod;
			}
			printf("%lld",(ans%mod+mod)%mod);
			return 0;
		}
		ans=a[n-1];
		n--;
		a2--;
		k--;
	}
	ll st=0,ed=n-1;
	while(true)
	{
		if(k==0) break;
		if(a2>1&&a0>1)
		{
			if(a[st]*a[st+1]>a[ed]*a[ed-1])
			{
				ans*=a[st]*a[st+1]%mod;
				ans%=mod;
				st+=2;
				a0-=2;
				k-=2;
			}
			else
			{
				ans*=a[ed]*a[ed-1]%mod;
				ans%=mod;
				ed-=2;
				a2-=2;
				k-=2;
			}
		}
		else if(a2>1)
		{
			ans*=a[ed]*a[ed-1]%mod;
			ans%=mod;
			ed-=2;
			a2-=2;	
			k-=2;		
		}
		else if(a0>1)
		{
			ans*=a[st]*a[st+1]%mod;
			ans%=mod;
			st+=2;
			a0-=2;			
			k-=2;
		}
		else
		{
			for(ll i=ed;i>ed-k;i--)
			{
				ans*=a[i];
				ans%=mod;
			}
			break;
		}
//		printf("%lld %lld %lld %lld\n",ans,a0,a2,k);
	}
	printf("%lld",(ans%mod+mod)%mod);
}

Measured memory_bytes: 5264
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;

typedef long long LL;
const int S = 2155;
const int N = 1e5 + 10;
struct data {
	int cnt; LL val;
	data(int _cnt = 0, LL _val = 0) {cnt = _cnt, val = _val;}
};
int n, ans, tot, top, is[S], pri[N]; LL a[N]; map <LL, data> mp;

inline int max(int a, int b) {return a > b ? a : b;}
inline int min(int a, int b) {return a < b ? a : b;}
template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + (LL)ch-'0', ch = getchar();
	x *= f;
}

inline void init(int n) {
	for (int i = 2; i <= n; ++i) {
		if (!is[i]) pri[++tot] = i;
		for (int j = 1; j <= tot && i * pri[j] <= n; ++j) {
			is[i * pri[j]] = 1;
			if (i % pri[j] == 0) break;
		}
	}
}

int main() {
	int p, cnt; LL x, g, x1, x2;
	in(n), init(S - 1);
	for (int i = 1; i <= n; ++i) {
		in(x), x1 = x2 = 1;
		for (int i = 1; i <= tot; ++i) {
			p = pri[i];
			if (x % p) continue;
			for (cnt = 0; x % p == 0;) x /= p, ++cnt;
			cnt %= 3;
			if (!cnt) continue;
			if (cnt == 1) x1 *= p, x2 *= p * p;
			else x1 *= p * p, x2 *= p;
		}
		if (x > 1) {
			x1 *= x;
			g = sqrtl(x);
			if (g * g == x) x2 *= g;
			else {
				if (x > 100000) {++ans; continue;}
				x2 *= x * x;
			}
		}
		if (mp.count(a[++top] = x1)) ++mp[x1].cnt;
		else mp[x1] = data(1, x2);
	}
	sort(a + 1, a + top + 1);
	n = unique(a + 1, a + top + 1) - a - 1;
	for (int i = 1; i <= n; ++i) {
		x1 = a[i], x2 = mp[x1].val;
		if (x1 == x2) {++ans; continue;}
		if (x2 < x1) {
			if (mp.count(x2)) continue;
			ans += mp[x1].cnt;
		} else {
			if (!mp.count(x2)) ans += mp[x1].cnt;
			else ans += max(mp[x1].cnt, mp[x2].cnt);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 6272
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007ll
#define INF 1000000000
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// まずは全探索
int main() {
cin.tie(0);
ios::sync_with_stdio(false);

// ダメージ H にする最少回数
int N; 
int64_t H, maxa = 0;
cin >> N >> H;
vector<pair<int64_t, int64_t>> ba(N);
rep(i, 0, N) {
    cin >> ba[i].second >> ba[i].first;
    maxa = max(maxa, ba[i].second);
}
sort(ALL(ba), greater<pair<int64_t, int64_t>>());

int64_t cnt = 0;
for (int i = 0; ba[i].first > maxa && H > 0 && i < N; ++i) {
    H -= ba[i].first;
    ++cnt;
}
if (H <= 0){
    cout << cnt << "\n";
    return 0;
}
else cnt += (H + maxa - 1)/ maxa;

cout << cnt << "\n";

}

// 境界，出力文字列 チェック



Measured memory_bytes: 1792
#include<stdio.h>
#define N 1010

int main(void){
  int i,num;
  char ch[N];

  for(i=0;scanf("%c",&ch[i])==1;i++){}
  num=i;
  for(i=0;i<num;i++){
    if(ch[i]=='a'
        && ch[i+1]=='p'
        && ch[i+2]=='p'
        && ch[i+3]=='l'
        && ch[i+4]=='e'){
      ch[i]='p';
      ch[i+1]='e';
      ch[i+2]='a';
      ch[i+3]='c';
      ch[i+4]='h';
    }else if(ch[i]=='p'
        && ch[i+1]=='e'
        && ch[i+2]=='a'
        && ch[i+3]=='c'
        && ch[i+4]=='h'){
      ch[i]='a';
      ch[i+1]='p';
      ch[i+2]='p';
      ch[i+3]='l';
      ch[i+4]='e';
    }
  }
  for(i=0;i<num;i++){
    printf("%c",ch[i]);
  }
  return 0;
}

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

int main() {
    string S , T; 
    cin >> S >> T;
    bool ans = false;
    for(int i = 0; i < S.size(); i++) {
        if(S == T) {
            ans = true;
            break;
        }
        S = S.back() + S.substr(0,S.size() - 1);
    }
    if(ans) {
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll a,b,c,k;
  	cin>>a>>b>>c>>k;
  	if(k<=a)
      cout<<k;
 	else
      if(k<=(a+b))
        cout<<a;
  	else
      cout<<a-(k-a-b);
      
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>

int main(){
    int32_t N, M;
    std::cin >> N >> M;

    // find common range. Max Li to Min Ri
    int32_t maxL = 0;
    int32_t minR = N;
    int32_t L = 0, R = 0;
    for(int32_t i = 0; i < M; i++){
       std::cin >> L >> R;
       maxL = std::max(maxL, L);
       minR = std::min(minR, R);
    }

    int32_t res = std::max(0, minR - maxL + 1);
    std::cout << res;

    return 0;
}


Measured memory_bytes: 256
import math

N = int(input())
S = input()
mod = 10**9 + 7

left = 0
ret = 1
for i in range(len(S)):
    if S[i] == 'W':
        if left % 2 == 1:
            left += 1
        else:
            if left > 0:
                ret *= left
                ret %= mod
                left -= 1
            else:
                print(0)
                exit()
    else:
        if left % 2 == 1:
            ret *= left
            ret %= mod
            left -= 1
        else:
            left += 1

if left > 0:
    print(0)
    exit()
            
for i in range(1, N+1):
    ret *= i
    ret %= mod
print(ret)


Measured memory_bytes: 40176
#include <stdio.h>
#define EM_NUM 4000

typedef struct {
    int em_num;
    long long int uni_cost;
    long long int quantity;
    long long int total;
} Employee;

int main(void) {
    int i, j, data_num;
    
    while(1) {
        
        scanf("%d", &data_num);
        if(data_num == 0)
            break;
        
        Employee emp[4000] = {0, 0, 0, 0};
        int count = 0;
        
        for(i = 0; i < data_num; i++) {
            scanf("%d %lld %lld", &emp[i].em_num, &emp[i].uni_cost, &emp[i].quantity);
            emp[i].total += emp[i].uni_cost * emp[i].quantity;
            for(j = 0; j < i; j++) {
                if(emp[j].em_num == emp[i].em_num) {
                    emp[j].total += emp[i].total;
                    
                    emp[i].em_num   = 0;
                    emp[i].quantity = 0;
                    emp[i].uni_cost = 0;
                    emp[i].total    = 0;//ここが不安
                }
            }
        }
        for(i = 0; i < data_num; i++) {
            if(emp[i].total >= 1000000){
                count++;
                printf("%d\n", emp[i].em_num);
            }
        }
        if(count == 0)
            puts("NA");
    }
    return(0);
}

Measured memory_bytes: 744
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

typedef long long ll;

int N;
ll D[100005];
ll parent[100005];
map<ll,int> tree_sizes;

map<ll,int> D_to_old;
int new_to_old[100005];

int main() {
        cin >> N;
        for (int i=0; i<N; i++) {
                cin >> D[i];
                tree_sizes[D[i]] = 1;
                D_to_old[D[i]] = i;
                parent[i] = -1;
        }

        sort(D,D+N);

        for (int i=0; i<N; i++) {
                new_to_old[i] = D_to_old[D[i]];
        }

        ll tot_depth = 0;
        for (int i=N-1; i>=1; i--) {
                if (N - 2*tree_sizes[D[i]] <= 0) {
                        cout << "-1\n";
                        return 0;
                }

                auto new_parent = tree_sizes.find(D[i] - (N - 2*tree_sizes[D[i]]));
                if (new_parent == tree_sizes.end()) {
                        cout << "-1\n";
                        return 0;
                }

                parent[new_to_old[i]] = D_to_old[new_parent->first];
                new_parent->second += tree_sizes[D[i]];
                tot_depth += tree_sizes[D[i]];
        }

        if (D[0] != tot_depth) {
                cout << "-1\n";
                return 0;
        }

        for (int i=0; i<N; i++) {
                if (parent[i] != -1) {
                        cout << i+1 << " " << parent[i]+1 << endl;
                }
        }
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_H=500,MAX_W=500;
int H,W,d;
char col[4]={'R','Y','G','B'};
char ans[MAX_H][MAX_W+1];
void pnt(int h,int w,int c){
	for(int i=h;i<h+d;i++){
		for(int j=w-d/2;j<=w+d/2;j++){
			if(i<0 || i>=H || j<0 || j>=W)continue;
			if(abs(h-i)+abs(w-d/2-j)<d/2 ||
			abs(h+d-1-i)+abs(w+d/2-j)<d/2){
				ans[i][j]=col[(c==0 ? 2 : 3)];
			}else if(abs(h-i)+abs(w+d/2-j)<d/2 ||
			abs(h+d-1-i)+abs(w-d/2-j)<d/2){
				ans[i][j]=col[(c==0 ? 3 : 2)];
			}else{
				ans[i][j]=col[c];
			}
		}
	}
}
int main(){
	scanf("%d %d %d",&H,&W,&d);
	if(d%2){
		REP(h,H){
			REP(w,W){
				ans[h][w]=col[h%2*2+w%2];
			}
		}
	}else{
		for(int h=0;h<H;h+=d){
			int f=h/d%2;
			for(int w=d/2-1;w<W+d/2;w+=d){
//				printf("pnt %d %d %d\n",h,w,f);
				pnt(h,w,f);
				f=1-f;
			}
		}
	}
	REP(h,H){
		printf("%s\n",ans[h]);
	}
}

Measured memory_bytes: 768
n = STDIN.gets.chomp.to_i
s = STDIN.gets.chomp.chars

def predict(s, init)
  (1...(s.size - 1)).each do |i|
    if s[i] == 'o'
      if init[i]
        init[i + 1] = init[i - 1]
      else
        init[i + 1] = !init[i - 1]
      end
    else
      if init[i]
        init[i + 1] = !init[i - 1]
      else
        init[i + 1] = init[i - 1]
      end
    end
  end
  init
end

def valid?(s, result)
  a = if s[0] == 'o'
    if result[0]
      result[1] == result[-1]
    else
      result[1] != result[-1]
    end
  else
    if result[0]
      result[1] != result[-1]
    else
      result[1] == result[-1]
    end
  end

  b = if s[-1] == 'o'
    if result[-1]
      result[0] == result[-2]
    else
      result[0] != result[-2]
    end
  else
    if result[-1]
      result[0] != result[-2]
    else
      result[0] == result[-2]
    end
  end
  a && b
end

def output(result)
  result.map{|r|
    if r
      "S"
    else
      "W"
    end
  }.join('')
end

init = [true, true]
result = predict(s, init)
if valid?(s, result)
  puts output(result)
  exit
end

init = [true, false]
result = predict(s, init)
if valid?(s, result)
  puts output(result)
  exit
end

init = [false, true]
result = predict(s, init)
if valid?(s, result)
  puts output(result)
  exit
end

init = [false, false]
result = predict(s, init)
if valid?(s, result)
  puts output(result)
  exit
end
puts -1

Measured memory_bytes: 13512
#include<bits/stdc++.h>
#define mod 998244353
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::map<std::string,int>M;
int f(std::string S){
	if(M.count(S))return M[S];
	int n=S.size(),ret=f(S.substr(1,n))*(1+(S[0]=='1'))%mod;
	for(int i=1;i+i<=n;++i){
		std::string AND(S.substr(0,i));
		for(int j=i+i;j<=n;j+=i){
			for(int k=0;k<i;++k)if(S[j-i+k]=='0')AND[k]='0';
			ret=(ret+1ll*f(AND)*f(S.substr(j,n-j)))%mod;
		}
	}
	return M[S]=ret;
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	std::string S;std::cin>>S;
	M[""]=M["0"]=1,M["1"]=2;printf("%d\n",f(S));
	return 0;
}


Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define LL long long

int n,m,k;
int C[12][1005];
char s[15][1005];
int dp[12][12][1005];
vector < int > cutp;

int white( int r1, int r2, int c1, int c2 ){
	int ans = C[r2][c2] - C[r1-1][c2] - C[r2][c1-1] + C[r1-1][c1-1];
	return ans;
}

int solve( int col , int mid ){
	int last = 1;
	for ( auto it : cutp ){
		if ( white(last,it,col, mid) > k ) return false;
		last = it+1;
	}
	if ( white(last,n,col,mid) > k ) return false;
	return true;
}

int f( int col ){
	
	if ( col > m ) return 0;
	int ans = 1e8;
	int l = col, r = m;
	while ( l < r ){
		int mid = ( l + r ) / 2;
		if ( solve(col,mid+1) ) l = mid+1;
		else r = mid;
	}
	
	if ( solve(col,l) ) {
		if ( l < m ) ans = min( ans, f(l+1) + 1 );
		else ans = min( ans, f(l+1) ) ;
	}
	return ans;
}

int main(){
	
	scanf("%d%d%d",&n,&m,&k);
	for ( int i = 0; i < n; i++ ) {
		scanf("%s",&s[i]);
		for ( int j = 0; j < m; j++ ){
			C[i+1][j+1] += C[i][j+1] + C[i+1][j] - C[i][j];
			if ( s[i][j] == '1' ) C[i+1][j+1]++; 
		}
	}
	
	memset(dp,-1,sizeof(dp));
	
	int ans = 1e8;
	for ( int i = 0; i < (1<<(n-1)); i++ ){
		int tmp = 0;
		cutp.clear();
		for ( int j = 0; j < n - 1; j++ ){
			if ( (i>>j) & 1 ) cutp.pb(j+1);
		}
		tmp += f(1) + cutp.size();
//		printf("mask = %d, %d %d\n",i, tmp, cutp.size());
		ans = min( ans, tmp );
	}
	printf("%d\n",ans);
	return 0;
}


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

#define dump(x) cout << (x) << endl
#define Int int64_t
#define fi first
#define se second
 
Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

bool dp[81][81][16005];

int main() {
    Int h, w;
    cin >> h >> w;
    Int f[100][100] = {};
    for (Int i = 0; i < h; i++) {
        for (Int j = 0; j < w; j++) {
            cin >> f[i][j];
        }
    }
    for (Int i = 0; i < h; i++) {
        for (Int j = 0; j < w; j++) {
            Int x;
            cin >> x;
            f[i][j] = abs(f[i][j] - x);
        }
    }
    dp[0][0][8000 + f[0][0]] = dp[0][0][8000 - f[0][0]] = true;
    for (Int i = 0; i < h; i++) {
        for (Int j = 0; j < w; j++) {
            vector<bool> a(16005, false);
            vector<bool> b(16005, false);
            if (0 < i) {
                for (Int k = 0; k < 16000; k++) {
                    b[k] = b[k] or dp[i - 1][j][k];
                }
            }
            if (0 < j) {
                for (Int k = 0; k < 16000; k++) {
                    b[k] = b[k] or dp[i][j - 1][k];
                }
            }
            if (0 < i) {
                for (Int k = 0; k < 16000; k++) {
                    if (0 <= k - f[i][j]) {
                        a[k - f[i][j]] = a[k - f[i][j]] or b[k];
                    }
                    if (k + f[i][j] < 16000) {
                        a[k + f[i][j]] = a[k + f[i][j]] or b[k];
                    }
                }
                for (Int k = 0; k < 16000; k++) {
                    dp[i][j][k] = dp[i][j][k] or a[k];
                }
            }
            if (0 < j) {
                for (Int k = 0; k < 16000; k++) {
                    if (0 <= k - f[i][j]) {
                        a[k - f[i][j]] = a[k - f[i][j]] or b[k];
                    }
                    if (k + f[i][j] < 16000) {
                        a[k + f[i][j]] = a[k + f[i][j]] or b[k];
                    }
                }
                for (Int k = 0; k < 16000; k++) {
                    dp[i][j][k] = dp[i][j][k] or a[k];
                }
            }
        }
    }
    Int res = INF;
    for (Int i = 0; i < 16000; i++) {
        //cout << i << " " << dp[h - 1][w - 1][i] << endl;
        if (dp[h -1][w - 1][i]) {
            res = min(res, abs(8000 - i));
        }
    }
    dump(res);
    return 0;
}

Measured memory_bytes: 102656
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <limits>
#include <functional>
#include <cassert>
#include <numeric>
#include <bitset>
#include <set>

#define FOR(x,n) for(int x = 0; x < n; x++)
#define INPUT(x) scanf("%d",&x)
#define PUT(x) printf("%d\n",x)
#define DPUT(x) printf("%.15lf\n",x)
#define GET(x,y) std::get<x>(y)
#define CHMAX(x,y) x = std::max(x,y)
#define CHMIN(x,y) x = std::min(x,y)
#define SP_END (i != n - 1 ? ' ' : '\n') ;

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;
using vch = std::vector<char>;
using vvch = std::vector<vch>;
using tiii = std::tuple<int, int, int>;

const ll mod197 = 1000000007LL;
const ll INF = 10000000000LL;

const double PI11 = 3.14159265359;

const int dis[5] = { 0,1,0,-1,0 };

const int disD[4] = { 0,1,1,0 };
const int disLD[3] = { 0,1,0 };

const char disC[4] = { 'U','D','R','L' };
const char disY[4] = { -1,1,0,0 };
const char disX[4] = { 0,0,1,-1 };

int main(void) {

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

	cout << a + b + c + max({ a,b,c }) * (pow(2, k) - 1) << endl;

	return 0;
}


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

int main(){
  int K;
  string S;
  cin >> K >> S ;
  K++;
  if(S.size()<K){
    cout << S << endl;
  }else{
    for(int i=0;i<K;i++){
      
      if((i+1)==K){
        cout << "..." << endl;
      }else{ 
         cout << S.at(i);
      }
    }
  }
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main(void)
{
	int i,j;
	int n,t = 0 ,h = 0;
	char tarou[100] = {0}, hanako[100] = {0};

	scanf("%d", &n);
	for(i = 0; i < n; i++)
	{
		scanf("%s %s", tarou,hanako);

			if (strcmp(tarou,hanako) == 0)
			{
				t++;
				h++;
			}else if (strcmp(tarou,hanako) > 0)
			{
				t += 3;
			}else
			{
				h += 3;
			}
	}

	printf("%d %d\n", t,h);

	return 0;
}

Measured memory_bytes: 604
#include <stdio.h>
#include <stdlib.h>
int N,max,sum;
int main(void) {
  if(! scanf("%d",&N) )exit(0);
  while(N--) {
    int L; if(! scanf("%d",&L) )exit(0);
    if(L>max) max=L;
    sum+=L;
  }
  puts( max<sum-max ? "Yes" : "No" );
}

Measured memory_bytes: 128
"use strict";

const main = arg => {
    arg = arg.trim().split("\n");
    const K = parseInt(arg[0].split(" ")[0]);
    const S = parseInt(arg[0].split(" ")[1]);
    
    let answer = 0;
    
    for(let i=0; i<=K; i++) {
        for(let j=0; j<=K; j++) {
            let X = i;
            let Y = j;
            
            if(i + j > S) continue;
            
            if(S - (i+j) <= K) {
                // console.log("X:" + X);
                // console.log("Y:" + Y);
                
                answer++;
            }
        }
    }
    
    console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <cstdio>
#include <iostream>

using namespace std;

char map[22][22];
int h,w,cnt,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

void search(int x,int y){
	cnt++;
	map[y][x] = '#';
	for(int i = 0; i < 4; i++){
		if(map[y+dy[i]][x+dx[i]] == '.')
			search(x+dx[i],y+dy[i]);
	}
}

int main()
{	
	while(scanf("%d%d",&w,&h) && h != 0 && w != 0){
		for(int i = 1; i <= h; i++){
			scanf("%s",&map[i][1]);
		}
		for(int i = 0; i <= h+1; i++){
			map[i][0] = '#';
			map[i][w+1] = '#';
		}
		for(int j = 0; j <= w+1; j++){
			map[0][j] = '#';
			map[h+1][j] = '#';
		}
		/*
		for(int i = 0; i <= h+1; i++){
			for(int j = 0; j <= w+1; j++){
				printf("%c",map[i][j]);
			}
			printf("\n");
		}
		*/
		cnt  = 0;
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
				if(map[i][j] == '@')
					search(j,i);
			}
		}
		printf("%d\n",cnt);
	}

	return 0;
}

Measured memory_bytes: 1196
n = gets.to_i
a = gets.chomp.split.map(&:to_i)
dp = Array.new(n + 1, 0)
dp[0] = 1000
stock = 0

(n - 1).times do |i|
  if a[i + 1] > a[i]
    cnt = dp[i] / a[i]
    stock += cnt
    dp[i + 1] = dp[i] - cnt * a[i]
  elsif a[i + 1] < a[i]
    dp[i + 1] = dp[i] + stock * a[i]
    stock = 0
  else
    dp[i + 1] = dp[i]
  end
end
dp[n] = dp[n - 1] + stock * a[n - 1]
puts dp.max

Measured memory_bytes: 14324
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  ll n,sum;
  cin>>n;
  sum=0;
  ll a[n];
  ll maxi=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
    maxi=max(maxi,a[i]);
  }
  cout<<sum-maxi/2<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int INF = (int)1e9 + 7;

//---------------------------------------------------------------
// ------ graph ------ //
using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) { }
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // pqが降順のため
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
using Edges = vector<Edge>;
struct Graph {
    vector<Edges> adj;
    Graph(int n) : adj(n) { }
    int size() { return adj.size(); }
    Edges operator [] (int v) { return adj[v]; }
    void add_edge(int a, int b, Weight w = 1) { // graph
        adj[a].emplace_back(a, b, w);
        adj[b].emplace_back(b, a, w);
    }
    void add_arc(int a, int b, Weight w = 1) {  // digraph
        adj[a].emplace_back(a, b, w);
    }
};
using Array = vector<Weight>;
using Matrix = vector<Array>;

// ------ WarshallFloyd ------ //
Matrix WarshallFloyd(Graph &g) {
    int n = g.size();
    Matrix d(n, Array(n, INF));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int i = 0; i < n; i++) for (Edge &e : g[i]) {
        d[e.src][e.dst] = min(d[e.src][e.dst], e.weight);
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (d[i][k] != INF && d[k][j] != INF) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    return d;
}
//---------------------------------------------------------------

int main() {
    int n, m; scanf("%d%d", &n, &m);
    Graph g(n);
    for (int i = 0; i < m; i++) {
        int a, b, c, d;
        scanf("%d,%d,%d,%d", &a, &b, &c, &d);
        g.add_arc(a - 1, b - 1, c);
        g.add_arc(b - 1, a - 1, d);
    }
    int S, G, V, P; scanf("%d,%d,%d,%d", &S, &G, &V, &P);
    Matrix d = WarshallFloyd(g);
    int ans = V - P - d[S - 1][G - 1] - d[G - 1][S - 1];
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 2796
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main()
{
    int64_t N;
    cin >> N;
    int64_t M = N-1;
    map<int64_t,int64_t>m;
    for (int64_t i = 0; i < M; i++)
    {
        int64_t S;
        cin >> S;
        if (m.count(S) > 0) {
            m[S] = m[S] + 1;
        } else {
            m[S] = 1;
        }
    }

    for (int64_t i=1; i < N+1; i++) {
        cout << m[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 16132