akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

LLI dp[200010];

LLI power(LLI a, LLI b) { LLI res = 1; while (b > 0) { if (b & 1)res = res * a % MOD; a = a * a % MOD; b >>= 1; }return res; }

int main()
{
	cout << fixed << setprecision(10);
	LLI n, k;
	cin >> n >> k;

	LLI ans = 0;

	for (LLI i = k; i <= n; i++)
	{
		LLI a = i * (n * 2 - (i - 1)) / 2;
		LLI b = (i * (i - 1) / 2);
		a %= MOD;
		b %= MOD;
		ans = (((ans + a) % MOD) + (MOD - b + 1)) % MOD;
	}
	cout << ans + 1;
	return 0;
}

Measured memory_bytes: 3636
import math
N, P = map(int, input().split())
D = {}
sqrt_p = int(math.sqrt(P))
for i in range(2, sqrt_p + 2):
    while P % i == 0:
        if i not in D:
            D[i] = 1
        else:
            D[i] += 1
        P //= i
if P != 1:
    if P not in D:
        D[P] = 1
    else:
        D[P] += 1

# print(D)
ans = 1
for d in D:
    if D[d] >= N:
        ans *= (d ** (D[d] // N))
print(ans)


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

using namespace std;

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

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

struct Segtree{
	typedef int sgT;
	vector<sgT> seg;
	int nbn; sgT INF;
	void init(int n){
		for(nbn=1; nbn<n+2; nbn<<=1); INF=1<<29; // min:+inf,max:-inf
		seg.assign(nbn*2, INF);
	}
	sgT comp(sgT l, sgT r){return min(l, r);}  //min<->max
	void update(int k,sgT x){
		k+=nbn-1; seg[k]=x;
		while(k>0){ k=(k-1)/2; seg[k]=comp(seg[k*2+1],seg[k*2+2]); }
	}
	sgT query2(int a,int b,int l,int r,int k){
		if(b<=l||r<=a) return INF;
		if(a<=l&&r<=b) return seg[k];
		return comp(query2(a,b,l,(l+r)/2,k*2+1), query2(a,b,(l+r)/2,r,k*2+2));
	}
	sgT query(int a,int b){ return query2(a,b,0,nbn,0); }
	sgT get(int a){return seg[nbn+a-1];}  // =query(a,a+1)

	int getpos(int l, int r, sgT v){
		int lo=l-1, hi=r;
		while(hi - lo >1){
			int md = (hi + lo) >> 1;
			if( query(lo, md+1) == v ) hi = md; else lo = md; 
		}
		return hi;
	}
};

struct Sts{
	int v,l,r,a,b;
	Sts(int v,int l,int r,int a,int b):v(v),l(l),r(r),a(a),b(b){}
	bool operator>(const Sts& b) const {
		return v > b.v; 
	}

};

Segtree sgg, sgk;



Sts f(int l, int r){
	auto& sg1 = l%2? sgk : sgg;
	auto& sg2 = l%2? sgg : sgk;
	
	int v = sg1.query(l,r);
	int a = sg1.getpos(l,r,v);
	int t = sg2.query(a+1,r);
	int b = sg2.getpos(a+1,r,t);
	return Sts(v,l,r,a,b);
}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	VI p(n);
	sgg.init(n+2); sgk.init(n+2);

	rep(i,n){
		int c; cin >>c;
		p[i] = c;
		if(i%2) sgk.update(i,c);
		else sgg.update(i,c);
	}
	Sts sta = f(0,n);
	priority_queue<Sts, vector<Sts>, greater<Sts> > pq;
	pq.push(sta);
	VI ans;
	int ct=0;
	while(!pq.empty()){
		auto cr = pq.top(); pq.pop();
		//printf("%d:%d:%d:%d:%d   ",cr.v,cr.l,cr.r,cr.a,cr.b);
		ans.push_back(p[cr.a]);
		ans.push_back(p[cr.b]);
		if(cr.a - cr.l > 1) pq.push(f(cr.l, cr.a));
		if(cr.b - cr.a > 1) pq.push(f(cr.a+1, cr.b));
		if(cr.r - cr.b > 1) pq.push(f(cr.b+1, cr.r));
	}
	
	for(auto x :ans) printf("%d ",x); puts("");
	return 0;
}


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

namespace {
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define len(x) (int)((x).size())
#define X first
#define Y second

#define FOR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;

ll expmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
template<typename T> T sqr(const T& x) { return x*x; }
ll flog(const ll x) { return 63 - __builtin_clzll(x); }
template<typename T> void sort(T& t) { sort(all(t)); }
template<typename T> void undupe(vector<T>& v) { sort(v); v.erase(unique(all(v)), v.end()); }

struct _IOS { _IOS() { ios::sync_with_stdio(0); cin.tie(0); } } _IOS;
}

const ll MOD = 1e9 + 9;
const ll INF = 1e15;
const double EPS = 1e-8;

int N;
vector<ll> A;

bool can(int j) {
  ll size = A[j];
  bool good = true;
  FOR(i,0,N) if (i != j) {
    if (A[i] <= 2 * size) {
      size += A[i];
    } else {
      good = false;
      break;
    }
  }
  return good;
}

int main() {
	cin >> N;
  A.resize(N);
  for (auto& x : A) cin >> x;
	sort(A);
  
  if (can(0)) cout << N << "\n";
  else {
    int lo = 0, hi = N - 1;
    while (lo != hi - 1) {
      int mid = (lo + hi)/2;
      if (can(mid)) hi = mid;
      else lo = mid;
    }
    cout << N - hi << "\n";
  }
}


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

int main(){
	deque<int>v;
	int q;cin>>q;
	rep(i,q){
		int a,b;cin>>a>>b;
		if(a==0){
			int x;cin>>x;
			if(b==0)v.push_front(x);
			else v.push_back(x);
		}
		else if(a==1){
			cout<<v[b]<<endl;
		}
		else{
			if(b==0)v.pop_front();
			else v.pop_back();
		}
	}
}



Measured memory_bytes: 4588
import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int[] W = new int[N];
        for (int i = 0; i < N; i++) {
            W[i] = Integer.parseInt(sc.next());
        }

        int left = 0;
        int right = 0;
        int dif = 100000;
        for (int i = 0; i < N; i++) {
            left = sum(Arrays.copyOfRange(W, 0, i));
            right = sum(Arrays.copyOfRange(W, i, W.length));
            dif = Math.min(dif, Math.abs(left - right));
        }
        System.out.println(dif);
    }

    private static int sum(int[] temp) {
        int n = temp.length;
        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret += temp[i];
        }
        return ret;
    }
}


