akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

const int p = pow(10, 9) + 7;

ll binpow(ll base, int n) {
    ll res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = (res * base) % p;
        }

        base = (base * base) % p;
        n = n / 2;
    }

    return res;
}

int choose(int n, int a) {

    ll numerator = 1;
     for (int i = 0; i < a; ++i) {
        numerator = numerator * (n - i) % p;
    }

    ll denom = 1;
    for (int i = 0; i < a; ++i) {
        denom = denom * (a - i) % p;
    }

    ll mult_inv_denom = binpow(denom, p - 2);
    return (numerator * mult_inv_denom) % p;

}

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

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

    int total = binpow(2, n) - 1;
    int nCa = choose(n, a);
    int nCb = choose(n, b);

    // need to make sure output positive modulo
    // see https://stackoverflow.com/questions/12276675/modulus-with-negative-numbers-in-c
    cout << (((total - nCa - nCb) %p) + p) %p;

    return 0;
}

/*
file=d
g++ -W -Wall -pedantic --std=c++17 -ggdb3 -o out ${file}.cpp && ./out

3 
*/


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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N, K;
    cin >> N >> K;
    ll ans = 0;
    for (ll i = K; i <= N + 1; ++i)
    {
        ll minNum = (i - 1) * i / 2;
        ll maxNum = N * (N + 1) / 2 - (N - i) * (N - i + 1) / 2;
        ans = (ans + maxNum - minNum + 1) % MOD;
    }

    cout << ans << endl;
}


Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main(void)
{
  while(true)
    {
  int h,w;
  cin>>h;
  cin>>w;
  if(h==0 && w==0)break;
  for(int i=0;i<h;i++)
    {
      for(int j=0;j<w;j++)
	{
	  if((i+j)%2==0)cout<<"#";
	  else cout<<".";
	}
      cout<<endl;
    }
  cout<<endl;
    }
  return 0;
}

Measured memory_bytes: 1152
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int y = sc.nextInt();
    int z = sc.nextInt();
    int i = 1;
    while(true){
      if(x < i * y + z * (i + 1)){
        System.out.println(i - 1);
        break;
      }
      i++;
    }
  }
}

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

constexpr int nax = 1e5, inf = 1e9;

int n, k, res, tab[nax + 1], deg[nax + 1], dis[nax + 1];
vector< int > gr[nax + 1];

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

    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
    {
        int v; cin >> v;
        tab[i] = v;
        if (i == 1 and v != 1) tab[i] = 1, ++res;
        else gr[v].push_back(i);
    }

    for (int i = 1; i <= n; ++i)
        deg[i] = gr[i].size();

    queue< int > Q;

    for (int i = 1; i <= n; ++i)
        if (not deg[i])
            Q.push(i);

    while (not Q.empty())
    {
        int v = Q.front(); Q.pop();
        for (int s : gr[v])
            dis[v] = max(dis[v], dis[s] + 1);
        if (dis[v] == k - 1 and v != 1 and tab[v] != 1)
            ++res, dis[v] = -inf;
        if (not --deg[tab[v]])
            Q.push(tab[v]);
    }

    cout << res << '\n';
}

Measured memory_bytes: 10240
use std::io::{ stdin, stdout, BufRead, Write };

const SP   : u8 = b' ';
const LF   : u8 = b'\n';
const ZERO : u8 = b'0';

#[inline(always)]
fn uitoa(mut n: usize, buf: &mut Vec<u8>) {
  buf.clear();
  if n == 0 {
    buf.push(ZERO);
    return;
  }

  while n > 0 {
    buf.push((n % 10) as u8 + ZERO);
    n /= 10;
  }

  buf.reverse();
}

#[inline(always)]
fn atoui(s: &[u8]) -> usize {
  let mut n = 0;
  for b in &s[..] { n = n * 10 + (b - ZERO) as usize; }
  n
}

#[inline(always)]
fn vec_write_with(buf: &mut Vec<u8>, s: &mut Vec<u8>, b: u8) {
  s.push(b);
  buf.write(s).unwrap();
}

macro_rules! input {
  ($stdin:ident, $delim:expr, $buf:ident) => {
    {
      $buf.clear();
      let len = $stdin.read_until($delim, &mut $buf).unwrap();
      $buf.truncate(len - 1);
      atoui(&$buf)
    }
  };
}

macro_rules! subroutine {
  ($buf:ident, $ans:ident, $odd:ident, $n:ident, $i:ident, $j:ident, $x:ident, $y:ident, $num:ident) => {
    if $odd != 0 {
      uitoa($y + 1, &mut $num);
      vec_write_with(&mut $ans, &mut $num, SP);

      uitoa($x + 1, &mut $num);
      vec_write_with(&mut $ans, &mut $num, SP);

      uitoa($i + 1, &mut $num);
      vec_write_with(&mut $ans, &mut $num, SP);

      uitoa($j + 1, &mut $num);
      vec_write_with(&mut $ans, &mut $num, LF);

      $n += 1;
    }
    $odd ^= $buf[$j * 2] & 1;
    $y = $i;
    $x = $j;
  };
}

