akhauriyash/Code-Regression huggingface dataset:
#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>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 1
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif


//改造
typedef long long int ll;
using namespace std;


//ここから編集する
ll mod = 1000000007;


int main() {
    int dir[4] = {-1,-1,-1,-1};
    string s;
    cin >> s;
    REP(i,0,s.size()){
        if(s[i] == 'N'){
            dir[0] = 1;
        }else if(s[i] == 'S'){
            dir[1] = 1;
        }else if(s[i] == 'W'){
            dir[2] = 1;
        }else if(s[i] == 'E'){
            dir[3] = 1;
        }
    }
    if(dir[0] * dir[1] > 0 && dir[2] * dir[3] > 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
    int n;
    cin>>n;
    vector<ll> a(n),s(n+1),t(n+1);
    ll sum=0;
    rep(i,0,n){
        cin>>a[i];
        sum+=a[i];
    }

    rep(i,0,n){s[i+1]=s[i]+a[i];}
    for(int i=n-1;i>=0;i--){t[i]=t[i+1]+a[i];}

    ll ans = sum;
    rep(i,0,n+1){
        ans=min(ans,abs(s[i]-t[i]));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8004
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n//i)

    return divisors


divisors = make_divisors(int(input()))
sub_list = []
for i in range(1, len(divisors), 2):
    sub_list.append(divisors[i] - divisors[i-1])

min_index = sub_list.index(min(sub_list))
print(divisors[min_index * 2] + divisors[(min_index+1) * 2 - 1] - 2)

Measured memory_bytes: 3296
import numpy as np
def repaint(h,w,s):
    for i in range(1,h+1):
        for p in range(1,w+1):
            if s[i][p] == '#':
                if (s[i-1][p] != '#') and (s[i][p-1] != '#') and (s[i+1][p] != '#') and (s[i][p+1] != '#'):
                    return 'No'
    return 'Yes'
H, W = map(int, input().split())
S = np.array([['0']*(W+2)] + [list('0' + input() + '0') for i in range(H)] +[['0']*(W+2)])
print(repaint(H,W,S))

Measured memory_bytes: 12516
#include <bits/stdc++.h>
#ifdef dbg
#include "./printer.hpp"
#else
#define dump(x) void(0)
#endif

using namespace std;

#define MOD 1000000007
#define INF 100000000000000000
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ALL(x) ((x).begin(), (x).end())
#define sync(); ios_base::sync_with_stdio(0);

inline long  toInt(string s) {long  v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


ll ex_euclid(ll a, ll b, ll &x, ll &y){
  ll xx,yy;
  x = yy = 1;
  xx = y = 0;
  while(b){
    ll m = a / b;
    ll t = xx;
    xx = x - m * xx;
    x = t;
    t = yy;
    yy = y - m * yy;
    y = t;
    t = b;
    b = a % b;
    a = t;
  }

  return a;
}

ll inverse(ll a){
  pair<ll,ll> p {MOD,a};
  pair<pair<ll,ll>,pair<ll,ll>> k {{1,0}, {0,1}};
  while(1){
    if(p.second == 1){
      return k.second.second;
    }
    ll temp = p.second;
    pair<ll,ll> tempp = k.second;
    k.second.first = k.first.first - (p.first / p.second) * k.second.first;
    k.second.second = k.first.second - (p.first / p.second) * k.second.second;
    p.second = p.first % p.second;
    p.first = temp;
    k.first = tempp;
  }
}

ll pw(ll a, ll b){
  ll ans = 1;
  ll mul = a;
  
  while(b){
    if((b & 1ll) == 1){
      ans *= mul;
      ans %= MOD;
    }
    mul = mul * mul;
    mul %= MOD;
    b = (b >> 1);
  }
  return ans;
}



int main(){
  sync();
  ll n;
  cin >> n;
  ll a;
  cin >> a;
  for(ll i = 1; i < n; i++){
    ll b;
    cin >> b;
    a = a * b / __gcd(a,b);
  }

  cout << a << endl;
}

Measured memory_bytes: 3208
n, y = gets.strip.split.map(&:to_i)
_i, _j, _k = -1, -1, -1

(0..n).each do |i|
    (0..n-i).each do |j|
       if i * 10000 + j * 5000 + (n - i - j) * 1000 == y
           _i, _j, _k = i, j, n - i - j
       end
    end
end

puts "#{_i} #{_j} #{_k}"

Measured memory_bytes: 3836
#include <iostream>
#include <array>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <climits>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using namespace std;

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res /= a;
	}
};

struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
} comb(2000005);

mint g(int r, int c) {
	return comb(r + c + 2, r + 1) - 1;
}

bool comp(int i, int j) {
	return i > j;
}

int main()
{
	int n;
	cin >> n;
	long long ll = 0;
	for (int i = 1; i <= n; i++)
	{
		if (i % 3 != 0 && i % 5 != 0)
		{
			ll += (long long)i;
		}
	}
	cout << ll;
}


Measured memory_bytes: 34216
# coding: utf-8
import sys
import numpy as np


input = sys.stdin.readline
N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=int)

