akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int n;
int m;
int h[N];
int ans[N];

int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= n; i++){
        scanf("%d" , &h[i]);
    }
    for(int j = 1; j <= m; j++){
        int a, b;
        scanf("%d%d" , &a , &b);
        ans[a] = max(ans[a] , h[b]);
        ans[b] = max(ans[b] , h[a]);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(ans[i] < h[i]){
            cnt++;
        }
    }
    printf("%d\n" , cnt);
}


Measured memory_bytes: 4576
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]

dp=[-1]*(n+1)

dp[0]=1

dp[1]=1

for i in a:
  dp[i]=0
  

for i in range(2,n+1):
  if dp[i]!=0:
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    
print(dp[n])


Measured memory_bytes: 80668
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk)
{
  var arr = chunk.split(" ");
  w = Number(arr[0])
  h = Number(arr[1])
  x = Number(arr[2])
  y = Number(arr[3])
  r = Number(arr[4])
  if ((r <= x) && (r <= w - x) && (r <= y) && (r <= h - y)) {
    console.log("Yes")
  }else{
    console.log("No")
  }
});

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

int main(){
  int n,k;
  cin >> n >> k;
  int a[200010]={};
  int sum[200010]={};
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum[a[i]]++;
  }
  int ans = 0;
  sort(sum,sum+200010,greater<int>());
  for(int j=0;j<k;j++){
    ans += sum[j];
  }
  cout << n-ans << endl;
}

Measured memory_bytes: 1920
import collections

n = int(input())


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


x = 1

for i in range(1, n+1):
    x *= i

p = collections.Counter(prime_factorize(x))

q = list(p.values())
ans = 0

ans += sum(1 for i in q if i >= 74)

for i in range(len(q)):
    for j in range(len(q)):
        if i == j:
            continue
        if q[i] >= 4 and q[j] >= 14:
            ans += 1
        if q[i] >= 2 and q[j] >= 24:
            ans += 1

for i in range(len(q)):
    for j in range(i + 1, len(q)):
        for k in range(len(q)):
            if i == k or j == k:
                continue
            if q[i] >= 4 and q[j] >= 4 and q[k] >= 2:
                ans += 1

print(ans)


Measured memory_bytes: 3316
import itertools
import math

n, d = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for i in itertools.combinations(x, 2):
    length = 0
    for j in range(d):
        length += (i[0][j] - i[1][j]) ** 2
    if math.sqrt(length) % 1 == 0:
        ans += 1
print(ans)


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

using namespace std;

typedef long long int ll;

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

  ll d, g;
  cin >> d >> g;
  vector < ll > p(d), c(d);
  for(int i = 0; i < d; i++) cin >> p[i] >> c[i];

  ll ans = LLONG_MAX;
  for(int i = 0; i < (1 << 12); i++){
    ll sum = 0, cnt = 0, ind = -1;
    for(int j = 0; j < d; j++){
      if((i >> j) & 1){
        sum += (j + 1) * p[j] * 100 + c[j];
        cnt += p[j];
      }
      else ind = j;
    }
    if(sum >= g){
      ans = min(ans, cnt);
      continue;
    }

    ll c = (ind + 1) * 100;
    ll nxt = (g - sum) / c;
    if(((g - sum) % c) != 0) nxt++;

    if(nxt >= p[ind]) continue;
    ans = min(ans, nxt + cnt);
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
def CountingSort(A, k):
    n = len(A)
    B = [0]*n
    C = [0]*(k+1)

    for j in range(n):
        C[A[j]] += 1

    for i in range(1,k):
        C[i] = C[i] + C[i-1]

    for j in range(n-1,-1,-1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
            
    return B

n = int(input())
*A, = map(int,input().split())

k = 10000
out = CountingSort(A,k)

print(*out, sep=" ")




Measured memory_bytes: 224504
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define all(v)  v.begin(),v.end()
#define pb push_back
#define size(v)  (int) v.size()
#define fast ios_base:: sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
ll power_mod(ll a,ll x){if(x==0) return 1;ll y=power_mod(a,x/2);ll ans=(y*y)%mod; if(x%2) ans=(ans*a)%mod;return ans;}
ll inv(ll a){return power_mod(a,mod-2);}
ll power(ll a, ll x){ if(x==0) return 1; ll y= power(a,x/2); ll ans=(y*y); if(x%2) ans*=a; return ans;}




int main()
{
   

   int n;
   cin>>n;
   int a[n+1];
   for(int i=1;i<=n;i++) cin>>a[i];
    int ct=0,mx=0;
   for(int i=1;i<=n;i++)
   {  
       if(a[i]>=mx)
       {
          mx=a[i];
          ct++;
       }
   }

   cout<<ct<<endl;
}




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

using namespace std;

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

    pair<int, int> p[n];
    for(int i=0; i<n; i++){
        int t1, t2;
        cin >> t1 >> t2;
        p[i] = make_pair(t1, t2);
    }

    int dp[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            dp[i][j] = 1000000000;
            if(i==j) dp[i][j] = 0;
        }
    }

    for(int l=2; l<=n; l++){
        for(int i=0; i<n-l+1; i++){
            int j = i+l-1;
            for(int k=i; k<j; k++){
                int t = p[i].first*p[k].second*p[j].second;
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+t);
            }
        }
    }

    cout << dp[0][n-1] << endl;

    return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
