akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
      a: i64,
      b: i64,
      c: i64,
      d: i64,
    }
    if (a-b).abs() <= d && (b-c).abs() <= d || (a-c).abs() <= d {
        println!("{}", "Yes");
    } else {
        println!("{}", "No");
    }
}


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

long long P[505];
vector< pair<int, int> > dir = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

int main() {

    for (int i=1; i<=500; i++)
    {
        P[i] = 1;

        for (int j=1; j<=5; j++)
            P[i] *= i;
    }
    
    int x;
    cin >> x;

    for (int i=0; i<=500; i++)
        for (int j=0; j<=500; j++)
        {
            for (auto d : dir)
            {
                if (P[i] * d.first - P[j] * d.second == x)
                {
                    cout << i * d.first << " " << j * d.second << "\n";
                    return 0;
                }
            }
        }

    return 0;
}


Measured memory_bytes: 3604
# -*- coding: utf-8 -*-
s = list(str(input()))

ans = 1000
for i in range(len(s) - 2):
    X = int(s[i]) * 100 + int(s[i + 1]) * 10 + int(s[i + 2])
    if abs(X - 753) < ans:
        ans = abs(X - 753)
print(ans)


Measured memory_bytes: 2940
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=list(input())
    N=list(reversed(list(map(int,N))))+[0]
    ans=0
    for i in range(len(N)):
        if N[i]>=6 or (N[i]==5 and N[i+1]>=5):
            ans+=10-N[i]
            N[i+1]+=1
        else:
            ans+=N[i]
    print(ans)

if __name__ == '__main__':
    main()


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

using namespace std;

long long f(long long a) {
    if(a < 0)
        return 0ll ;
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

int main()
{
    long long a , b ;
    cin>>a>>b ;
    return cout<<getXor(a , b)<<"\n" , 0 ;
}


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

int main() {
    vector<int> as;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        as.push_back(a);
    }

    vector<int> dp(n + 1, INT_MAX);
    for (int i = 0; i < n; i++) {
        *lower_bound(dp.begin(), dp.end(), as[i]) = as[i];
    }

    for (int i = 0; i < n + 1; i++) {
        if (dp[i] == INT_MAX) {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 3924
#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>;

const ll mod = 1000000007;
const double eps = 1e-8;

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
    int H, W, K;
    cin >> H >> W >> K;

    vector<vector<int>> S(H, vector<int>(W));
    for (int i=0; i<H; ++i) {
        for (int j=0; j<W; ++j) {
            char c;
            cin >> c;
            S[i][j] = c-'0';
        }
    }

    int res = W + H;
    for (int i=0; i<(1<<(H-1)); ++i) {
        // debug(bitset<8>(i));

        int cut = __builtin_popcount(i);
        vector<int> cnt(H, 0);

        for (int j=0; j<W; ++j) {
            vector<int> add(H, 0);
            int kk = 0;
            for (int k=0; k<H; ++k) {
                add[kk] += S[k][j];
                cnt[kk] += S[k][j];
                if ((i >> k) & 1) kk ++;
            }
            int mxa = *max_element(add.begin(), add.end());
            if (K < mxa) {
                cut = W + H;
                break;
            }
            int mxc = *max_element(cnt.begin(), cnt.end());
            if (K < mxc) {
                cut ++;
                cnt = add;
            }
            // debug("cnt:", cnt);
        }
        res = min(res, cut);
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n = I()
    lst = LI()
    ans = lst[0]
    for i in range(1, n):
        ans = gcd(ans, lst[i])
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 19172
#include<bits/stdc++.h>
#define rep(i,n)  for(ll i=0; i<n; i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF 1e9
using ll = long long;
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; }

int main(){
  int n, ans = 0; cin >> n;
  vi a(n); rep(i,n) cin >> a[i];
  sort(all(a));
  vi check(a[n-1]+1);
  rep(i,n) for(int j = a[i]; j <= a[n-1]; j += a[i]) check[j]++;
  rep(i,n) if(check[a[i]]==1) ans++;
  cout << ans;
}


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

int main() {
 int n;
  cin>>n;
  vector<int> a(n);
  bool b=true;
  for(int i=0;i<n;i++){
    cin>>a.at(i);
    if(!(a.at(i)%2!=0||a.at(i)%3==0||a.at(i)%5==0)){
b=false;
       break;
     }
    }
  if(b==true) cout<<"APPROVED"<<endl;
  else cout<<"DENIED"<<endl;
}


Measured memory_bytes: 256
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"sort"
)
 
func run() {

	var N int;
    N = nextInt();
    A := make([]int,N);
    for i := 0 ; i < int(N) ; i++ {
        A[i] = nextInt();
    }
	solve(N, A);

}

func solve(N int, A []int){
	B := make([]int,N);
	copy(B,A)
	sort.Sort(sort.IntSlice(A))
	
	for i := 0; i < int(N); i++ {
		if A[N-1] == B[i] {
			Println(A[N-2])
		}else {
			Println(A[N-1])
		}
	}
}


// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int {
	a, err := strconv.Atoi(next())
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}


type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

/////数字と文字
// 基本クラス
type NS struct {
    Num int
    Str string
}

//////　数字と数字
// 基本クラス
type NN struct {
    Num1 int
    Num2 int
}

 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}