for _ in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[:-w] + v, dp[w:])

print(dp[W])

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

int main(){
    string s;
    cin>>s;
    int a=0;
    if(s=="SUN"){
        cout<<7<<endl;
    }
    if(s=="MON"){
        cout<<6<<endl;
    }
    if(s=="TUE"){
        cout<<5<<endl;
    }
    if(s=="WED"){
        cout<<4<<endl;
    }
    if(s=="THU"){
        cout<<3<<endl;
    }
    if(s=="FRI"){
        cout<<2<<endl;
    }
    if(s=="SAT"){
        cout<<1<<endl;
    }
    return 0;
}

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}


#define incID(i, l, r) for(int i = (l); i < (r); i++)
#define inc(i, n) incID(i, 0, n)
template<typename T> bool setmin(T &a, T b) { if(a <= b) { return false; } else { a = b; return true; } }
template<typename T> bool setmax(T &a, T b) { if(b <= a) { return false; } else { a = b; return true; } }


// ---- ----

int n, k;
bool ans = true;
vector<int> vec[100000];
bool has[100000];
int mi[100000];
int ma[100000];

void prod(int x, int y) {
	if(has[y]) {
		if(has[x] && (mi[x] - mi[y]) % 2 == 0) { ans = false; }
		setmax(mi[x], mi[y] - 1);
		setmin(ma[x], ma[y] + 1);
		has[x] = true;
		if(mi[x] > ma[x]) { ans = false; }
		if(! ans) {
			printf("No\n");
			exit(0);
		}
	}
}

bool dfs(int node, int pre) {
	if(pre != -1) { prod(node, pre); }
	for(auto && i : vec[node]) {
		if(i != pre) {
			dfs(i, node);
			prod(node, i);
		}
	}
}

int main() {
	// scanf("%d", &n);
	reader(&n);
	inc(i, n - 1) {
		int a, b;
		//scanf("%d%d", &a, &b);
		reader(&a, &b);
		a--; b--;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	fill(mi, mi + n, -1000000);
	fill(ma, ma + n,  2000000);
	// scanf("%d", &k);
	reader(&k);
	inc(j, k) {
		int v, p;
		// scanf("%d%d", &v, &p);
		reader(&v, &p);
		v--;
		mi[v] = p;
		ma[v] = p;
		has[v] = true;
	}
	
	dfs(0, -1);
	dfs(0, -1);
	
	if(ans) {
		printf("Yes\n");
		inc(i, n) {
			// printf("%d\n", mi[i]);
			writerLn(mi[i]);
		}
	}
	
	return 0;
}


Measured memory_bytes: 11904
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <set>
using namespace std;
#define INF 1010101010
#define MOD 1000000007
#define LL long long
 
int main() {
    string s;
    cin >> s;
    int score = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i % 2 == 0 && s[i] == 'p') score--;
        if (i % 2 == 1 && s[i] == 'g') score++;
    }
    cout << score << endl;
}

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

using namespace std;

int main()
{
    vector<char> s;
    char c;
    scanf("%c", &c);
    while (c >= 'a' && c <= 'z') {
        s.push_back(c);
        scanf("%c", &c);
    }
    int k;
    cin >> k;
    vector<int> a(s.size());
    for (int i = 0; i < s.size(); i++)
        a[i] = ('z' - s[i] + 1) % 26;
    for (int i = 0; i < s.size(); i++) {
        if (a[i] <= k) {
            k -= a[i];
            s[i] = 'a';
        }
    }
    s.back() += k % 26;
    for (int i = 0; i < s.size(); i++)
        cout << s[i];
    return 0;
}

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


#define ONSPEED ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define f(i,x,n) for(i=x;i<n;i++)
#define rf(i,x,n) for(i=n;i>x;i--)
#define ll long long
#define GCD(a,b) __gcd(a,b)
#define ff first
#define ss second
#define adios return 0;

/*
tacet aquilae
*/

int main()
{
    ONSPEED;
    ll t,n,k,a,b,c,d,s=0,i,j,flag;
    string x,y;
    cin>>n;
    std::vector<ll> v1(n),v2;
    f(i,0,n) 
    {
    	cin>>v1[i];
    }
    v2=v1;
    sort(v2.begin(), v2.end());
    f(i,0,n)
    {
    	if(v1[i]!=v2[i])s++;
    }
    if(s<=2) cout<<"YES";
    else cout<<"NO";




    adios;
}
	


Measured memory_bytes: 3560
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
b = Hash.new(0)
a.each do |num|
  b[num] += 1
end
count = 0
b.each do |k,v|
  if k > v
    count += v
  elsif k < v
    count += v-k
  end
end
puts count

Measured memory_bytes: 17412
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vint;
typedef vector<uint> vuint;
typedef vector<ull> vull;
typedef vector<ll> vll;

