akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
int factorial(int n);
int factorial(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return n*factorial(n-1);
    }

}

bool is_prime(ll n) {
    // Assumes that n is a positive natural number
    // We know 1 is not a prime number
    if (n == 1) {
        return false;
    }

    ll i = 2;
    // This will loop from 2 to int(sqrt(x))
    while (i*i <= n) {
        // Check if i divides x without leaving a remainder
        if (n % i == 0) {
            // This means that n has a factor in between 2 and sqrt(n)
            // So it is not a prime number
            return false;
        }
        i += 1;
    }
    // If we did not find any factor in the above loop,
    // then n is a prime number
    return true;
}
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
typedef unsigned long long  ull;

int check(int x,vector <int> a,int n)
{  int county=0;
  map <int,int> mapa;
    for(int i=0;i<n;i++)
    {
        mapa.insert(pair<int,int>(a[i],0));
    }
    for(int i=0;i<n;i++)
    {
        mapa[a[i]]++;
    }
   // cout<<mapa[1]<<mapa[2]<<mapa[3]<<mapa[4]<<mapa[5]<<endl;
    for(int i=0;i<a.size();i++)
    {   mapa[a[i]]--;
        if(mapa[abs(a[i]-x)]>0)
        {
            county++;


            mapa[abs(a[i]-x)]--;
        }


    }
    return county;
}



int main()
{  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
    cin>>a[i];
}
int county=0;
for(int i=1;i<n-1;i++)
{
    for(int j=0;j<i;j++)
    {
        for(int k=i+1;k<n;k++)
        {
            if(a[i]!=a[j]&& a[j]!=a[k]&&a[i]!=a[k])
            {
                if(a[i]+a[j]>a[k]&&a[k]+a[j]>a[i]&&a[i]+a[k]>a[j])
                {
                    county++;
                }

            }
        }
    }


}

cout<<county<<endl;

}


Measured memory_bytes: 3644
package main

import "fmt"

func main() {
	var n, m, q int
	fmt.Scan(&n, &m, &q)
	as := make([]int, q)
	bs := make([]int, q)
	cs := make([]int, q)
	ds := make([]int, q)
	for i := 0; i < q; i++ {
		fmt.Scan(&as[i], &bs[i], &cs[i], &ds[i])
	}

	var dfs func(i int, nums []int) int
	dfs = func(i int, nums []int) int {
		if len(nums) == n {
			ss := 0
			for k := 0; k < q; k++ {
				s := score(
					nums[as[k]-1],
					nums[bs[k]-1],
					cs[k],
					ds[k],
				)
				ss += s
			}
			return ss
		}

		res := 0
		for j := i; j <= m; j++ {
			res = max(res, dfs(j, append(nums, j)))
		}
		return res
	}

	ans := 0
	for i := 1; i <= m; i++ {
		ans = max(ans, dfs(i, []int{}))
	}
	fmt.Println(ans)
}

func score(a, b, c, d int) int {
	if b-a == c {
		return d
	}
	return 0
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 6276
from math import ceil

n,k, *aa = map(int, open(0).read().split())

left = 0
right = 10**9

while right - left > 1:
    mid = (left + right) // 2
    summ = sum(0--a//mid-1 for a in aa)
    if summ <= k:
        right = mid
    else:
        left = mid

print(right)

Measured memory_bytes: 108708
#include <iostream>
using namespace std;
int main(void) {
  char a, b;
  cin >> a >> b;
  char c;
  if (a - b < 0) {
    c = '<';
  } else if (a == b) {
    c = '=';
  } else {
    c = '>';
  }
  cout << c << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    vector<ll> a(5,0);
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s.at(0)=='M')a.at(0)++;
        else if(s.at(0)=='A')a.at(1)++;
        else if(s.at(0)=='R')a.at(2)++;
        else if(s.at(0)=='C')a.at(3)++;
        else if(s.at(0)=='H')a.at(4)++;
        else continue;
    }
    ll sum=0;
for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
        for(int k=0;k<5;k++){
            if(i==j||j==k||k==i)continue;
            sum+=a.at(i)*a.at(j)*a.at(k);
        }
    }
}
sum/=6;
cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int n;
	char c;
	int rank;
	bool cards[4][13];
	//0:S,1:H,2:C,3:D
	//initialize
	for(int i=0;i<4;i++)for(int j=0;j<13;j++)cards[i][j]=true;
	//input
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> c >> rank;
		switch(c){
		case 'S':
			cards[0][rank-1]=false;
			break;
		case 'H':
			cards[1][rank-1]=false;
			break;
		case 'C':
			cards[2][rank-1]=false;
			break;
		case 'D':
			cards[3][rank-1]=false;
		}
	}
	//output
	//S
	for(int i=0;i<13;i++)
		if(cards[0][i]==true)
			cout<< "S " << i+1 << endl;
	//H
	for(int i=0;i<13;i++)
		if(cards[1][i]==true)
			cout<< "H " << i+1 << endl;
	//C
	for(int i=0;i<13;i++)
		if(cards[2][i]==true)
			cout<< "C " << i+1 << endl;
	//D
	for(int i=0;i<13;i++)
		if(cards[3][i]==true)
			cout<< "D " << i+1 << endl;
	//return
	return 0;
}

Measured memory_bytes: 1160
import java.util.*;
         
        public class Main {
          public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int a = sc.nextInt();
            int b = sc.nextInt();
            int h = sc.nextInt();
            System.out.println((a+b)*h/2);
         
          }
        }