fn main() {
  let stdin = stdin();
  let mut stdin = stdin.lock();

  let mut buf = Vec::with_capacity(500 * 2);
  let h = input!(stdin, SP, buf);
  let w = input!(stdin, LF, buf);

  let mut num = Vec::with_capacity(3);
  let mut ans = Vec::with_capacity(8 * 500);
  let mut n   = 0;

  let mut odd = 0;
  let mut x   = 0;
  let mut y   = 0;

  for i in 0..h {
    buf.clear();
    stdin.read_until(LF, &mut buf).unwrap();

    if i % 2 == 0 {
      for j in 0..w {
        subroutine!(buf, ans, odd, n, i, j, x, y, num);
      }
    } else {
      for mut j in 0..w {
        j = w - 1 - j;
        subroutine!(buf, ans, odd, n, i, j, x, y, num);
      }
    }
  }

  let stdout = stdout();
  let mut stdout = stdout.lock();

  uitoa(n, &mut buf);
  buf.push(LF);
  stdout.write(&buf).unwrap();

  stdout.write(&ans).unwrap();
  stdout.flush().unwrap();
}


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

int main(){
    int N, sum = 0;
    string S;
    cin >> N >> S;

    rep(i,N-2){
        if(S.substr(i,3) == "ABC"){
            sum++;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.array; // split
import std.conv; // to
 
void main()
{
   string n = chomp(readln());
   int a = to!int(n);
   if(a%10 == a/100){
       writeln("Yes");
   } else {
       writeln("No");
   }
}

Measured memory_bytes: 256
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let s = read::<String>().chars().collect::<Vec<_>>();
    let k = read::<usize>();

    let mut start = s.len();
    for i in 0..s.len() {
        if s[i] != '1' {
            start = i;
            break
        }
    }

    if k - 1 < start {
        println!("1")
    } else {
        println!("{}", s[start])
    }
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		char[] str = sc.next().toCharArray();
		
		int n = str.length;
		
		for(int i = 0; i < n/2; i++) {
//			System.out.println(str[i] +" "+ str[(n - 1)/2 - i - 1] +" " + str[i + (n + 1)/2] +" "+ str[n - 1 - i]);
			if((str[i] != str[n - 1 - i]) ||
					(str[i] != str[(n - 1)/2 - i - 1]) ||
					(str[i + (n + 1)/2] != str[n - 1 - i])){
				System.out.println("No");
				return;
			}
		}
		
		System.out.println("Yes");
	}

}


Measured memory_bytes: 23124
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    ll N; cin >> N;
    vector<ll> d(N);
    rep(i,N) cin >> d.at(i);
    ll sum = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            sum += d[i] * d[j];
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;

int main(){
    int n;
    cin >> n;
    double ans = 0;
    rep(i, n){
        double a;
        cin >> a;
        ans += 1/a;
    }

    cout << fixed << setprecision(9) << 1/ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626
#define mod llint(1e9+7)

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(llint a, llint b) {
	return a > b;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//aCbを1000000007で割った余りを求める
llint convination(llint a, llint b) {
	llint ans = 1;
	for (llint i = 0; i < b; i++) {
		ans *= a - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= b; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

//aのb乗をmodで割った余りを求める
llint power(llint a, llint b) {
	if (b == 1)return a;
	if (b == 0)return 1;
	llint tmp = power(a, b / 2);
	tmp *= tmp;
	tmp %= mod;
	if (b % 2 == 1) {
		tmp *= a;
		tmp %= mod;
	}
	return tmp;
}

int n, m;
vvint a(n);
vbool visited(n, false);

int dfs(int p, int &points) {
	visited[p] = true;
	for (int i : a[p]) {
		if (visited[i]) {
			return p;
		}
		else {
			points |= dfs(i, points);
		}
	}
}

int main() {
	int a, b;
	cin >> a >> b;
	cout << GCD(a, b) << endl;
	return 0;
}


Measured memory_bytes: 3084
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stdio.h>

using namespace std;



int main()
{
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='+')
        ans++;
        else if(s[i]=='-')
        ans--;
    }
    cout<<ans;
    //system("pause");
    return 0;
} 

Measured memory_bytes: 256
s = input()

for bit in range(1 << 3):
    ans = int(s[0])
    f = s[0]

    for i in range(3):
        # フラグが立っていれば "+" 、なければ "-"
        if bit & (1 << i):
            ans += int(s[i + 1])
            f += "+"
        else:
            ans -= int(s[i + 1])
            f += "-"
        f += s[i + 1]

    if ans == 7:
        print(f + "=7")
        exit()


Measured memory_bytes: 3060
maxval = 0

nums=list(map(int,input().split()))
h = nums[0]
w = nums[1]
G = [[0 for i in range(w)] for j in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    nums=list(map(int,input().split()))
    for j in range(w):
        G[i][j] = nums[j]

for i in range(h):
    for j in range(w):
        if G[i][j] == 1:
            dp[i][j] = 0
        else:
            if i == 0 or j == 0:
                dp[i][j] = 1
                if maxval == 0:
                    maxval = 1
            else:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
                if dp[i][j] > maxval:
                    maxval = dp[i][j]
                    

print(maxval ** 2)
























Measured memory_bytes: 56492
import scala.io.Source

object Main extends App{
  Source.stdin.getLines.toList.map(_.split(" ")).takeWhile(_(1) != "?")
    .map(x => (x(0).toInt,x(1),x(2).toInt))
    .map(x => (if(x._2 == "+") x._1+x._3 else if(x._2 == "-") x._1-x._3 else if(x._2 == "*") x._1*x._3 else if(x._2 == "/") x._1/x._3))
    .map(println)
}

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

int func2(int i){ //桁の総和を求める関数
  if( i < 10 ) return i;
  return i%10 + func2(i/10);
}
  

int func(int i, int a, int b){//桁の総和が適切なモノのみを返す
  int sum;
  sum = func2(i);
  if( a <= sum && sum <= b ){
    return i;
  }else{
    return 0;
  }
}
  
int main() {
  int n,a,b;
  cin >> n >> a >> b;
  int sum=0;
  for(int i=1;i<=n;i++){
     sum += func(i,a,b); 
  }
  
  cout << sum << endl;
  
  return 0;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(void) {
	ll A, B, C;
	cin>>A>>B>>C;
	ll cnt = 0;
	if(A % 2 == 1 || B % 2 == 1 || C % 2 == 1) {
		cout<<0<<endl;
		return 0;
	}
	while(true) {
		if(A == 0 && B == 0 && C == 0) {
			cnt = -1;
			break;
		}
		if(A % 2 == B % 2 && B % 2 == C % 2) {
			++cnt;
			A /= 2;
			B /= 2;
			C /= 2;
		} else {
			break;
		}
	}
	cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  int x,y;
  cin>>x>>y;
  cout << x + y/2 << endl;
  return 0;
}


Measured memory_bytes: 256
H,W = gets.chomp!.split.map(&:to_i)
Datas=[]
for i in 0...H
  Datas.push(gets.chomp!)
end

(W+2).times do
  print("#")
end
print("\n")

for i in 0...H do
  puts("##{Datas[i]}#")
end

(W+2).times do
  print("#")
end
print("\n")

Measured memory_bytes: 1788
// 2011/09/19 Tazoe

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string P;
	cin >> P;

	int N;
	cin >> N;

	int cnt = 0;
	for(int i=0; i<N; i++){
		string T;
		cin >> T;

		T += T;
		if(T.find(P)!=string::npos)
			cnt++;
	}

	cout << cnt << endl;

	return 0;
}

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

class BIT {
public:
	int size_ = 0;
	vector<long long> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_, 0);
	}
	void add(int pos, long long x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos&-pos);
		}
	}
	long long sum(int pos) {
		pos++; long long s = 0;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos&-pos);
		}
		return s;
	}
	long long getpoint(long long val) {
		long long cl = 0, cr = size_ + 1, cm, minx = (1 << 30);
		for (int i = 0; i < 25; i++) {
			cm = (cl + cr) / 2;
			long long v = sum(cm);
			if (v < val) { cl = cm; }
			else { cr = cm; minx = min(minx, cm); }
		}
		return minx;
	}
};

