akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <utility>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, K; cin >> N >> K;
  long long int ans = K;
  for (int i = 1; i < N; i++)
    ans *= (K-1);
  cout << ans << endl;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/10/16  Problem: nagoya_19_02  / Link:   ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL N;

LL ans = 0LL;

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

	LL a, b, c;

	cin >> a >> b >> c;
	ans = LLONG_MAX;
	ans = min({ ans, abs(a / 2 * b*c - (a - a / 2)*c*b),abs((a - a / 2) * b*c - (a / 2)*c*b) });
	ans = min({ ans, abs(b / 2 * c*a - (b - b / 2)*a*c),abs((b - b / 2) * c*a - (b / 2)*a*c) });
	ans = min({ans, abs(c / 2 * a*b - (c - c / 2)*b*a),abs((c-c/2) * a*b - (c / 2)*b*a) });

	
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
n = input()
a = int(n[0])
b = int(n[1])
c = int(n[2])
d = int(n[3])
if a+b+c+d==7:
    print(str(a)+"+"+str(b)+"+"+str(c)+"+"+str(d)+"=7")
    exit()
elif a+b+c-d==7:
    print(str(a)+"+"+str(b)+"+"+str(c)+"-"+str(d)+"=7")
    exit()
elif a+b-c+d==7:
    print(str(a)+"+"+str(b)+"-"+str(c)+"+"+str(d)+"=7")
    exit()
elif a+b-c-d==7:
    print(str(a)+"+"+str(b)+"-"+str(c)+"-"+str(d)+"=7")
    exit()
elif a-b+c+d==7:
    print(str(a)+"-"+str(b)+"+"+str(c)+"+"+str(d)+"=7")
    exit()
elif a-b+c-d==7:
    print(str(a)+"-"+str(b)+"+"+str(c)+"-"+str(d)+"=7")
    exit()
elif a-b-c+d==7:
    print(str(a)+"-"+str(b)+"-"+str(c)+"+"+str(d)+"=7")
    exit()
else:
    print(str(a)+"-"+str(b)+"-"+str(c)+"-"+str(d)+"=7")

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
  int a,b,n;
  while(cin >>a>>b>>n){
    int ans = 0;
    a%=b;
    for(int i=0; i<n; i++){
      a*=10;
      ans+=a/b;
      a%=b;
    }
    cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename x>
using ordered_set = tree<x,null_type,less<x>,rb_tree_tag,tree_order_statistics_node_update>;
#define sorta(a,n) sort(a,a+n)
#define sortad(a,n) sort(a,a+n,greater<__typeof(a[0])>())
#define all(x) (x).begin(),(x).end()
#define ms0(x) memset((x),0,sizeof((x)))
#define ms1(x) memset((x),-1,sizeof((x)))
typedef pair<int,int> pi;
#define inarr(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define prinarr(arr) {for(int x:arr)cout<<x<<" ";} cout<<"\n";
#define cout1(a) cout<<a<<"\n";
#define cout2(a,b) cout<<a<<" "<<b<<"\n";
#define cout3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";
#define setpre(n) cout<<fixed<<setprecision(8)<<n<<"\n";
#define filldp(arr,n,m,k) for(int i=0;i<n;i++){for(int j=0;j<m;j++) arr[i][j]=k;}

#define mod 1000000007
#define mod1 998244353


vector<vector<int>> adj;
vector<int> dis;
vector<int> parent;
vector<bool> visited;

void newgr(int n){
    n+=10;
    adj=vector<vector<int>>(n);
    dis=vector<int>(n,0);
    //parent=vector<int>(n,-1);
    visited=vector<bool>(n,false);
}

void dfs(int s){
    visited[s]=true;
    for(auto u:adj[s]){
        if(!visited[u]){
            //parent[u]=s;
            dis[u]=dis[s]+1;
            dfs(u);
        }
    }
}

void bfs(int s){
    queue<int> q;
    q.push(s);
    visited[s]=true;
    dis[s]=0;
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        for(auto x:adj[u]){
            if(!visited[x]){
                //parent[x]=u;
                visited[x]=true;
                dis[x]=dis[u]+1;
                q.push(x);
            }
        }
    }
}

long long power(long long x,long long y){  
    long long ans=1;
    x%=mod;
    while(y>0){
        if(y&1) ans=(ans*x)%mod;
        y>>=1;
        x=(x*x)%mod;
    }
    return ans;
}

long long modinv(long long b){ 
    return power(b,mod-2);
}