Measured memory_bytes: 11904
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;
    Func cin2;
    void calc()
    {
        cin = new Scanner();
        cin2 = new Func();
        string N=cin.next();
        string S=cin.next();
        int ans=0;
      for(int i=0;i<3;i++)
      {
        if(N[i]==S[i])ans++;
      }
      Console.WriteLine(ans);
        
    }
}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Answer
{
    public void Int2DArrayAns(int[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
    public void Char2DArrayAns(char[,]x,char c)
    {
        for(int i=0;i<x.GetLength(0);i++)
        {
            for(int j=0;j<x.GetLength(1)-1;j++)
            {
                Console.Write(x[i,j]);
                Console.Write(c);
            }
            Console.WriteLine(x[i,x.GetLength(1)-1]);
        }
    }
}

class Func
{
    public long GCDLong(long a, long b)
    {
        while(a!=0)
        {
          long t=a;
          a=b%a;
          b= t;
        }
      
        return b;        
    }
}

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

int main()
{
    ll n,i,k,j;
    cin>>n>>k;
    ll A[n+1],dp[n+1];
    for(i=1;i<=n;i++)
        cin>>A[i];
    
    for(i=0;i<=n;i++)
        dp[i]=999999999999999;

    dp[1]=0;
    
    for(i=2;i<=n;i++)
        for(j=i-1;j>=max((ll)1,i-k);j--)
            dp[i]=min(dp[i],dp[j]+abs(A[i]-A[j]));
    cout<<dp[n]<<"\n";    
}


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

int n,k;
int dist[300];

int nodist( int x ){
	while ( x ){
		int y = x % 10;
		x /= 10;
		if ( dist[y] ) return false;
	}
	return true;
}

int main(){

	cin >> n >> k;
	for ( int i = 0; i < k; i++ ){
		int coin;
		cin >> coin;
		dist[coin] = true;
	}

	for ( int i = n; ; i++ ){
		if ( nodist(i) ){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <limits.h>
typedef unsigned int uint;

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

#define H 200000
uint v[H+1];
int main(void){
    const uint h = gl();
    gl();
    const uint n = gl();
    for(uint i=1; i<h+1; i++){ v[i] = i+1; }
    for(uint i=0; i<n; i++){
        uint x = gl();
        uint y = gl();
        v[x] = y<v[x] ? y : v[x];
    }
    uint right = 1;
    for(uint x=1; x<h; x++){
        if(v[x+1]<right+1){
            printf("%d\n", x);
            return 0;
        }else if(v[x+1]>right+1){
            right++;
        }
    }
    printf("%d\n", h);
    return 0;
}


Measured memory_bytes: 896
int main(){
  int n,l[2000],a=0,b=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&l[i]);
  }
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(l[i]>l[j]){
        a=l[i];
        l[i]=l[j];
        l[j]=a;
      }
  	}
  }
  for(int i=0;i<n-2;i++){
    for(int j=i+1;j<n-1;j++){
      int k=j+1;
      while(l[i]+l[j]>l[k]&&k<n){
        b++;
        k++;
      }
  	}
  }
  printf("%d\n",b);
  return 0;
}

Measured memory_bytes: 256
/**
 *
 * Contest - Problema X: Nome (link)
 *
 * Abridge version.
 *
 * Solution: text
 */
#include <iostream>

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

using namespace std;

using ll = long long;
using ii = pair<ll, ll>;

#define LOG(var, sep) (cerr << #var << " = " << (var) << (sep))
#define LOGM(msg) (cerr << (msg))
#define LOGV(vec, sep) { cerr << #vec << " ="; for (const auto& v : vec) cerr << " " << v; cerr << (sep); }
#define LOGA(arr, N, sep) { cerr << #arr << " ="; for (int i = 0; i < N; ++i) cerr << " " << (arr)[i]; cerr << (sep); }
#define LOGA2(arr, N, M, sep) { cerr << #arr << " =\n"; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) cerr << (arr)[i][j] << " "; cerr << endl; } cerr << (sep); }

ostream& operator<<(ostream& os, const ii& p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

const int MAX { 100010 };
const ll oo { 1LL << 62 };
const int MOD { 1000000007 };

ll as[MAX], ps[MAX];

void precomp()
{
}

void solve(ll N, ll M)
{
/*    for (int a = 1; a <= N; ++a)
        for (int b = a; b <= N; ++b)
        {
            ll s = 0;

            for (int k = a; k <= b; ++k)
                s += as[k];

            if (s % M == 0)
                cout << "(" << a << ", " << b << ") ";
        }
cout << endl;
*/
    map<ll,ll> hist;
    map<ll,vector<ll>> who;

    for (int i = 1; i <= N; ++i)
        ps[i] = (ps[i - 1] + as[i]) % M;

//LOGA(as, N + 1, '\n');
//LOGA(ps, N + 1, '\n');
    ll ans = 0;

    for (int i = N; i > 0; --i)
    {
        hist[ps[i]]++;
        who[ps[i]].push_back(i);

        auto x = ps[i - 1];
        auto it = hist.find(x);

//LOG(i, ' '); LOG(as[i], ' '); LOG(x, '\n');
        ans += (it != hist.end() ? it->second : 0);

  //      if (it != hist.end())
   //     {
//LOG(ans, ' '); 
//for (auto y : who[x])
//{
//auto t = ii(i, y);
//LOG(t, ' ');
//}
//LOGM('\n');
//        }

    }

    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    precomp();

    ll N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; ++i)
        cin >> as[i];

    solve(N, M);

    return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
using LP=pair<ll,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N;
    cin>>N;
    if(N==1){
        cout<<"Hello World"<<endl;
    }
    else{
        int A,B;
        cin>>A>>B;
        cout<<A+B<<endl;
    }
}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))

