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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acos(-1);

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

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 (b<a) { a=b; return 1; } return 0; }

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int n; cin >> n;
	pair<pair<string, int>, int> p[n];
	rep(i, n){
		string s;
		int t;
		cin >> s >> t;
		string tmp = s;
		p[i] = make_pair(make_pair(s, -t), i);
	}

	sort(p, p+n);

	rep(i, n) cout << p[i].second+1 << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
o = {}
for i in range(n):
    name, value = input().split()
    if name in o:
        o[name] += int(value)
    else:
        o[name] = int(value)
o = sorted(o.items(), key=lambda x: x[0])
o.sort(key = lambda x: len(x[0]))
for i in o:
    print("{0} {1}".format(i[0], i[1]))


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

int main(){
  long long  N , K ; 
  cin >> N >> K ;
  vector<long long > A(N) ; 
  long long  L = 1 ;
  long long R = 1 ; 
  
  for(int i = 0 ; i < N ; i++){
    cin >> A.at(i) ; 

  }
    for(int i = 0 ; i < K   ; i++){
      L =  L * A.at(i) ; 
    }


  for(int i = K ; i < N ; i++){
  //  cout << L << endl; 
    R =(  A.at(i))*L / A.at(i-K) ; 
    
    if(A.at(i-K) < A.at(i)){
     cout << "Yes" << endl ;  
    }
    else{
     cout << "No" << endl ; 
    }

    L = R  ;

  }

    //    cout << L << endl ; 
}

Measured memory_bytes: 4840
use proconio::input;
// use std::collections::HashMap;

#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize,
        K: usize,
        mut Hs: [i32; N],
    }

    // 高さについて、連続で選んだほうが差が小さくなる
    Hs.sort();

    let mut ans = std::i32::MAX;
    for i in 0..N - 1 {
        let bigger_ind = i + K - 1;

        if bigger_ind > (N - 1) {
            break;
        }


        let diff = Hs[bigger_ind] - Hs[i];
        if diff < ans {
            ans = diff;
        }
    }

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


Measured memory_bytes: 3620
n,w = map(int,input().split())
vw = [list(map(int,input().split())) for _ in range(n)]

dp = [[0]*(w+1) for _ in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if vw[i][0]>j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-vw[i][0]]+vw[i][1])
            #[print(*dp[l]) for l in range(n+1)]
            #print("---------------")            
print(dp[n][w])

Measured memory_bytes: 150092
from itertools import combinations

N = int(input())
lst = [0, 0, 0, 0, 0]
for _ in range(N):
    s = input()[0]
    if s == "M":
        lst[0] += 1
    elif s == "A":
        lst[1] += 1
    elif s == "R":
        lst[2] += 1
    elif s == "C":
        lst[3] += 1
    elif s == "H":
        lst[4] += 1

ret = 0
for a, b, c in combinations(lst, 3):
    ret += a * b * c

