akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().solve();
	}

	private void solve() throws IOException {
		try {
			//			solveA();
			solveB();
			//			solveC();
			// solveD();
			// solveE();
			// solveF();
		} finally {
			if (in != null) {
				in.close();
			}
			if (out != null) {
				out.flush();
				out.close();
			}
		}

	}

	private void solveA() {
		int numA = nextInt();
		int numB = nextInt();
		int numC = nextInt();

		out.println(numC >= numA && numC <= numB ? "Yes" : "No");

	}

	private void solveB() {
		int numN = nextInt();
		int numM = nextInt();

		int[] wk = new int[numN];

		//		Map<Integer, Integer> wkMap = new TreeMap<Integer, Integer>();
		for (int i = 0; i < numM; i++) {
			int a = nextInt();
			int b = nextInt();
			wk[a - 1]++;
			wk[b - 1]++;
			//			wkMap.merge(wk[i][0], 1, (oldV, newV) -> oldV + newV);
			//			wkMap.merge(wk[i][1], 1, (oldV, newV) -> oldV + newV);
		}

		//		wkMap.values().stream().forEach(value -> out.println(value));
		for (int i : wk) {
			out.println(i);
		}
	}

	private void solveC() {
		int numN = nextInt();

		out.println("");
	}

	private void solveD() {
		int numN = nextInt();

		out.println("");
	}

	private void solveE() {
		int numN = nextInt();

		out.println("");
	}

	private void solveF() {
		int numN = nextInt();

		out.println("");
	}

	private final PrintWriter out = new PrintWriter(System.out);
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

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

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

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

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

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

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

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

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

Measured memory_bytes: 22100
import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""

def isUp(A):
	p = 0
	for a in A:
		if a < p:
			return False
		p = a
	return True
N = int(input())
A = [int(i) for i in input().split()]
ans = False

if isUp(A):
	ans = True
if not ans:
	for i in range(N-1):
		for j in range(i+1,N):
			A[i] += A[j]
			A[j] = A[i]-A[j]
			A[i] = A[i]-A[j]
			if isUp(A):
				ans = True
				break
			A[i] += A[j]
			A[j] = A[i]-A[j]
			A[i] = A[i]-A[j]
if ans:
	print("YES")
else:
	print("NO")


Measured memory_bytes: 3952
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repdm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)

int main()
{

  int N;
  cin >> N;
  int p[N];
  int maxPrice = 0;
  int ans = 0;
  rep(i, N)
  {
    cin >> p[i];
    if (maxPrice < p[i])
      maxPrice = p[i];
    ans += p[i];
  };
  cout << ans - (maxPrice / 2);
}

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

using namespace std;

int main()
{
	int a, b, c;

	scanf("%d%d%d", &a, &b, &c);

	if (a > b)
		swap(a, b);
	if (b > c)
		swap(b, c);
	if (a > b)
		swap(a, b);

	printf("%d %d %d\n", a, b, c);
	
	return (0);
}

Measured memory_bytes: 1188
#include <stdio.h>
int main(void)
{
    int n,m,t,i,j;
 
    scanf("%d %d",&n,&m);
     
    int a[100][100],b[100],ans[100];
 
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
 
 
 
    for(i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
 
    for(i=0;i<n;i++)
    {
        t = 0;
         
        for(j=0;j<m;j++)
        {
            t = t + (a[i][j]*b[j]);
             
        }
 
        ans[i] = t;
         
    }
 
    for(i=0;i<n;i++)
    {
        printf("%d\n",ans[i]);
    }
 
 
     
    return 0;
 
}

Measured memory_bytes: 640
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
using namespace std;



int main(){
	double x[4],y[4],big,sml;
	bool a,b;
	while( scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x[0],&y[0],&x[1],&y[1],&x[2],&y[2],&x[3],&y[3]) != EOF){
		if(x[3]<x[0] || x[2]>x[1] || y[3]<y[0] || y[2]>y[1] ) printf("NO\n");
		else printf("YES\n");
	}
			
	return 0;
}


Measured memory_bytes: 3144
//arc081 q1
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <tuple>
#include <deque>
#define pb push_back
#define pf push_front
#define mkt make_tuple
#define pqueue priority_queue
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
const int INF =  2147483647;
const ll INFLL = 9223372036854775807;

map<ll, ll> cache;


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

  ll n, a, h = 0, w = 0, ans;
  cin >> n;
  for (size_t i = 0; i < n; i++) {
    cin >> a;
    cache[a]++;
    ll num = cache[a];
    if ((num == 2 || num == 4) && (a >= h || a >= w)) {
      h = max(h, w);
      w = a;
    }
  }

  ans = h * w;

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define INF 0x3f3f3f3f
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
const ll mod=1000000007;
const double PI = acos(-1.0);
const double epsilon = PI / 180.0;//角度转弧度 
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N = 2e5+10;
int a[N];
int main() {
	int n;
	cin>>n;
	int sum = 0;
	rep(i, 1, n + 1) scanf("%d", &a[i]), sum ^= a[i];
	rep(i, 1, n + 1) cout<<(sum ^ a[i])<<" ";
	return 0;
}

Measured memory_bytes: 4420
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1e9;

signed main(){
	int n;scanf("%d",&n);
	int t=n%10;
	if(t==2||t==4||t==5||t==7||t==9)puts("hon");
	else if(t==0||t==1||t==6||t==8)puts("pon");
	else puts("bon");

	return 0;
}