#include <numeric>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n,k,x,y;
    cin >> n >> k >> x >> y;
    cout << (n<k?n*x:k*x+(n-k)*y) << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x;
	cin>>x;
	vector<bool> expo(x+1);
	expo[1]=1;
	for (int b=2;b<=x;b++)
	{
		int v=b*b;
		while(v<=x)
		{
			expo[v]=1;
			v*=b;
		}
	}
	for (int i=x;i>=1;i--)
	if(expo[i])
	{
		cout<<i<<endl;
		return 0;
	}
	return 0;
}

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

typedef long long ll;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

// bool compPair(const pair<int, int>& arg1, const pair<int, int>& arg2) {
//     return arg1.first > arg2.first;
// }

// template<class T> void chmin(T& a, T b) {
//     if (a > b) {
//         a = b;
//     }
// }

// template<class T> void chmax(T& a, T b) {
//     if (a < b) {
//         a = b;
//     }
// }

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

    if(n%10==7) { 
        cout << "Yes" << endl;
        return 0;
    }
    else n -= n%10;

    if((n%100)/10==7) { 
        cout << "Yes" << endl;
        return 0;
    }
    else n -= n%100;

    if((n%1000)/100==7) { 
        cout << "Yes" << endl;
        return 0;
    }
    else cout << "No" << endl;
    
    return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define fora(i,a,b) for(int i = a ; i<b ;i++)
typedef long long ll;
typedef int i;
typedef vector<i>vi;
typedef pair<i,i>pi;

ll w[100010];
ll v[100010];
ll dp[110][100010];
ll f(int i, ll W){
    if(W < 0) return -1e9;
    if(i == 0) return 0;
    ll &r = dp[i][W];
    if(r !=-1) return r;
    r = max( f(i-1 ,W)  , f(i-1 , W-w[i])+v[i]);
    return r;
}
int main(){
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll W;
    cin>>n>>W;
    memset(dp,-1,sizeof dp);
    fora(i,1,n+1){
        cin>>w[i]>>v[i];
    }
    cout<<f(n,W)<<"\n";
    return 0;
}

Measured memory_bytes: 89596
N=int(input())
lx=list(map(int,input().split()))
pav=sum(lx)/N
a=int(pav)
b=a+1
sa=0
sb=0
for i in range(N):
    sa+=(lx[i]-a)**2
    sb+=(lx[i]-b)**2
print(min(sa,sb))


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}




const long double PI = 3.14159265359;
const int MAX_N = 100010;

int dp[101000];
int h[101000];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k; cin >> n >> k;
	rep(i, n)cin >> h[i];
	rep(i, 101000)dp[i] = INF;
	dp[0] = 0;
	rep(i, n) {
		rep(j, k) {
			chmin(dp[i + j + 1], dp[i] + abs(h[i] - h[i + j + 1]));
		}
	}
	cout << dp[n - 1] << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main()
{
    int H,N;
    cin >> H >> N;
    int arr[N];
    for (int i=0;i<N;i++){
        cin >> arr[i];
        H  = H - arr[i];
    }
    if(H > 0){
        cout << "No";
    }
    else{
        cout << "Yes";
    }


    return 0;
}


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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)


int main()
{
  string s;
  cin >> s;
  ll c=0;
  forll(i, 1, s.size()){
	if (s[i-1] != s[i])
	  c++;
  }
  cout << c << endl;
}



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

int main() {
long long int n,count=0;
cin>>n;
long long int a[n];
for(int i=0;i<n;i++){
    cin>>a[i];
    if((i+1)%2!=0&&a[i]%2!=0)
    count++;
}
cout<<count;
}