int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int ans[n+1]={};
    for(int i=1;i<=200;i++){
        for(int j=1;j<=200;j++){
            for(int k=1;k<=200;k++){
                int pt=(i*i+j*j+k*k+i*j+j*k+k*i);
                if(pt<=n){
                    ans[pt]++;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    cout1(ans[i]);

    return 0;
}

Measured memory_bytes: 3652
n = int(input())
hi = list(map(int,input().split()))

p = 2
dp = []
dp.append(0)
dp.append(abs(hi[0]-hi[1]))
while(p != n):
    if abs(hi[p] - hi[p-1]) + dp[p-1] <= abs(hi[p]-hi[p-2])+dp[p-2]:
        dp.append(abs(hi[p]-hi[p-1])+dp[p-1])
        p += 1
    else:
        dp.append(abs(hi[p]-hi[p-2])+dp[p-2])
        p += 1

print(dp[-1])

Measured memory_bytes: 13928
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader ( new InputStreamReader(System.in));
		String []input = br.readLine().split(" ");
		int board = Integer.parseInt(input[0]);
		int alice = Integer.parseInt(input[1]);
		int borys = Integer.parseInt(input[2]);
		if(Math.abs(alice - borys)%2 == 0) {
			System.out.println("Alice");//お互いの差が偶数だったら
		}else {
			System.out.println("Borys");//お互いの差が奇数だったら
		}
	}
}

Measured memory_bytes: 21204
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int T = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        System.out.println( solve(N, T, A) );
    }

    private static int solve(int N, int T, int[] A) {
        int[] B = new int[N];
        B[N-1] = 0;
        int maxB = 0;
        int high = A[N-1];
        for (int i = N-2; i >=0 ; i--) {
            if( A[i] > high ) {
                high = A[i];
            }
            B[i] = high - A[i];
            maxB = Math.max(B[i], maxB);
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            if( B[i] == maxB ) ans++;
        }

        return ans;
    }

    private static void show(int[] array) {
        StringJoiner j = new StringJoiner(" ");
        for (int i : array) {
            j.add(String.valueOf(i));
        }
        System.err.println( j.toString() );
    }
}

Measured memory_bytes: 49404
# -*- coding: utf-8 -*-
a = []
for i in range(3):
  tmp = input()
  a.append(list(map(int, tmp.split())))

n = int(input())
# print('n', n)
b = []
for j in range(n):
    b.append(int(input()))

# print('a', a)
# print('b', b)

for i in range(3):
    for j in range(3):
        if a[i][j] in b:
            a[i][j] = 0

def check(a):
    #　たてビンゴ
    # 斜め
    if a[0][0] == 0 and a[1][1] == 0 and a[2][2] == 0:
            print('Yes')
            exit()
    if a[0][2] == 0 and a[1][1] == 0 and a[2][0] == 0:
            print('Yes')
            exit()
    for i in range(3):
        if (a[0][i] == 0 and a[1][i] == 0 and a[2][i] == 0):
            print('Yes')
            exit()
        if a[i] == [0, 0, 0]:
            print('Yes')
            exit()
    print('No')

check(a)

