akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007
const int MAX = 510000;
const int MOD = 1000000007;

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() {
	ll n,k;
	cin>>n>>k;
	vector<ll> ch;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		ch.push_back(now);
	}
	sort(ch.begin(),ch.end());
    COMinit();	
    ll ans1=0;
	for(ll i=0;i<n;i++){
		ll now=ch[i];
		ll m=COM(n-i-1,k-1);
		//cout <<m<<endl;
		now*=m;
		now%=inf;
		if(now<0){
			now+=inf;
		}
		ans1+=now;
		ans1%=inf;
		if(ans1<0){
			ans1+=inf;
		}
	}
	ll ans2=0;
	reverse(ch.begin(),ch.end());
	for(ll i=0;i<n;i++){
		ll now=ch[i];
		ll m=COM(n-i-1,k-1);
		now*=m;
		now%=inf;
		if(now<0){
			now+=inf;
		}
		ans2+=now;
		ans2%=inf;
		if(ans2<0){
			ans2+=inf;
		}
	}
	if(ans2-ans1<0){
		ans2+=inf;
	}
	cout <<ans2-ans1;
	// your code goes here
	return 0;
}

Measured memory_bytes: 16132
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
 *
 * @author Kenji
 */
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);
        ABC090C solver = new ABC090C();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC090C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            long N = in.nextInt();
            long M = in.nextInt();
            long ans = 0;
            if (N == 1 && M == 1) {
                ans = 1;
            } else if (N == 1 || M == 1) {
                ans = Math.max(N, M) - 2;
                ans = ans < 0 ? 0 : ans;
            } else {
                ans = (N - 2) * (M - 2);
            }
            out.println(ans);
        }

    }
}



Measured memory_bytes: 21460
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include <math.h>
#define MAX 100

#define M 1000000
#define L 12

char H[M][L];

int gC(char ch){
  int ct;
  if(ch=='A'){
    ct = 1;
  }
  else if(ch=='C'){
    ct = 2;
  }
  else if(ch=='G'){
    ct = 3;
  }
  else if(ch=='T'){
    ct = 4;
  }
  return ct;
}

long long gK(char str[]){
  
  long long sum = 0, p = 1, i;
  
  for(i=0;i<strlen(str);i++){
    
    sum += p*(gC(str[i]));
    
    p *= 5;
    
  }
  return sum;
}

int A(int key)
{
  return key%M;
}

int B(int key)
{
  return 1+key%(M-1);
}

int find(char str[])
{
  long long sum;
  int i,j;

  sum = gK(str);

  for(i=0;;i++){
    
    j = (A(sum)+i*B(sum))%M;
    
    if(strcmp(H[j],str)==0) return 1;
    
    else if(strlen(H[j])==0) return 0;
  }
}  

int insert(char str[]){
  long long sum;
  int i,h;

  sum = gK(str);
  
  for(i=0;;i++){
    
    h = (A(sum)+i*B(sum))%M;
    
    if(strcmp(H[h],str)==0) return 1;
    
    else if(strlen(H[h])==0){
      
      strcpy(H[h],str);
      
      return 0;
    }
  }
}

int main(){
  int i,n;
  char str[L],c[9];
  
  for(i=0;i<M;i++) H[i][0] = '\0';
    
  scanf("%d",&n);
    
  for(i=0;i<n;i++){
    
    scanf("%s%s",c,str);
    
    if(c[0]=='i') insert(str);
    
    else{
      
      if(find(str)==1) printf("yes\n");
      
      else printf("no\n");
    }
  }

  return 0;
}  




Measured memory_bytes: 13464
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
      int N = sc.nextInt();
      int[] A = new int[N];
      for(int i=0;i<N;i++){
        A[i] = sc.nextInt();
        if(A[i]%2==0&&A[i]%3!=0&&A[i]%5!=0){
          System.out.println("DENIED");
          return;
        }
      }
      
      System.out.println("APPROVED");
      

    }
  
  private static long lcm(long m, long n) {
    return m * n / gcd(m, n);
}
  
  private static long gcd(long m, long n) {
    if(m < n) return gcd(n, m);
    if(n == 0) return m;
    return gcd(n, m % n);
}
}


Measured memory_bytes: 20948
# abc109_a.py
# https://atcoder.jp/contests/abc109/tasks/abc109_a

# A - ABC333 /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 100点

# 問題文
# 1以上 3 以下の整数 A,Bが与えられます。
# A×B×Cが奇数となるような 1 以上 3 以下の整数 Cが存在するか判定してください。

# 制約
#     入力はすべて整数である
#     1≤A,B≤3

# 入力
# 入力は以下の形式で標準入力から与えられる。
# A B

# 出力
# 条件を満たすような Cが存在するなら Yes、そうでないなら No を出力せよ。

# 入力例 1
# 3 1

# 出力例 1
# Yes

# C=3とすると A×B×C=3×1×3=9となり、奇数となります。

# 入力例 2
# 1 2

# 出力例 2
# No

# 入力例 3
# 2 2

# 出力例 3
# No


def calculation(lines):
    # N = int(lines[0])
    A, B = list(map(int, lines[0].split()))
    if A % 2 != 0 and B % 2 != 0:
        return ['Yes']
    else:
        return ['No']


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3 1']
        lines_export = ['Yes']
    if pattern == 2:
        lines_input = ['1 2']
        lines_export = ['No']
    if pattern == 3:
        lines_input = ['2 2']
        lines_export = ['No']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9256
#include<stdio.h>