print(ret)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  string s;
  cin >> s;
  int ans=0;
  vector<int> a(5);
  rep(i, 3){
    if(s[i]=='R'){
      a[i+1]=a[i]+1;
    } else {
      a[i+1]=0;
    }
    ans=max(ans, a[i+1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3564
#include <stdio.h>

int main(void){
	long A,B,i;
	scanf("%ld %ld", &A,&B);
	for (i = 1; i <= B; i++) {
		if ((i*A) % B == 0) {
			printf("%ld", i*A);
			return 0;
		}
	}
}

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

int main()
{
    int n;

    cin >> n;

    int a[n + 5];

    for(int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);

    for(int i = 0; i < n - 1; i++){
        if(a[i] == a[i + 1]){
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;

    return 0;
}


Measured memory_bytes: 1024
S = gets.chomp

if S.length == 26
  start = S.length - 1
  index = start
  start.downto(1) do |i|
    if S[i] < S[i-1]
      index = i - 1
    else
      break
    end
  end

  if index == 0
    puts -1
    exit 0
  end

  ch = S[-1]
  index.upto(S.length - 1) do |i|
    if S[i] > S[index-1]
      ch = S[i]
    end
  end

  if index == 1
    puts ch
  else
    puts S[0..(index-2)] + ch
  end
else
  ('a'..'z').each do |s|
    if !S.include?(s)
      puts S + s
      break
    end
  end
end


Measured memory_bytes: 1788
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>
//#include <ostream>


using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  ll n;
  cin >> n;
  vector<ll> A(n);
  rep(i,n)cin >> A[i];
  vector<ll> cnt(200010,0);
  rep(i,n)cnt[A[i]]++;
  ll ans = 0;
  rep(i,200010){
    if(cnt[i]>=2)ans += (cnt[i]*(cnt[i]-1))/2;
  }

  for(int i = 1;i <= n;i++){
    ll sa = cnt[A[i-1]]-1;
    cout << ans -sa << endl;
  }




}


Measured memory_bytes: 5760
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int z = 0;
        int i = 0;
        for(int kk=0;kk<1000000;kk++){
            int n = sc.nextInt();
            if(n==0){
                System.exit(0);
            }else{
                int a[] = new int[n]; 
                a[0]= sc.nextInt();
                for(i=1;i<n;i++){
                    a[i] = sc.nextInt();
                    if((a[i-1]+1)==a[i]){
                    }else{
                        if(a[z]==a[i-1]){
                            System.out.print(a[i-1]+" ");
                            z=i;
                        }else{
                            System.out.print(a[z]+"-"+a[i-1]+" ");
                            z=i;
                        }
                    }
                }
                if(a[z]==a[i-1]){
                    System.out.print(a[i-1]);
                }else{
                    System.out.print(a[z]+"-"+a[i-1]);
                }
                System.out.println();
                z=0;
            }
        }
    }
 
}

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

int main(){
    string s, t;
    cin>>s>>t;
    if (s == t.substr(0,s.size())) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3580
#include <stdio.h>

int f(int x){
	return x*x;
}

int main(void){
	int d = 0;
	int len = 600;
	int n = 0;
	int sum = 0;
	while(scanf("%d", &d) != EOF){
		n = len / d;
		sum = 0;
		for(int i=0; i<n; ++i){
			sum += f(d*i)*d;
		}
		printf("%d\n", sum);
	}
	return 0;
}

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

//-----------------------------------------------

//------------------------------------------------
int main(){
  double w,h,x,y,s;
  cin>>w>>h>>x>>y;
  int ans=0;
  s=w*h/2;
  if(x==w/2 && y==h/2) ans+=1;
cout<<s<<endl<<ans<<endl;
}



Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1ll << 60;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

ll N, K, ans;
int main(){
  scanf("%lld%lld", &N, &K);
  for (ll i = K; i <= N + 1; i++){
    ll now = i * (2 * N - i + 1) / 2;
    now -= i * (i - 1) / 2 - 1;
    ans += now; ans %= MOD;
  }
  printf("%lld\n", ans);

  return 0;
}


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

using ll = long long;

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

int main(){
    int N;
    cin >> N;
    int mo = 1000000007;
    ll pro10 = 1, pro9 = 1, pro8 = 1;
    rep(i, N){
        pro10 *= 10;
        pro10 %= mo;
        pro9 *= 9;
        pro9 %= mo;
        pro8 *= 8;
        pro8 %= mo;
    }
    pro10 += mo;
    pro9 += mo;
    pro9 *= 2;
    pro9 -= pro8;
    pro9 %= mo;
    pro10 -= pro9;
    pro10 %= mo;
    cout << pro10 << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int mojikaku (string s){
  cout << s << endl;
  return 0;
}
int suujikaku (int t){
  cout << t <<endl;
}

int main(){
  int x,y;
  cin >> x >> y;
  
 int z=x+y/2;
  suujikaku(z);
  
}

Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, n) for(int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<60);
const ld pi=acosl(1);
const ll mod = 1000000007;
//const ll mod = 998244353;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};

void solve(){
  ll n;cin>>n;
  vector<ll>a(n);
  rep(i,n)cin>>a[i];

  map<ll,ll>mE;
  map<ll,ll>mO;
  rep(i,n){
    if(i%2==0)mE[a[i]]++;
    else mO[a[i]]++;
  }
  vector<pair<ll,ll>>E;
  vector<pair<ll,ll>>O;
  for(auto&i:mE)E.push_back(make_pair(i.second,i.first));
  for(auto&i:mO)O.push_back(make_pair(i.second,i.first));
  E.push_back(make_pair(0,-1));
  O.push_back(make_pair(0,-2));
  sort(all(E),greater<pair<ll,ll>>());
  sort(all(O),greater<pair<ll,ll>>());

  if(E[0].second!=O[0].second){
    cout<<n-E[0].first-O[0].first<<endl;
  }else{
    cout<<min(n-E[0].first-O[1].first,n-E[1].first-O[0].first)<<endl;
  }
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);cout<<fixed;
  cout<<setprecision(30);
  solve();
}


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

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

  // 数字ごとに登場する index を管理する
  //
  // 例 S = 123123の場合
  // 1: 0, 3
  // 2: 1, 4
  // 3: 2, 5
  //
  vector<vector<int>> v(10, vector<int>(0));
  for (int i = 0; i < n; i++) {
    int a = s.at(i) - '0';
    v.at(a).push_back(i);
  }

  int ans = 0;
  // 000〜999 について、貪欲法で探索する
  for (int i = 0; i < 1000; i++) {
    string t = to_string(i);
    int digit = 3 - (int)t.size();
    for (int i = 0; i < digit; i++) {
      t = '0' + t;
    }

    // 3文字の数を、数字として取得
    int x = t.at(0) - '0';
    int y = t.at(1) - '0';
    int z = t.at(2) - '0';
    // index に存在しない場合はスキップ
    if (v.at(x).size() == 0) { continue; }
    if (v.at(y).size() == 0) { continue; }
    if (v.at(z).size() == 0) { continue; }

    // 1文字目の数字を index の開始位置となる
    int index = v.at(x).at(0);
    auto itr_y = upper_bound(v.at(y).begin(), v.at(y).end(), index);
    // 2文字目が見つからなかった場合
    if (itr_y == v.at(y).end()) { continue; }

    auto itr_z = upper_bound(v.at(z).begin(), v.at(z).end(), *itr_y);
    // 3文字目が見つからなかった場合
    if (itr_z == v.at(z).end()) { continue; }

    // 3文字とも見つかった場合はインクリメント
    ans++;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3844
#include <stdio.h>

#define STR_MAX	10

int main(void)
{
	char str_in[STR_MAX + 1] = {'\0'};
	char str_out[STR_MAX + 1] = {'\0'};
	char *pOut;
	int cnt;

	scanf("%s", str_in);

	pOut = str_out;
	for (cnt = 0; ((str_in[cnt] != '\0') && (cnt < STR_MAX)); cnt++) {
		if (str_in[cnt] == '0') {
			*pOut = '0';
			pOut++;
		} else if (str_in[cnt] == '1') {
			*pOut = '1';
			pOut++;
		} else if ((str_in[cnt] == 'B') && (pOut != &str_out[0])) {
			pOut--;
			*pOut = '\0';
		} else {
			;
		}
	}

	printf("%s\n", str_out);

	return 0;
}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> foods(m, 0);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int l = 0; l < k; l++) {
            int a;
            cin >> a;
            a--;
            foods[a]++;
        }
    }

    int ans = 0;
    for (auto e : foods) {
        if (e == n) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = [0]*n
b = [0]*n
c = [0]*n
for i in range(n):
  a[i],b[i],c[i] = na()
dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)

for i in range(1,n):
  dpa[i] = max(dpb[i-1],dpc[i-1])+a[i]
  dpb[i] = max(dpa[i-1],dpc[i-1])+b[i]
  dpc[i] = max(dpb[i-1],dpa[i-1])+c[i]
  
print(max(dpa[-1],dpb[-1],dpc[-1]))



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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int3(a, b, c);
    int2(x, y);

    int ans = 0;
    if (a + b > c + c) {
        int tmp = min(x, y);
        ans += tmp * (c + c);
        int ans1 = ans + (x - tmp) * a + (y - tmp) * b;
        cout << min(ans1, max(x, y) * (c + c)) << endl;
    } else {
        cout << ans + x * a + y * b << endl;
    }



    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
a = []
for i in range(N):
	a.append(list(map(int, input().split())))
x = sorted(a)
cost = 0
k = 0
while x[k][1] < M:
	cost = cost +x[k][0] * x[k][1]
	M = M - x[k][1]
	k = k + 1
cost = cost + x[k][0] * M
print(cost)


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

int main() {
  int A, B, K; cin>>A>>B>>K;
  set<int> s;
  for(int i = 0; i < K; i++) {
     int C = A + i, D = B-i;
    if(C >= A && C <= B) s.insert(C);
    if(D >= A && D <= B) s.insert(D);
  }
  //cout << "SIZE = " << s.size() << endl;
  for(auto n : s) {
    cout << n << endl;
  }
  return 0;
}


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

int main() {

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    int sum = 0;
    rep(i, n){
        cin >> a[i];
        sum += a[i];
    }

    int cnt = 0;
    int ok = (sum+4*m-1) / (4*m);
    rep(i, n){
        if(a[i] >= ok){
            cnt++;
        }
    }

    if(cnt >= m){
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

    return 0;
}

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

namespace B_018_43
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            new Logic_A().Start();//OK
            Console.ReadLine();
        }

        public class Logic_A
        {
            public void Start()
            {
                var N = Convert.ToInt32(Console.ReadLine());

                Console.WriteLine(N * (N + 1) / 2);
            }
        }
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long

using namespace std;

int n;
unordered_map<int, int> test[20];

int calc(int honest_people[]) {
  int count = 0;

  // cout << "honest_people:" << endl;
  // // for (int i = 0; i < honest_people.size(); i++) {
  // for (int i = 0; i < n; i++) {
  //   if (i > 0) {
  //     cout << ",";
  //   }
  //   cout << honest_people[i];
  // }
  // cout << endl;

  for (int p = 1; p <= n; p++) {
    if (honest_people[p] != 1) {
      continue;
    }

    bool honest = true;
    bool error = false;
    for (int t = 1; t <= n; t++) {
      if (honest_people[t] != 1) {
        continue;
      }
      if (t == p) {
        continue;
      }
      if (test[t][p] == 0) {
        honest = false;
        error = true;
        break;
      }
    }

    // self testimony
    for (int d = 1; d <= n; d++) {
      if (honest_people[d] != 0) {
        continue;
      }

      if (test[p][d] == 1) {
        honest = false;
        error = true;
        break;
      }
    }

    if (error) {
      count = 0;
      break;
    }
    if (honest) {
      count++;
    }
  }

  return count;
}

int main() {
  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {
    int tnum;
    scanf("%d", &tnum);

    for (int j = 1; j <= n; j++) {
      test[i][j] = -1;
    }

    for (int j = 0; j < tnum; j++) {
      int person, honesty;
      scanf("%d %d", &person, &honesty);
      test[i][person] = honesty;
    }
  }

  // for (int i = 1; i <= 3; i++) {
  //   for (int j = 1; j <= 3; j++) {
  //     cout << test[i][j] << " ";
  //   }
  //   cout << endl;
  // }

  int current = 0;
  int ans = 0;

  for (;;) {
    // unordered_map<int, int> patterns;
    int honest_people[20];
    for (int i = 0; i < 20; i++) {
      honest_people[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
      int flag = (current & (1 << (i - 1)));
      if (flag >= 1) {
        // patterns[i] = 1;
        // honest_people.emplace_back(i);
        honest_people[i] = 1;
      }
    }

    int count = calc(honest_people);

    // cout << "count:" << count << endl;
    ans = max(ans, count);

    current += 1;

    if ((current & (1 << n))) {
      break;
    }
  }

  cout << ans << endl;
}

// 3
// 1
// 2 1
// 1
// 1 1
// 1
// 2 0

Measured memory_bytes: 384
import java.util.*;
public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	long[]a = new long[87];
	a[0]=2;a[1]=1;
	int N = sc.nextInt();
	for(int i=2;i<=N;i++) {
		a[i] = a[i-1] + a[i-2];
	   }
	System.out.println(a[N]);
	}
}


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