Measured memory_bytes: 3064
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def main():
    X = int(input())
    A = int(input())
    B = int(input())
    print((X - A) % B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4084
#include <bits/stdc++.h>
#define fill(x,c) memset(x,c,sizeof(x))
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
int a[200010];
int t,n;
int MOD = 1e9+7;
const int SIZE = 1e6+10;
int main(){
	cin>>n;
	REP(I,n){
		cin>>a[I];
	}
	sort(a,a+n);
	
	cout<<a[n/2]-a[n/2-1];
	return 0;
}




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

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
//priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

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

int n;

void solve(){
  cin >> n;
  int x=1;
  int p;
  while(x<=n){
    p=x;
    x*=2;
  }
  cout << p;
  cout << endl;
}

int main() {
  solve();
  return 0;
}



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

int main() {
    int N, T;
    cin >> N >> T;

    int c[N], t[N];
    for (int i = 0; i < N * 2; i++) {
        if (i % 2 < 1) {
            cin >> c[i / 2];
        } else {
            cin >> t[(i - 1) / 2];
        }
    }

    int minc = 1001;
    for (int i = 0; i < N; i++) {
        if (t[i] <= T && c[i] < minc) {
            minc = c[i];
        }
    }

    if (minc == 1001) {
        cout << "TLE" << endl;
    } else {
        cout << minc << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

ll dp[10001];

void solve(long long H, long long N, vector<long long> A, vector<long long> B){
	rep(i, H+1) {
		dp[i] = INF;
	}
	dp[0] = 0;
	repn(i, H) {
		rep(j, N) {
			dp[i] = min(dp[i], dp[max(i-A[j],0LL)]+B[j]);
		}
	}
	cout << dp[H] << endl;
}

int main(){	
	long long H;
	long long N;
	scanf("%lld",&H);
	scanf("%lld",&N);
	vector<long long> B(N-1+1);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
	}
	solve(H, N, A, B);
	return 0;
}



Measured memory_bytes: 384
n=input()
k=int(input())


dp=[[[0]*2 for i in range(k+2)] for j in range(len(n)+1)]
dp[0][0][0]=1


for i in range(len(n)):
  x=int(n[i])
  for j in range(k+1):
    
    if x==0:
      dp[i+1][j][0]+=dp[i][j][0]
    else:
      dp[i+1][j+1][0]+=dp[i][j][0]

    dp[i+1][j][1]+=dp[i][j][1]    #０
    if x!=0:
      dp[i+1][j][1]+=dp[i][j][0]    #０
    
    dp[i+1][j+1][1]+=dp[i][j][1]*9    #1~9

    if x!=0:
      dp[i+1][j+1][1]+=dp[i][j][0]*max(x-1,0)    #1~x-1


print(dp[-1][k][0]+dp[-1][k][1])

Measured memory_bytes: 62628
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
#define all(a)  (a).begin(),(a).end()
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
int per(int n, int r) {
	r = n - r;
	int sum = 1;
	int i;
	for (i = n; i >= r + 1; i--)sum *= i;
	return sum;
}
struct UnionFind {
	vector<int> par;

	UnionFind(int n) : par(n, -1) { }

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

	bool issame(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x) {
		return -par[root(x)];
	}
};
signed main(){
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	rep(i, b) {
		rep(j, a) {
			cout << 1;
		}
		rep(j, w - a) {
			cout << 0;
		}
		cout << endl;
	}
	rep(i, h - b) {
		rep(j, a) {
			cout << 0;
		}
		rep(j, w - a) {
			cout << 1;
		}
		cout << endl;
	}
}


Measured memory_bytes: 1280
n, m = map(int, input().split())
A = list(map(int, input().split()))
digit = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

dp = [(-1, -1)]*(n+1)
dp[0] = (0, -1)
for k in range(1, n+1):
    max_value = -1
    max_d = -1
    for num in A:
        if k >= digit[num]:
            suf, d = dp[k - digit[num]]
            if suf >= 0:
                value = num * (10 ** (d + 1)) + suf
                if value > max_value:
                    max_value = value
                    max_d = d + 1

    dp[k] = (max_value, max_d)
print(dp[n][0])

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

// Begin Header {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

#define all(x) x.begin(), x.end()
#define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)

constexpr size_t    operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t  operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };

constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;

template <class T>
using MaxHeap = priority_queue<T, vector<T>, less<T>>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

template <class T>
inline void input(vector<T> &vec) {
    for (auto &e: vec) {
        cin >> e;
    }
}

template <class T>
inline void input(vector<vector<T>> &mat) {
    for (auto &vec: mat) {
        input(vec);
    }
}

inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) {
        cout << " ";
    }
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e: vec) {
        os << e << delim[&e == &vec.back()];
    }
    return os;
}

template <class T>
inline vector<T> makeVector(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeVector(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(initValue, args...))>(sz, makeVector<T>(initValue, args...));
}

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

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

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

template <class T>
inline T diff(const T &a, const T &b) noexcept {
    return a < b ? b - a : a - b;
}
// End Header }}}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(string, a, b, c);

    a += b;
    a += c;

    print(stoi(a) % 4 == 0 ? "YES" : "NO");

    return 0;
}


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

signed main(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    int ans = 0;
    if(k >= a){
        ans += a;
        k -= a;
    }
    else{
        ans += k;
        k = 0;
    }
    if(k >= b){
        ans += 0;
        k -= b;
    }
    else{
        ans += 0;
        k = 0;
    }
    if(k >= c){
        ans -= c;
        k -= c;
    }
    else{
        ans -= k;
        k = 0;
    }
    cout << ans << endl;
}

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

int main(){
  int i,k,m,j,l,cnt=0,flag=1;
  char s[5000],ss[25000][6],sss[5][5];
  scanf("%s",s);
  scanf("%d",&k);
  for(i=1;i<=k;i++){
    for(j=0;j<strlen(s)-i+1;j++){
      for(l=0;l<i;l++){
        ss[cnt][l]=s[j+l];
      }
      cnt++;
    }
  }

  for(i=0;i<k;i++){
    strcpy(sss[i],"zzzzz");
    for(j=0;j<cnt;j++){
      if(strcmp(sss[i],ss[j])>0){
        flag=1;
        for(l=0;l<i;l++){
          if(strcmp(ss[j],sss[l])==0)flag=0;
        }
        if(flag) strcpy(sss[i],ss[j]);
      }
    }
  }
  printf("%s\n",sss[k-1]);
}

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

struct Edge{
  int to;
  int weight;
  Edge(int t,int w) : to(t),weight(w){}
};

using Graph = vector<vector<Edge>>;

