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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
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; }
//template end



int main(){
   int n; ll k; scanf("%d%lld",&n,&k);
   vector<int> a(n);
   rep(i,0,n)scanf("%d",&a[i]);
   sort(ALL(a)); ll lb=-INF,rb=INF;
   while(rb-lb>1){
      ll mid=(lb+rb)/2;
      ll cnt=0;
      rep(i,0,n){
         if(a[i]<0){
            int l=i,r=n;
            while(r-l>1){
               int m=(l+r)/2;
               if(1LL*a[i]*a[m]<mid)r=m; else l=m;
            }
            cnt+=n-r;
         }
         else{
            int l=i,r=n;
            while(r-l>1){
               int m=(l+r)/2;
               if(1LL*a[i]*a[m]<mid)l=m; else r=m;
            }
            cnt+=l-i;
         }
      }
      if(cnt<k)lb=mid; else rb=mid;
   }
   printf("%lld\n",lb);
   return 0;
}

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

int main ()
{
  int a,b,c;
  cin >> a >> b;
  c = a * b;
  
  if(c % 2 == 0){
	cout << "Even" << endl;
  }else{
   	cout << "Odd" << endl; 
  }
}
  

Measured memory_bytes: 256
S = input()
ans = 0
for i in range(len(S)):
	for j in range(i + 1, len(S) + 1):
		s = S[i:j]
		ok = True
		for k in range(len(s)):
			if s[k] not in {'A', 'C', 'G', 'T'}: ok = False
		if ok: ans = max(ans, j - i)
print(ans)


Measured memory_bytes: 3060
main = do
    n <- readLn :: IO Int
    a <- readLn :: IO Int
    b <- readLn :: IO Int
    c <- readLn :: IO Int
    d <- readLn :: IO Int
    e <- readLn :: IO Int
    let ls = [a,b,c,d,e]
    let m = minimum ls
    let wait = n `div'` m
    print $ wait + 4

div' :: Int -> Int -> Int
div' a b = ceiling $ fromIntegral a / fromIntegral b

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