#define init(type,var) type var;cin>>var;
#define vinit(type,var,n) vector<type> var((uint)n);loop(i,0,n)cin>>var[i];
#define linit(type,var,n) list<type> var;loop(i,0,n){type _v;cin>>_v;var.push_back(_v);}
#define range(container) container.begin(),container.end()
#define loop(i,first,end) for(ull i=(first);i<(end);i++)
#define outl(out) cout<<(out)<<endl;

const ull INF = (ull)(-1LL);

typedef int aint;

typedef vector<aint> vaint;
typedef list<aint> laint;

int main(void){
	init(aint, n);
	vinit(aint, p, n);
	vinit(aint, q, n);

	vaint v(n);
	for (aint i = 0; i < n; i++)v[i] = i + 1;

	aint a = 0, b = 0;
	aint i = 0;
	do{
		if (p == v)a = i;
		if (q == v)b = i;
		i++;
	} while (next_permutation(v.begin(), v.end()));

	outl(abs(a - b));

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define vc vector<int>
#define um unordered_map<int,int>
#define ll long long 
#define rep(i,a,b) for(__typeof(a) i=a; i<b; i++)
#define si(a) a.size()
#define all(a) a.begin(),a.end()
#define ss(a) a.second
#define ff(a) a.first
#define M 1000000
#define pb push_back
#define repit(i,a) for(auto i=a.begin(); i!=a.end(); i++)
#define take(arr,n) for(int i=0;i<n;i++)cin>>arr[i]
#define out(arr,n) for(int i=0;i<n;i++)cout<<arr[i]<<' '
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define reprev(i,b,a) for(__typeof(b) i=b; i>=a; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define doublearray vector<vector<int>>
#define mod 998244353 
using namespace std;
ll max(ll a, ll b){ return a>b?a:b; }
ll min(ll a, ll b){ return a<b?a:b; }
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}
int binaryS(ll x, ll sb[], int m){
    int l = 0, r=m;
    int mid = (l+r)/2;
    while(l<r){
        mid = (l+r)/2;
        if(sb[mid]<x) l= mid+1;
        else if(sb[mid]>x) r = mid-1;
        else return mid;
    }
    return l;
}
int main(){
    fastio;
    char c; cin>>c;
    if(c<='Z') cout<<'A'<<endl;
    else cout<<'a'<<endl;
    return 0;
}





Measured memory_bytes: 3660
def main():
    high, width = map(int, input().split())
    ans = high * width

    for i in range(1, high):
        a = i * width

        b1 = (high - i) * (width // 2)
        c1 = high * width - a - b1

        b2 = ((high - i) // 2) * width
        c2 = high * width - a - b2

        kari = min(max(a, b1, c1) - min(a, b1, c1), max(a, b2, c2) - min(a, b2, c2))

        ans = min(ans, kari)

    for i in range(1, width):
        a = i * high

        b1 = (width - i) * (high // 2)
        c1 = high * width - a - b1

        b2 = ((width - i) // 2) * high
        c2 = high * width - a - b2

        kari = min(max(a, b1, c1) - min(a, b1, c1), max(a, b2, c2) - min(a, b2, c2))

        ans = min(ans, kari)


    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 41584
#include<stdio.h>

int main(void)
{
    int num, top;
    int train[1024];
    int i;
 
    top = 0;
 
    while (scanf("%d", &num) != EOF){
        if (num == 0){
            printf("%d\n", train[top - 1]);
            train[top - 1] = 0;
            top--;
        }
        else { 
            train[top] = num;
            top++;
        }
    }
 
    return 0;
}

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

int main(void) {
    ll a;
    double b;
    cin >> a >> b;

    ll transB = round(100 * b);
    ll res = (a * transB) / 100;

    cout << res << endl;
    return 0;
}

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

long long dp[200001];
int l[10];
int r[10];
int n,k;
long long psum[200001];
const int mod=998244353;

int main() {
    scanf("%d %d",&n,&k);
    for(int i=0;i<k;i++) {
        scanf("%d %d",&l[i],&r[i]);
    }
    dp[1]=1;
    psum[1]=1;
    for(int i=2;i<=n;i++) {
        long long ret=0;
        for(int j=0;j<k;j++) {
            ret+=psum[max(0,i-l[j])]-psum[max(0,i-r[j]-1)];
            ret+=mod;
            ret%=mod;
        }
        dp[i]=ret;
        psum[i]=psum[i-1]+dp[i];
        psum[i]%=mod;
    }
    printf("%lld",dp[n]);
}

Measured memory_bytes: 6936
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include<deque>
#include<list>


using namespace std;

typedef long long ll;

typedef pair<ll, ll> pll;

const ll MOD_CONST = 1000000007;
const ll BIG_NUM = 1000000000000000000;
const int BIG_INT = 1000000000;

int n;
ll k;

vector<int> a(n);
vector<ll> f(n);
ll canLower(ll x) {
	ll cnt = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] * f[i] > x) {
			cnt += (a[i] - x / f[i]);
			
		}
	}

	
	return cnt <= k;
}


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

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

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

	sort(a.begin(), a.end(), greater<int>());
	sort(f.begin(), f.end());
	if (canLower(0)) {
		cout << 0 << endl;
		return 0;
	}

	ll r = 0;
	ll l = BIG_NUM;
	ll mid = (r + l) / 2;
	while (r != mid) {
		if (canLower(mid)) {
			l = mid;
		}
		else {
			r = mid;
		}

		mid = (r + l) / 2;
		
	}

	cout << l << endl;
}



Measured memory_bytes: 2560
/* ABC074_A
    Stuart_yg */

#include <stdio.h>
#include <string.h>
#include <math.h>

int main(){
    int n,a;

    //入力受け取り
    scanf("%d", &n);
    scanf("%d", &a);
    //差を出力
    printf("%d\n",n*n-a);
    return 0;
}

Measured memory_bytes: 1732
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



int main(){
    ll n,a,b,c;
    cin>>n>>a>>b>>c;
    cout<<n-a-b+c<<endl;
    
    
    return 0;
}



Measured memory_bytes: 3108
#include <iostream>
#include <string>
using namespace std;
int main() {
	int a, b, c, d, x, y;
	cin >> a >> b >> c >> d;
	if (a >= b) {
		x = b;
	}
	else {
		x = a;
	}
	if (c >= d) {
		y = d;
	}
	else {
		y = c;
	}
	cout << x + y << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< ll, ll >   cp2;
typedef pair< string, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789


///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////


int N, M;
int A, B;

vector<int>E[112345];

queue< int >q;
bool f[112345];

int ans[112345];

int main(){
    
    
    fill( f, f+112345, true );
    cin>>N>>M;
    REP( i, M ){
        cin>>A>>B;
        E[A].push_back( B );
        E[B].push_back( A );
    }
    
    q.push( 1 );
    f[1] = false;
    while( !q.empty() ){
        int t = q.front();
        q.pop();
        REP( i, E[t].size() ){
            int idx = E[t][i];
            if( f[idx] ){
                f[idx] = false;
                ans[idx] = t;
                q.push( idx );
            }
        }
    }
    
    puts("Yes");
    FOR( i, 2, N+1 ){
        cout<<ans[i]<<endl;
    }
}



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

#define ll long long int

ll knapsack(int idx,vector<ll> wt,vector<ll> val,int w,vector<vector<ll>> dp)
{
    if(idx==wt.size()) return 0;

    if(dp[idx][w] != -1) return dp[idx][w];

    if(w - wt[idx] >= 0)
    {
        dp[idx][w] = max(val[idx] + knapsack(idx+1,wt,val,w - wt[idx],dp), knapsack(idx+1,wt,val,w,dp) );
        return dp[idx][w];
    }

    dp[idx][w] = knapsack(idx+1,wt,val,w,dp);
    return dp[idx][w];
}

ll knapsack_2D(vector<ll> wt,vector<ll> val,int w)
{
    int n = wt.size();
    vector<vector<ll>> dp(n+1,vector<ll>(w+1,0));

    for(int i = 1;i <= n;i++ )
    {
        for(int cur_w = 1; cur_w <= w;cur_w++)
        {
            if(cur_w-wt[i-1] >=0)
            {
                dp[i][cur_w] = max(val[i-1] + dp[i-1][cur_w - wt[i-1]], dp[i-1][cur_w]) ;
            }
            else dp[i][cur_w] = dp[i-1][cur_w];
        }
    }

    return dp[n][w];
}

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

    vector<ll> wt(n),val(n);
    for(int i = 0;i<n;i++){
        cin>>wt[i]>>val[i];
    }

    // vector<vector<ll>> dp(n+1,vector<ll>(w+1,-1));
    // cout<<knapsack(0,wt,val,w,dp);

    cout<<knapsack_2D(wt,val,w);
}


Measured memory_bytes: 80256
n = int(input())
la = [int(w) for w in input().split()]
lb = [int(w) for w in input().split()]

ans = 0

for i in range(n):
    m = min(la[i], lb[i])
    la[i] -= m
    lb[i] -= m
    ans += m

    m = min(la[i + 1], lb[i])
    la[i+1] -= m
    lb[i] -= m
    ans += m

print(ans)


Measured memory_bytes: 25528
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, A, B, C;
	cin >> N >> A >> B >> C;

	vector<string> s(N);
	for (int i = 0; i < N; i++) cin >> s[i];
	s.emplace_back("**");

	string ans;
	for (int i = 0; i < N; i++) {
		if (s[i] == "AC") {
			if (A == C) {
				if (s[i + 1] == "BC") {
					A--, C++;
					ans += 'C';
				}
				else {
					A++, C--;
					ans += 'A';
				}
			}
			else if(A >= C) {
				A--, C++;
				ans += 'C';
			}
			else {
				A++, C--;
				ans += 'A';
			}
		}
		else if (s[i] == "AB") {
			if (A == B) {
				if (s[i + 1] == "BC") {
					A--, B++;
					ans += 'B';
				}
				else {
					A++, B--;
					ans += 'A';
				}
			}
			else if(A > B) {
				A--, B++;
				ans += 'B';
			}
			else {
				A++, B--;
				ans += 'A';
			}
		}
		else {
			if (B == C) {
				if (s[i + 1] == "AC") {
					C++, B--;
					ans += 'C';
				}
				else {
					C--, B++;
					ans += 'B';
				}
			}
			else if(B > C) {
				B--, C++;
				ans += 'C';
			}
			else {
				B++, C--;
				ans += 'B';
			}
		}

		if (A < 0 || B < 0 || C < 0) {
			cout << "No" << "\n";
			return 0;
		}

	}

	cout << "Yes" << "\n";
	for (const auto &e : ans) cout << e << "\n";

	return 0;
}

