akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
	int W,N,c=1;
	char ch;
	while (cin >> W, W)
	{
		cin >> N;
		int a[N], w[N];
		for (int i=0; i<N; i++)
			cin >> a[i] >> ch >> w[i];

		int dp[W+1];
		for (int i=0; i<=W; i++)
			dp[i] = -1;

		dp[0] = 0;
		for (int i=0; i<N; i++)
		for (int k=W; k>=0; k--)
			if (dp[k] >= 0 && k+w[i] <= W)
				dp[k+w[i]] = max(dp[k]+a[i], dp[k+w[i]]);

		int MAX = 0;

		for (int i=1; i<=W; i++)
			if (dp[MAX] < dp[i])
				MAX = i;

		cout << "Case " << c++ << ':' << endl;
		cout << dp[MAX] << endl;
		cout << MAX << endl;
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;
 
vector<P>E[100000];
int d[100000];
int main() {
    int v, e, r; scanf("%d%d%d", &v, &e, &r);
    rep(i, e) {
        int s, t, d; scanf("%d%d%d", &s, &t, &d);
        E[s].push_back(P(t, d));
    }
    memset(d, 0x3f, sizeof(d));
    priority_queue<P, vector<P>, greater<P>>que;
    d[r] = 0;
    que.push(P(0, r));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        if (p.first != d[p.second])continue;
        for (P u : E[p.second]) {
            if (d[u.first] > d[p.second] + u.second) {
                d[u.first] = d[p.second] + u.second;
                que.push(P(d[u.first], u.first));
            }
        }
    }
    rep(i, v) {
        if (d[i] == INF)puts("INF");
        else printf("%d\n", d[i]);
    }
}


Measured memory_bytes: 13104
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

d = {'r' : p, 's' : r, 'p' : s}
ans = 0
l = [1] * k + [0] * (n - k)

for i in range(k):
    ans += d[t[i]]

for i in range(k, n):
    if t[i] == t[i - k] and l[i - k]: continue
    ans += d[t[i]]
    l[i] = 1

print(ans)

Measured memory_bytes: 10652
#include <stdio.h>

int main(void){    
   int W,H,x,y,r;

 scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
 if(x+r>W||0>x-r||y+r>H||0>y-r){
    printf("No\n");
     } else {
         printf("Yes\n");
     }
     
 return 0;
}


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

int main(){
string s,t;
cin >> s>> t;
int ans =0;
for(int i = 0 ;i<s.size();++i){
    if(s[i]==t[i])
    ans +=1;

}
cout << ans <<endl;
}

Measured memory_bytes: 256
//
//  main.cpp
//  ABC_170_D
//
//  Created by Joe Mori on 2020/06/14.
//  Copyright © 2020 Joe Mori. All rights reserved.
//

#include <iostream>
#include<bits/stdc++.h>