int main(){
    string s;
    cin >> s;
    rep(i,s.size()){
        if(s[i] == s[i+1]){
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
}

Measured memory_bytes: 256
while True:
    h, w = map(int,input().split())
    if h == 0 and w == 0:
        break
    else:
        for i in range(h):
            if i % 2 != 0:
                for j in range(w):
                    if j % 2 != 0:
                        print('#', end="")
                    else:
                        print('.', end="")
                print()
            else:
                for k in range(w):
                    if k % 2 == 0:
                        print('#', end="")
                    else:
                        print('.', end="")
                print()
        print()
        




Measured memory_bytes: 7008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
const int iNF = 1e9 + 100;
const ll INF = 1e18 + 100;
typedef pair<int, int> pii;

int main(){
   float k, a, b;
   cin >> k >> a >> b;
   auto y = ceil(a / k);
   y = y * k;
   if( y >= a and y <= b){
      cout << "OK\n";
   }else{
      cout << "NG\n";
   }
   return 0;
}

Measured memory_bytes: 3724
import sys
input = sys.stdin.buffer.readline

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [(a, i+1) for i, a in enumerate(A)]
  L.sort(reverse=True)
  dp = [[-1]*(n+1) for _ in range(n+1)]
  dp[0][0] = 0
  ans = 0
  for i in range(n+1):
    for j in range(n+1-i):
      a, idx = L[i+j-1]
      if i:
        dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
      if j:
        dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
      if i+j == n:
        ans = max(ans, dp[i][j])
  print(ans)
if __name__ == "__main__":
  main()

Measured memory_bytes: 124828
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define rg register
#define ll long long
#define LDB long double
#define ull unsigned long long
#define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt)
#define go(i,x,a) for(rg int i=a;i<x;i++)
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
using namespace std;

const int maxn=1005;
int a,b,c,d;
char s[maxn];

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

int main(){
	scanf("%s",s); int n=strlen(s);
	go(i,n,0){
		if(s[i]=='N') a=1;
		if(s[i]=='S') b=1;
		if(s[i]=='E') c=1;
		if(s[i]=='W') d=1;
	}
	if(!(a^b) && !(c^d)) puts("Yes");
	else puts("No");
	return 0;
}//Faze


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;
int N,K,maxi=0,ans=0;
vector<int> G[MAX],dis(MAX);

void DFS(int u,int p){
    for(int i=0;i<G[u].size();i++){
        int a=G[u][i];
        if(a==p) continue;
        DFS(a,u);
        dis[u]=max(dis[u],dis[a]+1);
    }
    if(u==0) return;
    
    if(p==0){
        if(dis[u]==K){
            ans++;
            dis[u]=-1;
        }
    }else{
        if(dis[u]==K-1){
            ans++;
            dis[u]=-1;
        }
    }
}

int main(){
    
    cin>>N>>K;
    int a;cin>>a;
    if(a!=1) ans++;
    for(int i=1;i<N;i++){
        int a;cin>>a;
        a--;
        G[a].push_back(i);
    }
    DFS(0,-1);
    
    cout<<ans<<endl;
    
    
}





Measured memory_bytes: 13952
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAXN = 1000;

int n, edge;
int X[MAXN | 1], fst[MAXN | 1];
int sum[MAXN | 1], dp[MAXN | 1][5001];

struct Edge {
  int to, nxt;
  Edge() : to(0), nxt(0) {}
  Edge(int a, int b) : to(b), nxt(fst[a]) {}
} e[MAXN];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

inline void addEdge(int a, int b) {
  e[++edge] =  Edge(a, b);
  fst[a] = edge;
}

void DP(int x) {
  int size = 0;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    DP(to);
    sum[x] += sum[to];
    ++size;
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1, k = fst[x]; k; k = e[k].nxt, ++i) {
    int to = e[k].to;
    for (int j = 0; j <= X[x]; ++j) {
      if (j >= X[to]) dp[i][j] |= dp[i - 1][j - X[to]];
      if (j >= sum[to] - X[to]) dp[i][j] |= dp[i - 1][j - sum[to] + X[to]];
    }
  }
  bool flag = false;
  for (int i = X[x]; i >= 0; --i) {
    if (dp[size][i]) {
      flag = true;
      sum[x] += X[x] - i;
      break;
    }
  }
  if (!flag) {
    puts("IMPOSSIBLE");
    exit(0);
  }
}

int main() {
  n = read();
  for (int i = 2; i <= n; ++i) addEdge(read(), i);
  for (int i = 1; i <= n; ++i) X[i] = read();
  DP(1);
  puts("POSSIBLE");
  return 0;
}


Measured memory_bytes: 19840
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    string s,t;
    cin>>s>>t;
    int ans=0;
    for(int i=0;i<3;++i){
        if(s[i]==t[i])++ans;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
// ============ template finished ============

int main()
{
    vector<int> x(5);
    rep(i, 5)cin >> x[i];
    rep(i, 5)if (x[i] == 0)cout << i + 1 << endl;
    return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
#pragma GCC optimize ("O3")

inline static int gl(void){
    int x = 0;
    for(;;){
        unsigned int c = getchar_unlocked() - 48;
        if(c < 10){
            x = x*10 + c;
        }else{
            break;
        }
    }
    return x;
}

inline static void pl(unsigned int s){
    char str[9];
    int pos=9;
    if(s==0){
        putchar_unlocked('0');
        return;
    }
    do{
        pos--;
        str[pos]=s%10+48;
        s/=10;
    }while(s!=0);
    for(; pos<9; pos++){
        putchar_unlocked(str[pos]);
    }
}

char a[512];
unsigned short out[4*512*512];

int main(void){
    int h=gl(), w=gl(), pos=0;
    char haveCoin = 0;
    short old_y, old_x;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            int t = getchar_unlocked() - 48;
            getchar_unlocked();
            a[j] = t;
        }
        if(i%2==1){
            for(int j=1; j<=w; j++){
                if(haveCoin){
                    out[4*pos+0]=old_y;
                    out[4*pos+1]=old_x;
                    out[4*pos+2]=i;
                    out[4*pos+3]=j;
                    pos++;
                }
                haveCoin ^= a[j]&1;
                old_y = i;
                old_x = j;
            }
        }else{
            for(int j=w; j>0; j--){
                if(haveCoin){
                    out[4*pos+0]=old_y;
                    out[4*pos+1]=old_x;
                    out[4*pos+2]=i;
                    out[4*pos+3]=j;
                    pos++;
                }
                haveCoin ^= a[j]&1;
                old_y = i;
                old_x = j;
            }
        }
    }
    printf("%d\n", pos);
    for(int i=0; i<pos; i++){
        pl(out[4*i+0]); putchar_unlocked(' ');
        pl(out[4*i+1]); putchar_unlocked(' ');
        pl(out[4*i+2]); putchar_unlocked(' ');
        pl(out[4*i+3]); putchar_unlocked('\n');
    }
    return 0;
}


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

using i64 = int64_t;

int main(){
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> v(h+1, w+1);
    vector<pair<int,int>> obstacles;
    for(int i=0;i<n;++i){
        int x, y;
        cin >> x >> y;
        v[x] = min(v[x], y);
        obstacles.emplace_back(x, y);
    }

    vector<int> range(h+1);
    for(int x=2,y=1;x<=h;++x){
        if(v[x] > y+1)y++;
        range[x] = y;
    }

    int ans = h;
    for(auto e: obstacles){
        if(e.second <= range[e.first])ans = min(ans, e.first-1);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3440
// include
// ----------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>

// repetition
// ----------------------------------------------------------------------------
#define FOR(i, a, b) for (i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// memory clear
// ----------------------------------------------------------------------------
#define CLRNUM(a) memset((a), 0, sizeof(a))
#define CLRBOOL(a, flag) memset((a), flag, sizeof(a))
#define CLRCHAR(a) memset((a), '\0', sizeof(a))

// debug
// ----------------------------------------------------------------------------
#define DEBUGNUM(x) printf("%d\n", x);
#define DEBUGCHAR(x) printf("%c\n", x);
#define DEBUGSTR(x) printf("%s\n", x);
#define DEBUGFORNUM(i, a, b, x) FOR(i, a, b){ printf("%d ", x[i]); }
#define DEBUGFORCHAR(i, a, b, x) FOR(i, a, b){ printf("%c ", x[i]); }
#define DEBUGREPNUM(i, n, x) REP(i, n){ printf("%d ", x[i]); }
#define DEBUGREPCHAR(i, n, x) REP(i, n){ printf("%c ", x[i]); }

// other
// ----------------------------------------------------------------------------
#define PUTNL printf("\n")

// constant
// ----------------------------------------------------------------------------
#define INF 1000000000

int main(void)
{
    int n;

    while (scanf("%d", &n) != EOF){
        printf("%d\n", n * (n + 1) / 2 + 1);
    }

    return 0;
}

Measured memory_bytes: 0
# 線形探索
# 与えられた数字を一気に2で割るとしたとき、何回まで整数のままで割れますか、という考え方
# 2進数の1/2倍は右論理シフトになるだけ
# 2進数での右の0の個数(=はじめに1が出てくる数から1を引いた数)が2で割れる回数に等しい

import math
n = input()
a = list(map(int, input().split()))
ans = float("inf")
for i in a:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)
print(round(ans))

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

a.sort(reverse=True)

ans = 0
for i in range(1, n // 2 + 1):
  ans += a[i - 1] * 2
ans -= a[0]

if n % 2 == 1:
  ans += a[(n - 1) // 2]

print(ans)

Measured memory_bytes: 31700
#include<bits/stdc++.h>
using namespace std;
 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define in() ( { int a ; scanf("%d",&a); a; } )
 
const int N = 3e5 + 9;
const int mod = 1e9 + 7;
//int dx[]={1,0,-1,0,1,-1,-1,1};
//int dy[]={0,1,0,-1,1,1,-1,-1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll a, b, c, k, tot = 0;
    cin >> a >> b >> c >> k;
    tot += min(a, k);
    k -= a;
    if(k > 0){
        k -= b;
    }
    if(k > 0){
        tot -= min(k, c);
    }
    cout << tot << endl;
}

Measured memory_bytes: 3620
#include <iostream>
//#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>
//#include <deque>
//#include <bitset>
#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1000000000000 ;

void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}
void chmax(ll &a,ll b){	if(a<b) a = b ;}
void chmin(ll &a,ll b){ if(a>b) a = b ;}


const int MAX = 10000000 ;
// Union Find Tree
// 宣言時はstaticをつけて宣言（そうしないと巨大配列確保で動かない）
class UFT{
public :
	int par[MAX] ; //親の配列
	int rank[MAX] ; //木の高さ
	int size[MAX] ; //木の要素数
	bool root[MAX] ; //木のかどうか
	int graph ; // グループの数
	int tree ; //真に木構造になっているグラフの数

	//要素数を与える
	void init(int n){
		for(int i=0;i<n;i++){
			par[i] = i ;
			rank[i] = 0 ;
			size[i] = 1 ;
			root[i] = true ;
		}
		tree = n ;
		graph = n ;
	}

	//その要素が属する木の根を返す
	int find(int x){
		if(par[x]==x) return x ;
		return par[x] = find(par[x]) ;
	}

	//要素同士をつなげる
	void unite(int x,int y){
		x = find(x) ;
		y = find(y) ;
		if(x==y){
			if(root[x]){
				root[x] = false ;
				tree-- ;
			}
			return ;
		}
		if(rank[x]<rank[y]){
			par[x] = y ;
			size[y] += size[x] ;
			graph-- ;
			if(root[x]){
				root[x] = false ;
				tree-- ;
			}
		}else{
			par[y] = x ;
			size[x] += size[y] ;
			if(rank[x]==rank[y]) rank[x]++ ;
			graph-- ;
			if(root[y]){
				root[y] = false ;
				tree-- ;
			}
		}
	}

	//同じグループに所属しているか判定
	bool same(int x,int y){
		return find(x)==find(y) ;
	}
};


int main(){
	int n,m ;
	cin >> n >> m ;
	static UFT uft ;
	uft.init(n) ;
	while(m--){
		int a,b ;
		cin >> a >> b ;
		a-- ; b-- ;
		uft.unite(a,b) ;
	}
	cout << uft.graph-1 << endl ;
}

Measured memory_bytes: 4924
import java.util.Scanner;

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

    int H = scanner.nextInt();
    int W = scanner.nextInt();
    int N = scanner.nextInt();
    int sr = scanner.nextInt();
    int sc = scanner.nextInt();
    char[] s = scanner.next().toCharArray();
    char[] t = scanner.next().toCharArray();

    if (solve(H, W, N, sr, sc, s, t)) {
      System.out.println("NO");
    } else {
      System.out.println("YES");
    }
  }

  private static boolean solve(int H, int W, int N, int sr, int sc, char[] s, char[] t) {
    int[] rem = new int[] {sc, W - sc + 1, sr, H - sr + 1};
    int[] max = new int[] {W, W, H, H};
    char[] dir = new char[] {'L', 'R', 'U', 'D'};
    char[] otherdir = new char[] {'R', 'L', 'D', 'U'};

    for (int i = 0; i < 4; i++) {
      int r = rem[i];
      int m = max[i];
      char d = dir[i];
      char o = otherdir[i];

      for (int j = 0; j < N; j++) {
        if (s[j] == d) r--;
        if (r <= 0) return true;
        if (t[j] == o) r = Math.min(r + 1, m);
      }
    }
    return false;
  }
}


