akhauriyash/Code-Regression huggingface dataset:
// abc094_b
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <unordered_map>
#include <utility>
#include <vector>
#define loop(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) loop(i, 0, a)
#define FOR(i, a) for (auto i : a)
#define pb push_back
#define all(in) in.begin(), in.end()
#define shosu(x) fixed << setprecision(x)
#define show1d(v)                                                              \
  rep(i, v.size()) cout << " " << v[i];                                        \
  cout << endl << endl;
#define show2d(v)                                                              \
  rep(i, v.size()) {                                                           \
    rep(j, v[i].size()) cout << " " << v[i][j];                                \
    cout << endl;                                                              \
  }                                                                            \
  cout << endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def, Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def, pii> pip;
typedef vector<pip> vip;
template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
template <class T> bool contain(const std::string &s, const T &v) {
  return s.find(v) != std::string::npos;
}
int main(int argc, char *argv[]) {
  int n, m, x, a, cnt = 0,right=0,left=0;
  cin >> n >> m >> x;
  rep(i, m) {
    cin>>a;
    if(x<a)right++;
    else left++;
  }
  cnt=min(right,left);
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
#include<bitset>
#include<stack>
#include<time.h>



#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define ALL(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define getmid ((l+r)>>1)
#define mst(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) x&(-x)
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
#ifdef local
#define dbg(args...) cout << #args << " -> ", err(args);
void err(){ cout << endl; }
template<typename T, typename... Args>
void err(T a, Args... args){ cout << a << ' '; err(args...); }
#else
#define dbg(args...)
#endif // local

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <double, double> pdd;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const long double eps=1e-8;
const int mod=1e9+7;
const int maxn=3e5+100;
const int N=2e5+100;
const int M=500+10;
const ll mm=(1LL<<32);

template <class T>
inline void read(T &x)
{
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= c == '-';
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10)
        ++len;
    for (; len; --len, x %= y, y /= 10)
        putchar(x / y + 48);
}
ll qpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

vector<int>path[200100];
string s[200100];
struct Trie {
  int nex[1000100][26], cnt;
  int exist[1000100];
  void insert(string s, int idx) {
    int p = 0,len=s.size();
    for (int i = 0; i < len; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;
      p = nex[p][c];
      path[idx].push_back(p);
    }
    exist[p]++;
  }
}trie;
int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
#endif // local
    IOS;cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>s[i];reverse(s[i].begin(),s[i].end());
        trie.insert(s[i],i);
    }
    set<char>suf;
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        suf.clear();
        for(int j=s[i].size()-1;j>=0;--j)
        {
            int node=path[i][j];
            for(char c:suf)
                ans+=trie.exist[trie.nex[node][c-'a']];
            suf.insert(s[i][j]);
        }
        int node=0;
        for(char c:suf) ans+=trie.exist[trie.nex[node][c-'a']];
    }
    cout<<ans-n<<endl;
    return 0;
}



Measured memory_bytes: 125760
import heapq


def solve(a):
    pq = list()
    heapq.heapify(pq)
    delta = 0
    k = 0
    for i in range(len(a)):
        for x in a[i]:
            if k <= i:
                delta += x
                heapq.heappush(pq, x)
                k += 1
            elif pq:
                delta += x
                heapq.heappush(pq, x)
                delta -= heapq.heappop(pq)
    return delta


t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    left = [list() for i in range(n)]
    right = [list() for i in range(n)]
    ans = 0
    for i in range(n):
        k, l, r = map(int, input().split())
        if l > r:
            left[k - 1].append(l - r)
        elif l < r:
            if k < n:
                right[n - 1 - k].append(r - l)
        ans += min(l, r)
    print(ans + solve(left) + solve(right))

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

int main()
{
    int y[7];     //サイコロ
    int x[6][6] = { {0,3,5,2,4,0},{4,0,1,6,0,3},{2,6,0,0,1,5},{5,1,0,0,6,2},{3,0,6,1,0,4},{0,4,2,5,3,0} };
    int front;
    int back;
    int c;
    int d;
    int q;        //質問数
    int i;
    int j;
    cin >> y[1] >> y[2] >> y[3] >> y[4] >> y[5] >> y[6];
    cin >> q;
    for (i = 0; i < q; i++) {
        cin >> front >> back;
        for (j =1; j <= 6; j++) {
            if (front == y[j]) {
                c = j;
            }
            if (back == y[j]) {
                d = j;
            }
        }
        cout << y[x[c - 1][d - 1]] << endl;
    }
    return 0;
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

string S;
vector<string>vs;

void dfs(string s,char c){
    if(c=='a'){
        vs.pb(s);
        return;
    }

    bool expre=false,exaft=false;
    rep(i,S.size()){
        if(S[i]==c-1){
            S[i]=c;
            dfs(S,c-1);
            S[i]=c-1;
            expre=true;
        }
        if(S[i]==c){
            exaft=true;
            if(!expre)return;
            break;
        }
    }

    if(!exaft)dfs(S,c-1);
}

void solve(){
    vs.clear();
    dfs(S,'z');
    sort(all(vs));vs.erase(unique(all(vs)),vs.end());
    cout<<vs.size()<<endl;
    if(vs.size()<=10)rep(i,vs.size())cout<<vs[i]<<endl;
    else{
        rep(i,5)cout<<vs[i]<<endl;
        for(int i=vs.size()-5;i<vs.size();i++)cout<<vs[i]<<endl;
    }
}

signed main(){
    while(cin>>S,S!="#")solve();
}

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


int main() {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    rep(i, b) cout << a;
    cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,dp[1050][1050];
char gr[1050][1050];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>gr[i][j];
            if(i==1&&j==1)continue;
            if(gr[i][j]=='.')
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                dp[i][j]%=mod;
            }
        }
    }
    cout<<dp[n][m];
}