int main() {
    // insert code here...
    int N,count=0;
    std::cin>>N;
    std::vector<int>a(N);
    for(int i=0;i<N;i++){
        std::cin>>a[i];
    }
    std::sort(a.begin(),a.end());
    
    std::vector<bool>B(a[N-1]+1,true);
    for(int i=0;i<N;i++){
        if(!B[a[i]])continue;
        for(int j=2;j*a[i]<=a[N-1];j++){
            B[j*a[i]]=false;
        }
        if(a[i]==a[i+1])B[a[i]]=false;
    }
    for(int i=0;i<N;i++){
//        std::cout<<"a[i]:"<<a[i]<<" "<<B[a[i]]<<std::endl;
        if(B[a[i]]){
            count++;
        }
    }
    std::cout<<count<<std::endl;
    
    return 0;
}


Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -MOD * MOD;
const long double pi = 3.141592653589793;
ll five(ll x) {
	return x * x * x * x * x;
}
int main() {
	int x;
	cin >> x;
	for (int i = -2000; i <= 2000; i++) {
		for (int j = -2000; j <= 2000; j++) {
			if (five(i) - five(j) == x) {
				cout << i << " " << j << endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3592
from sys import stdin
import numpy as np
input = stdin.readline
n = input().rstrip()
n = int(n)
a = list(map(int, input().split()))
a = np.array(a)
suma = np.cumsum(np.array(a))

ans = 0
for i in range(n-1):
    x = suma[n-1] - suma[i]
    x %= 1000000007
    ans += a[i] * x
    ans %= 1000000007

print(ans)


Measured memory_bytes: 49544
//********************************************************************//
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fi first 
#define se second 
#define RANGE(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define DFOR(i, a, b) for(int i = a; i > b; --i)
#define DEB(x) cout << #x << ": " << x << endl
#define ALL(v) v.begin(), v.end() 
#define SORT(v) sort(ALL(v))
#define DISPV(v) { for(auto x___: v) cout << x___ << " "; cout << endl; }
#define DISPM(m) { for(auto x____: m){ cout << x____.first << ": " << x____.second << endl; } };
#define DISPMV(m) { for(auto x_____: m){ cout << x_____.first << ": " ;DISPV(x_____.second);} };
using LL = long long;
using VI = vector <int>;
using VC = vector <char>;
using VS = vector <string>;
using VL = vector <long long>;
using VVI = vector<VI>;
using VVL = vector <VL>;
using MII = map<int, int>;
using MIVI = map<int, VI>;
using MSS = map<string, string>;
using MLL = map<LL, LL>;
int READ_INT(){int temp;cin>>temp;return temp;}      // read an int
LL READ_LONG(){LL temp;cin>>temp;return temp;}      // read a long long
void mcs(VI &series, int &max_sum){                    // maximum contigous sub sum(kadane)
    int s=0;
    for(auto x: series){
        s += x;
        max_sum = max(max_sum, s);
        if(s < 0)s = 0;
    }
}
template<typename T>
T MAX(T t){ return t;}
template <typename T, typename... Args>
T MAX(T t, Args... args){ return max(t, MAX(args...)); }
const int MOD = int(1e9) + 7;
const int INF = 1e9 + 5;
const double PI = acos(-1.0); //M_PI;
const double EPS = 1e-9;
//********************************************************************//
 
int main(){
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

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

    if(t.size() - s.size() == 1){
        int n = 0;
        for(int i = 0; i < s.size(); ++i){
            if(t[i] == s[i])n++;
        }
        if(n == s.size()){
            cout << "Yes";
        }
        else 
            cout << "No";
    }
    else{
        cout << "No";
    }
    

    return 0;
}



/* complie flags
-Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector
*/

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

int atk1, h1, atk2, h2;

int main() {
    cin >> h1 >> atk1 >> h2 >> atk2;
    while (h1 >= 0 && h2 >= 0) {
        h2 -= atk1;
        if (h2 <= 0) {
            cout << "Yes";
            break;
        }
        h1 -= atk2;
        if (h1 <= 0) {
            cout << "No";
            break;
        }
    }
}

Measured memory_bytes: 3632
using System;
using System.Linq;
 
class GotoSchool
{
	public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        
        string[] str = Console.ReadLine().Split(' ');
        int[] ary = str.Select(int.Parse).ToArray();
 
        int[] num = new int[n];
 
        for(int i = 0; i < n; i++)
        {
            num[ary[i]-1] = i + 1;
        }
 
        Console.WriteLine(string.Join(" ", num));
    }
}

Measured memory_bytes: 29788
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 1000000007;
using ll = int64_t;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> G(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a-1].emplace_back(b-1);
        G[b-1].emplace_back(a-1);
    }
    vector<int> c(n), d(n);
    int Q;
    cin >> Q;
    vector<array<int, 3>> x(Q);
    for (int i = 0; i < Q; ++i) {
        int s, t, u;
        cin >> s >> t >> u;
        x[i] = {s-1, t, u};
    }
    reverse(x.begin(), x.end());
    for (int i = 0; i < Q; ++i) {
        int v = x[i][0], p = x[i][1], q = x[i][2];
        queue<pair<int, int>> que;
        que.emplace(v, p);
        while(!que.empty()){
            int vv, pp; tie(vv, pp) = que.front(); que.pop();
            if(c[vv] == 0) c[vv] = q;
            if(d[vv] >= pp) continue;
            d[vv] = pp;
            for (auto &&j : G[vv]) {
                que.emplace(j, pp-1);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        printf("%d\n", c[i]);
    }
    puts("");
    return 0;
}


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

int main()
{
  int n;
  cin >> n;
  int a[n * 2];
  for (int i = 0; i < n * 2; i++) {
    cin >> a[i];
  }
  sort(a, a + n*2);
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    int x = a[2*i];
    int y = a[2*i+1];
    if (x > y) {
      cnt += y;
    } else {
      cnt += x;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool bingo(int a[]){
  if(a[0]+a[1]+a[2]==0 || a[3]+a[4]+a[5]==0 || a[6]+a[7]+a[8]==0 
    || a[0]+a[3]+a[6]==0 || a[1]+a[4]+a[7]==0 || a[2]+a[5]+a[8]==0 
    || a[0]+a[4]+a[8]==0 || a[2]+a[4]+a[6]==0) return true;
  else return false;
}
int main(){
  int a[9];
  for(int i=0; i<9; i++){
    cin >> a[i];
  }
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    int b;
    cin >> b;
    for(int j=0; j<9; j++) if(a[j]==b) a[j]=0;
  }
  if(bingo(a)) cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 256
long long x, y, ans;
int main() {
	__builtin_scanf("%lld%lld", &x, &y);
	y /= x;
//	if (y <= 0) {
//		__builtin_puts("0");
//		return 0;
//	}
	while (y) y /= 2, ans++;
	__builtin_printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,i,j,k,cc[500000],a,b,c,s ;
struct p{
	long long x,y,z;
	bool operator < (const p& gg) const{
		return x<gg.x;
	}
}s1[500000],s2[500000];
struct pp{
	long long x,y,z;
	bool operator < (const pp& tt) const{
		return z<tt.z;
	}
}wow[1000000];
long long find(long long x){
	if (cc[x]==x) return x;
	else {
		cc[x]= find(cc[x]);
		return cc[x];
	}
}

int main(){
	scanf("%lld",&n);
	for (int i=0;i<n;i++){
		scanf("%lld %lld",&s1[i].x,&s1[i].y);
		s2[i].x=s1[i].y;
		s2[i].y=s1[i].x;
		s1[i].z=i+1;
		s2[i].z=i+1;
	}
	sort(s1,s1+n);
	sort(s2,s2+n);
	a=-1;
	for (int i=1;i<n;i++){
		a++;
		wow[a].x=s1[i].z;
		wow[a].y=s1[i-1].z;
		wow[a].z=(s1[i].x-s1[i-1].x);
	}
	for (int i=1;i<n;i++){
		a++;
		wow[a].x=s2[i].z;
		wow[a].y=s2[i-1].z;
		wow[a].z=(s2[i].x-s2[i-1].x);
	}	
//	for (int i=0;i<=a;i++) printf("%d %d %d\n",wow[i].x,wow[i].y,wow[i].z);		
	sort(wow,wow+a+1);
//	for (int i=0;i<=a;i++) printf("%d %d %d\n",wow[i].x,wow[i].y,wow[i].z);	
	for (int i=0;i<=300000;i++) cc[i]=i;
	for (int i=0;i<=a;i++){
		if (find(cc[wow[i].x])!=find(cc[wow[i].y])){
			cc[find(cc[wow[i].x])]=find(cc[wow[i].y]);
			s+=wow[i].z;
		}
	}
	printf("%lld\n",s);
	return 0;
}

Measured memory_bytes: 20224
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(int argc, char const *argv[])
{
    int N;
    cin >> N;
    vector<int> t, x, y;
    t.resize(N);
    x.resize(N);
    y.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> t[i] >> x[i] >> y[i];
    }

    int prvt = 0, prvx = 0, prvy = 0;
    for (int i = 0; i < N; i++)
    {
        if (t[i] - prvt < abs(x[i] - prvx) + abs(y[i] - prvy))
        {
            cout << "No" << endl;
            return 0;
        }else
        {
            if ((t[i] - prvt - abs(x[i] - prvx) - abs(y[i] - prvy)) % 2 != 0)
            {
                cout << "No" << endl;
                return 0;
            }
            
        }
        prvt = t[i];
        prvx = x[i];
        prvy = y[i];
           
    }
    
    cout << "Yes" << endl;
    
    return 0;
}

Measured memory_bytes: 1408
N, Y = gets.split.map &:to_i

def f(n, y)
  res = [0, 0, 0]
  loop do
    if n<0 or y<0
      return nil
    end
    if n*5000==y
      res[1] += n
      return res
    elsif n*5000<y
      res[0] += 1
      n -= 1
      y -= 10000
    else
      res[2] += 1
      n -= 1
      y -= 1000
    end
  end
end

if w=f(N, Y)
  puts w.join ' '
else
  puts [-1]*3*' '
end



Measured memory_bytes: 1788
#include <algorithm>
#include <bitset>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define pb push_back
#define debug1(x) cerr << #x << " = " << x << '\n';
#define debug2(x, y) cerr << #x << " = " << x << "   " << #y << " = " << y << "\n";
#define _ ios_base::sync_with_stdio(0);cin.tie(NULL);

void solve() {
    ll n;
    cin >> n;
    ll a[n];
    ll pre[n];
    for(ll i = 0; i<n; i++) cin >> a[i];
    pre[0] = a[0];
    for(ll i = 1; i<n; i++) {
        pre[i] = max(pre[i-1], a[i]);
    }
    ll ans = 0;
    for(ll i = 1; i<n; i++) {
        ans += (pre[i] - a[i]);
    }
    cout << ans << '\n';
}

int main() {_
    int t = 1;
//    cin >> t;
    for(int i = 1; i<=t; i++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 6732
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, k;
char s[N];
int a[N], sum[N];
class Node {
  public:
    int col, num;
    Node() {}
    Node(int _x, int _y) {
      this -> col = _x, this -> num = _y;
    }
}b[N];
int main() {
  scanf ("%d%d", &n, &k);
  scanf ("%s", s + 1);
  int tot = -1, now_col = 2, now_num = 0;
  int j = 1;
  a[0] = 2;
  while (j <= n) {
    if (s[j] != s[j - 1]) {
      b[++tot] = Node(now_col, now_num);
      now_col = s[j] - '0', now_num = 1;
      ++j;
      continue;
    }
    ++now_num;
    ++j;
  }
  b[++tot] = Node(now_col, now_num);
  b[++tot] = Node(2, 0);
  for (int i = 1; i <= tot; i++) {
    sum[i] = sum[i - 1] + b[i].num;
  }
  int ans = 0;
  for (int i = 1; i < tot; i++) {
    if (b[i].col == 1) {
      int ed = i + 2 * k;
      ed = min(ed, tot);
      ans = max(ans, sum[ed] - sum[i - 1]);
    }
    else {
      int ed = i + 2 * k - 1;
      ed = min(ed, tot);
      int st = max(i - 1, 1);
      ans = max(ans, sum[ed] - sum[st - 1]);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1536
#include <iostream>
using namespace std;
int main() {
  int a, b;
  string op;
  while(1) {
    cin >> a >> op >> b;
    if(op == "?") break;

    if(op == "+") cout << a+b << "\n";
    else if(op == "-") cout << a-b << "\n";
    else if(op == "*") cout << a*b << "\n";
    else if(op == "/") cout << a/b << "\n";
  }
  return 0;
}


Measured memory_bytes: 3108
k = int(input())
s = input()
n = len(s)

MAX = 10**6
MOD = 10**9+7

inv = [0] * (MAX+1)
inv[1] = 1
for i in range(2, MAX+1):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD

ans = val = pow(26, k, MOD)
for i in range(1, k+1):
    val *= (i+n-1) * 25 * inv[i] * inv[26] % MOD
    val %= MOD
    ans += val
    ans %= MOD
print(ans)


Measured memory_bytes: 49460
#include<stdio.h>

int dp[1005][30000];
int a[10009],b[10009];
int N;
int min2(int a,int b){
  if(a > b) return b;
  else return a;
}
int min3(int a,int b,int c){
  return min2(c,min2(a,b));
}
int rec_dp(int i,int j);
int main(void){
  int H,i,j,max=0,ans=200000000;
  scanf("%d %d\n",&H,&N );
  for(i=0; i<N; i++){
    scanf("%d %d\n",&a[i],&b[i] );
    if(max < a[i]) max = a[i];
  }
  for(i=0;i<N;i++){
    for(j=0;j<H+max;j++){
      dp[i][j] = -1;
    }
  }
  for(j=H; j < H+max; j++){
    if(ans > rec_dp(0,j)) ans = rec_dp(0,j);
  }
  printf("%d\n",ans );
  return 0;
}

int rec_dp(int i,int j){
  int con;
  if(dp[i][j] != -1) return dp[i][j];
  if(j <= 0) con = 0;
  else if(i == N-1 && j > 0) con = rec_dp(i, j - a[i]) + b[i];
  else con = min3(rec_dp(i, j-a[i])+b[i], rec_dp(i+1,j-a[i])+b[i], rec_dp(i+1,j)+0);
  return dp[i][j] = con;
}

Measured memory_bytes: 116352
while True:
    m,n = map(int,input().split())
    
    if  m== 0 and n == 0:
        break
    
    ta=[]
    ha=[]
    for i in range(m):
        ta.append(int(input()))
        
    for i in range(n):
        ha.append(int(input()))
    
    ta=sorted(ta)
    ha=sorted(ha)
    ans1=[]
    ans2=[]
    for i in sorted(ta):
        for j in sorted(ha):
            if sum(ta) - i + j == sum(ha) - j + i:
                ans1.append(i)
                ans2.append(j)
    
    if len(ans1)==0 and len(ans2)==0:
        print(-1)
    
    else:
        print(ans1[0],ans2[0])
    


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

int main() {
  int n, c;
  std::cin >> n >> c;

  std::vector<std::vector<bool>> tv(c, std::vector<bool>(100000, false));

  for (int i = 0; i < n; i++) {
    int s, t, c;
    std::cin >> s >> t >> c;
    for (int j = s - 1; j < t; j++) {
      tv[c - 1][j] = true;
    }
  }

  int count = 0;

  for (int i = 0; i < 100000; i++) {
    int tmp = 0;
    for (int j = 0; j < c; j++) {
      if (tv[j][i]) {
        tmp++;
      }
    }
    count = std::max(count, tmp);
  }

  std::cout << count << std::endl;
  return 0;
}

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

using namespace std;

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	long long n;
	cin >> n;
	long double s = (long double) sqrt(n);
	long long min_steps = 1e12;
	for (int i = 1; i <= s; ++i) {
		if (n % i == 0) {
			min_steps = min(min_steps, n / i + i - 2);
		}
	}
	cout << min_steps << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a[3][3];
	int count = 0;
	int n, b, i, j, k;

	//ビンゴの数字を配列 a に代入
	for (i = 0; i < 3; i++) {
		scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
	}

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d", &b);
		//選ばれた数字とビンゴの数が一致した配列 a の値を0に変える
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 3; k++) {
				if (a[j][k] == b) {
					a[j][k] = 0;
				}
			}
		}
	}

	//横列のビンゴを判定する
	for (i = 0; i < 3; i++) {
		if (a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0) {
			count = 1;
		}
	}

	//縦列のビンゴを判定する
	for (i = 0; i < 3; i++) {
		if (a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0) {
			count = 1;
		}
	}

	//斜めのビンゴを判定する
	if (a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0) {
		count = 1;
	}

	if (a[0][2] == 0 && a[1][1] == 0 && a[2][0] == 0) {
		count = 1;
	}

	//ビンゴがあったかどうかの判定
	if (count == 1) //ビンゴした
	{
		printf("Yes\n");
	}
	else //ビンゴしていない
	{
		printf("No\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
from collections import Counter
n=int(input())
S=[input() for i in range(n)]
S=dict(Counter(S).most_common())
m=int(input())
T=[input() for i in range(m)]
T=dict(Counter(T).most_common())

for i in S:
  for k in T:
    if i==k:
      S[i] -= T[k]

S=sorted(S.items(),key=lambda x:x[1],reverse=True)

if S[0][1] < 0:
  print(0)
else:
  print(S[0][1])



Measured memory_bytes: 3316
def main():
    N, K = list(map(int, input().split(' ')))
    points = [list(map(int, input().split(' '))) for _ in range(N)]
    points.sort(key=lambda p: p[1])
    ans = 10**19
    for b in range(N):
        bottom = points[b][1]
        for t in range(b + K - 1, N):
            top = points[t][1]
            target_points = points[b:(t+1)].copy()
            target_points.sort(key=lambda p: p[0])
            M = len(target_points)
            for left in range(M):
                right = left + K - 1
                if right >= M:
                    break
                width = target_points[right][0] - target_points[left][0]
                ans = min([ans, width * (top - bottom)])
    print(ans)


if __name__ == '__main__':
    main()

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

int main(){
    char inp[1001];
    cin >> inp;

    for (int i = 0; inp[i] != '\0'; i++)
	if ('D' <= inp[i] && inp[i] <= 'Z') inp[i] -= 3;
	else if (inp[i] == 'A') inp[i] = 'X';
	else if (inp[i] == 'B') inp[i] = 'Y';
	else if (inp[i] == 'C') inp[i] = 'Z';
    
    cout << inp << endl;
}

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

int main()
{
    deque < char > d;
    string s,t;
    int flag;
    cin >> s >> t;
    for (int i=0;i<s.size();i++){
        d.push_back(s[i]);
    }
    for (int i=0;i<s.size();i++){
        d.push_front(d[s.size()-1]);
        d.pop_back();
        for (int j=0;j<t.size();j++){
            if (d[j]==t[j]){
                flag=1;
            }else{
                flag=0;
                break;
            }
        }
    if (flag==1){
           break;
    }
    }
    if (flag==1){
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::*;

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

fn main(){
    let s: String = read().unwrap();
    let n = s.len();
    let mut ss = String::new();
    for _ in 0..n {
        ss.push('x');
    }
    println!("{}", ss);
}

Measured memory_bytes: 4352
N,K=map(int,input().split())
A=list(map(int,input().split()))

#DP[keta][limit]で考える

A01=[[0,0] for i in range(51)]

for keta in range(51):
    A1=0
    A0=0
    for a in A:
        if a & (1<<keta)==0:
            A1+=1<<keta
        else:
            A0+=1<<keta

    A01[keta]=[A0,A1]



def ANS(keta,limit):
    
    if keta==-1:
        return 0

    if limit==1:               
        return max(A01[keta][0],A01[keta][1])+ANS(keta-1,1)

    if limit==0:
        if K & (1<<keta)==0:
            return A01[keta][0]+ANS(keta-1,0)
        else:
            return max(A01[keta][0]+ANS(keta-1,1),A01[keta][1]+ANS(keta-1,0))

print(ANS(50,0))


Measured memory_bytes: 69264
n = int(input())
a = [int(i) for i in input().split()]


q = int(input())
b = []
for _ in range(q):
    b.append([int(i) for i in input().split()])

al = {}
suma = sum(a)

for i in a:
    if i not in al:
        al[i] = 1
    else:
        al[i] += 1

for i in range(q):
    if b[i][0] in al:
        suma += (b[i][1] - b[i][0]) * al[b[i][0]]
        
        if b[i][1] in al:
            
            al[b[i][1]] += al[b[i][0]]
            al[b[i][0]] = 0
        else:
            al[b[i][1]] = al[b[i][0]]
            al[b[i][0]] = 0
    print(suma)
    

Measured memory_bytes: 34484
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int h, m, s, sum1, sum2;
	while(cin >> h >> m >> s)
	{
		if(h==-1&&m==-1&&s==-1)
			break;
		sum1 = 60*60*60*h + 60*60*m+ 60*s;

		sum1 = 60*60*60*2 - sum1;
		sum2 = sum1*3;

		h = sum1/216000;
		m = (sum1%216000)/3600;
		s = ((sum1%216000)%3600)/60;

		//if(h<0){ h=0;m=0;s=0;}
		printf("%02d:%02d:%02d\n",h,m,s);
		h = sum2/216000;
		m = (sum2%216000)/3600;
		s = ((sum2%216000)%3600)/60;
		//if(h<0){ h=0;m=0;s=0;}
		printf("%02d:%02d:%02d\n",h,m,s);
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ll N,A,B,ans;
	cin>>N>>A>>B;
	if(N==1&&A!=B)ans=0;
	else if(A>B)ans=0;
	else ans=(B*(N-1)+A)-(A*(N-1)+B)+1;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <numeric>
#include <type_traits>
#include <limits>
#include <random>
#include <iomanip>

using namespace std;

using ll = long long;

typedef pair<ll, ll> P;

#define rep(i,N) for((long long) i = 0;i < (long long)N; ++i)

static int mod = 1000000007;
static int large_int = 1000000000;
static ll large_ll = 1000000000000000000;

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

string str;

int main() {
	cin >> str;
	if (str <= "2019/04/30") {
		cout << "Heisei" << endl;
	}
	else {
		cout << "TBD" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

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

    long power=1;
    const long div=pow(10,9)+7;

    for(int i=1; i<=n; i++){
        power*=i;
        power%=div;
    }

    cout << power << endl;

    return 0;
}

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

int main(){
	int N,M,C,cnt=0;
    cin >> N >> M >> C;
    int b[M];
    for(int i=0;i<M;i++)
      cin >> b[i];
    for(int i=0;i<N;i++){
      int ans = 0;
      for(int j=0;j<M;j++){
        int a;
        cin >> a;
      	ans += b[j]*a;
      }
      if(ans+C>0)
        cnt++;
    }
  cout << cnt << endl;
}


Measured memory_bytes: 256
s_x, s_y, t_x, t_y = map(int, input().split())
#点のインプット
for i in range(t_x - s_x):
  print("R", end="")
for i in range(t_y - s_y):
  print("U", end="")
for i in range(t_x - s_x):
  print("L", end="")
for i in range(t_y - s_y):
  print("D", end="")
  
t_x = t_x+1
t_y = t_y+1

print("D", end="")
for i in range(t_x - s_x):
  print("R", end="")
for i in range(t_y - s_y):
  print("U", end="")
print("LU", end="")
for i in range(t_x - s_x):
  print("L", end="")
for i in range(t_y - s_y):
  print("D", end="")
print("R")

Measured memory_bytes: 4468
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define Fast_cin ios::sync_with_stdio(false), cin.tie(0);
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long double lb;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

const double PI = acos(-1.0);

int a, b, x;

int main() {
    read(a); read(b); read(x);
    if(x >= a * a * b / 2) {
        printf("%.10lf\n", atan((double)(a * a * b - x) / a / a / a * 2) * 180 / PI);
    } else {
        printf("%.10lf\n", 90 - atan((double)x / a / b / b * 2) * 180 / PI);
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define th acos(0.5)
using namespace std; 
int D;
typedef struct P{
	double x, y;
};
void koch(int d, P p1, P p2){
	if(d == D){
		printf("%.8lf %.8lf\n", p2.x, p2.y); 
		return;
	}
	P s, u, t;
	s.x = (2.0 * p1.x + 1.0 * p2.x) / 3.0;
	s.y = (2.0 * p1.y + 1.0 * p2.y) / 3.0;
	t.x = (1.0 * p1.x + 2.0 * p2.x) / 3.0;
	t.y = (1.0 * p1.y + 2.0 * p2.y) / 3.0;
	double delta_x = t.x - s.x, delta_y = t.y - s.y;
	u.x = s.x + delta_x * cos(th) - delta_y * sin(th);
	u.y = s.y + delta_x * sin(th) + delta_y * cos(th);
	koch(d + 1, p1, s);
	koch(d + 1, s, u);
	koch(d + 1, u, t); 
	koch(d + 1, t, p2);
}
int main()
{
	scanf("%d", &D);
	P a, b;
	a.x = 0.0; a.y = 0.0; b.x = 100.0; b.y = 0.0;
	printf("%.8lf %.8lf\n", a.x, a.y);
	koch(0, a, b);
	return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> P;
typedef long long ll; 
 
#define int ll
 
 
main(){
	ll a;
	double b;
	cin >> a >> b;
	b *= 100.1;
	ll b2  = (ll)b;
	ll ans = (ll) a*b2/100;
	printf("%lld\n",ans);
 
	return 0;
}


Measured memory_bytes: 3808
use std::io;

fn main() {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let v = buf.trim().chars().collect::<Vec<char>>();
	let n:i32 = v[v.len() - 1].to_string().parse().ok().unwrap();
	if n == 2 || n == 4 || n == 5 || n == 7 || n == 9 {
		println!("hon");
	}else if n == 0 || n == 1 || n == 6 || n == 8 {
		println!("pon");
	}else{
		println!("bon");
	}
}

Measured memory_bytes: 2156
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i,l,r) for(int i=l;i<=r;i++)
int gr[100001];
int t,k;
int mex(unordered_set<int>s)
{
  int mex=0;
  while(s.find(mex)!=s.end())mex++;
  return mex;
}
int grundy(int n,int a[100])
{  
  
  if(gr[n]!=-1)return gr[n];
  unordered_set<int>s;
  for(int i=0;a[i]<=n && i<t;i++)
    s.insert(grundy(n-a[i],a));
  gr[n]=mex(s);
  return gr[n];
}
signed main()
{  // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //int n,k;
    memset(gr,-1,sizeof(gr));
    cin>>t>>k;
    int a[t];
    for(int i=0;i<t;i++)cin>>a[i];
      sort(a,a+t);

      for(int i=0;i<a[0];i++)
      {
        gr[i]=0;
      }
      gr[a[0]]=1;
     grundy(k,a);

     if(gr[k]!=0)cout<<"First"<<endl;
     else cout<<"Second"<<endl;

    return 0;
}

Measured memory_bytes: 21376
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <sstream>
#include <map>
#include <cstring>
#include <vector>
#include <queue>
#include <iomanip>
#include <stack>

using namespace std;
typedef long long ll;

ll ans, mx, sum, mn = 1e14, cnt;


ll arr[100001];
int main(){
	ll n;
	cin>>n;
	queue<long long> q; 

    for (ll i = 1; i <= 9; i++) 
        q.push(i); 
    for (ll i = 1; i <= 100000; i++) { 
        arr[i] = q.front(); 
        q.pop(); 
        if (arr[i] % 10 != 0) 
            q.push(arr[i] * 10 + arr[i] % 10 - 1);
        q.push(arr[i] * 10 + arr[i] % 10); 
        if (arr[i] % 10 != 9) 
            q.push(arr[i] * 10 + arr[i] % 10 + 1); 

    }
    cout<<arr[n];
      

}

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


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

//vector…可変長、データの大きさに合わせてサイズを変える
//list…双方向リスト、要素を挿入、削除の多いとき
//forward_list
//array…固定長配列
//set…集合
//multiset
//bitset…2進数、固定長ビット列
//map…連想配列、キーと値を関連付ける
//multimap
//deque
//stack…FILO
//queue…FIFO
//priority_queue…格納された最大値から順に取り出す
//pair…二つの値を一組
//tuple…複数の値を一組

template<typename T>
void remove(std::vector<T>& vector, char index) {
    vector.erase(vector.begin() + index);
}

template<class T>
T ma(std::vector<T> &v) {
    T maxi = 0;
    for(auto &i:v) maxi = max(maxi, i);
    return maxi;
}

template<class T>
T mi(std::vector<T> &v) {
    T mini = 0;
    for(auto &i:v) mini = min(mini, i);
    return mini;
}

template <class T>
T pow(T x, T y, T n = numeric_limits<T>::max()) {
    if(y == 0) return 1;
    if(y % 2 == 0) return pow((x * x) % n, y / 2);
    return (x * pow(x, y - 1)) % n;
}

#define rep(i, n, m) for (int i = n; i <= m; i++)
#define Rep(i, n, m) for (int i = m; i >= 1; i--)

typedef long long ll;
typedef unsigned long long ull;

/*
int gcd(int x, int y) {
    if (x < y) swap(x, y);
    return !y ? x : gcd(x % y, y);
}
*/
int main() {
    int p, q, r;
    cin >> p >> q >> r;

    int ans = 0;

    ans += p+q+r;

    ans -= max(p, max(q, r));

    cout << ans;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  ll n, p;
  cin >> n >> p;
  ll a = 2;
  if(n == 1){
    cout << p << endl;
  }else{
    ll maxi = 1;
    for(ll i = 1; pow(i , n) <= p; i++){
      if(p % (ll)pow(i, n) == 0){
        maxi = i;
      }
    }
    cout << maxi << endl;
  }

  /*
  map<ll, ll> m;
  ll maxi = p;
  while(a <= p) {
    if(p % a == 0){
      m[a]++;
      p /= a;
    }else{
      a++;
    }
  }
  ll ans = 1;
  for(int i = 2; i <= a; i++) {
    //cout << i << " " << m[i] << " ";
    if(m[i] >= n){
      ans *= pow(i, max((ll)1, m[i] / n));
    }
  }
  cout << ans << endl;
  */
  /*
  cout << endl;
  for(int i = 0; i < a; i++) {
    if(m[i] > 0){
      cout << i << " " << m[i] << " ";
    }
  }
  cout << endl;
  */
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
    int N, K;
    cin >> N >> K;

    cout << N - K + 1 << endl;

    return 0;
}


Measured memory_bytes: 256
use std::io::{self, Read};

fn main() {
    let mut n = String::new();
    io::stdin().read_to_string(&mut n).unwrap();

    let n: u64 = n.trim().parse().unwrap();

    let mut result: u64 = 0;
    for i in 1..=n {
        if i % 3 != 0 && i % 5 != 0 {
            result += i;
        }
    }

    println!("{}", result);
}


Measured memory_bytes: 2112
#include <stdio.h>

int main()
{
  int i,n;
  char str[200];
  scanf("%d", &n);
  scanf("%s", str);
  if(n%2){
    printf("No\n");
    return 0;
  }else{
    for(i=0;i<n/2;i++){
      if(str[i]!=str[i+n/2]){
	    printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 128
n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0

for b in x:
    # 整数にしていって，各popであまりをとる，一発目の値を各popで割った時のあまりがわかった
    if one_pop_count != 0:
        one_mod = (one_mod*2 + int(b) ) % one_pop_count
    zero_mod = (zero_mod*2 + int(b) ) % zero_pop_count

# f の前計算...popcountで割ったあまりをまたpopcountで割るの繰り返し
f = [0]*220000
pop_count = [0]*220000
for i in range(1,220000):
    pop_count[i] = pop_count[i//2] + i%2 # 最後の桁とそれ以外で分けるとpopcountできる
    f[i] = f[i % pop_count[i]] + 1

#pow2の前計算...2^iをpopcountで割ったあまりの計算
one_pow2 = [1]*220000
zero_pow2 = [1]*220000
for i in range(1, 220000): 
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

# n-1, n-2, ..., 0
for i  in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count # 負の数になっているから
            print(f[nxt]+1)
        else:
            print(0)
        
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt]+1)

Measured memory_bytes: 30120
#include<iostream>
using namespace std;
int main(){
	int x,y;
	cin>>x>>y;
	switch(x){
		case 1:
		case 3:
		case 5:
		case 7:
		case 8:
		case 10:
		case 12:
			switch(y){
				case 1:
				case 3:
				case 5:
				case 7:
				case 8:
				case 10:
				case 12:
					cout<<"Yes"<<endl;
				break;
				default:
					cout<<"No"<<endl;
				break;
			}
			break;
		break;
		case 4:
		case 6:
		case 9:
		case 11:
			switch(y){
				case 4:
				case 6:
				case 9:
				case 11:
					cout<<"Yes"<<endl;
				break;
				default:
					cout<<"No"<<endl;
				break;
			}
		break;
		case 2:
			if(y==2){
				cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		break;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1100000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)};
const int max_n = 1 << 20;

signed main() {
	int n;cin>>n;int l[2100];rep(i,n)cin>>l[i];
  sort(l,l+n);int ans = 0;
  rep(a,n){
    repd(b,a+1,n){
      int mm = abs(l[a]-l[b]), mx = l[a]+l[b];
      auto itr = upper_bound(l+b+1,l+n, mm),
          itrr = lower_bound(l+b+1,l+n, mx);
      int dif = distance(l,itrr)-distance(l,itr);
      ans += max((ll)0, dif);
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
#define INT_MAX 1<<30
const int mod = 1e9+7;


int main(){
    string s,t; cin >> s >> t;
    sort(all(s));
    sort(rall(t));
    if(s<t) puts("Yes");
    else puts("No");
}


Measured memory_bytes: 256
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}
import scala.collection.mutable.{Map, Queue, PriorityQueue}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  val N, M = in.next().toInt
  val pq = new PriorityQueue[Long]
  for (i <- 1 to N)
    pq.enqueue(in.next().toLong)

  ///
  for (_ <- 1 to M) {
    val now = pq.dequeue()
    pq.enqueue(now / 2)
  }
  val ans = pq.sum
  println(ans)

}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 56436
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int x, a, b;
    cin >> x >> a >> b;
    bool c = (abs(x-a)>abs(x-b));
    cout << (c?"B":"A") << endl;
}


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

using namespace std;

void solveA()
{
    int x;
    cin >> x;
    if (x == 7|| x == 5|| x == 3)
        cout << "YES\n";
    else
        cout << "NO\n";
}

void solveB()
{
    int a, b, c;
    cin >> a >> b >> c;

    int hp = max(a, b);
    hp = max(hp, c);

    int area;

    if (a == hp)
        area = (b * c) / 2;
    if (b == hp)
        area = (a * c) / 2;
    if (c == hp)
        area = (a * b) / 2;

    cout << area;
}

void solveC()
{
    int a, b;
    cin >> a >> b;
    if ((a*b) % 2 == 0)
        cout << "No\n";
    else
        cout << "Yes\n";
}

void solveD()
{
    int n, s=0, cp;

    cin >> n;
    cp = n;

    while (cp){
        s += cp%10;
        cp /= 10;
    }
    if (n % s == 0)
        cout << "Yes\n";
    else
        cout << "No\n";
}

void solveE()
{
    int n, t;

    cin >> n >> t;

    int rotas[n][2];

    int coast = INT_MAX;

    for (int i = 0; i < n; i++){

        cin >> rotas[i][0] >> rotas[i][1];

        if (rotas[i][1] < t){
            coast = min(coast, rotas[i][0]);
        }
    }
    if (coast == INT_MAX)
        cout << "TLE\n";
    else
        cout << coast << "\n";
}

void solveF()
{
    int k;
    cin >> k;
    int par = 0, impar = 0;
    for (int i = 1; i <= k ; i++){
        if (i % 2 == 0)
            par++;
        else
            impar++;
    }
    cout << par * impar << endl;
}

int main(int qtd, char* nome[])
{
    ios::sync_with_stdio(false);

    solveB();

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>
#include <bitset>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

struct mint {
    static const long long mod = 998244353;
    long long x;
    mint(long long x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod; return *this;}
    mint& operator-=(const mint& a) {if ((x += mod - a.x) >= mod) x -= mod; return *this;}
    mint& operator*=(const mint& a) {(x *= a.x) %= mod; return *this;}

    friend const mint operator+(const mint& a, const mint& b) { mint ret = a; return ret += b; }
    friend const mint operator-(const mint& a, const mint& b) { mint ret = a; return ret -= b; }
    friend const mint operator*(const mint& a, const mint& b) { mint ret = a; return ret *= b; }
    friend ostream& operator<<(ostream& s, const mint& a) { return s << a.x; }

    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2);}
    mint& operator/=(const mint a) { return (*this) *= a.inv();}
    friend const mint operator/(const mint& a, const mint& b) { mint ret = a; return ret /= b; }
};

using vm = vector<mint>;
using vvm = vector<vm>;
using vvb = vector<vb>;

int a, b, c, d;
vvm memo;
vvb checked;

mint rec(int h, int w) {
    if(checked[h][w]) return memo[h][w];
    mint ret;
    if(h == a && w == b) ret = 1;
    else if(h > a && w == b) ret = rec(h-1, w) * w;
    else if(h == a && w > b) ret = rec(h, w-1) * h;
    else ret = rec(h, w-1) * h + rec(h-1, w) * w - rec(h-1, w-1) * (h-1) * (w-1);
    checked[h][w] = true;
    return memo[h][w] = ret;
}

void solve() {
    cin >> a >> b >> c >> d;
    memo.assign(c + 1, vm(d + 1));
    checked.assign(c + 1, vb(d + 1, false));
    cout << rec(c, d) << endl;
    return;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

Measured memory_bytes: 75276
n = input().split()
x = input().split()
y = input().split()

start = int(n[2]) + 1
end = int(n[3]) + 1
for i in range(start, end):
    check = 0
    for x_c in x:
        if i <= int(x_c):
            check = 1
            break
    for y_c in y:
        if i > int(y_c):
            check = 1
            break 
    if check == 0:
        print("No War")
        exit()
print("War")

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

const long long MOD = 1e9 + 7;

int main()
{
    int n,m;
    cin >> n >> m;
    char z[n+1][m+1];
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin >> z[i][j];
        }
    }
    
    long long a[n+1][m+1] = {0};
    
    i = 1;
    j = 1;
    
    while(j<=m)
    {
        if(z[i][j] != '#')
        {
            a[i][j] = 1;
        }
        else
        {
            break;
        }
        j++;
    }
    
    j = 1;
    
    while(i<=n)
    {
        if(z[i][j] != '#')
        {
            a[i][j] = 1;
        }
        else
        {
            break;
        }
        i++;
    }
    
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=m;j++)
        {
            if(z[i][j] != '#')
            {
                a[i][j] = (a[i-1][j] + a[i][j-1])%MOD;
            }
            else
            {
                continue;
            }
        }
    }
    cout << a[n][m] % MOD;
}

Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  int w , h , n ;
  cin >> w >> h >> n ;
  vector<vector<char>> v(w,vector<char> (h,'.'));
  
  
  rep(i,n){
    int x , y , a ;
    cin >>x >> y >> a ;
    
    if(a==1){
      for(int i=0;i<x;i++){
        for(int j=0;j<h;j++){
          v.at(i).at(j) ='#';
        }
      }
    }
    
    if(a==2){
      for(int i=x;i<w;i++){
        for(int j=0;j<h;j++){
          v.at(i).at(j) ='#';
        }
      }
      
    }
    
    if(a==3){
      for(int i=0;i<w;i++){
        for(int j=0;j<y;j++){
          v.at(i).at(j) ='#';
        }
      }
      
    }
    
    if(a==4){
      for(int i=0;i<w;i++){
        for(int j=y;j<h;j++){
          v.at(i).at(j) ='#';
        }
      }
    
    }
  }
  
  int ans = 0;
    
    rep(i,w){
      rep(j,h){
        if(v.at(i).at(j) == '.') ans++;
      }
    }
  
  cout << ans ;
 
  
}


Measured memory_bytes: 256
def ABC122B():
    S = input()
    target = ['A', 'G', 'C', 'T']
    flag = False
    cnt = 0
    ans = 0
    for s in list(S):
        if s in target:
            cnt += 1
            if flag == False:flag = True
        if flag == True and s not in target:
            flag = False

            cnt = 0
        ans = max(ans, cnt)
    print(ans)

ABC122B()


Measured memory_bytes: 3060
def is_harhed_number(x):
    y = x
    numbox = []
    while y >= 10:
        p = y % 10
        numbox.append(p)
        y //= 10
    if (x % (y + sum(numbox))) == 0:
        return 'Yes'
    else:
        return 'No'
N = int(input())
print(is_harhed_number(N))

Measured memory_bytes: 2940
import math

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

X = []
for _ in range(N):
    temp = list(map(int, input().split()))
    X.append(temp)

ans = 0
for i in range(N):
    for j in range(i+1, N):
        d = 0
        for k in range(D):
            d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k])
        for z in range(130):
            if d == z**2:
                ans += 1
                break

print(ans)


Measured memory_bytes: 3064