Measured memory_bytes: 9680
#include <iostream>

using namespace std;

#define RPT(i, n) for (int i = 1; i <= n; i++)

int H, W;
char a[101][101];
bool row_is_white[101];
bool col_is_white[101];

int main()
{
    cin >> H >> W;
    RPT(i, H)
    {
        row_is_white[i] = true;
        RPT(j, W)
        {
            cin >> a[i][j];
            if (row_is_white[i] && a[i][j] == '#') row_is_white[i] = false;
        }
    }

    RPT(j, W)
    {
        col_is_white[j] = true;
        RPT(i, H)
        {
            if (a[i][j] == '#') {
                col_is_white[j] = false;
                break;
            }
        }
    }

    RPT(i, H)
    {
        if (row_is_white[i]) continue;
        RPT(j, W)
        {
            if (col_is_white[j]) continue;
            cout << a[i][j];
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i < n; ++i)
#define repe(i, n) for(int i=0; i <= n; ++i)
#define repr(i, n) for(int i=n-1; i > 0; --i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
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 (b<a) {a = b; return 1;} return 0;}
template <class T> using V=vector<T>;
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1000000007;
const ll MAX = 510000;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
    int n,k;
    cin >> n >> k;
    vector<int> L(n);
    rep(i,n) {
        cin >> L[i];
    }
    sort(all(L), greater<int>());
    int sum = 0;
    rep(i,k) {
        sum +=L[i];
    }
    cout << sum << "\n";
}


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

int main() {
  int N, K; cin >> N >> K;
  string S; cin >> S;
  int ans = 0;
  for(int i = 0; i < S.size()-1; i++) {
    if(S[i] == S[i+1]) ans++;
  }
  ans = min(ans+2*K, N-1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
import sys
from math import sqrt, hypot

def _hypot(p1, p2):
    return hypot(p2[0]-p1[0], p2[1]-p1[1])

def heron(p1, p2, p3):
    e1, e2, e3 = _hypot(p1, p2), _hypot(p2, p3), _hypot(p1, p3)
    z = (e1+e2+e3)/2
    return sqrt(z*(z-e1)*(z-e2)*(z-e3))

a = [tuple(map(float, l.split(","))) for l in sys.stdin]
result = 0
for p1, p2 in zip(a[1:], a[2:]):
    result += heron(a[0], p1, p2)
print(result)


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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")
ll A, B, N;
ll f(ll x) {
	return A * x / B - A * (x / B);
}

int main()
{
	cin >> A >> B >> N;
	ll l =0, r = N+1;
	fx(100) {
		ll x1 = (l * 2 + r) / 3;
		ll x2 = (l + r * 2) / 3;
		if (f(x1) <= f(x2)) {
			l = x1;
		}
		else {
			r = x2;
		}
	}
	//doublece(l,r)
	ce(max(f((l * 2 + r) / 3), f((l + r * 2) / 3)))
	return 0; 
}



Measured memory_bytes: 3636
def com(_x):
    _flg = 1
    mx  = int(_x**0.5)
    for i in range(2, mx+1):
        if _x % i == 0:
            _flg = 0
            break
    return _flg


x = int(input())
flg = 0
while flg == 0:
    #print("a")
    flg = com(x)
    if flg == 0:
        x+=1
print(x)


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

int main(){
  int x;
  int a, b;
  int glad;

  cin >> x;

  a = x / 500;

  b = (x % 500) / 5;

  glad = a * 1000 + b * 5;

  cout << glad << endl;

  return 0;
}


Measured memory_bytes: 256
// Sky's the limit :)
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int T = 1; 
    // cin >> T; 
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &&x : a)
            cin >> x;

        sort(a.begin(), a.end());
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (a[i] + a[j] > a[k] && a[i] != a[j] && a[j] != a[k] && a[k] != a[i])
                        cnt++;
                }
            }
        }

        cout << cnt << '\n';
    }
    
    return 0;
}



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

const ll MOD = 1e9+7;

int main() {
    // std::cout<<std::fixed<<std::setprecision(10);

    string S; cin >> S;
    // あまりiになるj桁目までの数
    vector<vector<ll>> dp(S.size()+1, vector<ll>(13, 0));

    // 0桁目までであまりが0になるもの
    dp[0][0] = 1;
    rep(i, S.size()) {
        ll c;
        if (S[i] == '?') {
            c = -1;
        } else {
            c = S[i] - '0';
        }
        if (c == -1){
            // cが?のとき
            // cout << "c == ?" << endl;
            rep(j, 13) {
                rep(k, 10) {
                    // j*10 + k == modの箇所に
                    // cout << "i: " << i+1 << ", j:  " << (j*10+k) % 13 << " = " << dp[i][j] << endl;
                    dp[i+1][(j*10+k) % 13] += dp[i][j];
                }
            }
        } else {
            rep(j, 13) {
                dp[i+1][(j*10+c) % 13] += dp[i][j];
            }
        }

        // あまり全通りをmodで割っておく
        rep(j, 13) {
            dp[i+1][j] %= MOD;
        }
        /*
        cout << "i: " << i << endl;
        rep(j, S.size()+1) {
            rep(k, 13) cout << dp[j][k] << " ";
            cout << endl;
        }
        cout << endl;
        */
    }
    cout << dp[S.size()][5]%MOD << endl;
    return 0;
}

