akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile, permutations


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N, M, R = readi(3)
    rs = readi1(R)

    G = arr(N, N, fill_value=10 ** 10)
    for i in range(N):
        G[i][i] = 0

    for _ in range(M):
        a, b, c = readi(3)
        G[a - 1][b - 1] = c
        G[b - 1][a - 1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

    ans = 10 ** 10
    for perm in permutations(rs):
        tmp = 0
        for i in range(len(perm) - 1):
            tmp += G[perm[i]][perm[i + 1]]
        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 49372
# coding:utf-8
for i in range(int(input())):
	a,b =int(input()),int(input())
	if a>=pow(10,80) or b>=pow(10,80):
		print("overflow")
	else:
		big = a+b
		if big >= pow(10,80):
			print("overflow")
		else:
			print(big);

Measured memory_bytes: 7704
#include<bits/stdc++.h> 
using namespace std; 
typedef long  double ll;
ll MOD=1e9+7;
const ll MAX=1e18;
 
void solve(){
     int n;cin>>n;
     ll ans=1;
     ll a[n];
     for(auto &x:a)cin>>x;
     sort(a,a+n);
     for(int i=0;i<n;i++){
         ans*=a[i];
         if(ans==0){cout<<0<<endl;return;}
         if(ans>MAX){cout<<-1<<endl;return;}
     }
     cout<<(long long int)ans<<endl;
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;t=1;
    // cin>>t;
    // cin.ignore();
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 5308
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    Int N, D; cin >> N >> D;
    cout << (N + (D*2+1)-1) / (D*2+1) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define db double
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define maxn 5005
#define mod 998244353
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define vv(z,a,b) vector<vector<int>>z(a,vector<int>(b))
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(c) begin(c),end(c)
#define pp pair<int,int>
#define fix(n) fixed << setprecision(n)
#define gmax(a,b) __gcd(a,b)
#define gmin(a,b) a/__gcd(a,b)*b
using namespace std;


int main(){

int n,m,k;
cin>>n>>m>>k;
vll a(n+1);
vll b(m+1);
rep(i,n+1){
ll an=0;

if(i==0)a.at(i)=0;
else {
cin>>an;
a.at(i)=a.at(i-1)+an;
}
}
rep(i,m+1){
int an=0;
if(i==0)b.at(i)=0;
else {
cin>>an;
b.at(i)=b.at(i-1)+an;
}
}
ll sum=0;
ll ans=0;
int ko=0;
rep(i,n+1){ 
	for(int j=m;j>=0;--j){
		sum=a.at(i)+b.at(j);
		if(sum<=k){
			ll anti =i+j;
			ans=max(ans,anti);
			m=j;
			break;
		}
		
	}
}

cout<<ans<<endl;

return 0;
}

Measured memory_bytes: 6408
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    d = list(map(int, input().split()))
    s = [i for i in range(10) if i not in d]
    for i in range(n, 10*n+1):
        for j in map(int, list(str(i))):
            if j in d:
                break
        else:
            print(i)
            break

if __name__ == '__main__':
    main()

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

int seg[][8] = {
	// 0 1 2 3 4 5 6 
	{  1,1,1,0,1,1,1}, // 0
	{  0,0,1,0,0,1,0}, // 1
	{  1,0,1,1,1,0,1}, // 2
	{  1,0,1,1,0,1,1}, // 3
	{  0,1,1,1,0,1,0}, // 4
	{  1,1,0,1,0,1,1}, // 5
	{  1,1,0,1,1,1,1}, // 6
	{  1,0,1,0,0,1,0}, // 7
	{  1,1,1,1,1,1,1}, // 8
	{  1,1,1,1,0,1,1}, // 9	
};

int broken[14][8];

int days[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool is_uruu(int y){
	return y % 400 == 0 || (y % 100 && y % 4 == 0);
}

void succ(int &y, int &m, int &d){
	++d;
	int md = days[m];
	if(m == 2 && is_uruu(y)) ++md;
	if(d > md) ++m, d = 1;
	if(m > 12) ++y, m = 1;
}

int count(int idx, int len, int x){
	int res = 0;
	for(int i = idx + len - 1; i >= idx; --i){
		int k = x%10;
		for(int j = 0; j < 7; ++j){
			if(seg[k][j] && !broken[i][j]) ++res;
		}
		x /= 10;
	}
	return res;
}

int cnt[1000];

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

	int k;
	cin >> k;
	while(k--){
		int p, i;
		cin >> p >> i;
		broken[p][i] = 1;
	}

	const int hi = 8;
	for(int i = 0; i < 60*60*24; ++i){
		int h = i/3600;
		int m = i%3600/60;
		int s = i%60;

		++cnt[count(hi, 2, h) + count(hi+2, 2, m) + count(hi+4, 2, s)];
	}

	long long ans = 0;
	int y = 0, m = 1, d = 1;
	while(y < 10000){
		int x = count(0, 4, y) + count(4, 2, m) + count(6, 2, d);
		if(x <= n) ans += cnt[n-x];
		succ(y, m, d);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1164
(defun splitat (c line)
  (labels ((rec (line acc)
				(let ((pos (position-if (lambda(cc) (char= c cc)) line)))
				  (if pos
					  (rec (subseq line (1+ pos)) (cons (subseq line 0 pos) acc))
					(nreverse (cons line acc))))))
	(rec line nil)))
(defun f (ns line)
  (let* ((n (parse-integer ns))
		 (arr (map 'vector (lambda(a) (parse-integer a)) (splitat #\space line))))
	(labels ((rec (i acc)
				  (if (< i (- n 2))
					(progn
					  (let ((a0 (elt arr i))
							(a1 (elt arr (1+ i)))
							(a2 (elt arr (+ i 2))))
						(rec (1+ i) (if (or (and (<= a0 a1) (<= a1 a2))
											(and (>= a0 a1) (>= a1 a2))
											)(1+ acc) acc))))
					acc)))
	  (format t "~A" (rec 0 0)))))

(let (
	  (line0 (read-line nil nil))
	  (line1 (read-line nil nil))
	  )
  (f line0 line1))


Measured memory_bytes: 17000
package main

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

var sc = bufio.NewScanner(os.Stdin)

func ri() (n int) {
	sc.Scan()
	b := sc.Bytes()
	if b[0] == 45 {
		return -b2i(b[1:])
	} else {
		return b2i(b)
	}
}

func b2i(a []byte) (n int) {
	for _, v := range a {
		n = n*10 + int(v-48)
	}
	return
}

func main() {
	sc.Split(bufio.ScanWords)
	n := ri()

	sum := 0
	minAbs := int(1e10)
	ctOdd := 0
	for i := 0; i < n; i++ {
		x := ri()
		if x < 0 {
			ctOdd++
			x *= -1
		}
		sum += x
		if x < minAbs {
			minAbs = x
		}
	}

	if ctOdd%2 == 0 {
		fmt.Println(sum)
	} else {
		fmt.Println(sum - minAbs*2)
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <iomanip>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp unordered_map<int,int>
#define pb push_back
using namespace std;
using vi=vector<int>;
mp h;
int n,q,a,b,p,x;
vector<vi> arr;
vi ans;
vector<bool> visited;
void dfs(int u,int c){
	visited[u]=1;
	ans[u]=(c+h[u]);
	for(auto &v:arr[u]){
		if(!visited[v]) dfs(v,ans[u]);
	}
}
int main() {
	// your code goes here
	fast;
	cin>>n>>q;
	arr=vector<vi>(n);
	ans=vi(n);
	visited=vector<bool>(n,0);
	for(int i=0;i<n-1;i++){
		cin>>a>>b;
		arr[a-1].pb(b-1);
		arr[b-1].pb(a-1);
	}
	for(int i=0;i<q;i++){
		cin>>p>>x;
		h[p-1]+=x;
	}
	dfs(0,0);
	for(int i=0;i<n;i++) cout<<ans[i]<<" ";
	return 0;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int n, k; cin >> n >> k;
	int r, s, p; cin >> r >> s >> p;
	map<char, int> score;
	score['s'] = r;
	score['p'] = s;
	score['r'] = p;
	string t; cin >> t;
	ll ret = 0;
	for (int i=0; i<k; i++) {
		char prev = t[i];
		ret += score[prev];
		char now;
		for (int j=1; i+k*j<n; j++) {
			now = t[i + k*j];
			if (prev==now) {
				prev = 'x';
				continue;
			} else {
				ret += score[now];
				prev = now;
			}
		}
	}
	cout << ret << endl;
	return 0;
}

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

const int N = 3000;
int dp[N+1][N+1];

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

	string a, b;
	cin >> a >> b;
	for (int i = 1; i <= a.size(); ++i) {
		for (int j = 1; j <= b.size(); ++j) {
			if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	}
	string res = "";
	int i = a.size();
	int j = b.size();
	while(i > 0 && j > 0) {
		if (a[i-1] == b[j-1]) {
			res.push_back(a[i-1]);
			--i;
			--j;
		} else {
			if (dp[i-1][j] > dp[i][j-1]) --i;
			else --j;
		}
	}
	for (int x = (int)res.size() - 1; x >= 0; --x) {
		cout << res[x];
	}
	cout << '\n';
}


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

int H, W;
vector<vector<int>> cells(20, vector<int>(20, -1));

vector<int> dw = {1, 0, -1, 0};
vector<int> dh = {0, 1, 0, -1};

bool inside(int h, int w) {
  if (h >= 0 && h < H && w >= 0 && w < W) return true;
  return false;
}

int calc(int i, int j) {
  vector<vector<int>> d(H, vector<int>(W));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      d[i][j] = cells[i][j];
    }
  }
  d = cells;
  // for (int i = 0; i < d.size(); i++) { cout << d[i][0]; for (int j = 1; j < d[i].size(); j++) { cout << ' ' << d[i][j]; } cout << '\n'; }
  int ans = 0;

  queue<pair<int, int>> q;
  q.push(make_pair(i, j));
  d[i][j] = 0;

  while (!q.empty()) {
    pair<int, int> c = q.front(); q.pop();
    int ch = c.first; int cw = c.second;
    for (int i = 0; i < 4; i++) {
      int nh = ch + dh[i];
      int nw = cw + dw[i];
      if (inside(nh, nw) && d[nh][nw] == -1) {
        d[nh][nw] = d[ch][cw] + 1;
        q.push(make_pair(nh, nw));
        ans = max(ans, d[nh][nw]);
      }
    }
  }
  return ans;
}

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

  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    string s; cin >> s;
    for (int j = 0; j < W; j++) {
      if (s[j] == '#') cells[i][j] = -10;
    }
  }

  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (cells[i][j] == -1) {
        ans = max(ans, calc(i, j));
      }
    }
  }

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

Measured memory_bytes: 256
Q,H,S,D = map(int, input().split())
N = int(input())

ans = 0
if N % 2 == 0:
    ans = min(8*Q, 4*H, 2*S, D)*N//2
else:
    ans = min(8*Q, 4*H, 2*S, D)*(N//2) + min(4*Q, 2*H, S)

print(ans)


Measured memory_bytes: 2940
class Node
    attr_accessor :key, :left, :right, :parent

    def initialize(key)
        @key = key
    end

    def depth
        parent == nil ? 0 : parent.depth + 1
    end

    def to_s
        key_s = "key = #{@key}, "
        parent_s =  @parent==nil ? "" : "parent key = #{@parent.key}, "
        left_s = @left==nil ? "" : "left key = #{@left.key}, "
        right_s = @right==nil ? "" : "right key = #{@right.key}, "
        key_s + parent_s + left_s + right_s
    end
end

gets
nodes = []
gets.chomp.split(" ").map(&:to_i).each_with_index do |key, index|
    node = Node.new(key)
    nodes.push(node)
    next if index == 0
    parent = nodes[(index+1)/2-1]
    if index.odd?
        parent.left = node
    else
        parent.right = node
    end
    node.parent = parent
end
nodes.each_with_index do |node, index|
    puts "node #{index+1}: #{node.to_s}"
end



Measured memory_bytes: 6884
#include <iostream>
#include <vector>
#include <cstdio>

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

using namespace std;

inline int getInt(){ int ret; scanf("%d\n", &ret); return ret; }

const int all = 'z' - 'a' + 1;

int m[all];
int cnts[8] = { 3,3,3,3,3,4,3,4 };
void init(){
  int ptr = 0;
  REP(i,8) REP(j,cnts[i])
    m[ptr++] = i + 2;
}

vector<string> words;

struct trie{
  struct trie *next[10];
  vector<int> word;
} buff[50 * 100];

int ptr = 0;

void initTrie(){
  ptr = 0;
}

trie *alloc(){
  trie *ret = &buff[ptr++];
  ret->word.resize(0);
  REP(i,10) ret->next[i] = NULL;
  return ret;
}

void addTrie(trie *now, const char *str, int i){
  if(str[i] == '\0'){
    now->word.push_back(words.size() - 1);
  }else{
    int id = m[str[i] - 'a'];

    if(now->next[id] == NULL)
      now->next[id] = alloc();

    addTrie(now->next[id], str, i + 1);
  }
}

int anss[400];
int ansptr;

void solve(trie *now, char *num, trie *root){
  REP(i,now->word.size()){
    anss[ansptr++] = now->word[i];
    solve(root, num, root);
    ansptr--;
  }

  if(*num == '\0'){
    if(now == root){
      // found answer
      REP(i,ansptr)
        printf("%s%c", words[anss[i]].c_str(), i == ansptr - 1 ? '.' : ' ');
      puts("");
    }else{
      // back track (do nothing)
    }
  }else{
    int nn = *num - '0';

    if(now->next[nn] != NULL){
      solve(now->next[nn], num + 1, root);
    }
  }
}

int main(){
  init();

  while(int n = getInt()){
    initTrie();
    words = vector<string>();

    trie *root = alloc();

    REP(i,n){
      char str[60]; scanf("%s", str);
      words.push_back(str);
      addTrie(root, str, 0);
    }

    char nums[400]; scanf("%s", nums);

    solve(root, nums, root);
    puts("--");
  }

  return 0;
}

Measured memory_bytes: 0
import sys
input = sys.stdin.readline


def solve():
  n,a,b = (int(i) for i in input().split())
  mod = 10**9+7
  all = pow(2,n,mod)-1
  
  comba = 1
  inva = 1
  for i in range(1,a+1):
    comba *= (n-i+1)
    comba %= mod
    
    inva *= i
    inva %= mod

  ta = pow(inva,10**9+5,mod)
  comba = (comba * ta)%mod
  
  combb = 1
  invb = 1
  for i in range(1,b+1):
    combb *= (n-i+1)
    combb %= mod
    
    invb *= i
    invb %= mod
  tb = pow(invb,10**9+5,mod)
  combb = (combb * tb)%mod
  
  print((all-comba-combb)%mod)
  
solve()

Measured memory_bytes: 3064
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, M = map(int, input().split())

    if 2*N >= M:
        ans = M // 2
    else:
        top = M // 2
        btm = 0

        while top - btm > 1:
            mid = (top + btm)//2
            if check(N + mid, M - 2*mid):
                btm = mid
            else:
                top = mid

        ans = N + btm

    print(ans)

def check(a, b):
    return 2*a <= b

if __name__ == '__main__':
    solve()

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

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 10;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<ll> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

int main() {
    map<string, ll> m;

    int n;
    cin >> n;
    rep(i, n) {
        int command;
        string k;
        cin >> command >> k;
        if (command == 0) {
            ll v;
            cin >> v;
            m[k] = v;
        } else if (command == 1) {
            cout << m[k] << endl;
        } else if (command == 2) {
            m.erase(k);
        }
    }

}



Measured memory_bytes: 27776
/* ファイル名：ITP1_9_D.c	*/
/* 内容：文字列 str に対して、次の与えられた命令の列を実行する				*/
/*		 print a b: str の a 文字目から b 文字目までを出力する。			*/
/*		 reverse a b: str の a 文字目から b 文字目までを逆順にする。		*/
/*		 replace a b p: str の a 文字目から b 文字目までを p に置き換える。	*/
/* include	*/
#include <stdio.h>
#include <string.h>

/* 外部変数宣言	*/

/* プロトタイプ宣言	*/

/* 関数名:main	*/
/* 処理内容:文字列 str に対して、与えられた命令の列を実行する	*/
int main( void )
{
	/* 内部変数定義	*/
	/* 入力	*/
	char str[1001];	/* 入力される文字列			*/
	char cmd[8];	/* 命令文字列				*/
	int n;			/* 与えられる命令の数		*/
	int a;			/* 入力される文字の位置1	*/
	int b;			/* 入力される文字の位置2	*/
	char p[1001];	/* 置き換える文字列			*/
	
	/* 処理	*/
	int i;			/* ループ用変数1			*/
	int j;			/* ループ用変数2			*/
	int inc;		/* インクリメント変数		*/
	int dec;		/* デクリメント変数			*/
	char rev;		/* 入れ替え用変数			*/
	
	/* 入力処理	*/
	scanf("%s",str);	/* 文字列の取得	*/
	
	scanf("%d",&n);		/* 命令の数を取得	*/
	
	/* 命令の数だけループ	*/
	for(i = 0; i < n; i++){
		scanf("%s",cmd);	/* 命令文字列を取得	*/
		
		/* 命令が"print"だった場合	*/
		if(strcmp(cmd,"print") == 0){
			scanf("%d %d",&a, &b);	/* aとbを取得	*/
			for(j = a; j <= b; j++){
				printf("%c",str[j]);	/* 文字列を1文字ずつ出力	*/
			}
			
			printf("\n");
		}
		/* 命令が"reverse"だった場合	*/
		else if(strcmp(cmd,"reverse") == 0){
			scanf("%d %d",&a, &b);	/* aとbを取得	*/
			
			inc = a;				/* インクリメント変数初期化		*/
			dec = b;				/* デクリメント変数初期化		*/
			
			/* 文字列の逆順にする範囲の中心までループ	*/
			while(inc < dec){
				/* a番目からb番目の入れ替え	*/
				rev = str[inc];
				str[inc] = str[dec];
				str[dec] = rev;
				inc++;
				dec--;
			}
		}
		/* 命令が"replace"だった場合	*/
		else if(strcmp(cmd,"replace") == 0){
			scanf("%d %d %s",&a, &b, p);	/* aとbとpを取得	*/
			
			/* pの長さまでループ*/
			for(j = 0; j < b - a + 1 ; j++){
				str[a + j] = p[j];			/* pをstrのa番目からb番目にコピー	*/
			}
		}
		/* 命令がどれにも該当しなかった場合	*/
		else{
			/* 処理なし	*/
		}
	}
	return 0;
}



Measured memory_bytes: 2104
#include<stdio.h>

int main(void){
    char s[65536];
    int i,y = 0;
    gets(s);
    for(i = 0;i <= 65535;i++){
        if(97 <= s[i] && s[i] <= 122){
            s[i]-=32;
        }   
    }   
    printf("%s\n",s);
    return 0;
}

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

typedef long long ll;

main()
{
    ll n, k, sum, c = 1;
    cin >> n >> k;
    ll arr[n];
    for(ll i = 0; i < n; i++){
        cin >> arr[i];
    }
    if(n == k){
        cout << 1;
    }
    else if(k == 2){
        cout << n - 1;
    }
    else{
        n = n - k - 1;;
        while(n >= 0){
            n = n - (k - 1);
            c++;
        }
        cout << c;
    }
}





///promy_pompom
//hello world


Measured memory_bytes: 4368
N, M = map(int, input().split())
A = list(map(int, input().split()))
from heapq import heapify, heappop, heappush
dis = []
for k in range(N):
  dis.append((-(A[k]-A[k]//2), k, 0))
heapify(dis)
while M:
  M -= 1
  item = heappop(dis)
  index = item[1]
  cnt = item[2] + 1
  discount = A[index]//pow(2, cnt) - A[index]//pow(2, cnt+1)
  heappush(dis, (-discount, index, cnt))

ans = 0
while dis:
  item = dis.pop()
  ans += A[item[1]]//pow(2, item[2])

print(ans)


Measured memory_bytes: 101300
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

int main(){
	int N, tmp, counter = 1, result = 0;
	cin >> N;
	vector<int> v;
	for(int i = 0; i < N; ++i){
		cin >> tmp;
		v.push_back(tmp);
	}
	int last = v[0];
	bool is_continue = false;
	for(int i = 1; i < v.size(); ++i){
		if(v[i] == last && !is_continue){ //連続 かつ 初めての連続
			counter = 2;
			is_continue = true;
		} else if(v[i] == last && is_continue){ //連続 かつ 前回も連続
			counter++;
		} else if(v[i] != last && is_continue){ //連続でない かつ 前回は連続
			result += counter / 2;
		}
		if(v[i] != last){
			is_continue = false;
			counter = 0;
		}
		last = v[i];
	}
	if(is_continue == true){
		result += counter / 2;	
	}
	cout << result << endl;
}


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

int main(){
    int h, w;
    while(1){
        cin >> h >> w;
        if(h == 0 && w == 0) break;
        for(int y = 0; y < h; y++){
            for(int x = 0; x < w; x++){
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
 
int main() {
    int W, H, N;
    int x[110];
    int y[110];
    int a[110];

    cin >> W >> H >> N; 
    int A[W][H];
    for(int i = 0; i < N; i++) {
        cin >> x[i] >> y[i] >> a[i];
    }

    for(int j = 0; j < W; j++) {
        for(int k = 0; k < H; k++) {
            A[j][k] = 1;
        }
    }
    for(int i = 0; i < N; i++) {
        if(a[i] == 1) {
            for(int j = 0; j < x[i]; j++) {
                for(int k = 0; k < H; k++) {
                    A[j][k] = 0;
                }
            }
        }
        if(a[i] == 2) {
            for(int j = x[i]; j < W; j++) {
                for(int k = 0; k < H; k++) {
                    A[j][k] = 0;
                }
            }
        }
        if(a[i] == 3) {
            for(int j = 0; j < W; j++) {
                for(int k = 0; k < y[i]; k++) {
                    A[j][k] = 0;
                }
            }
        }
        if(a[i] == 4) {
            for(int j = 0; j < W; j++) {
                for(int k = y[i]; k < H; k++) {
                    A[j][k] = 0;
                }
            }
        }
    }

    int count = 0;
    for(int j = 0; j < W; j++) {
        for(int k = 0; k < H; k++) {
            if(A[j][k] == 1) {
                count++;
            }
        }
    }
    cout << count << endl;

}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <cstdio>
#include <numeric>

using namespace std;

long long gcd(long long a, long long b)
{
    while(b != 0)
    {
        long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    long long A, B;
    cin >> A >> B;

    cout << (A*B)/gcd(A,B) << endl;

    return 0;
}

Measured memory_bytes: 888
import copy
import fractions
N=int(input())
A=list(map(int,input().split()))
ans=[]
L=[0 for i in range(N)]
R=[0 for i in range(N)]
for i in range(N):
  if i != 0:
    L[i]=fractions.gcd(L[i-1],A[i-1])
    R[N-1-i]=fractions.gcd(R[N-i],A[N-i])

for i in range(N):
  ans.append(fractions.gcd(L[i],R[i]))

print(max(ans))

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

int n, a[101010], b[101010], c[101010];

int main(){
  cin >> n;
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> b[i];
  rep(i, n) cin >> c[i];
  sort(a, a + n);
  sort(b, b + n);
  sort(c, c + n);
  
  long long int res = 0;
  rep(i, n){
    auto right_a = upper_bound(a, a + n, b[i] - 1);
    auto left_c = lower_bound(c, c + n, b[i] + 1);
    long long int num_a = (right_a - a);
    long long int num_c = n - (left_c - c);
    //cerr <<num_a<<" "<<num_c<<" "<< num_a * num_c << endl;
    res += num_a * num_c;
  }
  cout << res << endl;
  return 0;
}


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

int n, a[100005];
string s;
int main() {
	int i, k;
	cin>>s;
	n = s.size();
	for(i=0; i<n; i++) {
		if(s[i]=='R') k = i;
		else a[k + (i-k)%2]++;
	}
	for(i=n-1; i>=0; i--) {
		if(s[i]=='L') k = i;
		else a[k - (k-i)%2]++;
	}
	for(i=0; i<n; i++) printf("%d ", a[i]);
	return 0;
}

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

int main() {
    char c;
    cin >> c;
    if (c == 'A') {
        cout << 'T';
    } else if (c == 'T') {
        cout << 'A';
    } else if (c == 'G') {
        cout << 'C';
    } else {
        cout << 'G';
    }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    private void execute() throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String s1, s2;
        if (s.length() % 2 == 0) {
            s1 = s.substring(0, s.length() / 2);
            s2 = s.substring(s.length() / 2);
        } else {
            s1 = s.substring(0, (s.length() - 1) / 2);
            s2 = s.substring((s.length() / 2) + 1);
        }
        s2 = new StringBuffer(s2).reverse().toString();
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                count++;
            }
        }
        System.out.println(count);
    }

    public static void main(String[] args) {
        try {
            new Main().execute();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

}

Measured memory_bytes: 23124
#include <cstdio>
#define scanf __builtin_scanf

int S[100010];

int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for(int i=0; i<m; ++i) {
        int L, R; scanf("%d%d", &L, &R);
        S[L]++;
        S[R+1]--;
    }
    int res=0;
    for(int i=0; i<=n+1; ++i) {
        S[i+1]+=S[i];
        if (S[i+1]==m) ++res;
    }
    printf("%d\n", res);
}


Measured memory_bytes: 512
#include <stdio.h>
int main(){
  int a, b, c, i, sum1 = 0, sum2 = 0, A = 0, x = -1 ;
   
  scanf("%d %d %d", &a, &b, &c);
   

  while(sum1<=60*60){
    if(sum2<=c && c<=sum2+a)break;
    
    if(sum2+a+b>=60)sum1+=60;
    sum2 = ( sum2 + a + b )%60;    
    

  }

  if(sum1>60*60)printf("-1\n");
  else printf("%d\n", sum1+c);
  
  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  rep(i,1000){
    int a = i%10;
    int b = max( 0, (i%100 - a)/10 );
    int c = i/100;
    bool ok1 = false, ok2 = false, ok3 = false;
    rep(j,n){
      if(s[j]-'0' == c && !ok1){ ok1 = true; continue; }
      if(s[j]-'0' == b && ok1 && !ok2){ ok2 = true; continue;}
      if(s[j]-'0' == a && ok1 && ok2){ ok3 = true; }
    }
    if(ok3) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn][2];
map<int,int>mp;
map<int,int>wa;
int main(){
    int n,m;
    cin>>n>>m;
    int sum=0;
    int sum2=0;
    for(int i=1;i<=m;++i){
        int p;
        string s;
        cin>>p>>s;
        if(s=="WA"&&mp[p]==0){
            wa[p]++;
        }
        else if(s=="AC"&&mp[p]==0){
            mp[p]=1;
            sum++;
            sum2+=wa[p];
        }
    }
    cout<<sum<<" "<<sum2<<endl;
}


Measured memory_bytes: 9600
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;

int main() {
	int n,y;
	cin >> n>>y;
	y /= 1000;
	
	for (int i=0;i<=n;i++) {
	for (int j=0;j<=n-i;j++) {
	if (i*10+j*5+(n-i-j)*1==y) {
	printf("%d %d %d\n", i, j, n-i-j);
	return 0;
	}
	}
	}
	
	printf("-1 -1 -1\n");
	return 0;
}



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

using namespace std;

main(){
    double r;
    cin >> r;
    
    //cout << M_PI*r*r << M_PI*r*2 << endl;
    printf("%.5f %.5f\n",M_PI*r*r,M_PI*r*2);
}


Measured memory_bytes: 3196
K = int(input())
start = 1

DP = [[1 for i in range(10)] for j in range(12)]

# 下からの桁数
for j in range(1, 12):
    # その位の数
    for i in range(10):
        DP[j][i] = DP[j-1][i]
        if i != 0:
            DP[j][i] += DP[j-1][i-1]
        if i != 9:
            DP[j][i] += DP[j-1][i+1]
s = 0
# 後ろから考える
res = ""
for j in range(12):
    for i in range(1, 10):
        prev = s
        s += DP[j][i]
        if s >= K:
            res += str(i)
            # print(i, j)
            break
    if s >= K:
        break

top = i
keta = j
sa = K - prev
for k in range(keta-1, -1, -1):
    t = 0
    for j in range(max(0, top-1), min(9, top+1)+1):
        # print("kj", k, j)
        t_prev = t
        t += DP[k][j]
        if t >= sa:
            res += str(j)
            sa -= t_prev
            top = j
            break
print(res)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int x,y;
}a[105],b[105];
int used[105],cnt[105];
int n;
int find(int x){
    for(int i=1;i<=n;i++){
        if((a[x].x<b[i].x)&&(a[x].y<b[i].y)&&!used[i]){
            used[i]=1;
            if(cnt[i]==0||find(cnt[i])){
                cnt[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].x>>b[i].y;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        if(find(i)){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
s = {}
ans = 0
for n in range(N):
  chars = str(sorted(list(input())))

  if chars in s:
    s[chars] += 1
  else:
    s[chars] = 0
    
for value in s.values():
  ans += value * (value+1) // 2
  
print(ans)

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

int main() {
  int d;
  cin>>d;
  if(d==25){
    cout<<"Christmas"<<endl;
  }
  else if(d==24){
    cout<<"Christmas Eve"<<endl;
  }
  else if(d==23){
    cout<<"Christmas Eve Eve"<<endl;
  }
  else{
    cout<<"Christmas Eve Eve Eve"<<endl;
  }
}
    

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

typedef long long ll;

/* メモリ食い過ぎ注意 */
#define int ll
#define ALL(v) v.begin(), v.end()
#define _REP(i, n) for (int i = 0; i < n; i++)
#define REP(n) _REP(i, n)

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

int par[100001];
int rnk[100001];

void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        par[i] = i;
        rnk[i] = 0;
    }
}

int find(int x)
{
    // cout << par[x] << " ";
    if (par[x] == x)
    {
        // cout << "return " << x << endl;
        return x;
    }
    else
    {
        return (par[x] = find(par[x]));
    }
}

void unite(int x, int y)
{
    // cout << "arg=(" << x << "," << y << ")" << endl;
    x = find(x);
    // cout << "x=" << x << " ";
    y = find(y);
    // cout << "y=" << y << endl;
    if (x == y)
        return;
    if (rnk[x] < rnk[y])
    {
        par[x] = y;
    }
    else
    {
        par[y] = x;
        if (rnk[x] == rnk[y])
            rnk[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

signed main()
{
    int n, m;
    int x[100000], y[100000], z[100000];
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> x[i] >> y[i] >> z[i];

    init(n + 1);
    for (int i = 0; i < m; i++)
    {
        // cout << x[i] - 1 << "," << y[i] - 1 << endl;
        unite(x[i], y[i]);

    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (par[i] == i)
        {
            cnt++;
        }
        else
        {
            par[i] = par[par[i]];
        }
    }
    cout << cnt << endl;

    // cout << same(1, 5) << endl;
}

Measured memory_bytes: 4096
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <iomanip>
#include <set>
#include <sstream>
#include <queue>
using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    y[i] = x[i];
  }
  sort(y.begin(), y.end());

  for (int i = 0; i < n; i++) {
    if (x[i] < y[n/2]) {
      cout << y[n/2] << endl;
    } else {
      cout << y[n/2-1] << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 4352
//http://7ujm.net/stl/sort.html
//http://komaken.me/blog/2013/02/20/c-algorythm-sort%E9%96%A2%E6%95%B0%E3%81%AE%E4%BB%95%E6%A7%98%E3%82%92%E7%A2%BA%E8%AA%8D%E3%81%97%E3%81%A6%E3%81%BF%E3%82%8B/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;
using std::string;

int main()
{
    int n, t_point = 0, h_point = 0;
    string t_card, h_card;
    std::vector<string> sort_data; //ソート用データ

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> t_card >> h_card;

        sort_data.clear();           //初期化
        sort_data.push_back(t_card); //太郎カードをpush_back
        sort_data.push_back(h_card); //花子カードをpush_back

        std::sort(sort_data.begin(), sort_data.end(), std::greater<string>()); //辞書順大きい物にsort

        if (sort_data[0] == t_card && sort_data[0] == h_card) //互いに同じカードを出していた場合
        {
            t_point += 1;
            h_point += 1;
        }
        else if (sort_data[0] == t_card) //太郎カードが先頭に来ていた場合
        {
            t_point += 3;
        }
        else if (sort_data[0] == h_card) //花子カード~
        {
            h_point += 3;
        }
    }

    cout << t_point << " " << h_point << endl;
}


Measured memory_bytes: 3188
S = input()
T = input()
if T in S:
  print(0)
else:
  biggest_match = 0
  start = 0
  for i in range(len(S)-len(T)+1):
    j = 0
    match = 0
    for t in T:
      if t == S[i+j]:
        match += 1
      j += 1
    if match > biggest_match:
      biggest_match = match
      start = i
  print(len(T) - biggest_match)
      
  

Measured memory_bytes: 8912
import java.io.*;

public class Main {
	public static void main(String[] args) {
		InputStreamReader in = new InputStreamReader(System.in);
		BufferedReader reader = new BufferedReader(in);
		
		try {
			String str = reader.readLine();
			String[] str_sp = str.split(" ");
			
			int A = Integer.parseInt(str_sp[0]);
			int B = Integer.parseInt(str_sp[1]);
			
			int S = A * B - A - B + 1;
			System.out.println(S);
			
		} catch(IOException e) {
			System.out.println(e);
		}
	}
}


Measured memory_bytes: 22484
#include <iostream>
#include <stdio.h>

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

int main()
{
  long long int x,y,z=0,i,arr[100001],s=0,j,z1=0;

  cin>>x;

  for(i=0;i<x;i++)
    cin>>arr[i];
  for(j=0,i=1;i<x;j++,i=j+1)
  {
    if (arr[j]>=arr[i])
        s++;
    else
    {
        s=0;
    }
    if (s>=z1)
        z1=s;
  }
  cout<<z1;

     return 0;
}


Measured memory_bytes: 1024
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if A[i] <= B[i]:
        cnt += A[i]
        B[i] -= A[i]
    else:
        cnt += B[i]
        B[i] = 0
    if A[i+1] <= B[i]:
        cnt += A[i+1]
        A[i+1] = 0
    else:
        cnt += B[i]
        A[i+1] -= B[i]
print(cnt)

Measured memory_bytes: 24168
import math
n = int(input())

MOD = 10**9 + 7
prime = [True] * (n+1)

p = 2
while p*p <= n:
    for i in range(p*2, n+1, p):
        prime[i] = False
    p += 1

allPrimes = []
for p in range(2, n+1):
    if prime[p]:
        allPrimes.append(p)

res = 1

for i in range(len(allPrimes)):
    p = allPrimes[i]
    #print(p)
    n_exp = 0
    while (p <= n):
        n_exp += n//p
        p *= allPrimes[i]

    res = (res * (n_exp + 1)) % MOD

print(res)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
int dp[110000];
const int INF = 1001001001;
int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n)cin >> h[i];
    rep(i,n+1)dp[i] = INF;
    dp[1] = 0;
    rep(i,n){
        if(!i)continue;
        for(int j = 1;j<=k;j++){
            if(i+j <= n)dp[i+j] = min(dp[i+j],dp[i]+ abs(h[i+j-1]-h[i-1]));
        }
    }
    cout << dp[n] << endl;


    return 0;
}

Measured memory_bytes: 1024
N = int(input())
A_List = list(map(int,input().split()))
B_List = list(map(int,input().split()))
C_List = list(map(int,input().split()))
ans = 0

for i in range(len(A_List)):
    ans += B_List[A_List[i] - 1]
    if (i != 0) & (A_List[i] - A_List[i-1] == 1):
        ans += C_List[A_List[i-1]-1]
print(ans)
    

Measured memory_bytes: 9164
function main()
  
  N = parse(Int,readline())
  
  if N < 105
    println(0)
  elseif N < 135
    println(1)
  elseif N < 165
    println(2)
  elseif N < 189
    println(3)
  elseif N < 195
    println(4)
  else
    println(5)
  end
  
end

main()


Measured memory_bytes: 109404
import java.util.*;
import static java.lang.System.out;
import static java.lang.Math.*;

class Main{
  public static void main(String args[]){
    Scanner scan = new Scanner(System.in);
    while(true){
      int r = scan.nextInt();
      int c = scan.nextInt();
      if(r == 0 && c == 0) break;
      if((r * c) % 2 == 0) out.println("yes");
      else out.println("no");
    }
  }
}

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

int main() {
  int N;
  cin >> N;
  int a=0;
  for (int i = 1; i <= N; i++) {
    if(a<N&&N<=a+i){
      cout<<i<<endl;
      break;
    }
    a+=i;
  }
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long   // aaaaaaaaaaaaaaaaaa
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
template<typename T, typename U>ostream& operator << (ostream& os, pair<T, U>& pair_var)
{os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}
// head

double x,y,n,t,a,q,res;
int h[1010] = {};
double ans[1010] = {};
string s;
vector<pair<char,int> > vec;
signed main() {
	std::cin >>n>>t>>a;
	rep(i,0,n){
		std::cin >> h[i];
	}
	rep(i,0,SIZE(ans)){
		ans[i] = 1<<30;
	}
	rep(i,0,n){
		ans[i] = abs((t-0.006*h[i])-a);
	}
	double kota = *std::min_element(ans, ans+SIZE(ans));
	rep(i,0,n){
		if(kota == ans[i]){
			std::cout << i+1 << '\n';
			exit(0);
		}
	}
}

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

const int N = 100 * 1001;
long long n, res;
int a[N], lmax[N],rmax[N], pos[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
        lmax[i] = i - 1;
		rmax[i] = i + 1; 
    }
    for (int i = 1; i <= n; i++) {
        int lpos1 = lmax[pos[i]],
			lpos2 = lmax[lpos1],
         	rpos1 = rmax[pos[i]],
        	rpos2 = rmax[rpos1];
        if(lpos1 != 0)
			 res += 1LL * i * (lpos1 - lpos2) * (rpos1 - pos[i]);
        if(rpos1 != n + 1)
		 	res += 1LL * i * (pos[i] - lpos1) * (rpos2 - rpos1);
        lmax[rpos1] = lpos1;
        rmax[lpos1] = rpos1;
    }
    cout << res << "\n";
}


Measured memory_bytes: 5116
import itertools, math
N = int(input())
T = [list(map(int, input().split())) for i in range(N)]
d = 0
for l in itertools.permutations(range(N), N):
    for i in range(N - 1):
        d += math.sqrt((T[l[i]][0] - T[l[i + 1]][0]) ** 2 
        + (T[l[i]][1] - T[l[i + 1]][1]) ** 2)
print(d / math.factorial(N))

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

int main()
{
	char op;
	int a, b;

	while (1) {
		cin >> a >> op >> b;

		if (op == '?') {
			break;
		}

		switch (op) {
			case '+':
				cout << a + b << endl;
				break;
			case '-':
				cout << a - b << endl;
				break;
			case '*':
				cout << a * b << endl;
				break;
			case '/':
				cout << a / b << endl;
				break;
		}
	}

	return 0;
}

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

int main(){
    int n;
    cin>>n;
    string shopname;
    cin>>shopname;
    int ans=0;
    for (int i = 0; i < n; ++i) {
        string s;
        cin>>s;
        vector<vector<int>> pos(shopname.size());
        for (int j = 0; j < s.size(); ++j) {
            for (int k = 0; k < shopname.size(); ++k) {
                if(s[j]==shopname[k])pos[k].emplace_back(j);
            }
        }
        for (int j = 0; j < pos[0].size(); ++j) {
            for (int l = 0; ; ++l) {
                nextloop:;
                if(l>=pos[1].size())break;
                if(pos[1][l]<pos[0][j])continue;
                int nextpos=pos[1][l]-pos[0][j];
                int tpos=pos[1][l];
                for (int k = 2; k < shopname.size(); ++k) {
                    tpos+=nextpos;
                    if(tpos>=s.size()){++l;goto nextloop;}
                    auto tlb=lower_bound(pos[k].begin(),pos[k].end(),tpos);
                    if(tlb==pos[k].end()){++l;goto nextloop;}
                    if(*tlb!=tpos){++l;goto nextloop;}
                }
                ++ans;
                //cout<<s<<endl;
                goto endloop;
            }
        }
        endloop:;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3168
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>

using namespace std;

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

  int x[n], y[n];
  vector<int> od(n);
  for(int i = 0; i < n; i++){
    cin >> x[i] >> y[i];
    x[i] += 1000;
    y[i] += 1000;

    od[i] = i;
  }

  long double sum = 0;
  int num = 0;
  do{
    int dit = 0;
    for(int i = 0; i < n-1; i++){
      long double d;
      d = pow(x[od[i]] - x[od[i + 1]], 2.0) + pow(y[od[i]] - y[od[i+1]], 2.0);
      d = sqrt(d);

      sum += d;
    }
    num++;
  } while (next_permutation(od.begin(), od.end()));

  printf("%.10Lf", sum / num);

  return 0;
}

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

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

using namespace std;

int main(){
	string s,t; cin>>s>>t;
	int m=s.length(),n=t.length();

	int ans=n;
	rep(i,m-n+1){
		int cnt=0;
		rep(j,n) if(s[i+j]!=t[j]) cnt++;
		ans=min(ans,cnt);
	}
	cout<<ans<<'\n';

	return 0;
}


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

int main(){
  long A,B,C,K;
  long ans=0;
  cin >> A >> B >> C >> K;
  if(A>=K) ans = K;
  else if(A+B>=K) ans = A;
  else ans = A - (K-A-B);
  cout << ans << endl;
}


Measured memory_bytes: 3624
#import<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL i,j,m,n,r,w[100005];
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	if(n>9)cout<<r;
	else cout<<r+100*(10-n);
	
}

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

using namespace std;
#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__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

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;
}

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

  ll n, m;
  cin >> n >> m;

  string s, t;
  cin >> s >> t;

  if(n < m){
    swap(n, m);
    swap(s, t);
  }

  if(n % m != 0){

    ll g = gcd(n, m);

    ll ret = n / g * m;

    n /= g;
    m /= g;
    bool ok = true;
    rep(i, g){
      if(s[i*n] != t[i*m]) ok = false;
    }

    if(ok) cout << ret << endl;
    else cout << -1 << endl;


  }else{

    ll k = n / m;
    bool ok = true;
    for(int i = 0; i < m; i++){
      if(s[i*k] != t[i]){
        ok = false;
        break;
      }
    }

    if(ok){
      cout << n << endl;
      return 0;
    }else{
      cout << -1 << endl;
      return 0;
    }



  }

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
const int MOD = 1e9+7;
const int INF = 1<<30;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    double a, b, n;
    cin >> a >> b >> n;

    double x;
    if ((ll)n % (ll)b == 0) {
        x = n - 1.0;
    }
    else {
        if (n < b) x = n;
        else {
            if (n == (double)((ll)n / (ll)b + 1) * b - 1.0) {
                x = (double)((ll)n / (ll)b + 1) * b - 1.0;
            }
            else {
                x = (double)((ll)n / (ll)b) * b - 1.0;
            }
        }
    }
    cout << (ll)(floor(a / b * x) - a * floor(x / b)) << endl;

    return 0;
}

Measured memory_bytes: 3740
// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

//PointBlank's code (⌐■_■)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
 
#define repp(I, A, B) for(int I = A; I <= B; I++)
#define rep(I, A, B) for(int I = A; I < B; I++)
#define rrep(I, B, A) for(int I = B; I >= A; I--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define LB lower_bound
#define UB upper_bound
#define MP make_pair
#define mem(A, B) memset(A, B, sizeof(A));
#define mem0(A) memset(A, 0, sizeof(A));
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define bitsf(n) __builtin_popcount(n)
#define in_edges(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B), v[B].pb(A);}
#define in_edges2(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B);}
#define endl "\n"
ll power(ll x, ll y); 

const ll MOD = 1000000007;
 
int main() //PointBlank's code ¯\_(ツ)_/¯
{
    quickio
    ll h, w, A, B, C;
    cin >> h >> w;

    ll mn = 1e18;
    rep(i, 1, h){
        A = i*w;
        B = (h - i) * (w/2);
        C = (h - i) * (w - w/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
        B = w * ((h - i)/2);
        C = w * (h - i - (h - i)/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
    }

    swap(h, w);
    rep(i, 1, h){
        A = i*w;
        B = (h - i) * (w/2);
        C = (h - i) * (w - w/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
        B = w * ((h - i)/2);
        C = w * (h - i - (h - i)/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
    }

    cout << mn;
}

ll power(ll x, ll y)
{ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}

Measured memory_bytes: 256