#define removeDuplicate(a) sort(a.begin(), a.end()); a.resize(distance(a.begin(), unique(a.begin(), a.end())));


const int N = 6e5 + 10; 

int n;
int a[N];  
set<int> *q[N]; 

void merge (set<int> *&a, set<int> *&b) {
	if (a -> size() > b -> size()) { 
		for (auto value : *b) { 
			a -> insert(value); 
		}
		b -> clear(); 
	}
	else { 
		for (auto value : *a) { 
			b -> insert(value); 
		}
		a -> clear(); 
		a = b; 
	}
}

void zip () { 
	vector<int> rar; 
	for (int i = 1; i <= n; i++) { 
		rar.push_back(a[i]); 
	}
	removeDuplicate(rar); 
	for (int i = 1; i <= n; i++) { 
		a[i] = lower_bound(rar.begin(), rar.end(), a[i]) - rar.begin() + 1; 
	}
}

int main()
{
    #define file "9"
    //freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);

    cin >> n; 
    for (int i = 1; i <= 3 * n; i++) { 
    	q[i] = new set<int>; 
    }
    for (int i = 1; i <= n; i++) { 
    	int value; 
    	cin >> value;
    	a[i] = value;  
    }
    zip(); 
    for (int i = 1; i <= n; i++) { 
    	q[i] -> insert(a[i]); 
    }
    long long ret = 0; 
    int front = 1, back = n; 
    for (int value = 1; value <= n; value++) { 
    	for (int i = front; i <= back; i++) { 
    		merge(q[back + 1], q[i]);
    		front++;  
    		if (q[back + 1] -> find(value) != q[back + 1] -> end()) { 
    			break; 
    		}
    	}
    	back++; 
    	q[back] -> erase(value); 
    	if (q[back] -> empty()) { 
    		back--; 
    		continue; 	
    	}
    	ret += ((int)(q[back] -> size()));
    }
    cout << ret << endl; 
    return 0;
}




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