Measured memory_bytes: 9472
# coding: utf-8
# Your code here!
n,y = map(int,input().split())
total = 0
for i in range(n + 1):
    for j in range(n - i + 1):
        
        if i * 10000 + j * 5000 + (n-i-j) * 1000 == y:
            print(i ,j ,n-i-j)
            exit()
        
print(-1,-1,-1)

       
        


Measured memory_bytes: 2940
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
string s;
vvi in;
vi w;
int n,m,out;
int a,b;
vi f(){
	int e=w[b];
	a++;
	vi ss(4),t(4);
	if(s[a]=='('){b++;ss=f();}
	else ss=in[s[a]-'1'];
	a++;
	if(s[a]=='('){b++;t=f();}
	else t=in[s[a]-'1'];
	vi re(4);
	rep(i,4)if(e==0)re[i]=(ss[i]&&t[i]);
	else if(e==1)re[i]=(ss[i]||t[i]);
	else if(e==2)re[i]=(ss[i]^t[i]);
	a++;
	return re;
}
int main(){
	while(getline(cin,s),s!="END"){
		rep(i,s.size())if(s[i]==' '){
			s.erase(s.begin()+i);
			i--;
		}
		m=out=0;
		rep(i,s.size())if(s[i]=='(')m++;
		cin>>n;
		in=vvi(n,vi(4));
		w=vi(m);
		rep(i,n)rep(j,4)cin>>in[i][j];
		
		int q=pow(3,m);
		rep(i,q){
			int t=i;
			rep(j,m){
				w[j]=t%3;
				t/=3;
			}
			a=b=0;
			vi tmp=f();
			sort(all(tmp));
			if(tmp[0]==1)out++;
		}
		cout<<out<<endl;
		getline(cin,s);
	}
}

Measured memory_bytes: 1280
x, y, z, k = gets.to_s.split.map{|i|i.to_i}

A = gets.to_s.split.map{|i|i.to_i}.sort.reverse
B = gets.to_s.split.map{|i|i.to_i}.sort.reverse
C = gets.to_s.split.map{|i|i.to_i}.sort.reverse

t = []

i = 0
A.each_with_index do |a,i|
  B.each_with_index do |b,j|
    break if (i+1) * (j+1) > k
    t.push a + b
  end
end

t = t.sort.reverse[0,k]

v = []
C.each_with_index do |c,i|
  t.each_with_index do |u,j|
    break if (i+1) * (j+1) > k
    v.push( c + u )
  end
end

puts v.sort.reverse[0, k]

Measured memory_bytes: 3036
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)
cur = 0
for i in range(10**6):
    cur = a[cur] - 1
    if cur == 1:
        print(i+1)
        break
else:
    print(-1)

Measured memory_bytes: 43740
#define _GLIBCXX_DEBUG
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>//"geometry.cpp"
#include<iomanip>//"cout<<fixed<<setprecision(n)<<sth<<endl;"
#include<queue>
#include<string>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<algorithm>
#include<functional>//"greater<T>" Ex. sort(a,a+n,greater<int>());
#include<cmath>//"abs", "sqrt"
using namespace std;
#define pb push_back
#define fi first
#define sc second
#define mp make_pair
#define is insert	//tentative
typedef map<char,int> mci;

const int PLUS=1024,MINUS=1025,TIMES=1026,LEFT=1027,RIGHT=1028,ERROR=1029;

int calc(vector<int> v){
	if(v.size()==1){
		if(v[0]>=PLUS){
			return ERROR;
		}
		return v[0];
	}
	if(v.size()%2==0){
		return ERROR;
	}
	int i;
	for(i=0;i<v.size();++i){
		if(v[i]==TIMES){
			if(i%2==0){
				return ERROR;
			}
			break;
		}
	}
	if(i<v.size()){
		if(v[i-1]>=PLUS||v[i+1]>=PLUS){
			return ERROR;
		}
		v[i-1]*=v[i+1];
		if(v[i-1]>=PLUS){
			return ERROR;
		}
		for(;i<v.size()-2;++i){
			v[i]=v[i+2];
		}
		v.resize(v.size()-2);
		return calc(v);
	}
	if(v[0]>=PLUS){
		return ERROR;
	}
	for(i=1;i<v.size();i+=2){
		if(v[i]<PLUS||v[i]>=TIMES||v[i+1]>=PLUS){
			return ERROR;
		}
		if(v[i]==PLUS){
			v[0]+=v[i+1];
			if(v[0]>=PLUS){
				return ERROR;
			}
		}else{
			v[0]-=v[i+1];
			if(v[0]<0){
				return ERROR;
			}
		}
	}
	return v[0];
}