int main(void){
    int i,N,D,X;
    scanf("%d",&N);
    scanf("%d%d",&D,&X);
    int A[N];
    for(i = 0;i < N;i++) scanf("%d",&A[i]);
    int ans = X;

    for(i=0;i<N;i++) ans += (D-1)/A[i] + 1;

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

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

#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define SIZE(array) (sizeof(array) / sizeof(array[0]))

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

#define MOD 1000000007L
#define INF 100000000000

signed main() {
	int h, w;
	cin >> h >> w;
	int a[26] = {};
	for (size_t i = 0; i < h; i++) {
		string s;
		cin >> s;
		for (size_t j = 0; j < w; j++) {
			a[s[j] - 'a']++;
		}
	}
	int corn, edge = 0, centor = 0;
	if (w % 2 == 1 && h % 2 == 1) {
		centor = 1;
		edge = (w + h - 2) / 2;
	} else if (w % 2 == 1) {
		edge = h / 2;
	} else if (h % 2 == 1) {
		edge = w / 2;
	}
	corn = (h * w - (edge * 2 + centor)) / 4;
	// cout << corn << "," << edge << "," << centor << endl;
	// corner
	for (size_t i = 0; i < 26; i++) {
		while (a[i] >= 4 && corn > 0) {
			a[i] -= 4;
			corn--;
		}
	}
	// edge
	for (size_t i = 0; i < 26; i++) {
		while (a[i] >= 2 && edge > 0) {
			a[i] -= 2;
			edge--;
		}
	}
	// centor
	for (size_t i = 0; i < 26; i++) {
		if (a[i] == 1) {
			a[i] = 0;
			centor = 0;
		}
	}

	bool ok = corn == 0 && edge == 0 && centor == 0;
	for (size_t i = 0; i < 26; i++) {
		// cout << ((char)(i + 'a')) << ":" << a[i] << endl;
		ok = ok && a[i] == 0;
	}
	cout << (ok ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
n = gets.to_i
h = [[], [], []]
readlines.each do |line|
  a, b, c = line.chomp.split(" ").map(&:to_i)
  h[0].push(a)
  h[1].push(b)
  h[2].push(c)
end

dp = Array.new(n + 1, [])
dp[0] = [0, 0, 0]
(1..n).each do |i|
  dp[i] = [-1.0 / 0, -1.0 / 0, -1.0 / 0]
end

(0..(n - 1)).each do |i|
  (0..2).each do |j|
    (0..2).each do |k|
      dp[i + 1][j] = [dp[i + 1][j], dp[i][k] + h[j][i]].max unless j == k
    end
  end
end

p dp[-1].max

Measured memory_bytes: 44268
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    static String[] test = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};

    public static void main(String[] args) {
    	int N = nextInt();
        String S = next();

        String Answer = "";

        for (int i = 0; i < S.length(); i++) {
        	String dummy = S.substring(i, i+1);
        	Answer += change(dummy, N);
        }
        println(Answer);
    }

    static String change (String str, int num) {
    	for (int i = 0; i < 26; i++) {
    		if (str.equals(test[i])) {
    			int num2 = (i + num) % 26;
    			return test[num2];
    		}
    	}
    	return null;
    }

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

    static String next() {
        return sc.next();
    }

    static String nextLine(){
        return sc.nextLine();
    }

    static void println(Object o) {
        out.println(o);
        out.flush();
    }
}


Measured memory_bytes: 148132
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
void err() {
  cout << 0 << '\n';
  exit(0);
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int cnt[13] = {};
  int n;
  cin >> n;
  cnt[0]++;
  for (int i = 0; i < n; i++) {
    int in;
    cin >> in;
    cnt[in]++;
  }
  int d[24] = {};
  int prv = 0;
  for (int i = 0; i <= 12; i++) {
    if (i == 0 || i == 12) {
      if (cnt[i] >= 2) err();
      if (cnt[i]) d[i] = 1;
    } else {
      if (cnt[i] >= 3) err();
      if (cnt[i] == 2) {
        d[i] = 1;
        d[24 - i] = 1;
        prv = 0;
      }
      if (cnt[i] == 1) {
        if (prv == 0) {
          d[i] = 1;
          prv = 1;
        } else {
          d[24 - i] = 1;
          prv = 0;
        }
      }
    }
  }
  int ans = 1 << 30;
  for (int i = 0; i < 24; i++) {
    for (int j = 0; j < 24; j++) {
      if (i != j && d[i] && d[j]) ans = min(ans, abs(i - j));
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
n = int(input())
st = [input() for _ in range(n)]
count = 0
for s in st:
    count += s.count('AB')
first = 0
last = 0
both = 0
for s in st:
    if s[0] == 'B' and s[-1] == 'A':
        both += 1
    elif s[0] == 'B':
        first += 1
    elif s[-1] == 'A':
        last += 1
if first + last == 0 and both >= 1:
    print(count + both - 1)
else:
    print(count + min(first, last) + both)

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

int main(void)
{
    long long N, M;
    cin >> N >> M;
    vector<long long> vec;

    for (long long i = 1; i <= (long long)pow(M, 0.5); i++)
    {
        if (M % i == 0)
        {  
            if (M / i <= M / N)
            {
                long long ans = M / i;
                cout << ans << endl;
                exit(0);
            }
            else
            {
                vec.push_back(i);
            }                
        }
    }
    for (long long i = 0; i < vec.size(); i++)
    {
        if (vec[i] > M / N)
        {
            cout << vec[i-1] << endl;
            exit(0);
        }
    }
    cout << vec[vec.size()-1] << endl;
}

Measured memory_bytes: 384
let rec upper_bound l r p =
  if r <= 1 + l
  then l
  else let m = (l + r) / 2 in
       if p m 
       then upper_bound m r p
       else upper_bound l m p

let () = Scanf.scanf "%d\n" @@ fun n ->
  let as_ = Array.init n @@ fun _ ->
    Scanf.scanf "%d " @@ fun a -> a in
  let cost x =
    Array.fold_left ( + ) 0 @@
    Array.map (fun y -> (x - y) * (x - y)) as_ in
  Printf.printf "%d\n" @@ cost @@ upper_bound (-10000) 10000 @@ fun i ->
    cost i - cost (i - 1) <= 0


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

inline int64_t max(int64_t a, int64_t b){
  return (a > b ? a : b);
}

int main(){
  int64_t A,B,C,D;
  cin >> A >> B >> C >> D;

  int64_t m0 = B*D;
  int64_t m1 = A*D;
  int64_t m2 = B*C;
  int64_t m3 = A*C;
  int64_t r = max(max(m0,m1), max(m2, m3));
  cout << r << endl;
  
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
vector<ll> ans;
struct edge
{
  ll to;
  ll cost;
  edge() {}
  edge(ll to, ll cost) : to(to), cost(cost){};
};
void dfs(ll x, vector<vector<edge>> &g,vector<ll> &kk, vector<bool> &see)
{
  //点xに対する処理
  see[x] = 1;
  for (auto p : g[x])
  {
    if (see[p.to])continue;
    dfs(p.to, g,kk, see);
    if(kk[p.to]==1){
      kk[p.to]=0;
      kk[x]=(kk[x]+1)%2;
      ans.push_back(p.cost);
    }
  }
}
int main()
{
ll n , m ;
cin >> n >> m ;
map<ll,ll> a;
vector<ll> v,k,kk;
rep(i, n){
  ll aa,b;
  cin >> aa >> b;
  a[aa]=b;
}
for (auto i = a.begin(); i != a.end(); ++i) {
  v.push_back(i->second);
  k.push_back(i->first);
}
kk.push_back(v[0]);
rep(i,n-1){
  if(v[i]!=v[i+1])kk.push_back(1);
  else kk.push_back(0);
}
kk.push_back(v[n-1]);

vector<pair<ll,ll>> l(m);
rep(i, m){
  ll r,rr;
  cin >> r >> rr;
  l[i].first=lower_bound(k.begin(), k.end(), r)-k.begin();
  l[i].second=upper_bound(k.begin(), k.end(), rr)-k.begin();
}
vector<vector<edge>> g(n+1);
rep(i, m)
{
  if(l[i].first==l[i].second)continue;
  g[l[i].first].emplace_back(l[i].second,i+1);
  g[l[i].second].emplace_back(l[i].first,i+1); 
}
vector<bool> see(n+1);
rep(i,n+1){
  if(see[i]==0)dfs(i,g,kk,see);
}
for(auto r:kk){
  if(r!=0){
    cout << -1 << endl;
    return 0;
  }
}
sort(ans.begin(),ans.end());
cout << ans.size() << endl;
for(auto r:ans)cout << r << " ";
cout <<  endl;
return 0;
}

Measured memory_bytes: 32748
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define PI 3.141592
int main(void) {
    double x = 0, y = 0, theta = 0;
    while (1) {
        int d, dir;
        scanf("%d,%d", &d, &dir);
        if (d == 0 && dir == 0) break;
        y += cos((PI * theta) / 180) * d;
        x += sin((PI * theta) / 180) * d;
        theta = (theta + dir);
    }
    cout << (int)(x) << endl;
    cout << (int)(y) << endl;
    return 0;
}

Measured memory_bytes: 1212
from collections import Counter

n = int(input())
s = Counter([input() for i in range(n)])

s = s.most_common()

k = s[0][1]
lst = []
for i in range(len(s)):
    if k == s[i][1]:
        lst.append(s[i][0])
    else:
        break

lst = sorted(lst)
for i in lst:
    print(i)


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

int main(){
	string w;
	cin >> w;
	transform(w.begin(),w.end(),w.begin(),::toupper);
	int c = 0;
	while(1){
		string s;
		cin >> s;
		if(s=="END_OF_TEXT") break;
		transform(s.begin(),s.end(),s.begin(),::toupper);
		if(s==w) c++;
	}
	cout << c << endl;
}

Measured memory_bytes: 1192
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int k = Integer.parseInt(sc.next());
		int[] l = new int[n];
		for (int i = 0; i < n; i++)
			l[i] = Integer.parseInt(sc.next());
		Arrays.sort(l);
		int ans = 0;
		for (int i = 1; i <= k; i++)
			ans += l[n - i];
		System.out.println(ans);
	}
}

Measured memory_bytes: 21716
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long int
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	char x;
	cin>>x;
	if(x>='A'&&x<='Z')
	  cout<<"A"<<endl;
	else
	  cout<<"a"<<endl;
}


Measured memory_bytes: 3604
N=int(input())
S=input()
L=[[0 for j in range(10)]for i in range(N+1)]
R=[[0 for j in range(10)]for i in range(N+1)]
for i in range(N):
    for j in range(10):
        L[i+1][j]=L[i][j]
    L[i+1][int(S[i])]=1
for i in range(N-1,-1,-1):
    for j in range(10):
        R[i][j]=R[i+1][j]
    R[i][int(S[i])]=1
ans=[[[0 for k in range(10)]for j in range(10)] for i in range(10)]
num=[0 for k in range(10)]
for t in range(N):
    X=[]
    Y=[]
    k=int(S[t])
    for x in range(10):
        if L[t][x]==1:
            X.append(x)
    for y in range(10):
        if R[t+1][y]==1:
            Y.append(y)
    for i in X:
        for j in Y:
            if ans[i][j][k]==0:
                ans[i][j][k]=1
                num[k]+=1
print(sum(num))


Measured memory_bytes: 15732
#include <iostream>
#include <set>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int N;
  cin >> N;
  set<int> a;
  REP(i, N) {
    int A;
    cin >> A;
    if (!a.count(A))
      a.insert(A);
    else
      a.erase(A);
  }

  cout << a.size() << endl;
  return 0;
}

Measured memory_bytes: 4864
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N, W := ReadInt(), ReadInt()
	ws := make([]int, N)
	vs := make([]int, N)
	for i := 0; i < N; i++ {
		ws[i] = ReadInt()
		vs[i] = ReadInt()
	}

	maxSumV := int(1e3) * 100
	dp := make([][]int, N)
	for i := 0; i < N; i++ {
		dp[i] = make([]int, maxSumV+1)
		for sumV := 0; sumV <= maxSumV; sumV++ {
			dp[i][sumV] = W + 1
		}
	}

	dp[0][0] = 0
	dp[0][vs[0]] = ws[0]

	for i := 1; i < N; i++ {
		for sumV := 0; sumV <= maxSumV; sumV++ {
			dp[i][sumV] = dp[i-1][sumV]
			if sumV-vs[i] >= 0 {
				dp[i][sumV] = Min(dp[i][sumV], dp[i-1][sumV-vs[i]]+ws[i])
			}
		}
	}

	for sumV := maxSumV; sumV >= 0; sumV-- {
		w := dp[N-1][sumV]
		if w <= W {
			fmt.Println(sumV)
			return
		}
	}
}