#pragma GCC optimize("O3")
#pragma GCC target("sse4")
// io
#define get(i) scanf("%d", &i)
#define flush fflush(stdin)

// manipulations
#define f(i, n) for (int i = 0; i < n; i++)
#define fr(i, n) for (int i = n - 1; i >= 0; i--)
#define ff(i, a, b) for (int i = a; i <= b; i++)
#define sz(x) int((x).size())
#define fi first
#define se second

// built-in
#define bitcount __builtin_popcount
#define gcd __gcd

// short
#define pb push_back
#define fill(arr, a) memset(arr, a, sizeof(arr))
#define mp(a,b) make_pair(a,b)

// useful bits
#define IN(i,l,r) (i >= l && i <= r);
#define relax(a,b) a = max(a,b);
#define relaxi(a,b) a = min(a,b);

typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;

ll modpow(ll a, ll b, ll mod = (ll) (1e9 + 7)) 
{if (!b) return 1; a %= mod; return modpow(a * a % mod, b / 2, mod) * (b & 1 ? a : 1) % mod;}

// for rand
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// use uniform_int_distribution<int>(0, i)(rng)



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
//	freopen("output.txt", "w" , stdout);
	/* freopen("in.txt" , "r" , stdin); */
	/* clock_t start = clock(); */
	#endif
	int n;
	cin >> n;
	double a[n];
	for(int i = 0 ; i < n ; i++)
		cin >> a[i];
	sort(a, a+n);
	double ans = 0;
	ans = (a[0]+a[1])/2;
	for(int i = 2; i< n; i++){
		/* cerr << ans << endl; */
		ans = (a[i]+ans)/2;
	}
	cout << ans << endl;

	#ifndef ONLINE_JUDGE
	/* cout << setprecision(12) << ld(clock()-start) / CLOCKS_PER_SEC << endl; */
	#endif
	return 0;
}



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