int main(){
	string s;
	vector<int> x;
	int k=1,ans=-1;
	char c[7];
	c[0]='0';
	c[1]='1';
	c[2]='+';
	c[3]='-';
	c[4]='*';
	c[5]='(';
	c[6]=')';
	mci m;
	m.is(mp('+',PLUS));
	m.is(mp('-',MINUS));
	m.is(mp('*',TIMES));
	m.is(mp('(',LEFT));
	m.is(mp(')',RIGHT));
	cin>>s;
	for(int i=0;i<s.size();++i){
		if(s[i]=='.'){
			x.pb(i);
			k*=7;
		}
	}
	for(--k;k>=0;--k){
		int j=k;
		for(int i=0;i<x.size();++i){
			s[x[i]]=c[j%7];
			j/=7;
		}
		int a=0;
		vector<int> v,l;
		for(int i=0;i<s.size();++i){
			if(s[i]=='0'||s[i]=='1'){
				a*=2;
				a+=(s[i]-'0');
				if(i==s.size()-1){
					v.pb(a);
				}
			}else{
				if(i-1>=0&&(s[i-1]=='0'||s[i-1]=='1')){
					v.pb(a);
				}
				a=0;
				v.pb(m[s[i]]);
				if(m[s[i]]==LEFT){
					l.pb(v.size()-1);
				}
			}
		}
		while(!l.empty()){
			for(j=l[l.size()-1]+1;j<v.size();++j){
				if(v[j]==RIGHT){
					break;
				}
			}
			if(j==v.size()){
				a=ERROR;
				break;
			}
			vector<int> w(v.begin()+l[l.size()-1]+1,v.begin()+j);
			if(w.size()==1){
				a=ERROR;
				break;
			}
			v[l[l.size()-1]]=calc(w);
			if(v[l[l.size()-1]]==ERROR){
				a=ERROR;
				break;
			}
			for(int i=l[l.size()-1]+1;i<v.size()-w.size()-1;++i){
				v[i]=v[i+w.size()+1];
			}
			v.resize(v.size()-w.size()-1);
			l.pop_back();
		}
		if(a!=ERROR){
			a=calc(v);
			if(a!=ERROR){
				ans=max(ans,a);
			}else{
			}
		}else{
		}
	}
	if(ans>=0){
		cout<<ans<<endl;
	}else{
		cout<<-1<<endl;
	}
}

Measured memory_bytes: 3244
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

  public static void main(String[] args) throws IOException {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int q = Integer.parseInt(br.readLine());
      List<String> vector = new ArrayList<>();

      String[] query;
      int op;
      Integer num;
      for ( int i=0; i<q; i++ ){
        query = br.readLine().split(" ");

        switch(query[0]) {
          case "0" :
            vector.add(query[1]);
            break;
          case "1" :
            System.out.println( vector.get(Integer.parseInt(query[1])) );
            break;
          case "2" :
            vector.remove(vector.size()-1);
            break;
          default:
        }
      }
    }
  }
}


Measured memory_bytes: 85948
N, Q = [int(i) for i in input().split()]
S = input()
tdList = reversed([input().split() for _ in range(Q)])

l, r = 0, N - 1
lList, rList = [], []
for td in tdList:
    if td[0] == S[l] and td[1] == "L":
        l += 1
    elif td[0] == S[r] and td[1] == "R":
        r -= 1
    if l != 0 and S[l - 1] == td[0] and td[1] == "R":
        l -= 1
    if r != N - 1 and S[r + 1] == td[0] and td[1] == "L":
        r += 1
    if l > N - 1 or r < 0:
        break

ans = 0
if r >= l:
    ans = r - l + 1

print(ans)



Measured memory_bytes: 39348
#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

int main(){
    string in;
    getline(cin,in);
    rep(i,in.size())
        if(string(",.").find(in[i])!=string::npos)
            in[i]=' ';
    vector<string> ans;
    stringstream ss(in);
    string buf;
    while(ss>>buf){
        if(3<=buf.size() && buf.size() <=6)
            ans.push_back(buf);
    }
    rep(i,ans.size()){
        cout<<ans[i]<<(i!=ans.size()-1 ? ' ' : '\n');
    }
}

Measured memory_bytes: 1204
<?php
$answer = 0;

fscanf(STDIN, "%d", $N);
$array = array('M' => 0, 'A' => 0, 'R' => 0, 'C' => 0, 'H' => 0);
$keys = array_keys($array);
for ($i = 0; $i < $N; $i++) {
    fscanf(STDIN, "%s", $S);
    $arrS = str_split($S);
    if (in_array($arrS[0], $keys)) {
        $array[$arrS[0]]++;
    }
}
$sum = array_sum($array);
for ($i = 0; $i < 5; $i++) {
    for ($j = 0; $j < 5; $j++) {
        if ($i == $j) continue;
        $rest = $sum - $array[$keys[$i]] - $array[$keys[$j]];
        $answer += $array[$keys[$i]] * $array[$keys[$j]] * $rest;
    }
}
echo $answer / 6 . PHP_EOL;

Measured memory_bytes: 4856
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

int n;
string s[512];

bool full_col( int c ){
  REP( i , n ){
    if( s[i][c] == '.' ){
      return false;
    }
  }
  return true;
}

bool full_row( int r ){
  REP( i , n ){
    if( s[r][i] == '.' ){
      return false;
    }
  }
  return true;
}