long long Q, K, V, ty[1 << 18], a[1 << 18], b[1 << 18];
vector<long long> X;
BIT Z1, Z2;

int main() {
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> ty[i];
		if (ty[i] == 1) { cin >> a[i] >> b[i]; X.push_back(a[i]); }
	}
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	Z1.init(X.size() + 2);
	Z2.init(X.size() + 2);

	for (int i = 1; i <= Q; i++) {
		if (ty[i] == 1) {
			K++; V += b[i];
			int pos1 = lower_bound(X.begin(), X.end(), a[i]) - X.begin();
			Z1.add(pos1, 1);
			Z2.add(pos1, a[i]);
		}
		if (ty[i] == 2) {
			long long pos = Z1.getpoint((K + 1) / 2);
			long long pos2 = Z1.sum(pos);
			long long v1 = Z2.sum(pos);
			long long v2 = Z2.sum(X.size() + 1) - Z2.sum(pos);
			long long u1 = 1LL * (pos2) * X[pos] - v1;
			long long u2 = v2 - 1LL * (K - pos2) * X[pos];
			cout << X[pos] << " " << u1 + u2 + V << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 10740
#include <stack>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <iomanip>
#include <string>
#include <limits>
using namespace std;
int gcd(int a, int b)//最大公約数
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}
int mod = 1000000000 + 7;
vector<int> v;
class Calc
{
    // 宣言
    long long a;

    public:
        // 素因数分解
        void decompositPrime(long long a);
};

/*
 * 素因数分解
 */
void Calc::decompositPrime(long long n)
{
    // 割る数の初期値
    a = 2;
    // √n ≧ a ( n ≧ a * a ) の間ループ処理
    while (n >= a * a) {
        // a で割り切れたら、a は素因数
        // そして、割られる数を a で割る
        // a で割り切れなかったら、 a を 1 増加させる
        if (n % a == 0) {
            //printf("%d * ", a);
             v.push_back(a);
            n /= a;
        } else {
            a++;
        }
    }
    // 最後に残った n は素因数
    v.push_back(n);
    //printf("%d\n", n);
}
vector<int> divisor(int n) {//約数発見
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    std::sort(ret.begin(), ret.end());
    return ret;
}
long nc2(long n){
    return n*(n-1)/2;
}
template<typename TypeInt>
std::string Itoa(const TypeInt v, int base)
{
	static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string ret;
	static numeric_limits<TypeInt> t;
	TypeInt n = v;
	if (t.is_signed) {
		if (v < 0) n *= -1;
	}

	while (n >= base) {
		ret += table[n%base];
		n /= base;
	}
	ret += table[n];
	if (t.is_signed) {
		if (v < 0 && base == 10) ret += '-';
	}
	// 文字列の順番を逆にする
	std::reverse(ret.begin(), ret.end());

	return ret;
}
int main(){
    //std::stack<int> stack;
    long n;
    cin >> n;
    vector<long> a(n+1);
    for(int i = 0; i <= n; i++){
        cin >> a[i];
    }
    long ans = 0;
    long tmp = 1;
    vector<long> sum(n+2,0);
    sum[n] = a[n];
    for(int i = 1; i <= n; i++){
        sum[n-i] = sum[n-i+1] + a[n-i];
    }
    for(int i = 0; i <= n; i++){
        ans += tmp;
        tmp -= a[i];
        if(tmp < 0){
            cout << -1 << endl;
            return 0;
        }
        
        tmp = min(tmp*2, sum[i+1]);
    }
    cout << ans << endl;
    return 0;
}






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

def main():
    o = input()
    e = input()
    res = ""
    for i in range(len(e)):
        res = res + o[i] + e[i]
    if len(o) > len(e):
        res = res + o[-1]
    print(res)

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
// g++ -I ~/Documents/programming/cppLib -std=gnu++14 -o test ~/Documents/programming/cppLib/test.cpp && ./test && rm test
#include <bits/stdc++.h>
using namespace std;
template <typename T> using vector2 = vector <vector  <T>>;
template <typename T> using vector3 = vector <vector2 <T>>;
template <typename T> using vector4 = vector <vector3 <T>>;
using lint = long long;
#define FOR( i, a, b ) for( lint i=(a) ; i <= (b) ; ++i )
#define REP( i, n )    for( lint i= 0  ; i <  (n) ; ++i )
#define ALL( v )       (v).begin(), (v).end()

template <int mod>
struct mint{
    int data;
    mint( void ) :data(0) {}
    mint( int n ) :data(n % mod) {}
    operator int() { return data; }
    friend istream &operator>>(istream&is,mint&m){int n; is>>n; m=n; return is;}
    friend ostream &operator<<(ostream&os,mint&m){os<<(int)m; return os;}
    mint operator+(  int n ) { return (data + n) % mod; }
    mint operator+( mint m ) { return *this + (int)m; }
    void operator+=( int n ) { data = *this +      n; }
    void operator+=(mint m ) { data = *this + (int)m; }
    mint operator*(  int n ) { return (lint)data * n % mod; }
    mint operator*( mint m ) { return *this * (int)m; }
    void operator*=( int n ) { data = *this *      n; }
    void operator*=(mint m ) { data = *this * (int)m; }
    bool operator==( int n ) { return data == n; }
    bool operator==(mint m ) { return data == m.data; }
    bool operator!=( int n ) { return data != n; }
    bool operator!=(mint m ) { return data != m.data; }
    mint pow(int n){mint a=1,b=data;while(n>0){if(n&1)a*=b;b*=b;n>>=1;}return a;}
    mint pow(mint m){ return (*this).pow((int)m); }
};

using mint_7 = mint<1000000007>;
using mint_9 = mint<1000000009>;

int main() {
    mint_7 m, n;
    cin >> m >> n;
    cout << m.pow(n) << endl;
}



Measured memory_bytes: 3104
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int compare_int(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}


int main(void)
{
	int N, K, m = 0;
	int p[1001];
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++)
	{
		scanf("%d",p+i);
	}

	qsort(p, N, sizeof(int), compare_int);
	for (int i = 0; i < K; i++)
	{
		
		m = m + p[i];
	}
	printf("%d",m);
	return 0;
}

