akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
int main(){
    int n,m; cin >> n >> m;
    if(n >= m) cout << 0 << endl;
    else{
        vector<int> x(m); rep(i,m) cin >> x[i];
        sort(x.begin(),x.end());
        vector<int> l(m-1); rep(i,m-1) l[i] = x[i+1] - x[i];
        sort(l.begin(),l.end());
        int ans = x[m-1] - x[0];
        rep(i,n-1) ans -= l[m-2-i];
        cout << ans << endl;
    }
}


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

typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;

int N, M;
vector<int> a,b;
vector<vector<bool>> to;
vector<bool> visited;

void dfs(int x){
    visited[x] = true;
    for (int i=0;i<N;i++){
        if (x==i) continue;
        if (to[x][i] && !visited[i]) dfs(i);
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    a.resize(M),b.resize(M);
    to.resize(N,vector<bool>(N));
    for (int i=0;i<M;i++){
        cin >> a[i] >> b[i];
        a[i]--;b[i]--;
        to[a[i]][b[i]] = true;
        to[b[i]][a[i]] = true;
    }
    int ans = 0;
    visited.resize(N,false);
    for (int i=0;i<M;i++){
        to[a[i]][b[i]] = false;
        to[b[i]][a[i]] = false;
        for (int j=0;j<N;j++){
            visited[j] = false;
        }
        dfs(0);
        bool bridge = false;
        for (int j=0;j<N;j++) {
            if (!visited[j]) bridge = true;
        } 
        if (bridge) ans++;
        to[a[i]][b[i]] = true;
        to[b[i]][a[i]] = true;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, long long> P;
long long N;

class DisjointSet {
    public:
        vector<int> rank, p;
        
        DisjointSet() {}
        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for(int i = 0; i < size; i++) makeSet(i);
        }
        
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }
        
        bool same(int x, int y){
            return findSet(x) == findSet(y);
        }
        
        int findSet(int x){
            if(x != p[x]){
                p[x] = findSet(p[x]);
            }
            
            return p[x];
        }
        
        void unite(int x, int y){
            link(findSet(x), findSet(y));
        }
        
        void link(int x, int y){
            if(rank[x] > rank[y]){
                p[y] = x;
            } else {
                p[x] = y;
                if(rank[x] == rank[y]){
                    rank[y]++;
                }
            }
        }
};

class Edge{
public:
    int source; int target; long long cost;
 
    Edge(int source=0, int target=0, long long cost=0):
    source(source), target(target), cost(cost) {}
 
    bool operator < (const Edge &e) const {
        return cost < e.cost;
    }
};

long long kruskal(int N, vector<Edge> edges){
    long long totalCost = 0;
    sort(edges.begin(), edges.end());
    DisjointSet dset = DisjointSet(N + 1);
    for(int i = 0; i < N; i++){
        dset.makeSet(i);
    }
    
    
    for(int i = 0; i < edges.size(); i++){
        Edge e = edges[i];
        if(!dset.same(e.source, e.target)){
            totalCost += e.cost;
            dset.unite(e.source, e.target);
        }
    }
    
    return totalCost;
}

bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second < secondElof.second;
}

int main(void){
    // Your code here!
    // 頂点数と一致する。
    cin >> N;
    
    
    vector<Edge> edges (2*N-2);
    vector<P> A(N);
    vector<P> B(N);
    for(int i = 0; i < N; i++) {
        A[i].first = B[i].first = i;
        cin >> A[i].second >> B[i].second;
    }
    
    
    sort(A.begin(), A.end(), pairCompare);
    sort(B.begin(), B.end(), pairCompare);
    int cnt = 0;
    
    for(int i = 0; i < N-1; i++){
        edges[cnt].source = A[i].first;
        edges[cnt].target = A[i+1].first;
        edges[cnt].cost = A[i+1].second - A[i].second;
        cnt++;
    }
    
    
    for(int i = 0; i < N-1; i++){
        edges[cnt].source = B[i].first;
        edges[cnt].target = B[i+1].first;
        edges[cnt].cost = B[i+1].second - B[i].second;
        cnt++;
    }
    
    
    cout << kruskal(2*N-2, edges) << endl;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

int main() {
  string S;
  cin >> S;
  string T;
  cin >> T;

  int s = S.size();
  int t = T.size();

  bool ok = false;
  repr (i, s - t, 0) {
    string S_sub = S.substr(i, t);
    bool accord = true;
    rep (j, t) {
      if (S_sub[j] == '?')
        continue;
      if (S_sub[j] != T[j])
        accord = false;
    }
    if (accord) {
      S.replace(i, t, T);
      ok = true;
      break;
    }
  }

  if (!ok) {
    cout << "UNRESTORABLE" << endl;
    return 0;
  }

  rep (i, s) {
    if (S[i] == '?')
      S[i] = 'a';
  }

  cout << S << endl;
}

Measured memory_bytes: 256
import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		// Scanner sc = new Scanner(new File("test_1.txt"));
		// Scanner sc = new Scanner(new File("test_2.txt"));
		// Scanner sc = new Scanner(new File("in4.txt"));
		int N = sc.nextInt();
		int ans = 0;		
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			boolean is_prime = true;
			for (int i = 2; i * i <= n; i++)
				if (n % i == 0)
					is_prime = false;
			if (is_prime)
				ans++;
		}

		System.out.println(ans);		
	}
}