Measured memory_bytes: 13696
#include<bits/stdc++.h>
using namespace std;
#define range(a,b) (a).begin(),(a).begin()+(b)+2
int A,B,Q;
const long INF=10000000000;
const int size=100000;
vector<long> S(size+2),T(size+2);long X[size];
long shortest_route(int x,int y,int z){
    long a;
    if(S[x]<T[y]){
	    if(S[x+1]<T[y+1]){
		    a=min(X[z]-T[y],S[x+1]-X[z]);
		    return min(min(X[z]-S[x],T[y+1]-X[z]),a+S[x+1]-T[y]);
	    }else{
		    return min(X[z]-S[x],S[x+1]-X[z]);
	    }
    }else{
	   	if(S[x+1]<T[y+1]){
	    	return min(X[z]-T[y],T[y+1]-X[z]);
	    }else{
	       	a=min(X[z]-S[x],T[y+1]-X[z]);
		    return min(min(X[z]-T[y],S[x+1]-X[z]),a+T[y+1]-S[x]);
	    }
	}
}	    
int main(){
    cin>>A>>B>>Q;
	for(int i=1;i<=A;i++){
		cin>>S[i];
	}for(int i=1;i<=B;i++){
		cin>>T[i];
	}S[0]=-INF;S[A+1]=2*INF;
	T[0]=-INF;T[B+1]=2*INF;
	int x,y;
	for(int i=0;i<Q;i++){
		cin>>X[i];
		x=upper_bound(range(S,A),X[i])-S.begin()-1;
		y=upper_bound(range(T,B),X[i])-T.begin()-1;
		cout<<shortest_route(x,y,i)<<endl;
	}
}

Measured memory_bytes: 3712
using System;
using System.IO;
using System.Net;
using System.Net.Sockets;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;

public static class P
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var b = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var c = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(b.Sum() + a.Zip(a.Skip(1), (x, y) => y - x == 1 ? c[x - 1] : 0).Sum());
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

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

template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<template<class...> class ContT, class ValueT, size_t Dim>
struct vec_type
{
    using type = ContT<typename vec_type<ContT, ValueT, Dim-1>::type>;
};

template<template<class...> class ContT, class ValueT>
struct vec_type<ContT, ValueT, 0>
{
    using type = ValueT;
};

template<class ValueT, size_t Dim = 1>
using vec_t = typename vec_type<std::vector, ValueT, Dim>::type;


template<class ValueT, size_t Dim, class = typename std::enable_if<Dim == 0>::type>
auto make_vec(ValueT value = ValueT()) -> ValueT
{
    return value;
}

template<class ValueT, size_t Dim, class... Rest>
auto make_vec(size_t size0, Rest... rest)
{
    auto vec = make_vec<ValueT, Dim-1>(rest...);
    return std::vector(size0, vec);
}

int diffabs(int l, int r)
{
    if (l < r) return r-l;
    else return l-r;    
}


///////////////////////////////////////////////////

int main()
{
    int N, K;
    cin >> N >> K;
    vi p(N);
    for (int i = 0; i < N; i++)
        cin >> p[i];

    sort(begin(p), end(p), less<int>());

    int ans = 0;
    for (int k = 0; k < K; k++)
        ans += p[k];
    
    cout << ans << endl;
}

Measured memory_bytes: 3644
N, A, B = map(int, input().split())
X = list(map(int, input().split()))

# x -----> x ----> x            y ----> y                z ----> z

# テレポートとテレポートの間を１グループとすると、各グループは独立している
# 行った道を引き返すことはない。基本的に左から右への移動で十分。

dp = [-1] * (N + 1)
dp[0], dp[1] = 0, 0

for i in range(1, N):
    dp[i + 1] = min(dp[i] + A * (X[i] - X[i - 1]), dp[i] + B)