int main(){
  int n,m,r;
  cin >> n >> m >> r;
  Graph G(n);

  for(int i=0;i<m;++i){
    int from,to,weight;
    cin >> from >> to >> weight;
    G[from].push_back(Edge(to,weight));
  }
  vector<ll> dist(n,1001001);
  vector<int> cnt(n,0);
  queue<int> que;
  dist[r]=0;
  cnt[r]=1;
  que.push(r);
  while(!que.empty()){
    int v=que.front();
    que.pop();
    for(auto nv : G[v]){
      if(dist[nv.to] == 1001001 || dist[nv.to] > dist[v]+nv.weight){
        if(dist[nv.to]<0 && cnt[nv.to]>m){
          cout << "NEGATIVE CYCLE" << endl;
          return 0;
        }
        dist[nv.to] = dist[v]+nv.weight;
        cnt[nv.to]++;
        que.push(nv.to);
      }
    }
  }
  for(int i=0;i<n;++i){
    if(dist[i]==1001001) cout << "INF" << endl;
    //else if(dist[i]<0) cout << "NEGATIVE CYCLE" << endl;
    else cout << dist[i] << endl;
  }
  return 0;

}



Measured memory_bytes: 3172
N,W=map(int,input().split())
v=[0]
w=[0]
for r in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[]
for i in range(N+1):
    dp.append([0]*(W+1))

for i in range(1,N+1):
    for j in range(1,W+1):
        m1=dp[i-1][j]
        m2=0
        if w[i]<=j:
            m2=dp[i-1][j-w[i]]+v[i]
        # print(W,w[i])
        dp[i][j]=max(m1,m2)
print(dp[N][W])

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

int main(){
  int N; cin>>N;
  vector<int>s(N); 
  int S=0;
  for(int i=0;i<N;i++){
    cin>>s.at(i);
    S+=s.at(i);
  }
  
  if(S%10!=0)
    cout<<S;
  else{
    int margin=S;
    for(int i=0;i<N;i++){
      if(s.at(i)%10!=0)
        margin=min(margin,s.at(i));
    }
    
    cout<<S-margin;
  }
}
    
    
  

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

hap=0
for i in range(0,n-1):
    if s[i] == s[i+1]:
        hap += 1

if hap+2*k >= n-1:
    hap = n-1

else:
    hap = hap + 2*k

print(hap)

Measured memory_bytes: 3316
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)] + [0]
dp = [[float("inf") for _ in range(5)] for _ in range(n+1)]
def ev(x):
	if x == 0:
		return 2
	else:
		return x&1
def od(x):
	return (x+1)&1

dp[0] = [a[0], ev(a[0]), od(a[0]), ev(a[0]), a[0]]
for i in range(1, n+1):
	dp[i][0] = dp[i-1][0] + a[i]
	dp[i][1] = min(dp[i-1][:2]) + ev(a[i])
	dp[i][2] = min(dp[i-1][:3]) + od(a[i])
	dp[i][3] = min(dp[i-1][:4]) + ev(a[i])
	dp[i][4] = min(dp[i-1]) + a[i]
print(min(dp[n]))

Measured memory_bytes: 74436
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		int i = 0;
		int j = 0;
		int k = 0;
		int N = sc.nextInt();
		int Y = sc.nextInt();
		boolean result = false;
 
		loop: for (i = 0; i <= N; i++) {
			for (j = 0; j <= N - i; j++) {
				k = N - i - j;
				if (Y == 10000 * i + 5000 * j + 1000 * k) {
					result = true;
					break loop;
				}
			}
		}
 
		if (result) {
			System.out.println(i + " " + j + " " + k);
		} else {
			System.out.println("-1 -1 -1");
		}
	}
}

Measured memory_bytes: 22996
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  string s;
  cin >> s;
  if(s=="Sunny") cout << "Cloudy" << endl;
  else if(s=="Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
int a[200002], b[200002], n;
vector<int> v;
multiset<int> s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        auto it = s.lower_bound(x);
        if(it == s.begin()) s.insert(x);
        else
        {
            it--;
            s.erase(it);
            s.insert(x);
        }
    }
    cout << s.size();
}

Measured memory_bytes: 4992
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

int main() {
	int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
	for (int i = 0; i < tx-sx; i++)cout << "R";
	for (int i = 0; i < ty-sy; i++)cout << "U";
	for (int i = 0; i < tx-sx; i++)cout << "L";
	for (int i = 0; i < ty-sy; i++)cout << "D";
	cout << "L";
	for (int i = 0; i <= ty - sy; i++)cout << "U";
	for (int i = 0; i <= tx - sx; i++)cout << "R";
	cout << "D"<<"R";
	for (int i = 0; i <= ty - sy; i++)cout << "D";
	for (int i = 0; i <= tx - sx; i++)cout << "L";
	cout << "U";
}



