akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define DEBUG true
#ifdef ONLINE_JUDGE
#undef DEBUG
#define DEBUG false
#endif 

using namespace std;

#define MAXN ((int)2e5+5)
#define M ((int)1e5+5)
#define MOD (100000009)
#define INF (100000009)
#define ll long long
#define _ << " " <<
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define TRACE(x) if(DEBUG) cerr << #x << " = " << x << endl;
#define TRACE2(x,y) if(DEBUG) cerr << #x << " = " << x << " | " << #y << " = " << y << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pii pair<int,int>
#define mid ((l+r)/2)

int n,m;
vector <pii> v;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		int a,b;
		cin >> a >> b;
		v.pb({a,b});
	}
	sort(all(v));

	int res = 0;
	int it = 0;

	priority_queue <int> q;

	for (int i = 1; i <= m; ++i)
	{
		while(it < (int)v.size() && v[it].first <= i)
			q.push(v[it++].second);
		if(!q.empty())
		{
			res += q.top();
			q.pop();
		}
	}

	cout << res << endl;
}

Measured memory_bytes: 1908
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

N, M, K = map(int, input().split())
friend = UnionFind(N+1)
nocount = [[] for _ in range(N+1)]
ans = [0]*N
for i in range(M):
  a, b = map(int, input().split())
  friend.union(a,b)
  nocount[a].append(b)
  nocount[b].append(a)
for i in range(K):
  a, b = map(int, input().split())
  nocount[a].append(b)
  nocount[b].append(a)
for i in range(1, N+1):
  ans[i-1] = friend.size(i) -1
  for j in nocount[i]:
    if friend.same(i,j):
      ans[i-1] -= 1
print(*ans)

Measured memory_bytes: 110624
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
def solve(N,X,M):
    seen=set()
    order_seen=[]
    while X not in seen:
        seen.add(X)
        order_seen.append(X)
        X=f(X,M)
    pos=order_seen.index(X)  # Find position of when the cycle begins
    if pos>N:  # If position is greater than N, then we know we are not going to include any values from the cycle.
        return sum(order_seen[:N])
    terms_before_cycle=order_seen[:pos]
    sum_terms_before_cycle=sum(terms_before_cycle)
    ans=sum_terms_before_cycle
    terms_in_cycle=order_seen[pos:]
    sum_cycle=sum(terms_in_cycle)
    length_cycle=len(terms_in_cycle)
    number_remaining_terms=N-pos
    mult_factor=(number_remaining_terms)//length_cycle
    ans+=(sum_cycle*mult_factor)
    numb_remain=(number_remaining_terms)%length_cycle
    ans+=sum(terms_in_cycle[:numb_remain])
    return ans

# The function for the recurrence relation.  A_n+1=A_n^2%M
def f(A,M):
    return pow(A,2,M)

N,X,M=readMap()
print(solve(N,X,M))

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(15);
    cout << fixed;
    cin.tie(0);

    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c >= 22) {
        cout << "bust\n";
    } else {
        cout << "win\n";
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String S = sc.next();

        int ans = solve(S);
        System.out.println(ans);

    }

    private static int solve(String s) {
        char[] sn = s.toCharArray();
        int white = count(sn, '0', '1');
        int black = count(sn, '1', '0');
        return Math.min(white, black);
    }

    private static int count(char[] sn, char match, char counterpart) {
        int cnt = 0;
        for (int i = 0; i < sn.length; i++) {
            if (i % 2 == 0 && sn[i] == counterpart) {
                cnt++;
            }
            if (i % 2 == 1 && sn[i] == match) {
                cnt++;
            }
        }
        return cnt;
    }
}


Measured memory_bytes: 26232
a, b, c = sorted([int(i)for i in input().split()])
ans = 0
ma, mb, mc = [a % 2, b % 2, c % 2]

if ma == mb == mc:
    pass
elif ma != mb and mb == mc:
    b += 1
    c += 1
    ans += 1
elif ma == mc and ma != mb:
    a += 1
    c += 1
    ans += 1
elif ma == mb and mb != mc:
    a += 1
    b += 1
    ans += 1

ans += (c - b) // 2
ans += (c - a) // 2

print(ans)


Measured memory_bytes: 61856
#include<iostream>
#define MIN(a,b) (a)<(b)?(a):(b)
std::string s;
signed main(){std::cin>>s;int l(s.length()),t1(0),t2(0),ans(0);for(register int i(0);i<l;i++){s[i]==83?t1++:t2+=(t1>0),t1>=t2?ans+=MIN(t1,t2)<<1,t1-=MIN(t1,t2),t2=0:8;}return std::cout<<l-ans<<std::endl,0;}

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

using namespace std;

#define mp make_pair
#define pb push_back
#define repi(i, p, q) for (long i = p; i < q; i++)
#define repd(i, p, q) for (long i = p; i >= q; i--)
#define sz(x) x.size()
#define INF 2000000000
#define MOD 1000000007

typedef map<int, int> MI;
typedef pair<int, int> PI;
typedef long long int LLI;
typedef long int LI;
typedef int I;