Measured memory_bytes: 3764
void main() {
    string[] tmp = readln.split;
    string a = tmp[0], b = tmp[1], c = tmp[2];
    writeln(a[$-1] == b[0] && b[$-1] == c[0] ? "YES" : "NO");
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 256
#include <stdio.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define MOD 998244353

ll dp[3010][3010];
ll a[3010];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	rep(i,0,n)scanf("%lld",a+i);

	dp[0][0]=1;
	rep(i,0,n){
		rep(j,0,k+1)dp[i+1][j]+=2*dp[i][j];
		rep(j,0,k-a[i]+1)dp[i+1][j+a[i]]+=dp[i][j];
		rep(j,0,k+1)dp[i+1][j]%=MOD;
	}
	printf("%lld",dp[n][k]);
}

Measured memory_bytes: 72260
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
ans = 0
for i in range(n):
  a = list(map(int,input().split()))
  total = c
  for j, (a_temp,b_temp) in enumerate(zip(a,b)):
    total += a_temp * b_temp
  if total >0:
    ans += 1
print(ans)
  

Measured memory_bytes: 62168
#include<iostream>

using namespace std;

int main(){
 int a,b;
 cin >> a >> b;
 if(a % 3 == 0 || b % 3 == 0 || (a +b) % 3 == 0){
  cout << "Possible" << endl;
 }else{
  cout << "Impossible" << endl;
 }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int w = sc.nextInt();

        while(h != 0 || w != 0){
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    System.out.print("#");
                }
                System.out.println("");
            }
            System.out.println("");

            h = sc.nextInt();
            w = sc.nextInt();
            
        }


        sc.close();
    }
}


Measured memory_bytes: 34788
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let (V, E): (usize, usize) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };
    let (u, v, c): (Vec<usize>, Vec<usize>, Vec<i64>) = {
        let (mut u, mut v, mut c) = (vec![], vec![], vec![]);
        for _ in 0..E {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            u.push(iter.next().unwrap().parse().unwrap());
            v.push(iter.next().unwrap().parse().unwrap());
            c.push(iter.next().unwrap().parse().unwrap());
        }
        (u, v, c)
    };

    let _N = V;
    let _M = E;
    let _A = u;
    let _B = v;
    let _C = c;
    static INF: i64 = 1e15 as i64;

    // snip
    fn dfs(
        i: usize,
        t: usize,
        f: i64,
        G: &mut Vec<Vec<(usize, i64, usize)>>,
        next_edge: &mut Vec<usize>,
        level: &Vec<usize>,
    ) -> Option<i64> {
        if i == t {
            Some(f)
        } else {
            for k in next_edge[i]..G[i].len() {
                let (j, c, l) = G[i][k];
                if c > 0 && level[i] < level[j] {
                    if let Some(d) = dfs(j, t, std::cmp::min(f, c), G, next_edge, level) {
                        G[i][k] = (j, c - d, l);
                        let (_, w, _) = G[j][l];
                        G[j][l] = (i, w + d, k);
                        next_edge[i] = k;
                        return Some(d);
                    }
                }
            }
            next_edge[i] = G[i].len();
            None
        }
    }

    let flow = |s, t| {
        let mut G = vec![vec![]; _N + 1];
        for i in 0.._M {
            let k = G[_B[i]].len();
            let l = G[_A[i]].len();
            G[_A[i]].push((_B[i], _C[i], k));
            G[_B[i]].push((_A[i], 0, l));
        }
        let mut res = 0;
        loop {
            let mut level = vec![0; _N + 1];
            let mut q = std::collections::VecDeque::new();
            level[s] = 1;
            q.push_back(s);
            while let Some(i) = q.pop_front() {
                for &(j, c, _) in &G[i] {
                    if c > 0 && level[j] == 0 {
                        level[j] = level[i] + 1;
                        q.push_back(j);
                    }
                }
            }
            if level[t] == 0 {
                break;
            }
            let mut next_edge = vec![0; _N + 1];
            while let Some(f) = dfs(s, t, INF, &mut G, &mut next_edge, &level) {
                res += f;
            }
        }
        res
    };
    // snip

    let ans = flow(0, V - 1);

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



Measured memory_bytes: 5048
#include <iostream>

using namespace std;

int s,m,h;
int S;

int main()
{
    cin >> S;
    
    h = S/3600;
    m = (S%3600)/60;
    s = (S%3600)%60;
    
    cout << h << ":" << m << ":" << s << endl;
    
    return 0;
}


Measured memory_bytes: 3092
#include "bits/stdc++.h"
using namespace std;


int main(int argc, char const *argv[])
{
  string s;
  cin >> s;
int flag = 0;
  for(int i = 0; i < s.length(); i++){
    if(s[i] == '9')flag = 1;
  }

  if(flag){cout << "Yes";}
  else{
    cout << "No";
  }
  return 0;
}

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

typedef long long ll;

void print(){ std::cout << std::endl; }
template<typename H> void print(H&& head){ std::cout << head << std::endl; }
template<typename H, typename... T> void print(H&& head, T&&... tail){
  std::cout << head << " ", print(std::forward<T>(tail)...);
}