Measured memory_bytes: 3620
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define rep(i,n) for(int i=0; i <(n); i++)
int main(){
  int n;
  long a[100000];
  scanf("%d",&n);
  rep(i,n){
    scanf("%lld",&a[i]);
  }
  int x=0,y=0,z=0;
  rep(j,n){
    if(a[j]%4==0){
      x++;
    }else if(a[j]%2==0){
      y++;
    }else{
      z++;
    }
  }
  if(x==z-1){
    if(n%2==1&&y==0){
      printf("Yes\n");
      return 0;
    }
  }else if(x>z-1){
    printf("Yes\n");
    return 0;
  }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 896
import java.util.Scanner;

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static String I = "IMPOSSIBLE";
	public static String B = "Bad";
	public static String G = "Good";
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int a = ni();
		int b = ni();
		int c = ni();

		outn(c + " ");
		outn(a + " ");
		out(b);

	}

	/*
	 * 以下メソッド集
	 */
	static int ni() {
		return sc.nextInt();
	}

	static long nl() {
		return sc.nextLong();
	}

	static String n() {
		return sc.next();
	}

	static char[] nc() {
		return sc.next().toCharArray();
	}

	static int kaijo(int n) {
		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {
		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(String info) {
		System.out.println(info);
	}

	static void out(int info) {
		System.out.println(info);
	}

	static void out(double info) {
		System.out.println(info);
	}

	static void out(long info) {
		System.out.println(info);
	}

	static void out(char info) {
		System.out.println(info);
	}

	static void outn(String info) {
		System.out.print(info);
	}

	static void outn(int info) {
		System.out.print(info);
	}

	static void outn(double info) {
		System.out.print(info);
	}

	static void outn(long info) {
		System.out.print(info);
	}

	static void outn(char info) {
		System.out.print(info);
	}

	static int max(int a, int b) {
		return Math.max(a, b);
	}

	static long max(long a, long b) {
		return Math.max(a, b);
	}

	static int min(int a, int b) {
		return Math.min(a, b);
	}

	static long min(long a, long b) {
		return Math.min(a, b);
	}
}

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

int main(){
  int k,u,p,c;
  string s;

  cin >> s;

  k = u = p = c = 0;
  for(int i=0;i<(int)s.size();i++){
    if(s[i] == 'K')k++;
    if(s[i] == 'U')u++; 
    if(s[i] == 'P')p++;
    if(s[i] == 'C')c++;
  }

  if(k>u)k = u;
  if(p>c)p = c;
  if(k>p)k = p;

  printf("%d\n",k);
}

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

using namespace std;

/*

        Bismillahir Rahmanir Rahim
        Problem :
        Problem Link :
        Topics :
        Solver : Masud Parves
        I Love Code More than Sharks Love Blood <3
*/


#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define SZ(a)           (int)a.size()
#define all(a)  a.begin(), a.end()
#define allr(a)  a.rbegin(), a.rend()


#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)

#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)

#define CIN ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define TEST_CASE(t) for(int zz=1 ; zz<=t ; zz++)
#define PRINT_CASE printf("Case %d: ",zz)
#define Debug(x)            cout<<#x " = "<<(x)<<endl
#define NOT_VISITED 0
#define IS_VISITED 1
#define WHITE 0
#define GRAY 1
#define BLACK 2



int fx[4]= {1,-1,0,0};
int fy[4]= {0,0,1,-1};

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N  (1<<pos);}
//int Reset(int N,int pos){return N= N & ~(1<<pos);}
//bool Check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


const double PI = acos(-1.0);
const double EPS = 1e-6;
const int MOD = (int)1e9+7;
const int maxn = (int)2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;

bool MMYY(int m, int y){

    if(m==0 || m>12) return 0;
    return 1;
}

bool YYMM(int y, int m){
    if(m==0 || m>12) return 0;
    return 1;
}

int main() {
    CIN
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    string s;
    cin >> s;
    int f=(s[0]-48)*10+(s[1]-48);
    int ss=(s[2]-48)*10+(s[3]-48);

    //cout << f <<" "<<ss<< endl;

    //cout << MMYY(f, ss) << endl;
    if(MMYY(f, ss)==1 && YYMM(f, ss)==1){
        cout << "AMBIGUOUS" << endl;
    }else if(MMYY(f, ss)){
        cout << "MMYY" << endl;
    }else if(YYMM(f, ss)){
        cout << "YYMM" << endl;
    }else cout << "NA" << endl;

    return 0;
}



Measured memory_bytes: 256
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = collections.Counter(il())

    ret = 0
    for k in A:
        v = A[k]
        if k <= v:
            ret += abs(k-v)
        else:
            ret += v
    print(ret)


if __name__ == '__main__':
    main()


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

using namespace std;
#define rep(i, n) for(int i = 0 ; i < (int)(n) ; i++)
typedef long long ll;
typedef long double Double;

#ifndef INPUTS_DIR
#define INPUTS_DIR "./"
#endif


void solve(ll N, ll A, ll B, vector<ll> X) {
    long long ans = 0;
    for (int i = 0; i + 1 < N; i++) {
        ans += min(B, A * (X[i + 1] - X[i]));
    }
    cout << ans << endl;
}


void main_(istream &cin) {
    ll A;
    ll N;
    ll B;
    cin >> N;
    vector<ll> X(N - 1 + 1);
    cin >> A;
    cin >> B;
    for (int i = 0; i <= N - 1; i++) {
        cin >> X[i];
    }
    solve(N, A, B, X);
}