# print('dp', dp)
print(dp[-1])


Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
int main(){
    int h,w,k;
    cin >> h >> w >> k;
    ll dp[101][10];
    dp[0][1] = 1;
    for(int i = 1;i <= h;i ++){
        for(int j = 1;j <= w;j ++){
            ll x=0,y=0,z=0;
            for (int bit = 0; bit < (1<<w); ++bit){
                bool isConnect[w+1]={},isPossible=true;
                if(bit%2) continue;
                for(int l = 1;l < w;l ++){
                    if(bit & (1<<l)) isConnect[l] = true;
                }
                for(int l = 1;l < w;l ++){
                    if(isConnect[l]&&isConnect[l+1]) {isPossible=false;break;}
                }
                if(!isPossible) continue;
                if(isConnect[j-1]) x ++;
                else if(isConnect[j]) z ++;
                else y ++;
            }
            dp[i][j]=(dp[i-1][j-1]*x+dp[i-1][j]*y+dp[i-1][j+1]*z)%mod;
        }
    }
    cout << dp[h][k] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

int main()
{
    int n;
    cin>>n;
    vector<ll> a(n);
    int minus=0;
    ll low=1e9;
    rep(i,n)
    {
        cin>>a[i];
        if(a[i]<0)
        {
            minus++;
        }
        low=min(low,abs(a[i]));
    }
    ll ans=0;
    rep(i,n)
    {
        ans+=abs(a[i]);
    }
    if(minus%2!=0)
    {
        ans-=2*abs(low);   
    }
    cout<<ans;
    
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;
int n;
int m[100], a[100], b[100];
bool hantei();
void bubbleSort(int size){
  for(int end=size-1;end>0;end--){
    for(int j=0;j<end;j++){
      if(a[j+1]<a[j]){
	int tmp=a[j];
	a[j]=a[j+1];
	a[j+1]=tmp;

	tmp=m[j];
	m[j]=m[j+1];
	m[j+1]=tmp;

	tmp=b[j];
	b[j]=b[j+1];
	b[j+1]=tmp;
      }
    }
  }
}

main(){

  while(1){
    cin >> n;
    if(n==0) break;

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

    bubbleSort(n);

    if(hantei()) cout << "OK" << endl;
    else cout << "NG" << endl;
    
  }
  return 0;
}

bool hantei(){
  int now=0, sum=0;
  bool p[100];
  for(int i=0;i<n;i++){
    p[i]=false;
  }
  for(int i=0;i<n;i++){
    now=a[i];
    sum+=m[i];
    p[i]=true;
    for(int j=0;j<i;j++){
      if(!p[j]) continue;
      if(b[j]<=now){
	sum-=m[j];
	p[j]=false;
      }
    }
    if(sum>150) return false;
  }
  return true;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define VI  vector<ll>
#define lf(i,a,b) for(ll i=a;i<=b;i++)
const ll mod=1e9+7;
double pi = 2 * acos(0.0);
#define FASTIO ios_base::sync_with_stdio(false);cout.tie(NULL);cout.tie(NULL);
ll max(ll a, ll b) { return (a > b) ? a : b; }
ll min(ll a, ll b) { return (a < b) ? a : b; }
bool cmp(pair<ll,ll> a,pair<ll,ll> b)
{
    return (a.first)<(b.first);
}
ll power(ll a,ll b)
{
        ll p=1;
        for(ll i=1;i<=b;i++)
        p*=a;

        return p;
}
ll gcd(ll a, ll b){
    if (a == 0)
        return b;
    return gcd(b % a, a);
 }
void bfs(map<ll,vector<ll> > &g,ll src,vector<ll> &c)
{
    queue<ll> q;
    map<ll,ll> p;
    q.push(src);
    p[src]=src;
    c[src]=1;
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        ll i=1;
        for(auto v:g[u])
        {
            if(c[v]==-1)
            {
                q.push(v);
                p[v]=u;
                if(i==c[u]||i==c[p[u]])
                    i++;
                if(i==c[u]||i==c[p[u]])
                    i++;
                c[v]=i;
                i++;
            }
        }
    }
}
int main()
{
    FASTIO;
    ll n,i;
    cin>>n;
    ll a[n],dp[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        dp[i]=INT_MAX;
    }
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n-1]<<endl;
    return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include <algorithm>
#include <string>
using namespace std;
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(int)(n); i++)
typedef long long ll;
const int INF = numeric_limits<int>::max();
const int MOD = (1e9 + 7);

ll gcd(ll a, ll b){
  if(b==0) return a;
  else gcd(b, a%b);
}

 int main(){
  ll A, B, N;
  cin >> A >> B;
  N = gcd(A, B);
   ll cnt=0;
   const ll k = sqrt(N);
  for(ll i=2; i<=k; i++){
   if(N%i==0){
     while(N%i==0){
     N /= i;
     }
     cnt ++;
   }
  }
   if(N!=1) cnt++;
   cout << cnt+1 << endl;
  
}


Measured memory_bytes: 256
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

s = int(input())
ans = 0

for i in range(1,s//3+1):
    ans += cmb(s-2*i-1,i-1)

print(ans%(10**9+7))


Measured memory_bytes: 9604
#include <iostream>
using namespace std;
const int INF = 1000000000+7; 
int main() {
	long n, p=1;
	cin >> n;
	for(int i=1;i<=n;i++){
		p *= i;
		p %= INF;
	}
	cout << p << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    bool b=true;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a%2!=0)b=!b;
    }
    if(b)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <set>
#include <iterator>
using namespace std;

int n, k, l;
vector<int> p, q;
set<int> a, b;
int f[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};

int main(){
	cin >> n;
	p.reserve(n);
	q.reserve(n);
	for (int i = 0; i < n; ++i) cin >> p[i];
	for (int i = 0; i < n; ++i) cin >> q[i];
	for (int i = 0; i < n; ++i){
		a.insert(i+1);
		b.insert(i+1);
	}

	k = l = 0;
	for (int i = 0; i < n; ++i){
		k += f[n-i-1]*distance(a.begin(), a.find(p[i]));
		a.erase(p[i]);
		l += f[n-i-1]*distance(b.begin(), b.find(q[i]));
		b.erase(q[i]);
	}
	cout << abs(k - l);
}

Measured memory_bytes: 256
# coding=utf-8

###
### for atcorder program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

def get_input():
    N = []
    while True:
        try:
            #N.append(input())
            N.append(int(input()))
        except EOFError:
            break
    return N

N = [int(x) for x in input().split()]
N = sorted(N)

S = ''

for i in N[::-1]:
    S += str(i)+' ' 

print(S[:-1])




Measured memory_bytes: 5680
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define eps 1e-67
#define pf printf
#define sf scanf
#define sd(n) scanf("%d",&n)
#define sd2(n1,n2) scanf("%d %d",&n1,&n2)
#define slf(n) scanf("%lf",&n)
#define slf2(n1,n2) scanf("%lf %lf",&n1,&n2)
#define sLf(n1) scanf("%Lf",&n1)
#define sLf2(n1,n2) scanf("%Lf %Lf",&n1,&n2)
#define sl(n) scanf("%lld",&n)
#define sl2(n1,n2) scanf("%lld %lld",&n1,&n2)
#define rep(i,a,b) for(long long int i=a;i<b;i++)
#define repb(i,a,b) for(long long int i=a;i>=b;i--)
#define repa(i,a,b,c) for(long long int i=a;i<b;i=i+c)
#define reps(i,a,b,c) for(long long int i=a;i>b;i=i-c)
#define asort(a) sort(a.begin(),a.end())
#define asortb(a,comp) sort(a.begin(),a.end(),comp)
#define arev(a) reverse(a.begin(),a.end())
#define all(v) (v).begin(),(v).end()
#define allc(v,comp) (v).begin(),(v).end(),comp
#define allrc(v,a,b,comp) (v).begin()+a,(v).end()-b,comp
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define pbb pop_back
#define mp make_pair
#define mt make_tuple
#define bs(v,x) binary_search(v.begin(),v.end(),x)
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
#define tl(c) towlower(c)
#define root(x) sqrt(x)
#define power(a,n) pow(a,n)
#define tu(c) towupper(c)
#define sq(a) ((a)*(a))
#define cube(a) ((a)*(a)*(a))
#define mx 1000
#define MX 100000
#define mod 1000000007
using namespace std;
typedef string str;
typedef long long int ll;
typedef double lf;
typedef long double llf;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef char ch;
typedef map<ll,ll> mp;
void Solve()
{
    ll n,m,mm,ss,ans;

    cin>>n>>m;

    llf ans1;
    if(2*n>=m)
    {
        ans1=floor((m/2.00));
        ans=(ll)ans1;
    }
    else
    {
        ss=n*2+m;
        ans1=floor((ss/4));
        ans=(ll)ans1;
    }
    cout<<ans<<endl;
}
int main()
{
    Solve();
  return 0;
}

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

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
int main(){
    //入力
    int n;
    cin>>n;
    int p[n],q[n];
    for(int i=0;i<n;i++){
        cin>>p[i];
        q[i]=p[i];
    }
    //処理
    int count=0;
    
    sort(q, q + SIZE_OF_ARRAY(q));
    for(int i=0;i<n;i++){
        if(p[i]!=q[i])count++;
    }
    //出力
    if(count>2)cout<<"NO";
    else cout<<"YES";
}

Measured memory_bytes: 256
def lower_bound(arr, v)
  l = -1; r = arr.size
  while l + 1 < r
    m = (l + r) / 2
    if arr[m] <= v then l = m
    else r = m
    end
  end
  l
end
n = gets.to_i
arr = n.times.map{ gets.to_i }
sum = Array.new(2*n+1, 0)
(2*n).times{ |i| sum[i+1] += sum[i] + arr[i%n] }
l = 0; r = sum[n] / 3 + 1
while l + 1 < r
  m = (l + r) / 2
  i = 0
  while i < n
    a = lower_bound(sum[i,n], m + sum[i] - 1) + i + 1
    if a < i + n
      b = lower_bound(sum[a...i+n], m + sum[a] - 1) + a + 1
      break if b < i + n && sum[i+n] - sum[b] >= m
    end
    i += 1
  end
  i == n ? r = m : l = m
end
p l

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

/* using */
using namespace std;

/* main constructor */
struct Fast
{
    Fast()
    {
        std::cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(12);
    }
} fast;

/* define */
#define REP(i, x, n) for (int i = x; i < (int)(n); ++i)
#define RREP(i, x, n) for (int i = x - 1; i >= (int)(n); --i)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) REP(i, 1, n + 1)
#define rrep(i, n) RREP(i, n, 0)
#define each(i, n) for (auto &i : n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define eunique(x) (x).erase(unique(all(x)), (x).end())
#define int long long
#define MAX 1e9 + 7

/* function */
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

/* main */
signed main(void)
{
    int n;
    double sum = 0;
    cin >> n;
    rep(i, n)
    {
        double x;
        string u;
        cin >> x >> u;
        if (u[0] == 'J')
        {
            sum += x;
        }
        else
        {
            sum += x * 380000;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
from bisect import bisect_left
n,k=map(int,input().split())
if n==1:exit(print(1))
d=[1]
t=[1]
for i in range(2,int(n**0.5)+2):
  if n//d[-1]!=n//i:
    d.append(i)
    t.append(1)
  else:
    t[-1]+=1
dd=[]
for i in range(d[-1],0,-1):
  if n//i<=d[-1]:continue
  dd.append(n//i)
x=d+dd
for i in range(len(t),len(x)):
  t.append(x[i]-x[i-1])
di=[0]*len(x)
mod=10**9+7
for i in range(len(x)):di[i]=bisect_left(x,n//x[i])
n=len(x)
dp=[n*[0]for _ in range(k)]
dp[0]=t[:]
for i in range(1,k):
  for j in range(1,n):
    dp[i-1][j]+=dp[i-1][j-1]
    dp[i-1][j]%=mod
  for j in range(n):dp[i][j]=dp[i-1][di[j]]*t[j]%mod
print(sum(dp[-1])%mod)

Measured memory_bytes: 126696
def smaller(x, y):
	if x < y: return x
	return y

N, M, X = map(int, raw_input().split())
A = map(int, raw_input().split())
left = 0
right = 0
for i in range(0, X):
	if i in A: left += 1
for i in range(X+1, N+1):
	if i in A: right += 1
print smaller(left, right)

Measured memory_bytes: 28012
from math import factorial

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(int(i))
        i += 1
    if n > 1:
        table.append(int(n))
    return table

def __main__():
    n = int(input())
    if n == 1:
        print(1)
        return
    i = 2
    prime_factors_count = [0] * 1001
    while i <= n:
        prime_factors = prime_decomposition(i)
        for j in range(prime_factors[-1] + 1):
            c = prime_factors.count(j)
            prime_factors_count[j] += c
        i += 1
    c = 1
    for i in range(1001):
        if prime_factors_count[i] != 0:
            c *= prime_factors_count[i] + 1
    print(c % (10**9 + 7))

__main__()


Measured memory_bytes: 3064
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

def main():
    import sys
    input = sys.stdin.readline
    n,k=L()
    a=L()
    visited=[0]*(n+1)
    tmp=0
    now=0
    visited[0]=1
    loopat=-1
    for i in range(k):
        #print(visited,end="")
        tmp=i+2
        now=a[now]-1
        #print(now)
        #print(tmp,now+1)
        if visited[now]==0:
            visited[now]=i+2
        else:
            loopat=now
            break
    #print(visited)
    #print(loopat,visited[loopat],tmp)
    #print(tmp,now)
    if loopat==-1:
        print(now+1)
        exit()
    elif tmp-visited[loopat]==0:
        tmp2=k
        dist=1
        now=0
    else:
        tmp2=(k-(visited[loopat]-1))%(tmp-visited[loopat])
        dist=loopat+1
    #print(tmp2)
    
    #print(now,dist)
    #print(now+1,end=" ")
    for i in range(tmp2):
        now=a[now]-1
        dist=now+1
        #print(now,dist)
    #print()
    print(dist)
    
    
if __name__ == '__main__':
    main()

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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

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

    map<ll, ll> cnt;
    ll now = 0;
    for (int i = 0; i < N; i++) {
        cnt[now]++;
        now += A[i];
    }
    cnt[now]++;

    ll ans = 0;
    for(auto e : cnt) {
        ans += e.second * (e.second - 1) / 2;
    }
    
    cout << ans << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

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

int cnt[100005];

int main()
{
   int n;
   cin >> n;
   vector<int> a(n);
   for(int i = 0;i<n;++i)cin >> a[i];
   int ans = 0;
   for(auto i:a)cnt[i]++;

   for(int i = 1;i<100001;i++)
   {
      ans = max(cnt[i-1]+cnt[i]+cnt[i+1],ans);
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>

const int KIND_COUNT = 4;

const int A_INT = 0;
const int T_INT = 1;
const int G_INT = 2;
const int C_INT = 3;

const char A_CHAR = 'A';
const char T_CHAR = 'T';
const char G_CHAR = 'G';
const char C_CHAR = 'C';

struct Node {
  bool exist;
  struct Node *next[KIND_COUNT];
};

int kind(char v) {
  if (v == A_CHAR) {
    return A_INT;
  } else if (v == T_CHAR) {
    return T_INT;
  } else if (v == G_CHAR) {
    return G_INT;
  } else {
    return C_INT;
  }
}

struct Node *createNode() {
  struct Node *node = (struct Node *) malloc(sizeof(struct Node));

  for (int i = 0; i < KIND_COUNT; i++) {
    node->next[i] = NULL;
  }

  node->exist = false;

  return node;
}

void insert(struct Node *root, std::string word) {
  struct Node *node = root;
  
  for (int i = 0; i < word.size(); i++) {
    int k = kind(word[i]);

    if (node->next[k] == NULL) {
      node->next[k] = createNode();
    }

    node = node->next[k];
  }

  node->exist = true;
}

bool find(struct Node *root, std::string word) {
  struct Node *node = root;
  
  for (int i = 0; i < word.size(); i++) {
    int k = kind(word[i]);

    if (node->next[k] == NULL) {
      return false;
    }

    node = node->next[k];
  }

  return node->exist;
}



int main() {
  std::ios_base::sync_with_stdio(false);

  struct Node *root = createNode();
  
  int n = 0;

  std::cin >> n;

  for (int i = 0; i < n; i++) {
    std::string command;
    std::string word;

    std::cin >> command >> word;

    if (command[0] == 'i') {
      insert(root, word);
    } else {
      if (find(root, word)) {
	std::cout << "yes" << std::endl;
      } else {
	std::cout << "no" << std::endl;
      }
    }
  }
  
  return 0;
}

Measured memory_bytes: 17516
#include "bits/stdc++.h"
using namespace std;
#define MAX_V 101
#define INF 10000000
double cost[MAX_V][MAX_V];
double d[MAX_V];
int prev[MAX_V];
bool used[MAX_V];
int n;
typedef vector<int> vi;
#define rep(u,n) for(int u=0;u<n;u++)

void dijkstra(int s){
  fill(d, d + n, INF);
  fill(used, used + n, false);
  fill(prev, prev + n, -1);
  d[s] = 0;

  while(true){
    int v = -1;
    rep(u, n){
      if(!used[u] && (v == -1 || d[u] < d[v])) v = u;
    }

    if(v == -1) break;
    used[v] = true;

    rep(u, n){
      if(d[u] > d[v] + cost[v][u]){
    d[u] = d[v] + cost[v][u];
    prev[u] = v;
      }
    }
  }
}

vi get_path(int t){
  vi path;
  for(; t != -1; t = prev[t]) path.push_back(t);
  reverse(path.begin(), path.end());
  return path;
}

int main(){
  while(scanf("%d", &n) && n){
    int b;
    double x[MAX_V], y[MAX_V];
    rep(i, n){
      scanf("%d", &b); b--;
      scanf("%lf%lf", &x[b], &y[b]);
    }
    rep(i, MAX_V) rep(j, MAX_V) cost[i][j] = INF;
    rep(i, n) rep(j, n){
      if(i == j) continue;
      double dis = sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
      if(dis > 50) continue;
      cost[i][j] = dis;
    }

    int m;
    scanf("%d", &m);
    rep(i, m){
      int s, g;
      scanf("%d%d", &s, &g);s--;g--;
      dijkstra(s);
      if(d[g] == INF){
    puts("NA");
      }else{
    vi res = get_path(g);
    rep(i, res.size()) printf(i?" %d":"%d", res[i]+1);
    puts("");
      }
    }
  }
  return 0;
}

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

struct Point {
  double x, y;
};

void koch(int n, Point a, Point b) {
  if (n == 0) return;
  Point s, t, u;
  double th = M_PI * 60.0 / 180.0;

  s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
  s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
  t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
  t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
  u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
  u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

  koch(n - 1, a, s);
  printf("%.8f %.8f\n", s.x, s.y);
  koch(n - 1, s, u);
  printf("%.8f %.8f\n", u.x, u.y);
  koch(n - 1, u, t);
  printf("%.8f %.8f\n", t.x, t.y);
  koch(n - 1, t, b);
}

int main() {
  Point a, b;
  int n;

  scanf("%d", &n);

  a.x = 0;
  a.y = 0;
  b.x = 100;
  b.y = 0;

  printf("%.8f %.8f\n", a.x, a.y);
  koch(n, a, b);
  printf("%.8f %.8f\n", b.x, b.y);

  return 0;
}


Measured memory_bytes: 3216
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int a = Integer.parseInt(in.next());
            int b = Integer.parseInt(in.next());

            // 出力
            out.println((a + b + 1) / 2);

        }

    }
}



Measured memory_bytes: 23380
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
#define _GLIBCXX_DEBUG
using namespace std;

int main(){
  int64_t n;
  cin >> n;
  vector<int64_t> a(n);
  rep(i,n){
    cin >> a[i];
  }
  bool exodd = false;
  rep(i,n){
    exodd = exodd || (a[i] % 2 == 1);
  }
  if(exodd){
    cout << "first" << endl;
  }else{
    cout << "second" << endl;
  }
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    int H,W,i,j,x,ans=0;
    char A[1010][1010];
    int S[1010][1010];
    x=1e9+7;
    cin >> H >> W;
    
    for(i=1;i<=H;i++){
        for(j=1;j<=W;j++){
            cin >> A[i][j];
        }
    }
    
    for(i=0;i<=H;i++){
        for(j=0;j<=W;j++){
            S[i][j]=0;
        }
    }
    S[0][1]=1;
    
    for(i=1;i<=H;i++){
        for(j=1;j<=W;j++){
            if(A[i][j]=='.'){
                S[i][j]=(S[i][j-1]%x+S[i-1][j]%x)%x;
            }
        }
    }
    
    ans=S[H][W];
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 5248
import sys

N = int(input())
h_list = list(map(int, input().split()))

max_up = -1
max_down = 1

if h_list[0] > 1:
    h_list[0] -= 1

for i in range(len(h_list[:-1])):

    h = h_list[i]
    next_h = h_list[i+1]
    diff = next_h - h

    if diff > 0:
        h_list[i+1] = next_h - 1
    elif diff < 0:
        print("No")
        sys.exit()
print("Yes")


Measured memory_bytes: 14224
#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define FAST ios_base::sync_with_stdio(false);cin.tie(0);
    const double EPS = 1e-9;
    const double PI = acos(-1);
    const int knightDir[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2}};
    //const int dx[]={0,0,0,1,1,1,-1,-1,-1};
    //const int dy[]={-1,0,1,-1,0,1,-1,0,1};
    const int dx[] = {0 , 1 , 0 , -1};
    const int dy[] = {1 , 0 , -1 , 0};
    //#define MOD         1000000007LL
    #define MAX         1000005
    const ll MOD = 1000000000 + 7;
    ll pows(ll x , ll n)
    {
        ll ans = 1;
        for(int i = 1 ; i <= n ; i++)
        {
            ans *= x;
            ans = ans % MOD;
        }
        return ans;
    }
    int main()
    {
        FAST
        int t;
        t = 1;

        while(t--)
        {
           ll n;
           cin >> n;
           ll ans = (pows(10 , n) - (2 * pows(9 , n)) + pows(8 , n)) % MOD;
           ans += MOD;
           cout << ans % MOD << endl;
        }
    }



Measured memory_bytes: 3608
S = list(input())
Q = int(input())
reverse, front, tail = False, [], []

for q in range(Q):
    query = list(input().split())

    if len(query) == 1:
        reverse ^= 1

    elif len(query) == 3:
        f, c = int(query[1]), query[2]
        f -= 1

        if f ^ reverse:
            tail.append(c)
        else:
            front.append(c)

if reverse:
    print(''.join((front[::-1] + S + tail)[::-1]))
else:
    print(''.join(front[::-1] + S + tail))


Measured memory_bytes: 107824
/*
author:Rahul Chocha
school of eng. and applied science
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define MAXI INT_MAX
#define MINI INT_MIN
#define din(t) long long t; cin >> t;
#define fi(i, l, r, d) for (i = l; i < r; i += d)
#define fd(i, l, r, d) for (i = l - 1; i >= r; i -= d)
#define pb push_back
#define mp make_pair


void speed_up()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
}



int main()
{   

   	speed_up();
   	//din(t)
       ll t=1;
	while(t--){
       string s;
       cin>>s;
       if(s[0]=='R' && s[1]=='R' && s[2]=='R')  
       cout<<"3";
       else if((s[0]=='R' && s[1]=='R') || (s[2]=='R' && s[1]=='R') )
       cout<<"2";
       else if(s[0]=='R' || s[1]=='R' || s[2]=='R')   
       cout<<"1";
       else cout<<"0";
    }
} 


Measured memory_bytes: 3656
N, K = map(int, input().split())
d = dict()
for _ in range(N):
    a, b = map(int, input().split())
    d[a] = d.get(a, 0) + b
for key in sorted(d.keys()):
    c = d[key]
    if K <= c:
        break
    K -= c
print(key)

Measured memory_bytes: 16344
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stack>
#include <queue>
#include <functional>
#include <cmath>

using LL = long long;

int A, B, C, X, Y;

int main()
{
    scanf("%d%d%d%d%d", &A, &B, &C, &X, &Y);

    int mn = std::min(X, Y);
    LL ans = 0;

    if (2 * C < A + B)
        ans += 2LL * mn * C;
    else
        ans += 1LL * mn * (A + B);

    if (X > mn)
        ans += std::min(1LL * (X - mn) * A, 2LL * (X - mn) * C);
    if (Y > mn)
        ans += std::min(1LL * (Y - mn) * B, 2LL * (Y - mn) * C);

    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
  long long n;
  string s;
  vector<long long> v(26,1);
  cin>>n>>s;
  for(long long i=0;i<n;i++){
    v[s[i]-'a']++;
  }
  long long ans=1;
  for(int i=0;i<26;i++){
    ans*=v[i];
    ans%=1000000007;
  }
  cout<<ans-1<<endl;
  return 0;
}

Measured memory_bytes: 512
#貰うDP
import itertools
N, MOD = int(input()), 10**9+7
memo = [{'AGC':0, 'ACG':0, 'GAC':0} for i in range(N + 1)]
C = list('ACGT')
for c in itertools.product(C, C, C):
    c = ''.join(c)
    if c in memo[3]:
        continue
    else:
        memo[3][c] = 1

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i>= 1:
            t[i-1], t[i] = t[i], t[i-1]
            if ''.join(t).count('AGC') == 1:
                return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    ret = 0
    for c in 'ACGT':
        if ok(c + last3):
            ret = (ret + dfs(cur - 1, c + last3[:-1])) % MOD
    memo[cur][last3] = ret
    return ret

def answer(n):
    ans = 0
    clist = list('ACGT')
    for c in itertools.product(clist, clist, clist):
        ch = ''.join(c)
        ans += dfs(n, ch)
    return ans % MOD

print(answer(N))

Measured memory_bytes: 3896
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <time.h>
#include <iomanip>
#include <bitset>

using namespace std;

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n, x;
  cin >> n >> x;
  int sum = 0;
  int ans = 0;
  rep(i, 0, n) {
    int a;
    cin >> a;
    sum += a;
    if(sum <= x) ans++;
  }
  cout << ans + 1 << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long c = sc.nextLong();
		long x = sc.nextLong();
		x /= 50;
		long count = 0L;
		for (int i = 0; i <= a; i++) {
			for(int j = 0; j <= b; j++) {
				for(int l = 0; l <= c; l++) {
					if(10*i+2*j+l==x) {
						count++;
					}
				}
			}

		}
		System.out.println(count);
	}
}

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

int main(){
  
  int N, b, c, d, e;
  cin >> N;
  b = 0;
  c = 0;
  d = 0;
  e = 0;
 
  for(int i = 0; i < N; i++){
    string a;
    cin >> a;
    if(a == "G"){
      b += 1;
    }
    else if(a == "P"){
      c += 1;
    }
    else if(a == "W"){
      d += 1;
    }
    else{
      e += 1;
    }
  }
  if(b == 0 || c == 0 || d == 0 || e == 0){
    cout << "Three" << endl;
  }
  else{
    cout << "Four" << endl;
  }
}

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

int main(){
  ll n;
  cin>>n;
  ll L[n];
  L[0]=2,L[1]=1;
  for (int i = 2; i <= n; i++)
  {
    /* code */
    L[i]=L[i-1]+L[i-2];
  }
  cout<<L[n]<<endl;
  
  
  }

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int a = in.nextInt();
			int b = in.nextInt();
			if(a + b < 24) {
				out.println(a + b);
			} else {
				out.println(a + b - 24);
			}
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}


Measured memory_bytes: 22996
package main

import (
  "fmt"
)

func abs(a int) int {
  if a < 0 {
    return -a
  }
  return a
}

func main() {
  var N int
  fmt.Scan(&N)
  
  h := make([]int, N)
  for i := 0; i < N; i++ {
    fmt.Scan(&h[i])
  }
  
  dp := make([]int, N)
  for i := 1; i < N; i++ {
    dp[i] = abs(h[i-1] - h[i]) + dp[i-1]
    if i > 1 {
      if p := abs(h[i-2] - h[i]) + dp[i-2]; dp[i] > p {
        dp[i] = p
      }
    }
  }
  fmt.Println(dp[N-1])
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    ll n,sum=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        if(!(i % 3 == 0 || i % 5 == 0)) sum += i;
    }
    cout << sum << endl;
}

Measured memory_bytes: 3636