func Min(xs ...int) int {
	min := xs[0]
	for _, x := range xs[1:] {
		if min > x {
			min = x
		}
	}
	return min
}

func Max(xs ...int) int {
	max := xs[0]
	for _, x := range xs[1:] {
		if max < x {
			max = x
		}
	}
	return max
}

var sc = bufio.NewScanner(os.Stdin)

func init()        { sc.Buffer(make([]byte, 256), 1e9); sc.Split(bufio.ScanWords) }
func Read() string { sc.Scan(); return sc.Text() }

func ReadInt() int {
	v, e := strconv.Atoi(Read())
	if e != nil {
		panic(e.Error())
	}
	return v
}


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

using namespace std;

void solve()
{
    int n;
    string s, t;
    cin >> s >> n;
    int s1 = 0, s2 = 0;
    while (n--)
    {
        cin >> t;
        if ("replace" == t)
        {
            string u;
            cin >> s1 >> s2 >> u;
            s = s.substr(0, s1) + u + s.substr(s2 + 1);
        }
        else if ("reverse" == t)
        {
            cin >> s1 >> s2;
            t = s.substr(s1, s2 - s1 + 1);
            reverse(t.begin(), t.end());
            s = s.substr(0, s1) + t + s.substr(s2 + 1);
        }
        else
        {
            cin >> s1 >> s2;
            cout << s.substr(s1, s2 - s1 + 1) << endl;
        }
    }
}

