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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
    ll h,w;cin>>h>>w;
   vector<string>s(h);
   vector<vector<ll>>tmp(h,vector<ll>(w,0));
    for (int i = 0; i < h; ++i) {
        cin >>s[i];
    }
    for (int i = 0; i < h; ++i) {
        ll now=0;vector<ll>memo;
        for (int j = 0; j < w; ++j) {
            if(s[i][j]=='.')now++;
            else {
                memo.push_back(now);
                now=0;
            }
        }
        memo.push_back(now);
        ll k=0;
        for (int j = 0; j < w; ++j) {
            if(s[i][j]=='.')tmp[i][j]+=memo[k];
            else k++;
        }
    }
    for (int i = 0; i < w; ++i) {
        ll now=0;vector<ll>memo;
        for (int j = 0; j < h; ++j) {
            if(s[j][i]=='.')now++;
            else {
                memo.push_back(now);
                now=0;
            }
        }
        memo.push_back(now);
        ll k=0;
        for (int j = 0; j < h; ++j) {
            if(s[j][i]=='.')tmp[j][i]+=memo[k];
            else k++;
        }
    }
    ll ans=0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
           ans=max(ans,tmp[i][j]-1);
        }
    }
    cout <<ans <<endl;
    return 0;
}


Measured memory_bytes: 35712
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,W;
    cin >> N >> W;
    int w[N];
    int v[N];
    for(int i=0;i<N;i++)cin >> w[i] >> v[i];

    vector<vector<long> >dp(N+1,vector<long>(W+1,0));
    for(int i=0;i<N;i++){
        for(int j=0;j<w[i];j++){
            dp[i+1][j] = dp[i][j];
        }

        for(int j=0;j<W;j++){
            if(j+w[i] <= W){
                dp[i+1][j+w[i]] = max(dp[i][j] + v[i], dp[i][j+w[i]]);
            }
        }
    }
    
    
    long maxx = 0;
    for(int i=0;i<=W;i++){
        if(maxx < dp[N][i])maxx = dp[N][i];

    }
    cout << maxx << endl;
}


Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
int dp[3001][3001];
int main()
{
	int i,j;
	string a,b;
	cin>>a>>b;
	int n1,n2;
	n1=a.length();
	n2=b.length();
	for(i=0;i<=n1;i++)
	dp[n1][0]=0;
	for(i=0;i<=n2;i++)
	dp[0][n2]=0;
	for(i=1;i<=n1;i++)
	{
		for(j=1;j<=n2;j++)
		{
			if(a[i-1]==b[j-1])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				//dp[i][j].push_back(a[i-1]);
				//dp[i][j].append(a,i-1,1);
			}
			else
			{
				if(dp[i-1][j]>=dp[i][j-1])
				dp[i][j]=dp[i-1][j];
				else
				dp[i][j]=dp[i][j-1];
			}
		}
	}
//	for(i=0;i<n2;i++)
	//	cout<<" "<<b[i];

//	for(i=1;i<=n1;i++)
//	{
//		//cout<<a[i]<<" ";
//		for(j=1;j<=n2;j++)
//		{
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	i=n1;j=n2;int k=0;
	string s="";
	for(;i>0 && j>0;)
	{
	//	cout<<i<<" "<<j<<endl;
			if(dp[i-1][j]==dp[i][j] || dp[i][j-1]==dp[i][j])
			{
				if(dp[i-1][j]>=dp[i][j-1])
				{
					i--;
				}
				else
				j--;
				
			}
			else
			{
			//	cout<<"true";
				s+=a[i-1];
				i--;j--;
			}
		
	}
	for(i=s.length()-1;i>=0;i--)
	cout<<s[i];
	return 0;
}

Measured memory_bytes: 35456
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
//================================================

int a = 0, b = 0, c, d, n, k=0;
string s, t;