int main(){

  n = in();
  REP( i , n ){
    s[i] = stin();
  }

  bool ok = false;
  REP( i , n ){
    REP( j , n ){
      if( s[i][j] == '#' ){
        ok = true;
      }
    }
  }

  if( not ok ){
    cout << -1 << endl;
    return 0;
  }
  
  int cnt = 0;
  REP( i , n ){
    if( full_col( i ) ){
      cnt++;
    }
  }

  int ans = INF;
  REP( i , n ){
    bool f = false;
    REP( j , n ){
      if( s[j][i] == '#' ){
        f = true;
        break;
      }
    }
    int res = 0;
    if( not f ){
      res++;
    }
    REP( j , n ){
      if( s[i][j] == '.' ){
        res++;
      }
    }
    chmin( ans , res + n - cnt );
  }

  assert( ans != INF );
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 512
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 1_000_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "a", long, "b");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, m;
    scan(n, m);
    auto drink = new Pair[](n);
    foreach (i; iota(n))
    {
        long a, b;
        scan(a, b);
        drink[i] = Pair(a, b);
    }
    drink.sort!"a.a < b.a"();
    long ans, cnt;
    foreach (e; drink)
    {
        if(cnt + e.b <= m)
        {
            cnt += e.b;
            ans += e.a * e.b;
        }
        else
        {
            ans += e.a * (m - cnt);
            break;
        }
    }
    ans.writeln();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 12576