abs1 = [0]*(n-1)
abs1_sum = 0
for i in range(1,n):
    abs1[i-1] = abs(a[i-1]-a[i])
    abs1_sum += abs(a[i-1]-a[i])


abs2 = [0]*(n-2)
for i in range(2,n):
    abs2[i-2] = abs(a[i-2]-a[i])
#print(abs1)

b_0 = abs(a[0])
b_1 = abs(a[1])
b_n1 = abs(a[n-1])
b_n2 = abs(a[n-2])
ans = []
for i in range(n):
    if i == 0:
        ans.append(abs1_sum - abs1[0] + b_1 + b_n1)
    elif i == n-1:#
        #print(abs1[:n-2],abs(p[0]),abs(p[-1]))
        ans.append(abs1_sum - abs1[-1] + b_0 + b_n2)
    else:
        ans.append(b_0 + b_n1 + abs1_sum - abs1[i] - abs1[i-1] + abs2[i-1])

for i in range(n):
    print(ans[i])




Measured memory_bytes: 61168
/*
g++ -std=c++11 -o2 -Wall ABC096D.cpp -o ./out/ABC096D.out
./out/ABC096D.out
*/

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

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define tr(c, i) for (iter(c) != (c).begin(); i != (c).end(); ++i)
#define pb push_back
#define mp make_pair

typedef long long ll;

bool isprime(int p) {
	if (p == 1) return false;
	for (int i = 2; i < p; i++) {
		if (p%i == 0) return false;
	}
	return true;
}

int main(){
//    freopen("./input/input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
  	for (int i = 11; i <= 55555; i += 10) {
  		if (isprime(i) == true) {
  			if (i != 11) cout << " ";
  			cout << i; n--;
  		}
  		if (n == 0) break;
    }
    cout << "\n";
}


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long

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

    if (s[2] == s[3] && s[4] == s[5]) cout << "Yes";
    else cout << "No";

    return 0;
}

Measured memory_bytes: 256
A, B, C = map(str, [input() for i in range(3)])
dic = {'A': A, 'B': B, 'C': C}
turn = 'A'
while True:
    if dic[turn] != '':
        turn_b = turn
        turn = dic[turn_b][0].upper()
        dic[turn_b] = dic[turn_b][1:]
    else:
        print(turn)
        break


Measured memory_bytes: 2940
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N,M,X,Y=rl()
x=rl()
y=rl()
x_ = max(x+[X])
y_ = min(y+[Y])

if x_ < y_:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3064
N = int(input())
B_array = [int(i) for i in input().split()]
A_array = []

A_array.append(B_array[0])

for i in range(1, N-1):
    B_i = B_array[i]
    B_iminus1 = B_array[i-1]
    if B_i < B_iminus1:
        A_array.append(B_i)
    else:
        A_array.append(B_iminus1)

A_array.append(B_array[N-2])

counter = 0
for i, e in enumerate(A_array):
    counter += e

print(counter)

Measured memory_bytes: 38484
#include <stdio.h>


int main(void)
{
	int a, b, c, k;
	scanf("%d %d %d", &a, &b, &c);
	scanf("%d", &k);

	int i = 0;
	while (i < k)
	{
		if (a>=b)
			b = 2*b;
		else if (b >= c)
			c = 2*c;
		if (a<b && b<c)
			break;
		i++;
	}
	if (i == k)
		printf("No\n");
	else
		printf("Yes\n");
	return(0);
}


Measured memory_bytes: 2072
/*
 * I'm strong. Stronger than all of you. Extremely strong.
 * I can kill all those Titans there. Even if I'm alone.
 * You're either incompetent or you're spineless cowards.
 * How pathetic.
 * You can sit here and suck on your fingers. Yeah, do that.
 * ~ Mikasa Ackerman
 */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;