Measured memory_bytes: 1752
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

h = {}
for a in A:
	if a in h:
		print('NO')
		exit()
	h[a] = 1
print('YES')


Measured memory_bytes: 100820
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ans=0;
	string s1,s2;
	cin>>n>>s1>>s2;
	for(int i=0;i<n;++i)
	{
		int l=0;
		for(int j=i;j<n;++j)
		{
			if(s1[j]!=s2[l])break;
			++l;
		}
		ans=max(ans,l);
	}
	cout<<n*2-ans<<endl;
}

Measured memory_bytes: 256
xn = input().split()
data_2 = []
x = int(xn[0]) #これに近い値

if int(xn[1]) == 0:
    print(x)
else:
    data_str = input().split()
    data = [int(s) for s in data_str] #data_strをint型に変換
    #data.sort() #小さい順
    #dataにない値が出るまでxから１引き続ける　１引き続けた値をaとする
    a = int(xn[0])
    #check
    while True: #while1
        while True: #while2
            for i in range(len(data)):
                if data[i] != a:
                    continue
                else:
                    a -= 1
                    break #forから抜け出す
            else:
                data_2.append(a)
                break #while2から抜け出す

        if len(data_2) == 1: #リストに１つデータが入っていたら　入ってないならwhile1ループ
            break #while1から抜け出す    


    #dataにない値が出るまでxかに１を足し続ける　１足し続けた値をbとする
    b = int(xn[0])
    while True: #while1
        while True: #while2
            for i in range(len(data)):
                if data[i] != b:
                    continue
                else:
                    b += 1
                    break #forから抜け出す
            else:
                data_2.append(b)
                break #while2から抜け出す

        if len(data_2) == 2: #リストに2つデータが入っていたら　入ってないならwhile1ループ
            break #while1から抜け出す  


    #aとbの小さい方をprint
    if abs(x-a) <= abs(b-x):
        print(a)
    else:
        print(b)