int main()
{
	int n;
	cin >> n;
	vector<int> x(n);
	rep(i, n)
		cin >> x[i];
	int  m = 100000000;
	for(int i=1;i<=100;i++)
	{
		int sum = 0;
		rep(j, n)
		sum += (x[j] - i) * (x[j] - i);
	m = min(sum,m);
	}
	cout << m << endl;
	return 0;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;


void main() {
    string s;
    long k;

    scan(s);
    scan(k);
    k--;

    int pos = -1;
    char nm = '1';

    foreach (i ; 0 .. s.length) {
        if (s[i] != '1') {
            nm = s[i];
            pos = i.to!int;
            break;
        }
    }

    if (nm == '1') {
        writeln(1);
    }
    else {
        if (k < pos) {
            writeln(1);
        }
        else {
            writeln(nm);
        }
    }
}






















void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define gcd std::__gcd
#define EB emplace_back
#define get Get

typedef std::pair <int, int> pr;

struct _hash_ {
	typedef unsigned long long u64;
	static std::hash <u64> H;
	inline size_t operator () (const pr &x) const {return H(x.first | (u64)x.second << 32);}
};

typedef std::unordered_map <pr, int, _hash_> umap;
typedef std::vector <int> vector;
const int N = 254, mod = 998244353;

int n, cnt = 0;
int x[N], y[N], pw2[N];
umap M;
vector ps[N * N];

inline int get(const pr &v) {
	umap::iterator it; bool ret;
	std::tie(it, ret) = M.emplace(v, cnt + 1);
	return ret ? ++cnt : it->second;
}

inline int gw(int n) {return (pw2[n] - n - 1 + mod) % mod;}

int main() {
	int i, j, A, B, d, m, ans = 0;
	scanf("%d", &n);
	for (*pw2 = i = 1; i <= n; ++i) pw2[i] = pw2[i - 1] * 2 % mod;
	M.reserve(n * n), M.rehash(n * n * n);
	for (i = 0; i < n; ++i) {
		scanf("%d%d", x + i, y + i);
		for (j = 0; j < i; ++j) {
			d = gcd(A = y[i] - y[j], B = x[j] - x[i]);
			if (A /= d, B /= d, A < 0) A = -A, B = -B;
			d = get(pr(A, B)), ps[d].EB(i), ps[d].EB(j);
		}
	}
	for (auto &v : M) {
		std::tie(A, B) = v.first;
		vector &p = ps[v.second];
		std::sort(p.begin(), p.end());
		p.erase(std::unique(p.begin(), p.end()), p.end());
		for (int &k : p) k = A * x[k] + B * y[k];
		std::sort(p.begin(), p.end()), m = p.size();
		for (i = j = 0; i < m; i = j) {
			for (; j < m && p[i] == p[j]; ++j);
			ans += gw(j - i);
		}
	}
	ans = pw2[n] - n - 1 - ans;
	printf("%d\n", ans + (ans >> 31 & mod));
	return 0;
}

Measured memory_bytes: 67124
require 'pp'
def q a;PP.pp(a, STDERR);end

n = gets.to_i
xs = gets.split.map(&:to_i)

zeros = [0] * n
ac = 0
n.times do |i|
  if xs[n - i - 1] == 0
    ac += 1
    zeros[n-i-1] = ac
  else
    ac = 0
  end
end

ans = 0
n.times do |i|
  j = i
  sum = 0
  xor = 0
  while j < n
    if zeros[j] > 0
      ans += zeros[j]
      j += zeros[j]
    else
      sum += xs[j]
      xor ^= xs[j]
      if sum == xor
        ans += 1
      else
        break
      end
      j += 1
    end
  end
end

p ans


Measured memory_bytes: 18324
a, b, c, d = [int(i) for i in input().split()]

turn = 0
while a > 0 and c > 0:
    if turn == 0:
        c -= b
    else:
        a -= d
    turn = 1 - turn

if c <= 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 61744
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <set>
using namespace std;



int main(int argc, const char * argv[]){
    while(true){
        string str[2] = {"", ""};
        string result[2] = {"", ""};
        int pointer[2] = {0, 1};
        
        cin >> str[0];
        if(str[0][0] == '-') return 0;
        cin >> str[1] >> result[0];
        result[2] = "";
        // pointer[0] = 0;
        // pointer[1] = 1;
        char next = str[1][0];
        
        int i = 0;
        while(i < result[0].length()){
            if(next == result[0][i]){
                // push down
                next = str[0][pointer[0]];
                pointer[0]++;
                i++;
            }else{
                //push right
                cout << next;
                next = str[1][pointer[1]];
                pointer[1]++;
            }
        }
        cout << next;
        for(;pointer[1] < str[1].length(); pointer[1]++){
            cout << str[1][pointer[1]];
        }
        cout << result[2] << endl;
    }
}

Measured memory_bytes: 1188
import java.util.*;
import static java.lang.Integer.*;
//import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		Integer a[] = new Integer[3];
		a[0] = parseInt(sc.next());
		a[1] = parseInt(sc.next());
		a[2] = parseInt(sc.next());
		sc.close();
		Arrays.sort(a, Collections.reverseOrder());
		int ans = a[0]*10+a[1]+a[2];
		out.println(ans);
	}
}


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

using namespace std;

#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair

typedef long long LL;
typedef pair<int,int> pi;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){
    os << v.first <<" "<<v.second<<endl;
    return os;
}

int main()
{
    LL A,B;
    cin >> A >> B;
    if(A < B) swap(A,B);
    if(A == B || (A-1) == B) cout << "Brown" << endl;
    else cout << "Alice" <<endl;

    return 0;
}


Measured memory_bytes: 256
#B - Making Triangle
N = int(input())
L = list(map(int,input().split()))
count = 0
for i in range(N-2):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]+L[j]>L[k] and L[i]+L[k]>L[j] and L[k]+L[j]>L[i] and L[i] != L[j] and L[j] != L[k] and L[k]!=L[i]:
                count += 1
            else:
                pass

print(count)

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