Measured memory_bytes: 30416
import java.util.*;

public class Main {
    public static void main(String[] args) {	
	Main main = new Main();
    	main.solveC();
    }
    
    private void solveA() {
    	Scanner sc = new Scanner(System.in);
    	int A = sc.nextInt();
    	int B = sc.nextInt();
	int X = sc.nextInt();	
    	System.out.println(A > X ? "NO" : (A+B >= X ? "YES" : "NO"));
    }

    private void solveB() {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
    	int M = sc.nextInt();
	int X = sc.nextInt();

	int[] a = new int[M];

	for(int i=0; i < M; i++){
	    a[i] = sc.nextInt();	    
	}

	int ans1=0;
	for(int i=X; i > 0; i--){
	    for(int j=0; j < M; j++){
		if (a[j] == i) ans1++;	    
	    }
	}

	int ans2=0;
	for(int i=X; i < N; i++){
	    for(int j=0; j < M; j++){
		if (a[j] == i) ans2++;	    
	    }
	}
	System.out.println(Math.min(ans1,ans2));
    }
    private void solveC() {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int[] X = new int[N];
	int[] Y = new int[N];

	for(int i=0; i < N; i++){
	    X[i] = sc.nextInt();	    
	}

	for(int i=0; i < N; i++){
	    Y[i] = X[i];	    
	}

	Arrays.sort(X);

	int ans1 = X[N/2 -1];
	int ans2 = X[N/2];

	for(int i=0; i < N; i++){
	    if (Y[i]<=ans1) System.out.println(ans2);
	    else System.out.println(ans1);
	}
       
    }
    private void solveD() {
	Scanner sc = new Scanner(System.in);
	System.out.println();
    }
}