typedef long long int LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define si(n) scanf("%d", &n)
#define dout(n) printf("%d\n", n)
#define sll(n) scanf("%lld", &n)
#define lldout(n) printf("%lld\n", n)

#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

#define fast_io                                                                \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL)

#define endl '\n'
constexpr int N = 10, M = 200;
int dist[N][N];
int x[M][M];
int main() {
  fast_io;
  int h, w;
  cin >> h >> w;
  for (int i = 0; i < 10; i++)
    for (int j = 0; j < 10; j++)
      cin >> dist[i][j];
  for (int k = 0; k < 10; k++)
    for (int i = 0; i < 10; i++)
      for (int j = 0; j < 10; j++)
        if (dist[i][j] > dist[i][k] + dist[k][j])
          dist[i][j] = dist[i][k] + dist[k][j];
  int ans = 0;
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++) {
      int temp;
      cin >> temp;
      if (abs(temp) != 1)
        ans += dist[temp][1];
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
using namespace std;
char a[22][22];
int n,m;
struct pos{
	int x;
	int y;
	int step;
};
pos make_pos(int a,int b,int c){
	pos ret;
	ret.x=a;
	ret.y=b;
	ret.step=c;
	return ret;
}

int bfs(int sx,int sy,int ex,int ey){
	bool vis[n+2][m+2];
	for(int i=0;i<=n+1;++i)
		for(int j=0;j<=m+1;++j)
			if(a[i][j]=='#')
				vis[i][j]=true;
			else
				vis[i][j]=false;
	queue<pos> q;
	q.push(make_pos(sx,sy,0));
	vis[sx][sy]=true;
	int move[2][4]={{0,0,-1,1},{-1,1,0,0}};
	while(!q.empty()){
		pos fr=q.front();
		q.pop();
		if(fr.x==ex&&fr.y==ey)
			return fr.step;
		pos newpo;
		for(int i=0;i<4;++i){
			int nx=fr.x+move[0][i];
			int ny=fr.y+move[1][i];
			if(vis[nx][ny])
				continue;
			vis[nx][ny]=true;
			newpo=make_pos(nx,ny,fr.step+1);
			q.push(newpo);
		}
	}
	return 0;
}
int main(){
	for(int i=0;i<22;++i)
		for(int j=0;j<22;++j)
			a[i][j]='#';
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			cin>>a[i][j];
	int maxv=0;
	for(int i1=1;i1<=n;++i1)
		for(int j1=1;j1<=m;++j1){
			if(a[i1][j1]=='#')
				continue;
			for(int i2=1;i2<=n;++i2)
				for(int j2=1;j2<=m;++j2){
					if(a[i2][j2]=='#')
						continue;
					if(i1==i2&&j1==j2)
						continue;
					
					maxv=max(maxv,bfs(i1,j1,i2,j2));
				}
		}
	
	cout<<maxv<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
const in mdl=1000000007;
VVI wy;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,k;
  cin>>n>>k;
  wy.resize(k+1,VI(n+1,0));
  wy[0][n]=1;
  for(in i=1;i<=k;++i){
    for(in j=n-1;j>=0;--j){
      wy[i][j]=wy[i][j+1]+wy[i-1][j+1];
    }
    forn(j,n){
      if(n-j>=i)
	wy[i][j]+=wy[i-1][j];
      wy[i][j]%=mdl;
    }
    if(i<k){
      wy[i][0]=0;
    }
  }
  in rs=wy[k][0];
  if(k<n){
    forn(z,n-k-1){
      rs*=2;
      rs%=mdl;
    }
  }
  cout<<rs<<endl;
  return 0;
}


Measured memory_bytes: 31616
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
enum MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std;
// dfmt on

void main()
{
    real A, B;
    scan(A, B);
    writefln("%.0f", floor(A * B));
}


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

using namespace std;

int n,a,b;
vector<int> h;

bool ok(long long x) {
	long long cnt=0;
	for(int i=0;i<n;++i)
		cnt+=max(0LL,(h[i]-b*x+a-b-1)/(a-b));
	return cnt<=x;
}

int main() {
	cin >> n >> a >> b;
	h.resize(n);
	for(auto &e:h) cin >> e;
	long long l=0,r=1e9;
	while(r-l>1) {
		long long mid=(l+r)>>1;
		if(ok(mid)) r=mid;
		else l=mid;
	}
	cout << r << endl;
	
	return 0;
}


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

int main()
{
    int n; cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    
    int ans = 0;
    while (true) {
        int i = 0;
        while (i < n && h[i] == 0) i++;
        if (i == n) break;
        while (i < n && h[i] > 0) {
            h[i]--; i++;
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
	cin.tie(0)->sync_with_stdio(false);

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

	int cnt = 0;
	for (int i = 1; i <= n; i++)
		if (i % 2 && a[i] % 2)
			cnt++;
	cout << cnt << '\n';
	return 0;
}

Measured memory_bytes: 3616
from itertools import combinations

candidates = []
while True:
    n, k = map(int,input().split())
    if n == k == 0:
        break
    candidates.append([n,k])

def twoSum(tup):
    count = []
    can = list(range(1,tup[0]+1))
    for i in combinations(can,3):
        if sum(i) == tup[1]:
            count.append(i)
    return len(count)

for tup in candidates:
    print(twoSum(tup))


Measured memory_bytes: 5736
import java.util.*;
import static java.lang.System.*;

class Main {
	public static Scanner sc = new Scanner(in);
	public static Random rand=new Random();

	public int  josephus(int n, int k, int s) {//はじめにk
		 long x = k * s;
		 while (x > n) x = ((x - n) * k - 1) / (k - 1);
		 return (int)x;
	}


	public void run() {
		while(true){
			int n=sc.nextInt(),k=sc.nextInt(),m=sc.nextInt();
			if(n==0)return;
			int j=josephus(n,k,n)-k+m+n*k;
			while(j<=0)j+=n;
			while(j>n)j-=n;
			ln(j);
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}

	public int[] nextIntArray(int n){
		int[] res=new int[n];
		for(int i=0;i<n;i++){
			res[i]=sc.nextInt();
		}
		return res;
	}
	public static void pr(Object o) {
		out.print(o);
	}
	public static void ln(Object o) {
		out.println(o);
	}
	public static void ln() {
		out.println();
	}
}

Measured memory_bytes: 20500
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
int main() {
    string s, t;
    cin >> s >> t;
    cout << t+s << endl;
    return 0;
}

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

int main() {
    int D, G;
    cin >> D >> G;
    vector<int> p(D), c(D);
    for (int i = 0; i < D; i++) {
        cin >> p[i] >> c[i];
    }
    int min_problems = 100 * D;
    //cout << "G = " << G << endl << endl;

    for (int s = 0; s < (1 << (D)); s++) {
        //cout << "case : s = " << s << endl;
        int problems = 0, points = 0;
        vector<int> p_temp(D);
        for (int i = 0; i < D; i++) {
            p_temp[i] = p[i];
        }

        for (int t = 0; t < D; t++) { //ボーナス込みで問題を解く
            if (s & (1 << t)) {
               problems += p_temp[t];
                int point = 100 * (t + 1) * p_temp[t];
                point += c[t];
                points += point;
                p_temp[t] = 0;
            }
        }
        //cout << "   current points = " << points << endl;

        for (int t = p_temp.size() - 1; points < G; t--) { //点数の高い問題から順に
            if (p_temp[t] == 0) {
                continue;
            }
            while (p_temp[t] > 0 && points < G) {
                points += 100 * (t + 1);
                p_temp[t]--;
                problems++;
            }
            if (p_temp[t] == 0) {
                points += c[t];
            }
        }
        /*cout << "   last points = " << points << endl;

        cout << "   problems = " << problems << ", ";
        if (problems > min_problems) {
            cout << "min_problems < problems";
        } else {
            cout << "problems < min_problems";
        }
        cout << endl;*/

        min_problems = min(problems, min_problems);
    }

    cout << min_problems << endl;

    return 0;
}

Measured memory_bytes: 3632
import Data.Array.IO
import Data.Array.Unboxed
import Control.Monad

type Graph = UArray (Int, Int) Int
type Memo = IOUArray (Int, Int, Int) Int

shortest_path :: Memo -> Graph -> Int -> Int -> Int -> IO Int
shortest_path m g i j (-1) = return $ g ! (i, j)
shortest_path m g i j k    = do
    v <- readArray m (i, j, k)
    if v /= -1 then return v
    else do
        d  <- shortest_path m g i j (k - 1)
        ik <- shortest_path m g i k (k - 1)
        kj <- shortest_path m g k j (k - 1)
        let ans = min d (ik + kj)
        writeArray m (i, j, k) ans
        return ans

read_int :: String -> Int
read_int = read

tokenize :: String -> [Int]
tokenize = map read_int . words

main = do
    getLine
    c <- forM [0..9] $ \i -> getLine
    let g_aslist = concat $ map tokenize c
    let g = listArray ((0, 0), (9, 9)) g_aslist :: Graph
    memo <- newArray ((0,0,0), (9,9,9)) (-1) :: IO(Memo)
    wall <- filter (\x -> x >= 0) . map read_int . concat . map words . lines <$> getContents
    dists <- mapM (\x -> shortest_path memo g x 1 9) $ wall
    print . sum $ dists



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

const int N = 1e6;

int divisorCnt[N + 1];

void sieve() {
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            ++divisorCnt[j];
        }
    }
}

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    sieve();

    int n;
    std::cin >> n;

    int64_t ans = 0;

    for (int c = 1; c < n; c++) {
        int ab = n - c;
        ans += divisorCnt[ab];
    }

    std::cout << ans;


    return 0;
}

Measured memory_bytes: 7520
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	long long x,k,d;
	long long l,s,c,a,b;
	scanf("%lld %lld %lld",&x,&k,&d);
	l=0; s=0; c=0; a=0; b=0;
	if(x<0){
		x=x*-1;
	}
	l=x-((x/d)*d);
	s=(x-((x/d+1)*d))*-1;
	if(s<l){
		c=x/d+1;
		b=1;
	}
	else{
		c=x/d;
		b=2;
	}
	a=k-c;
	if(c>k){
		printf("%lld\n",x-(k*d));
	}
	else{
		if(a%2==0){
			if(b==1){
				printf("%lld\n",s);
			}
			else{
				printf("%lld\n",l);
			}
		}
		else{
			if(b==2){
				printf("%lld\n",s);
			}
			else{
				printf("%lld\n",l);
			}
		}
	}
	return 0;
}