Measured memory_bytes: 28816
def power_sockets(A, B):
    s=0
    if B == 1:
        s = 0
    elif B <= A:
        s=1
    else:
        s=(B-A) // (A-1) + 1
        if (B-A) % (A-1) > 0:
            s = s + 1
    return s

A,B=map(int,input().split())
print(power_sockets(A,B))

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

int N;
vector<int> S2, S3, S6;

int main(){
  cin >> N;
  if(N == 3){
    cout << "2 5 63" << endl;
  }
  else{
    for(int i=2; i<=30000; i++){
      if(i%6 == 0){
        S6.push_back(i);
      }
      else if(i%2 == 0){
        S2.push_back(i);
      }
      else if(i%3 == 0){
        S3.push_back(i);
      }
    }
    //cout << S2.size() << ", " << S3.size() << ", " << S6.size() << endl;
    int z2=2, z3=2, z6=0;
    N -= 4;
    while(N >= 2 && z2 <= S2.size()-2){
      N -= 2;
      z2 += 2;
    }
    while(N >= 2 && z3 <= S3.size()-2){
      N -= 2;
      z3 += 2;
    }
    while(N > 0){
      N--;
      z6++;
    }
    //cout << z2 << ", " << z3 << ", " << z6 << endl;
    //cout << N << endl;
    for(int i=0; i<z2; i++)
      cout << S2[i] << " ";
    for(int i=0; i<z3; i++)
      cout << S3[i] << " ";
    for(int i=0; i<z6; i++)
      cout << S6[i] << " ";
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
using namespace std;

int main(){
  int n;
  string s;
  cin>>n;
  cin>>s;
  vector<char> t;
  int d=0,m=0;

  for(int i=0;i<n;i++){
    if(s[i]=='('){
      d++;
    }else{
      d--;
    }
    m=min(m,d);
  }
  
  for(int i=abs(m);i>0;i--){
    t.push_back('(');
    d++;
  }
  for(int i=0;i<n;i++){
    t.push_back(s[i]);
  }
  for(int i=abs(d);i>0;i--){
    t.push_back(')');
  }
  for(auto &e:t){
    cout<<e;
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<vector>
#include<iostream>
#include<algorithm>
#include<chrono>
#include<set>
#include<cstdio>
#include<string>
#include<unordered_map>

using namespace std;


int main()
{
    int n;
    cin >> n;
    vector<int> ans(n);
    vector<int> re(n);
    int acc = 0;
    for(int i = 0; i < n; i++)
    { 
        scanf("%d",&re[i]);
        acc ^= re[i];
    }
    for(int i = 0; i < n; i++){
        ans[i] = acc ^ re[i];
    }
    for(auto&& item:ans) 
      cout << item << endl;
}


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

using namespace std;


int main(void) {
    // A => A-=B <= C, A+=D
    long t;
    cin >> t;

    for(int i=0; i<t; i++) {
        long a, b, c, d;
        cin >> a >> b >> c >> d;
        if(b > d) {
            cout << "No" << endl;
            continue;
        }
        if(a < b) {
            cout << "No" << endl;
            continue;
        }
        if(b <= c) {
            cout << "Yes" << endl;
            continue;
        }

        assert(b <= d);
        assert(a >= b);
        assert(b >  c);

        // if a can be (c, b), No
        // if a always be [0, c], Yes
        // a % b
        // (a+kd) % b
        long g = __gcd(d, b);
        // (a + kg) <= c
        // kg <= c-a
        // k <= (c-a)/g
        long k = (c-a)/g;
        if(!(k*g <= c-a)) k--;
        long s = (a + (k+1)*g) % b;
        cout << (c < s && s < b ? "No" : "Yes") << endl;
    }
    
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int H = sc.nextInt();
        int W = sc.nextInt();
        char[][] mine = new char[H+2][W+2];
        for(int i = 1; i <= H; i++){
            String s = sc.next();
            for(int j = 1; j <= W; j++){
                mine[i][j] = s.charAt(j-1);
            }
        }
        sc.close();

        for(int i = 1; i <= H; i++){
            for(int j = 1; j <= W; j++){
                if(mine[i][j] == '.'){
                    int count = 0;
                    if(mine[i-1][j-1] == '#')
                            count++;
                    if(mine[i][j-1] == '#')
                        count++;
                    if(mine[i+1][j-1] == '#')
                        count++;
                    if(mine[i-1][j] == '#')
                        count++;
                    if(mine[i][j] == '#')
                        count++;
                    if(mine[i+1][j] == '#')
                        count++;
                    if(mine[i-1][j+1] == '#')
                        count++;
                    if(mine[i][j+1] == '#')
                        count++;
                    if(mine[i+1][j+1] == '#' )
                        count++;
                    mine[i][j] = String.valueOf(count).charAt(0);
                }
                System.out.print(mine[i][j]);
            }
            System.out.println();
        }
    }
}

Measured memory_bytes: 22228
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    ll ans = 1;
    while(1){
        if((ans*8)/100==(a*100)/100&&(ans*10)/100==(b*100)/100) break;
        if((ans*8)/100>(a*100)/100&&(ans*10)/100>(b*100)/100){
            cout<<"-1"<<endl;
            return 0;
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(int argc, char *argv[]){
  int n, t, e;
  cin >> n >> t >> e;
  int x[n];
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }
  int a = 0;
  for (int i = 0; i < n; i++) {
    while(1){
      if(t - e <= a*x[i] && a*x[i] <= t + e){
        std::cout << i + 1 << std::endl;
        return 0;
      }
      else a++;
      if(a*x[i] > t + e){
       a = 1;
       break; 
      }
    }
  }
  std::cout << -1 << std::endl;
  return 0;
}

Measured memory_bytes: 1164
#include<stdio.h>

int main(void){
    
    int N,A[20],B[20],C[20],i,ans = 0;

    scanf("%d",&N);
    for(i = 0;i < N;i++){
        scanf("%d",&A[i]);
    }
    for(i = 0;i < N;i++){
        scanf("%d",&B[i]);
    }
    for(i = 0;i < N - 1;i++){
        scanf("%d",&C[i]);
    }

    for(i = 0;i < N;i++){
        ans += B[A[i]-1];
        //printf("%d 追加 ans:%d\n",B[A[i]-1],ans);
        if(A[i] -  1 == A[i - 1]){
            ans += C[A[i - 1]-1];
            //printf("Cの %d 追加 ans:%d\n",C[A[i-1]-1],ans);
        }
    }

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

Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>

int main()
{
    long long A,B,C,X,Y,price=0;

    scanf("%lld%lld%lld%lld%lld",&A,&B,&C,&X,&Y);
    if( ( A + B ) >= ( 2 * C ) ){
        if( X > Y ){
            if( ( 2 * C ) < A ){
                price = 2 * C * X;
            }else{
                price = ( 2 * C * Y ) + ( X - Y ) * A;
            }
        }else{
            if( ( 2 * C ) < B ){
                price = 2 * C * Y;
            }else{
                price = ( 2 * C * X ) + ( Y - X ) * B;
            }
        }
    }else{
        price = A * X + B * Y;
    }

    printf("%lld\n",price);

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int N; // ドーナツの種類
int X; // お菓子の素

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

	int use = 0; // 使ったお菓子の素
	int ret = 0; // 作った数
	int min = 9000000; // 最も素材の使用量が少ない

	vector<int> m(N); // 各ドーナツを作るのに必要な素材の量

	for (int i = 0; i < N; i++) {
		cin >> m[i];
		use += m[i];
		ret++;
		if (min > m[i]) min = m[i]; // 最小値更新
	}

	ret += (X - use) / min;

	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N = int(readline())
A = np.array(readline().split(), np.int64)

mod = 10**9+7
ans = 0
for i in range(64):
	B = (A>>i)&1
	x = np.count_nonzero(B)
	y = N - x
	x *= y

	for _ in range(i):
		x *= 2
		x %= mod
	ans += x
	ans %= mod
print(ans)

Measured memory_bytes: 36992
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

func init() {
	sc.Split(bufio.ScanWords)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	x, n := scanInt(), scanInt()
	xm := make(map[int]bool)
	for i := 0; i < n; i++ {
		p := scanInt()
		xm[p] = true
	}

	d := 10000
	var ans int
	for i := -100; i <= 200; i++ {
		if xm[i] {
			continue
		}
		if abs(x-i) < d {
			d = abs(x - i)
			ans = i
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1772
while 1:
  m,f,r = map(int,input().split())
  p = m + f 
  if m == f == r == -1:
    break
  if m == -1 or f == -1:
    print("F")
  elif p >= 80:
    print("A")
  elif 65 <= p < 80:
    print("B")
  elif 50 <= p < 65:
    print("C")
  elif 30 <= p < 50:
    if r >= 50:
      print("C")
    else:
      print("D")
  elif p < 30:
    print("F")
  else:
    pass


Measured memory_bytes: 5596
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

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

/*-------------------------------------------*/

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

    ll N, M;
    cin >> N >> M;
    string s;
    cin >> s;
    vector<vector<int>> G(N);
    vector<int> cntA(N), cntB(N);

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
        (s[a] == 'A' ? cntA[b] : cntB[b])++;
        (s[b] == 'A' ? cntA[a] : cntB[a])++;
    }

    queue<int> que;
    rep(i, N) if(!cntA[i] || !cntB[i]) que.push(i);

    while(!que.empty()) {
        N--;
        int v = que.front();
        que.pop();
        vector<int> &vec = (s[v] == 'A' ? cntA : cntB);
        for(int u : G[v]) {
            if(!cntA[u] || !cntB[u]) continue;
            if(--vec[u] == 0) que.push(u);
        }
    }

    cout << (N ? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 12240
#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	//カードの山
	string cards;

	//シャッフル回数
	int shuffle_num;

	//下から取り出すカードの枚数
	int h;

	while(1)
	{
		//カードの山を入力
		cin >> cards;

		if(cards == "-") break;

		//シャッフル回数を入力
		cin >> shuffle_num;

		for(int i = 0; i < shuffle_num; i++)
		{
			//取り出すカードの枚数を入力
			cin >> h;

			string tmp;

			//先頭から取り出すカードの文字列を取得
			tmp = cards.substr(0, h);

			//取り出したカードは先頭から削除
			cards.erase(0, h);

			//先頭から取り出したカードの文字列を末尾に加える
			cards = cards + tmp;
		}

		cout << cards << endl;
		cards = "";
	}
	return 0;
}



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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

int main() {
    ll N,H;
    cin >> N >> H;
    vector<ll> A,B;

    rep(i,N) {
        ll a,b;
        cin >> a >> b;
        A.push_back(a);
        B.push_back(b);
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end(),greater<ll>());
    ll a_max = A.back();
    ll t = 0;
    ll cnt = 0;
    rep(i,N) {
        if (B[i]>a_max) {
            t+=B[i];
            cnt++;
        }
        if (t>=H) {
            break;
        }
    }
    if (t>=H) {
        cout << cnt << endl;
    }
    else {
        while(1) {
            t+=a_max;
            cnt++;
            if (t>=H) {
                break;
            }
        }
        cout << cnt << endl;
    }

}


Measured memory_bytes: 2036
n,x,y=[int(j) for j in input().split()]
ans=[0]*n
for i in range(1,1+n):
    for j in range(i+1,1+n):
        t=min(j-i,abs(x-i)+abs(y-j)+1)
        ans[t]+=1
print('\n'.join(map(str,ans[1:])))

Measured memory_bytes: 3188
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

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



int main() {
    int K;
    string S;

    cin >> K >> S;

    if(S.size() <= K){
        cout << S << endl;
    }else{
        string ans="";
        for(int i=0; i<K; i++){
            ans += S[i];
        }
        cout << ans+"..." << endl;
    }
}


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

int main(){
  int n,k;
  string s;
  cin >> n >> s >> k;
  
  char point;
  point = s.at(k-1);
  
  for(int i; i<n; i++){
    if(s.at(i) != point){
      s.at(i) = '*';
    }
  }
  
  cout << s << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

const int INF = INT_MAX / 4;

int main(void) {
	int n, m, s, g1, g2;
	
	while (cin >> n >> m >> s >> g1 >> g2, n) {
		s--; g1--; g2--;

		VVI es(n, VI(n, INF));
		for (int i = 0; i < m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			a--; b--;
			es[a][b] = c;
		}
		for (int i = 0; i < n; i++) {
			es[i][i] = 0;
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					es[i][j] = min(es[i][j], es[i][k] + es[k][j]);
				}
			}
		}

		int ans = INF;
		for (int i = 0; i < n; i++) {
			ans = min(ans, es[s][i] + es[i][g1] + es[i][g2]);
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1260
#include<iostream>
#include<sstream>
#include<algorithm>
#include<numeric>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define mp make_pair
#define pb push_back
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

typedef int Weight;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
Weight minimum_steiner_tree(const vector<int>& T, const Matrix &g) {
  const int n = g.size();
  const int numT = T.size();
  if (numT <= 1) return 0;

  Matrix d(g); // all-pair shortest
  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        d[i][j] = min( d[i][j], d[i][k] + d[k][j] );

  Weight OPT[(1 << numT)][n];
  for (int S = 0; S < (1 << numT); ++S)
    for (int x = 0; x < n; ++x)
      OPT[S][x] = inf;

  for (int p = 0; p < numT; ++p) // trivial case
    for (int q = 0; q < n; ++q)
      OPT[1 << p][q] = d[T[p]][q];

  for (int S = 1; S < (1 << numT); ++S) { // DP step
    if (!(S & (S-1))) continue;
    for (int p = 0; p < n; ++p)
      for (int E = 0; E < S; ++E)
        if ((E | S) == S)
          OPT[S][p] = min( OPT[S][p], OPT[E][p] + OPT[S-E][p] );
    for (int p = 0; p < n; ++p)
      for (int q = 0; q < n; ++q)
        OPT[S][p] = min( OPT[S][p], OPT[S][q] + d[p][q] );
  }
  Weight ans = inf;
  for (int S = 0; S < (1 << numT); ++S)
    for (int q = 0; q < n; ++q)
      ans = min(ans, OPT[S][q] + OPT[((1 << numT)-1)-S][q]);
  return ans;
}
int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w;

int main()
{
  while(scanf("%d%d",&h,&w),h){
    Matrix m(h*w,Array(h*w,inf));
    vi heart;
    rep(i,h)rep(j,w){
      int t; scanf("%d",&t);
      if(t)heart.pb(i*w+j);
      rep(d,4){
	int ny=i+dy[d],nx=j+dx[d];
	if(ny<0||ny>=h||nx<0||nx>=w)continue;
	m[ny*w+nx][i*w+j]=m[i*w+j][ny*w+nx]=1;
      }
      m[i*w+j][i*w+j]=0;
    }
    int ans=minimum_steiner_tree(heart,m);
    printf("%d\n",h*w-ans-1);
  }
  return 0;
}

Measured memory_bytes: 1132
fn getline() -> String{
	let mut __ret=String::new();
	std::io::stdin().read_line(&mut __ret).ok();
	return __ret;
}

const MOD: i64 = 1000000007;

fn mpermu(a: i64, num: i64) -> i64 {
	match num {
    	0 => 1,
    	_ => a * mpermu(a - 1, num - 1) % MOD
    }
}

fn mpow(x: i64,  y: i64) -> i64 {
    match y {
        0 => 1,
        _ => (x.pow((y % 2) as u32) * mpow(x * x % MOD, y / 2)) % MOD
    }
}

fn main(){
	let s=getline();
	let a:Vec<_>=s.trim().split(' ').collect();
	let n:i64=a[0].parse().unwrap();
	let m:i64=a[1].parse().unwrap();
    
    let mut v: i64 = m;
    let mut r: i64 = 1;
    let mut div: i64 = 2;
    
    while div * div <= m {
   	  let mut rd = 0;

      while v % div == 0 {
      	v /= div;
        rd+=1;
      }
      r = (r * mpermu((rd + n - 1) % MOD, rd) % MOD) * mpow(mpermu(rd, rd), MOD - 2) % MOD;
      div+=1;
    }
    if v > 1 {
    	r = (r * (1 + n - 1)) % MOD;
    }
    
	println!("{}", r);

}

Measured memory_bytes: 4352
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

void solveSingleCase(int caseNo)
{
    int N;
    cin >> N;
    VEC(int) A(N), B(N), C(N);
    READVEC(A);
    READVEC(B);
    READVEC(C);

    sort(ALL(A));
    sort(ALL(B));
    sort(ALL(C));

    lint ret = 0;
    int a = 0, c = 0;
    FOR(i, 0, N) {
        while (a < N && A[a] < B[i])
            a++;
        while (c < N && C[c] <= B[i])
            c++;
        ret += a * 1LL * (N - c);
    }

    cout << ret << endl;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int r=1,b=0,data;
	char s[3];
	cin>>s;
	for(int i=0;i<3;i++)
	{
		if(s[i]=='x')
		{
			r=1;
		}
		else
		{
			b++;
		}
	}		
	
	data = (700*r)+(100*b);

	cout<<data<<endl;		
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		int[] a = sc.nextIntArray(n);

		int[] count = new int[100001];
		for (int i = 0; i < n; i++) {
			for (int j = Math.max(0, a[i] - 1); j <= a[i] + 1; j++) {
				count[j]++;
			}
		}

		Arrays.sort(count);

		out.println(count[count.length - 1]);
		out.flush();
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) return false;
		}
		return true;
	}

	private byte readByte() {
		if (hasNextByte()) return buffer[ptr++];
		return -1;
	}

	private boolean isPrintableChar(byte c) {
		return '!' <= c && c <= '~';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		byte b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public int nextInt() {
		if (!hasNext()) throw new NoSuchElementException();
		int n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) throw new NumberFormatException();
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}
}

Measured memory_bytes: 23380
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		br.close();

		int n = s.length();
		long[] dp0 = new long[n + 1];
		long[] dp1 = new long[n + 1];
		dp1[0] = 1;
		for (int i = n - 1; i >= 0; i--) {
			int j = n - 1 - i;
			int c = s.charAt(i) - '0';
			dp0[j + 1] = Math.min(dp0[j] + c, dp1[j] + c + 1);
			dp1[j + 1] = Math.min(dp0[j] + 10 - c, dp1[j] + 9 - c);
		}
		long ans = Math.min(dp0[n], dp1[n] + 1);
		System.out.println(ans);
	}
}


Measured memory_bytes: 47828
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

ll dp[200010][50];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, T;
    cin >> N >> T;
    vector<plglg> azero;
    vector<plglg> apl;
    REP(i, 0, N) {
        ll a, b;
        cin >> a >> b;
        if (a == 0) {
            azero.push_back(plglg(a, b));
        } else {
            apl.push_back(plglg(a, b));
        }
    }
    sort(azero.begin(), azero.end());
    sort(apl.begin(), apl.end(), [](plglg a, plglg b) {
        return a.first * (b.second + 1) > b.first * (a.second + 1);
    });
    fill(dp[0], dp[0] + 50, inf);
    dp[0][0] = 0;
    REP(i, 0, apl.size()) {
        ll a = apl[i].first;
        ll b = apl[i].second;
        REP(j, 0, 50) {
            dp[i + 1][j] = dp[i][j];
        }
        REP(j, 1, 50) {
            ll now = dp[i][j - 1];
            if (now > T) {
                break;
            }
            ll num = now + 1 + (a * (now + 1) + b);
            if (num <= T) {
                dp[i + 1][j] = min(dp[i + 1][j], num);
            } else {
                break;
            }
        }
    }
    ll ans = 0;
    REP(i, 0, 50) {
        ll time = dp[apl.size()][i];
        if (time > T) {
            break;
        }
        ll num = i;
        REP(j, 0, azero.size()) {
            ll b = azero[j].second;
            if (time + 1 + b <= T) {
                time += 1 + b;
                num++;
            } else {
                break;
            }
        }
        ans = max(ans, num);
    }
    // REP(i, 0, azero.size()) {
    //     cout << azero[i].first << " " << azero[i].second << endl;
    // }
    // cout << "aaa" << endl;
    // REP(i, 0, apl.size()) {
    //     cout << apl[i].first << " " << apl[i].second << endl;
    // }
    cout << ans << endl;
}


Measured memory_bytes: 82284
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<queue>

#define INF 1e9

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using ppi = pair<pii, int>;

int h, w;
vvi field(30, vi(30));
vi c_costs(4);
int f_dir[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
bool is_in_field(int y, int x, int h, int w){
  return (y >= 0 && y < h && x >= 0 && x < w);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  while(cin >> w >> h && h){
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        cin >> field[i][j];
      }
    }
    for(int &i: c_costs) cin >> i;
    vvvi cost(30, vvi(30, vi(4, INF)));
    cost[0][0][1] = 0;
    queue<ppi> q;
    q.push({{0, 0}, 1});
    auto ex = [](int i, int j){
      if(j == i) return 0;
      if(j == (i+1)%4) return 1;
      if(j == (i+2)%4) return 2;
      return 3;
    };
    while(!q.empty()){
      ppi now = q.front(); q.pop();
      int now_y = now.first.first, now_x = now.first.second, now_dir = now.second;
      for(int j = 0; j < 4; j++){
        int nx_y = now_y+f_dir[0][j], nx_x = now_x+f_dir[1][j], nx_dir = j;
        if(!is_in_field(nx_y, nx_x, h, w)) continue;
        int ex_dir = ex(now_dir, nx_dir);
        int ex_cost = (field[now_y][now_x] == ex_dir) ? 0 : c_costs[ex_dir];
        if(cost[nx_y][nx_x][nx_dir] > cost[now_y][now_x][now_dir] + ex_cost){
          q.push({{nx_y, nx_x}, nx_dir});
          cost[nx_y][nx_x][nx_dir] = cost[now_y][now_x][now_dir] + ex_cost;
        }
      }
    }
    cout << *min_element(cost[h-1][w-1].begin(), cost[h-1][w-1].end()) << endl;
  }
  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}



Measured memory_bytes: 3236
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>
#include<iomanip>
 
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mp(a, b) make_pair(a, b)
#define mt(a,b,c) make_tuple(a,b,c)
#define rank qwertyuio
#define next dfghjk
#define plus fsghsf
#define minus ytryr
#define pb push_back
#define debug(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
 
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
 
const int N = (int)1e5+7;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int mod = (int)1e9 + 7;

const int mod1 = (int)1e9 + 9;
const int mod2 = 998244353;
const int mod3 = (int)1e6+3;
const ld eps = 1e-12;
const double pi = atan2(0, -1);
const int ABC = 26;
 
 
ll binary_search(vector<ll> arr,ll val,ll l,ll r){
    ll m=l+(r-l)/2;
    if(l>=r){
        return l;
    }
    if(val<arr[m]){
        return binary_search(arr,val,l,m);
    }
    else{
        return binary_search(arr,val,m+1,r);
    }
}//return position less than
ll binary_search2(vector<ll> arr,ll val,ll l,ll r){
    ll m=l+(r-l)/2;
    if(l>=r){
        return l;
    }
    if(val<=arr[m]){//changed here
        return binary_search2(arr,val,l,m);
    }
    else{
        return binary_search2(arr,val,m+1,r);
    }
}//return position less than or equal


int fact[N];
 
int add(int a, int b) {
	return (a + b) % mod;
}
 
int mul(int a, int b) {
	return (a * b) % mod;
}
 
int binpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
 
int divv(int a, int b) {
	return mul(a, binpow(b, mod - 2));
}
 
int getC(int n, int k) {
	return divv(fact[n], mul(fact[n - k], fact[k]));
}
 
void init() {
	fact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = mul(i, fact[i - 1]);
	}
}



int main()
{   ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
	cin>>n;
	int a[n];
	int i;
	int min=(int)1e9;
	int ans=0;
	rep(i,0,n){
		cin>>a[i];
		if(a[i]<=min){
			ans++;
			min=a[i];
		}
	}
	cout<<ans;

    return 0;
             
    
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{


    ll i,j,k,a,b,c,n,t,m,d;
    vector<ll> v,s;
    string st,et;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a;
        v.push_back(a);
    }
    b = 0;
    a = 0;
    c = 0;
    for(i=0; i<n; i++)
    {
        if(i%2==0)
        {
            b = b+v[i];
            if(b<=0)
            {
                b = b-v[i];
                d = abs(b-1);
                d = abs(v[i]-d);
                a = a+d;
                b = 1;
            }
        }
        else if(i%2==1)
        {
            b = b+v[i];
            if(b>=0)
            {
                b = b-v[i];
                d = abs(b+1);
                d = abs(v[i]+d);
                a = a+d;
                b = -1;
            }
        }
    }
    b = 0;
    for(i=0; i<n; i++)
    {
        if(i%2==1)
        {
            b = b+v[i];
            if(b<=0)
            {
                b = b-v[i];
                d = abs(b-1);
                d = abs(v[i]-d);
                c = c+d;
                b = 1;
            }
        }
        else if(i%2==0)
        {
            b = b+v[i];
            if(b>=0)
            {
                b = b-v[i];
                d = abs(b+1);
                d = abs(v[i]+d);
                c = c+d;
                b = -1;
            }
        }
    }
    cout<<min(a,c)<<endl;
}


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

int main(int argc, char const *argv[])
{
    int N;
    cin >> N;

    int ans;
    if (N % 2 == 1)
    {
        ans = N / 2 + 1;
    }
    else
    {
        ans = N / 2;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // include all standard C++ libraries

using namespace std;

// Loops
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define _rrep(i,n) rrepi(i,n,0)
#define rrepi(i,a,b) for(int i=int(a)-1;i>=int(b);--i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(xi, x) for (auto&& xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)


// typedef
using ll = long long;
template <class T> using vec = vector<T>;
using vi   = vector<int>;
using vvi  = vector<vi>;
using vvvi = vector<vvi>;
using pii  = pair<int, int>;


// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second


// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase( unique(all(v)), v.end() )
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<class T> pair<T, size_t> max(vector<T> &x){ auto it = max_element(all(x)); return mp(*it, it-x.begin()); }
template<class T> pair<T, size_t> min(vector<T> &x){ auto it = min_element(all(x)); return mp(*it, it-x.begin()); }

template<class T> inline bool chmax(T &maxval, const T &newval) { if (maxval<newval) { maxval=newval; return 1; } return 0; }
template<class T> inline bool chmin(T &minval, const T &newval) { if (minval>newval) { minval=newval; return 1; } return 0; }

// Utilities
// Grid world utilities
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
#define inside(H,W,y,x) 0<=(x) && (x)<(W) && 0<=(y) && (y)<(H)

inline int in() {int x; cin >> x; return x;} // read int from cin
inline  ll IN() {ll x; cin >> x; return x;}  // read ll from cin



// Debug
#ifdef LOCAL
  #include "dump.hpp"
  #define debug(x) cerr << #x << ": " << x << '\n'
#else
  #define dump(...)
  #define debug(x)
#endif

// Paste snippets here!!

// 

int main(){
  cin.tie(0); ios::sync_with_stdio(false);    // Magic for faster cin
  ll H, A;
  cin >> H >> A;
  cout << H/A + ((H%A)?1:0) << endl;
  return 0;
}


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

#define f(i,x,y)			for(int i=x; i<y; i++)
#define ll 					long long 
#define mp 					make_pair
#define F 					first
#define S 					second
#define N 					100005
#define M 	 				1000000007

int main()
{
	int m,n;
	cin>>m>>n;
	char a[m][n];

	f(i,0,m)
		f(j,0,n)
			cin>>a[i][j];

	int dp[m][n];

	if(a[0][0]=='.')
		dp[0][0] = 1;
	else
		dp[0][0] = 0;

	f(j,1,n)
	{
		if(a[0][j]=='#')
			dp[0][j] = 0;
		else
		dp[0][j] = dp[0][j-1];
	}
	f(i,1,m)
	{
		if(a[i][0]=='#')
			dp[i][0] = 0;
		else
		dp[i][0] = dp[i-1][0];
	}

	f(i,1,m)
		f(j,1,n)
		{
			if(a[i][j]=='#')
				dp[i][j] = 0;
			else
				dp[i][j] = (dp[i-1][j]+dp[i][j-1])%M;
		}

// f(i,0,m)
// {
// 	f(j,0,n)
// 		cout<<dp[i][j]<<" ";
// 	cout<<endl;
// }
		
	cout<<dp[m-1][n-1]%M;
	
	return 0;
}

Measured memory_bytes: 5120
use std::collections::VecDeque;

const INF: usize = 1e9 as usize;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let distance: usize = sc.read();
    let n: usize = sc.read();
    let mut m = vec![];
    for _ in 0..n {
        let x: usize = sc.read();
        m.push(x);
    }
    m.push(distance + 1);

    let first = m[0];

    let mut ds = vec![];
    for i in 1..m.len() {
        let d = m[i] - m[i - 1] - 1;
        ds.push(d);
    }

    ds.sort();

    let mut costs = vec![0; distance + 1];
    let mut seg = 0;
    for i in (0..distance).rev() {
        while let Some(d) = ds.pop() {
            if d < i {
                ds.push(d);
                break;
            } else {
                seg += 1;
            }
        }
        costs[i] = costs[i + 1] + seg;
    }

    let q: usize = sc.read();
    let mut l = vec![];
    for i in 0..q {
        let x = sc.read::<usize>();
        l.push((x, i));
    }
    l.sort();

    let mut ans: Vec<i64> = vec![0; q];
    let mut cur = distance;
    for (l, i) in l.into_iter() {
        if l < first - 1 {
            ans[i] = -1;
            continue;
        }
        let l = l - (first - 1);
        while cur > 1 && costs[cur - 1] <= l {
            cur -= 1;
        }
        if cur == 1 && costs[1] > l {
            ans[i] = -1;
            continue;
        }
        ans[i] = cur as i64;
    }

    for ans in ans.into_iter() {
        sc.write(format!("{}\n", ans));
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}



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

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

bool is_prime(int x) {
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int x;
    cin >> x;
    while (true) {
        if (is_prime(x))
            return cout << x, 0;
        x++;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <functional>
#include <utility>
#include <tuple>
#include <numeric>
#include <queue>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <regex>
#include <stack>
#include <limits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	cout << 1 - n << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 998244353;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    ll n;
    cin >> n;
    ll ans = 0LL;
    for (ll i = 1LL; i <= n; ++i) {
        ll del = n / i;
        ans += (del * (del + 1)) / 2 * i;
    }
    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 3628
import java.util.*


fun calc141D(N: Int, M: Int, A: List<Int>): Long {
    val queue= PriorityQueue(A.map { -it })

    for (i in 1..M){
        val m = queue.poll()
        queue.add(m/2)
    }
    return -queue.map { it.toLong() }.sum()
}


fun main(args: Array<String>) {
    val (N, M) = readLine()!!.split(" ").map { it.toInt() }
    val A = readLine()!!.split(" ").map { it.toInt() }
    val ans = calc141D(N, M, A)
    println(ans)
}


Measured memory_bytes: 74504