akhauriyash/Code-Regression huggingface dataset:
N,A,B =  list(map(int,input().split(" ")))
S = input()
for p in S:
    if p=="a":
        if A > 0:
            print("Yes")
            A -= 1
        elif B > 0:
            print("Yes")
            B -= 1
        else:
            print("No")
    if p=="b":
        if B > 0:
            print("Yes")
            B -= 1
        else:
            print("No")

    if p == "c":
        print("No")


Measured memory_bytes: 52952
N=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))
d,t={},{}
for key in D:
    if key in d:
        d[key]+=1
    else:
        d[key]=1
for key in T:
    if key in t:
        t[key]+=1
    else:
        t[key]=1
flag=True
for key in list(set(T)):
    if key not in d or t[key]>d[key]:
        flag=False
print("YES" if flag else "NO")

Measured memory_bytes: 64980
class Dice:
    def __init__(self, labels):
        self.labels = labels
        
    def __str__(self):
        return str(self.labels[0])
    
    def roll_south(self):
        self.labels[0], self.labels[1], self.labels[5], self.labels[4] = self.labels[4], self.labels[0], self.labels[1], self.labels[5]
            
    def roll_east(self):
        self.labels[0], self.labels[2], self.labels[5], self.labels[3] = self.labels[3], self.labels[0], self.labels[2], self.labels[5]
    
    def roll_west(self):
        self.labels[0], self.labels[3], self.labels[5], self.labels[2] = self.labels[2], self.labels[0], self.labels[3], self.labels[5]
    
    def roll_north(self):
        self.labels[0], self.labels[4], self.labels[5], self.labels[1] = self.labels[1], self.labels[0], self.labels[4], self.labels[5]
        
    def get_faces(self):
        return self.labels
        
def main():
    labels = list(map(int, input().split()))
    d = Dice(labels)
    n = int(input())
    for i in range(n):
        faces = list(map(int, input().split()))
        ind0 = labels.index(faces[0])
        ind1 = labels.index(faces[1])
        if ind0 == 1:
            d.roll_north()
        elif ind0 == 4:
            d.roll_south()
        else:
            while d.get_faces()[0] != faces[0]:
                d.roll_east()
        while d.get_faces()[1] != faces[1]:
            d.roll_east()
            d.roll_south()
            d.roll_west()
        print(d.get_faces()[2])
        