int main()
{
  ll N; std::cin >> N;
  std::vector< ll > va(N, 0LL);
  for (ll i = 0; i < N; i++) {
    std::cin >> va[i];
  }

  ll cnt = 0;
  for (auto a : va) {
    if (a == cnt+1) {
      cnt++;
    }
  }

  print(cnt == 0 ? -1 : N - cnt);

  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<sstream>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 1000000000+7
using namespace std;
typedef long long ll;

int main(){
  string s; cin >> s;
  for(int i=0; i<s.length()-1; i++){
    if(s[i]==s[i+1]){
      cout << i+1 << " " << i+2 << endl;
      return 0;
    }
  }
  for(int i=0; i<s.length()-2; i++){
    if(s[i]==s[i+2]){
      cout << i+1 << " " << i+3 << endl;
      return 0;
    }
  }
  cout << -1 << " " << -1 << endl;
  return 0;
}

Measured memory_bytes: 512
from collections import deque

LIST = deque()

num_command = int(input())

for loop in range(num_command):

    input_command = input()

    if input_command == 'deleteFirst':
        LIST.popleft()
    elif input_command == 'deleteLast':
        LIST.pop()
    else:
        com,num = input_command.split()

        if com == 'insert':
            LIST.appendleft(num)
        elif com == 'delete':
            try:
                LIST.remove(num)
            except:
                pass

print(' '.join(LIST))



Measured memory_bytes: 69736
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
using namespace std;
int main(){
    int k, s;
    cin >> k >> s;
    k++;
    int cnt = 0;
    REP(i,k){
        REP(l,k){
            int z = s - i - l;
            if(0<=z&&z<k){
                cnt++;
            }
        }

    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int n;
vector<int> a,dpx,dpy;
int dfs(int i,int s,int t, bool b){
  if(i==n) return abs(t-s);
  int res;
  if(b){
    if(dpx[i]>=0) return dpx[i];
    res = 0;
    for(int j=i;j<n;++j){
      res = max(res,dfs(j+1,a[j],t,!b));
    }
    dpx[i] = res;
  }else{
    if(dpy[i]>=0) return dpy[i];
    res = 1e9;
    for(int j=i;j<n;++j){
      res = min(res,dfs(j+1,s,a[j],!b));
    }
    dpy[i] = res;
  }
  return res;
}

int main(){
  int s,t;
  cin >> n >> s >> t;
  a = vector<int>(n);
  rep(i,n) cin >> a[i];
  dpx = dpy = vector<int>(n,-1);
  cout << dfs(0,s,t,true) << endl;;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define RREP(i, a, n) for(int i=n-1; i>=a; i--)
#define MOD 1000000007

bool deter[100001];
int main()
{
	int N;
	int T[100001], A[100001];
	cin >> N;
	REP(i, 0, N) cin >> T[i];
	REP(i, 0, N) cin >> A[i];

	int mx;
	bool flag = false;
	if (T[N - 1] == A[0]) {
		mx = T[N - 1];

		REP(i, 0, N) {
			if (T[i] == A[i] && T[i] == mx) {
				flag = true;
				break;
			}
		}
	}

	if (!flag) cout << 0 << endl;
	else {
		deter[0] = deter[N - 1] = true;
		int t = T[0];
		int a = A[N - 1];

		REP(i, 1, N-1) {
			if (T[i] != t) deter[i] = true;
			t = T[i];
		}
		RREP(i, 1, N - 1) {
			if (A[i] != a) deter[i] = true;
			a = A[i];
		}

		long long ans = 1;
		REP(i, 0, N) {
			if (!deter[i]) {
				ans *= min(T[i], A[i]);
				ans %= MOD;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
# encoding: utf-8
import sys
# from collections import deque
input = sys.stdin.readline

N = int(input())

if N % 2:
    M = N * (N - 1) // 2 - N // 2
    print(M)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if (i + j + 2) == N: continue
            else:
                print(i + 1, j + 1)
else:
    M = N * (N - 1) // 2 - N // 2
    print(M)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if (i + j + 2) == (N + 1): continue
            else:
                print(i + 1, j + 1)

Measured memory_bytes: 3612
#include <bits/stdc++.h>
 
using namespace std;
#define M 1005
#define N 15
int a[M];
int b[M];
int c[M];
int dp[M][4500];
int n,m;
int mx;
 
int solve(int idx,int mask)
{
    if(idx == m)
    {
        if(mask == mx)
        {
            return 0;
        }
        return 1e9;
    }
 
    if(dp[idx][mask] != -1)
    {
        return dp[idx][mask];
    }
    int temp = mask | c[idx];
    int A = solve(idx + 1, temp) + a[idx];
    int B = solve(idx + 1, mask);
 
    return dp[idx][mask] = min(A,B);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>n>>m;
    mx = (1<<n) - 1;
    for(int i = 0 ; i < m ; i++)
    {
        cin>>a[i]>>b[i];
        for(int j = 0 ; j < b[i] ; j++)
        {
            int x;
            cin>>x;
            c[i] |= (1<<(x - 1)) ;
        }
    }
    int ans = solve(0,0);
    cout<<((ans != 1e9)?ans:-1)<<endl;
 
    return 0;
}

Measured memory_bytes: 21340
#include <vector>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <string>
#include <utility>
#include <stack>
#include <numeric>
#include <random>
#include <algorithm>
#include <queue>
#include <functional>
#include <iterator>
#include <list>
#include <unordered_map>
#include <deque>
#include <math.h>
#include <tgmath.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, b, e) for(i = b; i < e; ++i)
#define repr(i, b, e) for (i = b; i >= e; --i)
#define ull unsigned long long int
#define ll long long int
#define pint pair<int, int>

#define M_DEBUG 1
#define PI 3.141592653589793

#define E '\n'

#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << "\n";}
#define INF (1e18)

const ll MAX = 1000000000;
const ll MOD = 1e9 + 7;

ll 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;

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;
}

ll aabs(ll a) {
    if (a < 0) return -a;
    return a;
}

//fast power
ll calc(ll a, ll b) {
    if (b == 0) return 1;
    else if (b % 2 == 0) {
        ll d = calc(a, b / 2);
        return (d * d) % MOD;
    }
    else return (a * calc(a, b - 1)) % MOD;
}

//fast combination
ll comb(ll n, ll a) {
    ll b = 1, c = 1;
    for (ll i = 1; i <= a; ++i) {
        b = b * i % MOD;
        c = c * (n - i + 1) % MOD;
    }

    return c * calc(b, MOD - 2) % MOD;
}

ll comb2(ll a) {
    ll b = a / 2;
    if (a % 2) {
        b = (a - 1) / 2;
        return (b * a);
    }
    return (b * (a - 1));
}

int dfs(int x, int y, int z) {
    if (x == a && y == b && z == c) return 1;
    
    int ans = 0;
    if (x != a) ans += dfs(x + 1, y, z);
    if (x >= y + 1/* && y != b*/) ans += dfs(x, y + 1, z);
    if (y >= z + 1/* && z != c*/) ans += dfs(x, y, z + 1); 

    return ans;
}

uint64_t gcd_impl( uint64_t n, uint64_t m ) {
        for( int i = 0; i < 10; ++i ) {
                uint64_t t = n - m;
                bool q = m > t;
                n = q ? m : t;
                m = q ? t : m;
                if( m == 0 ) { return n; }
        }
        return gcd_impl( m, n % m );
}

uint64_t gcd( uint64_t n, uint64_t m ) {
        return n > m ? gcd_impl( n, m ) : gcd_impl( m, n );
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;

    vector<int> aa(m);

    rep (i, 0, m) cin >> aa[i]; 
    
    b = accumulate(aa.begin(), aa.end(), 0LL);

    if (b > n) {
        cout << -1 << endl;
        return 0;
    }

    cout << n - b << endl;

    return 0;
}



Measured memory_bytes: 3700
const main = (input: string) => {
  let [r, D, x] = input.trim().split(" ").map(str => parseInt(str))
  const OUTPUT_LINE = 10;
  let answer: string = "";
 
  for (let i = 0; i < OUTPUT_LINE; i++) {
    answer = `${answer}${r * x - D}\n`;
    x = r * x - D
  }
 
  console.log(answer.trim());
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7628
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, functools, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ; count = 0; pro = 1

n=int(input())
count=0
# @functools.lru_cache(maxsize=None)
memo=[0]*(n+1)
memo[0]=0
def func(n):
    if memo[n] or n==0:return memo[n]
    # print(n)
    # global count
    # count+=1
    # if count%10==0:print(count)
    if n==0:
        return 0
    re=inf
    k=s=1
    while 9**s<=n:
        re=min(re,func(n-9**s)+1)
        s+=1
    while 6**k<=n:
        re=min(re,func(n-6**k)+1)
        k+=1
    re=min(re,func(n-1)+1)
    memo[n]=re
    return re
    
print(func(n))
# print(memo)



Measured memory_bytes: 59612
a,b = map(int, input().split())
n = [1]*a
r = [0]*a
r[0] = 1

for i in range(b):
    ta,tb = map(int, input().split())
    ta-=1
    tb-=1
    if r[ta] == 1:
        r[tb] = 1
    n[ta] -=1
    n[tb] +=1
    if n[ta] ==0:
        r[ta] = 0
print(sum(r)) 


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

#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433L;

template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
    SPEED
    int N; cin >> N;
    vector<int> V(N+1),W(N+1);
    for(int i = 1; i <= N; ++i) cin >> V[i] >> W[i];

    //O(Q)
    int nl = 1<<11,nr=1<<7,L_max=100001;
    vector<int> msb(nl,0);
    for(int i = 1; i < nl; ++i) msb[i]=31-__builtin_clz(i);
    vector<int> bit_w_dp(nl,0);
    vector<int> bit_v_dp(nl,0);
    vector<vector<int>> dp(nl,vector<int>(L_max,0));

    //前計算
    for(int n = 1; n < min(nl,N+1); ++n) {
        int k = 2*n;
        vector<int> l;
        while(k/=2) l.push_back(k);
        int sz=l.size();
        //bit全探索
        for(int i = 1; i < (1<<sz); ++i) {
            bit_w_dp[i]=bit_w_dp[i^(1<<msb[i])]+W[l[msb[i]]];
            bit_v_dp[i]=bit_v_dp[i^(1<<msb[i])]+V[l[msb[i]]];
            if(bit_w_dp[i]<=L_max) chmax(dp[n][bit_w_dp[i]],bit_v_dp[i]);
        }
        //累積max
        for(int i = 1; i < L_max; ++i) {
            chmax(dp[n][i],dp[n][i-1]);
        }
    }

    int Q; cin >> Q;
    string ans_str="";

    //クエリ
    while(Q--) {
        int p,L; cin >> p >> L;
        vector<int> r;
        int k = 2*p,l=0;
        while(k/=2) {
            if(k<nl) chmax(l,k);
            else r.push_back(k);
        }
        int sz = r.size(),ans=dp[l][L];
        //bit全探索
        for(int i = 1; i < (1<<sz); ++i) {
            bit_w_dp[i]=bit_w_dp[i^(1<<msb[i])]+W[r[msb[i]]];
            bit_v_dp[i]=bit_v_dp[i^(1<<msb[i])]+V[r[msb[i]]];
            if(bit_w_dp[i]<=L) chmax(ans,dp[l][L - bit_w_dp[i]]+bit_v_dp[i]);
        }
        ans_str += to_string(ans)+"\n";
    }
    cout << ans_str;

    return 0;
}


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

int main() {
  int N, check = 1;
  cin >> N;
  vector<pair<int64_t, int64_t>> a(N);
  int64_t time = 0;
  for (int i = 0; i < N; i++) {
    cin >> a.at(i).second >> a.at(i).first;
  }
  sort(a.begin(), a.end());
  for (int i = 0; i < N; i++) {
    time += a.at(i).second;
    if (time > a.at(i).first) {
      cout << "No" << endl;
      check = 0;
      break;
    }
  }
  if (check == 1) {
    cout << "Yes" << endl;
  }
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N; cin >> N;
    string s; cin >> s;
    int len = s.length();
    int c = 1;
    for(int i = 0; i < len-1; i++){
        if(s[i] != s[i+1]) c++;
    }
    cout << c << endl;
}

Measured memory_bytes: 512
st1 = input()
st2 = input()
li = []
count = 0

k = 0

for i in range(len(st1)-len(st2)+1):
    for s2 in st2:
        if s2 in st1[i+k]:
            count += 1
        k += 1
    li.append(count)
    count = 0
    k = 0

print(len(st2) - max(li))


Measured memory_bytes: 9056
N = gets.to_i
S = gets.chomp

ans = ''
lv = 0
S.chars.each do |c|
  lv += (c == '(' ? 1 : -1)
  if lv.negative?
    ans = '(' + ans
    lv = 0
  end
  ans += c
end

while lv.positive?
  ans += ')'
  lv -= 1
end

puts ans


Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<limits>
using ll = long long;
using namespace std;

int main() {
	string t;
	cin >> t;
	int p = t.size() -1;
	if (p == 0) {
		if (t == "?")t = 'D';
	}
	if (p != 0) {
		for (int i = 0; i < p; i++) {
			if (t.at(i) == 'P') {
				if (t.at(i + 1) == '?') {
					t.at(i + 1) = 'D';
				}
			}
			if (t.at(i) == '?') {
				if (t.at(i + 1) == 'D')t.at(i) = 'P';
				if (t.at(i + 1) == 'P')t.at(i) = 'D';
				if (t.at(i+1) == '?') {
					t.at(i) = 'P'; t.at(i + 1) = 'D';
				}
			}
			if (t.at(i) == 'D') {
				if (t.at(i + 1) == '?')t.at(i+1) = 'D';
			}
		}
	}
	
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> A(n);
  int m = 100005;
  vector<int> cnt(m);
  rep(i, n) {
    cin >> A[i];
    cnt[--A[i]]++;
  }
  int dbl = 0;
  rep(i, m) {
    if(cnt[i] > 1) dbl += cnt[i]-1;
  }
  cout << n-(dbl+1)/2*2 << "\n";
  return 0;
}


Measured memory_bytes: 4000
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int res[100001];
vector<int> col[100001];
int sum[100005];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int p;
		scanf("%d",&p);
		col[p-1].push_back(i);
	}
	for(int i=0;i<n;i++){
		sum[i]=-1;
	}
	int mini=0;
	for(int i=0;i<n;i++){
		sum[i]+=col[i].size();
		if(i>0)sum[i]+=sum[i-1];
		if(sum[i]<sum[mini])mini=i;
	}
	stack<int> sta;
	for(int i=0;i<n;i++){
		mini=(mini+1)%n;
		if(col[mini].size()>0){
			res[mini]=col[mini][0];
			int N=col[mini].size();
			for(int i=N-1;i>=1;i--){
				sta.push(col[mini][i]);
			}
		}else{
			int v=sta.top();
			res[mini]=v;
			sta.pop();
		}
	}
	for(int i=0;i<n;i++){
		printf("%d\n",res[i]+1);
	}
	return 0;
}

Measured memory_bytes: 8256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <algorithm>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

int main() {
	int A, B, M;
	vector<int> a, b;
	int _tmp;
	int x,y,c;
	int ans = 200005;
	cin >> A >> B >> M;
	rep(i, A)
	{
		cin >> _tmp;
		a.push_back(_tmp);
	}
	rep(i, B)
	{
		cin >> _tmp;
		b.push_back(_tmp);
	}

	rep(i, M)
	{
		cin >> x >> y >> c;
		if (a[x - 1] + b[y - 1] - c < ans)
		{
			ans = a[x - 1] + b[y - 1] - c;
		}
	}

	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	if (a[0] + b[0] < ans)
		ans = a[0] + b[0];

	cout << ans;
}

Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

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

    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    Rep (i, N) {
        cin >> A[i];
    }

    ll ok = 1e9, ng = 0;
    while (abs(ok-ng) > 1) {
        ll mid = (ok + ng) / 2;
        ll cnt = 0;
        Rep (i, N) {
            cnt += (A[i] - 1) / mid;
        }
        // cout << mid << " " << cnt << "\n";
        if (cnt <= K) ok = mid;
        else ng = mid;
    }

    cout << ok << endl;

}

Measured memory_bytes: 4776
#include <bits/stdc++.h>
 #define ll long long
 #define int long long
 #define MOD  1000000007
 #define MAX 500005
 #include<iomanip>
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define x first
 #define y second
using namespace std;
 
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
      
}

 int32_t main()
{
    Need_for_speed(activated);
//    satisfy
//    {}
    ll h,a;
    cin>>h>>a;
    cout<<(h+a-1)/a<<endl;
    return 0;
}












Measured memory_bytes: 256
N, A, B, C, D = [int(_) for _ in input().split()]

dAB = B - A
dCD = (D - C) / 2
m = (C + D) / 2

x = A
v = 0
for i in range(2, N + 1):
    if x < B:
        x += m
    else:
        x -= m
    v += dCD

if x - v <= B <= x + v:
    print("YES")
else:
    print("NO")



Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
using Graph = vector<vector<int>>;

signed main() {
  int A, B, K;
  cin >> K >> A >> B;
  
  for( int i = A; i <= B; i++ ){
    if( i%K == 0 ){
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
struct req{
	long long a,b,c;
	long long d;
}r[1005];
int main()
{
	long long n,m,q;
	cin>>n>>m>>q;
	for(long long i=0;i<q;i++)
	{
		cin>>r[i].a>>r[i].b>>r[i].c>>r[i].d;
	}
	vector<long long> k;
	for(long long i=0;i<m;i++)
	{
		k.push_back(0);
	}
	for(long long i=0;i<n;i++)
	{
		k.push_back(1);
	}
	long long ans=0;
	do{
		long long cnt=1,cnt2=0;
		long long sum=0;
		vector<long long> v(n);
		for(long long i=1;i<m+n;i++)
		{
			if(k[i]==0)cnt++;
			else{
				v[cnt2]=cnt;//cout<<v[cnt2]<<" ";
				cnt2++;
			}
		}
		//cout<<endl;
		for(long long i=0;i<q;i++)
		{
			if(v[r[i].b-1]-v[r[i].a-1]==r[i].c)sum+=r[i].d;
			//cout<<v[r[i].a-1]<<" "<<v[r[i].b-1]<<" "<<r[i].c<<" "<<r[i].d<<endl;
		}
		//cout<<"s:"<<sum<<endl;
		ans=max(ans,sum);
	}while(next_permutation(k.begin(),k.end()));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <algorithm>
#include<iomanip>
#include<cmath>
using namespace std;

int main() {
	int n, a, b;
	cin >> n >> a >> b;

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int x = i;
		int temp = 0;
		while (x != 0) {
			temp += x % 10;
			x /= 10;
		}
		if (a <= temp && b >= temp)ans += i;
	}
	cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353;
ll gyaku(ll n){
  ll u=mod-2;
  ll ret=1;
  ll now=n;
  while(u>0){
    if(u%2==1){
      ret*=now;
      ret%=mod;
    }
    now*=now;
    now%=mod;
    u/=2;
  }
  return ret;
}
ll nck(ll n,ll k){
  if(n<k)swap(n,k);
  if(2*k>n)k=n-k;
  ll ret=1;
  for(ll i=1;i<=k;i++){
    ret*=gyaku(i);
    ret%=mod;
  }
  for(ll i=0;i<k;i++){
    ret*=(n-i);
    ret%=mod;
  }
  return ret;
}
int main(){
  ll n,a,b,k;cin>>n>>a>>b>>k;
  ll ans=0;
  ll cc[n+1];
  cc[0]=1;
  for(ll i=1;i<=n;i++){
    cc[i]=cc[i-1]*gyaku(i);
    cc[i]%=mod;
    cc[i]*=(n-i+1);
    cc[i]%=mod;
  }
  
  for(ll i=0;i<=n;i++){
    ll u=k-i*a;
    if(u<0)break;
    if(u%b==0&&u/b<=n){
      ll sum=cc[i]*cc[u/b];
      sum%=mod;
      ans+=sum;
      ans%=mod;
    }
  }
  cout<<ans%mod<<endl;
}
     

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

typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll LINF = 1e18;
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define MP make_pair
#define MT make_tuple
#define F first
#define S second
#define PB push_back
#define dump(x)  cout << #x << " = " << (x) << endl;	//debug
#define SZ(x) ((ll)(x).size())
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (ll i = (a); i >= (b); i--)
#define ps(s) cout << #s << endl;
#define pv(v) cout << (v) << endl;
#define pvd(v) cout << setprecision(16) << (v) << endl;
#define ALL(a)  (a).begin(),(a).end()
#define RANGE(a, start_index, num)  (a).begin()+(start_index),(a).begin()+(num)

int main() {
	string s;
	cin >> s;
	int lim = SZ(s) - 1;
	int res1 = 0, res2 = 0;
	FOR(i,0,lim){
		if(i%2==0){
			if (s[i] == '0')res2++;
			else res1++;
		}
		else {
			if (s[i] == '1')res2++;
			else res1++;
		}
	}
	int res = min(res1, res2);
	pv(res)
	return 0;
}

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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + (c ^ 48), c = nc;
  return x;
  #undef nc
}

typedef long long ll;
const int maxn = 2e5 + 10;
int n, A[maxn], ans[maxn];

vector <int> E[maxn];

int len, val[maxn];

void dfs(int u,int f){
  ans[u]=len;
  for(int v:E[u])if(v!=f){
    int pos=lower_bound(val+1,val+len+1,A[v])-val;
    int lst=val[pos];
    val[pos]=A[v];
    bool flg=pos>len;
    if(flg)len++;
    dfs(v,u);
    val[pos]=lst,len-=flg;
  }
}

void solve() {
  cin>>n;
  rep(i,1,n)A[i]=read();
  rep(i,2,n){
    int u=read(),v=read();
    E[u].push_back(v),E[v].push_back(u);
  }
  val[len=1]=A[1];
  dfs(1,0);
  rep(i,1,n)printf("%d\n",ans[i]);
}

int main() {
//  int T = read();
//  while (T--) solve();
  solve();
  return 0;
}

Measured memory_bytes: 30540
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args)throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    int[] v = new int[n];
    int[] c = new int[n];

    String[] str = in.readLine().split(" ");
    for(int i=0; i<n; i++) {
      v[i] = Integer.parseInt(str[i]);
    }
    str = in.readLine().split(" ");
    for(int i=0; i<n; i++) {
      c[i] = Integer.parseInt(str[i]);
    }
    
    int diff = 0;
    int ans = 0;
    for(int i=0; i<n; i++) {
      diff = v[i]-c[i];
      if(diff>0)
        ans += diff;
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 21460
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

int main() {
    // input
    int n, a; scanf("%d%d", &n, &a);
    vector<int> x(n); REP (i, n) scanf("%d", &x[i]);
    // solve
    int sum_x = accumulate(ALL(x), 0);
    auto dp = vectors(n + 1, sum_x + 1, ll());
    dp[0][0] = 1;
    REP (i, n) {
        REP_R (j, n) {
            REP (k, sum_x - x[i] + 1) {
                dp[j + 1][k + x[i]] += dp[j][k];
            }
        }
    }
    ll result = 0;
    REP3 (j, 1, n + 1) if (a * j <= sum_x) {
        result += dp[j][a * j];
    }
    // output
    printf("%lld\n", result);
    return 0;
}


Measured memory_bytes: 1280
h,w,d=map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]

dx = [0 for _ in range(h*w+5)]
dy = [0 for _ in range(h*w+5)]

for i in range(h):
    for j in range(w):
        dx[a[i][j]] = i
        dy[a[i][j]] = j

dfromd = [0 for _ in range(h*w+1)]

for i in range(d+1,h*w+1):
        dfromd[i] = dfromd[i-d]+abs(dx[i-d]-dx[i])+abs(dy[i-d]-dy[i])

q = int(input())
for _ in range(q):
    l,r=map(int,input().split())
    print(dfromd[r]-dfromd[l])

Measured memory_bytes: 56924
import time
import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = time.time()
ans = []
for a in A:
    heapq.heappush(ans, -a)

for _ in range(M):
    l = heapq.heappop(ans)
    heapq.heappush(ans, -((-l)//2) )

print(-sum(ans))

Measured memory_bytes: 14376
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        loop = range(10)
    else:
        loop = [int(s)]
    for j in range(13):
        for lo in loop:
            dp[(10*j+lo)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)


Measured memory_bytes: 43740
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int A[50];
int fib(int n){
	if(n==1 || n==0) A[n]=1;
	
	else if(A[n]) ;
	else A[n]=fib(n-1)+fib(n-2);
	return A[n];
}

int main (){
	int n;
	cin>>n;
	cout<<fib(n)<<endl;
	return 0;
}


Measured memory_bytes: 3096
using System;
using System.Linq;
using System.Collections.Generic;
public class Hello{
    public static void Main(){
        // Your code here!
        int[] array = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        int H = array[0];
        int W = array[1];
        //C#はstringの文字は書き換えられず，char型配列の要素は書き換えられるのでchar型の二重配列にしたほうがよい．
        char[,] board = new char[50,50];　
        
        //最初にあらかじめ各方向への移動を表す配列を用意しておくと便利
        int[] dx = {1,-1,0,0,1,1,-1,-1};
        int[] dy = {0,0,1,-1,1,-1,-1,1};
        
        for(int i = 0; i < H; i++) //読み込み
        {
            string line = Console.ReadLine();
            for(int j = 0; j < W; j++)
            {
                board[i, j] = line[j];
            }
        }
        
        for(int i = 0; i < H; i++)
        {
            for(int j = 0; j < W; j++)
            {
                if(board[i, j] == '#')
                {
                    continue;
                }
                int num = 0;
                
                for(int k = 0; k < 8; k++)
                {
                    
                    if(i + dy[k] < 0 || H <= i + dy[k]) continue;
                    if(j + dx[k] < 0 || W <= j + dx[k]) continue;
                    
                    if(board[i + dy[k], j + dx[k]] == '#')
                    {
                        num++;
                    }
                }
                
                //int型をchar型に変換
                board[i, j] = num.ToString()[0];
            }
        }
        
        for(int i = 0; i < H; i++)
        {
            for(int j = 0; j < W; j++)
            {
                Console.Write(board[i,j]);
            }
            Console.WriteLine();
        }
    }
}



Measured memory_bytes: 13396
n = gets.chomp.to_i

## これは n が数十を超えると計算量が大きくて使いものにならなくなる。
# def fibonacci(n)
#     return 1 if n == 0 || n == 1
#     return fibonacci(n - 2) + fibonacci(n - 1)
# end
# puts fibonacci(i)


## 動的計画法のメモ化再帰を使うと効果的。
# dp = []
# def dpFibonacci(n, dp)
#     if n == 0 || n == 1 then
#         dp[n] = 1
#         return dp[n]
#     end
#     return dp[n] if dp[n]
#     dp[n] = dpFibonacci(n - 2, dp) + dpFibonacci(n - 1, dp)
# end
# puts dpFibonacci(i, dp)


## もしくは動的計画法をループに展開したアルゴリズムとして実装することもできる。
## 下の loopedDpFibonacci は、与えられた配列 fib に第n項までのフィボナッチ数列を格納してくれる。
fib = []
def loopedDpFibonacci(n, fib)
    fib[0] = 1
    fib[1] = 1
    if n >= 2 then
        2.upto(n) do |i|
            fib[i] = fib[i - 2] + fib[i - 1]
        end
    end
end

loopedDpFibonacci(n, fib)
puts fib[n]


Measured memory_bytes: 6872
#include <bits/stdc++.h>
typedef long long ll;
#define  rep(i,a,b)for(long long i=a;i<b;++i)
#define  rrep(i,a,b)for(int i=a;i>=b;--i)
#define  yesno(flag)if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl;
using namespace std;
const ll INF=100000000000000LL;
const ll r197=1000000007;
typedef pair<ll,ll>P;
typedef pair<int,P>Pa;
bool Inframe(int a,int b,int c,int d,int h,int w){
	if(a+b>=0&&a+b<h&&c+d>=0&&c+d<w)return true;
	return false;
}
//void swap(ll a,ll b){
//	ll d;
//	d=a;
//	a=b;
//	b=d;
//	return;
//}
ll mypow(ll x,int m){
	if(m==0)return 1;
	if(m%2==0){
		int x2=mypow(x,m/2);
		return x2*x2;
	}else{
		int x2=mypow(x,m/2);
		return x2*x2*x;
	}
}
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
//    	cout<<b<<endl;
        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 ans=0;
ll total=0;
int m;
ll d[200003],c[200003];
string al="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main() {
	string str;
	cin>>m>>str;
	string ans="";
	rep(i,0,str.size()){
		int g=str[i]-'A';
		ans+=al[(g+m)%26];
	}
	cout<<ans<<endl;
		return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
int p[110];
typedef pair<int,pair<int,int> >P;
priority_queue<P,vector<P>,greater<P> >Q;
int main(){
  int n,m;
  while(cin>>n>>m&&n+m){
    for(int i=0;i<m;i++){
      int a,b,c;
      cin>>a>>b>>c;
      Q.push(make_pair(c,make_pair(a,b)));
    }
    for(int i=0;i<n;i++)p[i]=i;
    int ans=0;
    while(!Q.empty()){
      int a=Q.top().second.first,b=Q.top().second.second;
      int cost=Q.top().first;Q.pop();
      int x=a,y=b;
      while(p[x]!=x)x=p[x];
      while(a!=x)a=p[a],p[a]=x;
      while(p[y]!=y)y=p[y];
      while(b!=y)b=p[b],p[b]=y;
      if(x!=y){
	ans+=cost;
	p[x]=y;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

const int N=405;
const int mod=1e9+7;
int n,c,Max;
int a[N],b[N],sum[N][N],dp[N][N];

int main(void)
{
	scanf("%d%d",&n,&c);
	for(register int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for(register int i=1;i<=n;++i)
		scanf("%d",&b[i]);
	for(register int i=0;i<N;++i)
		sum[i][0]=1;
	for(register int i=0;i<N;++i)
		for(register int j=1;j<=c;++j)
			sum[i][j]=1ll*sum[i][j-1]*i%mod;
	for(register int i=1;i<N;++i)
		for(register int j=0;j<=c;++j)
			sum[i][j]=1ll*(sum[i-1][j]+sum[i][j])%mod;
	dp[0][0]=1;
	for(register int i=1;i<=n;++i)
		for(register int j=0;j<=c;++j)
			for(register int k=0;k<=j;++k)
				dp[i][j]=1ll*(dp[i][j]+1ll*dp[i-1][j-k]*(sum[b[i]][k]-sum[a[i]-1][k]+mod)%mod)%mod;
	printf("%d\n",dp[n][c]);
	return 0;
}

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

int main() {
    int H, W;
    cin >> H >> W;
    int odd_flag;
    if (W%2 == 0) odd_flag = 0;
    else odd_flag = 1;
    ll ans = 0;
    rep(i,H) {
    	if (H == 1 or W == 1) {
    		ans = 1;
    		break;
    	}
    	if (i%2 == 0 && odd_flag == 0) ans += W/2;
    	else if (i%2 == 0 && odd_flag == 1) ans += (W+1)/2;
    	else if (i%2 == 1) ans += W/2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		int[][] c = new int[3][3];
		for (int i = 0 ; i < 3 ; i++) {
			c[0][i] = sc.nextInt();
			c[1][i] = sc.nextInt();
			c[2][i] = sc.nextInt();
		}

		for (int i = 1 ; i < 3 ; i++) {
			for (int j = 1 ; j < 3 ; j++) {
				if (c[i-1][j-1] - c[i][j-1] != c[i-1][j] - c[i][j]) {
					System.out.println("No");
					System.exit(0);
				}
			}
		}
		System.out.println("Yes");
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include<vector>
#include<algorithm>
#include<numeric>

using namespace std;
#define qaz 20000

int m;
int parent(int i){
    return i/2;
    }

int left(int i){
    return 2*i;
    
}
int right(int i){
     return 2*i+1;
}

int a[qaz];
int main(void){
    cin>>m;
    for(int j=1;j<=m;j++){
        cin>>a[j];
    }
    
    for(int i=1;i<=m;i++){
        cout<<"node "<<i<<": key = "<<a[i]<<", ";
        if(parent(i)>=1)cout<<"parent key = "<<a[parent(i)]<<", ";
        if(left(i)<=m) cout<<"left key = "<<a[left(i)]<<", ";
        if(right(i)<=m) cout<<"right key = "<<a[right(i)]<<", ";
        cout<<endl;
    }

    return 0;
}




Measured memory_bytes: 3084