int main() {
#ifdef INTELLIJ
    ifstream ifs(string(INPUTS_DIR) + "in_1.txt");
    if (ifs.is_open()) {
        main_(ifs);
        ifs.close();
    } else {
        cerr << "Error: no input." << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    main_(cin);
#endif
}





Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
////////////////////
int main() {
    string N;
    cin >> N;
    // N = "575";
    string s(N.rbegin(), N.rend());
    
    if(N == s) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 200000;

int n, p, q;
int eu[MaxN], ev[MaxN];

struct halfEdge
{
	int v;
	halfEdge *next;
};
halfEdge adj_pool[MaxN * 2], *adj_tail = adj_pool;
halfEdge *adj[MaxN + 1];

inline void addEdge(const int &u, const int &v)
{
	adj_tail->v = v, adj_tail->next = adj[u];
	adj[u] = adj_tail++;
}

inline void adj_init()
{
	adj_tail = adj_pool;
	for (int u = 1; u <= n; ++u)
		adj[u] = NULL;
}

int dfs_clock = 0;
int dfn_l[MaxN + 1], dfn_r[MaxN + 1];

int dep[MaxN + 1];

int fa[MaxN + 1];

void dfs1(int u)
{
	dfn_l[u] = ++dfs_clock;

	for (halfEdge *e = adj[u]; e; e = e->next)
		if (e->v != fa[u])
		{
			fa[e->v] = u;
			dep[e->v] = dep[u] + 1;
			dfs1(e->v);
		}

	dfn_r[u] = dfs_clock;
}

inline bool valid(int u, int v)
{
	if (dfn_l[u] > dfn_l[v])
		swap(u, v);
	if (dfn_l[v] <= dfn_r[u])
		return dep[v] - dep[u] <= 2;
	return fa[u] == fa[v];
}

bool inv[MaxN + 1];

int dist[MaxN + 1];
bool vis[MaxN + 1];

void dfs2(int u)
{
	vis[u] = true;

	for (halfEdge *e = adj[u]; e; e = e->next)
		if (!vis[e->v])
		{
			dist[e->v] = dist[u] + 1;
			if (dist[e->v] < dep[e->v])
				dfs2(e->v);
		}
}

inline int query()
{
	int res = 0;
	for (int u = 1; u <= n; ++u)
		if (vis[u])
		{
			res = max(res, dep[u]);
			if (inv[u])
				return -1;
		}
	return res * 2;
}

int main()
{
	cin >> n >> p >> q;
	for (int i = 1; i < n; ++i)
		eu[i] = getint(), ev[i] = getint();
	for (int i = 1; i < n; ++i)
	{
		int u = getint(), v = getint();
		addEdge(u, v);
		addEdge(v, u);
	}

	dfs1(q);

	adj_init();

	for (int i = 1; i < n; ++i)
	{
		int u = eu[i], v = ev[i];
		if (!valid(u, v))
			inv[u] = inv[v] = true;
		else
		{
			addEdge(u, v);
			addEdge(v, u);
		}
	}

	dfs2(p);

	cout << query() << endl;

	return 0;
}

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

#define mod 1000000007 
typedef long long ll;
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fre freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define int long long
#define read(t) int t; cin>>t;
#define read2(x,y) int x,y; cin >> x >> y;
#define read3(x,y,z) int x,y,z; cin >> x >> y >> z;
#define read4(a,b,c,d) int a,b,c,d; cin >> a >> b >> c >> d;
#define f(a,b,c) for(int a=b;a<c;++a)
#define readarr(arr,n) int* arr = new int[n]; f(i,0,n) cin>>arr[i];
#define printarr(arr,n) f(i,0,n) cout << arr[i] << space; cout << line;
#define INF INT_MAX
#define line "\n"
#define space " "
#define vi vector<int> 
#define vii vector<vi>
#define mp make_pair
#define pb push_back
#define zero 0LL


struct Vector{
    double x; double y;
    Vector(double X, double Y){
        x = X;
        y = Y;
    }
    double mag(){
        return sqrt(pow(x,2) + pow(y,2));
    }
    double polar(){
        double _angle = atan2(y,x);
        return _angle;  
    }
    Vector operator + (Vector const &vec){
        Vector res(vec.x + x,vec.y + y);
        return res;
    } 
};

bool SortbyAngle(Vector a, Vector b){
    return a.polar() < b.polar();
}

int32_t main(){
    speed;
    #ifdef LOCAL
        fre;
    #endif
    read(n);
    vector<Vector> v;
    f(i,0,n){
        double x,y; 
        cin >> x >> y;
        v.pb(Vector(x,y));
    }
    sort(v.begin(),v.end(),SortbyAngle);
    double _max = 0;
    f(i,0,n){
        Vector test = v[i];
        _max = max(_max,test.mag());
        int counter = n - 1; int j = i+1;
        f(i,0,counter and j != i){
            test = test + v[j];
            _max = max(_max,test.mag());
            j = (j+1) % n;
        }
        
    }
    cout << setprecision(13) << _max << line;
    return 0;
}


Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        char c = s.next().charAt(0);
        if(c>='a'&&c<='z') System.out.println('a');
        else System.out.println('A');



    }

}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {return Integer.parseInt(next());}

    public long nextLong() throws IOException {return Long.parseLong(next());}

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25312
using System;
using System.Linq;
namespace ConsoleTest {
  class Program {
    static void Main(string[] args) {
      Console.ReadLine();
      int[] a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
      int max = a[0];
      for (int i = 1; i < a.Length; i++) {
        max = max > a[i] ? max : a[i];
      }
      int min = a[0];
      for (int i = 1; i < a.Length; i++) {
        min = min < a[i] ? min : a[i];
      }
      Console.WriteLine(max - min);
    }
  }
}

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