int main()
{
    solve();
    return 0;
}



Measured memory_bytes: 3176
N = int(input())
p = list(map(int, input().split()))
ans = 1
for i in range(1, N):
    if i > 1:
        min_value = min(min_value, p[i - 1])
    else:
        min_value = p[0]
    if p[i] <= min_value:
        ans += 1
print(ans)

Measured memory_bytes: 24744
"use strict";
function I(t,i){this._s=t.split("\n"),this._c=0,this._l=0,this._f=i||Number}I.prototype.a=function(t){var i=this._s[this._l];if(i){var s=i.trim().split(" "),h=s[this._c];return this._c++,s.length===this._c&&(this._c=0,this._l++),t?t(h):this._f(h)}},I.prototype.l=function(t){var i=this._s[this._l];if(i)return this._c=0,this._l++,i.split(" ").map(t||this._f)},module.exports=I;

function main(input) {
  var o = new I(input);

  var a = o.a();
  var b = o.a();

  if (a >= 13) {
    console.log(b);
  } else if (a <=5) {
    console.log(0);
  } else {
    console.log(b / 2);
  }
}


main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21956
import java.util.Scanner;
class Main{
    int n,x,y;
    boolean z;
    public void solve(){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(x = 3; x <= n; x++){
            y = x;
            z = false;

                if(y % 3 == 0){
                    System.out.printf(" %d",x);
                    z = true;
                }else{
                    while(z == false){
                        if(y % 10 == 3){
                            System.out.printf(" %d",x);
                            z = true;
                        }
                        y /= 10;
                        if(y < 3){
                            z = true;
                        }
                    }   
                }
        }
        System.out.println();
    }
    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 33736
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int  A,B,C,X,Y;
  cin  >> A >> B >> C >> X >> Y;
  int t=100000000000;
  int a,b;
  for(int i=0; i<=100000; i++){
    a=X-i;
    b=Y-i;
    if(a<0){a=0;}
    if(b<0){b=0;}
    if(A*a+B*b+C*2*i<=t){t=A*a+B*b+C*2*i;}
  }
  cout << t <<endl;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int power10(int n) {
    if (n == 0) return 0;
    int ret = 1;
    rep(i, n) ret *= 10;
    return ret;
}
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int s[10], c[10];
    rep(i, M) {
        cin >> s[i] >> c[i];
        s[i]--;
    }
    int num = -1;
    REP(i, power10(N - 1), power10(N) - 1) {
        //cout << i << endl;
        string S = to_string(i);
        bool ok = true;
        rep(j, M) {
            if (S[s[j]] - '0' != c[j]) ok = false;
        }
        if (ok) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}


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

int main()
{
    vector <int> A(100000);
    int N;
    cin >> N; 

    for(int i=0;i<N;i++){
        cin >>  A.at(i);
    }
    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());
    cout << A.at(0)-A.at(N-1) << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  int a = sc.nextInt();
  int b = sc.nextInt();
  int c = sc.nextInt();
  int d = sc.nextInt();
  int e = sc.nextInt();
  int k = sc.nextInt();
  System.out.println(e-a <= k ? "Yay!":":(");
}}


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

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