Measured memory_bytes: 9548
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;cin>>N;
  vint T(N);
  int sum=0;
  repeat(i,N){
    cin>>T[i];
    sum+=T[i];
  }
  int M;cin>>M;
  repeat(i,M){
    int P,X;cin>>P>>X;P--;
    cout << sum-T[P]+X<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

vint a, f;
int n;
ll k;

bool check(ll x) {
    vll mx(n);
    rep(i,n) mx[i] = x/f[i];
    ll ct = 0;
    rep(i,n) ct += max((ll)0,(ll)a[i]-mx[i]);
    return ct <= k;
}

int main() {
    cin >> n >> k;
    a.resize(n); 
    f.resize(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> f[i];
    sort(rall(a));
    sort(all(f));
    ll l = -1;
    ll r = inf_l;
    while (r-l > 1) {
        ll mid = (l+r)/2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout << r << endl;
}

Measured memory_bytes: 6404
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/















int N;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	int ans = (N - 1) / 2;
	cout << ans << endl;
}







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

using namespace std;

int main(){
  int k;
  string s;
  cin >> k >> s;
  if (s.length() <= k){
    cout << s << "\n";
  }
  else {
    cout << string(s.begin(), s.begin() + k) << "...\n";
  }
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> board(H);
  getline(cin, board.at(0));
  for (int i=0; i<H; i++) {
    getline(cin, board.at(i));
  }
  
  char ch;
  int sum;
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      ch = (board.at(i)).at(j);
      if (ch == '#')
        cout << ch;
      else {
        sum = 0;
        for (int n=-1; n<=1; n++) {
          for (int m=-1; m<=1; m++) {
            if (i+n<0 || i+n>=H || j+m<0 || j+m>=W)
              continue;
            if (board[i+n].at(j+m) == '#')
              sum++;
          }
        }
        cout << sum;
      }
    }
    cout << endl;
  }
  
}