Measured memory_bytes: 1736
# +-+-...と-+-+...をためす

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

def solve(start_sgn):
  sgn = start_sgn
  r = 0
  s = 0
  for a in A:
    s += a
    if s*sgn <= 0:
      r += abs(s-sgn)
      s = sgn
    sgn *= -1
  return r

print(min(solve(1), solve(-1)))

Measured memory_bytes: 14332
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    char a,b;
    cin >> a >> b;
    if(a=='H' && b=='H'){
        cout << 'H' <<endl;
    }else if(a=='D' && b=='D'){
        cout << 'H' <<endl;
    }else{
        cout << 'D' <<endl;
    }
}


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){
		int n = in.nextInt(), m = in.nextInt();
		int[] a = new int[m];
		for(int i = 0; i < m; i++) a[i] = in.nextInt() - 1;
		int[] p = new int[n];
		int b;
		for(int i = 0; i < m; i++){
			int x = 0;
			for(int j = 0; j < n; j++){
				b = in.nextInt() - 1;
				if(b == a[i]) p[j]++;
				else x++;
			}
			p[a[i]] += x;
		}
		for(int i = 0; i < n; i++){
			System.out.println(p[i]);
		}
	}

}

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

int main()
{
  int n;
  cin >> n;
  int a[n],b[n];
  for(int i=0;i<n;++i) cin >> a[i] >> b[i];
  sort(a, a + n);
  sort(b, b + n);
  int cmin, cmax, c;
  if(n%2 == 1){
    cmin = a[n/2];
    cmax = b[n/2];
    c = cmax - cmin + 1;
  }else{
    cmin = a[n/2-1] + a[n/2];
    cmax = b[n/2-1] + b[n/2];
    c = cmax - cmin + 1;
  }

  cout << cmax - cmin + 1 << endl;
}