int main() {
    int n,k;
    cin >> n >> k;
    int number = n%k;
    if(number == 0) {
        cout << 0;
    } else if(number < k) {
        cout << 1;
    }
}

Measured memory_bytes: 256
#include<iostream>
//#include<iomanip>
using namespace std;
int main()
{
    int ans=1,n,k,i=0;
    cin>>n>>k;
    while(i!=n)
    {
    	if(ans>=k)
    	{
    		ans=ans+k;
    		i++;
		}
    	if(ans<k)
    	{
    		ans=ans+ans;
    		i++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::collections::VecDeque;
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::collections::HashMap;

#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        #[allow(unused_variables)]
        #[allow(unused_mut)]
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
 
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };
 
    ($next:expr, chars) => {
        read_value!($next, string).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, bytes) => {
        read_value!($next, string).into_bytes()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("parse error")
    };
}

fn main() {
    input!{
        n: usize,
        m: usize,
        v: [usize; n]
    }
    let all: usize = v.iter().sum();
    let s = all / (4 * m) + if all % (4 * m) > 0 {1} else {0};
    let a = v.iter().filter(|&&x| x >= s).count();
    println!("{}", if a >= m {"Yes"} else {"No"});
}


Measured memory_bytes: 4352
/*
ID: yaoxinw2
TASK: test
LANG: C++
*/
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(b>=a){
		cout<<"unsafe"<<endl;
	}else{
		cout<<"safe"<<endl;
	}
	return 0;
} 

Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath> 
using namespace std;
double n,t,a,minn=999999999,mbh;
double h[1010];
int main()
{
	cin>>n>>t>>a;
	cin>>h[1];
	mbh=1,minn=t-h[1]*0.006;
	for(int i=2;i<=n;i++)
	  {
	  	cin>>h[i];
	  	double dq=t-h[i]*0.006;
	  	if(abs(dq-a)<=abs(minn-a))
	  	  {
	  	  	minn=dq;
	  	  	mbh=i;
			}
	  }
	cout<<mbh;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#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 equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



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

  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  FOR(i, k, n) cout << (a[i] > a[i - k] ? "Yes" : "No") << '\n';

  




  
  return 0;
}

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

using namespace std;

using ll = int;
using ld = long double;

using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using gr = vector<vll>;
using wgr = vector<vpll>;

#define pb push_back
#define FOR(i, m, n) for (ll i(m); i < n; i++)
#define DWN(i, m, n) for (ll i(m); i >= n; i--)
#define REP(i, n) FOR(i, 0, n)
#define DW(i, n) DWN(i, n, 0)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define D(n) DW(i, n)
#define DD(n) DW(j, n)
struct d_ {
    template<typename T> d_ & operator ,(const T & x) { cerr << ' ' <<  x; return *this;}
    template<typename T> d_ & operator ,(const vector<T> & x) { for(auto x: x) cerr << ' ' <<  x; return *this;}
} d_t;
#define dbg(args ...) { d_t,"|",__LINE__,"|",":",args,"\n"; }
#define EPS (1e-10)
#define INF (1LL<<61)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define all(x) begin(x),end(x)
#define IN(n) ll n;cin >> n;
#define x first
#define y second

const ll M = 507;
ll n;
ll h[M][M];
bool isfree[M][M];
bool valid(ll x, ll y) {
    return x>=0 && y>=0 && x<n && y<n;
}

const ll dx[]={1,0,-1,0};
const ll dy[]={0,-1,0,1};
const ll D = 4;