Measured memory_bytes: 256
import random

def calc_score(D, C, S, T):
    score = 0
    last = [0]*26
    for d in range(D):
        t = T[d] - 1
        score += S[d][t]
        last[t] = d + 1
        for i in range(26):
            score -= C[i]*(d + 1 - last[i])
    return score

def main():
    D = int(input())
    C = list(map(int, input().split()))
    S = []
    for i in range(D):
        S.append(list(map(int, input().split())))

    sorted_scores = []
    for i in range(D):
        scores = [(j, S[i][j]) for j in range(26)]
        sorted_scores.append(sorted(scores, key=lambda x: x[1], reverse=True))
    # print(sorted_scores)
    sorted_c = []
    sorted_c = [(i, C[i]) for i in range(26)]
    sorted_c.sort(key=lambda x: x[1], reverse=True)
    # print(sorted_c)
    last = [0]*26
    ans = []
    for d in range(D):
        score = -100*365*365
        t = 0
        for i in range(26):
            tmp = S[d][i]
            for j in range(26):
                if i != j:
                    tmp -= C[j]*(d + 1 - last[j])
            if tmp > score:
                score = tmp
                t = i + 1
        last[t - 1] = d + 1
        ans.append(t)
    score = calc_score(D, C, S, ans)

    # try to reduce penalty
    for i in range((10**3)//2):
        d = random.randint(0, D - 1)
        t = random.randint(0, 12)
        org_t = ans[d]
        ans[d] = sorted_c[t][0] + 1
        s = calc_score(D, C, S, ans)
        if s <= score:
            ans[d] = org_t
        else:
            score = s

    # try to increase score
    for i in range((10**3)//2):
        d = random.randint(0, D - 1)
        t = random.randint(0, 12)
        org_t = ans[d]
        ans[d] = sorted_scores[d][t][0] + 1
        s = calc_score(D, C, S, ans)
        if s <= score:
            ans[d] = org_t
        else:
            score = s
    print('\n'.join(map(str, ans)))

if __name__ == '__main__':
    main()


Measured memory_bytes: 79280
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 200005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


bool vis[N];

void solve(){
    int n, m; cin>>n>>m;
    int si = 1;
    int ei = n;
    int i = 0;
    vector<pii> vect;
    while(i<m){
        int v1 = ei-si;
        int v2 = n-v1;
        if(!vis[v1] && !vis[v2] && v1!=v2){
            vect.pb({si, ei});
            vis[v1] = true;
            vis[v2] = true;
            si++;
            ei--;
            i++;
        }
        else{
            si++;
        }
    }
    for(pii p: vect){
        cout<<p.F<<" "<<p.S<<"\n";
    }
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}





Measured memory_bytes: 5520
#include<bits/stdc++.h> 
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define fo(i,k,n) for(i=k;i<=n;i++)
#define endl '\n'
void solve(){
	ll i,j,n,k;
	cin>>n>>k;
	ll h[n];
	fo(i,0,n-1) cin>>h[i];
	ll dp[n];
	dp[0]=0;
	fo(i,1,n-1){
		dp[i]=LLONG_MAX;
		for(j=1;j<=k;j++){
			if(i-j<0) break;
			dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]) );
		}
	}
	cout<<dp[n-1]<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll t;
	t=1;//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 1792
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
arrA = list(map(int,input().split()))
# arrA = np.array(input().split(),dtype=np.int64)
arrA.sort()
arrA = arrA[::-1]