int main()
{
    vector<int> v(3);
    cin >> v[0] >> v[1] >> v[2];
    sort(v.begin(), v.end());

    int ans = 0;
    if ((v[1] - v[0]) % 2 == 0)
    {
        ans += (v[1] - v[0]) / 2;
        v[0] += ans * 2;
    }
    else
    {
        v[0]++;
        v[2]++;
        ans++;

        int sub = v[1] - v[0];
        v[0] += sub;
        ans += sub / 2;
    }

    if ((v[2] - v[0]) % 2 == 0)
    {
        ans += v[2] - v[0];
    }
    else
    {
        v[0]++;
        v[1]++;
        ans++;
        ans += v[2] - v[0];
    }

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

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

int main() {

	ll n, k; cin >> n >> k;
	vector<ll> h(n);
	for (ll i = 0; i < n; i++) {
		cin >> h[i];
	}
	sort(h.begin(), h.end());
	ll ans = 10000000000;
	for (ll i = 0; i < n - k + 1; i++) {
		ll tmp = h[i + k - 1] - h[i];
		ans = min(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, Y;
  cin >> N >> Y;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; i+j <= N; j++) {
      if (i*10000ll+j*5000ll+(N-i-j)*1000ll == Y) {
        cout << i << ' ' << j << ' ' << N-i-j;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1";
}

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

signed main(){
	int n,q;
	cin >> n >> q;
	for(int i = 0;i < q;i++){
		int a,b;
		cin >> a >> b;
		if(n == 1) cout << min(a,b) << endl;
		else{
			while(a != b){
				if(a > b) swap(a,b);
				b = (b + n - 2) / n;
			}
			cout << a << endl;
		}
	}
	return 0;
}

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

using namespace std;

int main() {
    #ifdef LOCAL
    freopen("in", "r", stdin);
    #endif // LOCAL
    ios::sync_with_stdio(0); cin.tie(0);
    int64_t x, k, d;
    cin >> x >> k >> d;
    int64_t step = abs(x) / d;
    if (step > k) cout << abs(x) - k * d;
    else {
        if ((k - step) % 2 == 0) cout << abs(x) % d << endl;
        else cout << min(abs(x % d + d), abs(x % d - d)) << endl;
    }
    return 0;
}


Measured memory_bytes: 3600
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<functional>
#include <random>
#include<iostream>
#include<iomanip>
using namespace std;

int grid[1024][1024];
int grid_moto[11][1024];
int grid_honto[11][1024];

int bit_sum(int a) {
	int ret = 0;
	while (a > 0) {
		ret += a % 2;
		a = a >> 1;
	}
	return ret;
}

int main() {
	int N, M;
	int H, W;
	bool swapped = false;
	cin >> N >> M;
	if (N > M) { int swap = N; N = M; M = swap; swapped = true; }
	H = 1 << N;
	W = 1 << M;


	for (int i = 1; i < N + 1; i++) {
		for (int j = 0; j < (1 << i); j++) {
			for (int k = 0; k < W / (1 << i); k++) {
				grid_moto[i-1][j*W / (1 << i) + k] = j % 2;
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			grid[i][j] = 0;
			for (int k = 0; k < N; k++) {
				if ((i >> k) % 2 == 1) {
					grid[i][j] = grid[i][j] ^ grid_moto[k][j];
				}
			}
		}
	}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (i == 0 || j == 0) { grid_honto[i][j] = 0; }
			else {
				grid_honto[i][j] = grid[i][j] ^ grid[i - 1][j] ^ grid[i][j - 1] ^ grid[i - 1][j - 1];
			}
		}
	}
	if (!swapped) {
		for (int i = 1; i < H; i++) {
			for (int j = 1; j < W; j++) {
				cout << grid_honto[i][j];
			}
			cout << "\n";
		}
	}
	else {
		for (int i = 1; i < W; i++) {
			for (int j = 1; j < H; j++) {
				cout << grid_honto[j][i];
			}
			cout << "\n";
		}
	}
}

Measured memory_bytes: 5504
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]){
        char buf[128]={0};
        long long X = 0;
        string str1;
        long long a = 0, b = 0;

        getline(cin, str1);
        strcpy(buf, str1.c_str());
        X = atoll(buf);
        a = X/500;
        b = (X-(a*500))/5;

        printf("%lld\n", 1000*a+5*b);

        return 0;

}

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

/*任意の2か所の符号を変えることは可能、例えばデータ格納配列A[N]が存在するとする。
A[i]とA[j]の二つの符号を変えたいとき、A[i]とA[i+1]、A[i+1]とA[i+2]、...、A[j-1]とA[j]と
選択していくと、A[i]とA[j]の間の値はいずれも(-1)を二回かけられているため元の値に戻る
よって負の値を正の値に変えていけばよいが、負の値が奇数個であった場合、一か所だけ
正の値に戻すことができない。(正の値に戻すにはペアを作らなければならないから)
よって絶対値の最小値を残すようにする。例外として、0がある場合は任意の負の値と0を
ペアとすることで処理可能*/

int abs(int a){
  if(a < 0)
    return -a;
  else
    return a;
}

int main(){       
  int N;
  cin >> N;
  
  int nmax = 1e9;                           //値の絶対値の最小値
  int minus_c = 0;                           //負の値の数
  int64_t sum = 0;                         //入力した値の絶対値の和
  bool exist_0 = false;                //入力値に0が含まれているか否か
  vector<int> A(N);                    //入力値の格納先

  for(int i = 0; i < N; i++){
    int val;
    cin >> val;
    A[i] = val;
    
    if(abs(val) < nmax)                  //絶対値が最小の入力値を格納
      nmax = abs(val);
    
    if(val < 0)                                      //負の値の数を格納
      minus_c++;
    else if(val == 0)                        //0の存在を確認
      exist_0 = true;

    sum += abs(val);
  }

  if(exist_0)
    cout << sum << endl;
  else if(minus_c & 1)
    cout << sum - 2 * nmax << endl;
  else
    cout << sum << endl;

  return 0;
  
}
  

Measured memory_bytes: 640
n = int(input())
lis = []
for i in range(n):
    a, b = map(int, input().split())
    lis.append((a-b, a+b))

lis.sort(key=lambda x: x[1])
cnt = 0
INF = 10**9
prev_r = -INF

for l, r in lis:
    if l < prev_r:
        continue
    cnt += 1
    prev_r = r
print(cnt)


Measured memory_bytes: 18260
#include <bits/stdc++.h>
using namespace std;
int keta(int n){
  int digit = 0;
  while(n != 0) {
    n = n / 10;
    digit = digit + 1;
  }
  return digit;
}
int main() {
  int N, count = 0;
  cin >> N;
  for(int i = 1; i < N+1; i++) {
    if(keta(i)%2 == 1) {
      count = count + 1;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define   vpll   vector<pll >
#define   all(x) x.begin(),x.end()
#define   present(c,x)    ((c).find(x) != (c).end())
#define   dbg(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){
  std::cerr << name << " = " << arg1 << "\n";
}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    std::cerr.write(names, comma - names) << " = " << arg1;
    ZZ(comma, args...);
}
#define   sz(a)  a.size()
#define   vll vector<int>
#define   pll pair<int,int>
#define   ff  first
#define   ss  second
#define   br  cout<<"\n";
#define   ld  long double
#define   int  long long int
const int  INF = 1e18+7;
const int  MAX = 3001;
const int  MOD = 998244353;


int n , s ;
int A[MAX] , dp[MAX][MAX] ;
int sets ( int r , int sum ){
	if ( !sum ) return ( n - r + 1 ) ;
	if ( r == n  ) return 0 ;
	if ( dp[r][sum] != - 1) return dp[r][sum] ;
	int ans = 0 ;
	ans = sets ( r + 1 , sum ) ;
	if ( sum >= A[r] ){
		ans += sets( r + 1 , sum - A[r] ) ;
		ans %= MOD ;
	}		
	return dp[r][sum] = ans ;
}
void solve(){
    memset ( dp , -1 , sizeof dp ) ;
    cin >> n >> s ;
    for ( int i = 0 ; i < n   ; i++ )
    	cin >> A[i] ;
    int ans = 0 ;
    for ( int r = 0 ; r < n ; r++ )
    	ans += sets ( r , s ) , ans %= MOD ;
    cout << ans ;
}
int32_t main(){
    int t;
    t=1;
    cin.sync_with_stdio(0), cin.tie(0);
    //cin>>t;
    while(t--){
        solve();
        br;
    }
    return 0;
}
 
 
 
 
 
 

Measured memory_bytes: 70912
/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.

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

int mod = 1000000007;
ll dp[100005];
const ll INF = 1e18;

ll gcd(long long a,long long b){

  if(b == 0)
    return a;
  else return gcd(b,a%b);
}


bool sortbyval(const pair<string, int> &a,
               const pair<string, int> &b)
{
    return (a.second < b.second);
}


int main(){

 long long a,r;
 long double b;

 cin>>a>>b;

  b *= 100;
  b = round(b);
  r = a*b/100;

 cout<<r<<endl;

return 0;
}


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

for i in range(n): #Bi
    lst[i] -= i+1

lst.sort()
if n%2 == 0:
    k = n//2
    b = (lst[k] + lst[k-1])/2
else:
    k = (n-1)//2
    b = lst[k]

ans = 0
for i in range(n):
    ans += abs(lst[i] - b)

print(int(ans))

Measured memory_bytes: 26128
#include<stdio.h>



int main(){
	
	int a,b;
	int sum;
	
	scanf("%d %d",&a,&b);
	sum=a*b*a;
	
	if(sum%2!=0){
		
		printf("Yes\n");
	}
	
	else{
		
		printf("No\n");
	}
		
}

Measured memory_bytes: 128
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        List<Integer> hps = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            int hp = scanner.nextInt();
            hps.add(hp);
        }
        hps.sort(Comparator.reverseOrder());
        long result = 0;
        for (int i = k; i < n; i++) {
            result += hps.get(i);
        }
        System.out.println(result);
    }
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 100000;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int w, h;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> w >> h;
    while (w != 0) {
        int dp[h + 1][w + 1][2][2] = {};
        dp[1][0][0][0] = 1;
        dp[0][1][0][1] = 1;
        rep(i, h)rep(j, w){
            (dp[i + 1][j][0][0] += dp[i][j][0][0]) %= mod;
            (dp[i][j + 1][1][1] += dp[i][j][0][0]) %= mod;
            (dp[i + 1][j][1][0] += dp[i][j][0][1]) %= mod;
            (dp[i][j + 1][0][1] += dp[i][j][0][1]) %= mod;
            (dp[i + 1][j][0][0] += dp[i][j][1][0]) %= mod;
            (dp[i][j + 1][0][1] += dp[i][j][1][1]) %= mod;
        }
        int ans = 0;
        rep(i, 2)rep(j, 2) (ans += dp[h - 1][w - 1][i][j]) %= mod;
        cout << ans << endl;
        cin >> w >> h;
    }
}

