akhauriyash/Code-Regression huggingface dataset:
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'a1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    n, r = read_int_list()
    if n < 10:
        r += 100 * (10 - n)
    return r


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()


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


int main(){
  int n,m;
  cin >> n >> m;
  vector<int> x(m),y(m);
  for(int i=0;i<m;++i){
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
  }
  vector<int> red(n);
  vector<int> num(n);
  for(int i=0;i<n;++i){
    if(i==0){
      red[i]=1;
      num[i]=1;
    }else{
      red[i]=0;
      num[i]=1;
    }
  }
  for(int i=0;i<m;++i){
    num[x[i]]--;
    num[y[i]]++;
    if(red[x[i]]==1){
      red[y[i]]=1;
      if(num[x[i]]==0){
        red[x[i]]=0;
      }
    }
  }
  int ans=0;
  for(int i=0;i<n;++i){
    if(red[i]==1){
      ans++;
    }
    //cout << red[i] << endl;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)
	log.SetFlags(log.Lshortfile)
	n := nextInt()
	p := make([]int, n)
	for i := 0; i < n; i++ {
		p[i] = nextInt()
	}
	ans := 0
	for i := 0; i < n; i++ {
		if p[i] == i+1 {
			if i == n-1 {
				p[i], p[i-1] = p[i-1], p[i]
			} else {
				p[i], p[i+1] = p[i+1], p[i]
			}
			ans++
		}
	}
	fmt.Println(ans)
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}
var MAX = math.MaxInt32

func pow(a, b int) int {
	return int(math.Pow(float64(a), float64(b)))
}

func lcm(a, b int) int {
	return a * b / gcd(a, b)
}
func gcd(a, b int) int {
	if a < b {
		a, b = b, a
	}
	for b != 0 {
		a, b = b, a%b
	}
	return a
}
func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}
func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}
func sum(a []int) (r int) {
	for i := range a {
		r += a[i]
	}
	return r
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

type Pair struct {
	a, b int
}

type Pairs []Pair

func (p Pairs) Len() int {
	return len(p)
}
func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].a == p[j].a {
		return p[i].b < p[j].b
	}
	return p[i].a < p[j].a
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