Measured memory_bytes: 9128
require 'prime'

N = gets.to_i

# N!を素因数分解する =>
# Nを素因数分解する
# N-1を素因数分解する
# ~~~
# 1を素因数分解する
prime_divisions = Hash.new {0}
1.upto(N) do |i|
  (Prime.prime_division(i)).each do |k|
    prime_divisions[k[0]] += k[1]
  end
end

count = Hash.new(0)
prime_divisions.each do |k, v|
  [2, 4, 14, 24, 74].each do |t|
    count[t]+=1 if v >= t
  end
end

res = 0
# p^74
res += count[74]
# p^2*q^24
# 同じものを使えないので-1する
# 24以上のものには2以上のものも含まれている
res += count[24] * (count[2]-1)
# p^4*q^14
res += count[14] * (count[4]-1)
# p^2*q^4*r^4
# 2^4*3^4*5^2、3^4*2^4*5^2のようなパターンを重複して数えてしまうので2で割る
res += (count[4] * (count[4]-1)/2 )* (count[2]-2)

p res


Measured memory_bytes: 2044
import java.util.*;

public class Main {

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

        String s = sc.next();
        char[] arr = s.toCharArray();

        for (int i=0; i<s.length(); i++) {
            if (i%2==0) {
                if (arr[i]!='h') {
                    System.out.print("No");
                    return;
                }
            }else {
                if (arr[i]!='i') {
                    System.out.print("No");
                    return;
                }
            }
        }

        if (arr[s.length()-1]=='h') {
            System.out.print("No");
            return;
        }

        System.out.print("Yes");
    }

}



Measured memory_bytes: 23124
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<utility>//swapでaとbの値を入れ替える
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
#define sortaa(s) sort(s.begin(),s.end())
#define r(s) reverse(s.begin(),s.end())
using namespace std;


int main() {
  string a,b;
  cin>>a;
  rep(i,a.size()){
  if(a[i]=='1')b+='1';
  if(a[i]=='0')b+='0';
  if(a[i]=='B'&&b.size()>0)b.erase(b.size()-1);
   }
   
   cout<<b<<endl;
 return 0;
 }

Measured memory_bytes: 256
import java.util.*;

class Main {
    static int i=1;
  
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      while(true) {
        int x = sc.nextInt();
        if (x == 0) {
          break;
        } else {
        System.out.println("Case " + i + ": " + x);
        i ++;
        }
      }
    }
}


Measured memory_bytes: 42496
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter syso = new PrintWriter(System.out);
		double n=sc.nextDouble();
		double a=sc.nextDouble();
		int t=sc.nextInt();
		int ans=(int)Math.ceil(n/a);
		syso.println(ans*t);
        syso.close();
    }
    
 
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
		public int[] nextArr(int n) throws IOException{
			int arr[]=new int[n];
			for(int i=0;i<n;i++)arr[i]=nextInt();
			return arr;
		}
		public BigInteger BigInteger(String s) throws IOException{
			BigInteger a=new BigInteger(s);
			return a;
		}
 
	}
}

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

long long h(long long n){
    if(n == 0) return 1;
    else return h(n-1) * 2 + 3;
}

long long pt(long long n){
    if(n == 0) return 1;
    else return pt(n-1) * 2 + 1;
}