Measured memory_bytes: 3372
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
cs = list(map(int, input().split()))

f = dict() #k?????§??????????????????????°??????????????????¨?????°
f[0] = 0
for k in range(1,n+1):
    f[k] = float('inf')
    for c in cs:
        if k - c < 0:
            continue
        f[k] = min(f[k], f[k - c] + 1)

print(f[n])

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

int main(){
    // a + b = x
    // 2a + 4b = y
    // -2b = 2x - y
    //  b = y/2 - x
    // a = 2x - y/2
    int x, y;
    cin >> x >> y;
    if (y % 2 == 0){
        if (x <= y/2 && y/2 <= 2*x){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3632
import java.util.*

fun main(args:Array<String>){
    val (n,k) = readLine()!!.split(" ").map{it.toInt()}
    val v = readLine()!!.split(" ").map{it.toInt()}
    var ans = 0
    for(i in 0 .. n){
        for(j in 0 .. n){
            if(i + j > n || i + j > k) break
            val a = ArrayList<Int>()
            for(l in 0 until i) a.add(v[l])
            for(l in 0 until j) a.add(v[n - 1 - l])
            a.sort()
            var sum = a.sum()
            for(l in 0 until Math.min(k - (i + j), i + j)){
                if(a[l] < 0) sum -= a[l]
            }
            ans = Math.max(ans, sum)
        }
    }
    println(ans)
}


Measured memory_bytes: 39804
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>

using namespace std;
using ll = long long;
using ld = long double;
const ll mod =  1000000007;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll power(ll base, ll exponent, ll module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ ll root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2, mod);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };


const int inf = 1e9+7;

signed main() {
  ios::sync_with_stdio(false);
  ll n, m;
  cin >> n >> m;
  vector<int> s(n);
  vector<int> t(m);
  REP(i, n) cin >> s[i];
  REP(i, m) cin >> t[i];
  vector<vector<ll>> dp = vector<vector<ll>>(n+1, vector<ll>(m+1, 0));
  vector<vector<ll>> cum = vector<vector<ll>>(n+1, vector<ll>(m+1, 0));
  REP(i, n) {
    REP(j, m) {
      if(s[i] == t[j]) {
        dp[i+1][j+1] = (cum[i][j] + 1) % mod;
      }
      else {
        dp[i+1][j+1] = 0;
      }
      cum[i+1][j+1] = (cum[i+1][j] + cum[i][j+1] - cum[i][j] + dp[i+1][j+1] + mod) % mod;
    }
  }
  cout << (cum[n][m] + 1) % mod << endl;

  return 0;
}


Measured memory_bytes: 62976
import sys
X, K, D = map(int, input().split())
X = abs(X)
if X // D >= K:
    print(X - K*D)
    sys.exit()
K = K - (X // D)
A = X - X//D*D
if K % 2 == 0:
    print(A)
else:
    print(abs(A - D))

Measured memory_bytes: 9148
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String N = sc.next();
        String[] tile = N.split("");
        
        String[] a = new String[tile.length];
        String[] b = new String[tile.length];
        
        int cnt1 = 0;
        int cnt2 = 0;
        

        for(int i = 0;i<tile.length;i++) {
        	if(i%2 == 0) {
        		if(tile[i].equals("1")) {
        			cnt1++;
        		}
        	}else {
        		if(tile[i].equals("0")) {
        			cnt1++;
        		}
        	}
        }
        
        for(int i = 0;i<tile.length;i++) {
        	if(i%2 == 0) {
        		if(tile[i].equals("0")) {
        			cnt2++;
        		}
        	}else {
        		if(tile[i].equals("1")) {
        			cnt2++;
        		}
        	}
        }
        System.out.println(Math.min(cnt1, cnt2));
       
    }
}

Measured memory_bytes: 32620
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <limits.h>
#include <math.h>

int main(int argc, char *argv[])
{
    char s[100001];
    int len;
    int i;
    int ans;

    scanf("%s", s);

    len = strlen(s);

    ans = 0;
    for (i = 0; i < len; i++) {
        if (s[i] == '0' + (i % 2)) {
            ans++;
        }
    }

    if (ans > len / 2) {
        ans = len - ans;
    }

    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>

#define MULT(x,y) ((x*y)%1000000007L)
#define llint long long int

int main(void){
  llint n, a, b;
  std::cin >> n >> a >> b;
  std::vector<llint> x;
  for(int i=0; i<n; i++){
    int temp;
    std::cin >> temp;
    x.push_back(temp);
  }

  llint ret = 0;
  for(int i=1; i<n; i++){
    llint temp1 = (x[i]-x[i-1])*a;
    llint temp2 = b;
    ret += temp2<temp1?temp2:temp1;
  }
  std::cout << ret << std::endl;




  return 0;
}


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

#define MODADD(x, y) ((x) = ((x) + (y)) % MOD)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

string K;
int D, n;
ll dp0[2][100], dp1[2][100];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> K >> D;
    n = K.size();
    dp0[0][0] = 1;
    for (int i = 0; i < n; i++) {
        memset(dp1, 0, sizeof dp1);
        for (int m = 0; m < D; m++) {
            for (int d = 0; d <= 9; d++)
                MODADD(dp1[1][(m + d) % D], dp0[1][m]);
            for (int d = 0; d < K[i] - '0'; d++)
                MODADD(dp1[1][(m + d) % D], dp0[0][m]);
            MODADD(dp1[0][(m + K[i] - '0') % D], dp0[0][m]);
        }
        swap(dp0, dp1);
    }
    cout << (dp0[0][0] + dp0[1][0] + MOD - 1) % MOD << endl;
}


Measured memory_bytes: 384
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
}
int main()
{
    vok();
    ll n,k;
    IN n>>k;
    vll a(n);
    bitset<50> b[n];
    loop(i,0,n)
    {
        IN a[i];
        bitset<50> temp(a[i]);
        b[i]=temp;
    }
    bitset<50> ans(0);
    rloop(i,49,0)
    {
        int countt=0;
        loop(j,0,n)
        {
            if(b[j][i])
            {
                countt++;
            }
            //cout<<"";
        }
        //cout<<"";
        ans[i]=1;
        if((countt*2)<n && ans.to_ullong()<=k)
        {
            //Do Nothing
        }
        else
        {
            ans[i]=0;
        }
    }
    ll fans=0LL;
    //cout<<"";
    ll X=ans.to_ullong();
    loop(i,0,n)
    {
        //cout<<"";
        fans+=(X^a[i]);
    }
    OUT fans<<endl
    return 0;
}

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