Measured memory_bytes: 5204
class ABProblem:
    def output(self, a, b):
        print "%d %d %.5f" % (a / b, a % b, a * 1.0 / b)

if __name__ == "__main__":
        abp = ABProblem()
        a, b = map(int, raw_input().split())
        abp.output(a, b)

Measured memory_bytes: 6432
c1 = input()
c2 = input()

# マス目を 180度回転 させたとき、元のマス目と一致するなら YES を、そうでないなら NO を出力せよ。

if [c1[0], c1[1], c1[2]] == [c2[2], c2[1], c2[0]]:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 8876
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000000;
int main(){
  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  for (int i = 0; i < N; i++){
    cin >> w[i] >> v[i];
  }
  vector<vector<long long>> dp(N + 1, vector<long long>(100001, INF));
  //i番目の品物までで価値vを得るときの最小重さ
  dp[0][0] = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j <= 100000; j++){
      if (j < v[i]){
        dp[i + 1][j] = dp[i][j];
      } else {
        dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
      }
    }
  }
  int M = 0;
  for (int i = 0; i <= 100000; i++){
    if (dp[N][i] <= W){
      M = i;
    }
  }
  cout << M;
}

Measured memory_bytes: 80256
#include<stdio.h>
int main(void){
	int i,j,n,q,S[10000],T[500],C=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&S[i]);
	}
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&T[i]);
	}
	
	for(i=0;i<q;i++){
		for(j=0;j<n;j++){
			if(T[i]==S[j]){
				C++;
				break;
			}
		}
	}
	
	printf("%d\n",C);
	return 0;
}


Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void fastIO(){
  ios_base::sync_with_stdio(0); cin.tie(0);
}