Alice = sum(arrA[0::2])
Bob = sum(arrA[1::2])

ans = Alice-Bob

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


Measured memory_bytes: 3060
n,k=map(int,input().split())
s=input()
t=list(s)
if t[k-1]=='A':
  t[k-1]='a'
elif t[k-1]=='B':
  t[k-1]='b'
elif t[k-1]=='C':
  t[k-1]='c'
print("".join(t))

Measured memory_bytes: 3060
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]

diff = [0] * N
minus_count = 0
minus_sum = 0
for i in range(N):
    diff[i] = A[i] - B[i]
    if diff[i] < 0:
        minus_count += 1
        minus_sum += -diff[i]

diff = sorted(diff, reverse=True)
cumsum = [0] * (N + 1)
for i in range(N):
    cumsum[i] += diff[i] + cumsum[i - 1]

# print(minus_count)
# print(minus_sum)
# print(diff)
# print(cumsum)


def check(x):
    a = x - minus_count
    if a < 0:
        return False

    plus_sum = cumsum[a - 1]
    # print(x, a)
    # print('plus', plus_sum)
    # print('minus', minus_sum)
    if plus_sum >= minus_sum:
        return True


def main():
    if sum(A) < sum(B):
        print(-1)
        return

    sup = N
    inf = -1
    while sup - inf > 1:
        mid = (sup + inf) // 2

        if check(mid):
            sup = mid
        else:
            inf = mid

    print(sup)


if __name__ == '__main__':
    main()


Measured memory_bytes: 20468
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000000000
int S[500005],n,count=0;
void Merge(int left,int mid,int right)
{
	int *q=(int *)malloc(sizeof(int)*(mid-left+1));
	int *p=(int *)malloc(sizeof(int)*(right-mid+1));
	int k,i,j;
	for(i=0;i<mid-left;i++)
	p[i]=S[i+left];
	for(i=0;i<right-mid;i++)
	q[i]=S[i+mid];
	p[mid-left]=q[right-mid]=MAX;
	i=j=0;
	for(k=left;k<right;k++)
	{
		if(q[i]>p[j])
		S[k]=p[j++];
		else
		S[k]=q[i++];
		count++;
	}
}
void MergeSort(int left,int right)
{
	if(left+1<right)
	{
		int mid=(left+right)/2;
		MergeSort(left,mid);
		MergeSort(mid,right);
		Merge(left,mid,right);
	}
}
int main(int argc, char *argv[])
{
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%d",&S[i]);	
	MergeSort(0,n);
	for(i=0;i<n;i++)
	if(i+1==n)
	printf("%d\n%d\n",S[i],count);
	else
	printf("%d ",S[i]);
	return 0;
}


Measured memory_bytes: 64464
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (1e9)
#define INFL (1e12)
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>using arr=vector<vector<T>>;
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
 
int main()
{
    int n;
    while(cin >> n){
        if(n==0) break;
        int h1, m1, s1, h2, m2, s2;
        int maxv=0, minv=3600*24;
        vector<int> v(60*60*24, 0);
        rep(i, n){
            scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
            // printf("%d:%d:%d %d:%d:%d\n", h1, m1, s1, h2, m2, s2);
            int st = h1*3600 + m1*60 + s1;
            int ed = h2*3600 + m2*60 + s2;
            chmin(minv, st); chmax(maxv, ed);
            v[st] += 1;
            v[ed] += -1;
        }
        int ans = 0;
        rep(i, 86400) v[i+1] += v[i];
        FOR(i, minv, maxv+1) chmax(ans, v[i]);
        pr(ans);
    }
    return 0;}