int main()
{
    int b[] = {1, 0, 0};
    char x, c, y;
    while(cin >> x >> c >> y) {
        int xi = x - 'A';
        int yi = y - 'A';
        int tmp = b[xi]; b[xi] = b[yi]; b[yi] = tmp;
    }
    for (int i = 0; i < 3; ++i) {
        if (b[i]) {
            cout << (char)('A' + i) << endl;
            break;
        }
    }
}



Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n;
	cin >> n; 
	vector<int> a(n);
	for(int i=0;i<n;i++)
		cin >> a[i];

	long long mxkabu=0,mxkabu_kane=0,mxkane=1000;

	for(int i=0;i<n;i++)
	{
		long long tmp=max(mxkane,mxkabu*a[i]+mxkabu_kane);
		if(mxkabu>mxkane/a[i])
			mxkabu=mxkabu;
		else if(mxkabu==mxkane/a[i])
		{
			mxkabu_kane=max(mxkabu_kane,mxkane%a[i]);
		}
		else
		{
			mxkabu=mxkane/a[i];
			mxkabu_kane=mxkane%a[i];
		}
		mxkane=tmp;
//		cerr << mxkane << " " << mxkabu << " " << mxkabu_kane << endl;
	}

	cout << mxkane << endl;




}

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

using namespace std;


#define PI 3.14159265
#define int long long


main(){

	int n, m; cin >> n >> m;


	vector <int> x(m);

	for(int i = 0; i < m; i++){
		cin >> x[i];
	}

	if(m <= n){
		cout << 0 << endl; return 0;
	}

	sort(x.begin(), x.end());


	vector <int> d;

	for(int i = 1; i < m; i++){
		d.push_back(x[i] - x[i - 1]);
	}


	sort(d.begin(), d.end());


	int sum = 0;
	for(int i = 0; i < m - n; i++){
		sum += d[i];
	}

	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 2168
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);

	int N,M,a,b;
    bool judge=false;
	cin >> N;
    cin >> M;
    vector<vector<int>> ship(N+2);

    for(int i=0;i<M;i++){
        cin >> a;
        cin >> b;
        ship[a].push_back(b);
        ship[b].push_back(a);
    }
    queue<int> task;
    for(int i=0;i<ship[1].size();i++){
        task.push(ship[1][i]);
    }
    while(!task.empty()){
        int t=task.front();
        task.pop();
        for(int i=0;i<ship[t].size();i++){
            if(ship[t][i]==N){
                judge=true;
            }
        }
    }
    if(judge) cout << "POSSIBLE" << "\n";
    else cout << "IMPOSSIBLE" << "\n";
}

Measured memory_bytes: 12400
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cfloat>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

#define ITER( c ) __typeof( (c).begin() )
#define IREP( c, it ) for ( ITER(c) it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

	int casenum = 1;

	while ( true )
	{
		int w;
		cin >> w;

		if ( !w )
		{
			break;
		}

		int n;
		cin >> n;

		vector< PII > tres( n );
		EACH( tre, tres )
		{
			char dummy;

			cin >> tre.fst >> dummy >> tre.snd;
		}

		VVI dp( n + 1, VI( w + 1, 0 ) );

		REP( i, 0, n )
		{
			REP( j, 0, w + 1 )
			{
				dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] );

				if ( j + tres[i].snd <= w )
				{
					dp[ i + 1 ][ j + tres[i].snd ] = max( dp[ i + 1 ][ j + tres[i].snd ], dp[i][j] + tres[i].fst );
				}
			}
		}

		int resnum = -1, resmax = 0;

		REP( i, 0, w + 1 )
		{
			if ( resmax < dp[n][i] )
			{
				resnum = i;
				resmax = dp[n][i];
			}
		}

		cout << "Case " << casenum++ << ':'<< endl;
		cout << resmax << endl;
		cout << resnum << endl;
	}

	return 0;
}

Measured memory_bytes: 5040
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus >= 201703L
#        pragma GCC target("avx2")
#    else
#        pragma GCC target("avx")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    string s;
    cin >> s;

    int n = s.size();
    vector<int> ans(n);

    for (int i = 0; i < n;) {
        int r = 0, l = 0;
        int index = 0;

        while (s[i] == 'R') {
            r++;
            i++;
        }
        index = i - 1;
        while (s[i] == 'L') {
            l++;
            i++;
        }

        int len = (l + r) / 2;
        if ((r + l) % 2 == 0) {
            ans[index] = len;
            ans[index + 1] = len;
        } else {
            if (r % 2 == 1) {
                ans[index] = len + 1;
                ans[index + 1] = len;
            } else {
                ans[index] = len;
                ans[index + 1] = len + 1;
            }
        }
    }

    for (int i = 0; i < n - 1; i++) {
        cout << ans[i] << ' ';
    }
    cout << ans[n - 1] << endl;

    return 0;
}


Measured memory_bytes: 1104
var
	a,b,c,lt,sum:integer;
 