Measured memory_bytes: 121096
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC066A
{
	class Program
	{
		static void Main(string[] args)
		{
			int a, b, c, s;

			string[] word = Console.ReadLine().Split();

			a = int.Parse(word[0]);
			b = int.Parse(word[1]);
			c = int.Parse(word[2]);

			int m = a;
			if (b > m) m = b;
			if (c > m) m = c;
			s = a + b + c - m;

			Console.WriteLine(s);

			//Console.ReadKey();
		}
	}
}


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

int main()
{
    int N, K;
    string S;

    cin >> N;
    cin >> S;
    cin >> K;

    for (int i = 0; i < N; i++)
    {
        if (S[i] != S[K - 1])
        {
            S[i] = '*';
        }
    }
    cout << S << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

#define N_MAX 20

int N;
pair<int, int> table[N_MAX][N_MAX];
int tmp[N_MAX];

bool makenext()
{
	bool last = true;
	for (int i = 0; i < N; i++){
		if (0 == tmp[i]){
			tmp[i] = 1;
			last = false;
			break;
		}
		else{
			tmp[i] = 0;
		}
	}

	return last;
}

void solv()
{
	scanf("%d", &N);
	int A[N_MAX];
	for (int i = 0; i < N; i++){
		scanf("%d", A + i);
		for (int j = 0; j < A[i]; j++){
			int x, y; scanf("%d%d", &x, &y);
			table[i][j] = make_pair(x, y);
		}
	}

	int ret = 0;
	fill(tmp, tmp + N, 0);
	while (true){
		bool valid = true;
		for (int i = 0; i < N; i++){
			if (0 == tmp[i]){
				continue;
			}
			for (int j = 0; j < A[i]; j++){
				if (table[i][j].second != tmp[table[i][j].first - 1]){
					valid = false;
					break;
				}
			}
			if (!valid){
				break;
			}
		}

		if (valid){
			int cnt = 0;
			for (int i = 0; i < N; i++){
				cnt += tmp[i];
			}
			ret = max(ret, cnt);
		}

		if (makenext()){
			break;
		}
	}

	printf("%d", ret);

	return;
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	solv();

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 128
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

int A,B,K,i,cnt;
inline void solve(){
  IN3(A,B,K);
  for(i=min(A,B);i;i--){
    if(A%i==0&&B%i==0){
      cnt++;
      if(cnt==K){
        OUT(i);
        return;
      }
    }
  }
}

int main(int argc,char**argv){
  BEGIN
  solve();
  END
}


Measured memory_bytes: 256
#include <cstdio>

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int ans = 1;
    for(int i = 1; i <= n; i++){
        if(ans * 2 <= ans + k){
            ans = ans * 2;
        }else{
            ans = ans + k;
        }
    }
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 128
from collections import defaultdict
d = defaultdict(int)
a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

S = input()
if S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

if len(S) < 26:
    for x in S:
        d[x] += 1
    for x in a:
        if d[x] == 0:
            print(S+x)
            exit()
else:
    i = 25
    while S[i-1] > S[i]:
        i -= 1
    ss = sorted(list(S[i-1:]))
    t = S[i-1]
    print(S[:i-1] + ss[ss.index(t)+1])


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

using namespace std;

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  vector<vector<int>> a(n, vector<int>(m));
  vector<bool> active(m, true);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &a[i][j]);
      a[i][j]--;
    }
  }
  int result = 0x3FFFFFFF;
  for (int i = 0; i < m; i++) {
    vector<int> counter(m, 0);
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        if (active[a[j][k]]) {
          counter[a[j][k]]++;
          break;
        }
      }
    }
    auto maxi = max_element(counter.begin(), counter.end());
    int idx = maxi - counter.begin();
    active[idx] = false;
    result = min(result, *maxi);
  }
  printf("%d\n", result);
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <stdlib.h>
using namespace std;
typedef long long int lld;
typedef long double ld;
lld ans = 0;
int main(void){
	string s;
	int k;
	cin >> s >> k;
	int tmp = 1;
	for(int p=1;p<s.size();p++){
		if(s[p]==s[p-1]) tmp++;
		else{
			ans += (lld)(tmp/2);
			tmp = 1;
		}
	}
	ans += (lld)(tmp/2);
	int num1 = 0;
	for(int p=0;p<s.size();p++){
		if(s[p]==s[s.size()-1]) num1++;
		else break;
	}
	int num2 = 0;
	for(int p=s.size()-1;p>=0;p--){
		if(s[p]==s[s.size()-1]) num2++;
		else break;
	}
	if(num1==num2&&num1==s.size()){
		printf("%lld",((lld)(s.size())*(lld)(k))/2);
		return 0;
	}
	ans = (ans*(lld)k);
	if(num1%2&&num2%2){
		ans += (lld)(k-1);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define It iterator
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;

int a,b,c,t;

int main() {
    //freopen("test.in","r",stdin);
    cin>>a>>b>>c;
    t=c*3;
    cout<<a<<" "<<b<<" " <<t-a-b<<endl;
    cout<<2*t-2*a-b-2*c<<" "<<c<< " " << 2*a+b+c-t<<endl;
    cout<<-t+a+b+c*2<<" "<<t-b-c<< " " << t-a-c<<endl;


    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int bit_search(int H, int W, int K, vector<vector<char>> c) {
    int sum = 0;
    vector<vector<char>> d;
    for (int bit_h = 0; bit_h < (1 << H); ++bit_h) {
        for (int bit_w = 0; bit_w < (1 << W); ++bit_w) {
            int black = 0;
            d = c;
            for (int i = 0; i < H; i++) {
                if (bit_h & (1 << i)) {
                    for (int j = 0; j < W; j++){
                        d.at(i).at(j) = '-';
                    }
                }
            }
            for (int j = 0; j < W; j++) {        
                if (bit_w & (1 << j)) {
                    for (int i = 0; i < H; i++) {
                        d.at(i).at(j) = '-';
                    }
                }
            }
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (d.at(i).at(j) == '#') black++;
                }
            }
            if (black == K) sum++;
        }
    }
    return sum;
}

int main(){
    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<char>> c(H, vector<char>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> c.at(i).at(j);
        }
    }
    int sum = bit_search(H, W, K, c);
    cout << sum << endl;
}

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