vector<int>digits;
bool check(int n){
	string s = to_string(n);
	for(int i=0;i<s.length();i++){
		int x = s[i]-48;
		if(binary_search(digits.begin(),digits.end(),x)){
			return false;
		}
	}
	return true;
}
int main(){
  fastIO();
  int n,k;
  cin>>n>>k;
  for(int i=0;i<k;i++){
  	int d;
  	cin>>d;
  	digits.push_back(d);
  }
  sort(digits.begin(),digits.end());
  while(1){
  	bool veredict = check(n);
  	if(veredict){
  		break;
  	}
  	n++;
  }
  cout<<n<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int n,m,maxl=0,minr=114514;
    cin >> n >> m;
    int l[m],r[m];
    for(int i=0;i<m;i++){
        cin >> l[i] >> r[i];
        if(maxl<l[i]) maxl=l[i];
        if(minr>r[i]) minr=r[i];
    }
    if(minr>=maxl)
    cout << minr-maxl+1;
    else cout << 0;
    
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(){
   int a,b,s;
    
   scanf("%d %d",&a,&b);
   if (b<a) s=a--;
   else     s=b--;
   if (b<a) s+=a;
   else     s+=b;
   printf("%d\n",s);
   return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a<b &&b<c){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3100
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line: Vec<u32> = read_as_vec();
    let (x, a) = (line[0], line[1]);

    if x < a{
        println!("{}", 0);
    }else{
        println!("{}", 10);        
    }
}


Measured memory_bytes: 4352
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
void solve();
signed main(){
#ifdef Sprinkle
   clock_t clock_start=clock();assert(freopen("test.txt","r",stdin));
#else
   ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#endif
   solve();
#ifdef Sprinkle
   cerr<<"Running Time: "<<((clock()-clock_start) *1.0 / CLOCKS_PER_SEC)<<"s\n";
#endif
}
#ifdef Sprinkle
void err(){cerr<<"\n";}template<typename T,typename...U>void err(const T&hd,const U&...tl){cerr<<hd<<(sizeof...(tl)?", ":"");err(tl...);}
#define debug(x...) cerr<<""#x" = ";err(x)
#else
#define debug(...) 0
#endif
int a[2005];
void solve(){
    int n;
    cin>>n;
    for(int i= 0 ;i<n;++i){
        cin>>a[i];
    }
    sort(a,a+n);
    int ans  = 0;
    for(int i = 0;i<n-2;++i){
        for(int j = i+1;j<n-1;++j){
            int base = lower_bound(a+j+1,a+n,a[i]+a[j])-a;
            ans += base - 1 - j ;  
        }
    }
    cout<<ans<<endl;
}

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N, M;
  cin >> N >> M;
  llvec a(N), b(M);
  rep(i, N)cin >> a[i];
  rep(i, M)cin >> b[i];
  vector<llvec> dp(N+1, llvec(M+1, 0));
  rep(i, N){
    rep(j, M){
      if(a[i]!=b[j])dp[i+1][j+1] = mod(dp[i][j+1]+dp[i+1][j]-dp[i][j], MOD);
      else dp[i+1][j+1] = mod(dp[i+1][j]+1+dp[i][j+1], MOD);
    }
    //DUMP(k, dp[i+1]);cerr<< endl;
  }
  cout << dp[N][M]+1;
  return 0;
}