using namespace std;

int main(){
    char a[3], c; REPI(i, 3) cin >> a[i];
    int i = 2;
    while(cin >> c){
        if(c == a[i--]) continue;
        else{
            cout << "NO"; return 0;
        }
    }cout << "YES";
}


Measured memory_bytes: 256
MOD = 10**9 + 7

N,K = map(int,input().split())
adj = [list() for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    adj[a].append(b)
    adj[b].append(a)


deg = [0]*N
deg2 = [0]*N
cnt = 1
visited = [False]*N
stack = [0]

while stack:
    u = stack.pop()
    visited[u] = True
    cnt *= K-deg[u]-deg2[u]
    cnt %= MOD
    for v in adj[u]:
        if not visited[v]:
            deg[v] += 1
            deg2[v] += deg[u]
            deg[u] += 1
            stack.append(v)

print(cnt)

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

#define pb push_back
#define PQ priority_queue
#define make_unique(x) sort((x).begin(), (x).end()); (x).erase(unique((x).begin(), (x).end()), (x).end())

typedef long long ll;
typedef long double ld;

//__builtin_popcount(x)

using namespace std;

const int mod = 1e9 + 7;

ll add(ll a, ll b) {
    ll res = a + b;
    if (res >= mod) res -= mod;
    return res;
}

ll sub(ll a, ll b) {
    ll res = a - b + mod;
    if (res >= mod) res -= mod;
    return res;
}

ll mul(ll a, ll b) {
    return (((a % mod) * (b % mod)) % mod);
}

/* Z-FUNCTION
ll l = 0, r = 0, n = (int)s.size();
vector<int> z(n, 0);
for (int i = 1; i < n; i++) {
    if (r >= i) {
        z[i] = min(1ll*z[i-l], r-i+1);
    }
    while (z[i] + i < n && s[z[i]] == s[z[i] + i]) z[i]++;        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
*/

/*vector<int> find_dividers(int x) {
    vector<int> dividers;

    for (int i = 1; i <= sqrt(x); i++) {
        if (x % i == 0) {
           dividers.push_back(i);
            if (i * i != x) {
                dividers.push_back(x / i);
            }
        }
    }

    return dividers;
}*/

/*int nok(int a, int b) {
    return a / __gcd(a, b) * b;
}*/

bool ok(const string& s) {
    int len = (int)s.size();
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - i - 1]) return false;
    }
    return true;
}

void solve() {
    int n, k;
    cin >> n >> k;
    int dp[n+1];
    for (int i = 0; i <= n; i++) dp[i] = mod;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (k >= n) {
        cout << abs(a[n - 1] - a[0]) << endl;
        return;
    }

    for (int i = 1; i <= k; i++) {
        dp[i] = abs(a[i] - a[0]);
    }

    for (int i = k + 1; i < n; i++) {
        for (int j = i - k; j <= i - 1; j++) {
            dp[i] = min(dp[i], abs(a[i] - a[j]) + dp[j]);
        }
    }

    /*for (int i = 0; i <= n; i++) cout << dp[i] << ' ';
    cout << endl;*/

    cout << dp[n-1];
}

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

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

    return 0;
}



Measured memory_bytes: 4012
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(int argc, char* argv[]){
    int d[] = {0, 0, 0, 0, 0};
    int k;
    rep(i, 5){
        cin >> d[i];
    }
    cin >> k;

    bool ok = true;
    rep(i, 5){
        rep(j, 5){
            if(i==j) continue;
            if(abs(d[i]-d[j] > k)) ok = false;
        }
    }
    if(ok){
        cout << "Yay!" << endl;
    } else {
        cout << ":(" << endl;
    }
}

Measured memory_bytes: 256
s=input()[::-1]
i=0
f=True
while 1:
  p=s[i:i+5]
  if not p:break
  if p=="maerd" or p=="esare":
    i+=5
  elif p=="remae":
    if s[i:i+7]=="remaerd":
      i+=7
    else:
      f=False
      break
  elif p=="resar":
    if s[i:i+6]=="resare":
      i+=6
    else:
      f=False
      break
  else:
    f=False
    break
if f:
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3188
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())
 
def solve(S):
    return all(c in 'RUD' for c in S[::2]) and all(c in 'LUD' for c in S[1::2])
    
 
print 'Yes' if solve(rr()) else 'No'