string s;
string ans;

bool dfs(string t) {
	if (t > s) { ans = t; return true; }
	
	char start;
	if (s.length() > t.length()) start = s[t.length()];
	else start = 'a';
	for (char c = start; c <= 'z'; c++) {
		int i;
		for (i = 0; i < t.length(); i++) if (c == t[i]) break;
		if (i < t.length()) continue;
		if (dfs(t + c)) return true;
	}
	return false;
}

int main() {
	cin >> s;
	if (dfs("")) cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

map<ll, ll> dp;
ll mod = 1000000007;

ll f(ll n) {
	if (dp[n]) return dp[n];
	if (n == 0) return dp[n] = 1;
	if (n % 2 == 0) return dp[n] = f(n / 2) + f(n / 2 - 1);
	return dp[n] = f(n / 2);
}

ll sum(ll n) {
	if (n == 0) return 1;
	else if (n % 2 == 0) return (3 * sum(n / 2 - 1) + f(n / 2)) % mod;
	else return (3 * sum(n / 2) - f(n / 2) + mod) % mod;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	int n;
	cin >> n;
	cout << sum(n) << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
    //cout<<"Hello World!";
    int a,b;
    cin>>a>>b;
    string x,y;
    int p=a;
    while(a--){
        y=y+to_string(b);
    }
    while(b--){
        x=x+to_string(p);
    }
    if(x[0]<=y[0]){
        cout<<x<<endl;
    }
    else cout<<y<<endl;
   // cout<<x<<y<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,int>a;
string s[10000005];
int ans;
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> s[i];
		if(a[s[i]] != 1){
			a[s[i]] = 1;
			ans++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 331756
n = int(input())
listV =  list(map(int,input().split()))
sortedListV = sorted(listV)

for i in range(0 , n-1):
    if (i != 0):
        result = (result + sortedListV[i+1]) / 2
    else:
        result = (sortedListV[i] + sortedListV[i+1]) / 2
print(result)

Measured memory_bytes: 3060
import fractions

def main():
    N, start = map(int, input().split())
    X = list(map(int, input().split()))
    dists = []
    for x in X:
        dists.append(abs(x - start))

    ans = dists[0]
    for d in dists[1:]:
        ans = fractions.gcd(ans, d)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 97408
import java.util.Scanner;
import java.util.Arrays;
import java.util.List;

public class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		int n, r, p, c;
		int card[] = new int[51];
		int nextCard[] = new int[51];
		while (true)
		{
			n = sc.nextInt();
			r = sc.nextInt();
			if (n == 0 && r == 0)
			{
				break;
			}
			for (int i = 1; i <= n; i++)
			{
				card[i] = n-i+1;
				nextCard[i] = n - i + 1;
			}
			for (int i = 0; i < r; i++)
			{
				p = sc.nextInt();
				c = sc.nextInt();
				for (int j = 1; j <= c; j++)
				{
					nextCard[j] = card[p - 1 + j];
				}
				for (int j = 1; j < p; j++)
				{
					nextCard[c + j] = card[j];
				}
				for (int j = 1; j <= n; j++)
				{
					card[j] = nextCard[j];
				}
				// for (int j = 1; j <= n; j++)
				// {
				// 	System.out.print(card[j] + " ");
				// }
				// System.out.println();
			}
			System.out.println(card[1]);
		}
		sc.close();
	}
}


Measured memory_bytes: 36804
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
  int n, W;
  cin >> n >> W;
  vector<ll> w(n), v(n);
  vector<vector<ll>> dp(n + 1, vector<ll>(W + 1));
  rep(i, n) {
    cin >> w[i] >> v[i];
  }

  rep(i, n) {
    for(int j = 0; j <= W; ++j) {
      dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
      if(j - w[i] >= 0) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);  
    }
  }
  cout << dp[n][W] << endl;

}