bool flag[2000005] = {};
void Main() {
	int N;  cin >> N;
	vint A(N); cin >> A;
	sort(begin(A), end(A));
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		auto &a = A[i];
		if (!flag[a]) {
			if (i == N-1 || a < A[i+1]) {
				cnt++;
			}
			for (int i = a; i <= 2000005; i += a) {
				flag[i] = true;
			}
		}
	}
	cout << cnt << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 6100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin>>n;
  ll a[n],b[n];
  for(ll i=0;i<n;i++) cin>>a[i]>>b[i];
  reverse(a,a+n);
  reverse(b,b+n);
  ll ans=0;
  for(ll i=0;i<n;i++){
    if((a[i]+ans)%b[i]){
      ans+=b[i]-(a[i]+ans)%b[i];
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

const ll M=int(1e9)+7;
int n, k;

ll fact[2001*2001];

ll Pow(ll b, ll e){
	ll ret=1;
	while(e){
		if(e&1) ret=ret*b%M;
		e/=2; b=b*b%M;
	}
	return ret;
}
ll modinv(ll x){
	return Pow(x, M-2);
}

ll combi(int n, int k){
	return fact[n]*modinv(fact[k])%M*modinv(fact[n-k])%M;
}

ll dp[2010][2010];

int main()
{
	fact[0]=1;
	for(int i=1; i<=2000*2000; ++i) fact[i]=fact[i-1]*i%M;
	read(n, k);
	if(k == 1){
		puts("1");
		return 0;
	}
	
	for(int i=n+1; 1<=i; --i){
		for(int j=min(n,i); 1<=j; --j){
			if(i==n+1 && j==n){
				dp[i][j]=1;
				continue;
			}
			ll d=dp[i+1][j];
			if(j+1<=i){
				ll c1=k-2;
				ll c2=(n-j)*k-(i-j-1);
				d += dp[i][j+1]*combi(c1+c2, c1)%M;
				d %= M;
			}
			dp[i][j]=d;
		}
	}
	printf("%lld\n", dp[1][1]*fact[n]%M);
	return 0;
}


Measured memory_bytes: 61568
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300005,mod=1000000007;
int n,h,a[N],x[N],y[N],s[N],d[N],ans;
vector<int>v;
int qp(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void pre(int k,int l,int r)
{
	if(l==r)
	{
		x[k]=y[k]=l;
		return;
	}
	s[k<<1]=s[k]*(k<<1)%mod;
	s[k<<1|1]=s[k]*(k<<1|1)%mod;
	int mid=l+r>>1;
	pre(k<<1,l,mid);
	pre(k<<1|1,mid+1,r);
	x[k]=x[k<<1];
	y[k]=y[k<<1|1];
}
void clear(int k)
{
	d[k]=0;
	if(k==1)
		return;
	clear(k/2);
}
void rec1(int k,int t)
{
	t=t*k%mod;
	d[k]=(d[k]+t)%mod;
	if(k==1)
		return;
	rec1(k/2,t);
}
void rec2(int k,int t,int l)
{
	t=t*k%mod;
	ans=(ans+t*(d[k^1])%mod*(k/2)%mod*qp(l,mod-2)%mod)%mod;
	if(k==1)
		return;
	rec2(k/2,t,l);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin>>h;
	n=(1<<h)-1;
	for(int i=1;i<=n/2+1;i++)
		cin>>a[i];
	s[1]=1;
	pre(1,1,n/2+1);
	for(int i=1;i<=n/2;i++)
	{	
		v.clear();
		for(int j=x[i<<1];j<=y[i<<1];j++)
		{
			rec1(a[j]+n/2,s[j+n/2]);
			v.push_back(a[j]+n/2);
		}
		for(int j=x[i<<1|1];j<=y[i<<1|1];j++)
			rec2(a[j]+n/2,s[j+n/2],i==1?1:s[i]*s[i/2]%mod);
		for(auto j:v)
			clear(j);
	}	
	cout<<ans<<endl;
	return 0;
}


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

const int MAX_H = 10;

string a[MAX_H];

int main() {
    int h, w;
    cin >> h >> w;

    for (int r = 0; r < h; r++) {
        cin >> a[r];
    }

    int cnt = 0;
    for (int r = 0; r < h; r++) {
        for (int c = 0; c < w; c++) {
            if (a[r][c] == '#') cnt++;
        }
    }

    if (cnt == w + h - 1) cout << "Possible" << endl;
    else cout << "Impossible" << endl;

    return 0;
}


Measured memory_bytes: 256
import math
import time

N, M = map(int, input().split())

st = time.time()

a = math.factorial(N) % 1000000007
b = math.factorial(M) % 1000000007
"""
if N == M:
    for i in range(1,N+1):
        a *= i % 1000000007
    b = a

elif N - M == 1:
    for i in range(1,M+1):
        b *= i % 1000000007
    a = b * N 
elif M - N == 1:
    for i in range(1,N+1):
        a *= i % 1000000007
    b = a * M 
"""

if abs(N-M) == 1:
    ans = a * b %1000000007
elif N == M:
    ans = 2*a*b % 1000000007
else:
    ans = 0

print(ans)

ed = time.time() -st
#print(ed)

Measured memory_bytes: 4148
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    char a, b;
    cin >> a >> b;
    string s="", t="";
    rep(i, a-'0') s += b;
    rep(i, b-'0') t += a;
    if(s < t) cout << s << endl;
    else cout << t << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int city  = sc.nextInt();
		long[] monster = new long[city+1];
		long[] brave = new long[city];
		long anser = 0;
		for(int i=0;i<city+1;i++) {
			monster[i] = sc.nextLong();
		}
		for(int i =0;i<city;i++) {
			brave[i] = sc.nextLong();
		}

		//勇者の攻撃がなくなるまで
		for(int i = 0; i<brave.length;i++) {
			anser += Math.min(monster[i],brave[i]);
			anser += Math.min(monster[i+1],Math.max(brave[i]-monster[i], 0));
			monster[i+1] -= Math.min(monster[i+1],Math.max(brave[i]-monster[i], 0));
		}
		System.out.println(anser);
	}
}

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

int main() {
  int s, s1, s2, s3;
  cin >> s;
  s1 = s / 100;
  s2 = (s - 100 * s1) / 10;
  s3 = s - 100 * s1 - 10 * s2;
  cout << (s1 + s2 + s3) << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    // 整数の入力
    int N,L;
    cin >> N >> L;
    vector<string>data(N);
    string tmp;
    
    for(int i=0;i<N;i++){
        cin >> data[i];
    }   
    sort(data.begin(),data.end());

    // 出力
    for(int i=0;i<N;i++){
        cout << data[i];
    }   
    cout << endl;

    return 0;
}


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

/***********************************************/
/* Dear online judge:
 * I've read the problem, and tried to solve it.
 * Even if you don't accept my solution, you should respect my effort.
 * I hope my code compiles and gets accepted.
 *  ___  __     _______    _______
 * |\  \|\  \  |\  ___ \  |\  ___ \
 * \ \  \/  /|_\ \   __/| \ \   __/|
 *  \ \   ___  \\ \  \_|/__\ \  \_|/__
 *   \ \  \\ \  \\ \  \_|\ \\ \  \_|\ \
 *    \ \__\\ \__\\ \_______\\ \_______\
 *     \|__| \|__| \|_______| \|_______|
 */
const long long mod = 1000000007;

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

	string s;
	int K;
	cin>>s>>K;
	vector<string> mn;
	for(int i = 0;i < (int)s.size();i++) {
		for(int j = 1;j <= K && i + j <= (int)s.size();j++) {
			mn.push_back(s.substr(i,j));
		}
	}
	sort(mn.begin(),mn.end());
	mn.erase(unique(mn.begin(),mn.end()),mn.end());
	cout<<mn[K-1]<<'\n';
	return 0;
}


Measured memory_bytes: 1660
n=int(input())
'''
import sys
sys.setrecursionlimit(1000000)
def kaijo(n):
    if n==0:
        return(1)
    else:
        n=n%(10**9+7)
        return(n*kaijo(n-1))
print(kaijo(n)%(10**9+7))
'''
ans=1
for i in range(1,n+1):
    ans=i*(ans%(10**9+7))
print(ans%(10**9+7))

Measured memory_bytes: 2940
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import Counter
from heapq import heappush, heappop

p, g, ig = 998244353, 3, 332748118
W = [pow(g, (p - 1) >> i, p) for i in range(24)]
iW = [pow(ig, (p - 1) >> i, p) for i in range(24)]
 