Measured memory_bytes: 28012
while True:
	a,op,b=input().split()
	a=int(a)
	b=int(b)

	if op=="?":
		break
	if op=="+":
		print(a+b)
	if op=="-":
		print(a-b)
	if op=="*":
		print(a*b)
	if op=="/":
		print(a//b)


Measured memory_bytes: 5592
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define IOS cin.tie(0); ios::sync_with_stdio(false)
const int INF = 1e9;
using namespace std;

main() {
    int N; cin >> N;
    int ans=0,pos=0;
    rep(i,N){
        int a; cin >> a;
        if(a>0) pos+=a;
        else {ans+=pos/2; pos=0;}
    }
    ans+=pos/2;
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int res=0;
  int n=S.length();
  for(int i=0; i<S.length(); ++i){
    n=n-1;
    if(i==n || n<i){
      break;
    }
    if(S[i]!=S[n]) res++;
  }
  cout << res;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <utility>
#include <string>
#include <queue>
#include <cmath>
#include <array>

typedef long long ll;

ll nextLunlun(const ll cur)
{
    ll next = cur + 1;

    while(1) {
        const int digits = 1 + std::log10(next);
        bool ok = true;
        for (int i = 1; i < digits; i++) {
            const ll p10 = pow(10, i);
            const ll p1  = pow(10, i - 1);
            const ll n10 = (next / p10) % 10;
            const ll n1  = (next / p1 ) % 10;

            if (abs(n10 - n1) > 1) {
                next += p1;
                next -= (next % p1);
                ok = false;
                break;
            }
        }
        if (ok) {break;}
    }

    return next;
}

ll solve(const int k)
{
    ll count = 1;
    ll c = 1;

    while(count != k) {
        c = nextLunlun(c);
        count++;
    }

    return c;
}

int main(int argc, char *argv[])
{
    int k;

    std::cin >> k;

    ll ans = solve(k);

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 512
#!/usr/bin/env python
# coding: utf-8

# In[1]:


X, Y, Z, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]


# In[14]:


AB = []
for x in range(X):
    for y in range(Y):
        AB.append(A[x] + B[y])
AB.sort(reverse=True)
if K < X * Y:
    AB = AB[:K]
W = len(AB)
AB


# In[16]:


ABC = []
for w in range(W):
    for z in range(Z):
        ABC.append(AB[w] + C[z])
ABC.sort(reverse=True)
if K < W * Z:
    ABC = ABC[:K]
ABC


# In[17]:


print('\n'.join(map(str, ABC)))


# In[ ]:





# In[ ]:






Measured memory_bytes: 151640
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {

  int a,b;
  cin >> a >> b;

  if(a < b) {
    for(int i = 0;i < b;i++) cout << a;
    cout << endl;
  }else {
    for(int i = 0;i < a;i++) cout << b;
    cout << endl;
  }
  
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
/*
time:32m54s
WA:7
桁数が等しくないときは大小自明
桁数が等しいときは先頭から比較していく
文字列Aの先頭はA[0]であることに注意忘れがち!!!!!
これで7回間違えた!!!!!!!!!!
*/
int main() {
    string A, B;
    cin >> A >> B;
    long long na = A.size();
    long long nb = B.size();
    char a, b;
    if(na > nb)  {
        cout << "GREATER" << endl;
    }
    else if(na < nb) {
        cout << "LESS" << endl;
    }
    else if(A == B) {
        cout << "EQUAL" << endl;
    }
    else {
        for(int i = 0; i < na; i++){
            if(A[i] > B[i]) {
                cout << "GREATER" << endl;
                break;
            }
            else if(A[i] < B[i]) {
                cout << "LESS" << endl;
                break;
            }
            else continue;
        }
    }
    return 0;
}

Measured memory_bytes: 3576
n = int(input())
num_t, num_h = 0, 0

for _ in range(n):
    card = input().split()
    if card[0] == card[1]:
        num_t += 1
        num_h += 1
    elif card[0] > card[1]:
        num_t += 3
    else:
        num_h += 3

print(num_t, num_h)


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

int main(){
  int n;
  cin >> n;
  int d[n][2];
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 2; j++){
      cin >> d[i][j];
    }
  }
  
  int cnt = 0;
  int f = 0;
  for(int i = 1; i < n - 1; i++){
    if(d[i - 1][0] == d[i - 1][1] && d[i][0] == d[i][1] && d[i + 1][0] == d[i + 1][1]){
      f = 1;
      cout << "Yes" << endl;
      break;
    }
  }
  if(f == 0){
    cout << "No" << endl;
  }

}

Measured memory_bytes: 3620
#include<stdio.h>
#include<stdlib.h>

int t[11];
int cnt;
int n,s;
//int flg=0;

int sum(int k){
  int i,s=0;

  for(i=0;i<k;i++)
    s+=t[i];
  return s;
}

void backtrack(int i,int k){
  //  flg++;
  //  if(flg>20)
  //   exit(1);
  //  printf("Call:[%d,%d]\n",i,k);
  if(i==10){
    if(k==n){
      if(s==sum(k))
	cnt++;
    }
    //    puts("return");
    return;
  }
  else{
    backtrack(i+1,k);
    t[k]=i;
    backtrack(i+1,k+1);
  }
  //  puts("fall");
}

int main(void){
  
  for(;;){
    scanf("%d%d",&n,&s);
    if(n==0&&s==0)
      break;
    
    if(s<0||45<s||n<1)
      puts("0");
    else{
      cnt=0;
      backtrack(0,0);
      printf("%d\n",cnt);
    }    
  }
  return 0;
}

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

int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  rep(i,n) cin>>a[i];
  
  vector<ll> kosu(200005);
  rep(i,n) kosu[a[i]]++;
  
  ll kumi = 0;
  rep(i,200005){
    kumi += kosu[i]*(kosu[i]-1)/2;
  }
  
  rep(i,n){
    ll ans = kumi -kosu[a[i]]+1;
    cout << ans << endl;
  }
}