main()


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int i = 0; i < m; i++)
        cin >> x.at(i);
    sort(x.begin(), x.end());
    vector<int> d(m - 1);
    for (int i = 0; i < m - 1; i++)
        d.at(i) = x.at(i + 1) - x.at(i);
    sort(d.begin(), d.end(), greater<int>());
    for (int i = 0; i < n - 1 && i < m - 1; i++)
        d.at(i) = 0;
    int s = 0;
    for (int i = 0; i < m - 1; i++)
        s += d.at(i);
    cout << s << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n,dup=0;
    cin >> n;
    vector<int> h(n),v(n);
    for(int i=0;i<n;i++)
        cin >> h[i],v[i]=h[i];
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
        if(v[i] != h[i]) dup +=1;
    if(dup <= 2)
        cout << "YES";
    else cout << "NO\n";
}


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

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int X=in();

	vector<ll> Y;
	
	for(ll i=0;i<=1000;i++){
		ll Z=i*i*i*i*i;
		Y.push_back(Z);
	}

	REP(i,1001){
		REP(j,1001){
			ll A=Y[i]+Y[j];
			if(A==X){
				out(i,-j);
				return 0;
			}
			A=Y[i]-Y[j];
			if(A==X){
				out(i,j);
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3668
from math import gcd
import sys

MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p,MAXN+1,p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1
    
def pf(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
        
    return list(tmp)




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



g = 0
for a in A:
    g = gcd(g,a)
if g > 1:
    print('not coprime')
    sys.exit()

deta = set()
for a in A:
    a=pf(a)
    
    for p in a:
        if p in deta:
            print("setwise coprime")
            sys.exit()
            
        deta.add(p)


print("pairwise coprime")
    

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

S=sum(A)//2

S1 = [0]
s1 = 0
for i in range(N//2+1):
    s1+=A[2*i]
    S1.append(s1)

S2 = [0]
s2 = 0
for i in range(N//2):
    s2+=A[2*i+1]
    S2.append(s2)

ans = []

for i in range(N):
    if i%2==1:
        ans.append(2*(S-((S1[N//2+1]-S1[(i+1)//2])+(S2[(i-1)//2]))))
    else:
        ans.append(2*(S-((S2[N//2]-S2[i//2])+(S1[i//2]))))

print(*ans)

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

template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }

typedef tree<int,null_type,less<int>,rb_tree_tag,
		tree_order_statistics_node_update> indexed_set;

#define P pair<int,int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define st std::string 
#define pb push_back 
#define ll long long 
#define pq(x) std::priority_queue<x> 
#define ultapq(x) priority_queue<x,vector<x>,greater<x>> 
#define show_pq(x,n) for(int i = 0; i < n; i++){cout<<x.top(); x.pop();} 
#define itrt(yo) for(auto x:yo){std::cout<<x<<" ";} 
#define vec(x) std::vector<x> 
#define nl '\n' 
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define ALL(x) x.begin(),x.end() 
#define just int i= 0; i<n ; i++

void solve(){
    int n;
    cin>>n;
    int a[n]; for(just){cin>>a[i];}
    int m; cin>>m;
    
    for (int i = 0; i < m; i++)
    {

        int p,x; cin>>p>>x;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (i==p-1)
            {
                sum+=x;
            }else
            {
                sum+=a[i];
            }
            
            
            
        }
        cout<<sum<<nl;
        

        

    }
    

}

int main()
{
    IOS;
    int t=1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    
}

    

    
	

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)
#define INF 1000000000
#define all(x) (x).begin(), (x).end()

vector<int> dp;
vector<int> h;
int k;

int dfs(int i){
    if(i <= 0){
        return 0;
    }
    int ans;
    if(dp.at(i) != -1){
        ans = dp.at(i);
    }else{
        ans = INF;
        for(int j = 1; j <= min(k, i); j++){
            ans = min(ans, dfs(i - j) + abs(h.at(i) - h.at(i - j)));
        }
        dp.at(i) = ans;
    }
    return ans;
}

int main(){
    int n;
    cin >> n >> k;
    h = vector<int>(n);
    rep(i, n){
        cin >> h.at(i);
    }
    dp = vector<int>(n, -1);
    cout << dfs(n - 1) << endl;
}


Measured memory_bytes: 10328
package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	hw := make([]int, m)
	sum := 0
	for i:=0; i<m; i++{
		fmt.Scan(&hw[i])
		sum += hw[i]
	}

	if n >= sum {
		fmt.Println(n - sum)
	}else{
		fmt.Println(-1)
	}
}

Measured memory_bytes: 2440
import java.util.Scanner;

public class Main {
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A1 = sc.nextInt();
		int A2 = sc.nextInt();
		int A3 = sc.nextInt();
		System.out.println(A1+A2+A3>21 ? "bust":"win");
	}	
}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
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;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    string s;
    cin >> s;
    cout << (s == "ABC" ? "ARC" : "ABC") << endl;
}


Measured memory_bytes: 3648
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

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

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    ll N;
    cin>>N;
    ll ans=1;
    for(ll i=1;i<=N;++i){
        ans=ans*i%MOD;
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int c[100][100],a,b,n;
char ch[100][100];
int check(int x,int y){
	c[x][y] = 1;
	switch (ch[x][y]) {
	case '>':
		if (c[x][y+1] == 1) return 1;
		n = check(x,y+1);
		break;
	case '<':
		if (c[x][y-1] == 1) return 1;
		n = check(x,y-1);
		break;
	case 'v':
		if (c[x+1][y] == 1) return 1;
		n = check(x+1,y);
		break;
	case '^':
		if (c[x-1][y] == 1) return 1;
		n = check(x-1,y);
		break;
	case '.':
		a = x;
		b = y;
		return 0;
		break;
	}
	return n;
}
int main(){
	int x,y,i,j;
	while(cin >> x >> y && (x != 0 && y != 0)){
		for(i=0;i<x;i++){
			cin >> ch[i];
		}
		if (check(0,0)) cout << "LOOP" << endl;
		else cout << b << " " << a << endl;
		for(i=0;i<100;i++){
			for(j=0;j<100;j++){
				c[i][j] = 0;
				ch[i][j] = '\0';
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
n=int(input())
d=list(map(int,input().split()))
m=int(input())
a=list(map(int,input().split()))
ans="NO"
if n>=m:
    d.sort()
    a.sort()
    cnt_n=0
    cnt_m=0
    while cnt_m<m:
        if d[cnt_n]==a[cnt_m]:
            cnt_n+=1
            cnt_m+=1
        else:
            cnt_n+=1
        if n-cnt_n<m-cnt_m:
            break
    if cnt_m==m:
        ans="YES"
print(ans)

Measured memory_bytes: 35420
import math
n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
#print(n)
#print(c)
def euc_dist(c1, c2):
  x1, y1 = c1
  x2, y2 = c2
  return round(math.sqrt((x1 - x2)**2 + (y1 - y2)**2), 10)
"""
def dcount(m):
  if m<2: return 0
  elif m==2: return 1
  else: return dcount(m-1) + m-1
  """

d = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  for j in range(n):
    if i==j: d[i][j] = 0
    else: d[i][j] = euc_dist(c[i], c[j])
#print(d)

sum = 0
for i in range(n):
  for j in range(n):
    #print('sum={}'.format(sum))
    sum += d[i][j]
#print('sum={}, (n-1)!={}, n={}'.format(sum, math.factorial(n-1), n))
print(sum/n)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
long long n;
long long city[6];
long long a[6];

int main(){
	long long min=1000000000000001;
	long long ans=4;
	cin>>n;
	for (int i=1;i<=5;i++){
		cin>>a[i];
		if (a[i]<min) min=a[i];
	}
	ans+=n/min;
	if (n%min!=0) ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int get_changes(string s) {
	int c = 0;
	for (int i = 1; i < (int) s.size() - 1; ++i) {
		if (s[i] == s[i - 1] && s[i] == s[i + 1]) {
			++c;
			s[i] = (((s[i] - 'a') + 1) % 26) + 'a';
 		}
	}

	for (int i = 1; i < (int) s.size(); ++i) {
		if (s[i] == s[i - 1]) {
			++c;
		}	
	}

	return c;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string s;
	cin >> s;

	long long k;
	cin >> k;

	int sz = s.size();
	string copy = s;
	sort(copy.begin(), copy.end());
	if (copy[0] == copy[sz - 1]) {
		cout << sz * k / 2 << "\n";
		return 0;
	}

	long long c = get_changes(s);
	s = s + s;
	long long cc = get_changes(s);
	cout << c + (k - 1) * (cc - c) << "\n";

	return 0;

}

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

count = 0

for i in range(n):
    add_number = b[i] - a[i]
    if add_number >= 0:
        count += a[i]
        a[i] = 0
        if a[i+1] >= add_number:
            a[i+1] -= add_number
            count += add_number
        elif a[i+1] < add_number:
            count += a[i+1]
            a[i+1] = 0
            
    elif add_number < 0:
        count += b[i]
        
print(count)

Measured memory_bytes: 18476
#include<bits/stdc++.h>
using namespace std;
#define ll long long

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

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

	vector<int> q(n);
	ll s = 0;
	for (int i = 0; i < n - 1; i++) {
		q[i] = v[i + 1] - v[i];
		s = s + q[i];
	}

	q[n - 1] = k - v[n - 1] + v[0];
	s = s + q[n - 1];
	int p = *max_element(q.begin(), q.end());

	cout << s - p << endl;

}

Measured memory_bytes: 4856
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll Pow(ll a, ll b, ll c){
    ll ans = 1;
    a %= c;
    while (b){
        if (b & 1) ans = (ans * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return (ans % c);
}

bool cmp(const int &a, const int &b){
    return a < b;
}

ll gcd(ll x, ll y){
    return x % y == 0 ? y : gcd(y, x % y);
}

ll lcm(ll x, ll y){
    return x / gcd(x, y) * y;
}

int main(){
    ll a, b, c, d;
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    ll tmp = lcm(c, d);
    ll t1 = b / c - (a - 1) / c;
    ll t2 = b / d - (a - 1) / d;
    ll t3 = b / tmp - (a - 1) / tmp;
    printf("%lld\n", b - a + 1 - t1 - t2 + t3);
    return 0;
}


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

int main() {
    int N,M;
    cin >> N >> M;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin >> A.at(i);
    }

    int vote_sum = 0;
    for(int i:A){
        vote_sum += i;
    }

    int canSelect = 0;
    for(int i=0;i<N;i++){
        if(A.at(i)*(4*M)>=vote_sum){//選べるとき
            canSelect++;
        }
    }

    if(canSelect>=M) cout << "Yes" << endl;
    else cout << "No" << endl;


    return 0;
}




Measured memory_bytes: 256
#include<set>
#include<iostream>
using namespace std;
int main(){
  int a,b,k;
  cin >> a >> b >> k;
  if(a+k-1>=b){
    for (int i=a; i<b+1; i++){
      cout << i << endl;
    }
  }
  
  else {
    for (int i=a; i<=a+k-1; i++){
      cout << i << endl;
    }
    
    for (int i = max(b-k+1,a+k); i<b+1; i++){
      cout << i << endl;
    }
  }
}

Measured memory_bytes: 256
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    AB = [set() for _ in range(n+1)]
    for a, b in map(lambda x: map(int, x.split()), args[1:]):
        AB[a].add(b)
        AB[b].add(a)

    inf = 10**9
    D = [inf]*(n+1)
    B = [0]*(n+1)

    Q = deque()
    Q.append((1, 0, 0))  # room, distance, previous room
    while Q:
        r, d, p = Q.popleft()
        if d < D[r]:
            D[r] = d
            B[r] = p
            for nr in AB[r]:
                Q.append((nr, d+1, r))

    ret = ['Yes']
    for i in range(2, n+1):
        if D[i] == inf:
            ret = ['No']
            break
        ret.append(str(B[i]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 92604
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int N, A[402];
ll S[402];

ll dp[402][402];
ll f(int l, int r) {
    ll &re = dp[l][r];
    if (re != -1)RT re;
    if (l + 1 == r)RT re = 0;
    re = LLONG_MAX/3;
    for (int i = l + 1; i < r; ++i) {
        smin(re, f(l, i) + f(i, r) + S[r] - S[l]);
    }
    RT re;
}

void solve() {
    MEM(dp, -1);

    cin >> N;
    rep(i, N) {
        cin >> A[i];
        S[i + 1] = S[i] + A[i];
    }
    cout << f(0, N) << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define FOR(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using ll = long long;

int main() {
  int n; cin >> n;
  string s; cin >> s;
  int scnt = 0, ecnt = 0;
  REP(i,n) {
    if (s[i] == '(') scnt++;
    else if (scnt == 0) ecnt++;
    else scnt--;
  }
  REP(i,ecnt) cout << '(';
  cout << s ;
  REP(i,scnt) cout << ')';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<pair<ll, ll>> ab(n);
  for (int i = 0; i < n; i++) cin >> ab[i].first >> ab[i].second;
  sort(ab.begin(), ab.end());
  vector<ll> v(n);
  for (int i = 0; i < n-1; i++) ab[i+1].second += ab[i].second;
  for (int i = 0; i < n; i++) v[i] = ab[i].second;
  int x = lower_bound(v.begin(), v.end(), k)-v.begin();
  dump(ab[x].first);
  return 0;
}


Measured memory_bytes: 2560
import java.util.Scanner;

  
public class Main {
	
  public static void main(String[] args) {
	  Scanner sc=new Scanner(System.in);
	  int x;
	  int i=0;
	  int n=Integer.MAX_VALUE;
	  for(i=1;i<n;i++){
		  x=Integer.parseInt(sc.next());
		  if(x!=0){
		  System.out.println("Case " + i +": " + x );
		  }
		  else{
			  
			  break;
		  }
		  
	  }
	  
    
  }
}

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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    al = input()
    if al.isupper():
        print("A")
    else:
        print("a")
    return
if __name__ == '__main__':
    main()


Measured memory_bytes: 9076
#include<iostream>
using namespace std;
int main() {

	int d;
	cin >> d;
	int c[26];
	int i, j;
	for (i = 0; i < 26; i++) {
		cin >> c[i];
	}
	int s[365][26];
	for (i = 0; i < d; i++) {
		for (j = 0; j < 26; j++) {
			cin >> s[i][j];
		}
	}
	int last[26];
	for (i = 0; i < 26; i++) {
		last[i] = 0;
	}
	int jmax, jindex;
	for (i = 1; i <= d; i++) {

		jmax = 0;
		jindex = -1;
		for (j = 0; j < 26; j++) {
			if (c[j] *(i - last[j]) > jmax) {
				jmax = c[j] *(i - last[j]);
				jindex = j;
			}
			else if (c[j] *(i - last[j]) == jmax) {
				if (s[i - 1][j] > s[i - 1][jindex]) {
					jindex = j;
				}
			}
		}
		for (j = 0; j < 26; j++) {
			if (s[i - 1][j] + 20 * c[j] * (i - last[j]) >= jmax) {
				jmax = s[i - 1][j] + 20 * c[j] * (i - last[j]);
				jindex = j;
			}
		}
		last[jindex] = i;
		cout << jindex + 1 << endl;
		


	}
	return 0;


}

Measured memory_bytes: 3684
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()

res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L, L[i]+L[j])
        res += idx-(j+1)

print(res)

Measured memory_bytes: 3316
#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define pf push_front
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bt(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }

vector<int> get_bits(int mask) {
	vector<int> bb;
	while(mask) { int b = bt(mask); bb.pb(b); mask ^= (1 << b); }
	reverse(all(bb));
	return bb;
}

int get_mask(vector<int> v) {
	int mask = 0;
	for(int x : v) { mask ^= (1 << x); }
	return mask;
}

template<typename T>
void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

void sc() {}

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// #ifndef LOCAL
// string to_string(__int128 x) {
// 	string s = "";
// 	bool neg = 0;
// 	if(x < 0) { s += "-"; neg = 1; x = -x; }
// 	if(!x) s += '0';
// 	while(x) {
// 		int rem = x % 10;
// 		s += to_string(rem);
// 		x /= 10;
// 	}
// 	reverse(s.begin() + neg, s.end());
// 	return s;
// }
// #endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,ll b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
	Read problem statement carefully!!!
*/

const int N = 1e5 + 5;
int a[N];

void solve() {
	int n;
    sc(n);
    vector<int> v;
    fr(i, 1, n) {
        sc(a[i]);
        v.pb(a[i]);
    }
    uniq(v);
    fr(i, 1, n) {
        a[i] = upper_bound(all(v), a[i]) - v.begin();
    }
    int ans = 0;
    fr(i, 1, n) {
        if((a[i] % 2) != (i % 2)) ans++;
    }
    cout << ans / 2 << endl;
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}

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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  int n, a, b;
  cin >> n >> a >> b;
  if ((b - a) % 2) cout << "Borys" << '\n';
  else cout << "Alice" << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;

const int mod = 1e9 + 7;
int binomialCoeff(int n, int r) {
    int res = 1;
    if(r > n - r)r = n - r;
    for(int i = 0; i < r; i++) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}


int power(int x, int n, int mod) {
    //(x^n)%mod
    int result = 1;
    while(n) {
        if(n % 2)
            result = (result * x) % mod;
        x = (x * x) % mod;
        n /= 2;
    }
    return result;
}

int inverseMod(int x, int mod) {
    return power(x, mod - 2, mod);
}


int32_t main() {

    fast
    int n;
    cin >> n;
    if(n == 1) {
        cout << 0;
        return 0;
    }
    int ans=(power(10,n,mod)-((2*power(9,n,mod))%mod-power(8,n,mod)+mod)%mod+mod)%mod;
    //int ans = ((( n * (n - 1)) % mod) * power(10, n - 2, mod)) % mod;
    cout << ans;


    return 0;
}



Measured memory_bytes: 3536
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int n;
string s;
vector<bool> ans; // true = S, false = W

bool check(){
	bool zero = (ans[0] == ans[n]);
	bool ss = true;
	if(s[0] == 'o'){
		if(ans[0]){
			if(ans[n-1] != ans[1]) ss = false;
		}else{
			if(ans[n-1] == ans[1]) ss = false;
		}
	}else{
		if(ans[0]){
			if(ans[n-1] == ans[1]) ss = false;
		}else{
			if(ans[n-1] != ans[1]) ss = false;
		}
	}

	return (zero&&ss);
}

void circle(bool x,bool y){
	ans[0] = x,ans[1] = y;

	for(int i = 1; i < n; i++){
		if(s[i] == 'o'){
			if(ans[i]) ans[i+1] = ans[i-1];
			else ans[i+1] = !ans[i-1];
		}else{
			if(ans[i]) ans[i+1] = !ans[i-1];
			else ans[i+1] = ans[i-1];
		}
	}
}

int main()
{
	cin >> n >> s;
	bool flag = false;
	ans.resize(n+1);

	for(int i = 0; i < (1<<2); i++){
		circle(1&(i>>0),1&(i>>1));
		//cout << (int)((i>>1)&1) << " " << (int)((i>>0)&1) << " " << i <<  endl;
		if(check()){
			for(int i = 0; i < n; i++){
				if(ans[i]) cout << 'S';
				else cout << "W";
			}printf("\n");
		return 0;
		}
	}

	// circle(true,true);

	// if(check()){
	// 	for(int i = 0; i < n; i++){
	// 		if(ans[i]) cout << 'S';
	// 		else cout << "W";
	// 	}printf("\n");
	// 	return 0;
	// }

	// circle(true,false);

	// if(check()){
	// 	for(int i = 0; i < n; i++){
	// 		if(ans[i]) cout << 'S';
	// 		else cout << "W";
	// 	}printf("\n");
	// 	return 0;
	// }

	// circle(false,true);

	// if(check()){
	// 	for(int i = 0; i < n; i++){
	// 		if(ans[i]) cout << 'S';
	// 		else cout << "W";
	// 	}printf("\n");
	// 	return 0;
	// }


	// circle(false,false);

	// if(check()){
	// 	for(int i = 0; i < n; i++){
	// 		if(ans[i]) cout << 'S';
	// 		else cout << "W";
	// 	}printf("\n");
	// 	return 0;
	// }

	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 512
a,b = map(int,input().split())

def gcd(a,b):
  while a % b != 0:
    temp = b
    b = a % b
    a = temp
  return b

def lcm(a,b):
    return int(a * b / gcd(a,b))
  
print(lcm(a,b))
    

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

int main() {
   int N, M;
  cin >> N >> M;
  
  vector<int> vecab(2 * M);
  for(int i = 0; i < 2 * M; i++) {
  cin >> vecab.at(i);
  }
  
  vector<int> count(N + 10);
  for(int i = 1; i < N + 10; i++) {
    count.at(i) = 0;
  }
  
  
  for(int i = 0; i < 2 * M; i++) {
    count.at(vecab.at(i)) += vecab.at(i) / vecab.at(i);
  }
  
  for(int i = 1; i <= N; i++) {
    cout << count.at(i) << endl;
  }
  
  
  
  return 0;
  
    
}

Measured memory_bytes: 256
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()

x = max(a)
s = sum(a)
if x < s-x:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <cstdio>
int a[10];
int main() {
	int n, rat, cnt = 0, mn, mx;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &rat);
		if(rat >= 1 && rat <= 399)          a[1] ++;
		else if(rat >= 400 && rat <= 799)   a[2] ++;
		else if(rat >= 800 && rat <= 1199)  a[3] ++;
		else if(rat >= 1200 && rat <= 1599) a[4] ++;
		else if(rat >= 1600 && rat <= 1999) a[5] ++;
		else if(rat >= 2000 && rat <= 2399) a[6] ++;
		else if(rat >= 2400 && rat <= 2799) a[7] ++;
		else if(rat >= 2800 && rat <= 3199) a[8] ++;
		else a[9]++;
	}
	for(int i = 1; i <= 8; i++) 
		if(a[i])
			cnt++;
			
	mn = cnt;
	mx = cnt + a[9];
	if(mn < 1 && a[9]) mn = 1;
	printf("%d %d\n", mn, mx);
	return 0;
} 

Measured memory_bytes: 128
import bisect
import sys

def main():
  input = sys.stdin.readline
  n, d, a = map(int, input().split())
  fox = [None]*n
  for i in range(n):
    x, h = map(int, input().split())
    fox[i] = (x, h)

  fox.sort()
  x = [int(fox[i][0]) for i in range(n)]
  h = [int(fox[i][1]) for i in range(n)]

  ans = 0
  bit = [0]*n
  for i in range(n):
    if i != 0:
      bit[i] += bit[i-1]
    sub = max([(h[i]-bit[i]-1)//a+1, 0])
    ans += sub
    bit[i] += sub*a
    index = bisect.bisect_right(x, x[i]+2*d)
    if index != n:
      bit[index] -= sub*a
  print(ans)

if __name__ == "__main__":
  main()

Measured memory_bytes: 41868
inf = 10 ** 15
mod = 10 ** 9 + 7

n = int(input())
d = [list(map(int, input().split())) for i in range(n)]
d.sort()
pre = 0
count= 0
for num in d:
    if pre != num:
        count+=1
    pre = num
print(count)

Measured memory_bytes: 38512
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;


int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

const string MINUSINF = "-";
int match[10] = {2,5,5,4,5,6,3,7,6};
string dp[11000];

void chmax(string& a, string b){
  if(a.size() < b.size()) a = b;
  else if(a.size() == b.size()){
    if(a<b) a = b;
  }
}

int main(){
  int n,m; cin >> n >> m;
  vector<int> a(m);
  rep(i,m) cin >> a[i];
  
  rep(i,11000) dp[i] = MINUSINF;
  dp[0] = "";
  
  for(int i = 0; i <= n; i++){
    if(dp[i] == MINUSINF) continue;
    rep(j,m){
      chmax(dp[i+match[a[j]-1]],dp[i]+(char)('0'+a[j]));  
    }
  }
  
  cout << dp[n] << endl;
  
  return 0;
}

Measured memory_bytes: 43776
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever while (true)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
using namespace std;

main {
  int n, a;
  cin >> n >> a;
  queue<P<string, int>> q;
  while (n--) {
    string name;
    int time;
    cin >> name >> time;
    q.emplace(name, time);
  }
  int totalTime = 0;
  while (q.size()) {
    string name;
    int time;
    tie(name, time) = q.front();
    q.pop();
    totalTime += min(time, a);
    if (time > a) {
      q.emplace(name, time - a);
    } else {
      cout << name << ' ' << totalTime << endl;
    }
  }
}

Measured memory_bytes: 6332
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

struct UnionFind {
    vector<int> d;
    UnionFind(int n): d(n, -1) {}
    int root(int x) {
        if (d[x] < 0) return x;
        return d[x] = root(d[x]);
    }
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size(int x) { return -d[root(x)]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    int ans = n;
    for (int i = 0, x, y, z; i < m; i++) {
        cin >> x >> y >> z;
        x--; y--;
        if (uf.unite(x, y)) ans--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <stdio.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

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

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

  // ll n, w;
  // cin >> n >> w;
  // vector<ll> x(n), v(n);
  // for (int i = 0; i < n; ++i) {
  //   cin >> x[i] >> v[i];
  // }
  // vector<vector<ll>> dp(n + 1, vector<ll>(w + 1));
  // for (int i = 1; i <= n; ++i) {
  //   for (int j = 0; j <= w; ++j) {
  //     dp[i][j] = dp[i - 1][j];
  //     if (x[i - 1] <= j) {
  //       dp[i][j] = max(dp[i][j], dp[i - 1][j - x[i - 1]] + v[i - 1]);
  //     }
  //   }
  // }
  // cout << dp[n][w];

  int n;
  cin >> n;
  vector<ld> p(n);
  for (int i = 0; i < n; ++i) cin >> p[i];
  vector<vector<ld>> dp(n + 1, vector<ld>(n + 1));
  dp[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]);
      if (j) {
        dp[i][j] += dp[i - 1][j - 1] * p[i - 1];
      }
    }
  }
  ld sum = 0;
  for (int i = (n + 1) / 2; i <= n; ++i) {
    sum += dp[n][i];
  }
  cout << fixed << setprecision(10) << sum;
}


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

int main() {
  int N;
  cin >> N;
  vector<char> S(N);
  
  
  for(int i=0; i<N; i++){
    cin >> S[i];
  }
  
  
  vector<int> c(26);
  int n;
  for(int i=0; i<N; i++){
    n = S[i] - 'a';
    c[n]++;
  }
  
  long long ans = 1;
  long long ans2;
  for(int i=0; i<26; i++){
    ans *= (c[i]+1);
    ans2 = ans%1000000007;
    ans = ans2;
  }
  
  ans--;
  
  cout << ans << endl;
}

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

int main() {
    ll N,M;
    cin >> N >> M;
    priority_queue<ll> que;
    for (int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        que.push(a);
    }
    for (int i = 0; i < M; i++) {
        ll t = que.top();
        que.pop();
        que.push(t/2);
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += que.top();
        que.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 4252
import copy
from collections import Counter
n = int(input())
a = list(map(int,input().split()))

a_plus1 = copy.copy(a)
a_minus1 = copy.copy(a)
for x in range(n):
    a_plus1[x] += 1
for y in range(n):
    a_minus1[y] -= 1
a_total = a + a_plus1 + a_minus1
cnt = Counter(a_total)
a_max = list(cnt.values())
print(max(a_max))

Measured memory_bytes: 33696
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int N;cin>>N;
    if(N%2==0)cout<<N*N/4<<endl;
    else cout<<N/2*(N/2+1)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<long long >v;
int a[111111];
int main()
{
    long long t,n,c,x,p;
    string s;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    cout<<abs(a[(n/2)-1]-a[n/2]);


}




Measured memory_bytes: 640
#include<cstdio>
#include<algorithm> 

#define Fast register
inline char Getchar(){
	static char BUF[16384],*S=BUF,*T=BUF;
	return(S==T)&&(T=(S=BUF)+fread(BUF,1,16384,stdin),S==T)?EOF:*S++;
}
inline int Getint(){
	Fast int s=0;Fast char c;
	while(c=Getchar(),c<48||c>57);
	while(s=s*10+c-48,c=Getchar(),c>47&&c<58);
	return s;
}

int a[101];

int main(){
	Fast int N=Getint(),Ans=0;
	for(Fast int i=1;i<=N;++i)a[i]=Getint();
	std::sort(a+1,a+N+1);
	for(Fast int i=N,opt=1;i;--i,opt^=true)Ans+=(opt?a[i]:-a[i]);
	return(printf("%d",Ans),0);
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<stdio.h>
#include<stack>
#include<math.h>
#include <utility>
#include <tuple>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define Rep(i,n) for(int i=1;i<=(n);i++)
#define LL long long int
 
 /* 
 greater<int>() 
 sortの第三因数に入れて降順 
sqrt(double) √を求める 
pair<int,int> x=make_pair(a,b)
x.first
tuple
get<番目>(変数名)
 */
using namespace std;
 
LL lcm(LL n, LL m)
{
	LL u;
	LL ansl = 0;
	for(u=m; u>=m; u++){
		if(u%n == 0){
			if(u%m == 0){
				ansl = u;
				break;
			}
		}
	}
	return ansl;
}
 
int main(){

    double x,y;
    cin >>y;
    
    printf("%f\n",(int)(y/2+(int)y%2)/y);
    return 0;


}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var s = int.Parse(Console.ReadLine());
    var set = new HashSet<int> {s};
    for (int i = 2; ; i++) {
      if ((s & 1) == 0) s /= 2;
      else s = s * 3 + 1;
      if (set.Contains(s)) {
        Console.WriteLine(i);
        return;
      } else {
        set.Add(s);
      }
    }
  }
}

Measured memory_bytes: 13396
n=int(input())

dp=[0]*100010
dp[0]=0


for i in range(1,100010):
  n6=0
  n9=0
  li=[]
  while 6**(n6+1)<=i:
    n6+=1
  while 9**(n9+1)<=i:
    n9+=1
  for j in range(n6+1):
    li.append(dp[i-6**n6])
  for jj in range(n9+1):
    li.append(dp[i-9**n9])
  dp[i]=min(li)+1
print(dp[n])

Measured memory_bytes: 3828
#include<bits/stdc++.h> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#define mod 1000000007
#define mod2 998244353
#define int long long
#define endl "\n"
#define p_b push_back
#define fastIO ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
template <class T> 
using _ost = tree<
		T, 
		null_type, 
		less<T>, 
		rb_tree_tag, 
        tree_order_statistics_node_update>;
// char alphabet[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
void swap(int* a,int* b){
    int temp = *a;
    *a=*b;
    *b=temp;
}	
int32_t main(){
 	fastIO;
 	int n,x,y;
 	cin>>n>>x>>y;
 	int ans[n]={0};
 	for(int i=1;i<n;i++){
 		for(int j=i+1;j<=n;j++){
 			int dist=j-i;
 			dist=min(dist,min(abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y)));
 			ans[dist]++;
 		}
 	}
 	for(int i=1;i<n;i++)cout<<ans[i]<<endl;
} 	

Measured memory_bytes: 256
s = input()
if s == "SAT":
  print(1)
elif s == "FRI":
  print(2)
elif s == "THU":
  print(3)
elif s == "WED":
  print(4)
elif s == "TUE":
  print(5)
elif s == "MON":
  print(6)
else:
  print(7)


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

int l[11],v1,v2;
double sum,a;


int main(){
	while(scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",&l[1],&l[2],&l[3],&l[4],&l[5],&l[6],&l[7],&l[8],&l[9],&l[10],&v1,&v2)!=EOF){
		sum=l[1]+l[2]+l[3]+l[4]+l[5]+l[6]+l[7]+l[8]+l[9]+l[10];
		a=sum*v1/(v1+v2);
		for(int i=1;i<11;i++){
			if(a>l[i]) a-=l[i];
			else {
				printf("%d\n",i);
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 2696
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
using Graph = vector<vector<int>>;
///////////////////////////////////////




int main() {
	string N; cin >> N;
	int n = N.size();
	int K; cin >> K;
	ll dp[110][2][4];
	//dp[i][j][k][l]で、上位i個の桁を決めた,N未満が確定している,一番上の桁が0以外で確定,0以外の数字がk個
	REP(i, 110) {
		REP(j, 2) {
			REP(k, 4) {
				dp[i][j][k] = 0;
			}
		}
	}
	dp[0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k <= K; ++k) {
				int x;
				x = j ? 9 : N[i] - '0';
				for (int d = 0; d <= x; ++d) {
					if (d != 0) {
						if (k < K) {
							dp[i + 1][j || (d < x)][k + 1] += dp[i][j][k];
						}
					}
					else {
						dp[i + 1][j||(d<x)][k] += dp[i][j][k];
					}
				}
			}
		}
	}
	cout << dp[n][0][K] + dp[n][1][K] << endl;
	return 0;
}

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

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

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

int main(){
    int n;
    cin>>n;
    int d[n];
    rep(i, n){
        cin>>d[n-i-1];
    }
    rep(i, n){
        if(i){
            cout<<" "<<d[i];
        }
        else{
            cout<<d[i];
        }
    }
    cout<<endl;
}


Measured memory_bytes: 3104
module Main where
import qualified Control.Monad as C
import qualified Data.Char as C
import qualified Data.List as L
import qualified Data.Map as M
import qualified Data.Array as A

int = read :: String -> Int
getWord :: IO String
getWord = do
  c <- getChar
  if C.isSpace c
  then
    return []
  else do
    ws <- getWord
    return (c:ws)
getInt = fmap int getWord
replace pred a = map (\x -> if pred x then a else x)

main = interact $ printer . solver . parser
parser = int
printer = unlines . (:[]) . show

solver n = sum $ map (pattern n) [1..n]
    
pattern n a = (n-1) `div` a

Measured memory_bytes: 3920
#include <bits/stdc++.h>
using namespace std;
double pi=acos(-1);
int main()
{

    int n;cin>>n;
    int f[n+1];
    memset(f,0,sizeof f);
    for(int i=2;i<=n;i++)
    {
        int a;cin>>a;
        if(a!=i)f[a]++;
    }
    for(int i=1;i<=n;i++)cout<<f[i]<<endl;


	return 0;
}


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

int main(){

	int h, s, m, S;

	cin >> S;
	
	h = S / 60 / 60;
	m = (S - 3600 * h) / 60;
	s = S - 3600 * h - 60 * m;

	cout << h << ":" << m << ":" << s << endl;

	return 0;
}

Measured memory_bytes: 3092