void dfs(ll i, ll j) {
    REP(d,D) {
        ll ii=i+dx[d], jj=j+dy[d];
        if(!valid(ii,jj)) continue;
        if(h[ii][jj] > h[i][j]+!isfree[i][j]) {
            h[ii][jj]=h[i][j]+!isfree[i][j];
            dfs(ii,jj);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin >> n;
    ll ret = 0;
    F(n)FF(n) h[i][j]=min(i, min(j, min(n-i-1, n-j-1)));
    F(n*n) {
        ll p; cin >> p; p--;
        ll x=p/n, y=p%n;
        ret += h[x][y];
        isfree[x][y] = 1;
        dfs(x,y);
    }
    cout << ret << endl;
    return 0;
}


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

using namespace std;

#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define sz(x) (int)(x).size()
#define f(n) for(int i=0;i<n;++i)
#define f2(n) for(int j=0;j<n;++j)
#define f3(n) for(int k=0;k<n;++k)
#define F(i,x,n,y) for(int i=x;i<n;i+=y)
#define FF(i,x,n,y) for(int i=x;i>=n;i-=y)
#define fa(x,y) for(auto x:y)

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

//Warsaw debug template
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
    enable_if<sizeof dud<c>(0) x 1,debug&>::type operator<<(c i){
sim > struct rge {c b,e;};
sim > rge<c> range(c i, c j) {return rge<c>{i,j};}
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug{
#ifdef LOCAL
~debug() {cerr<<endl; }
eni(!=) cerr<< boolalpha << i; ris;}
eni(==) ris <<range(begin(i),end(i)); }
sim, class b dor(pair<b,c> d){
ris<<"("<<d.first<<","<<d.second<<")";
}
sim dor(rge<c> d){
    *this << "[";
    for(auto it=d.b;it!=d.e;++it)
        *this <<"," +(it==d.b)<< *it;
    ris<<"]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) "["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"
//End of debug template

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    vi a(n+1);
    vi b(n);
    f(n+1) cin>>a[i];
    f(n) cin>>b[i];
    ll ans=0;
    f(n){
        if(b[i]>=a[i]){
            ans+=a[i];
            b[i]-=a[i];
            if(b[i]>=a[i+1]){
                ans+=a[i+1];
                a[i+1]=0;
            }else{
                ans+=b[i];
                a[i+1]-=b[i];
            }
        }else{
            ans+=b[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 4756
#include <stdio.h>
int main(void){
    // Your code here!
    int i,j,k,r,c;
    int a[101][101]={{0}};
    scanf("%d %d",&r,&c);
    for(i=0;i < r;i++){
        for(j=0;j<c;j++){
            scanf("%d",&a[i][j]);
            if(j==0){
                a[i][c]=a[i][0];
            }else{
                a[i][c]=a[i][c]+a[i][j];
            }
            if(i==0){
            a[r][j]=a[0][j];
        }else{
            a[r][j]=a[r][j]+a[i][j];
        }
        }
    }
    
     for(i=0;i < r;i++){
         if(i==0){
             a[r][c]=a[0][c];
         }else{
             a[r][c]=a[r][c]+a[i][c];
         }
     }
    for(i=0;i<r+1;i++){
         for(j=0;j<c+1;j++){
             printf("%d",a[i][j]);
             if(j==c)break;
             printf(" ");
         }
         printf("\n");
    }
    
    return 0;
}
    


Measured memory_bytes: 2124
import java.util.*;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
	    for(int i = 0; i < n; ++i)
		{
	        int gx = stdIn.nextInt();
	        int gy = stdIn.nextInt();
	        int p = stdIn.nextInt();
	        boolean[][][][] stage = new boolean[16][16][16][16];
	        for(int a = 0; a < 16; ++a)
	        {
	        	for(int b = 0; b < 16; ++b)
	        	{
	        		for(int c = 0; c < 16; ++c)
	        		{
	        			for(int d = 0; d < 16; ++d)
	        			{
	        				stage[a][b][c][d] = true;
	        			}
	        		}
	        	}
	        }
	        for(int j = 0; j < p; ++j)
			{
	        	int x1 = stdIn.nextInt();
	            int y1 = stdIn.nextInt();
	            int x2 = stdIn.nextInt();
	            int y2 = stdIn.nextInt();
	            stage[x1][y1][x2][y2] = false;
	            stage[x2][y2][x1][y1] = false;
	        }
	        int[][]dp = new int[17][17];
	        dp[0][0] = 1;
	        dp[1][1] = 1;
	        for(int y = 0; y <= gy; ++y)
			{
	            for(int x = 0; x <= gx; ++x)
				{
	                if(x == 0 && y == 0) continue;
	                if(x > 0 && stage[x - 1][y][x][y])
					{
	                    dp[y + 1][x + 1] += dp[y + 1][x];
	                }
	                if(y > 0 && stage[x][y - 1][x][y])
					{
	                    dp[y + 1][x + 1] += dp[y][x + 1];
	                }
	            }
	        }
			if(dp[gy + 1][gx + 1] == 0)
			{
				System.out.println("Miserable Hokusai!");
	        }
	        else
			{
	        	System.out.println(dp[gy + 1][gx + 1]);
	        }
	    }
	}
}

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

int findSumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int n,a,b;
    cin >> n >> a >> b;
    int total = 0;
    for (int i = 1; i<= n; ++i) {
        int sum = findSumOfDigits(i);
        if (sum >= a && sum <= b) {
            total += i;
        }
    }
    cout << total << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {

	int S;
	int h,m,s;
	scanf("%d",&S);

	h = S/3600;
	m = (S-h*3600)/60;
	s = S-h*3600-m*60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

Measured memory_bytes: 592
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
//        int[] a = new int[3];

        while (true) {
            int n = scan.nextInt(), x = scan.nextInt();
            if (n == 0 && x == 0) break;
            int count = 0;

            for (int i = 1; i < n + 1; i++) {
                for (int j = i + 1; j < n + 1; j++) {
                    for (int k = j + 1; k < n + 1; k++) {
                        if ((i + j + k) == x) {
                            if (!(i == k || j == i || k == j)) {
                                count++;
                            }

                        }
                    }
                }
            }
            System.out.println(count);
        }
    }
}

Measured memory_bytes: 26564
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
template<typename T> inline T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }





int n, k;
vector<int> a;

bool check(int x) { // 不必要
    
    if (a[x] >= k) return 0;
    
    int dp[n + 1][k + 1];
    fill_n(*dp, (n + 1) * (k + 1), 0);
    
    
    rep(j, n) {
        if (x == j) {
            rep(l, k + 1) dp[j + 1][l] = dp[j][l];
            continue;
        }
        
        rep(l, k + 1) {
            if (l == 0) {
                if (a[j] >= k - a[x] && a[j] < k) return 0;
                dp[j + 1][(a[j] > k ? k : a[j])] = 1;
            } else if (dp[j][l] == 0) continue;
            else {
                if (a[j] + l >= k - a[x] && a[j] + l < k) return 0; // 1にしてたorz
                dp[j + 1][(a[j] + l > k ? k : a[j] + l)] = 1;
            }
            
        }
    }
    
    return 1;
}

template<typename T>
void binary_search(T ok, T ng) {
    while (abs(ng - ok) > 1) {
        T mid = (ng + ok) / 2;
        // cout << mid << endl;
        (check(mid) ? ok : ng) = mid;
        // cout << ok << " " << ng << endl;
    }
    cout << ok + 1 << endl;
}






int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    
    
    cin >> n >> k;
    rep(i, n) { int A; cin >> A; a.eb(A); }
    sort(all(a));
    binary_search(-1, n);
    
}



Measured memory_bytes: 98048
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

namespace INPUT{
	const int L=1<<15;
	char _buf[L],*S,*T,c;
	char _gc(){
		if(S==T){
			T=(S=_buf)+fread(_buf,1,L,stdin);
			if(S==T) return EOF;
		}
		return *S++;
	}
	void readi(int &X){
		for(c=_gc();c<'0'||c>'9';c=_gc());X=c&15;
		for(c=_gc();c>='0'&&c<='9';X=X*10+(c&15),c=_gc());
	}
}
using INPUT::readi;

const int INF=5E8;
const int Maxn=1E5+5;

int N;
struct E{
	int v,w,nxt;
}adj[Maxn<<1];
int hed[Maxn],TE;
int siz[Maxn];
LL Ans;

void addedge(int u,int v,int w){
++TE,adj[TE].v=v,adj[TE].w=w,adj[TE].nxt=hed[u],hed[u]=TE;}

bool T(int X){
	if(N&1) return X<=N/2;
	return X<N/2;
}

void Dfs_1(int u,int Fa){
	siz[u]=1;
	for(int v,k=hed[u];k!=-1;k=adj[k].nxt)
		if((v=adj[k].v)!=Fa){
			Dfs_1(v,u);
			siz[u]+=siz[v];
			Ans+=(LL)adj[k].w*min(N-siz[v],siz[v])*2;
		}
}

void Dfs_2(int u,int Fa,int W){
	bool flag=true;
	for(int v,k=hed[u];k!=-1;k=adj[k].nxt)
		if((v=adj[k].v)!=Fa){
			Dfs_2(v,u,adj[k].w);
			flag&=T(siz[v]);
			if(!(N&1) && siz[v]==N/2)
				printf("%lld",Ans-adj[k].w),exit(0);
		}
	if(Fa) flag&=T(N-siz[u]);
	if(flag){
		if(Fa){
			int mn=W;
			for(int k=hed[u];k!=-1;k=adj[k].nxt)
				mn=min(mn,adj[k].w);
			printf("%lld",Ans-mn); exit(0);
		}
		else{
			int mn=INF;
			for(int k=hed[u];k!=-1;k=adj[k].nxt)
				mn=min(mn,adj[k].w);
			printf("%lld",Ans-mn); exit(0);
		}
	}
}

int main(){
	readi(N);
	memset(hed,-1,sizeof(hed));
	for(int u,v,w,i=1;i<N;++i)
		readi(u),readi(v),readi(w),
		addedge(u,v,w),addedge(v,u,w);
	Dfs_1(1,0),Dfs_2(1,0,INF);
	return 0;
}


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

ll calc_value(int x, const vector<pair<int, ll>> &buy) {
  ll sum_value = 0;
  for (auto z: buy) {
    if ((x | z.first) == x) sum_value += z.second;
  }

  return sum_value;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<pair<int, ll>> buy(n);
  for (int i = 0; i < n; i++) {
    int a;
    ll b;
    cin >> a >> b;
    buy[i] = {a, b};
  }

  ll ans = calc_value(k, buy);

  for (int i = 29; i >= 0; i--) {
    if (k & (1 << i)) {
      int x = (k ^ (1 << i)) | ((1 << i) - 1);
      ans = max(ans, calc_value(x, buy));
    }

  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1920
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-04-23 16:32:25
*/

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(),(x).end()
#define rev(x) greater<x>()
#define MOD 1000000007
#define INF 1000000000

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

LL modpower(LL n, LL m, LL mod)
{
    if (m == 0) {
        return 1;
    } else if (m % 2 == 0) {
        LL p = modpower(n, m/2, mod);
        return p*p % mod;
    } else {
        return n*modpower(n, m-1, mod) % mod;
    }
}

LL modinv(LL n, LL mod)
{
    return modpower(n, mod-2, mod);
}

LL modcombination(LL n, LL r, LL mod)
{
    LL ret = 1;

    for (int i = 0; i < r; i++) {
        ret *= (n-i);
        ret %= mod;
        ret *= modinv(i+1, mod);
        ret % mod;
    }

    return ret % mod;
}

int gcd(int k, int l)
{
    if (l > 0) return gcd(l, k%l);
    else return k;
}

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n) {
        for (int i = 0; i < n; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

    vector<bool> v(n, false);
    int cur = 0;
    int cnt = 0;
    int ans = -1;
    do {
        cnt++;
        v[cur] = true;
        if (a[cur] == 2) {
            ans = cnt;
        } else {
            cur = a[cur]-1;
        }
    } while (!v[cur]);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
long long s[100005];
int main(){
	long long n,a,b,i,num=0;
	cin>>n>>a>>b;
	for(i=1;i<=n;i++)
		cin>>s[i];
	for(i=1;i<n;i++)
		num+=min(a*(s[i+1]-s[i]),b);
	cout<<num<<endl;
}

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

int dp[1001][1001];
int main() {
	string a, b; cin >> a >> b;
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	rep(i, a.size() + 1)rep(j, b.size() + 1) {
		if (i < a.size()) {
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
			if (j < b.size()) {
				if (a[i] == b[j])dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
			}
		}
		if (j < b.size())dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + 1);
	}
	printf("%d\n", dp[a.size()][b.size()]);
}

Measured memory_bytes: 7256
/*
 * @Author: Kaizyn
 * @Date: 2020-06-18 16:58:32
 * @LastEditTime: 2020-06-18 17:24:49
 */ 
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const double eps = 1e-7;
const double PI = acos(-1);
typedef pair<int, int> pii;
const int MOD = 998244353;
const long long INF = 1e18;
const int N = 1e6+7;
const int dir[] = {0,-1,0,1,0};

struct Node {
  int x, y, d;
  long long dis;
  friend bool operator <(const Node &lhs, const Node &rhs) {
    return lhs.dis > rhs.dis;
  }
};

int n, m, k, bx, by, ex, ey;
vector<vector<int>> a;
vector<vector<long long>> dis[4];
priority_queue<Node> q;

inline long long solve() {
  cin >> n >> m >> k
      >> bx >> by >> ex >> ey;
  --bx; --by; --ex; --ey;
  a.resize(n, vector<int>(m));
  for (int i = 0; i < 4; ++i) {
    dis[i].resize(n, vector<long long>(m, INF));
  }
  for (int i = 0; i < n; ++i) {
    static string str;
    cin >> str;
    for (int j = 0; j < m; ++j) {
      a[i][j] = str[j] == '.';
    }
  }
  for (int i = 0; i < 4; ++i) {
    dis[i][bx][by] = 0;
    q.push(Node{bx, by, i, 0});
  }
  while (q.size()) {
    Node u = q.top();
    q.pop();
    int ux = u.x;
    int uy = u.y;
    if (u.dis > dis[u.d][ux][uy]) continue;
    for (int i = 0, vx, vy, vdis; i < 4; ++i) {
      vx = ux+dir[i];
      vy = uy+dir[i+1];
      if (vx < 0 || vy < 0 || vx >= n || vy >= m || !a[vx][vy]) continue;
      vdis = i == u.d ? u.dis+1 : (u.dis+k-1)/k*k+1;
      if (vdis >= dis[i][vx][vy]) continue;
      dis[i][vx][vy] = vdis;
      q.push(Node{vx, vy, i, vdis});
    }
  }
  long long res = INF;
  for (int i = 0; i < 4; ++i) {
    res = min(res, dis[i][ex][ey]);
  }
  return res >= INF ? -1 : (res+k-1)/k;
}

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

Measured memory_bytes: 46220
from collections import deque
def slidemax(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] <= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

def slidemin(X, k):
    q = deque([])
    ret = []
    for i in range(len(X)):
        while q and q[-1][1] >= X[i]:
            q.pop()
        deque.append(q, (i+k, X[i]))
        if q[0][0] == i:
            deque.popleft(q)
        if i >= k-1:
            ret.append(q[0][1])
    return ret

N, K = map(int, input().split())
A = [int(a) for a in input().split()]

a = 0
l = -1
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]: a = i
    if i >= K-1 and a <= i - K + 1:
        if i - l > 1: cnt += 1
        l = i

MA = slidemax(A, K)
MI = slidemin(A, K)
ans = 1 - max(cnt-1, 0)
l = -1
for i in range(K, N):
    if MI[i-K] != A[i-K] or MA[i-K+1] != A[i]:
        ans += 1

print(ans)

Measured memory_bytes: 98000
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
using namespace std;
//typedef __int64 LL;
//typedef long long int LL;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef pair<int,int> P;
//typedef pair<LL,LL> PL;

const int MOD=1000000007;

void ans(bool flag)
{
	if(flag)cout<<"Yes"<<"\n";
	else cout<<"No"<<"\n";
}

int main(){
	double pi=atan(1)*4;

	double a,b,h,m;
	cin>>a>>b>>h>>m;
	double po=((h+m/60)*30-m*6)/180*pi;
	//cout<<cos(po)<<"\n";
	cout<<setprecision(15)<<sqrt(a*a+b*b-2*a*b*cos(po))<<"\n";
	return 0;
}

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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

int n, m;

int main(){
	cin >> n >> m;
	cout << int((m*1900+(n-m)*100)*pow(2,m))<< endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,ans=0;
  cin>>N;
  vector<int> B(N-1);
  for(int i=0;i<N-1;i++) cin>>B[i];
  ans=B[N-2]+B[0];
  for(int j=N-2;j>0;j--) ans+=min(B[j],B[j-1]);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
s = input()
c = 0
cg = 0
for i in range(n):
    if s[i] == 'a':
        if c < a+b:
            c += 1
            print('Yes')
        else:
            print('No')
    elif s[i] == 'b':
        if c < a+b and cg < b:
            c += 1
            cg += 1
            print('Yes')
        else:
            print('No')
    else:
        print('No')



Measured memory_bytes: 4016
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF=1<<29;

vector<P> table[100000]; //隣接リスト to,cost
int d[100000]; //S→Gのcost
int preva[100000];
bool used[100000];
priority_queue<P> que;
int path;
bool use[100000];

void dijkstra(int s){
	fill(d,d+100000,INF);
	fill(used,used+100000,false);
	d[s]=0;
	que.push(P(s,0));

	while(!que.empty()){

		int Rto=que.top().first, Rcost=que.top().second; //中継点(Relay),S→Rのcost
		que.pop();
		if(used[Rto]) continue;
		if(Rcost > d[Rto]) continue;
		used[Rto]=true;

		for(int i=0;i<table[Rto].size();i++){
			int to=table[Rto][i].first, cost=table[Rto][i].second; //目的地(G),R→Gのcost
			if(d[to] > cost + Rcost){
				d[to] = cost + Rcost;
				que.push( P(to,d[to]) );
				preva[to]=Rto;
			}
		}

	}
}

int dfs(int s){
	int res=0;
	for(int i=0;i<table[s].size();i++){
		if(use[table[s][i].first]) continue;
		use[table[s][i].first]=true;
		res++;
		res+=dfs(table[s][i].first);
	}
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin>>N;
	for(int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		a--; b--;
		table[a].push_back(make_pair(b,1));
		table[b].push_back(make_pair(a,1));
	}
	for(int i=0;i<1000;i++) preva[i]=-1;
	dijkstra(0);

	vector<int> path;
	for(int t=N-1;t!=-1;t=preva[t]) path.push_back(t);
	reverse(path.begin(),path.end());
	int fennec,snuke;
	fennec=path[(path.size()+1)/2-1];
	snuke=path[(path.size()+1)/2];

	for(int i=0;i<N;i++) use[i]=false;
	use[fennec]=true;
	use[snuke]=true;
	int ans=dfs(fennec)+1;
	if(ans>N-ans) cout<<"Fennec"<<endl;
	else cout<<"Snuke"<<endl;
	return 0;
}

Measured memory_bytes: 9592
#include<stdio.h>
int main(){
  int h,w,i,j,a;
  while(scanf("%d %d",&h,&w)){
    if(h==0 && w==0)break;
    for(i=1;i<=h;i++){
      for(j=1;j<=w;j++){
	a=(i+j)%2;
	if(a!=0)printf(".");
	if(a==0)printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}	

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main()
{
	int N;
	cin >> N;
	ce(N*N*N)
    return 0;
}



Measured memory_bytes: 764
#include <stdio.h>
#include <string.h>

int main(void)
{
    int n, i, j;
    int count = 0;
    char w[100][11];
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    scanf("%s", w[i]);

    for (j = 0; j < n; j++)
    {
        for (i = j + 1; i < n; i++)
        {
            if (!strcmp(w[j], w[i])) {
                count ++;
            }
        }
    }

    for (i = 0; i < n - 1; i++)
    {
        if (w[i][strlen(w[i]) - 1] != w[i + 1][0]) {
            count ++;
        }
    }

    if (count == 0) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


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

int main()
{
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s.at(i) == '1') {
            cnt++;
        }
    }

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

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

double fave(double x1,double x2){
  return (x1 + x2) / 2.0;
}

int main() {
  int N;
  cin >> N;
  
  vector<int> Vi;
  
  rep(i,N){
    int tmpVi = 0;
    cin >> tmpVi;
    Vi.push_back(tmpVi);
  }
  
  sort(Vi.begin(), Vi.end());
  
  double ans = fave((double)Vi.at(0),(double)Vi.at(1));

  rep(i,N-2){
    ans = fave(ans,(double)Vi.at(i+2));
  }
  
  cout << fixed;
  cout << setprecision(10) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

const int MOD = 1000000007;

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

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

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

void debug(VS &board){
	int h = board.size();
	rep(i,h){
		cout<<board.at(i)<<endl;
	}
	return;
}

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

LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	int n;
	cin>>n;
	cout<<(n%1000?1000-n%1000:0)<<endl;
	return 0;
}


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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = (1 << 30);
constexpr ll L_INF = (1ll << 62);

//==================================

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

    int D, G;
    cin >> D >> G;

    Vi p(D), c(D);
    for (int i = 0; i < D; ++i) {
        cin >> p[i] >> c[i];
    }

    int ans = I_INF;
    int bit_sup = (1 << D);
    for (int bit = 0; bit < bit_sup; ++bit) {
        int ac = 0;
        int point = 0;
        for (int i = 0; i < D; ++i) {
            if (bit & (1 << i)) {
                ac += p[i];
                point += 100 * (i + 1) * p[i] + c[i];
            }
        }

        if (point >= G) {
            ans = min(ans, ac);
        }
        else {
            int nfull;
            for (int i = D - 1; i >= 0; --i) {
                if ((bit & (1 << i)) == 0) {
                    nfull = i;
                    break;
                }
            }
            int ac2 = (G - point + 100 * (nfull + 1) - 1) / (100 * (nfull + 1));
            if (ac2 < p[nfull]) {
                ans = min(ans, ac + ac2);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

typedef long long ll;

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

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;

const double PI = acos(-1.0);

int N,Q;
vector<ll> a,x;
ll solve(ll K){
    ll r = 0;
    ll sum = 0;
    ll res = 0;
    for(ll l = 0; l < N; l++){
        while(r < N && sum + a[r] <= K){
            sum += a[r];
            r++;
        }
        res += r - l;
        if(l == r)r++;
        else sum -= a[l];
    }
    return res;
}
int main() {
    cin>>N>>Q;
    a.resize(N);
    x.resize(Q);
    rep(i,N)cin>>a[i];
    rep(i,Q)cin>>x[i];
    rep(i,Q){
        cout<<solve(x[i])<<endl;;
    }
}


Measured memory_bytes: 3620
/*
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1192&lang=jp
2????????????????¶?????¨?????????´???????¨????????¨?????????????????????°?¶?????¨??????§????¨????????¨???????????????§?????????????????????????¨??????????.
 */

#include<iostream>
using namespace std;
int X, Y, S;
int solve() {
  int p = 1, q = S-1, r, u, t, max = 0;
  while(p <= S/2) {
    r = (100 * p + 99) / (100 + X);
    u = (100 * q + 99) / (100 + X);
    if ( r*(100+X)/100 != p || u*(100+X)/100 != q) goto next;
    t = r * (100 + Y) / 100 + u * (100 + Y) / 100;
    if (t > max) max = t;
  next:
    ++p;
    --q;
  }
  return max;
}
  
int main(){
  while(cin >> X >> Y >> S && X > 0) {
    cout << solve() <<endl;
  }
  return 0;
}

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

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    cout << "vowel" << endl;
    return 0;
  }
  cout << "consonant" << endl;
  return 0;
}

Measured memory_bytes: 3620
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
if n==1:
        print(1)

else:
    for i in range(n-1):
            if a[i]!=a[i+1]:
                    b.append(a[i])

    b.append(a[n-1])
    ans=1

    for i in range(len(b)-1):
            c.append(b[i+1]-b[i])

    d=c[0]
    for i in range(1,len(b)-1):
            if d*c[i]>=0:
                    d=c[i]
            else:
                    ans+=1
                    d=0
    print(ans)




Measured memory_bytes: 14436
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;

int main() {
    ll k;
    cin >> k;

    if(k%2 == 0) {
        out(-1);
        re0;
    }

    if(7%k == 0) {
        out(1);
        re0;
    }

    ll x = 7;
    exrep(i, 2, 1000000) {
        x = (x * 10 + 7) % k;
        if(x == 0) {
            out(i);
            re0;
        }
    }
    
    out(-1);
    re0;
}

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

int main(){
    int N;

    cin >> N;

    if(65<=N&&N<=90){
        cout << '1' << endl;
    }

    else if(97<=N&&N<=122){
        cout << '2' << endl;
    }

    else{
        cout << '0' << endl;
    }

    return 0;
}


Measured memory_bytes: 3116
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a;
    int ans=0;
    for(int i=0;i<n;i++){
      a=sc.nextInt();
      while(a%2==0){
        a/=2;
        ans++;
      }
    }
    System.out.println(ans);
  }
}

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

using namespace std;
int main() {
  int n, t, a;
  cin >> n >> t >> a;
  double diffMax = 9999999999;
  int result = -1;
  for (int i = 0; i < n; i++) {
    int h;
    cin >> h;
    double temp = t - h * 0.006;
    double diff = abs(a - temp);
    if (diffMax > diff) {
      diffMax = diff;
      result = i;
    }
  }
  cout << result + 1 << endl;
  return 0;
}

Measured memory_bytes: 256
def sixprint(s):
    l = len(str(s))

    return str(0)*(6-l) + str(s)

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

l = []
dic = {}
for i in range(M):
    pp,yy = map(int,input().split())
    lis = [i,pp,yy]
    l.append(lis)
    dic[pp] = 1

lll = sorted(l,key=lambda x:x[2])

for i in range(M):
    lll[i].append(dic[lll[i][1]])
    dic[lll[i][1]] += 1
llll = sorted(lll,key=lambda x:x[0])

for i in range(M):
    print(sixprint(llll[i][1]) + sixprint(llll[i][-1]))


Measured memory_bytes: 36844
#include<stdio.h>

int main() {
	int n,i,a[100];
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[n-i-1]);
	}
	for (i = 0; i < n - 1; i++) {
		printf("%d ", a[i]);
	}
	printf("%d\n", a[n - 1]);
	return 0;
}

Measured memory_bytes: 596
#if 0
cat <<EOF >mistaken-paste
#endif
// thanks for @rsk0315_h4x

#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
#define _USE_MATH_DEFINES

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

#define BIG 2000000007
#define VERYBIG 2000000000000007LL

#define MOD 1000000007
#define FOD  998244353
typedef uint64_t ull;
typedef  int64_t sll;

#define N_MAX 1000000


ull n, m;

sll a[N_MAX + 5];
char s[N_MAX + 1];

bool func (ull x) {
	ull dsum = 0;
	ull flow = 0;
	ull xv = x;
	for (sll i = 0; i < n; i++) {
		flow += a[i] + xv % 10;
		dsum += flow % 10;
		flow /= 10;
		xv /= 10;
	}

	return (dsum <= x);
}

ull solve () {
	sll i, j, ki, li;
	sll result = 0;
	sll sum = 0;

	n = strlen(s);
	j = n - 1;
	sum = 0;
	for (i = 0; i < n + 10; i++) {

		if (j >= 0) {
			sum += (s[j] - '0') * 9;
		}
		a[i] = sum % 10;
		sum /= 10;

		j--;
	}

	n += 10;

	ull ok = VERYBIG, ng = 0;
	while (ng + 1 < ok) {
		ull med = (ok + ng) / 2;
		if (func(med)) {
			ok = med;
		} else {
			ng = med;
		}
	}
	result = (ok - 1) / 9 + 1;

	printf("%lld\n", result);
	return 0;
}

int32_t main (void) {
	scanf("%s", s);
	solve();
	return 0;
}


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

int main(){
  int r,g,b;
  cin >> r  >> g  >> b;
  r *= 100;
  g *= 10;
  int i = r + g + b;

  if (i % 4 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
}

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

int n,m,sum;
int a[10004];

int main(){

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

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

    return 0;
}

Measured memory_bytes: 3680
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map { it.toLong() }
    var total:Long = 0
    for (i in k until n+2){
        val max = ((2 * n - i + 1) * i) / 2
        val min = ((i - 1) * i ) / 2
        total += max - min + 1
    }
    total %= 1000000007
    println(total)
}



Measured memory_bytes: 36460
"""
~~ Author : Bhaskar
~~ Dated : 01~06~2020
"""

import sys
from bisect import *
from math import floor,sqrt,ceil,factorial as F,gcd,pi
from itertools import chain,combinations,permutations,accumulate
from collections import Counter,defaultdict,OrderedDict,deque
from array import array
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
mod = 1000000007
lcm = lambda a,b : (a*b)//gcd(a,b)
setbit = lambda x : bin(x)[2:].count("1")

def solve():
    n = int(sys.stdin.readline())
    d = Counter()
    while n%2 == 0:
        d[2] += 1
        n //= 2
    i = 3
    while i*i < n:
        if n%i == 0:
            while n%i == 0:
                d[i] += 1
                n //= i
        i += 2
    if n != 1:
        d[n] += 1
    ans = 0
    for k,v in d.items():
        minn = 1
        while v-minn >= 0:
            v -= minn
            minn +=1
            ans += 1
    print(ans)

if __name__ == "__main__":
    try:
        sys.stdin = open("input.txt","r")
    except :
        pass
    solve()


Measured memory_bytes: 9492
#include<iostream>
using namespace std;
int p,q,ans=1,j;

int so(int n){
  for(int i=2;i*i<=n;i++)if(n%i==0)return 1;
  return 0;
}

int main(){
  cin>>p>>q;
  if(so(q)){
    for(int i=2;q>=i;i++){
      for(j=0;q%i==0;j++){
	q/=i;
	if(p%i==0)p/=i,j--;
      }
      if(j==0)continue;
      /*if(p%(i*j)==0)p/=(i*j);
	else*/ ans*=i;
    }
    cout<<ans<<endl;
  }else cout<<q<<endl;
  return 0;
}

Measured memory_bytes: 3100
input = STDIN.read
blue_lines = input.lines[0].to_i
blues = input.lines[1, blue_lines]
red_lines = input.lines[blue_lines+1].to_i
reds = input.lines[blue_lines+2, red_lines]

words = Hash.new(0)
blues.each { |b| words[b] = words[b] + 1 }
reds.each { |r| words[r] = words[r] - 1 }

val = words.sort {|(k1, v1), (k2, v2)| v2 <=> v1}.first.last
if val > 0
  puts val
else
  puts 0
end

Measured memory_bytes: 1788