Measured memory_bytes: 4992
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n) { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x) { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int n, m;
	while (cin >> n >> m, n) {
		vector<pii> root(n);
		int ans = 0;
		REP(i, n) {
			cin >> root[i].second >> root[i].first;
			ans += root[i].second * root[i].first;
		}
		RSORT(root);
		REP(i, n) {
			if (m - root[i].second < 0) {
				ans -= m*root[i].first;
				break;
			}
			else {
				ans -= root[i].second*root[i].first;
				m -= root[i].second;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3020
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    String r = sc.next();
    String g = sc.next();
    String b = sc.next();
    
    String rgbString = r + g + b;
    int rgbInt = Integer.parseInt(rgbString);
    if (rgbInt % 4 == 0) {
      System.out.println("YES");
    } else {
      System.out.println("NO");
    }
  }
}

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

int main() {
  int a,s;
  cin>>a>>s;
  if ((s-1)%(a-1)==0) {
    cout<<((s-1)/(a-1))<<endl;
  } else {
    cout<<((s-1)/(a-1)+1)<<endl;
  }
}



Measured memory_bytes: 256
#include<stdio.h>
main(){
        int i,j,key,N;
            
            scanf("%d ",&N);
                int a[N];
                    for(i=0;i<N;i++){
                                scanf("%d",&a[i]);
                                    }
                        
                        for(j=1;j<N;j++){
                              for(i=0;i<N;i++){
                                  printf("%d",a[i]);
                                  if(i+1!=N){
                                      printf(" ");
                                  }
                              }
                              printf("\n");
                              key = a[j];
                              i=j-1;
                              while(i>=0 && a[i]>key){
                                  a[i+1]=a[i];
                                  i--;
                              }

                              a[i+1]=key;
                        }
                            
                        for(i=0;i<N;i++){
                            printf("%d",a[i]);
                            if(i+1!=N){
                                printf(" ");
                            }
                        }
                        printf("\n");
}



Measured memory_bytes: 2140
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define Would
#define you
#define please

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


	int N, M;
	cin >> N >> M;
	int A[100000] = {};

	int RT = pow(M, 0.5);
	for (int i = 2; i <= RT; i++) {
		while (M % i == 0) {
			A[i]++;
			M /= i;
		}
	}
	if (M != 1) A[1]++;

	ll pasu[100100][35] = {};
	ll mod = 1e9 + 7;

	rep1(i, N) {
		pasu[i][0] = 1;
		rep1(ii, 34) {
			if (i == 1) pasu[i][ii] = 1;
			else pasu[i][ii] = (pasu[i][ii - 1] + pasu[i - 1][ii]) % mod;
		}
	}

	ll kotae = 1;
	rep(i, 100000) {
		kotae = (kotae * pasu[N][A[i]]) % mod;
	}

	co(kotae);


	Would you please return 0;

}

Measured memory_bytes: 28160
prefectures = Hash.new {|h, k| h[k] = []}

n, m = gets.split.map(&:to_i)
m.times do |i|
  p, y = gets.split.map(&:to_i)
  prefectures[p] << [y, i]
end

puts prefectures.flat_map {|k, v|
  v.sort.map.with_index(1) {|(y, i), j| [i, sprintf("%06d%06d", k, j)]}
}.sort.map(&:last)

Measured memory_bytes: 38640
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
typedef long long ll;
const int MAX = 999999999;

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

    vector<int> nums(n);
    rep(i, n) cin >> nums[i];

    bool flag = true;
    int sum = 0;
    rep(i, n){
        if(nums[i] == *max_element(all(nums)) && flag) {
            sum += nums[i]/2;
            flag = false;
        }
        else{ sum += nums[i];}
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;

int main() {
    ll N,s=0;
    cin>>N;
    vel a(N);
    rep0(i,N){cin>>a[i];}
    sort(all(a));
    rep0(i,N-1){
        s+=a[i+1]-a[i];
    }
    cout<<s<<endl;
}


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

int main(){ 
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<c-(d-b)<<" " ;
    cout<<c-a+d<<" ";
    cout<<a-(d-b)<<" " ;
    cout<<c-a+b;
    return 0;
}


Measured memory_bytes: 256
from itertools import product

h,w,k = map(int, input().split())
g = [['']*w for _ in range(h)]
for i in range(h):
    g[i] = input()

res = 0
for p in product((0,1), repeat = h):
    for q in product((0,1), repeat = w):
        black = 0
        for i in range(h):
            for j in range(w):
                if p[i] == 1 and q[j] == 1 and g[i][j] == '#':
                    black += 1
        if black == k:
            res += 1
print(res)

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

using namespace std;
typedef long long ll; const ll MAX_N = 1 << 18;

ll bit[ MAX_N + 1]; int n; vector<ll> a;

ll sum(ll i){
  ll s = 0;
  while( i > 0){ s += bit[i]; i -= i & -i;}
  return s;}

void add(ll k , ll x){
  while( k <= n){ bit[k] += x; k += k & -k;}
}

ll solve(){
  ll ans = 0;
  for(int j = 0; j < n; j++){
    ans += j - sum( a[j]); add( a[j],1);}
  return ans;}

int main(){
  cin >> n; vector<ll> b(n), c(n); a.resize(n);
  for(int i = 0; i < n; i++){
    cin >> b[i]; c[i] = b[i];}
  
  memset(bit, 0, sizeof(bit));
  sort(c.begin(),c.end());
  for(int i = 0; i < n; i++){
    a[i] = (ll)(lower_bound(c.begin(),c.end(), b[i]) - c.begin()) + 1;}
  
  cout << solve() << endl; return 0;}


Measured memory_bytes: 9696
/*
 * FileName:     merge_sort_fix
 * CreatedDate:  2020-04-13 17:25:44 +0900
 * LastModified: 2020-04-13 21:33:38 +0900
 */

#include <stdio.h>
#define INFTY 1000000001
int count=0;
void merge(long int *s,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;
    long int L[n1+1],R[n2+1];
    for(int i=0;i<n1;i++){
        L[i]=s[left+i];
    }
    for(int i=0;i<n2;i++){
        R[i]=s[mid+i];
    }
    L[n1]=INFTY;
    R[n2]=INFTY;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        if(L[i]<=R[j]){
            s[k]=L[i++];
        }
        else{
            s[k]=R[j++];
        }
        count++;
    }
}
void mergesort(long int *s,int left,int right){
    if(left+1<right){
        int mid = (left+right)/2;
        mergesort(s,left,mid);
        mergesort(s,mid,right);
        merge(s,left,mid,right);
    }
}
int main(void){
    int n;
    scanf("%d",&n);
    long int s[n];
    for(int i=0;i<n;i++){
        scanf("%ld",&s[i]);
    }
    mergesort(s,0,n);
    printf("%ld",s[0]);
    for(int i=1;i<n;i++){
        printf(" %ld",s[i]);
    }
    printf("\n");
    printf("%d\n",count);
    return 0;
}



Measured memory_bytes: 9544
k=int(input())
a=[]
def judge(x):
    if x> 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i)<=1:
            judge(x*10+i)