def convolve(a, b):
    def fft(f):
        for l in range(k, 0, -1):
            d = 1 << l - 1
            U = [1]
            for i in range(d):
                U.append(U[-1] * W[l] % p)
 
            for i in range(1 << k - l):
                for j in range(d):
                    s = i * 2 * d + j
                    t = s + d
                    f[s], f[t] = (f[s] + f[t]) % p, U[j] * (f[s] - f[t]) % p
 
    def ifft(f):
        for l in range(1, k + 1):
            d = 1 << l - 1
            U = [1]
            for i in range(d):
                U.append(U[-1] * iW[l] % p)
 
            for i in range(1 << k - l):
                for j in range(d):
                    s = i * 2 * d + j
                    t = s + d
                    f[s], f[t] = (f[s] + f[t] * U[j]) % p, (f[s] - f[t] * U[j]) % p
 
    n0 = len(a) + len(b) - 1
    k = (n0).bit_length()
    n = 1 << k
    a = a + [0] * (n - len(a))
    b = b + [0] * (n - len(b))
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    for i in range(n0):
        a[i] = a[i] * invn % p
    del a[n0:]
    return a

N = int(input())
P = 998244353
nn = 2 * N + 10
fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P

dfa = [1] * (nn+1)
for i in range(2, nn+1):
    dfa[i] = dfa[i-2] * i % P
dfa += [1]