begin
	lt := 0;
	read(a,b,c);
    
    lt := a - b;
    sum := c - lt;
    
    begin
    if sum > 0 then
   	 writeln(sum)
    else 
     writeln('0');
    end;
 	
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

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

    string S; cin >> S;
    F0R(i, sz(S) - 1) {
    	if (S[i] == S[i+1]) {
    		cout << "Bad" << endl;
    		return 0;
    	}
    }

    cout << "Good";

    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 764
#include<iostream>
#include<cstdio>

using namespace std;

int main()
{
    int N;
    cin >> N;
    if(N==1)cout<<"Hello World"<<endl;
    else{
            int a,b;
        cin >>a>>b;
        cout<<a+b<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

ll a[300001];
ll sum1[100001]; // sum1[i] : 0～N+i-1番目までのaのうち、大きい順にN個の取った和
				 // iは0からNまでのN+1通り

ll sum2[100001]; // sum2[i] : N+i～3N-1番目までのaのうち、小さい順にN個取った和

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

	int N; cin >> N;
	for (int i = 0; i < 3*N; i++) cin >> a[i];

	priority_queue<ll, vector<ll>, greater<ll>> P1; // 前半のうち大きい順にN個

	sum1[0] = 0LL;
	for (int i = 0; i < N; i++) {
		P1.push(a[i]);
		sum1[0] += a[i];
	}
	for (int i = 1; i <= N; i++) {
		sum1[i] = sum1[i - 1];
		if (a[N + i - 1] > P1.top()) { // 今までに取ったN個のうちの最小値より大きかったら交換
			sum1[i] += (a[N + i - 1] - P1.top());
			P1.pop();
			P1.push(a[N + i - 1]);
		}
	}
	
	priority_queue<ll> P2;                            // 後半のうち小さい順にN個
	sum2[N] = 0LL;

	for (int i = 0; i < N; i++) {
		P2.push(a[2 * N + i]);
		sum2[N] += a[2 * N + i];
	}
	for (int i = 1; i <= N; i++) {
		sum2[N - i] = sum2[N - i + 1];
		if (a[2 * N - i] < P2.top()) {
			sum2[N - i] -= (P2.top() - a[2 * N - i]);
			P2.pop();
			P2.push(a[2 * N - i]);
		}
	}
	
	ll ans = -LLINF;
	int pos = 0;
	for (int i = 0; i <= N; i++) {
		if (ans <= (sum1[i] - sum2[i])) {
			ans = sum1[i] - sum2[i];
			pos = i;
		}
	}

	/*
	for (int i = 0; i <= N; i++) cout << sum1[i] << " "; cout << endl;
	for (int i = 0; i <= N; i++) cout << sum2[i] << " "; cout << endl;
	*/

	//cout << pos << endl;
	cout << ans << endl;
	
	

	return 0;
}

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

int main()
{
    vector<vector<int>> c(3,vector<int>(3));
    for(int i = 0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin >> c[i][j];
        }
    }
    
    bool ok = true;
    int a,b;
    
    a = c[0][1] - c[0][0];
    b = c[0][2] - c[0][1];

    int p,q;
    
    p = c[1][0] - c[0][0];
    q = c[2][0] - c[1][0];
    
    if(a != c[1][1] - c[1][0] || a != c[2][1] - c[2][0])
    {
        ok = false;
    }
    else if(b != c[1][2] - c[1][1] || b != c[2][2] - c[2][1])
    {
        ok = false;
    }
    else if(p != c[1][1] - c[0][1] || p != c[1][2] - c[0][2])
    {
        ok = false;
    }
    else if(q != c[2][1] - c[1][1] || q != c[2][2] - c[1][2])
    {
        ok = false;
    }
    
    if(ok)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    
    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    string a;
    cin>>a;
    for(int i=0;i<3;i++){
        if(a[i]=='1'){
            a[i]='9';
        }
        else if(a[i]=='9'){
            a[i]='1';
        }
    }
    cout<<a<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <queue>
#include <limits>
using namespace std;

typedef pair<double, int> P;

int x[1002], y[1002], r[1002];
double cost[1002][1002];
double d[1002];

int main()
{
    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);
    r[0] = r[1] = 0;

    int N;
    scanf("%d", &N);
    N += 2;
    for (int i = 2; i < N; i++)
        scanf("%d%d%d", &x[i], &y[i], &r[i]);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cost[i][j] = max(hypot(x[i] - x[j], y[i] - y[j]) - r[i] - r[j], 0.);

    for (double &nd : d)
        nd = numeric_limits<double>::infinity();
    d[0] = 0;
    priority_queue<P> q;
    q.push(P(0, 0));

    while (!q.empty()) {
        auto p = q.top();
        double nowd = -p.first;
        int v = p.second;
        q.pop();
        if (nowd < d[v])
            continue;
        for (int i = 0; i < N; i++) {
            double nextd = d[v] + cost[v][i];
            if (d[i] > nextd) {
                d[i] = nextd;
                q.push(P(-nextd, i));
            }
        }
    }

    printf("%.12f\n", d[1]);
}


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

#define int long long int
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define endl "\n"

int32_t main()
{
	IOS;
	int a, b, c;
	cin >> a >> b >> c;
	map<int, int>m;
	m[a]++;
	m[b]++;
	m[c]++;
	if (m[5] == 2 && m[7] == 1)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;


	return 0;
}

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