Measured memory_bytes: 3508
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>

using namespace std;

int main()
{
  uint64_t H;

  cin >> H;

  uint64_t attack_num = 0;
  uint64_t index_num = 0;
  while (true) {
    static uint64_t present_hp = H;
    attack_num += pow(2, index_num);
    if (present_hp < 2) {
      break;
    }
    else {
      present_hp /= 2;
    }
    index_num++;
  }

  cout << attack_num;
  return 0;
}


Measured memory_bytes: 256
while True:
    try:
        a,b = map(int, input().split())
        nlist = sorted([a,b])
        while True:
            c = nlist[1]%nlist[0]
            nlist = [c, nlist[0]]
            if (c == 0):
                break
        ss = nlist[1]
        print(ss, int(a*b/ss))
    
    except EOFError:
        break


Measured memory_bytes: 5596
#include<bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define ll long long
#define d1(x)  cerr << #x << "--> " << x << endl
#define d2(x, y)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<endl
#define d3(x, y,z)  cerr << #x << "--> " << x << " | " << #y << "--> " << y <<" | " << #z << "--> "<< z<< endl
#define vpll vector<pair<ll,ll>>
#define F first
#define S second
#define T ll tt; cin>>tt; while(tt--)
using namespace std;

ll mode=pow(10,9)+7;
bool cmp(pair<ll,ll> x, pair<ll, ll> y){
    return x.S<y.S;
}
//ll n,k,m;


int main(){ 
    
  //  #ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
  //  #endif
    
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	ll n;
	cin>>n;
	string a,b;
	cin>>a>>b;
	for (int i=0;i<n;i++){
		cout<<a[i]<<b[i];
	}
	
    return 0;
}

Measured memory_bytes: 256
N = int(input())
tl = [[] for _ in range(N+1)]
d = {}
for _ in range(N-1):
    a, b, c = map(int, input().split())
    tl[a].append(b)
    tl[b].append(a)
    d[(a, b)] = c
    d[(b, a)] = c
Q, K = map(int, input().split())
seen = [False]*(N+1)
stack = [K]
seen[K] = True
while len(stack):
    n = stack.pop()
    for v in tl[n]:
        if not seen[v]:
            stack.append(v)
            seen[v] = True
            if n != K:
                d[(K, v)] = d[(K, n)]+d[(n, v)]
for _ in range(Q):
    x, y = map(int, input().split())
    print(d[(K, x)]+d[(K, y)])


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

#define rep(i, n) for(int (i) = 0; i < (n); ++(i))

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 62;

int main() {
  ll N;
  std::cin >> N;

  ll ans = INF;
  for(ll a = 1; a * a <= N; ++a) {
    if(N % a == 0) {
      ans = std::min(ans, (a - 1) + (N / a - 1));
    }
  }
  std::cout << ans << '\n';
}


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

void convert(int x, char a[], int n) {//dec to bin array, 低位
    int p = 0, t = x;
    while (t > 0) {
        a[p] = t % 2;
        t >>= 1;
        p++;
    }
}

bool check(int mat[15][15], int k[], char bin[], int n, int m, int p[]) {//for one state, check if all light
    //int cnt = 0;//count how many '1'
    int i, j;
    for (i = 0; i < m; i++) {
        int cnt = 0;
        for (j = 0; j < k[i]; j++) {
            if (bin[mat[i][j]] == 1)
                cnt++;
        }
        if (p[i] == 0 && cnt % 2 != 0 || p[i] == 1 && cnt % 2 == 0)
            return false;
    }
    return true;
}

int main() {
    int a, p[20], m, n, i, j, k[20];
    int s[15][15];
    
    scanf("%d %d", &n, &m);

    for (i = 0; i < m; i++) {
        scanf("%d", &k[i]);
        for (j = 0; j < k[i]; j++) {
            scanf("%d", &s[i][j]);
            s[i][j]--;//1~N -> 0~N-1
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d", &p[i]);
    }
     
    int cnt = 0;
    int l = 1 << n;
    char arr[16];
    for (i = 0; i < l; i++) {
        convert(i, arr, n);
        if (check(s, k, arr, n, m, p)) {
            cnt++;
        //    printf("%d\n", i);
          //  printf("%d %d %d %d %d\n", arr[0],arr[1],arr[2],arr[3],arr[4]);
        }
    }
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b){ if(a < b) { a=b; return 1; }return 0;}
template<class T> inline bool chmin(T& a, T b){ if(a > b) { a=b; return 1; }return 0;}
const long long INF = 1LL << 60;
// spring s; cin >> s;
// cout << res << endl;
// --------write my code!!!!!----------//

int main(){
    int A; cin >> A;
    int first; cin >> first;
    int res = 1;
    
    rep(i,A-1){
        int B; cin >> B;
        if(first<=B){
            res++;
            first=B;
        }
        else continue;
    }
    
    cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
ll mod = 1000000007;

ll C[2005][2005];

void PascalTriangle() {
    rep(i, 2005) {
        C[i][0] = C[i][i] = 1;
    }
    for(int i = 2; i < 2005; i++) {
        for(int j = 1; j < i; j++) {
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            C[i][j] %= mod;
        }
    }
}

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

    PascalTriangle();
    
    for(int i = 1; i <= k; i++) {
        ll ans = C[n-k+1][i]*C[k-1][i-1];
        ans %= mod;
        cout << ans << endl;
    }
    
    return 0;
}

Measured memory_bytes: 30208
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<unistd.h>
#include <array>
#include <map> 
#define ALL(a)  (a).begin(),(a).end()
const long long INF = 1LL<<58;


using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int a, int b)
{
  if(a>b){
    return gcd(b,a);
  }
	return a == 0 ? b : gcd(b % a, a);
}
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}