long long slove(long long n, long long k){
    long long ht = h(n);
    long long htdiv = ht / 2 + 1;
    long long rpt;
    // cout << endl;
    // cout << n << " " << k << endl;
    // cout << ht << " " << htdiv << endl;
    
    if(k == ht){
        // cout << "k == ht" << endl;
        rpt = pt(n);
    }else if(n == 1){
        // cout << "n is 1" << endl;
        if (2 <= k && k <= 4) rpt = k - 1;
        else rpt = 0;
    }else if(k > htdiv){
        // cout << "k > htdiv" << endl;
        rpt = slove(n-1, k-htdiv) + pt(n - 1) + 1;
    }else if(k == htdiv){
        // cout << "k == htdiv" << endl;
        rpt = pt(n - 1) + 1;
    }else{
        // cout << "k < htdiv" << endl;
        rpt = slove(n-1, k-1);
    }
    // cout << "rpt is " << rpt << endl;
    return rpt;
}

int main(void){
    long long n, k;
    cin >> n >> k;
    cout << slove(n, k) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int n; cin >> n;
  vector<int> v(n);
  rep(i, n) cin >> v[i];
  int ans = 0;
  rep(i, n){
    if(v[i] == i+1){
      v[i+1] = v[i];
      ans++;
    }
  }
  cout << ans << endl;
  system("pause");
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int main(void) {
    int n; cin >> n;
    vector<P> a(n);
    rep(i, n) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(),a.end());
    vector<int> table(n);
    rep(i, n) {
        table[a[i].second] = i;
    }
    rep(i, n) {
        if(table[i] == n-1) cout << a[n-2].first << endl;
        else cout << a[n-1].first << endl;
    }
}



Measured memory_bytes: 3968
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
for i in range(n):
  #左側
  left = min(a[i], b[i])
  ans += left

  a[i] -= left
  b[i] -= left

  #右側
  right = min(a[i + 1], b[i])
  ans += right
  a[i + 1] -= right
  b[i] -= right

print(ans)



Measured memory_bytes: 18624
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

typedef long long ll;

const ll mod=1e9+7;

#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define rc(x)  return cout<<x<<"\n",0
#define sz(s)  (int) s.size()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;

ll t;
const int nax=305;
double p[nax][nax][nax], ev[nax][nax][nax];	

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vector<int>cnt(4);
	for (int i=0; i<n; i++) {
		ll x;
		cin >> x;
		cnt[x]++;
	}
	p[cnt[1]][cnt[2]][cnt[3]]=1;
	for (int c=n; c>=0; c--) {
		for (int b=n-c; b>=0; b--) {
			for (int a=n-b-c; a>=0; a--) {		
				if (a==0 && b==0 && c==0) {
					continue;
				}
				if (a+b+c>n) {
					continue;
				}
				double p_waste = (double) (n-(a+b+c)) / n;
				
				double ev_waste = p_waste / (1-p_waste);
			
				ev[a][b][c]+=ev_waste*p[a][b][c];
				if (a!=0) {
					double p_go = (double) a / (a+b+c); 
					p[a-1][b][c] += p[a][b][c]*p_go;
					ev[a-1][b][c] += ev[a][b][c]*p_go;
					
				}
				if (b!=0) {
					double p_go = (double) b / (a+b+c); 
					p[a+1][b-1][c] += p[a][b][c]*p_go;
					ev[a+1][b-1][c] += ev[a][b][c]*p_go;
				}
				if (c!=0) {
					double p_go = (double) c / (a+b+c); 
					p[a][b+1][c-1] += p[a][b][c]*p_go;
					ev[a][b+1][c-1] += ev[a][b][c]*p_go;
				}	
			}	
		}
	}
	/*for (int c=n; c>=0; c--) {
		for (int b=n; b>=0; b--) {
			for (int a=n; a>=0; a--) {
				cout << ev[a][b][c] << " ";
			}
			cout << '\n';
		}
		cout << '\n';
		cout << '\n';
		
	}*/
	cout << setprecision(10) << ev[0][0][0] + 1*cnt[1] + 2*cnt[2] + 3*cnt[3]<< '\n';
}

Measured memory_bytes: 438528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a-1; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


int main(){
    string s, t;    cin >> s >> t;
    vector<vector<ll>> dp(s.size()+1, vector<ll>(t.size()+1));
    rep(i, s.size()){
        rep(j, t.size()){
            dp[i+1][j+1] = dp[i][j] + (s[i]==t[j]);
            dp[i+1][j+1] = max(max(dp[i+1][j], dp[i][j+1]), dp[i+1][j+1]);
        }
    }
    ll sc=s.size(), tc=t.size();
    string res="";
    while(0<tc && 0<sc){
        if(dp[sc][tc]==dp[sc-1][tc]) sc -= 1;
        else if(dp[sc][tc]==dp[sc][tc-1]) tc -= 1;
        else{
            res += s[sc-1];
            sc -= 1, tc -= 1;
        }
    }
    reverse(ALL(res));
    cout << res << endl;
    
}


Measured memory_bytes: 73648
n, m = map(int, input().split())

tmp = [0] * n
wa = [0] * n
ac = [0] * n

for _ in range(m):
    p, s = input().split()
    p = int(p)
    p = p - 1
    
    # print(p)
    # print(s)
    
    if s == 'WA':
        if ac[p] == 0:
            tmp[p] += 1
        
    if s == 'AC':
        if ac[p] == 0:
            ac[p] = 1
            wa[p] = tmp[p]
        