int main(){
	int a,b,c,x;
	cin >> a >> b >> c >> x;
  	ll ans=0;
  	rep(i,a+1)rep(j,b+1)rep(k,c+1)if(i*500+j*100+k*50==x)ans++;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    char s[200001];
    int i=0, ans=0, cnt=0;
    scanf("%s", s);
    while(s[i]!='\0'){
        if(cnt==0 && s[i]=='A'){
            cnt++;
            ans++;
        }
        else if(cnt>0) cnt++;
        if(s[i]=='Z') ans=cnt;
        i++;
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 384
n=int(input())
A=list(map(int,input().split()))

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self): #popせずに見るだけ
        return self.hq[0] * self.sign
    
hq=Heapq(A[:n]) ; L=[0]*(n+1) ; L[0]=sum(A[:n])
hq2=Heapq(A[2*n:],1) ; R=[0]*(n+1) ; R[-1]=sum(A[n*2:])
ans=-2**62
for i in range(n,2*n):
    ku= hq.pop()
    ire= max(ku, A[i])
    L[i-n+1]= L[i-n]+ire-ku
    hq.push(ire)
    #
    ku=hq2.pop()
    ire= min(ku,A[-i-1])
    R[-(i-n+2)]= R[-(i-n+1)]+ire-ku
    hq2.push(ire)
#print(L,R)
for i in range(n+1):
    ans=max(ans, L[i]-R[i])
print(ans)

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

typedef long long ll;
using namespace std;
const long long int divisor = 2019; // not prime!!!!

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll L, R;
    cin >> L >> R;
    ll ans = 2020;
    if (R / divisor - L / divisor) { // p≡0 mod 2019なるpをLR間にとれる
        ans = 0;
    } else {
        for (ll i = L; i <= R - 1; ++i) {
            for (ll j = i + 1; j <= R; ++j) {
                long long int residual = i * j % divisor;
                if (!residual) {
                    ans = 0;
                    break;
                }
                ans = min(ans, residual);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}


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

int main(){
  int n,m;
  cin >> n >> m;
  priority_queue<int> q;
  rep(i,n){
    int a;
    cin >> a;
    q.push(a);
  }
  rep(i,m){
    int a = q.top(); q.pop();
    q.push(a/2);
  }
  
  ll ans = 0;
  rep(i,n){
    ans += q.top(); q.pop();
  }
  cout << ans << endl;
}


Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>




typedef long long ll;
#define PI 3.14159265359
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define mp make_pair
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBAC
#include <functional>
/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;*/
//copy(v1.begin(), v1.end(), back_inserter(v2));
using namespace std;

ll gcd(ll a, ll b) {
	ll c;
	if (a < b) {
		c = a; a = b; b = c;
	}
	while (b != 0) {
		c = a % b; a = b; b = c;
	}
	return a;
}

ll lcm(ll a, ll b) {
	ll c;
	c = a * b / gcd(a, b);
	return c;
}

int sort_greater(int m, int n) {
	vector<int> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < n; i++) {
		cout << a[i];
	}
	return 0;
}

int bubblesort(int a[], int n) {
	int sw = 0;
	bool flag = 1;
	for (int i = 0; flag; i++) {
		flag = 0;
		for (int j = n - 1; j >= i + 1; j--) {
			if (a[j] < a[j - 1]) {
				swap(a[j], a[j - 1]);
				flag = 1;
				sw += 1;
			}
		}
	}
	return sw;
}

int a_z()
{
	for (int i = 0; i <= ('Z' - 'A'); i++) {
		cout << (char)('A' + i);
	}
	return 0;
}

int selecttionsort(int a[], int n) {
	int t, sw = 0, minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = 0; j < n - 1; j++) {
			if (a[j] < a[minj]) {
				minj = j;
			}
		}
		t = a[i]; a[i] = a[minj]; a[minj] = t;
		if (i != minj) sw += 1;

	}
	return sw;
}

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

const ll mod = 1000000007;

map<string, int> memo;

using P=pair<int, int>;

/*void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) continue;
		ans[u] += ans[v];
		dfs(u, v);
	}
}*/
ll findIndex(int value, vector<ll> a)
{

	for (ll i = 0; i < (ll)a.size(); i++) {
		if (a[i] == value) {
			return i;
		}
	}
	return -1;
}

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