Measured memory_bytes: 23764
D,N=map(int,input().split())
a=100**(D)
A=[]
for i in range(1,101):
    A.append(i*a)
if D==0:
    A.remove(100)
    A.append(101)
elif D==1:
    A.remove(10000)
    A.append(10100)
elif D==2:
    A.remove(1000000)
    A.append(1010000)
print(A[N-1])

Measured memory_bytes: 9168
a = input().split()
a = list(a)
for i in range(3):
  a[i] = int(a[i])
a.sort()

if(a[0] == a[1]):
  if(a[1] == a[2]):
    print(1)
  else:
    print(2)
elif(a[1] == a[2]):
  print(2)
else:
  print(3)

Measured memory_bytes: 3060
#include <stdio.h>
int F_seisu(long long int N){
		long long int i,j,k;
		for(i=1;i*i<=N;i++){
			if(N%i==0){
				j=i;}}
				return j;}
				
int order(long long int n){
	int i,j;
	j=0;
	for(i=1;n>0;i++){
		
			n/=10;
			j+=1;}
			return j;}
int main(void)
{int A,M,B,j,x,i,k,l,m,flag;
	 long long int N;
	scanf("%lld",&N);
	j=F_seisu(N);
	x=N/j;
	if(order(j)>=order(x))
	printf("%d",order(j));
	else
	printf("%d",order(x));


	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
typedef long long ll;
#define PI 3.14159265
ll exponent(ll x,ll n,ll m)
{  if(n==0)
    return 1;
    if(n%2!=0)
    {
        return (x*exponent(((x%m)*(x%m))%m,(n-1)/2,m))%m;
    }
    else
    return exponent(((x%m)*(x%m))%m,n/2,m);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(NULL);
    int h,w,n;
    cin>>h>>w>>n;
    int maxi=max(h,w);
    cout<<n/maxi+min(1,n%maxi);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int cn=0;
    while(a%2==0&&b%2==0&&c%2==0)
    {
        cn++;
        int x=b/2+c/2;
        int y=a/2+c/2;
        int z=a/2+b/2;
        a=x;
        b=y;
        c=z;
        //cout<<a<<' '<<b<<' '<<c<<' '<<endl;
        if(cn>10000007)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<cn<<endl;;
    return 0;
}



Measured memory_bytes: 256
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

pub fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        x.abs()
    } else {
        gcd(y, x % y)
    }
}

pub fn pow(x: i64, n: i64) -> i64 {
    let (mut x, mut y, mut n) = (x % P, 1_i64, n);
    while n > 0 {
        if n % 2 != 0 {
            y = (y * x) % P;
            n -= 1;
        }

        x = (x * x) % P;
        n /= 2;
    }
    y
}

const P: i64 = 1_000_000_007;

type V2 = (i64, i64);

fn main() {
    let mut scan = Scan::new();

    let N = scan.word::<usize>();
    let mut total = 0_i64;

    // A = 0, B != 0
    let mut az = 0;
    // A != 0, B = 0
    let mut bz = 0;
    // A = B = 0
    let mut zz = 0;

    let mut freq = HashMap::<V2, [usize; 2]>::new();

    for _ in 0..N {
        let A = scan.word::<i64>();
        let B = scan.word::<i64>();

        match (A, B) {
            (0, 0) => {
                zz += 1;
                continue;
            }
            (0, _) => {
                az += 1;
                continue;
            }
            (_, 0) => {
                bz += 1;
                continue;
            }
            _ => {}
        }

        let (r, s) = {
            let mut a = A.abs();
            let mut b = B.abs();
            let g = gcd(a, b);
            a /= g;
            b /= g;
            if A.signum() == B.signum() {
                ((a, b), 0)
            } else {
                ((b, a), 1)
            }
        };

        freq.entry(r).or_insert([0, 0])[s] += 1;
    }

    // A = B = 0 のサバは他のすべてのサバと相性が悪いので、
    // このようなサバ x を含む選び方は {x} しかない。
    total += zz;

    let mut ab = 1_i64;

    for (_, xs) in freq {
        let (x, y) = (xs[0], xs[1]);

        // x 匹のサバからなるグループと y 匹のサバからなるグループは互いに仲が悪いので、
        // 「サバを1匹も選ばない」「x 匹のグループから 1..=x 匹を選ぶ」「y 匹のグループから 1..=y 匹を選ぶ」
        // の3通りのケースを考える。
        // 他のサバに関しては好きに選んでいいので、場合の数は掛け合わせていく。
        ab *= (pow(2, x as i64) + pow(2, y as i64) - 1) % P;
        ab %= P;
    }

    ab *= (pow(2, az) + pow(2, bz) - 1) % P;
    ab %= P;

    // サバを1匹も選ばないケースは除く。
    ab += P - 1;

    total += ab;
    total %= P;

    println!("{}", total);
}