X = list(Counter([int(input()) for _ in range(2 * N)]).values())
M = len(X)
Y = [[] for _ in range(M)]
for x in X:
    L = [1]
    s = 1
    for i in range(x // 2):
        s = s * ((x - i * 2) * (x - i * 2 - 1) // 2) % P
        L.append(s * fainv[i+1] % P)
    Y.append(L)

for i in range(1, M)[::-1]:
    Y[i] = convolve(Y[i*2], Y[i*2+1])

ans = 0
for i, x in enumerate(Y[1]):
    ans = (ans + x * (-1 if i & 1 else 1) * dfa[N * 2 - i * 2 - 1]) % P
print(ans)

Measured memory_bytes: 102000
#include <bits/stdc++.h>
#define ll long long

using namespace std;

string s;
int k, num[210];

int main()
{
	cin >> s >> k;
	int cnt = 0, cur = 1;
	for (int i = 1; i < s.size(); i++)
		if (s[i] == s[i - 1])
			cur++;
		else
		{
			num[++cnt] = cur;
			cur = 1;
		}
	bool flag = false;
	if (s[s.size() - 1] == s[0] && cnt >= 1)
	{
		flag = true;
		cur += num[1];
	}
	num[++cnt] = cur;
	if (!flag && cnt == 1)
	{
		ll t = 1ll * s.size() * k;
		cout << t / 2 << endl;
	}
	else if (!flag)
	{
		ll ans = 0;
		for (int i = 1; i <= cnt; i++)
			ans += num[i] / 2;
		cout << ans * k << endl;
	}
	else
	{
		ll ans = num[1] / 2, tmp = 0;
		for (int i = 2; i <= cnt; i++)
			tmp += num[i] / 2;
		ans += tmp * k - num[cnt] / 2 + (num[cnt] - num[1]) / 2;
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    int sum,cnt,p;
    sum=a+b;
    cnt=a-b;
    p=a*b;
    int mx=max(sum,cnt);
    mx=max(mx,p);
    cout<<mx<<endl;
    return 0;
}



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

int main() {
    int N;
    int d[110];
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> d[i];

    int num[110] = {0};
    for (int i = 0; i < N; ++i) {
        num[d[i]]++;
    }

    int res = 0;
    for (int i = 1; i <= 100; ++i) {
        if (num[i]) {
            ++res;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
	
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	int x=sc.nextInt(),n=sc.nextInt(),min=301;
    int[] p=new int[n],a=new int[300-n];
    
    
    for(int i=0;i<n;i++){
      p[i]=sc.nextInt();
      
    }
    int l=0;
    for(int i=-150;i<150;i++){
      int f=0;
      for(int j=0;j<n;j++){
        if(i==p[j]){
          f++;
          break;
        }
      }
      if(f==0){
        a[l]=i;
        l++;
      }
    }
    
    if(n==0){
      System.out.println(x);
    }else{
      for(int i=0;i<a.length;i++){
        if(min<=(int)Math.abs(x-a[i])){
          System.out.println(a[i-1]);
          break;
        }else{
          min=(int)Math.abs(x-a[i]);
        }
      }
    }
  }
}


Measured memory_bytes: 36044
#include <iostream>

using namespace std;
int main()
{
    int n;
    cin >> n;
    int R0, R1;
    cin >> R0 >> R1;
    int maxv = R1 - R0;
    int minv = min(R0, R1);
    for (int i = 2; i < n; i++) {
        int R;
        cin >> R;
        maxv = max(maxv, R - minv);
        minv = min(minv, R);
    }
    cout << maxv << endl;
    return 0;
}


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

using namespace std;

#define int				long long
#define pb 				push_back
#define endl 			'\n'
#define F				first
#define S				second
#define mod				(ll)998244353
#define mp              make_pair
#define lb				lower_bound
#define ub				upper_bound
#define ios 			ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inf				1e18
#define mem(a,x)		for(int i=0;i<(int)(sizeof(a)/sizeof(a[0]));i++) a[i] = x;
#define trace(a)		cout<<(#a)<<" --> "<<a<<endl
#define trace2(a,b)		{trace(a);trace(b);}
#define trace3(a,b,c)	{trace(a);trace(b);trace(c);}
#define trace4(a,b,c,d) {trace(a);trace(b);trace(c);trace(d);}
#define M_PI           	3.14159265358979323846

signed main(){
	ios;
	string s;
	cin>>s;
	int n = s.length();
	int ans[n];
	mem(ans,0);
	int cnt1 = 0, cnt2 = 0, cnt;
	for(int i=0;i<n;i++){
		if(s[i] == 'R' && s[i+1] == 'L'){
			int j = i;
			int k = i+1;
			while(j>=0 && s[j] == 'R'){
				cnt1++; j--;
			}
			while(k<n && s[k] == 'L'){
				cnt2++; k++;
			}
			cnt = cnt1+cnt2;
			if(cnt1 == cnt2){
				ans[i] = cnt/2;
				ans[i+1] = cnt/2;
			}
			else if(cnt1>cnt2){
				if(cnt1%2 == 0){
					ans[i+1] = (cnt+1)/2;
					ans[i] = cnt-ans[i+1];
				}
				else{
					ans[i] = (cnt+1)/2;
					ans[i+1] = cnt-ans[i];
				}
			}
			else{
				if(cnt2%2 == 0){
					ans[i] = (cnt+1)/2;
					ans[i+1] = cnt-ans[i];
				}
				else{
					ans[i+1] = (cnt+1)/2;
					ans[i] = cnt-ans[i+1];
				}
			}
			cnt1 = 0; cnt2 = 0;
		}
	}
	for(int i=0;i<n;i++)
		cout<<ans[i]<<" ";
	return 0;
}






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

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

    vector<int> a(n), b(n), c(n);
    for(int i = 0; i < n; ++i) 
    {
        cin >> a[i];
        --a[i];
    }
    for(int i = 0; i < n; ++i) cin >> b[i];
    for(int i = 0; i < n - 1; ++i) cin >> c[i];

    int res = 0;
    for(int i = 0; i < n; ++i)
    {
        res += b[a[i]];
        if(i > 0 && a[i] == a[i - 1] + 1)
            res += c[a[i - 1]];
    }
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
using p=pair<int,int>;
#define int long long
#define rep(i,N) for(int i=0;i<N;i++)
 
signed main(){
  int N;
  cin>>N;
  int M=N,P=1;
  int S=sqrt(N);
  for(int i=2;i<S+1;i++){
    if(N%i==0)P=i;
  }
  M=N/P;
  cout<<P+M-2<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#include <random>
#include <time.h>
#include <cstdio>
#include <list>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define vec vector<int>
#define vecll vector<ll>
#define vecstr vector<string>
#define vecch vector<char>
#define vecpii vector<pii>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
string strin(){string s;cin>>s;return s;}
char chin(){char c;cin>>c;return c;}
ll lin() {ll x;scanf("%lld",&x);return x;}

int main(){
    int n=in();
    vector<ll> a(n),sum(n);
    sum[0]=a[0]=in();
    rep(i,n-1){
        a[i+1]=in();
        sum[i+1]=sum[i]+a[i+1];
    }
    ll ans=LONG_MAX;
    rep2(k,2,n-2){
        ll l1=0,r1=k-1,l2=k,r2=n-1;
        while(l1+1<r1){
            ll m=(l1+r1)/2;
            if(sum[m]<sum[k-1]-sum[m]){
                l1=m;
            }else if(sum[m]>sum[k-1]-sum[m]){
                r1=m;
            }else{
                l1=m;
                r1=m;
            }
        }
        while(l2+1<r2){
            ll m=(l2+r2)/2;
            if(sum[m]-sum[k-1]<sum[n-1]-sum[m]){
                l2=m;
            }else if(sum[m]-sum[k-1]>sum[n-1]-sum[m]){
                r2=m;
            }else{
                l2=m;
                r2=m;
            }
        }
        if(l1<k-2&abs(sum[l1]-sum[k-1]+sum[l1])>abs(sum[l1+1]-sum[k-1]+sum[l1+1]))l1++;
        if(l2<n-2&abs(sum[l2]-sum[k-1]-sum[n-1]+sum[l2])>abs(sum[l2+1]-sum[k-1]-sum[n-1]+sum[l2+1]))l2++;
        ll p=sum[l1],q=sum[k-1]-sum[l1],r=sum[l2]-sum[k-1],s=sum[n-1]-sum[l2];
        ans=min(ans,max(p,max(q,max(r,s)))-min(p,min(q,min(r,s))));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3328
#include<cstdio>
#include<vector>
#include<algorithm>
#include<sstream>
#include<string>
#include<iostream>
using namespace std;
string conv(int n){
    stringstream ss;
    while(n){
        ss<<n%8;
        n/=8;
    }
    string ret=ss.str();
    reverse(ret.begin(),ret.end());
    return ret;
}
const int l[]={0,1,2,3,5,7,8,9};
int main(){
    int n;
    while(cin>>n,n){
        string str=conv(n);
        for(int i=0;i<str.length();i++){
            cout<<l[str[i]-'0'];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1216
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 1
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	q := make([]word, 0)
	q = append(q, word{
		i: 0,
		data: [11]int{
			-1,
			-1,
			-1,
			-1,
			-1,
			-1,
			-1,
			-1,
			-1,
			-1,
			-1,
		},
	})
	for len(q) > 0 {
		p := q[0]
		if p.i == n {
			break
		}
		q = q[1:]
		m := -1
		for j := 0; j < n; j++ {
			if m < p.data[j] {
				m = p.data[j]
			}
		}
		for i := 0; i <= m+1; i++ {
			w := word{
				i: p.i + 1,
			}
			for j := 0; j < n; j++ {
				w.data[j] = p.data[j]
			}
			w.data[p.i+1] = i
			q = append(q, w)
		}
	}
	for i := 0; i < len(q); i++ {
		a := make([]string, n)
		for j := 0; j < n; j++ {
			a[j] = fmt.Sprintf("%c", 'a'+q[i].data[j+1])
		}
		aa := strings.Join(a, "")
		fmt.Fprintln(writer, aa)
	}
}

type word struct {
	i    int
	data [11]int
}


Measured memory_bytes: 52352
Class Main
    Public Shared Sub Main()
    Dim X As long = Console.ReadLine()
    dim A,B as integer
    for A = -120 to 120
    for B = -120 to 120
    if Math.Pow(A,5) - Math.Pow(B,5) = X then
      Console.WriteLine(A & " " & B)
      exit sub
    end if
    next B
  next A
   End Sub
End Class


Measured memory_bytes: 28688
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define MOD (1e9+7)

int main(void){
	int n,i;
	ll a[12345],b[12345],debt=0;
	bool flag = true;
	cin >> n;
	for(i=0; i<n; i++){
		cin >> a[i];
	}
	for(i=0; i<n; i++){
		cin >> b[i];
	}
	for(i=0; i<n; i++){
		if(a[i]>b[i]){
			debt += (a[i]-b[i])*2;
			b[i] = a[i];
		}
	}
	for(i=0; i<n; i++){
		debt -= ((b[i]-a[i])/2)*2;
	}
	cout << ((debt<=0)?"Yes":"No") << endl;
	return 0;
}


Measured memory_bytes: 384
N, K = map(int, input().split())
As = list(map(int, input().split()))
P = 10**9 + 7

As.sort()
dic = {-1:0, 1:0}
for a in As:
  if a < 0:
    dic[-1] += 1
  else:
    dic[1] += 1

rlt = 1
j = 0
if N == K:
  for a in As:
    rlt *= a
    rlt %= P
  while rlt < 0:
    rlt += P
elif As[N-1] < 0 and K%2 == 1:
  for i in range(1,K+1):
    rlt *= As[-i]
    rlt %= P
  while rlt < 0:
    rlt += P
else:
  s = 0
  i = 0
  j = 1
  while s < K:
    if i+1 >= dic[-1] or s+1 == K:
      rlt *= As[-j]
      rlt %= P
      j += 1
      s += 1
    elif j+1 > dic[1]:
      rlt *= As[i]*As[i+1]
      rlt %= P
      i += 2
      s += 2
    else:
      if As[i]*As[i+1] > As[-j]*As[-(j+1)]:
        rlt *= As[i]*As[i+1]
        rlt %= P
        i += 2
        s += 2
      else:
        rlt *= As[-j]
        rlt %= P
        j += 1
        s += 1
        
print(rlt)

Measured memory_bytes: 93764
def function():
    _N,K = map(int, input().split())
    teleportes = list(map(int, input().split()))

    # ループを見つける
    i,count = 0,0
    visited = [-1] * len(teleportes) # 訪れた街にチェック
    while True :
        if visited[i] == -1: # 最初に訪れた
            visited[i] = count # 何番目に訪れたかを記録
            i = teleportes[i] - 1
            count += 1
        else:
            loops = count - visited[i] # 以前訪れてから何回旅したか
            break
    
    if K <= visited[i]:
        i = 0
    else:
        K -= visited[i]
        K %= loops
    for _k in range(K):
        i = teleportes[i] - 1
    print(i+1)

if __name__ == '__main__':
    function()


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

int main(){
  int n;
  cin >> n;
  vector<int> b(n);
  rep(i,n-1) cin >> b[i];

  int ans = b[0];
  rep(i,n){
    if(i == n-1){
  		ans += b[n-2];
  		continue;
  	}else if(b[i] <= b[i+1]){
  		ans += b[i];
  		continue;
  	}else{
  		ans += b[i+1];
  	}
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>

using namespace std;
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

const int maxn = 4e5;
const int MOD = 1e9 + 7;

vector<long long> fact(maxn + 1, 1);
vector<long long> inv(maxn + 1, 1);

long long mod_pow(long long a, long long b, long long p = MOD) { // = (a^b) % p //((a^-1) % p) = (a^(p-2)) % p;
	long long res = 1;
	a %= p;

	while (b > 0) {
		if ((b & 1) == 1) res = ((res % p) * (a % p)) % p;
		a = ((a % p) * (a % p)) % p;
		b >>= 1;
	}
	return res;
}

void preC() {
	for (long long i = 1; i <= maxn; i++) {
		fact[i] = (i * fact[i - 1]) % MOD;
		inv[i] = (mod_pow(i, MOD - 2) * inv[i - 1]) % MOD;
	}
}

long long C(long long n, long long r) { // nCr % MOD
	if (n < r) return 0;
	return (fact[n] * ((inv[r] * inv[n - r]) % MOD)) % MOD;
}


int main() {

	preC();
	long long  n, k; cin >> n >> k;
	long long ans = 0;
	for (int i = 0; i <= min(k, n - 1); i++) {
		ans = (ans % MOD + (C(n, i) * C(n - 1, i)) % MOD) % MOD;
	}
	cout << ans;


	return 0;
}

Measured memory_bytes: 8952
#include <cstdio>
using namespace std;
char s[] = "RGYB";
int n, m, k;
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; putchar(10), i++)
		for (int j = 0; j < m; j++)
			putchar(s[(i + j) / k % 2 * 2 + (i + m - j) / k % 2]);
}

Measured memory_bytes: 384
#include <stdio.h>
int main(){

  int result,book,i;

  while(1){

    scanf("%d",&result);
    
    if(result != 0){
      
      for(i = 0; i < 9; i++){
	
	scanf("%d",&book);
	
	result -= book;
	
      }
      
      printf("%d\n",result);
      
    } else {
      
      break;
      
    }

  }
  
  return 0;

}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <tuple>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using tlli = tuple<ll, ll, int>;
static ll INF = 1000000000000000000ll;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<pll> p(n);
	for(int i = 0; i < n; ++i){
		ll a, b;
		cin >> a >> b;
		p[i] = pll(min(a, b), max(a, b));
	}
	set<tlli> rset, bset;
	for(int i = 0; i < n; ++i){
		rset.emplace(p[i].first, p[i].second, i);
		bset.emplace(p[i].second, p[i].first, i);
	}
	ll answer =
		(get<0>(*rset.rbegin()) - get<0>(*rset.begin())) *
		(get<0>(*bset.rbegin()) - get<0>(*bset.begin()));
	while(get<0>(*rset.begin()) < get<1>(*rset.begin())){
		const auto r = *rset.begin();
		const auto b = tlli(get<1>(r), get<0>(r), get<2>(r));
		rset.erase(r);
		rset.insert(b);
		bset.erase(b);
		bset.insert(r);
		const ll t =
			(get<0>(*rset.rbegin()) - get<0>(*rset.begin())) *
			(get<0>(*bset.rbegin()) - get<0>(*bset.begin()));
		answer = min(answer, t);
	}
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 30464
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pa;

int main(){
    ll N,P,Q;
    cin >> N >> P >> Q;
    vector<ll> C(N);
    vector<Pa> v(N);
    for(ll i=0;i<N;i++){
        cin >> C[i];
        v[i] = {C[i]+P*i,i};
    }
    sort(v.begin(),v.end(),greater<Pa>());
    ll ans = P*N*Q+P*N*(N-1)/2,now = ans;
    for(ll i=0;i<N;i++){
        ll id = v[i].second;
        now += C[id]+P*id-P*Q-2*(N-1-i)*P;
        ans = max(ans,now);
    }
    cout << ans << endl;
}


Measured memory_bytes: 14444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

int N, M;

int main() {
  cin >> N >> M;

  using p = pair<int, int>;
  vector<p> v(N + M);
  rep(i, N) {
    cin >> v[i].first;
    v[i].second = 1;
  }
  rep(i, M) { cin >> v[i + N].second >> v[i + N].first; }

  sort(v.rbegin(), v.rend());

  int n = N;
  ll ans = 0;
  rep(i, N + M) {
    ll k = min(v[i].second, n);
    ans += v[i].first * k;
    n -= k;
    if (n == 0) break;
  }

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


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

struct Edge{
  int to;
  long long cost;
};

struct NODE{
  int pos;
  long long cost;
};
bool operator < (const NODE &a,const NODE &b){
  return a.cost > b.cost;
}
vector<Edge> g[100000],rg[100000];

int N,E;
const ll INF = 1e15;
vector<ll> dijkstra(vector<Edge> g[100000], int s){
  priority_queue<NODE> Q;
  Q.push({s,0});
  vector<ll> res(N,INF);
  while(Q.size()){
    NODE q= Q.top();Q.pop();
    if(res[q.pos] == INF){
      res[q.pos] = q.cost;
    }
    else{
      continue;
    }
    for(auto n : g[q.pos]){
      Q.push({n.to,q.cost+n.cost});
    }
  }
  return res;
}
vector<int> memo(100,inf),tmp;
bool dfs(int k,int n){
  if(memo[k] == 0) return true;
  if(memo[k] != inf) return false;
  memo[k] = n;
  bool f = false;
  for(auto t: g[k]){
    f |= dfs(t.to,n+1);
  }
  return f;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> E;
  int s, t;
  rep(i,E){
    cin >> s >> t;
    g[s].push_back({t,1});
  }
  tmp = memo;
  bool ans = false;
  rep(i,N){
    memo = tmp;
    ans |= dfs(i,0);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 7868
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <iomanip>
#include <math.h>
#include <unordered_map>
#include <unordered_set>
//#define local
#ifdef local
    #include "dbg-macro/dbg.h"
#endif
//#define hacks
#ifdef hacks
    #include <boost/multiprecision/cpp_int.hpp>
#endif
#define p std::pair
#define ll long long
#define ld long double
#define ull unsigned long long
#define pi std::pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (unsigned long long i = 0; i < (unsigned long long)(n); ++i)
#define vec std::vector
#define oreq |=
#define npm next_permutation
using namespace std;
std::vector<unsigned ll> genprimevec(const unsigned ll N);
ll extgcd(ll a, ll b, ll& x, ll& y);
ll nCr(ll n, ll r);
void stat();
template <typename T> T fact(T num);
constexpr ll mod = 1000000000 + 7;

int main()
{
    stat();
    int n;
    cin >> n;
    ull ans = 0;
    vec<ll> v(3 * n);
    rep(i, 3 * n) { cin >> v[i]; }
    sort(all(v),[](ll l,ll r){return l>r;});
    for(int index=1;index!=(2*n)+1;index+=2){
	    ans+=v[index];
    } 
cout<<ans<<endl;
    return 0;
}
ll extgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


std::vector<unsigned ll> genprimevec(const unsigned ll N)
{
    std::vector<bool> is_prime(N + 1);
    for (unsigned ll i = 0; i <= N; i++) {
        is_prime[i] = true;
    }
    std::vector<unsigned ll> P;
    for (unsigned ll i = 2; i <= N; i++) {
        if (is_prime[i]) {
            for (unsigned ll j = 2 * i; j <= N; j += i) {
                is_prime[j] = false;
            }
            P.emplace_back(i);
        }
    }
    return P;
}

void stat(){
#ifdef local
    rep(i, 2){std::cout << "local enable" << std::endl;
}
#endif
#ifdef hacks
rep(i, 2) { std::cout << "boost enable" << std::endl; }
#endif
}

ll nCr(ll n, ll r)
{
    ll num = 1;
    for (ll i = 1; i <= r; i++) {
        num = num * (n - i + 1) / i;
    }
    return num;
}

template <typename T> T fact(T num)
{
    if (num == 1) { return 1; }
    return num * fact(num - 1);
}


Measured memory_bytes: 5556
MOD = 10 ** 9 + 7
L = input()

dp = [(0, 1)]
if not len(L) == 1:
    for l in L[1:]:
        if l == '0':
            dp0 = (dp[-1][0] * 3 + 1) % MOD
            dp1 = (dp[-1][1]) % MOD
        else:
            dp0 = (dp[-1][0] * 3 + dp[-1][1] + 1) % MOD
            dp1 = (dp[-1][1] * 2) % MOD
        dp.append((dp0, dp1))

print(((dp[-1][0] + dp[-1][1]) * 2 + 1) % MOD)


Measured memory_bytes: 16724
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  	cin>>n;
  	vector<char>s1(n);
  	vector<char>s2(n);
  	for(int i=0;i<n;i++){
    	cin>>s1[i];
    }
  	
  	if(n%2==1){
    cout<<"No"<<endl;
    }
  	else {
    	for(int i=0;i<n/2;i++){
        	s2[i]=s1[i];
          	s2[i+(n/2)]=s1[i];
        }
    
  		int a=0;
  		for(int i=0;i<n;i++){
    		if(s1[i]==s2[i]){
    			a++;
    		}
		}
  		if(a==n){
     		cout<<"Yes"<<endl;
    	}
  		else{
     		cout<<"No"<<endl;
     }
        }
    	}

Measured memory_bytes: 256
#include <stdio.h>
int B[9900000];
long cnt=0;
void shellSort(int n);
void insertionSort(int n,int g);
void Answer(int n,int G[30],int m);
int main(void){
	int i,n,m;
	char str[1000];

	fgets(str,sizeof(str),stdin);
	sscanf(str,"%d",&n);
	for(i=0;i<n;i++){
		fgets(str,sizeof(str),stdin);
		sscanf(str,"%d",&m);
		B[i]=m;		
	}
	shellSort(n);
	return 0;
}

void shellSort(int n){
	int i,m,G[1000];
	int tmp=0;
	for(m=0; ;m++){
		if(n>=3*tmp+1) G[m]=3*tmp+1;
		else break;
		tmp=3*tmp+1;
	}
	for(i=m-1;i>=0;i--)
		insertionSort(n,G[i]);
	Answer(n,G,m);
}
void insertionSort(int n,int g){
	int i,j,v;
	for(i=g;i<n;i++){
		v = B[i];
		j = i - g;
		while(j>=0 && B[j]>v){
			B[j+g] = B[j];
			j = j - g;
			cnt++;
			B[j+g] = v;
		}
	}
}
void Answer(int n,int G[1000],int m){
	int i;
	printf("%d\n",m);
	for(i=m-1;i>=0;i--){
		if(i!=m-1) printf(" ");
		printf("%d",G[i]);
	}
	printf("\n%d\n",cnt);
	for(i=0;i<n;i++){
		printf("%d\n",B[i]);
	}	
}

Measured memory_bytes: 4712
//ほぼstandard answer
#include<iostream>
using namespace std;

class Cube{
public:
  int f[6];
  Cube(){} 
  void roll_z(){ roll(1, 2, 4, 3);} //横向き
  void roll_y(){ roll(0, 2, 5, 3);} //サイコロの番号は+1
  void roll_x(){ roll(0, 1, 5, 4);}
  void roll(int i, int j, int k, int l){
    int t = f[i]; f[i] = f[j]; f[j] = f[k]; f[k] = f[l]; f[l] = t;
  }
  void move(char ch){
    if ( ch == 'W' ) roll_y();
    if ( ch == 'N' ) roll_x();
    if ( ch == 'E' ) for ( int i = 0; i < 3; i++ ) roll_y();
    if ( ch == 'S' ) for ( int i = 0; i < 3; i++ ) roll_x();
  }
};

int getRight( Cube c1, int f1, int f2 ){ //what is the right face
  for(int i = 0; i < 6; i++){
    for ( int j = 0; j < 4; j++ ){
      if ( c1.f[0] == f1 && c1.f[1] == f2 ) return c1.f[2];
      c1.roll_z(); //違ったら横に回転してf[1]変えてみよか(前面)
    }
    if ( i % 2 == 0 ) c1.roll_y();
    /*i%2==0 に意味はないんちゃう？
      3回ずつ2方向回転*/
    else c1.roll_x();
  }
  return -1;
}

int main(){
  Cube c; 
  int f1,f2; //question
  //f1 -> up    f2 -> front
  
  for ( int i = 0; i < 6; i++ ) cin >> c.f[i]; //define each face 
  int q; cin >> q; //the number of questions
  
  for ( int i = 0; i < q; i++ ){
    cin >> f1 >> f2;
    cout << getRight(c, f1, f2) << endl;
  }
  
  return 0;
}



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

using namespace std;

const long long MOD=1000000007;

long long add_mod(long long x,long long y){
	return (x+y)%MOD;
}

long long sub_mod(long long x,long long y){
	return (x-y+MOD)%MOD;
}

long long mul_mod(long long x,long long y){
	return x*y%MOD;
}

long long inv_mod(long long x){
	if(x == 1) return 1;
	long long d = MOD/x+1;
	return d*inv_mod(x-(MOD%x))%MOD;
}

long long div_mod(long long x, long long y){
	return x*inv_mod(y)%MOD;
}

long long conv_mod(long long n,long long r){
	long long numer = 1, denom = 1;
	for(int i = 0;i < r;i++){
        numer = mul_mod(numer,n-i);
        denom = mul_mod(denom,i+1);
	}
	return div_mod(numer,denom);
}

long long pow_mod(long long x,long long y){
	long long r = 1;
	for(long long n = x;y != 0;y /= 2,n = mul_mod(n,n)){
		if(y % 2){
			r = mul_mod(r,n);
		}
	}
	return r;
}

int n;

void solve(){
    int i,j;
    string str;
    int a,b;
    cin >> n >> a >> b;
    long long ans = 0;
    ans = pow_mod(2,n);
    ans = sub_mod(ans,1);
    ans = sub_mod(ans,conv_mod(n,a));
    ans = sub_mod(ans,conv_mod(n,b));
    cout << ans << endl;
}

int main(){
    solve();
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]

class Util():
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)

def main():
    N,M = cin.mapInt()
    X = cin.mapInt()
    S = [0] * (M - 1)
    X.sort()
    for i in range(M - 1):
        S[i] = X[i + 1] - X[i]
    ans = sum(S)
    S.sort(reverse = True)
    for i in range(min(N - 1,M - 1)):
        ans -= S[i]
    print(ans)
    return

if __name__ == "__main__":
    main()


Measured memory_bytes: 53160
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define ALL(A) A.begin(),A.end()
const long long mod=1000000007;
int main(){
    int n;
    cin>>n;
    vector<int> h(n);
    for(int i=0;i<n;i++)
    cin>>h[i];

    int i=0,ans=0;
    while(i<n)
    {
        while(h[i]==0)
        i++;

        for(int j=i;j<n;j++){
            if(h[j]==0)
            break;
            h[j]--;
        }
        ans++;
    }
    cout<<ans-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    k = f.read_int()

    depth = [float('inf')] * k
    depth[1] = 1

    que = collections.deque([1])
    while len(que) > 0:
        num = que.popleft()
        n1 = (num*10)%k
        if depth[n1] > depth[num]:
            depth[n1] = depth[num]
            que.appendleft(n1)
        n2 = (num+1)%k
        if depth[n2] > depth[num]+1:
            depth[n2] = depth[num]+1
            que.append(n2)

    return depth[0]


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> dp(n + 1, vector<int>(3));

    rep(i, n) {
        int a, b, c;
        cin >> a >> b >> c;

        dp[i + 1][0] = max(dp[i][1] + a, dp[i][2] + a);
        dp[i + 1][1] = max(dp[i][0] + b, dp[i][2] + b);
        dp[i + 1][2] = max(dp[i][0] + c, dp[i][1] + c);
    }

    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;

    return 0;
}

Measured memory_bytes: 5760
a=[]
for x in input().split(" "):
    a.append(int(x))

b=[]
if a[1]-a[0]+1<-1000000:
    i=-1000000
    while i<a[1]+a[0]:
        b.append(str(i))
        i+=1
elif a[1]+a[0]-1>1000000:
    i=a[1]-a[0]+1
    while i<1000000:
        b.append(str(i))
        i+=1
else:
    i=a[1]-a[0]+1
    while i<a[1]+a[0]:
        b.append(str(i))
        i+=1

print(' '.join(b))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N;
  cin>>N;
  
  vector<double> money(N);
  vector<string> type(N);
  for(int i=0;i<N;i++){
    cin>>money[i]>>type[i];
  }
  
  double ans=0;
  
  
  for(int i=0;i<N;i++){
    if(type[i]=="JPY"){
      ans+=money[i];
    }
    else{
      ans+=(money[i]*380000);
    }
  }
  
  printf("%.10f",ans);
}

Measured memory_bytes: 3752
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <bitset>
using namespace std;

int N, M, P, adj[20][20], fullbit;

// dp[S] := S が連結になる確率
double prob, dp[1 << 15], sum = 0;

double rec(int bit) {
    double &res = dp[bit];
    if(res >= 0) return res;
    
    int LSB = bit & (-bit);
    res = 0;
    for(int A=bit; A>0; A=(A-1)&bit) {
        int B = bit - A;
        if(A == 0 || B == 0 || !(A & LSB)) continue;
        int edges = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if( (A >> i & 1) && (B >> j & 1) ) edges += adj[i][j];
            }
        }
        res += rec(A) * pow(prob, edges);
    }
    return res = 1 - res;
}

int main() {
    cin >> N >> M >> P;
    prob = 1.0 * P / 100;
    for(int i=0; i<M; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u][v]++;
        adj[v][u]++;
    }

    fullbit = (1 << N) - 1;
    fill(dp, dp + fullbit + 1, -1);
    cout << fixed << setprecision(12) << rec(fullbit) << endl;
    return 0;
}


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

#define int    long long

void fast()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}
//a^n O(log(n))

int power(int a, int n)
{
	int result = 1;
	while (n > 0)
	{
		if (n & 1)
		{
			result = result * a;
		}
		a = a * a;
		n = n >> 1;

	}
	return result;
}


bool compare(string &s1, string &s2)
{
	return s1.size() < s2.size();
}

int32_t main()
{
	fast();
	int l, r, d;
	cin >> l >> r >> d;

	int cnt = 0;

	for (int i = l; i <= r; ++i)
	{
		if (i % d == 0)
		{
			cnt++;
		}
	}

	cout << cnt << '\n';

	return 0;
}


Measured memory_bytes: 3612