print("{} {}".format(sum(ac), sum(wa)))

Measured memory_bytes: 5364
#include <iostream>
using namespace std;
const long long MOD = 1e9+7;
//aのMODbでの逆元
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
long long combi(int n,int k){
    k = min(k,n-k);
    long long p = 1;
    for(int i = n;i>=n-k+1;i--){
        p*=i;
        p%=MOD;
    }
    for(int i = 0;i<k;i++){
        p*=modinv(i+1,MOD);
        p%=MOD;
    }
    return p;
}
int main(){
    long long h,w,a,b;
    cin >> h >> w >> a >> b;
    long long comb1 = 1;
    long long comb2 = combi(w+h-b-2,w-b-1);
    long long ans = 0;
    for(int i = 0;i<h-a;i++){
        ans+=((comb1*comb2)%MOD);
        ans%=MOD;
        comb1*=(b+i);
        comb2*=(h-1-i);
        comb1%=MOD;
        comb2%=MOD;
        comb1*=modinv(i+1,MOD);
        comb2*=modinv(w+h-b-2-i,MOD);
        comb1%=MOD;
        comb2%=MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    ll N, Q;
    cin >> N >> Q;
    vector<ll> S(N), T(N), X(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i] >> T[i] >> X[i];
    }
    vector<ll> D(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> D[i];
    }

    vector<pair<llll, ll>> E;
    for (ll i = 0; i < N; i++) {
        E.push_back(make_pair(make_pair(S[i] - X[i], 2), X[i]));
        E.push_back(make_pair(make_pair(T[i] - X[i], 1), X[i]));
    }
    for (ll i = 0; i < Q; i++) {
        E.push_back(make_pair(make_pair(D[i], 3), i));
    }

    vector<ll> ans(Q);

    sort(ALL(E));

    set<ll> s;

    for (ll i = 0; i < 2*N+Q; i++) {
        if(E[i].first.second == 2){
            s.insert(E[i].second);
        }
        else if(E[i].first.second == 1){
            s.erase(E[i].second);
        }
        else{
            if(s.empty()){
                ans[E[i].second] = -1;
            }
            else{
                ans[E[i].second] = *s.begin();
            }
        }
    }

    for (ll i = 0; i < Q; i++) {
        printf("%lld\n", ans[i]);
    }

}

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

int main(){
  string S, T, U;
  int A, B;
  cin >> S >> T;
  cin >> A >> B;
  cin >> U;
  cout << ((T == U) ? to_string(A)+' ' + to_string(B - 1) : to_string(A-1) +' '+ to_string(B));
}

Measured memory_bytes: 256
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))
A = A1 + A2 + A3
N = int(input())
s = set() # index of A
for _ in range(N):
  b = int(input())
  if b in A:
    s |= {A.index(b)}
# bingo index
bingo = [{0, 1, 2}, {0, 3, 6}, {0, 4, 8}, {1, 4, 7}, {2, 4, 6}, {2, 5, 8}, {3, 4, 5}, {6, 7, 8}]
print(['No','Yes'][any(b <= s for b in bingo)])

Measured memory_bytes: 9028
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n; cin>>n;
    string s; cin>>s;

    int ok = 0, ng = n;
    while(ng - ok > 1){
        int mid = (ok + ng) / 2;

        bool valid = false;
        map<string, P> string_ht;
        for(int i=0; i+mid<=n; i++){
            string t = s.substr(i, mid);
            auto itr = string_ht.find(t);

            if(itr == string_ht.end()){
                string_ht[t] = P(i, i + mid - 1);
            }
            else{
                int ch = i;
                int ph, pt;
                tie(ph, pt) = string_ht[t];
                if(pt < ch){
                    valid = true;
                    break;
                }
            }
        }

        if(valid){
            ok = mid;
        }
        else{
            ng = mid;
        }
    }

    cout << ok << endl;

    return 0;
}

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