for i in range(1,10):
    judge(i)

a.sort()
print(a[k-1])


Measured memory_bytes: 7664
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define EPS 10e-6
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;
typedef long long ll;
int a, b;

int gcd(int a, int b){
	if(a < b) return gcd(b,a);
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main(){
	while(cin >> a >> b){
		cout << gcd(a, b) << " " << (a/gcd(a,b))*b << endl;
	}
	
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define dup(x,y) (((x)+(y)-1) / (y)) //整数型のまま切り上げ演算する
#define PI 3.14159265359
typedef long long LL;
template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> inline T gcd(T x, T y) { if (y == 0) { return x; } else if (x == 0) { return y; }return gcd(y, x % y); }
template<class T> inline T lcm(T x, T y) { return (x * y) / gcd(x, y); }
template<class T> inline vector<T> convert_to_binary_number(T x) { vector<T> binary_num; while (x != 1) { binary_num.push_back(x % 2); x /= 2; } binary_num.push_back(1); return binary_num; }
template<class T> inline void print_vector(vector<T> vec) { for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl;}
vector<LL> make_divisors(LL n){vector<LL> divisors;for(int i = 1; i <= sqrt(n); i++) {if(n%i == 0){divisors.push_back(i);if(i != n/i){divisors.push_back(n / i);}}}return divisors;}
const LL MOD = 1e9 + 7;
const LL INF = 1LL << 60;

int main(void){
    LL N, M;
    cin >> N >> M;

    LL ans = 0;
    if(N >= M / 2) {
        ans = M / 2;
    }else{
        ans = N;
        M -= N * 2;
        ans += M / 4;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#! /usr/bin/env python3

alp = 'abcdefghijklmnopqrstuvwxyz'
S = input()
if S == alp[::-1]:
    print(-1)
else:
    if len(S) == len(alp):
        s = []
        for i in range(1, len(S))[::-1]:
            s += [S[i]]
            r = [x for x in s if x > S[i-1]]
            if r:
                print(S[:i-1] + sorted(r)[0])
                break
    else:
        for i in S : alp = alp.replace(i, '')
        print(S+alp[0])

Measured memory_bytes: 3064
A = [[]]*3
for row in range(3):
    A[row] = list(map(int, input().split()))
n = int(input())
B = [0]*n
for i in range(n):
    B[i] = int(input())
flag = False


def check_bingo(A, B):
    for row in range(3):
        if A[row][0] and A[row][1] and A[row][2]:
            return True

    for col in range(3):
        if A[0][col] and A[1][col] and A[2][col]:
            return True

    if A[0][0] and A[1][1] and A[2][2]:
        return True
    if A[0][2] and A[1][1] and A[2][0]:
        return True
    return False


for row in range(3):
    for col in range(3):
        if A[row][col] in B:
            A[row][col] = True
        else:
            A[row][col] = False

print("Yes" if check_bingo(A, B) else "No")

Measured memory_bytes: 9256
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define substr(s,f,t) (s.substr(f-1,t-f+1))
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{ll x,y,t;};
struct Edge{ll to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}
};
vi a;
int k;
bool check(int dust){
  bool dp[a.size()+1][k+1];
  for(int i=0;i<a.size()+1;i++)for(int j=0;j<k+1;j++)dp[i][j]=false;
  dp[0][0]=true;
  for(int i=0;i<a.size();i++){
    for(int j=0;j<=k;j++){
      if(i==dust){
	dp[i+1][j]=dp[i][j];
      }else{
	if(dp[i][j]){
	  dp[i+1][j]=true;
	  if(j+a[i]<=k)
	    dp[i+1][j+a[i]]=true;
	}
      }
    }
  }
  if(k<a[dust])return false;
  for(int i=k-a[dust];i<k;i++){
    if(dp[a.size()][i])return true;
  }
  return false;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n>>k;
  for(int i=0;i<n;i++){
    ll num;cin>>num;
    if(num<=k)a.pb(num);
  }
  // if(sum<k){cout<<n<<endl;return 0;}
  sort(ALL(a));
  int left=-1,right=a.size();
  while(right-left>1){
    int mid=(left+right)/2;
    if(!check(mid)){
      left=mid;
    }else{
      right=mid;
    }
  }
  cout<<left+1<<endl;
  return 0;
}


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

namespace ConsoleApp15
{
    class Class60
    {
        static void Main()
        {
            string S = Console.ReadLine();

            long ans = 0;
            for(int bit = 0;bit<(1<<S.Length-1); bit++)
            {
                long sum = int.Parse(S[0].ToString());
                for(int i = 1; i < S.Length; i++)
                {
                    if ((bit & (1 << i-1)) != 0)
                    {
                        sum *= 10;
                        sum += int.Parse(S[i].ToString());
                    }
                    else
                    {
                        ans += sum;
                        sum = int.Parse(S[i].ToString());
                    }
                }
                ans += sum;
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11092