#include <iostream>
#include <string>
typedef long long ll;
using namespace std;

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

    int index = 0;
    int count = 0;
    string x = "ABC";
    while (index <= n)
    {
        index = S.find(x);
        if (index == -1)
        {
            break;
        }
        else
        {
            count++;
            index += 3;
            S = S.substr(index);
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int n, i, a[200002], ans=1, flag=0;
	scanf("%d %d %d", &n, &a[0], &a[1]);
	if (a[0] < a[1])flag = 1;//単調増加
	if (a[0] > a[1])flag = -1;//単調減少

	for (i = 2; i < n; i++) {
		scanf("%d", &a[i]);
		if (a[i - 1] > a[i]) {
			if (flag == 0) {
				flag = -1;
			}
			else if (flag == 1) {
				flag = 0;
				ans++;
			}

		}
		else if (a[i - 1] < a[i]) {
			if (flag == 0) {
				flag = 1;
			}
			else if (flag == -1) {
				flag = 0;
				ans++;
			}
		}
	}
		printf("%d", ans);
	}

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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RFOR(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); --i)
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define RREP(i, n) for (int i = (int)(n - 1); i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(a) ((int)(a).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define SQ(x) ((x) * (x))

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

struct P {
    double x, y, z, r;
};

struct Edge {
    int a, b;
    double cost;

    bool operator<(const Edge& o) const {
        return cost < o.cost;
    }
};

struct UnionFind {
    vector<int> v;
    UnionFind(int size) : v(size, -1) { }
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (v[y] < v[x]) swap(x, y);
            v[x] += v[y]; v[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
    int size(int x) { return -v[find(x)]; }
};

struct Graph {
    int n;
    vector<Edge> es;

    double kruskal() {
        UnionFind uf(n);
        SORT(es);

        double total = 0;
        REP(ei, es.size()) {
            Edge& e = es[ei];
            if (!uf.same(e.a, e.b)) {
                uf.unite(e.a, e.b);
                total += e.cost;
            }
        }
        return total;
    }
};

int main() {
    int N;
    while (cin >> N, N) {
        vector<P> p(N);
        Graph g;
        g.n = N;
        REP(i, N) {
            cin >> p[i].x >> p[i].y >> p[i].z >> p[i].r;
        }
        REP(i, N) {
            FOR(j, i+1, N) {
                double d = sqrt(SQ(p[i].x - p[j].x) + SQ(p[i].y - p[j].y) + SQ(p[i].z - p[j].z)) - p[i].r - p[j].r;
                if (d < 0) d = 0;
                g.es.push_back({i, j, d});
            }
        }
        printf("%.3f\n", g.kruskal());
    }
}

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

using namespace std;

class Dice{
  public:
    int a[6], tmp, i;

    Dice(int input[6]){
      for (i = 0; i < 6; i++) {
        a[i] = input[i];
      }
    }

    void e() {
      tmp = a[2]; a[2] = a[0]; a[0] = a[3]; a[3] = a[5]; a[5] = tmp;
    }

    void n() {
      tmp = a[0]; a[0] = a[1]; a[1] = a[5]; a[5] = a[4]; a[4] = tmp;
    }

    void w() {
      tmp = a[0]; a[0] = a[2]; a[2] = a[5]; a[5] = a[3]; a[3] = tmp;
    }

    void s() {
      tmp = a[0]; a[0] = a[4]; a[4] = a[5]; a[5] = a[1]; a[1] = tmp;
    }
};


int main(void)
{
  int i, in[6];
  string command;
  for (i = 0; i < 6; i++) cin >>in[i];
  cin >> command;
  Dice d(in);
  for (i = 0; i < command.size(); i++) {
    if (command[i] == 'E') d.e();
    else if (command[i] == 'N') d.n();
    else if (command[i] == 'S') d.s();
    else if (command[i] == 'W') d.w();
  }
  cout << d.a[0] << endl;
  return 0;
}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
using namespace std;
char s1[0xfffff],s2[0xfffff];
int main()
{
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	gets(s1);
	gets(s2);
    int l=strlen(s1);
    int ll=strlen(s2); 
    sort(s1,s1+l);
    sort(s2,s2+ll); 
	for(int i=0;i<=max(l,ll);i++)   
	{
        if(s1[i]<s2[ll-i-1])
        {
            cout<<"Yes"<<endl;
            return 0;
        }
        if(s1[i]>s2[ll-i-1])
            break;
    }
    cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
    int64_t n, l;
    cin >> n >> l;

    int64_t s = 0;
    for (auto i : irange(0L, n)) {
        s += l + i;
    }

    if (l * (l + n - 1) <= 0) {
        // NOP
    } else if (abs(l) < abs(l + n - 1)) {
        s -= l;
    } else {
        s -= l + n - 1;
    }

    cout << s << endl;
}

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


int main() {
  int r;
  cin >> r;
  if (r < 1200) cout << "ABC" << endl;
  else if (r < 2800) cout << "ARC" << endl;
  else cout << "AGC" << endl;
}

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

using namespace std;

int main(){

    int n, h;
    cin >> h >> n;
    int tot = 0;
    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];

    for(int i = 0; i < n; i++)
        tot += arr[i];

    if( tot >= h )
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


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


void solve(long long K, long long N, std::vector<long long> A){
    vector<long long> dA(N);
    for(int i = 0; i < N; ++i){
        if(i == 0) dA[i] = A[i] + K - A[N-1];
        else{
            dA[i] = A[i] - A[i-1];
        }
    }
    cout << K - *max_element(dA.begin(), dA.end()) << endl;
    return;
}

int main(){
    long long K;
    scanf("%lld",&K);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(K, N, std::move(A));
    return 0;
}


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

int main(){
    long long a, b, c;
    cin >> a >> b >> c;

    long long an = b*c*((a+1)/2) - b*c*(a/2);
    long long bn = a*c*((b+1)/2) - a*c*(b/2);
    long long cn = a*b*((c+1)/2) - a*b*(c/2);

    cout << min(an, min(bn, cn)) << endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

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

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 55;

int n, ans, cnt[MAXN];
bool v[MAXN];

inline void DFS(int x)
{
	if (x == 13)
	{
		int ret = 24;
		for (int i = 0; i < 24; i ++)
			for (int j = i + 1; j < 24; j ++)
				if (v[i] && v[j])
					ret = min(ret, min(j - i, 24 - j + i));
		ans = max(ans, ret);
		return ;
	}
	if (cnt[x] == 2)
		v[x] = v[24 - x] = 1, DFS(x + 1);
	else if (cnt[x])
	{
		v[x] = 1, DFS(x + 1), v[x] = 0;
		if (x)
			v[24 - x] = 1, DFS(x + 1), v[24 - x] = 0;
	}
	else
		DFS(x + 1);
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		cnt[Read()] ++;
	cnt[0] ++;
	for (int i = 1; i < 12; i ++)
		if (cnt[i] > 2)
			return puts("0"), 0;
	if (cnt[12] > 1 || cnt[0] > 1)
		return puts("0"), 0;
	DFS(0);
	return printf("%d\n", ans), 0;
}


Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))

c = []
xn = 0
TF = [False for _ in range(8)]
for r in a:
    if r <= 399:
        TF[0] = True
    elif 400 <= r <= 799:
        TF[1] = True
    elif 800 <= r <= 1199:
        TF[2] = True
    elif 1200 <= r <= 1599:
        TF[3] = True
    elif 1600 <= r <= 1999:
        TF[4] = True
    elif 2000 <= r <= 2399:
        TF[5] = True
    elif 2400 <= r <= 2799:
        TF[6] = True
    elif 2800 <= r <= 3199:
        TF[7] = True
    else:
        xn += 1
truenum = sum(1 for i in TF if i)
minv = truenum
if truenum == 0:
    minv = 1
maxv = truenum + xn
print(minv, maxv)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int w,h;
int mp[20][20];
int memo[20][20];
int ans;
int count;
 
int saiki(int x,int y) {
  count++;
  int dx[3] = {-1,0,1};
  int dy[3] = {1,1,1};
   
  if(y >= h-1) ans++,memo[y][x]++;
  else if(mp[y][x] != 1) {
    for(int i=0;i<3;i++) {
      int nx = dx[i]+x;
      int ny = dy[i]+y;
      if(nx <0|| nx >= w || memo[ny][nx] == -1||mp[ny][nx] == 1) continue;
       
      if(memo[ny][nx] > 0 && mp[ny][nx] == 0) {
	ans += memo[ny][nx];
	memo[y][x] += memo[ny][nx];
      } 
      else if(mp[ny][nx] == 0){
	saiki(nx,ny);
	if(memo[ny][nx] > 0) memo[y][x] += memo[ny][nx];
      }
      else if(nx==x && mp[ny][nx] == 2){
	int ty = ny;
	while(mp[ty][nx] == 2) ty+=2;
	if(mp[ty][nx] == 0 && memo[ty][nx] == 0){
	  saiki(nx,ty);
	  if(memo[ty][nx] > 0) memo[y][x] += memo[ty][nx];
	}
	else if(mp[ty][nx] == 0 && memo[ty][nx] > 0){
	  memo[y][x] += memo[ty][nx];
	  ans+= memo[ty][nx];
	}
      }
    }
    if(memo[y][x] == 0) memo[y][x] = -1;
  }
}
 
 
int main() {
 
  while(1) {
    cin >> w >> h;
    if(w == 0 && h == 0) break;
 
    for(int i=0;i<=19;i++)
      for(int j=0;j<=19;j++){
	memo[i][j] = 0;
	mp[i][j] = 0;
      }
     
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)
	cin >> mp[i][j];
 
 
    ans = 0;
    count = 0;
    for(int i=0;i<w;i++) {
      if(mp[0][i] !=1) saiki(i,0);
    }
    int ans2 = 0;
    for(int i=0;i<w;i++)
      if(memo[0][i] > 0) ans2+=memo[0][i];
     
    //cout << ans << endl;
       cout << ans2 << endl;
    //cout << count << endl;
  }
 
  return 0;
}

Measured memory_bytes: 1164
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> sl;

void dfs(int keta, int now, int c3, int c5, int c7) {
	if (keta == 10)return;
	if(now != 0 && c3 > 0 && c5 > 0 && c7 > 0)sl.push_back(now);
	int add[3] = { 3,5,7 };
	for (int i = 0; i < 3; i++) {
		int nxt = now * 10 + add[i];
		if (i == 0)dfs(keta + 1, nxt, c3 + 1, c5, c7);
		if (i == 1)dfs(keta + 1, nxt, c3, c5 + 1, c7);
		if (i == 2)dfs(keta + 1, nxt, c3, c5, c7 + 1);
	}
}

int main() {
	dfs(0, 0, 0, 0, 0);
	sort(sl.begin(), sl.end());
	int N;
	cin >> N;
	int ans = 0;
	for (int i = 0; i < sl.size(); i++) {
		if (sl[i] <= N)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define rep(i,n) for(int i=0;i<(n);i++)
#define repx(i,x,n) for(int i=(x);i<(n);i++)
#define ll long long
#define vl vector<ll>
#define vvl vector<vl>
using namespace std;

int main(){
    
    int n,k,c1=0,c2=0,ans=0;
    string s;
    cin >> n >> k >> s;

    rep(i,n-1){
        if(s[i] == 'R' && s[i+1] == 'L'){
            c1++;
        }else if(s[i] == 'L' && s[i+1] == 'R'){
            c2++;
        }else{//(s[i] == s[i+1])
            ans++;
        }
    }

    //cout << "ans,c1,c2=  " << ans << ", " << c1 << ", " << c2 <<endl;

    while(k > 0){
        if(c1 > 0 && c2 > 0){
            ans += 2;
            c1--;
            c2--;
            k--;
        }else if(c1 > 0){
            ans++;
            break;
        }else if(c2 > 0){
            ans++;
            break;
        }else{//(c1 == 0 && c2 == 0)
            break;
        }
    }

    cout << ans << endl;

    return 0;
}


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

int main(void){
    int n;
    cin >> n;
    
    int i, cnt = 0;
    for(i = 1; i <= n; i += 2){
        if(i == 105 || i == 135 || i == 165 || i == 189 || i == 195){
            cnt++;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}


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

int main() {
	bool a=false,b=false,c=false;
	char S;
	for(int i=0;i<3;i++)
	{
		cin>>S;
		if(S=='a')a=true;
		if(S=='b')b=true;
		if(S=='c')c=true;
	}
	if(a&&b&&c)cout<<"Yes";
	else cout<<"No";
	}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
 
int main()
{
  long long int a,b,c,d;
  scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
  
 	//printf("%lld %lld %lld %lld\n",a,b,c,d);
 
  	//printf("%lld",100000000*100000000l);
  
  
    
  if (a<=0 && 0<=b && c<=0 && 0<=d )
  {
    if ( (b*d) >= (a*c) )
    {
    printf("%lld",b*d);
    return 0;
    } else {
    printf("%lld",a*c);
    return 0;  
    }
  }
  
    if (0<=a && d<=0 && c<=0 && d<=0)
  {
    printf("%lld",a*d);
    return 0;
  }
  
   if (a<=0 && b<=0 && 0<=c && 0<=d )
  {
    printf("%lld",b*c);
    return 0;
  }
   
  if (0<=b && 0<=d )
  {
    printf("%lld",b*d);
    return 0;
  }

   
  if (a<=0 && c<=0)
  {
   	printf("%lld",a*c);
   	return 0;
  }
  
  
  return 0;
}

Measured memory_bytes: 2148
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin >> s;
    for(int i = 0;i<s.size();i++){
        if(s[i]=='U'||s[i]=='D'){
            continue;
        }
        else if(s[i]=='L'){
            if(i%2==0){
                cout << "No" << endl;
                return 0;
            }
        }
        else{
            if(i%2==1){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
import Text.Printf
import Control.Monad
avg list = sum list / (fromIntegral (length list) :: Double) 
main = do
  n <- readLn
  when (n /= 0) $ do
    s <- return . map (\x -> read x :: Double) . words =<< getLine
    let m = avg s
    putStrLn $ printf "%.08f" $ sqrt $ (/) (sum $ map (\x -> (x - m)^2) s) n
    main

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

int main(void){
    // Your code here!
   int a, b, c;
   cin >> a >> b >> c;
   if((b*10+c) % 4 == 0){
       cout << "YES" << endl;
   } else {
       cout << "NO" << endl;
   }
}


Measured memory_bytes: 256
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<ll,ll>
#define vi(x) vector<x>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;

signed main()
{
    fast;
  
    ll s,w;
    cin>>s>>w;
    if(w>=s) cout<<"unsafe";
    else cout<<"safe";
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int>a(3);
    for(int i=0;i<3;i++){
        cin>>a[i];}
    sort(a.begin(),a.end());
    int x=a.at(1)-a.at(0);
    int y=a.at(2)-a.at(1);
    cout<<x+y<<endl;
    return 0;}
    

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

int main() {
  int M, N;
  cin >> N >> M;
  
  priority_queue<int64_t> A;
  for(int i = 0; i < N; ++i) {
    int64_t a;
    cin >> a;
    A.push(a);
  }
  
  while(M > 0) {
    auto a = A.top();
    A.pop();
    A.push(a/2);
    --M;
  }
  
  int64_t total = 0;
  for(int i = 0; i < N; ++i) {
    total += A.top();
    A.pop();
  }
  cout << total << endl;
  return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(ll)1e18;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int s,w;cin>>s>>w;
    if(w>=s)cout<<"unsafe";
    else cout<<"safe";
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
int main(void){
  int N;
  cin >> N;
  vector<int>t(N),x(N),y(N);
  for(int i=0; i<N; ++i){
    cin >> t.at(i) >> x.at(i) >> y.at(i);
  }
  int X=0,Y=0,T=0,can=0,dt,dx,dy;
  for(int i=0; i<N; ++i){
    dt=t.at(i)-T;
    dx=x.at(i)-X;
    dy=y.at(i)-Y;
    if(dt >= abs(dx)+abs(dy) && dt%2==abs(dx+dy)%2){
      can = 1;
    }
    else {
      can = 0;
      break;
    }
    T+=dt;
    X+=dx;
    Y+=dy;
  }
  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s; int K; cin>>s>>K;
	for (char &ch : s) {
		if(ch=='a') continue;
		int cur='z'-ch+1;
		if(cur>K) continue;
		K-=cur;
		ch='a';
	}
	s.back()=(s.back()-'a'+K)%26+'a';
	cout<<s<<"\n";
	return 0;
}


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

int N;
map<long long, int> S;
long long R;

int main() {
  cin >> N;
  long long s = 0; ++S[0];
  for(int i = 0; i < N; ++i) {
    long long a; cin >> a; s += a;
    R += S[s]; ++S[s];
  }
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 12800
#include <iostream>

using namespace std;

int main()
{
    int h,n,sum=0;
    cin>>h>>n;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum+=x;
    }
    if (sum>=h)
        cout << "Yes";
    else
        cout<<"No";

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[100010], b[100010], ans;
int main () {
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) scanf ("%d", &a[i]), b[i] = a[i];
	sort (b + 1, b + n + 1);
	for (int i = 1; i <= n; i++) a[i] = lower_bound (b + 1, b + n + 1, a[i]) - b;
	for (int i = 2; i <= n; i += 2) ans += a[i] & 1;
	printf ("%d\n", ans);
	return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define endl "\n"     
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

const int N=1e3+5;
const int mod=1e9+7;

char a[N][N];
int n,m;
int cache[N][N];

int dp(int i,int j)
{
     if(i>n || j>m || a[i][j]=='#')
          return 0;
     if(i==n && j==m)
          return 1;
     int &ans=cache[i][j];
     if(ans!=-1)
          return ans;
     return ans=(dp(i+1,j)+dp(i,j+1))%mod;    
}

int32_t main()
{
	IOS;
     memset(cache,-1,sizeof cache);
     cin>>n>>m;
     for(int i=1;i<=n;i++)
     {
          for(int j=1;j<=m;j++)
               cin>>a[i][j];
     }
     cout<<dp(1,1);
     
	return 0;
}

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

S1 = 0
S2 = 0
#S1が奇数番目が正の場合、S2が偶数番目が負の場合
cnt1 = 0
cnt2 = 0

for i,num in enumerate(a):
    S1 += num
    if i % 2 == 0 and S1 <= 0:
        cnt1 += 1 - S1
        S1 = 1
    if i % 2 != 0 and S1 >= 0:
        cnt1 += 1 + S1
        S1 = -1

    S2 += num
    if i % 2 == 0 and S2 >= 0:
        cnt2 += 1 + S2
        S2 = -1
    if i % 2 != 0 and S2 <= 0:
        cnt2 += 1 - S2
        S2 = 1

print(cnt1 if cnt1 <= cnt2 else cnt2)


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

const int KIND = 26;

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int D; cin>>D;
    vi c(KIND);
    rep(i,KIND) cin>>c[i];
    vector<vi> s(D, vi(KIND));
    rep(i,D)rep(j,KIND) cin>>s[i][j];
    vi t(D);
    rep(i,D) cin>>t[i];
    rep(i,D) t[i]--;
    vi last(KIND,0);
    ll V=0;
    rep(i,D){
        last[t[i]] = 0;
        rep(j,KIND)if(t[i]!=j){
            last[j]++;
            V -= c[j]*last[j];
        }
        V += s[i][t[i]];
        cout<<V<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3672
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,a[101],sum;
int main()
{
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	sort(a,a+n);
	bool f;
	if (sum%10!=0) cout<<sum;
	else
	{
		for (int i=0;i<n;i++)
		{
			if ((sum-a[i])%10==0) {f=false; continue;}
			else {cout<<sum-a[i]; f=true; break;}
		}
  		if (!f) cout<<"0";
	}
    return 0;
}

Measured memory_bytes: 256
a1,a2,a3 = map(int, input().split())
b1,b2,b3 = map(int, input().split())
c1,c2,c3 = map(int, input().split())
if (b1 - a1) == (b2 - a2) == (b3 - a3) and (c1 - b1) == (c2 - b2) == (c3 - b3):
  if a2 - a1 == b2 - b1 == c2 - c1 and a3 - a2 == b3 - b2 == c3 - c2:
    print("Yes")
  else:
    print("No")
else:
  print("No")

  

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

long long n, p;
map<long long, int> mp;

long long solve();

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

  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long ans = 1;
  for(long long i = 2; i * i <= p; ++i) {
    while(p % i == 0) {
      ++mp[i];
      p /= i;
    }
  }
  if(p > 1) ++mp[p];
  for(auto it = mp.begin(); it != mp.end(); ++it)
    while(it->second >= n) {
      ans *= it->first;
      it->second -= n;
    }
  return ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
using namespace std;

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


string t;
vector < string> st;
int s[1000]={0};
int max1=0;
int max2=0;

int main(){
	while(cin >>t){
		bool flag=true;
		int tmp = t.size();
		max1 = max(max1,tmp );
		rep(i,st.size()){
			if(t == st[i]){
				s[i]++;
				max2 = max(max2,s[i]);
				flag = false;
				break;
			}
		}
		if(flag){
			st.push_back(t);
		}
	}
	rep(i,st.size()){
		if(s[i]==max2){
			cout<<st[i]<<" ";
			break;
		}
	}
	rep(i,st.size()){
		if(st[i].size()==max1){
			cout<<st[i]<<endl;
			break;
		}
	}
	return 0;
}

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

using namespace std;

template <typename T> T &chmin(T &a, const T &b) {return a = min(a, b);}
template <typename T> T &chmax(T &a, const T &b) {return a = max(a, b);}

using ll = long long;
using ld = long double;

const ll INF = 1e15;
const ld eps = 1e-9, pi = acos(-1.0);

int main(){
  int n;
  cin >> n;
  int x[n], y[n];
  REP(i, n) cin >> x[i] >> y[i];
  int perm[n];
  ld res = 0;
  REP(i, n) perm[i]=i;
  int cnt = 0;
  do {
    REP(i, n-1){
      res+=sqrt((x[perm[i+1]]-x[perm[i]])*(x[perm[i+1]]-x[perm[i]])+(y[perm[i+1]]-y[perm[i]])*(y[perm[i+1]]-y[perm[i]]));
    }
    cnt++;
  } while(next_permutation(perm, perm+n));
  cout << setprecision(20) << res/cnt << endl;
  return 0;
}

Measured memory_bytes: 3748
// [[ABC134C] Exception Handling] https://www.luogu.com.cn/problem/AT4843
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main() {
  int a, b, k;
  scanf("%d%d%d", &a, &b, &k);
  for (int i = a; i <= min(b, a + k - 1); i++) printf("%d\n", i);
  for (int i = max(b - k + 1, a + k); i <= b; i++) printf("%d\n", i);
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

object Main extends App {

  val sc = new Scanner(System.in)

  val k, a, b = sc.nextLong()

  if (a + 2 > b) {
    println(k + 1)
  } else if (a >= k) {
    println(k + 1)
  } else {
    val m = (k - a + 1) / 2
    println(a + m * (b - a) + (if ((k - a + 1) % 2 == 0) 0 else 1))
  }
}


Measured memory_bytes: 25528
#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 ll;
const int MOD = 1000000007;
const int INF = 1000000000;

int f[100005],b[100005];
int Par[100005],Rank[100005],Size[100005];
int ans[100005];

void init(int n)
{
   rep(i,n)
   {
      Par[i]=i;
      Rank[i] = 0;
      Size[i]=1;
   }
}

int find(int x)
{
   if(Par[x]==x)
   {
      return x;
   }
   else
   {
      return Par[x] = find(Par[x]);
   }
}
void unite(int x,int y)
{
   x = find(x);
   y = find(y);
   if(x==y)return ;

   if(Rank[x]<Rank[y])
   {
      Par[x] = y;
      Size[y]+= Size[x];
   }
   else
   {
      Par[y]=x;
      Size[x]+= Size[y];
      if(Rank[x]==Rank[y])Rank[x]++;
   }
}

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

int size(int x)
{
   return Size[find(x)];
}

int main()
{
   memset(f,0,100005*sizeof(int));
   memset(b,0,100005*sizeof(int));
   int n,m,k;
   cin >> n >> m >> k;
   init(n);
   rep(i,m)

   {
      int a,c;
      cin >> a >> c;
      a--;c--;
      f[a]++;
      f[c]++;
      unite(a,c);
   }
   rep(i,n)ans[i] = size(i)-1-f[i];
   rep(i,k)

   {
      int a,c;
      cin >> a >> c;
      a--;c--;
      b[a]++;
      b[c]++;
      if(same(a,c))
      {
         ans[c]--;
         ans[a]--;
      }
   }
   rep(i,n)cout<<ans[i]<<endl;
   return 0;
}

Measured memory_bytes: 3200