struct File {
    int aa;
    int bb;

    File(const int& aa, const int& bb)
        : aa(aa), bb(bb) {}
};

bool operator<(const File& a, const File& b)
{
    // ファイル種別、ファイル名の順番で優先順位を付けて比較
    return std::tie(a.aa, a.bb) < std::tie(b.aa, b.bb);
}

long long kaijo(long long x){
  long long l=10*10*10*10*10*10*10*10*10+7;
  long long sum=1;
  for(int i=x;i>0;i--){
    sum*=i;
    if(sum>l){
      sum%=l;
    }
  }
  return sum;
}


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

//formerは前方のindex(自分自身を含んで良い)
template<class T>int former(const vector<T>&v,T x){
  return upper_bound(v.begin(),v.end(),x)-v.begin()-1;
}
//latterは後方のindex(自分自身を含んで良い)
template<class T>int latter(const vector<T>&v,T x){
  return lower_bound(v.begin(),v.end(),x)-v.begin();
}


int main() {
    int N;
    cin>>N;
    vector<int>x;
    vector<int>y;
    vector<int>h;
    x.resize(N);
    y.resize(N);
    h.resize(N);
    for(int i=0;i<N;i++){
      cin>>x[i]>>y[i]>>h[i];
    }
    int kodo=0;
    int xx,yy;
    for(int px=0;px<102;px++){
      for(int py=0;py<102;py++){
        for(int i=0;i<N;i++){
          if(h[i]>0){
            kodo=h[i]+abs(x[i]-px)+abs(y[i]-py);
            break;
          }
        }
        for(int i=0;i<N;i++){
          if(h[i]!=max(kodo-abs(x[i]-px)-abs(y[i]-py),0)){
            break;
          }
          if(i==N-1){
            cout << px << " " << py << " " << kodo<<endl;
                    return 0;
          }
        }
        


        
      }
    }
    

}
  




Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MAX 100000
typedef long long ll;
typedef pair<ll,int> P;

bool check(int x){
  for(int i=1;;i++){
    if(i*i==x) return true;
    else if(i*i>x) return false;
  }
}

int main(){
  int N,D,X[10][10];
  cin>>N>>D;
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++) cin>>X[i][j];
  }
  int x=0,ans=0;
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++,x=0){
      for(int k=0;k<D;k++){
        x+=(X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
      }
      if(check(x)) ans++;
    }
  }
  cout<<ans<<endl;
}


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

a = [b[0]]
for i in range(n-2):
    a.append(min(b[i],b[i+1]))
  #  print(b[i],b[i+1])
a.append(b[-1])
#print(a)
print(sum(a))

Measured memory_bytes: 38608
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int A[] = new int[N];
		for(int i=0;i<N;i++){
			A[i]=Integer.parseInt(sc.next());
		}
		sc.close();
		
		int count=0;
		for(int i=0;i<N-1;i++){
			int minj=i;
			for(int j=i;j<N;j++){
				if(A[j]<A[minj]){
					minj=j;
				}
			}
			int temp=A[i];
			if(i!=minj){
				A[i]=A[minj];
				A[minj]=temp;
				count++;
			}
		}
		
		for(int i=0;i<N-1;i++){
			System.out.print(A[i]+" ");
		}
		System.out.println(A[N-1]);
		System.out.println(count);

	}

}

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

using namespace std;

typedef long long ll;
typedef long double ld;

int n,k;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;n--;k--;
    cout<<(n+k-1)/k<<"\n";
    return 0;
}
/**
**/


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

int main(void){
	int h, w;
	while(1){
		cin >>h >>w;
		if(h==0 && w==0){
			break;
		}
		for(int i=0; i<h; i++){
			for(int j=0; j<w; j++){
				if(i==0 || i==h-1 || j==0 || j==w-1){
					cout <<"#";
				}else{
					cout <<".";
				}			}
			cout <<endl;
		}
		cout <<endl;
	}
	return 0;
}

Measured memory_bytes: 1152