Measured memory_bytes: 31616
#include<stdio.h>
int main(){
    long A[10], N;
    int a[10][10] = {0}, i, j;
    while ( scanf("%ld", &A[1]) != EOF ) {
        for ( i = 2; i <= 8; i++ ) {
            scanf("%ld", &A[i]);
        }
        N = 10000000;
        for ( i = 1; i <= 8; i++ ) {
            for ( j = 1; j <= 8; j++ ) {
                a[j][i] = A[j] / N;
                A[j] = A[j] % N;
                /*printf("a");*/
            }
            N /= 10;
            /*printf("b");*/
        }
        /*for ( i = 0; i < 8; i++ ) {
            for ( j = 0; j < 8; j++ ) {
                printf("%d ", a[i][j]);
            }
            printf("\n");
        }*/
        for ( i = 1; i <= 8; i++ ) {
            for ( j = 1; j <= 8; j++ ) {
                if ( a[i][j] == 1 ) {
                    if ( a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1] == 3 ) printf("A\n");
                    else if ( a[i + 1][j] + a[i + 2][j] + a[i + 3][j] == 3 ) printf("B\n");
                    else if ( a[i][j + 1] + a[i][j + 2] + a[i][j + 3] == 3 ) printf("C\n");
                    else if ( a[i + 1][j - 1] + a[i + 1][j] + a[i + 2][j - 1] == 3 ) printf("D\n");
                    else if ( a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j + 2] == 3 ) printf("E\n");
                    else if ( a[i + 1][j] + a[i + 1][j + 1] + a[i + 2][j + 1] == 3 ) printf("F\n");
                    else if ( a[i][j + 1] + a[i + 1][j - 1] + a[i + 1][j] == 3 ) printf("G\n");
                    break;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1692
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;

// gcd
LL gcd(LL a, LL b) {
	while(b){
		auto t=a%b;
		a=b;
		b=t;
	}
	return a;
}

//lcm
LL lcm(LL a, LL b) {return a/gcd(a,b)*b;}

// a>=0, b>=0, x*a+y*b=gcd>=0, a>0,b>0=>abs(y)<=a,abs(x)<=b
LL gcdex(LL a,LL b,LL& x, LL& y){
	LL ax=1,ay=0;
	LL bx=0,by=1;
	while(b){
		LL r=a/b;
		LL t=a-r*b; a=b; b=t;
		LL tx=ax-r*bx; ax=bx; bx=tx;
		LL ty=ay-r*by; ay=by; by=ty;
	}
	x=ax;
	y=ay;
	return a;
}
LL modinv(LL a, LL m){
	LL x,y;
	gcdex(a,m,x,y);
	if(x<0){
		x+=m;
	} else if(x>=m){
		x-=m;
	}
	return x;
}
const long long M = 1000000007;

void solve(long long N, std::vector<long long> x){
	vector<LL> dif;
	LL ret=0;
	LL s=0;
	int u=0,v=N-2;
	for(int i=1;i<N-1;i++){
		LL a=modinv(i,M);
		LL b=modinv(i+1,M);
		s+=M+x[v]-x[u];
		s%=M;
		u++;
		v--;
		//cerr << s << ", " << i << ", " << i+1<<endl;
		ret+=s*a%M*b%M;
		ret%=M;
	}
	for(int i=1;i<N;i++){
		LL a=modinv(i,M);
		ret+=(x[N-1]-x[N-1-i])*a%M;
		//cerr << x[N-1]-x[N-1-i] << ", " << i << endl;
		ret%=M;
	}
	for(int i=1;i<N;i++){
		ret*=i;
		ret%=M;
	}
	cout << ret << endl;

}

int main(){
#if 0
	int a[5]={1,2,3,4,5};
	int v[7]={};
	do{
		int r=6;
		int i;
		for(i=0;i<5;i++){
			if(a[i]==1){
				i++;
				break;
			}
		}
		for(;i<5;i++){
			r=min(r,a[i]);
		}
		v[r]++;
	}while(next_permutation(a,a+5));
	for(int i=1;i<=6;i++){
		cerr << i << ", " << v[i] << endl;
	}
#endif
    long long N;
    scanf("%lld",&N);
    std::vector<long long> x(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&x[i]);
    }
    solve(N, std::move(x));
    return 0;
}


Measured memory_bytes: 1656
#include<bits/stdc++.h>
using namespace std;
long long k,a,b;
int main()
{
	cin>>k>>a>>b;
	if(a>=b-1)
	{
		cout<<k+1<<endl;
		return 0;
	}
	if(k<=a)
	{
		cout<<k+1<<endl;
		return 0; 
	}
	long long ans=a;
	k-=a;
	k++;
	ans+=k%2;
	ans+=k/2*(b-a);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto M = readln.chomp.to!int;
    long r, n = -1;
    foreach (_; 0..M) {
        auto dc = readln.split.to!(long[]);
        auto d = dc[0];
        auto c = dc[1];
        if (n == -1) {
            --c;
            n = d;
        }
        while (c) {
            if (c % 2 == 1) {
                ++r;
                n += d;
                if (n >= 10) {
                    ++r;
                    n = 1 + n%10;
                }
            }
            c /= 2;
            r += c;
            d *= 2;
            if (d >= 10) {
                r += c;
                d = 1 + d%10;
            }
        }
    }
    writeln(r);
}

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

char translate(char);

int main()
{
	char b;
	scanf("%c", &b);
	putchar(translate(b));
	putchar('\n');

	return 0;
}

char translate(char c)
{
	switch(c)
	{
	case 'A': return 'T';
	case 'T': return 'A';
	case 'C': return 'G';
	case 'G': return 'C';
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define _GLIBCXX_DEBUG
const int MOD = 1000000007;

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  string S;
  // 1回目の(sx, sy)→(tx, ty)の移動
  for (int i=0; i<ty-sy; i++) cout << 'U';
  for (int i=0; i<tx-sx; i++) cout << 'R';
  // 1回目の(tx, ty)→(sx, sy)の移動
  for (int i=0; i<ty-sy; i++) cout << 'D';
  for (int i=0; i<tx-sx; i++) cout << 'L';
  // 2回目の(sx, sy)→(tx, ty)の移動
  cout << 'L';
  for (int i=0; i<ty-sy+1; i++) cout << 'U';
  for (int i=0; i<tx-sx+1; i++) cout << 'R';
  cout << 'D';
  // 2回目の(tx, ty)→(sx, sy)の移動
  cout << 'R';
  for (int i=0; i<ty-sy+1; i++) cout << 'D';
  for (int i=0; i<tx-sx+1; i++) cout << 'L';
  cout << 'U' << endl;
}

Measured memory_bytes: 256
import math

def check(a, b, d):
  sum = 0
  for i in range(0, d):
  	sum += (a[i] - b[i])**2
  return ((sum - int(math.sqrt(sum))**2) == 0)

n, d = [int(s) for s in input().split()]
xn = []
for i in range(0, n):
  xn.append([int(s) for s in input().split()])

cnt = 0
for i in range(0, n-1):
  for j in range(i+1, n):
    if(check(xn[i], xn[j], d)):
      cnt += 1

print(cnt)

Measured memory_bytes: 3064