Measured memory_bytes: 80256
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(input())
    if N == 0:
        return False
    A = [int(readline()) for i in range(N)]
    k = int(readline())

    ans = 0
    left = 0; right = N-1
    while left <= right:
        mid = (left + right) >> 1
        v = A[mid]
        ans += 1
        if v == k:
            break
        if v < k:
            left = mid+1
        else:
            right = mid-1
    write("%d\n" % ans)
    return True
while solve():
    ...



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


int main(){
    
    long long n;cin>>n;
    vector<long long> v(n);
    vector<long long>freq(n+1,0);
    for(auto &i : v){
        cin>>i;
        freq[i]++;
    }
    long long ans=0;
    for( long long i=1;i<=n;i++){
        ans+=(freq[i]*(freq[i]-1)/2);
    }
    // cout<<ans<<"\n";
    for(long long i=0;i<n;i++){
        cout<<ans-(freq[v[i]]*(freq[v[i]]-1)/2)+((freq[v[i]]-1)*(freq[v[i]]-2)/2)<<"\n";
    }
}

Measured memory_bytes: 5760
use std::io;
use std::cmp::max;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let iter = buf.split_whitespace();
	let mut v: Vec<T> = Vec::new();
	for i in iter {
		v.push(i.parse().ok().unwrap());
	}
	v
}

fn main() {
	let v:Vec<i32> = procon_read();
	let n = v[0];
	let mut cntmax = 0;
	let mut ret = 1;
	for i in 1..(n+1) {
		let mut cnt = 0;
		let mut check = i;
		while check%2 == 0 {
			check = check/2;
			cnt += 1;
		}
		if cnt == max(cntmax, cnt) {
			ret = i;
			cntmax = cnt
		}
	}
	println!("{}", ret);
}

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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;
const ll MOD = 1000000007;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;

	vector<ll> l(n);
	for (auto &v : l) {
		cin >> v;
	}
	sort(begin(l), end(l));

	ll ans = 0;
	for (int a = 0; a < n; a++) {
		for (int b = a + 1; b < n; b++) {
			int r = lower_bound(begin(l), end(l), l[a] + l[b]) - begin(l);
			int s = b + 1;
			ans += r - (b + 1);
		}
	}

	// 0 1 2 3
	// b s g r
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
 
#define MASS_MAX 3
 