int main()
{
    int k, x;
    cin >> k >> x;
    if (500 * k >= x)
        cout << "Yes" << endl;
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3588
n,s = map(int,input().split())

al = list(map(int,input().split()))

ans = 0
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for i in range(n):
    for k in range(s, -1, -1):
        if k - al[i] < 0:
            dp[k] = 2 * dp[k]
        else:
            dp[k] = 2 * dp[k] + dp[k-al[i]]
        dp[k] %= 998244353

print(dp[-1])



Measured memory_bytes: 68700
# encoding: utf-8
n, t = map(int, input().split())
min_num = -1
min_c = -1
for i in range(n):
	ctmp, ttmp = map(int, input().split())
	if ttmp <= t:
		if min_c == -1 or min_c > ctmp:
			min_c = ctmp
			min_num = i + 1
if min_num != -1:
  	print(min_c)
else:
	print('TLE')

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

int main (){
	int n, a, x, b=0;
	
	cin >> n >> a;
	
	for (int i=0; i<n; i++){
		cin >> x;
		if (x >= a) b++;
	}
	
	cout << b << endl;
	
	return 0;
}

Measured memory_bytes: 256
/*
 * cpp_filepath
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }


void solve() {
  int x, y;
  cin >> x >> y;
  cout << x + (y/2) << endl;
}


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

int main()
{
  long long N;
  cin >> N;

  if(N % 2 == 1)
  {
    cout << 0 << endl;
    return 0;
  }
  else
  {
    vector<long long> q(N);
    for (long long i = 0; i < N; i++)
    {
      cin >> q[i];
    }

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

    cout << q[N / 2] - q[N / 2 - 1] << endl;
  }

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Y cout << "YES\n"
#define N cout << "NO\n"
#define REP(i, a, b) for (int i = a; i <= b; i++)
#define R(i, n) for (int i = 0; i < n; i++)
#define RE(i, a, b) for (int i = a; i >= b; i--)
int prime[1000010], p[100001][2];
int fun()
{
	int k = 0;
	for (int i = 2; i < 1000001; i++)
	{
		if (prime[i] == 0)
		{
			p[k][0] = i;
			k++;
			for (int j = i + i; j < 1000001; j += i)
			{
				prime[j] = 1;
			}
		}
	}
	return k;
}

int main()
{
		int x , n , a[1000] = {0} ;
		cin >> x >> n ;
		for(int i = 0 ; i < n ; i ++)
		{
			int d ;
			cin >> d ;
			a[d] = 1 ;
		}
		int min = 1000 , max ;
		for(int i = x ; i >= 0 ; i--)
		{
			if(a[i] == 0)
			{
				min = i ;
				break ;
			}
		}
		for(int i = x ; i < 102 ; i++)
		{
			if(a[i] == 0)
			{
				max = i ;
				break ;
			}
		}
		if( (max-x) >= (x-min) )
		{
			cout << min << endl ;
		}
		else
		{
			cout << max << endl ;
		}
}


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



ll s(ll x) {
    ll re = 0;
    while (x > 0) {
        re += x % 10;
        x /= 10;
    }
    RT re;
}

bool cmp(ll x, ll y) {
    RT x*s(y) <= y * s(x);
}

void solve(int K) {
    for (int n = 1; n <= 1000001 &&K > 0; ++n) {
        bool ok = true;
        for (int m = n + 1; m <= 10000001; ++m) {
            if (!cmp(n, m)) {
                ok = false;
                break;
            }
        }
        if (ok) {
            K--;
            cout << n << ',' << endl;
        }
    }

}

const int MAGIC[36] = {
1,
2,
3,
4,
5,
6,
7,
8,
9,
19,
29,
39,
49,
59,
69,
79,
89,
99,
199,
299,
399,
499,
599,
699,
799,
899,
999,
1099,
1199,
1299,
1399,
1499,
1599,
1699,
1799,
1899
};

void solve2(int K) {
    ll d = 1, cur = 0;
    rep(i, K) {
        ll x = cur + d, y = cur + d * 10;
        if (cmp(x, y)) {
            cur = x;
        } else {
            cur = y;
            d *= 10;
        }
        cout << cur << endl;
    }
}

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

    solve2(K);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<stdio.h>
using namespace std;
long long int a[100000];
int main()
{
    long long int n,i,x,y,t,s,d;
   scanf("%lld",&n);
   s=0;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&d);
        a[d]++;
        s+=d;
    }
   scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&x,&y);
       a[y]+=a[x];
       s+=(y-x)*a[x];
       a[x]=0;
        printf("%lld\n",s);
    }
    return 0;
}
 

Measured memory_bytes: 4500
//abc106_d.cpp
//Sat Aug 18 19:56:08 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,m,d;
	cin >> n >> m >> d;

	int train[n+1][n+1],imos[n+1][n+1];
	for (int i=0;i<n+1;i++){
		for (int j=0;j<n+1;j++){
			train[i][j] = 0;
			imos[i][j] = 0;
		}
	}

	for (int i=0;i<m;i++){
		int tempx, tempy;
		cin >> tempx >> tempy;
		train[tempx][tempy]++;
	}

	for (int i=1;i<n+1;i++){
		for (int j=1;j<n+1;j++){
			imos[i][j] = imos[i][j-1]+train[i][j];
		}
	}

	for (int i=1;i<n+1;i++){
		for (int j=1;j<n+1;j++){
			imos[j][i] = imos[j-1][i]+imos[j][i];
		}
	}

//	for (int i=0;i<n+1;i++){
//		for (int j=0;j<n+1;j++){
//			cout << imos[i][j] << " ";
//		}
//		printf("\n");
//	}


	for (int i=0;i<d;i++){
		int tempp,tempq;
		cin >> tempp >> tempq;
		cout << imos[tempq][tempq]-imos[tempp-1][tempq]-imos[tempq][tempp-1]+imos[tempp-1][tempp-1] << endl;
	}
}

Measured memory_bytes: 2944
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	void run() {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			double[] x,y;
			x = new double[4];
			y = new double[4];
			for(int i=0;i<4;i++) {
				x[i] = sc.nextDouble();
				y[i] = sc.nextDouble();
			}
			
			if(isNotTyouhuku(x, y)) System.out.println("NO");
			else System.out.println("YES");
		}
	}
	
	boolean isNotTyouhuku(double[]x , double[] y) {
		return x[1] < x[2] || x[0] > x[3] || y[1] < y[2] || y[0] > y[3]; 
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000
n = int(input())
alst = list(map(int, input().split()))
if n == 2:
    if sum(alst) % 2 != 0:
        print(-1)
    elif alst[0] < alst[1]:
        print(-1)
    else:
        print((alst[0] - alst[1]) // 2)
    exit()

if alst.count(1) == n:
    if n % 2 == 0:
        print(0)
    else:
        print(-1)
    exit()
    
if alst.count(1) == n - 1:
    print(-1)
    exit()

xor = 0
for num in alst[2:]:
    xor ^= num
total = alst[0] + alst[1]
if xor > total:
    print(-1)
    exit()

diff = total - xor
if diff % 2 == 1:
    print(-1)
    exit()

if alst[0] == 1:
    if xor == alst[0] ^ alst[1]:
        print(0)
    else:
        print(-1)
    exit()
    
diff //= 2
total_bin = format(total, "b")
diff_bin = format(diff,"b")
xor_bin = format(xor,"b")
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            ans += 2 ** (j - 1)
            continue
for j in range(i, 0, -1):
    if j <= len(diff_bin):
        if diff_bin[-j] == "1":
            continue
    if j <= len(xor_bin):
        if xor_bin[-j] == "0":
            continue    
    if ans + 2 ** (j - 1) < alst[0]:
        ans += 2 ** (j - 1)
if (ans ^ (total - ans)) != xor:
    print(-1)
elif ans == 0 or ans >= alst[0]:
    print(-1)
else:
    print(alst[0] - ans)

Measured memory_bytes: 62308
S = list(input())
T = list(input())

ans = "z" * 100
for i in range(len(S) - len(T) +1)[::-1]:
  ok = True

  for j in range(len(T)):
    if S[i+j] != "?" and S[i+j] != T[j]:
      ok = False
  if ok:
    s = S[:i] + T + S[i+len(T):]
    s = "".join(s)
    ans = min(ans, s.replace("?", "a"))
    break
if ans == "z" * 100:
  print("UNRESTORABLE")
else:
  print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int num[N], r[N], n, m;

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	r[1] = 1;
	for (int i = 1; i <= n; i++) num[i] = 1;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		if (r[a]) r[b] = 1;
		num[a] --;
		num[b] ++;
		if (!num[a]) r[a] = 0;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) ans += r[i];
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <queue>

using namespace std;

class range {
private:
  struct Iterator {
    int val;
    int operator*() {return val;}
    bool operator!=(Iterator &itr) {return val < itr.val;}
    void operator++() {++val;}
  };
  Iterator i, n;
public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  Iterator &begin() {return i;}
  Iterator &end() {return n;}
};

template<class T> T at(vector<T> v, int i) {return v[(i % (int)v.size() + v.size()) % v.size()];}

typedef int Weight;
struct Edge {
  int from, to;
  Weight weight;
  Edge(int from, int to, Weight weight) :
    from(from), to(to), weight(weight) {}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

Matrix adjacency(const Graph &graph) {
  int n = graph.size();
  Matrix distance(n, Array(n, 1e9));
  for (const Edges &edges : graph) for (const Edge &edge : edges) {
    distance[edge.from][edge.to] = edge.weight;
  }
  return distance;
}

void debug(const Graph &g) {
  for (const Edges &es : g) for (const Edge &e : es) {
    cerr << e.from << " " << e.to << " " << e.weight << endl;
  }
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> c(n), r(n);
  for (int i : range(n)) cin >> c[i] >> r[i];
  Graph graph(n);
  for (int i : range(k)) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    graph[a].emplace_back(a, b, 1);
    graph[b].emplace_back(b, a, 1);
  }
  Matrix matrix(n, Array(n, -1));
  for (int i : range(n)) {
    queue<pair<int, int>> que;
    que.push(make_pair(0, i));
    while (!que.empty()) {
      auto now = que.front();
      que.pop();
      if (matrix[i][now.second] != -1) continue;
      matrix[i][now.second] = now.first;
      for (const auto &edge : graph[now.second]) {
        que.push(make_pair(now.first + 1, edge.to));
      }
    }
  }
  vector<bool> used(n, false);
  vector<int> dis(n, 1e9);
  dis[0] = 0;
  while (true) {
    int v = -1;
    for (int i : range(n)) if (!used[i] && (v == -1 || dis[i] < dis[v])) v = i;
    if (v == -1) break;
    used[v] = true;
    for (int i : range(n)) if (matrix[v][i] <= r[v]) dis[i] = min(dis[i], dis[v] + c[v]);
  }
  cout << dis[n - 1] << endl;
}

Measured memory_bytes: 99468
s=input()
for i in s:
    if i == 'B'and s.index(i) == 0:
        s=s[1:]
    elif   i == 'B'and s.index(i) !=0 :
        s=s[:s.index(i)-1]+s[s.index(i)+1:]
    
print(s)


Measured memory_bytes: 3060
import bisect
n,m,v,p=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
ok=n#idx
ng=-1
def solve(x):
    if bisect.bisect_right(l,l[x])>=n-p+1:
        return 1
    lx=l[x]+m
    lxi=bisect.bisect_right(l,lx)-1
    if lxi<=n-p-1:
        return 0
    #n-p-1<lxi
    f=0
    for i in range(n):
        if i<=x or i>n-p:
            f+=m
            continue         
        else:
            f+=min(lx-l[i],m)
    if f>=v*m:
        return 2
    else:
        return 0
#for i in range(n):
    #print(solve(i))
while ok-ng>1:
    x=(ok+ng)//2
    if solve(x):
        ok=x
    else:
        ng=x
    #print(x)
print(n-ok)

Measured memory_bytes: 62576
x = int(input())
y = []
count1 = 0
flag = 0
for i in range(0, 130):
  y.append(i*i*i*i*i)
for i in y:
  if i == x:
    print("0 -" + str(count1))
    flag = 1
    break;
  count1 += 1
count1 = 0
for i in y:
  if flag == 1:
    break;
  count2 = 0
  for j in y[:count1]:
    y2 = i + j
    y3 = i - j
    if y2 == x:
      print(str(count1) + " -" + str(count2))
      flag = 1
      break;
    if y3 == x:
      print(str(count1) + " " + str(count2))
      flag = 1
      break;
    count2 +=1
  count1 += 1

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

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

int main() {
	int H, W, N; cin >> H >> W >> N;
	map<int, map<int, int>>mp; long long cnt[10] = {};
	cnt[0] = (long long)(H - 2) * (W - 2);
	for (int i = 0, a, b; i < N; i++) {
		cin >> a >> b;
		for (int j = 0; j < 9; j++)mp[a + dy[j]][b + dx[j]]++;
	}
	for (auto&& row : mp) {
		int y = row.first;
		if (y < 2 || H - 1 < y)continue;
		for (auto&& col : row.second) {
			int x = col.first;
			if (x < 2 || W - 1 < x)continue;
			cnt[col.second]++; cnt[0]--;
		}
	}
	for (int i = 0; i < 10; i++)cout << cnt[i] << endl;

	return 0;
}

Measured memory_bytes: 70528
n=int(input())
m=list(map(int,input().split()))
k=10**6+1
p=[0]*k
m.sort()
for i in range(1,n):
    if m[i]==m[i-1]:
        p[m[i]]=1
res=0
for i in range(n):
    if p[m[i]]==0:
        res+=1
    
    if i!=n-1 and m[i]!=m[i+1]:
        for j in range(m[i]*2,k,m[i]):
            p[j]=1
print(res)
        
    
     
    

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

long n, m;
vector<int> G[100000];
int col[100000];

bool isb(int from, int c) {
  if (col[from] != 0) {
    if (col[from] == c) return true;
    return false;
  }
  col[from] = c;
  bool ret = true;
  for (int to : G[from]) {
    if (!isb(to, -c)) {
      ret = false;
    }
  }
  return ret;
}

int sub(int from) {
  return isb(from, 1);
}

int main() {
  cin >> n >> m;
  for (int j = 0; j < m; ++j) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  long cnt[2] = {};
  long iso = 0;
  for (int i = 0; i < n; ++i) {
    if (G[i].empty()) {
      ++iso;
      continue;
    }
    if (col[i] != 0) continue;
    int ret = sub(i);
    ++cnt[ret];
  }
  
  long sum = cnt[0] + cnt[1];
  cout << sum * sum + cnt[1] * cnt[1]
        + n * n - (n - iso) * (n - iso) << endl;
}


Measured memory_bytes: 9984
package main

import (
	"fmt"
	"math"
)

func intMax(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

func intMin(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func main() {
	var S string
	fmt.Scan(&S)

	N := len(S)
	ans := N
	for i := 0; i < N-1; i++ {
		if S[i] != S[i+1] {
			ans = intMin(ans, intMax(i+1, N-i-1))
		}
	}
	fmt.Println(ans)
}


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

int main(){
    using namespace std;
    unsigned long X, Y;
    cin >> X >> Y;
    if((X + Y) % 3)return 0 & puts("0");
    {
        unsigned long k{(X + Y) / 3};
        if(X < k || Y < k)return 0 & puts("0");
        X -= k;
        Y -= k;
    }
    unsigned long N{X + Y}, d{1}, n{1};
    constexpr unsigned long MOD = 1000000007;
    for(unsigned long i = 0, j = N; i < X;){
        (d *= j--) %= MOD;
        (n *= ++i) %= MOD;
    }
    unsigned long a{MOD - 2};
    while(a){
        if(a & 1)(d *= n) %= MOD;
        (n *= n) %= MOD;
        a >>= 1;
    }
    cout << d << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
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;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int main(){
    int n, K;
    scanf("%d%d", &n, &K);
    lint ans = K;
    rep(i, n-1) ans *= K-1;
    printf("%lld\n", ans);
}

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

// 条件を満たすような分割が出来る=>2部グラフになっている
// もし2部グラフでないなら、分割不可。2部グラフならグラフの直径+1が最大分割数となる
int main() {
    int n;
    cin >> n;
    vector<vector<int>> s(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
          #include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;  char c;
          
            cin >> c;
            if (c == '0') s[i][j] = INF;
            else s[i][j] = 1;
        }
    }

    for (int k = 0; k < s.size(); k++) {
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < s.size(); j++) {
                if (s[i][k] == INF || s[k][j] == INF)
                    continue;
                s[i][j] = min(s[i][j], s[i][k] + s[k][j]);
            }
        }
    }

    set<vector<int>> sv;
    int diam = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j)
                diam = max(s[i][j], diam);
            s[i][j] = s[i][j] % 2;
        }
        sv.insert(s[i]);
    }

    int k;
    if (sv.size() != 2) k = -1;
    else k = diam + 1;
    cout << k << endl;
    return 0;
}


Measured memory_bytes: 640
x, n = map(int, input().split())

if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))
    p.sort()
    # 左
    left = p
    for i in range(x, -100, -1):
        if i not in p:
            left = i
            break
    # 右
    right = p
    for i in range(x, 110):
        if i not in p:
            right = i
            break

    leftabs = abs(x - left)
    rightabs = abs(right - x)

    if leftabs == rightabs:
        print(left)
    elif leftabs > rightabs:
        print(right)
    else:
        print(left)


Measured memory_bytes: 9204