Measured memory_bytes: 256
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    s = str(stdin.readline().rstrip())
    t = str(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    anss = []
    for i in range(len(s)-len(t)+1):
        test = s[i:len(t)+i]
        flag = True
        for j in range(len(t)):
            if test[j] != "?" and test[j] != t[j]:
                flag = False
        if flag==True:
            ans = s[0:i] + t + s[i+len(t):]
            ans = ans.replace("?","a")
            anss.append(ans)
    if len(anss) == 0:
        print("UNRESTORABLE")
        exit()
    anss.sort()
    print(anss[0])


if __name__ == '__main__':
    solve()


Measured memory_bytes: 9020
#include<iostream>
using namespace std;
int main(){
	int n,sum;
	while(cin>>n,n){
		sum=0;
		for(int i=1;i*i<=n;i++){
			if(n%i==0&&i!=n){
				sum+=i;
				if(n/i!=n&&n/i!=i)
				sum+=n/i;
			}
			
		}
		if(n==sum)
		cout<<"perfect number"<<endl;
		else if(n>sum)
		cout<<"deficient number"<<endl;
		else 
		cout<<"abundant number"<<endl;
	}
	return 0;
}

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

int main() {
  int h1, h2, m1, m2, k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  cout << (h2 - h1) * 60 + m2 - m1 - k;
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ld long double
#define inf 1e18
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mk make_pair
#define mod 1000000007
#define setbits __builtin_popcount
#define fi first
#define se second
int main()
{
    fastIO;
    ll n,m;
    cin>>n>>m;
    string str;
    ll val=0,val1=0,x,y,i;
    set<ll>s;
    map<ll,ll>m1;
    for(i=0;i<m;i++)
    {
        cin>>x>>str;
        if(str=="WA")
        {
            if(s.find(x)==s.end())
            {
                m1[x]++;
            }
        }
        else
        if(str=="AC")
        {
            s.insert(x);
        }
    }
    for(auto itr=m1.begin();itr!=m1.end();itr++)
    {
        if(s.find(itr->first)!=s.end())
        {
            val1+=itr->second;
        }
    }
    cout<<s.size()<<' '<<val1<<'\n';
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define lcm(x, y) ((x) * (y) / __gcd((x), (y)))
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#include <iostream>

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; // trick to explore an implicit 2D grid
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; // S,SE,E,NE,N,NW,W,SW neighbors  //GO FOR EVEN FOR 4 moves

#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
vector<LL> v, sum;
LL sz;
bool possible(LL check, LL extra, LL val)
{
   // part;
    auto lower = lower_bound(v.begin(), v.end(), check);
    LL pos = lower - v.begin();
    LL last = pos - 1;
    LL uninvolved = sz - val;
    //debug(pos);
    //debug(check);
    //debug(pos);
    //debug(last);
    //debug(uninvolved);
    LL needed = check*(last-uninvolved)-(sum[last] - sum[uninvolved]);
    //debug(needed);
   // debug(extra);
    if (needed <= extra)
    {
       // cout << "returning true" << endl;
        return true;
    }
    else
    {
       // cout << "returning false" << endl;

        return false;
    }
}
int main()
{
    fastinput;
    LL n, i, j, k, t, temp, tc;
    cin >> n;
    map<LL, LL> freq;
    for (i = 0; i < n; i++)
    {
        cin >> j;
        freq[j]++;
    }
    for (auto x : freq)
    {
        v.pb(x.second);
    }
    v.pb(0);
    sort(all(v));
    sz = v.size();
    sum.resize(sz);
    sum[0] = 0;
    sz--;
    for (i = 1; i <= sz; i++)
    {
        sum[i] = sum[i - 1] + v[i];
    }

    for (i = 1; i <= n; i++)
    {
        LL now = i;
        LL each_max = n / now;
        LL ans = 0;
        if (freq.size() < i)
        {
            ans = 0;
        }
        else
        {
            LL extra_got = sum[sz - now];
            LL lb = 1, ub = each_max;
            LL mid;
            ans=0;
            while (lb <= ub)
            {
                mid = (lb + ub) / 2;
                if (possible(mid, extra_got, now))
                {
                    ans = mid;
                   // debug(mid);
                    //cout<<"possible"<<endl;
                    lb = mid + 1;
                }
                else
                {
                    ub = mid - 1;
                }
            }
        }
       // debug(now);
        cout<<ans<<endl;
        //part;
        //part;
    }

    return 0;
}


Measured memory_bytes: 25908
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int D = sc.nextInt();
        
        int T_time = (A-1)/D+1;
        int A_time = (C-1)/B+1;

        
        if (T_time < A_time)
        	System.out.println("No");
        else
        	System.out.println("Yes");
        

	}
}


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

int main()
{
  int H,W;
  cin >> H >> W;
  int count = 0;
  vector<string> S(H);
  for(int i=0; i<H; i++)
  {
    cin >> S.at(i);
  }
    
  
  for(int i=0; i<H; i++)
  {
    for(int j=0; j<W; j++)
    {
      count = 0;
      if(S.at(i).at(j) == '.') //空きマスの場合
      {
          for(int k=max(0,j-1); k<=min(j+1,W-1); k++) //周りのマスを探す
          {
            for(int l=max(0,i-1); l<=min(i+1,H-1); l++)
            {
              if(S.at(l).at(k) == '#') count++;
            }
          }
        cout << count;
      }
      else
      {
        cout << '#';
      }
    }
    cout << endl;
  }
}     

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue;
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> &vec){ return (ll)vec.size(); }
ll sz(string &s){ return (ll)s.size(); }

ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }

int main(){
    ll a,b,q;
    cin >> a >> b >> q;
    vector<ll> s(a+2),t(b+2);
    rep(i,0,a) cin >> s[i+1];
    rep(i,0,b) cin >> t[i+1];
    s[0] = -LINF; s[a+1] = LINF;
    t[0] = -LINF; t[b+1] = LINF;

    rep(i,0,q){
        ll x;
        cin >> x;
        vector<P> vec;

        ll ok = 0,ng = a+1;
        while(abs(ok-ng) > 1){
            ll mid = (ok+ng)/2;
            
            if(s[mid] < x) ok = mid;
            else ng = mid;
        }
        vec.push_back(P(s[ok],0));
        vec.push_back(P(s[ok+1],0));

        ok = 0,ng = b+1;
        while(abs(ok-ng) > 1){
            ll mid = (ok+ng)/2;
            
            if(t[mid] < x) ok = mid;
            else ng = mid;
        }
        vec.push_back(P(t[ok],1));
        vec.push_back(P(t[ok+1],1));

        ll res = LINF;
        rep(j,0,sz(vec)){
            rep(k,0,sz(vec)){
                if(vec[j].sc == vec[k].sc) continue;
                res = min(res,(ll)abs(x-vec[j].fs)+abs(vec[j].fs-vec[k].fs)); 
            }
        }
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 4756
A,B = [int(i) for i in input().split()]

if A == B:
    print(A)
    exit()
p = B-A+1
q = p //2
if A%2 == 0:
    if p%2 == 0:
        if q%2 != 0:
            print(1)
        else:
            print(0)
    else:
        if q%2 != 0:
            print(B^1)
        else:
            print(B)
else:
    if p%2 == 0:
        if q%2 != 0:
            print(A^B)
        else:
            print(A^B^1)
    else:
        if q%2 != 0:
            print(A^1)
        else:
            print(A)


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

int main()
{
	string s;	cin >> s;
	for(int i = 0; i < 3; i ++)
	{
		if(s[i] == '1')	s[i] = '9';
		else if(s[i] == '9')	s[i] = '1';
	}
	cout << s << endl;
}

Measured memory_bytes: 256
# abc140_c.py
# https://atcoder.jp/contests/abc140/tasks/abc140_c

# C - Maximal Value /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 長さ Nの値の分からない整数列 Aがあります。
# 長さ N−1の整数列 Bが与えられます。このとき、Bi≥max(Ai,Ai+1)が成立することが分かっています。
# Aの要素の総和として考えられる値の最大値を求めてください。

# 制約
#     入力は全て整数
#     2≤N≤100
#     0≤Bi≤105

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N
# B1 B2 ... BN−1

# 出力
# Aの要素の総和として考えられる値の最大値を出力せよ。

# 入力例 1
# 3
# 2 5

# 出力例 1
# 9

# Aとして、例えば A = ( 2 , 1 , 5 )や、 A = ( −1 , −2 , −3 ), A = ( 2 , 2 , 5 ) 等が考えられます。
# これらのうち A の要素の総和が最大となるものは、 A = ( 2 , 2 , 5) です。

# 入力例 2
# 2
# 3

# 出力例 2
# 6

# 入力例 3
# 6
# 0 153 10 10 23

# 出力例 3
# 53


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    lst = [0] * N
    lst[0] = values[0]
    lst[N-1] = values[N-2]
    for n in range(1, N-1):
        lst[n] = min(values[n-1], values[n])

    return [sum(lst)]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3', '2 5']
        lines_export = [9]
    if pattern == 2:
        lines_input = ['2', '3']
        lines_export = [6]
    if pattern == 3:
        lines_input = ['6', '0 153 10 10 23']
        lines_export = [53]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9292
#include <bits/stdc++.h>
using namespace std;
#define IL inline
IL int read() {
	char ch = getchar(); int u = 0, f = 1;
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
	return u * f;
}

string  s;
int main() {
	cin >> s;
	if (s.size() == 3) reverse(s.begin(), s.end());
	cout << s;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc085/tasks/abc085_d
# Hダメージ以上与えたい
# ダメージが大きい方から与えたいが、武器が消えると困るときもある

# 投げつける選択は最後でいい。(ダメージも一番大きい)
# 通常攻撃で一番ダメージが大きいのを連発したいし、倒せるギリギリになったら
# 通常攻撃よりもダメージが大きい投げつけ攻撃を行いたい
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok


N, H = read_ints()
A, B = read_col(N, 2)
a_ma = max(A)
B.sort(reverse=True)
B_use = B[:bisect_left_reverse(B, a_ma)]

# 投げつけ攻撃だけで倒せる場合
cnt = 0
for b in B_use:
    H -= b
    cnt += 1
    if H <= 0:  # 投げつけ攻撃だけで倒せる場合
        print(cnt)
        exit()

# 投げつけ攻撃だけで倒せない場合
ans = len(B_use)
ans += int((H - 0.5) // a_ma) + 1
# ans += (H // a_ma) + 1

print(ans)


Measured memory_bytes: 11844
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int N; cin >> N;
    vector <int> H(N);
    for (int i = 0; i < N; i++){
        cin >> H.at(i);
    }
    int H_max = H.at(0);
    int ans = 0;
    for (int i = 0; i < N; i++){
        if (H.at(i) >= H_max){
            ans++;
            H_max = max(H_max,H.at(i));
        }
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
const double ep=1e-7;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double pi=acos(-1);
#define debug1 puts("?");
#define debug(x) cout<<"##"<<(x)<<endl;
#define mk make_pair
#define PII pair<int,int>
#define PIII pair<int,PII >
#define PIII1 pair<PII,int>
#define PIL pair<int,ll>
#define PLL pair<ll,ll>
#define eb emplace_back
#define fi first
#define se second
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define dep(i,a,b) for(register int i=(a);i>=(b);--i)
#define sd(x) scanf("%d",&(x))
#define slld(x) scanf("%lld",&(x))
#define sdd(x,y) scanf("%d%d",&(x),&(y))
#define sc(s) scanf("%s",(s))
#define pd(x) printf("%d\n",(x))
#define plld(x) printf("%lld\n",(x))
#define pdk(x) printf("%d ",(x))
#define plldk(x) printf("%lld ",(x))
#define pdd(x,y) printf("%d %d\n",(x),(y))
typedef long long ll;
int pre[maxn],be[maxn];
int n,m,cnt;
int Find(int x)
{
	return x==pre[x]?x:pre[x]=Find(pre[x]);
}
void mix(int x,int y)
{
	int fx=Find(x),fy=Find(y);
	pre[fx]=fy;
}
void solve()
{
	sdd(n,m);
	rep(i,1,n)pre[i]=i;
	rep(i,1,m)
	{
		int x,y;
		sdd(x,y);
		mix(x,y);
	}
	rep(i,1,n)be[Find(i)]++;
	rep(i,1,n)if(be[i])cnt++;
	pd(cnt-1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
//	sd(T);
	while(T--)solve();
} 

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

using namespace std;
typedef long long ll;

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

int main(){
  int N; cin >> N;
  vector<ll> A(N); 
  for(int i = 0; i < N; i++){
    cin >> A[i];}
  
  vector<ll> left(N,0); vector<ll> right(N,0);
  
  left[0] = A[0]; right[N-1] = A[N-1];
  
  for(int i = 1; i < N; i++){
    left[i] = gcd(A[i], left[i-1]);}
  
  for(int j = N - 2; j >= 0; j--){
    right[j] = gcd(A[j],right[j+1]);}
  
  ll max_cnt = 0;
  
  for(int i = 1; i < N - 1; i++){
    max_cnt = max(max_cnt, gcd(left[i-1],right[i+1]));}
                  
  cout << max(max_cnt,max(right[1],left[N-2])) << endl;
                  
                  return 0;}
    

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()
#define INF 9999999

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;



typedef int Number;
typedef vector<Number> Array;
typedef vector<Array> Matrix;

Matrix mul(const Matrix &a, const Matrix &b){
	Matrix res(a.size(), Array(b[0].size()));
	REP(i, a.size()){
		REP(j, b[0].size()){
			REP(k, a[0].size()){
				res[i][j] |= a[i][k] & b[k][j];
			}
		}
	}
	return res;
}

Matrix powMat(const Matrix &a, int b){
	if(!b){
		Matrix res(a.size(), Array(a[0].size(), 0));
		REP(i, a.size()) res[i][i] = 1;
		return res;
	}
	Matrix res = powMat(mul(a, a), b / 2);
	if(b&1) res = mul(res, a);
	return res;
}


int main(void){
	int N, M, Z;
	while(cin>>N>>M>>Z, N){
		vector<pair<int, int> > g;
		g.push_back(make_pair(0,0));
		REP(i,M){
			int s, d;
			cin >> s >> d;
			s--; d--;
			g.push_back(make_pair(s,d));
			g.push_back(make_pair(d,s));
		}
		Matrix a(g.size(), Array(g.size(), 0));
		REP(i, g.size()){
			REP(j, g.size()){
				if(!j) continue;
				if(i == j) continue;
				if(g[i].first == g[j].second && g[i].second != g[j].first){
					a[i][j] = 1;
				}
			}
		}
		Matrix b = powMat(a, Z);
		int f = 0;
		REP(i, g.size()){
			if(g[i].first == N-1){
				if(b[0][i]) f = 1;
			}
		}
		if(f) cout << "yes" << endl;
		else cout << "no" << endl;
	}
	return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
typedef unsigned long long ull;
typedef long long ll;
#define MAX 100005
using namespace std;
int dp[MAX];
int main() {
  int n;
  cin >> n;
  dp[0] = 0;
  for(int i=1;i<=n;i++) {
    dp[i] = MAX;
    int power=1;
    while(power<=i) {
      dp[i]=min(dp[i], dp[i-power]+1);
      power*=6;
    }
    power=1;
    while(power<=i) {
      dp[i]=min(dp[i], dp[i-power]+1);
      power*=9;
    }
  }
  cout << dp[n] << endl;
  return 0;
}

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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;
    string S;
    cin >> S;

    ll a = 0, b = 0, c = 0;
    REP(i, S.length())
    {
        string s = "No";
        if (S[i] == 'a')
        {
            if (A + B > a + b)
            {
                s = "Yes";
                a++;
            }
        }
        else if (S[i] == 'b')
        {
            if (A + B > a + b && B > b)
            {
                s = "Yes";
                b++;
            }
        }
        cout << s << endl;
    }
    return 0;
}

Measured memory_bytes: 896
import math
a,b,c = [int(x) for x in input().split()]
k = int(input())
a1,b1,c1 = math.log2(a),math.log2(b),math.log2(c)
k1,k2 = 0,0
# print(a1,b1,c1)
if b1<=a1:
    k1 = math.floor(a1-b1+1)
    b1 = b1+k1
if c1<=b1:
    k2 = math.floor(b1-c1+1)
if k1+k2<=k:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9324
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
const i64 MOD = 1e9+7;
const i64 INF = 1e18+7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


signed main(){
    int n;
    cin >> n;
    constexpr double per = (1000000 - 100) / 1000000.0;

    vector<int> x(n), y(n);
    for(int i = 0; i < n; ++i){
        cin >> x[i] >> y[i];
    }
    int y_min_idx = distance(y.begin(), min_element(y.begin(), y.end()));
    int y_max_idx = distance(y.begin(), max_element(y.begin(), y.end()));

    auto get_side = [&](int px, int py){
        if(x[y_max_idx] == x[y_min_idx]){
            return px > x[y_max_idx];
        }
        double d = 1.0 * (y[y_max_idx] - y[y_min_idx]) / (x[y_max_idx] - x[y_min_idx]);
        double sy = y[y_min_idx] - d * x[y_min_idx];

        double x_pos = (py - sy) / d;
        return x_pos < px;
    };
    // [0]: l  [1]: r
    vector<map<double, double>> v(2);
    for(int i = 0; i < n; ++i){
        if(y[i] == y[y_max_idx] || y[i] == y[y_min_idx]){
            if(v[1].find(y[i]) == v[1].end())
                v[1][y[i]] = x[i];
            else
                chmax(v[1][y[i]], 1.0 * x[i]);
            if(v[0].find(y[i]) == v[0].end())
                v[0][y[i]] = x[i];
            else
                chmin(v[0][y[i]], 1.0 * x[i]);
        }
        else if(get_side(x[i], y[i])){
            // r, max
            if(v[1].find(y[i]) == v[1].end())
                v[1][y[i]] = x[i];
            else
                chmax(v[1][y[i]], 1.0 * x[i]);
        }
        else{
            // l, min
            if(v[0].find(y[i]) == v[0].end())
                v[0][y[i]] = x[i];
            else
                chmin(v[0][y[i]], 1.0 * x[i]);
        }
    }
    int q;
    cin >> q;

    auto is_right = [&](double sx, double sy, double ex, double ey, double cx, double cy){
        if(sx == ex){
            return sx < cx;
        }
        double d = (ey - sy) / (ex - sx);
        double start_y = sy - d * sx;
        double x_pos = (cy - start_y) / d;
        return x_pos < cx;
    };

    auto f = [&](double px, double py){
        if(py >= y[y_max_idx] || py <= y[y_min_idx])
            return false;
        auto l_iter = prev(v[0].upper_bound(py - 1e-6));
        if(!is_right(l_iter->second, l_iter->first, next(l_iter)->second, next(l_iter)->first, px, py))
            return false;
        auto r_iter = prev(v[1].upper_bound(py - 1e-6));
        if(is_right(r_iter->second, r_iter->first, next(r_iter)->second, next(r_iter)->first, px, py))
            return false;
        return true;
    };

    for(int i = 0; i < q; ++i){
        double px, py;
        cin >> px >> py;
        px *= per, py *= per;
        cout << f(px, py) << endl;
    }
}



Measured memory_bytes: 4700