int main(void) {
	char mass[MASS_MAX];
	int i;
    int cnt = 0;
 
	scanf("%s", mass);
	for (i = 0; i < MASS_MAX; i++)
	{
		if (mass[i] == '1')
		{
			cnt++;
		}
	}
	printf("%d", cnt);
 
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define	BUCKET_SIZE	1000000


typedef struct hash_t{
	char str[13];
	struct hash_t *next;
}HASH_T;


HASH_T *TABLE[BUCKET_SIZE];


void Init_table()
{
	int i;


	for(i = 0; i < BUCKET_SIZE; i++)
		TABLE[i] = NULL;
}


unsigned int Hash(char *str)
{
	int i;
	int num;
	unsigned int sum = 0;


	for(i = 0; i < strlen(str); i++){
		if(str[i] == 'A')
			num = 1;
		else if(str[i] == 'C')
			num = 2;
		else if(str[i] == 'G')
			num = 3;
		else if(str[i] == 'T')
			num = 4;
		sum += num * pow(6, i);
	}

	return sum % BUCKET_SIZE;
}


int Hash_find(char *str)
{
	HASH_T *p;


	for(p = TABLE[Hash(str)]; p != NULL; p = p->next){
		if(!strcmp(str, p->str))
			return 1;
	}

	return 0;
}


int Hash_insert(char *str)
{
	HASH_T *p;
	int h;


	if(Hash_find(str))
		return 0;

	if( (p = (HASH_T *)malloc(sizeof(HASH_T))) == NULL){
		printf("malloc error\n");
		exit(1);
	}

	h = Hash(str);
	strcpy(p->str, str);
	p->next = TABLE[h];
	TABLE[h] = p;

	return 1;
}


int main()
{
	char in_str[30];
	char command[10], str[20];
	int command_n;
	int i;


	fgets(in_str, sizeof(in_str), stdin);
	sscanf(in_str, "%d", &command_n);

	Init_table();

	for(i = 0; i < command_n; i++){
		fgets(in_str, sizeof(in_str), stdin);
		sscanf(in_str, "%s %s", command, str);

		if(command[0] == 'i')
			Hash_insert(str);
		else if(command[0] == 'f'){
			if(Hash_find(str))
				printf("yes\n");
			else
				printf("no\n");
		}
	}

	return 0;
}


Measured memory_bytes: 18332
#include <stdio.h>

int min(int a,int b){
  if(a<=b){
    return a;
  }else{
    return b;
  }
}

int main(void){
  int N,A,B;
  int p;
  scanf("%d%d%d",&N,&A,&B);
  int counter[3] = {0,0,0};

  for(int i = 0;i<N;i++){
    scanf("%d",&p);
    if(p<=A){
      counter[0]++;
    }else if(p>A && p<=B){
      counter[1]++;
    }else{
      counter[2]++;
    }
  }

  if(counter[1]<counter[2]){
    printf("%d\n",min(counter[0],counter[1]));
  }else{
    printf("%d\n",min(counter[0],counter[2]));
  }

  return 0;
}

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

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


    int length = s.length();
    int i = length - 1;

    int lengthW = 0;
    int minB = i;

    long ans = 0;

    while (1) {
        if (i < 0) {
            break;
        }

        if (s.at(i) != 'B') {
            i--;
            lengthW++;

            continue;
        }

        ans += lengthW;
        i--;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
 
int main() {
  int N;
  double sum = 0.0d, temp;
  
  std::cin >> N;
  
  for (int i=0; i<N; ++i) {
  	std::cin >> temp;
    sum += 1.0d / temp;
  }
  
  std::cout << std::setprecision(10) << std::fixed << 1.0d / sum << std::endl;
}

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

typedef long long ll;
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define fork(i, n) for (ll i = 0; i < (n); i++)
#define forn for (ll i = 0; i < (n); i++)
#define fori(i, k, n) for (ll i = k; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define en '\n'
#define FILL(x, v) memset(x, v, sizeof(x))
#define pb push_back
#define fast                     \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(NULL);

template <typename A, typename B>
inline void chmin(A &a, B b)
{
	if (a > b)
		a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b)
{
	if (a < b)
		a = b;
}
template <typename T>
void print(vector<T> &a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
template <typename T>
void print(deque<T> &a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
template <typename T>
void print(vector<vector<T>> &a)
{
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[i].size(); j++)
			cout << a[i][j] << ' ';
		cout << en;
	}
}
const int mxn = 5e5;
const int M = 1e9 + 7;

ll pw(ll b, ll e)
{
	ll res = 1;
	while (e)
	{
		if (e % 2)
			res = (res * b) % M;
		b = (b * b) % M;
		e >>= 1; // e/=2;
	}
	return res;
}

ll iv[mxn + 1], f1[mxn + 1], f2[mxn + 1];
ll nck(int n, int k)
{
	return f1[n] * f2[k] % M * f2[n - k] % M;
}

int main()
{
	fast;
	iv[1] = 1;
	for (int i = 2; i <= mxn; ++i)
		iv[i] = M - M / i * iv[M % i] % M;
	f1[0] = f2[0] = 1;
	for (int i = 1; i <= mxn; ++i)
	{
		f1[i] = f1[i - 1] * i % M;
		f2[i] = f2[i - 1] * iv[i] % M;
	}
	int n, m;
	cin >> n >> m;
	ll ans = 0;
	for (int i = 0; i <= n; ++i)
	{
		ll c = i & 1 ? M - 1 : 1;
		c = c * nck(n, i) % M * nck(m, i) % M * f1[i] % M * nck(m - i, n - i) % M * nck(m - i, n - i) % M * f1[n - i] % M * f1[n - i] % M;
		ans = (ans + c) % M;
	}
	cout << ans;
}

Measured memory_bytes: 15376
N = int(input())
h = [int(i) for i in input().split()]

# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
      
dp=[1000000000]*N
dp[0]=0
#dp[1]=abs(h[1]-h[0])
 
#配るDP
for i in range(N-1):
    #print(abs(h[i]-h[i+1])+dp[i],dp[i+1],abs(h[i]-h[i+2])+dp[i],dp[i+2])
    dp[i+1]=chmin(abs(h[i]-h[i+1])+dp[i],dp[i+1])
    if i < N-2:
        dp[i+2]=chmin(abs(h[i]-h[i+2])+dp[i],dp[i+2])
    
print(dp[-1])

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

int a,b;
int main()
{
    cin>>a>>b;
	
	int c=a+b;
	int d=a-b;
	int e=a*b;
	int t;
	
	t=max(c,d);
	t=max(t,e);
	cout<<t<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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

	int N;
	cin >> N;


	int dp[2001] = {};

	dp[0] = 1;
	const int mod = 1e9 + 7;
	rep(i, N - 1) {
		for (int j = i + 3; j <= N; j++) {
			dp[j] += dp[i];
			dp[j] %= mod;
		}
	}

	co(dp[N]);

	Would you please return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define DEBUG2(x, y) cerr << #x << ": " << x << " " << #y << ": " << y << "\n"
#define DEBUG3(x, y, z) cerr << #x << ": " << x << " " << #y << ": " << y << " " << #z << ": " << z << "\n"
#define PRINTALL(V)    \
  for (auto v : (V)) { \
    cerr << v << " ";  \
  }                    \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
#define pint pair<int, int>
#define ld long double
using namespace std;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> using vec = std::vector<T>;
template <class T> void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N;
  string s, t;
  cin >> N >> s >> t;
  int i = N;
  for (; i >= 0; i--) {
    string sp = s.substr(N - i, i);
    string tp = t.substr(0, i);

    if (sp == tp) {
      break;
    }
  }
  print(2 * N - i);
}

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

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

  bool is_yes = false;
  
  for(int i = 0; i < 26; ++i){
    for(int j = 0; j < 15; ++j){
      int total = 4 * i + 7 * j;

      if(total == num){
        is_yes = true;
        break;
      }
      else continue;
    }
    if(is_yes == true) break;
    else continue;
  }

  if(is_yes == true) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
  
}


Measured memory_bytes: 384
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int main()
{
  int n,k;
  for(;cin>>n>>k,n;)
    {
      int has[n+2];
      int lists[n+2];
      memset(has,false,sizeof(has));
      lists[n+1]=0;
      bool zero=false;
      for(int i=0;i<k;i++)
	{
	  int tmp;
	  cin>>tmp;
	  if(tmp!=0)
	    has[tmp]=true;
	  else
	    zero=true;
	}
      for(int i=n;i>0;i--)
	{
	  int tmp=0;
	  if(has[i])
	    tmp=lists[i+1]+1;  
	  lists[i]=tmp;
	}
      int ans=0;
      for(int i=1;i<=n;i++)
	{
	  int tmp=lists[i];
	  if(zero && i+tmp+1<=n)
	    {
	      //	      cout<<"i:"<<i<<" "<<lists[i]<<endl;
	      //      cout<<"i+tmp+1:"<<i+tmp+1<<" "<<lists[i+tmp+1]<<endl;
	      tmp+=1+lists[i+tmp+1];
	    }
	  ans=max(ans,tmp);
	  //	  i+=tmp+1;
	  //	  cout<<"@i:"<<i<<endl;
	}
      cout<<ans<<endl;
    }

}

Measured memory_bytes: 1948
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
	string s;
	cin >> s;
	cout << s[0] << s.length()-2 << s[s.length()-1] << endl;
	return 0;
}