int main(){
    int N;
    int A[210];

    cin >> N;

    for (int i=0; i<N; i++){
        cin >> A[i];
    }

    int count = 0;

    while (true){
        bool exist_odd = false;
        for (int i=0; i<N; i++){
            if (A[i] % 2 != 0) exist_odd =true;
        }

        if (exist_odd) break;

        for (int i=0; i<N; i++){
            A[i] /= 2;
        }
        count++;
    }



    cout << count << endl;
}

Measured memory_bytes: 256
N,K = [int(i) for i in input().split()]
R,S,P = [int(i) for i in input().split()]
T = input()

def cal(t):
    if t=="r":
        return (t,P)
    elif t=="s":
        return (t,R)
    elif t=="p":
        return (t,S)
point = 0
for i in range(K):
    count = i
    data = []
    while count < N:
        data.append(cal(T[count]))
        count += K
    n = "q"
    for j in data:
        if n != j[0]:
            point += j[1]
            n = j[0]
        else:
            n = "q"

print(point)

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

#define LINE_BUF_SIZE 100

int main(){

    int i,j,k;
    int max = 0;
    int count = 0;
    int M,N,v;
    char line[LINE_BUF_SIZE];

    fgets(line,sizeof(line),stdin);
    sscanf(line,"%d", &N);

    long int A[N+2];

    A[0] = 0;
    A[N+1] = 0;

    for(i=1;i<=N;i++){
        scanf("%d",&v);
        A[i] = v;
    }

    long int ans = 0;

    for(i=0;i<=N;i++){              /*本来の金額*/
        ans += fabs(A[i+1]-A[i]);
    }

    int ans_hold = ans;

    for(i=1;i<=N;i++){   /*最後は残す*/

        if(A[i+1] > A[i] && A[i] > A[i-1]){
            printf("%d\n",ans);
        }

        else{
            ans = ans - (fabs(A[i-1]-A[i]) + fabs(A[i+1]-A[i])) + fabs(A[i+1]-A[i-1]);
            printf("%d\n",ans);
            ans  = ans_hold;
        }
    }

    return 0;

}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main() {
  ll n;
  cin >> n;
  ll ans = 1e18;
  for(ll i=1; i*i<=n; i++) {
    if(n%i != 0) continue;
    ans = min(i+n/i-2, ans);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	if (a >= 2 + b)
	{
		cout << a + a - 1 << endl;
	}
	else if (b >= 2 + a)
	{
		cout << b + b - 1 << endl;
	}
	else
	{
		cout << a + b << endl;
	}
	return 0;
}
/*
死のマウス
.　　あり許せん！
　　　∧＿＿∧
　|| （＃｀Д´ ） ||
　|| ( |　 　| | |||
　从| |　 　| |从从
￣) ⊂ノ￣￣!_つ￣て
　フヘ(　　　　ヽヘ(＼

*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int N, arr[3][3], b[10];
bool brr[3][3];
int main() {
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 3; j++) cin >> arr[i][j];
	}
	cin >> N;
	for(int i = 0; i < N; i++) cin >> b[i];
	for(int i = 0; i < N; i++) {
 	    for(int j = 0; j < N; j++) {
			brr[i][j] = false;
			 for(int k = 0; k < N; k++) {
				if(arr[i][j] == b[k]) brr[i][j] = true;
			}
		}
	}
	string ans = "No";
 	for(int i = 0; i < 3; i++) {
 		if(brr[i][0] and brr[i][1] and brr[i][2]) ans = "Yes";
	}
	for(int i = 0; i < 3; i++) {
 		if(brr[0][i] and brr[1][i] and brr[2][i]) ans = "Yes";
	}
	if(brr[0][0] and brr[1][1] and brr[2][2]) ans = "Yes";
	if(brr[0][2] and brr[1][1] and brr[2][0]) ans = "Yes";
	
	
	cout << ans << endl;

}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 1001001001;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

const int mod = 1e9 + 7;

int n;
vector<vector<P>> tos;
vector<int> rFroms;

void bfs(int target, int d) {
    if(rFroms[target] != -1) return;
    rFroms[target] = d;
    auto to = tos[target];
    for (auto t : to) {
        bfs(t.first, (d + t.second) % 2);
    }
}


int main() {
    cin >> n;

    tos = vector<vector<P>>(n);
    rFroms = vector<int>(n, -1);

    rep(i, n - 1) {
        int from, to, distance;
        cin >> from >> to >> distance;
        from--;
        to--;
        tos[from].emplace_back(to, distance % 2);
        tos[to].emplace_back(from, distance % 2);
    }


    bfs(0, 0);

    for (auto r : rFroms) {
        cout << r << endl;
    }

}



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

using namespace std;

const int MOD = 1000000007;

int main() {
  int n, k;
  cin >> n >> k;

  vector<int> a(n + 1, 0);
  // 1-index で受け取る
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  // dp[i][j] := i番目の人まででj個のアメちゃんを分けるときの場合の数
  vector<vector<long long>> dp(n + 10, vector<long long>(k + 10, 0));
  vector<vector<long long>> dp_sum(n + 10, vector<long long>(k + 10, 0));
  for (int j = 0; j <= k; j++) {
    dp_sum[0][j] = 1;
  }

  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      dp[i][j] = dp_sum[i - 1][j];
      if (j - a[i] - 1 >= 0) {
        dp[i][j] -= dp_sum[i - 1][j - a[i] - 1];
      }
      dp_sum[i][j] = dp[i][j];
      if (j - 1 >= 0) {
        dp_sum[i][j] += dp_sum[i][j - 1];
      }
      dp[i][j] %= MOD;
      dp_sum[i][j] %= MOD;
    }
  }
  cout << (dp[n][k] < 0 ? dp[n][k] + MOD : dp[n][k]) << endl;

  return 0;
}

Measured memory_bytes: 173168
def solve(N, M, lrd):
    edges = {}
    nodes = {}
    for l, r, d in lrd:
        if not l in edges:
            edges[l] = {}
        if not r in edges:
            edges[r] = {}
        edges[l][r] = d
        edges[r][l] = -d
        nodes[l] = None
        nodes[r] = None
    for node in nodes:
        if nodes[node] is not None:
            continue
        nodes[node] = 0
        stack = []
        stack.append(node)
        while stack:
            node = stack.pop()
            for n, d in edges[node].items():
                if nodes[n] is None:
                    stack.append(n)
                    nodes[n] = nodes[node] + edges[node][n]
                else:
                    if nodes[n] != nodes[node] + edges[node][n]:
                        return False
    return True

if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    lrd = []
    for i in range(M):
        lrd.append([int(x) for x in input().split()])
    if solve(N, M, lrd):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 96916
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
#define MOD (1000000007ll)
#define l_ength size

ll sq(ll x){
	return x*x;
}

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

bool isvowel(char c){
	int i;
	string v="aeiou";
	for(i = (v.size()-1); i>=0; --i){
		if(c == v[i]){
			return true;
		}
	}
	return false;
}

ll manhattan(ll x1, ll y1, ll x2, ll y2){
	return ((ll)(abs(x1-x2)+abs(y1-y2)));
}

int main(void){
	int n,m,i,j,ans;
	ll a[55],b[55],c[55],d[55],mn,tmp;
	cin >> n >> m;
	for(i=0; i<n; ++i){
		cin >> a[i] >> b[i];
	}
	for(j=0; j<m; ++j){
		cin >> c[j] >> d[j];
	}
	for(i=0; i<n; ++i){
		mn = INFLL;
		for(j=0; j<m; ++j){
			tmp = manhattan(a[i],b[i],c[j],d[j]);
			if(mn > tmp){
				mn = tmp;
				ans = j;
			}
		}
		cout << (ans+1) << endl;
	}
	return 0;
}

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

using namespace std;

struct Edge{
    int from,to,cost;
    Edge(int from,int to,int cost): from(from), to(to), cost(cost){}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

bool operator < (const Edge &e, const Edge &f){
    return e.cost < f.cost;
}

struct UF {
	vector<int> data;
	UF(int size) : data(size, -1) { }
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool find(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

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

    int n,m;
    while(cin>>n>>m,n){
        UF uf(n);
        Edges es;
        vector<int> ans;
        for(int i=0;i<m;i++){
            int st,gt,c;cin>>st>>gt>>c;
            st--;gt--;
            es.push_back(Edge(st,gt,c));
        }
        sort(es.begin(),es.end());
        for(int i=0;i<m;i++){
            int st=es[i].from,gt=es[i].to;
            if(!uf.find(st,gt)){
                uf.unite(st,gt);
                ans.push_back(es[i].cost);
            }
        }
        cout<<ans[(n-1)/2]<<endl;
    }
}


Measured memory_bytes: 3300
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=305*305,L=305,inf=INT_MAX;
int n,l,a[N],b[N],w[N];
vi v[L];
ii dist[L][L];
bool vis[L][L];
priority_queue<pair<ii,int>,vector<pair<ii,int> >,greater<pair<ii,int> > > s;
void fun(int u)
{
  rep(i,1,n+1) dist[u][i].fi=dist[u][i].se=inf;
  dist[u][u]=mp(0,0);
  s.push(mp(mp(0,0),u));
  while(sz(s))
    {
      auto it=s.top(); s.pop();
      if(vis[u][it.se]) continue;
      vis[u][it.se]=true;
      for(auto id:v[it.se])
	{
	  int v1=(it.se^a[id]^b[id]);
	  ii tmp=dist[u][v1];
	  if(dist[u][it.se].se+w[id]<=l)
	    dist[u][v1]=min(dist[u][v1],mp(dist[u][it.se].fi,dist[u][it.se].se+w[id]));
	  else
	    dist[u][v1]=min(dist[u][v1],mp(dist[u][it.se].fi+1,w[id]));
	  if(tmp!=dist[u][v1] && !vis[u][v1])
	    s.push(mp(dist[u][v1],v1));
	}
    }
}
int main()
{
  int m;
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; 
  cin>>n>>m>>l;
  //rep(i,1,n+1) rep(j,1,n+1) d[i][j]=mp(inf,inf);
  //rep(i,1,n+1) d[i][i]=mp(0,0);
  rep(i,1,m+1)
    {
      cin>>a[i]>>b[i]>>w[i];
      if(w[i]>l) continue;
      //d[a[i]][b[i]]=min(d[a[i]][b[i]],mp(0,w[i]));
      swap(a[i],b[i]);
      //d[a[i]][b[i]]=min(d[a[i]][b[i]],mp(0,w[i]));
      v[a[i]].pb(i); v[b[i]].pb(i);
    }
  rep(i,1,n+1) fun(i);
  int q;
  cin>>q;
  while(q--)
    {
      int x,y;
      cin>>x>>y;
      if(dist[x][y].fi==inf) cout<<-1<<endl;
      else cout<<dist[x][y].fi<<endl;
    }
  return 0 ;
}


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

int main() {
  int n;  cin >> n;
  string blue[100];
  for (int i = 0; i < n; i++) cin >> blue[i];
  
  int m;  cin >> m;
  string red[100];
  for (int i = 0; i < m; i++) cin >> red[i];
  
  int yen, max = 0;
  for (int i = 0; i < n; i++) {
    yen = 1;
    for (int j = i + 1; j < n; j++) {
      if (blue[i] == blue[j])
        yen++;
    }
    for (int j = 0; j < m; j++) {
      if (blue[i] == red[j])
        yen--;
    }
    if (max < yen)
      max = yen;
  }
  
  cout << max << endl;
}


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

using namespace std;

int n,l,dp[100005],a[100005];

int func(int i){

  if(i>n)return 0;
  if(dp[i]>0)return dp[i];
  if(a[i]>a[i-1] && a[i]>a[i+1])return dp[i]=l-a[i];

  int res=0;
  if(a[i]<a[i-1])res=max(res,func(i-1));
  if(a[i]<a[i+1])res=max(res,func(i+1));

  return dp[i]=l-a[i]+res;
}

int main(void){
  int in;
  
  while(cin >> n >> l){
    
    for(int i=0;i<n+2;i++)dp[i]=0;

    for(int i=1;i<n+1;i++)
      cin >> a[i];

    a[0]=a[n+1]=0;

    int res=0;
    for(int i=1;i<n+1;i++)
      res=max(res,func(i));

    cout << res << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3116
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int x = sc.nextInt();
		
		System.out.println((long)Math.ceil((-1 + Math.sqrt(1 + 8.0*x))/2));
	}

}


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

int main() {
    int N,K,count = 0;
  	cin >> N >> K;
  	int h[N];
  	for(int i=0;i<N;i++){
    cin >> h[i];
    }
    for(int i=0;i<N;i++){
    	if(h[i]>=K){
    		count++;
    	}
    }
 	cout << count <<endl;
  	return 0;
}

Measured memory_bytes: 640
using System;
using System.Linq;
using System.Collections.Generic;

class MyClass
{
    public static void Main(string[] args)
    {
        var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var A = input[0]; //1000
        var B = input[1]; //500
        var X = input[2];
        var p = new int[3];
        p[0] = (int)Math.Ceiling(X / 1000.0) * A;
        p[1] = (int)Math.Ceiling(X / 500.0) * B;
        p[2] = B + (int)Math.Ceiling((X - 500) / 1000.0) * A;
        Console.WriteLine(p.Min());
    }
}


Measured memory_bytes: 18492
#include"bits/stdc++.h"
using namespace std;

int n;

void Main() {
  cin >> n;

  for (int i = 1; i <= 9; i++) {
    if (n % i == 0 && n / i <= 9) {
      cout << "Yes" << endl;
      return;
    }
  }
  cout << "No" << endl;
}

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

Measured memory_bytes: 256
// Problem : A - Frog 1
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;

#define ff first
#define fs second
#define lb lower_bound
#define ub upper_bound

#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector< vi >
#define vpii vector< pii >
#define vb vector<bool>
#define si set<int>
#define mii map<int, int>
#define mci map<char, int>
#define md 1000000007
#define pb push_back
#define eb emplace_back
#define fio ios_base::sync_with_stdio (false); cin.tie (NULL);  cout.tie (NULL);
#define qw1(x) cerr<<#x<<": "<<x<<" "<<endl
#define qw2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define qw3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define qw4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl


#define f(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define rl(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define all(x) x.begin(),x.end()
#define endl '\n'
void printv(vector<int>  v){ for(int i=0;i<v.size();i++) cout<<v[i]<<' '; cout<<endl;   }
int bem(int m , int n, int mod) { int res=1; while(n){
	     			        if(n%2!=0) { res*=m; res%=mod; }
	    			        m*=m;   m%=mod;   n/=2;
			                          }
				return res;	}
int be(int a, int b) { int res=1; 	while(b){
				if(b%2!=0) res*=a;
				a*=a; b/=2;
				}
			return res;	}
void sieve(int n, vb &prime){
    prime[0]=false;     prime[1]=false;
    for(int i=2;i*i<=n;i++){
         if(prime[i]==true){
              for(int j=i*i;j<=n;j+=i)    prime[j]=false;
             	  }
    	 }
	}
int fun( vi &v, vi &dp, int n)
{
	if(dp[n]!=-1) return dp[n];
	if(n==1) return dp[n]=0;
	if(n==2) return dp[n]=abs(v[1]-v[0]);
	if(n==3) return dp[n]=abs(v[2]-v[0]);
	else 
	return dp[n]=min(fun(v, dp, n-1)+abs(v[n-1]-v[n-2]), 
	 fun(v, dp, n-2)+abs(v[n-3]-v[n-1]));
}
void solve()
  {
  	int n; cin>>n;
  	vi v(n);
  	f(i, 0, n-1) cin>>v[i];
  	vi dp(n+1, -1);
  	cout<<fun(v, dp, n)<<endl;

  }

int32_t main ()
{
//fio
int t=1; 
//cin>>t; 
while(t--){
	solve();
}
 
}








Measured memory_bytes: 4992
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

struct UnionFind {
    vector<int> p;
    UnionFind(int n) {
        p = vector<int>(n, -1);
    }
    int parent(int a) {
        if (p[a] < 0) return a;
        return p[a] = parent(p[a]);
    }
    int same(int a, int b) {
        return parent(a) == parent(b);
    }
    int size(int a) {
        return -p[parent(a)];
    }
    bool unite(int a, int b) {
        a = parent(a);
        b = parent(b);
        if (same(a, b)) return false;
        if (size(a) < size(b)) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    UnionFind uni(n);
    vector<int> num1(n, 0);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        uni.unite(a, b);
        ++num1[a];
        ++num1[b];
    }
    vector<int> num2(n, 0);
    rep(i, k) {
        int c, d;
        cin >> c >> d;
        --c, --d;
        if (uni.same(c, d)) {
            ++num2[c];
            ++num2[d];
        }
    }
    rep(i, n) {
        if (i > 0) cout << " ";
        cout << uni.size(i) - 1 - num1[i] - num2[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 4256
N = int(input())
A = [int(input()) for i in range(N)]
now = 2
count = A[0]-1
for i in range(1,N):
    if A[i] == now:
        now += 1
    elif A[i]%now != 0:
        count += A[i]//now
    else:
        count += (A[i]-1)//now
print(count)

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll inf = 1e6+5;
typedef pair<int, bool> pib;
int main() {
    int a,b,h; cin >> a >> b >> h;
    cout << (h*(a+b))/2;
}



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

int main() {
  int N, M;
  cin >> N >> M;
  string result = "";
  for (int i = 0; i < N; ++i) {
    result += "0";
  }
  vector<bool> flgs(10, false);
  bool flg = false;
  for (int i = 0; i < M; ++i) {
    int si;
    char ci;
    cin >> si >> ci;
    if ((flgs.at(si) && result.at(si - 1) != ci) || (si == 1 && ci == '0' && N != 1)) {
      flg = true;
      break;
    }
    flgs.at(si) = true;
    result.at(si - 1) = ci;
  }
  if (flg) {
    cout << -1 << endl;
  } else {
    if (result.at(0) == '0' && N != 1) {
      result.at(0) = '1';
    }
    cout << result << endl;
  } 
}

Measured memory_bytes: 256
def main():
    from collections import deque

    N = int(input())
    s = input()

    ans = deque(s)
    cnt = 0
    for c in s:
        if c == ')':
            if cnt:
                cnt -= 1
            else:
                ans.appendleft('(')
        else:
            cnt += 1

    for _ in range(cnt):
        ans.append(')')

    print(''.join(ans))


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

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

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 (b<a) { a = b; return 1; } return 0; }

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

// ------------------------------------------------------------------------------------------

signed main() {
	int x, y, z;
	cin >> x >> y >> z;
	swap(x, y);
	swap(x, z);

	cout << x << " " << y << " " << z << endl;

	return 0;
}

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

#define ll              long long
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             (int)(1e18)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define rep(i,j,n)      for(int i=j;i<n;i++)
#define all(p)          p.begin(),p.end()
#define ub(a,b)         upper_bound(all(a),b)
#define lb(a,b)         lower_bound(all(a),b)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

void run()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
vector<vector<ll>> g;
vector<int> ans;
vector<bool> vis;
void dg(ll n, ll m)
{
	g.resize(n);
	for (ll i = 0; i < m; i++)
	{
		ll u, v;
		cin >> u >> v;
		u--, v--;
		g[u].pb(v);
	}
}
void dfs(int s)
{
	bool flag = false;
	vis[s] = true;
	for (auto child : g[s])
	{
		flag = true;
		if (!vis[child])
		{
			dfs(child);
		}
	}
	for (auto child : g[s])
	{
		ans[s] = max(ans[s], ans[child]);
	}
	ans[s] += flag;
}
int32_t main()
{
	run();
	int n, m;
	cin >> n >> m;
	ans.assign(n, 0);
	vis.assign(n, false);
	dg(n, m);
	for (int i = 0; i < n; i++)
	{
		if (!vis[i])
		{
			dfs(i);
		}
	}
	int answer = 0;
	for (auto ele : ans)
	{
		//cout << ele << " ";
		answer = max(answer, ele);
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 8576