void comb(vector<vector <long long int> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (ll j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}

const int INF = 1001001001;

int main() {
	int n; 
	cin >> n;
	bool a = false;
	rep(i, n / 4+1) {
		rep(j, n/7+1) {
			if (i * 4 + 7 * j == n) {
				a = true;
				break;
			}
		}
	}
	if (a == true)cout << "Yes";
	else cout << "No";
	return 0;
}













Measured memory_bytes: 256
n = int(input())
C = []
S = []
F = []
for _ in range(n-1):
  c,s,f = map(int, input().split())
  C.append(c)
  S.append(s)
  F.append(f)

for i in range(n-2):
  ans = C[i]+S[i]
  for j in range(i+1, n-1):
    if S[j] >= ans:
      ans += (S[j]-ans) + C[j]
    else:
      if (ans-S[j])%F[j] == 0: ans += C[j]
      else: ans += F[j] - (ans-S[j])%F[j] + C[j]
  print(ans)
print(C[-1]+S[-1])
print(0)

Measured memory_bytes: 3188
s = input()

f = 1
c = 0

for i in range(len(s)):
    on = 0
    if i==0:
        if not s[i]=='A':
            f = 0
        else:
            on = 1
    elif i>=2 and i<=len(s)-2:
        if s[i] == 'C':
            c += 1
            on = 1
            
    if on == 0 and s[i].islower()==False:
        f = 0
        
if c!=1:
    f=0
    
if f==0:
    print("WA")
else:
    print("AC")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <array>
#include <complex>
#include <cmath>
#include <iomanip>

using Comp = std::complex<double>;

constexpr double Eps = 0.00000001;
constexpr double Inf = 1000000000;

double cross(const Comp& a, const Comp& b) {
	return a.real() * b.imag() - a.imag() * b.real();
}

bool intersects(const Comp& s1, const Comp& l1, const Comp& s2, const Comp& l2) {
	double c12 = cross(l1, l2);
	if (std::abs(c12) <= Eps)
		return false;

	const Comp l = s2 - s1;
	double t1 = cross(l, l1) / c12;
	double t2 = cross(l, l2) / c12;
	return 0 <= t1 && t1 <= 1 && 0 <= t2 && t2 <= 1;
}

struct Circle {
	Comp center;
	double r;

	std::array<Comp, 2> intersections(const Circle& c) const {
		double l = std::abs(c.center - center);
		Comp n_l = (c.center - center) / l;

		double theta = std::acos((r*r + l * l - c.r * c.r)/(2*r*l));

		return {
			center + std::polar(r, theta) * n_l,
			center + std::polar(r, -theta)* n_l
		};
	}
};

int main() {
	int n;
	while (std::cin >> n, n != 0) {
		std::vector<Circle> circles(n);
		for (auto&& c : circles) {
			int x, y;
			std::cin >> x >> y >> c.r;
			c.center = Comp(x, y);
		}

		std::vector<std::array<Comp, 2>> iss(n - 1);
		for (int i = 0; i < n - 1; ++i)
			iss[i] = circles[i].intersections(circles[i + 1]);

		auto isValid = [&](const Comp& a, const Comp b, int s, int t) {
			for (int i = s; i < t; ++i)
				if (!intersects(a, b - a, iss[i][0], iss[i][1] - iss[i][0]))
					return false;

			return true;
		};

		std::vector<std::array<double, 2>> dp(n - 1, {Inf, Inf});

		dp[0][0] = std::abs(iss[0][0] - circles[0].center);
		dp[0][1] = std::abs(iss[0][1] - circles[0].center);
		for (int i = 2; i / 2 < n - 1; ++i) {
			if (isValid(circles[0].center, iss[i / 2][i % 2], 0, i / 2))
				dp[i / 2][i % 2] = std::abs(iss[i / 2][i % 2] - circles[0].center);

			for (int j = 0; j / 2 < i / 2; ++j) {
				if (isValid(iss[j / 2][j % 2], iss[i / 2][i % 2], j / 2 + 1, i / 2)) {
					dp[i / 2][i % 2] = std::min(
						dp[i / 2][i % 2],
						dp[j / 2][j % 2] + std::abs(iss[i / 2][i % 2] - iss[j / 2][j % 2])
					);
				}
			}
		}

		double ans = Inf;
		if (isValid(circles[0].center, circles[n - 1].center, 0, n - 1))
			ans = std::abs(circles[n - 1].center - circles[0].center);

		for (int i = 0; i / 2 < n - 1; ++i) {
			if (isValid(iss[i / 2][i % 2], circles[n - 1].center, i / 2 + 1, n - 1)) {
				ans = std::min(
					ans,
					dp[i / 2][i % 2] + std::abs(circles[n - 1].center - iss[i / 2][i % 2])
				);
			}
		}

		std::cout << std::fixed << std::setprecision(6) << ans << std::endl;
	}
}


Measured memory_bytes: 3524
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
#include <cassert>
#include <unordered_map>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;


const ll MOD = 1e9 + 7;

ll pw(ll a, ll p) {
	ll res = 1;
	while (p > 0) {
		if (p & 1) {
			res = (res * a) % MOD;
		}
		a = (a * a) % MOD;
		p /= 2;
	}
	return res;
}

int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n, k;
	cin >> n >> k;
	vector<ll> have(k + 1);
	ll ans = 0;
	for (ll i = k; i >= 1; i--) {
		ll cur = pw(k / i, n);
		for (int j = i + i; j <= k; j += i) {
			cur -= have[j];
			if (cur < 0)cur += MOD;
		}
		have[i] = cur;
		cur = (cur * i) % MOD;
		ans = (ans + cur) % MOD;
	}
	cout << ans;
}

Measured memory_bytes: 4004