Measured memory_bytes: 20088
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <bitset>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

int main(void){

    int A, B;
    cin >> A >> B;
    if(B % A == 0){
        printf("%d\n",  A+B);
    }
    else{
        printf("%d\n",  B-A);

    }

    return 0;
}

Measured memory_bytes: 256
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;
char a,b;
int main(){
	cin>>a>>b;
	if(a=='H' && b=='H')cout<<"H"<<endl;
	if(a=='H' && b=='D')cout<<"D"<<endl;
	if(a=='D' && b=='H')cout<<"D"<<endl;
	if(a=='D' && b=='D')cout<<"H"<<endl;








	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//vector<pair<int,int> > pc[100001];
//int ABS(int a){return max(a,-a);}
int main(){
    int n;
    cin>>n;
    int h[n+2];
    h[0]=0;h[n+1]=0;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    int ans=0;
    int ch=1;
    while(ch){
        ch=0;
        for(int l=1;l<=n+1;l++){
            if(h[l]==0&&h[l-1]!=0){
                ans++;
            }
        }
        for(int l=1;l<=n+1;l++){
            if(h[l]!=0){
                h[l]--;
                ch++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
  int N; cin >> N;
  int ans[100000];
  
  for(int i = 1; i*i< N; i++){
    for(int j = 1; j*j < N;j++){
      for(int k = 1; k*k < N;k++){
        int total = ((i+k)*(i+k)+(j+k)*(j+k)+(i+j)*(i+j))/2;
        ans[total]++;
      }
    }    
  }
  for(int i = 1; i <= N; i++){
    cout << ans[i] << endl;
  }
}


Measured memory_bytes: 3760
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <sstream>
//#include <unordered_map>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORD(i, a, b) for(int i = (a-1); i >= (b); i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
typedef long long int ll;
using namespace std;
ll mod=1000000007;
//ll mod=67280421310721;
//ll mod=998244353;
ll INF=1e18;
ll po(ll a,ll b)
{
	ll re=1;
	while(b)
	{
		if(b%2==1)
		{
			re=(re*a);
			re%=mod;
		}
		a=(a*a);
		a%=mod;
		b>>=1;
	}
	return re;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string str;
	cin>>str;
	long long int n;
	n=str.length();
	long long  sum = 0;
	for(long long  i=0;i<n;++i){
		sum=(sum+(str[i]-'0'))%9;
	}
	if(sum%9==0)
		cout<<"Yes";
	else
		cout<<"No";
		
	
	return 0;
}

Measured memory_bytes: 3688
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;


int main(void){
  int n,q,i,rk[100005]={};
  string s;
  
  cin >> n >> q >> s;
  
  for (i=0;i<n;i++){
    if (s[i]=='A' && s[i+1]=='C') rk[i+1]=1;
  }
  
  for (i=2;i<=n;i++) rk[i]+=rk[i-1];
  
  int l,r;
  for (i=0;i<q;i++){
    cin >> l >> r;
    cout << rk[r-1]-rk[l-1] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1408
import copy
N, M = map(int, input().split())
H = list(map(int, input().split()))
RH = copy.copy(H)
for j in range(M):
  a, b = map(int, input().split())
  ah = H[a-1]
  bh = H[b-1]
  if ah > bh:
    RH[b-1] = 0
  elif bh > ah:
    RH[a-1] = 0
  else:
    RH[a-1] = 0
    RH[b-1] = 0
RH = sorted(RH, reverse=True)
ans = 0
for i in range(M):
  if RH[i] == 0: break
  ans += 1
print(ans)

Measured memory_bytes: 20972
import java.util.*;

class Main {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final String S = sc.next();
        sc.close();

        int n = S.length();
        int cnt = 0;
        for (int i=0; i<n/2; i++) {
            if (!S.substring(i, i+1).equals(S.substring(n-i-1, n-i))) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 23636
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>

using namespace std;
typedef long long ll;

/*迷路
const int INF = 50;

typedef pair<int,int> P;
char field[52][52];
int d[51][51];
int r,c;
int sx,sy;
int gx,gy;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int bfs(){
    queue<P> que;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            d[i+1][j+1] = INF;
        }
    }
    que.push(P(sy,sx));
    d[sy][sx]=0;
while(que.size()){
    P p=que.front();
    que.pop();
    if(p.second==gx&&p.first==gy) break;
    for(int i=0;i<4;i++){
        int nx=p.second+dx[i];
        int ny=p.first+dy[i];

        if(1<=nx&&nx<=c&&1<=ny&&ny<=r&&field[ny][nx]!='#'&&d[ny][nx]==INF){
            que.push(P(ny,nx));
            d[ny][nx] = d[p.first][p.second] + 1;
        }
    }
}
return d[gy][gx];
}
*/
int main(){
  string s;
  cin>>s;
  int ans = 0;
  for(int i = 0; i<3;i++){
    if(s[i]=='1') ans++;
  }
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;

int main()
{
    long long n, ans = 0;
    cin >> n;
    vector<long long> a(n+1), b(n);
    for(int i = 0; i < n+1; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    long long tmp;
    for(int i = 0; i < n; i++){
        if(b[i] > a[i]){
            tmp = a[i+1];
            a[i+1] = a[i]+a[i+1]-b[i];
            if(a[i+1] < 0){
                a[i+1] = 0;
                ans += a[i]+tmp;
            }else{
                ans += b[i];
            }
        }else{
            ans += b[i];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl

#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define gap cout<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())



int main(){
	int a[3][3];
	int b[3][3];
	map<int,pair<int,int>> mp;
	fo(i,3){
		fo(j,3){
			cin>>a[i][j];
			mp[a[i][j]]={i,j};
			b[i][j]=0;
		}
	}
	int n;
	cin>>n;
	int tmp;
	fo(i,n){
		cin>>tmp;
		if(mp.count(tmp)) ;
		else continue;
		auto j=mp[tmp];
		b[j.first][j.second]=1;
	}
	bool taken;
   bool is=false;
	fo(i,3){
		 taken=true;
		fo(j,3){
			if(b[i][j]==1) ;
			else{
				taken=false;
				break;
			}
		}
		if(taken) is=true;
	}
    
	fo(i,3){
		taken=true;
		fo(j,3){
			if(b[j][i]==1) ;
			else{
				taken=false;
				break;

			}
		}
		if(taken) is=true;

	}

	if(b[0][0]&&b[1][1]&&b[2][2]) is=true;
	if(b[2][0]&&b[1][1]&&b[0][2]) is=true;

    if(is) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


	
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
  char s[100001];
  scanf("%s", s);
  
  int n = strlen(s);
  int b_score = 0;
  int w_score = 0;
  for(int i=0; i<n; i++){
    if(s[i] != '0' + i%2){
      ++w_score;
    } else {
      ++b_score;
    }
  }
  
  printf("%d\n", min(b_score, w_score));
  return 0;
}

Measured memory_bytes: 384
///
// File:  a.cpp
// Author: ymiyamoto
//
// Created on Sat Nov  4 02:05:47 2017
//

#include <cstdint>
#include <iostream>

using namespace std;

int32_t main()
{
  int32_t R, G;
  cin >> R;
  cin >> G;

  cout << G * 2 - R << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <functional>
#include "math.h"
#include <set>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define VI vector<int>
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define MB 1000000007
#define NB 1000000000
#define N5 100007
#define ll long long int
int N,W;
ll w[N5],v[N5],dp[101][N5];

int main()
{

	cin >>N >> W;
	REP(i,N){
		cin >> w[i] >> v[i];
	}
	REP(i,W){
		dp[0][i] = 0;
	}

	FOR(i,1,N+1){
		REP(j,W+1){
			if(j-w[i-1]>=0){
				dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1],dp[i-1][j]);
			} else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}

/*	REP(i,N+1){
		REP(j,W+1){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
*/
	cout << dp[N][W];
}





Measured memory_bytes: 80128
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int N; cin>>N;
  vector<int> L(N);
  for(int i=0;i<N;i++){
    cin>>L.at(i);
  }

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

	int ans = 0;
	for(int i=0;i<N-2;i++){
		for(int j=i+1;j<N-1;j++){
			for(int k=j+1;k<N;k++){
				if((L.at(i)+L.at(j))>L.at(k)){
					ans++;
				}else{
					break;
				}
			}
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)
bool chk(int n)
{
    int j=0;
    while(n!=0)
    {
        n/=10;
        j++;
    }
    if(j%2)return true;
    return false;
}
int main()
{
    int n,i,j,t;
    boost;
    cin>>n;
    int c=0;
    rep(i,1,n+1)
    {
        if(chk(i))c++;
    }
    cout<<c;
    return 0;
}



Measured memory_bytes: 256
ip = input().split()
usdata = []
usdata.append(int(ip[0]))
usdata.append(int(ip[1]))
flag = 0

for i in usdata:
    if i >= 9:
        flag = 1
    else:
        pass

if flag == 1:
    print(":(")
else:
    print("Yay!")


Measured memory_bytes: 2940
n,m,x,y=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
max_X=max(X)
min_Y=min(Y)
print('No War' if max_X<min_Y and max_X<y and x<min_Y else 'War')

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

using namespace std;
struct TNode{
    long long Left, Right;
    long long lz;
};
TNode st[200 * 100000];
int cnt_node = 0;
//a[u] -> a[v] += val
int AddNode() {
    //st.push_back({0, 0, 0});
    return cnt_node++;
}
void update(int root, long long l, long long r, long long u, long long v, long long val) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        st[root].lz += val;
        return;
    }
    long long mid = (l + r) >> 1;
    if (st[root].Left == 0) st[root].Left = AddNode();
    if (st[root].Right == 0) st[root].Right = AddNode();
    update(st[root].Left, l, mid, u, v, val);
    update(st[root].Right, mid + 1, r, u, v, val);
}
long long get(int root, long long l, long long r, long long pos) {
    if (l == r) return st[root].lz;
    long long mid = (l + r) >> 1;
    if (pos <= mid) {
        if (st[root].Left == 0) st[root].Left = AddNode();
        return get(st[root].Left, l, mid, pos) + st[root].lz;
    }
    if (st[root].Right == 0) st[root].Right = AddNode();
    return get(st[root].Right, mid + 1, r, pos) + st[root].lz;
}
const int maxn = 2e5 + 5;
pair<int, int> a[maxn];
int main() {
#ifdef LDT
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    AddNode();
    int n;
    long long len, dmg;
    cin >> n >> len >> dmg;
    len *= 2;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + 1 + n);
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        long long pos = a[i].first;
        long long hp = get(0, 0, 3e9, pos) + a[i].second;
        if (hp <= 0) continue;
        long long t = hp / dmg + (hp % dmg != 0);
        update(0, 0, 3e9, pos, pos + len, -t * dmg);
        res += t;
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 153856
def solve
  res = 10**10
  1.upto(N) do |i|
    break if N < i*i
    next if N%i != 0
    res = [res, [i.to_s.size, (N/i).to_s.size].max].min
  end
  res
end

N=gets.to_i
p solve


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
const int N = (1 << 18);
int h[200010], a[200010], ch[200010];
map<int, long long> dp;
map<int, int> ind;
long long segt[N * 2];
void update(int idx, long long val) {
    idx += N - 1;
    segt[idx] = val;
    for (idx /= 2; idx >= 1; idx /= 2) {
        segt[idx] = max(segt[idx * 2], segt[idx * 2 + 1]);
    }
}
long long query(int r) {
    r += N - 1;
    int l = N;
    long long mx = 0;
    for (; l <= r; l /= 2, r /= 2) {
        if (l % 2 == 1) {
            mx = max(mx, segt[l]);
            ++l;
        }
        if (r % 2 == 0) {
            mx = max(mx, segt[r]);
            --r;
        }
    }
    return mx;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        ch[i] = h[i];
    }
    sort(ch + 1, ch + 1 + n);
    for (int i = 1; i <= n; ++i) {
        ind[ch[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; ++i) {
        dp[h[i]] = a[i] + query(ind[h[i]] - 1);
        //cout << dp[h[i]] << '\n';
        update(ind[h[i]], dp[h[i]]);
    }
    long long answer = 0;
    for (int i = 1; i <= n; ++i) {
        answer = max(answer, dp[h[i]]);
    }
    cout << answer;
}

Measured memory_bytes: 30992
#include<iostream>
int n,m;
int A[2000],B[2000];
bool solve(int i,int m){
	if(m==0){
		return true;
	}
	if(i>=n){
		return false;
	}
	bool res=solve(i+1,m)||solve(i+1,m-A[i]);
	return res;
}
int main(){
    std::cin>>n;
    for(int i=0;i<n;i++){
    std::cin>>A[i];
    }
    std::cin>>m;
    for(int i=0;i<m;i++){
    std::cin>>B[i];
    }
	for(int i=0;i<m;i++){
		if(solve(0,B[i])){
			std::cout<<"yes\n";
		}else{
			std::cout<<"no\n";
		}
	}
  return 0;
}



Measured memory_bytes: 3076
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] l = new int[n];
        int max = 0;
        int sum = 0;
        for(int i = 0; i <n; i++){
            l[i] = sc.nextInt();
            if(l[i] > max) max = l[i];
            sum += l[i];
        }
        if(sum - max > max) System.out.println("Yes");
        else System.out.println("No");
    }
}

Measured memory_bytes: 23764
import Data.List.Split
main = do
  s <- getLine
  putStrLn $ aux s

aux :: String -> String
aux str
  | a < b = "a < b"
  | a==b  = "a == b"
  | True  = "a > b"
  where
    [a,b] = map (\x -> read x :: Int)  (splitOn " " str)

Measured memory_bytes: 3604
import Control.Applicative
import Data.List

solve acc _ [] = acc
solve acc (a0:a1:as) (b:bs) = do
  let (r, b') = if a0 <= b then (a0, b - a0) else (b, 0)
  let (l, a1') = if a1 <= b' then (a1, 0) else (b', a1 - b')
  let acc' = acc + r + l
  solve acc' (a1':as) bs


main = do
  n <- read <$> getLine :: IO Int
  --[n, m] <- (map read).words <$> getLine :: IO [Int]
  as <- (map read).words <$> getLine :: IO [Int]
  bs <- (map read).words <$> getLine :: IO [Int]
  print $ solve 0 as bs


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

typedef long long ll;

int main(void){
    string s;
    cin >> s;
    ll ans = 0, cnt = 0;
    for(int i=0; i<s.length(); i++){
        if(s[i] == 'W'){
            ans += i - cnt;
            cnt++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
"use strict";

const main = (arg: string) => {
  const input: string = arg.trim();

  const [_, ...x] = input.split('\n');

  const y = { AC: 0, WA: 0, TLE: 0, RE: 0 }


  x.forEach((e: string) => {
    y[e]++
  })

  const ans = `AC x ${y.AC}
WA x ${y.WA}
TLE x ${y.TLE}
RE x ${y.RE}`

  console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));



Measured memory_bytes: 43300
n,q = map(int,input().split())
S = list(input())
a = [0]*n

for i in range(1,n):
    a[i] = a[i-1]
    if (S[i-1]=='A')and(S[i]=='C'):
        a[i] += 1 
for i in range(q):
    l,r = map(int,input().split())
    print(a[r-1]-a[l-1])


Measured memory_bytes: 8536
#include<stdio.h>
int main(){
  int bingo[3][3];
  int num,hit;
  for(int i=0;i<3;i++) 
    scanf("%d %d %d",&bingo[i][0],&bingo[i][1],&bingo[i][2]);
  
  scanf("%d",&num);
  for(int i=0;i<num;i++){
    scanf("%d",&hit);
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if(hit==bingo[j][k])
          bingo[j][k]=-1;
      }
    }
  }
  for(int i=0;i<3;i++){
    if(bingo[i][0]+bingo[i][1]+bingo[i][2] < 0 ||bingo[0][i]+bingo[1][i]+bingo[2][i] < 0){
      printf("Yes");
      return 0;
    }
  }
  if(bingo[0][0]+bingo[1][1]+bingo[2][2]<0 ||bingo[0][2]+bingo[1][1]+bingo[2][0]<0){
    printf("Yes");
  }
  else
    printf("No");
}

Measured memory_bytes: 128
#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <math.h>
#include <iomanip>
#include <queue>
#include <map>
#include <list>
#include <set>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 50
#define LARGENUM 1000000007
#define INF 9223372036854775807
#define ull unsigned long long 
typedef pair <int, int> P;

int main(){
    int N;
    cin >> N;
    int a[N+1];
    for (int i = 1; i <= N ;i++) cin >> a[i];
    int count = 0;
    for (int i = 1; i <= N; i++){
        if (i % 2 == 1 && a[i] % 2 == 1) count ++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <cstdio>
#include <new>
#include <vector>
#include <cstdlib>
#include <string>
#include <set>
#include <tuple>
#include<map>

using namespace std;
int main() {
	string N;
	cin >> N;

	cout << "ABC" << N << endl;

}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
typedef unsigned long long BITMASK; typedef long long ll; typedef long double ld;
#define smallest_on_bit(bit_mask) (__builtin_ctzint((bit_mask) & (-(bit_mask))))
#define CLOCK_START clock_t chrono_clk_beg = clock()
#define CLOCK_END clock_t chrono_clk_end = clock(); cerr << (double(chrono_clk_end - chrono_clk_beg) / CLOCKS_PER_SEC) << " sec"
#define bug(args ...) cerr << __LINE__ << ">> ", err(new istringstream(string(#args)), args), cerr << '\n'
#define toBinary(name, num) string name = bitset<8>(num).to_string();
#define toDecimal(name, binary) unsigned long name = bitset<8>(binary).to_ulong();
#define all(x) x.begin(), x.end()
#define mapfind(mp, x) (mp.find(x) != mp.end())
#define arrfind(arr, x) (find(all(arr), x) != arr.end())
#define removeDuplicates(vec) sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define int ll
#define double ld
#define INF LONG_MAX
void err(istringstream *iss) {} template<typename T, typename ... Args> void err(istringstream *iss, const T &_val, const Args & ... args) { string _name; *iss >> _name; if (_name.back()==',') _name.pop_back(); cerr << _name << " = " << _val << "; ", err(iss, args ...); }
#define MOD 1000000007

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int h, n;
    cin >> h >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    if (h > accumulate(all(a), 0)) cout << "No\n";
    else cout << "Yes\n";
    return 0;
}

Measured memory_bytes: 1024
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B
  * Structured Program II - How many ways?
  */
object Main {
  def main(args: Array[String]): Unit = {
    val dataSets = Iterator.continually(io.StdIn.readLine()).takeWhile(_ != null).map(_.split(" ").map(_.toInt))
      .map { case Array(n, x) => (n, x) }
      .takeWhile(_ != (0, 0))
      .toList
    val results = dataSets.map { case (n, x) =>
      // Memory Limit Exceeded
      // (1 to n).combinations(3).count(_.sum == x)
      (for (a <- 1 to n - 2;
            b <- a + 1 to n - 1 if a < b;
            c <- b + 1 to n if a < c && b < c && (a + b + c) == x)
        yield 1).length
    }
    results.foreach(println)
  }

}

Measured memory_bytes: 90092
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVL vector<vector<ll>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
constexpr ll MOD = 1000000007;
using std::cout;
using std::endl;
using std::vector;
using std::cin;
using std::map;
using std::multimap;
using std::set;
using std::multiset;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll pow(ll a, ll b) {
	ll ans = 1;
	while (b > 0) {
		if (b % 2 == 1) {
			ans *= a;
			ans %= MOD;
		}
		b /= 2;
		a *= a;
		a %= MOD;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a - b < b) { return comb(a, a - b); }
	ll c = 1;
	FOR(i, a - b + 1, a + 1) {
		c *= i;
		c %= MOD;
	}
	ll k = 1;
	FOR(i, 2, b + 1) {
		k *= i;
		k %= MOD;
	}
	c *= pow(k, MOD - 2);
	return c % MOD;
}
multiset<ll> prime_decomposition(ll n) {
	ll i = 2;
	multiset<ll> table{};
	while (i * i <= n) {
		while (n % i == 0) {
			n /= i;
			table.emplace(i);
		}
		++i;
	}
	if (n > 1) {
		table.emplace(n);
		return table;
	}
	return table;
}

int main() {
	ll n, m;
	cin >> n >> m;
	vector<multiset<ll>> cake(8);
	REP(i, n) {
		ll a, b, c;
		cin >> a >> b >> c;
		cake[0].emplace(a + b + c);
		cake[1].emplace(-a + b + c);
		cake[2].emplace(a - b + c);
		cake[3].emplace(-a - b + c);
		cake[4].emplace(a + b - c);
		cake[5].emplace(-a + b - c);
		cake[6].emplace(a - b - c);
		cake[7].emplace(-a - b - c);
	}
	ll ans = 0;
	REP(i, 8) {
		ll sum = 0;
		auto itr = cake[i].rbegin();
		for (int j = 0; j < m; ++j, ++itr) {
			sum += *itr;
		}
		ans = std::max(sum, ans);
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdlib>
#include<utility>
#include<tuple>
#include<string>
#include<vector>
#include<numeric>
#include<algorithm>
#include<queue>
#include<deque>
#include<bitset>
#include<cmath>
#include<map>
#include<iomanip>
using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;
#define rep(i, a, b) for(int i = a; i < b; i++)

int main() {
	
	long double a, b;
	cin >> a >> b;

	ll ans = a * b;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3728
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int N, M;
bool from1[200000];
bool toN[200000];

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

    cin >> N >> M;
    for(int i = 0; i < M; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        if(a == 0){
            from1[b] = true;
        }
        if(b == 0){
            from1[a] = true;
        }
        if(a == N - 1){
            toN[b] = true;
        }
        if(b == N - 1){
            toN[a] = true;
        }
    }

    for(int i = 0; i < N; ++i){
        if(from1[i] && toN[i]){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main()
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if (a < c && c < b)
		printf("Yes\n");
	else if (b < c && c < a)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize("O3")

#include<bits/stdc++.h>
#define sp " "
#define endl "\n"
#define MAX 10e9
#define MAXN 100001
#define mod 1000000007
#define inf_int 2e9
#define inf_ll 2e18
#define e 1e-9
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpl vector<pair<ll,ll>>
#define vpc vector<pair<char,char>>
#define adj_list vector<vl>
#define umap unordered_map<ll, ll>
#define pll pair<ll,pair<ll, ll>>
#define clr(x) memset(x,0,sizeof(x))
#define cy cout << "YES" << endl
#define cn cout << "NO" << endl
#define google cout << "Case #" << ++it << ": " << ans << endl;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long int ll;

ll it = 0, ans = 0;

ll spf[MAXN];
void sieve()
{
    spf[1] = 1;
    for (auto i=2; i<MAXN; i++)
  		spf[i] = i;
  	for (auto i=4; i<MAXN; i+=2)
        spf[i] = 2;
    for (auto i=3; i*i<MAXN; i++)
    {
        if (spf[i] == i)
        {
            for (auto j=i*i; j<MAXN; j+=i)
                if (spf[j]==j)
                    spf[j] = i;
        }
    }
	return;
}

vl getFactorization(ll x)
{
    vl ret;
    while (x != 1)
    {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}


void check()
{
	ll n,k;
	cin >> n >> k;
	vl a(n);
	for(int i=0;i<n;i++) cin >> a[i];
	ll dp[n];
	memset(dp,mod,sizeof(dp));
	dp[0] = 0, dp[1] = abs(a[1]-a[0]);
	for(int i=0;i<n;i++) {
		for(int j=i+1;j<=i+k and j<n;j++) dp[j] = min(dp[j],dp[i]+abs(a[j]-a[i]));
	}
	cout << dp[n-1] << endl;
    return ;
}

int32_t main()
{
    fastio
    ll t = 1;
    // cin >> t;
    while(t--)
        check();
    return 0;
}


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

int main(){
    ll h;
    cin >> h;
    ll a = h;
    ll cnt = 1;
    ll coef = 1;
    while(a > 1){
        coef *= 2;
        a /= 2;
        cnt += coef;
    }
    
    cout << cnt << endl;
    
} 

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

using namespace std;
using ll=long long;
using vi=vector<int>;

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int n, m;
    cin >> n >> m;
    vi a(n , 1) , red(n , 0);
    red[0] = 1;
    for(int i = 0; i < m; i++){
        int from , to;
        cin >> from >> to;
        --from , --to;
        if(a[from] >= 1){
            a[from]--;
            a[to]++;
            red[to] |= red[from];
            if(a[from] ==0){
                red[from] = 0;
            }
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(red[i])cnt++;
    }
    cout << cnt << '\n';




    return 0;
}













Measured memory_bytes: 1024
def main():
    n=int(input())
    a=input()
    flag=0
    cnt=0
    for i in range(n):
        if flag==0:
            if a[i]=="A":
                flag=1
            else:
                pass
        elif flag==1:
            if a[i]=="B":
                flag=2
            else:
                if a[i]=="A":
                    flag=1
                else:
                    flag=0
        elif flag==2:
            if a[i]=="C":
                flag=0
                cnt+=1
            else:
                if a[i]=="A":
                    flag=1
                else:
                    flag=0
    print(cnt)
main()


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

int main(){
  int max = 0;
  int N;
  cin>>N;
  int *L;
  L = new int[N];
  int sum = 0;
  for(int i = 0;i < N;i++){
	cin>>L[i];
    sum += L[i];
    if(L[i] > max)max = L[i];
  }
  sum -= max;
  if(sum > max)cout<<"Yes";else cout<<"No";
 return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
 
using namespace std;
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 
 
 

int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=1;i<=2000;i++)
    {
        double x=i;
        int x1=i*0.08;
        int x2=i*0.1;
        if(x1==a&&x2==b)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"-1\n";

    return 0;   
}
 
 


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 //Compiler version g++ 6.3.0
int main(){
  int a,b;
  cin >> a >> b;
  int ans=0;
  for(int i=a; i<=b; i++){
    if(i/10000==i%10&&(i%10000)/1000==(i%100)/10){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <iostream>
using namespace std;
typedef string::const_iterator State;

int h,w;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int fie[51][51];
bool vis[51][51][4][1005];
int x,y,gx,gy;
string str;
int to[1005];
int last[1005];

int solve(){
	int n=str.size();
	int depth=0;
	for(int i=0;i<n;i++){
		if(str[i]=='[' || str[i]=='{'){
			last[depth++]=i;
		}
		if(str[i]==']' || str[i]=='}'){
			depth--;
			to[i]=last[depth];
			to[last[depth]]=i;
		}
	}
	int dir=0;
	memset(vis,false,sizeof(vis));
	vis[y][x][dir][0]=true;
	int cur=0,ret=0;
	while(cur<n){
		if(str[cur]=='[' || str[cur]=='{'){
			bool nt=false;
			bool val=false;
			char p=str[cur+1];
			if(p=='~'){
				p=str[cur+2];
				nt=true;
			}
			if(p=='N' && dir==0)val=true;
			if(p=='E' && dir==1)val=true;
			if(p=='S' && dir==2)val=true;
			if(p=='W' && dir==3)val=true;
			if(p=='C' && fie[y+dy[dir]][x+dx[dir]]==-1)val=true;
			if(p=='T')val=true;
			if(nt)val=!val;
			if(val){
				if(nt)cur+=3;
				else cur+=2;
			}else{
				cur=to[cur]+1;
			}
		}else if(str[cur]==']')cur++;
		else if(str[cur]=='}')cur=to[cur];
		else{
			if(str[cur]=='^'){
				if(fie[y+dy[dir]][x+dx[dir]]!=-1){
					y+=dy[dir];
					x+=dx[dir];
				}
			}
			if(str[cur]=='v'){
				if(fie[y-dy[dir]][x-dx[dir]]!=-1){
					y-=dy[dir];
					x-=dx[dir];
				}
			}
			if(str[cur]=='>')dir=(dir+1)%4;
			if(str[cur]=='<')dir=(dir+3)%4;
			cur++;
			ret++;
		}
		if(y==gy && x==gx)break;
		if(vis[y][x][dir][cur])return -1;
		vis[y][x][dir][cur]=true;
	}
	if(y!=gy || x!=gx)return -1;
	return ret;
}

int main(void){
	scanf("%d%d",&h,&w);
	for(int i=0;i<h;i++){
		cin >> str;
		for(int j=0;j<w;j++){
			if(str[j]=='#')fie[i][j]=-1;
			if(str[j]=='g'){
				gx=j;
				gy=i;
			}
			if(str[j]=='s'){
				x=j;
				y=i;
			}
		}
	}
	cin >> str;
	printf("%d\n",solve());
	return 0;
}

Measured memory_bytes: 13552
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  cin >> c;
  
  if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
n=list(map(int,list(input())))
a=[1 if i%2==0 else 0 for i in range(len(n))]
b=[1 if i%2==1 else 0 for i in range(len(n))]
num_a=0
num_b=0
for i in range(len(n)):
	if n[i] is a[i]:
		num_a+=1
	if n[i] is b[i]:
		num_b+=1

if num_a>=num_b:
	print(len(n)-num_a)
else:
	print(len(n)-num_b)

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


int main(void)
{
    int i;
    int num[10];

    for (i = 0; i < 10; i++) {
        scanf("%d", &num[i]);
    }

    sort(num, num+10, greater<int>());

    printf("%d\n", num[0]);
    printf("%d\n", num[1]);
    printf("%d\n", num[2]);

    return 0;
}

Measured memory_bytes: 1204
////////////////////////
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
namespace my {
char itoc(int i) { return i + '0'; }
int ctoi(char c) { return c - '0'; }
ll gcd(ll a, ll b) {
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b != 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
ll lcm(ll a, ll b) { return a * b / my::gcd(a, b); }
vector<pair<ll, ll>> primeFac(ll n) {
  vector<pair<ll, ll>> ret;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i != 0) continue;
    ll exp = 0;
    while (n % i == 0) {
      n /= i;
      exp++;
    }
    ret.push_back(make_pair(i, exp));
  }
  if (n != 1) ret.push_back(make_pair(n, 1));
  return ret;
}
}  // namespace my
////////////////////////

int main() {
  int x, y;
  cin >> x >> y;
  for (int i = 0; i <= x; i++) {
    for (int j = 0; j <= x; j++) {
      if (i + j == x && i * 2 + j * 4 == y) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}

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

long long GCD(long long a, long long b) {
    return b == 0 ? a : GCD(b, a % b);
}

void Main()
{
	int N, X; cin >> N >> X;
	vector<int> x(N);
	rep(i,N) cin >> x[i];
	auto min_el_it = min_element(x.begin(), x.end());
	auto idx = distance(x.begin(), min_el_it);
	auto min_el = *min_el_it;
	int tmp = min(min_el, X);
	if (tmp != X) x[idx] = X;
	rep(i,N) x[i] -= tmp;

    long long res = x[0];
    for (int i = 0; i < N; ++i) res = GCD(res, x[i]);
    cout << res << endl;
}

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


Measured memory_bytes: 640