Measured memory_bytes: 256
from sys import stdin
from copy import deepcopy
import queue

class Dice:
    def __init__(self, nums):
        self.labels = [None] + [ nums[i] for i in range(6) ]
        self.pos = {
            "E" : 3,
            "W" : 4,
            "S" : 2,
            "N" : 5,
            "T" : 1,
            "B" : 6
        }

    def rolled(dice, queries):
        d = deepcopy(dice)
        for q in queries:
            if q == "E":
                d.pos["T"], d.pos["E"], d.pos["B"], d.pos["W"] = d.pos["W"], d.pos["T"], d.pos["E"], d.pos["B"]
            elif q == "W":
                d.pos["T"], d.pos["E"], d.pos["B"], d.pos["W"] = d.pos["E"], d.pos["B"], d.pos["W"], d.pos["T"]
            elif q == "S":
                d.pos["T"], d.pos["S"], d.pos["B"], d.pos["N"] = d.pos["N"], d.pos["T"], d.pos["S"], d.pos["B"]
            elif q == "N":
                d.pos["T"], d.pos["S"], d.pos["B"], d.pos["N"] = d.pos["S"], d.pos["B"], d.pos["N"], d.pos["T"]
        else:
            return d

nums = [int(x) for x in stdin.readline().rstrip().split()]
q = int(stdin.readline().rstrip())
dice = Dice(nums)

# TとSに対応するクエリを記憶し, resをすぐに呼び出せるようにする
memo = [[False] * 7 for i in range(7)]
memo[dice.pos["T"]][dice.pos["S"]] = ""

# クエリとさいころの東面を記憶
res = { "" : dice.labels[dice.pos["E"]] }

# BFSで探索, 解を求めたらreturn Trueで抜け出す
# diceの中身をいじってはならない
def solve(T, S):
	if isinstance(memo[T][S], str):
		return memo[T][S]

	que = queue.Queue()
	que.put(dice)
	sol_q = ["E", "N", "S", "W"]
	
	while not que.empty():
		d = que.get()
		if d.pos["T"] == T and d.pos["S"] == S:
			break
		else:
			for i in sol_q:
				d_next = Dice.rolled(d, i)
				que.put(d_next)
				memo[d_next.pos["T"]][d_next.pos["S"]] = memo[d.pos["T"]][d.pos["S"]] + i
				res[memo[d_next.pos["T"]][d_next.pos["S"]]] = d_next.labels[d_next.pos["E"]]
	else:
		return memo[T][S]

for i in range(q):
    ts = [int(x) for x in stdin.readline().rstrip().split()]
    T = dice.labels.index(ts[0])
    S = dice.labels.index(ts[1])
    
    if solve(T, S) != False:
        print(res[memo[T][S]])


Measured memory_bytes: 7100
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define SORT(c) sort((c).begin(),(c).end())
#define MOD 1000000007 //S.size() 配列名.Length()
using namespace std;
typedef unsigned long long ll;

int main(void){
	int n;
	cin >> n;
	map<string, int> mp;
	rep(i, n){
		string s;
		cin >> s;
		SORT(s);
		mp[s]++;
	}

	ll ans = 0;
	for(auto x : mp){
		int num = x.second;
		ans += (ll)num * (num - 1) / 2;
	}

	cout << ans <<endl;

	return 0;
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
 
 
int main() 
{
    int N,X;
    cin>>N>>X;
    vector<int>D(N+2),L;
    for (int i = 0; i < N; i++)
    {
        int l;
        cin>>l;
        L.push_back(l);
    }
    D.push_back(0);
    for (int i = 1; i < N+2; i++)
    {
        D[i]=D[i-1]+L[i-1];
    }
 
    auto it = upper_bound(D.begin(),D.end(),X);
    if(it==D.end())
    {
        cout<<N+1<<endl;
        return 0;
    }
 
    auto ans=distance(D.begin(),it);
    cout<<ans<<endl;
    
    return 0;   
}

Measured memory_bytes: 3616
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <random>

#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef long long int ll;
const ll INF = 10000000000;
const double PI = acos(-1);
const ll mod = 1000000007;

int main()
{
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
    return 0;
}


Measured memory_bytes: 3608