int main(void){
  int n,m;
  while(cin >> n >> m,m+n){
    vector<int> ps(n);
    for(int i = 0 ; i < n ; i ++){
      cin >> ps[i];
    }
    sort(ps.begin(),ps.end(),greater<int>());
    int ans = 0;
    for(int i = 0 ; i < n ; i ++){
      if((i+1)% m != 0){
        ans += ps[i];
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1216
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


//CODE
void solve(void)
{  
  int N,C;
  cin>>N>>C;
  vector<vector<int> > data(C,vector<int>(C));
  for (int i = 0; i < C; i++)
  {
    for (int j = 0; j < C; j++)
    {
      cin>>data[i][j];
    }
  }
  vector<vector<int> > GRID(3);

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      int A;
      cin>>A;
      A--;
      GRID[((i+1)+(j+1))%3].push_back(A);
    }
    
  }
  // int ANS = 0;
  // DEBUG(GRID);
  vector<vector<int> > COST_vec (3,vector<int>(C,0));
  for (int i = 0; i < 3; i++)
  {
    int COST =INF;
    for (int c = 0; c < C; c++)//色をcに統一するときの累計コストを求める。
    {
      int SUM = 0;
      for (int k = 0; k < GRID[i].size(); k++)
      {
        int X = GRID[i][k];
        SUM += data[X][c];
      }
      COST_vec[i][c] = SUM;
    }
    
  }
  int ANS = INF;
  for (int i = 0; i < C; i++)
  {
    for (int j = 0; j < C; j++)
    {
      for (int k = 0; k < C; k++)
      {
        if(i != j && j != k && k != i)
        {
          chmin(ANS,COST_vec[0][i] + COST_vec[1][j] + COST_vec[2][k]);
        }
      }
      
    }
    
  }
  cout<<ANS<<endl;
  
  
  // cout<<ANS<<endl;
  
  
  
  
  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();
  

 
  return 0;
}


Measured memory_bytes: 2608
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())





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

	int cnt[4] = {};
	int ans = 0;

	int n;
	cin >> n;
	rep(i,n) {
		string s;
		cin >> s;

		for (int i = 0; i + 1 < s.size();i++) {
			if (s[i] == 'A' && s[i + 1] == 'B')ans++;
		}
		if (s.back() == 'A') {
			if (s.front() == 'B') {
				cnt[0]++;
			}
			else {
				cnt[1]++;
			}
		}
		else {
			if (s.front() == 'B') {
				cnt[2]++;
			}
			else {
				cnt[3]++;
			}
		}
	}
	bool enda = false;
	rep(i,n){
		if (enda) {
			if (cnt[0]) {
				ans++;
				cnt[0]--;
				enda = true;
				continue;
			}
			else if (cnt[2]) {
				ans++;
				cnt[2]--;
				enda = false;
				continue;
			}
		}
		else {
			if (cnt[1]) {
				cnt[1]--;
				enda = true;
				continue;
			}
		}
		for (int i = 0; i < 4;i++) {
			if (cnt[i]) {
				cnt[i]--;
				enda = i < 2;
				break;
			}
		}
	}

	cout << ans << endl;




	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<iostream>
#include<fstream>
#include<iomanip>

using namespace std;

int n, m;
int data[100000];

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i){
		scanf("%d", &data[i]);
	}

	int Max = data[0] - 1;
	for (int i = 1; i < m; ++i) {
		if ((data[i] - data[i - 1])/2>Max){
			Max = (data[i] - data[i - 1])/2;
		}
	}
	if (n - data[m - 1] > Max) {
		Max = n - data[m - 1];
	}
	printf("%d\n", Max);
	return 0;
}

Measured memory_bytes: 1328
use std::env;
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let X = read::<i32>();
    let A = read::<i32>();
    let B = read::<i32>();

    let num = (X-A)/B;
    println!("{}", X-A-B*num);

}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include<numeric>
#include<cmath>
#include<map>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> pll;
const ll inf = 1LL << 60;

int main(){
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
    ll N; cin>>N;
    ll sq = (ll)(sqrt(N));
    int ans = 1;

    vector<bool> ifprimes(sq+1,true);
    vector<ll> primes;
    for(int i = 2;i <= sq; i++){
        if(ifprimes[i] == false) continue;
        else{
            primes.push_back(i);
            for(int k = 2*i; k <= sq; k+=i){
                ifprimes[k] = false;
            }
        }
    }
    vector<ll> divide;
    map<ll,int> minus;
    //ll now_n = N;
    FOR(i,2,sq+1){
        if(N % i == 0) {
            divide.push_back(i);
            if(i*i != N){
                divide.push_back(N / i);
            }
        }     
    }

    REP(i,divide.size()){
        ll now_n = N;
        while(now_n % divide[i] == 0){
            now_n /= divide[i];
        }
        if(now_n % divide[i] == 1)ans++;
    }

    ll minus_n = N-1;
    REP(i,primes.size()){
        if(minus_n%primes[i] == 0){
            while(minus_n % primes[i] == 0){
                minus[primes[i]]++;
                minus_n /= primes[i];
            }
        }
    }
    if(minus_n > 1)minus[minus_n]++;
    ll mm = 1;
    for(auto itr = minus.begin(); itr != minus.end(); ++itr){
        mm *= (itr->second+1);
    }
    ans += (mm-1);

    cout << ans << endl;
}

Measured memory_bytes: 4368
#!/bin/bash
':' /*
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro node:5.2-slim \
  /bin/bash -c "node /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
*/

"use strict";

const main = (input) => {
  let n = Number.parseInt(input[0]);
  let a = Array.from(input[1].split(" "), x => Number.parseInt(x));

  let cnt = 1;
  for(let ai of a) {
    if(ai==cnt) cnt+=1;
  }

  return cnt==1 ? -1 : n - cnt + 1;
};
console.log(main(require("fs").readFileSync("/dev/stdin", "utf-8")
  .trim().split("\n")));


Measured memory_bytes: 36928