akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;

class Program
{
	static void Main(string[] args)
	{
		string[] input = Console.ReadLine().Split(' ');
		int n = int.Parse(input[0]);
		int m = int.Parse(input[1]);
		int[] a = new int[m];
		int[] b = new int[m];
		List<int>[] ikerutoko = new List<int>[n];
		for(int i = 0; i < n; i++) ikerutoko[i] = new List<int>();
		for(int i = 0; i < m; i++)
		{
			input = Console.ReadLine().Split(' ');
			a[i] = int.Parse(input[0]);
			b[i] = int.Parse(input[1]);
			ikerutoko[a[i]-1].Add(b[i]);
			ikerutoko[b[i]-1].Add(a[i]);
		}

		int[] michishirube = new int[n];
		michishirube[0] = -1;
		Queue<int> que = new Queue<int>();
		que.Enqueue(1);
		while(que.Count > 0)
		{
			int pointNow = que.Dequeue();
			foreach(int pointNext in ikerutoko[pointNow-1])
			{
				que.Enqueue(pointNext);
				if(michishirube[pointNext-1]==0) michishirube[pointNext-1] = pointNow;
			}
			ikerutoko[pointNow-1].Clear();
		}
		Console.WriteLine("Yes");
		for(int i = 1; i<n; i++)
		{
			Console.WriteLine(michishirube[i]);
		}
	}

}



Measured memory_bytes: 58516
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    int x, y, z;
    int k;
    long[] a, b, c;

    void run() {
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = sc.nextInt();
        z = sc.nextInt();
        k = sc.nextInt();
        a = new long[x];
        b = new long[y];
        c = new long[z];

        for (int i = 0; i < x; i++) {
            a[i] = sc.nextLong();
        }
        for (int i = 0; i < y; i++) {
            b[i] = sc.nextLong();
        }
        for (int i = 0; i < z; i++) {
            c[i] = sc.nextLong();
        }

        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);

        PriorityQueue<V> q = new PriorityQueue<>();
        q.add(new V(a[x - 1] + b[y - 1] + c[z - 1], x - 1, y - 1, z - 1));
        HashSet<Long> used = new HashSet<>();
        used.add(ints2long(x - 1, y - 1, z - 1));
        for (;k > 0; k--) {
            V cur = q.remove();
            System.out.println(cur.cost);
            if (cur.a - 1 >= 0 && !used.contains(ints2long(cur.a - 1, cur.b, cur.c))) {
                q.add(new V(a[cur.a - 1] + b[cur.b] + c[cur.c], cur.a - 1, cur.b, cur.c));
                used.add(ints2long(cur.a - 1, cur.b, cur.c));
            }

            if (cur.b - 1 >= 0 && !used.contains(ints2long(cur.a, cur.b - 1, cur.c))) {
                q.add(new V(a[cur.a] + b[cur.b - 1] + c[cur.c], cur.a, cur.b - 1, cur.c));
                used.add(ints2long(cur.a, cur.b - 1, cur.c));
            }

            if (cur.c - 1 >= 0 && !used.contains(ints2long(cur.a, cur.b, cur.c - 1))) {
                q.add(new V(a[cur.a] + b[cur.b] + c[cur.c - 1], cur.a, cur.b, cur.c - 1));
                used.add(ints2long(cur.a, cur.b, cur.c - 1));
            }
        }
    }

    long ints2long(long x, long y, long z) {
        return x * 10000 * 10000 + y * 10000 + z;
    }

    class V implements Comparable<V> {
        long cost;
        int a, b, c;
        V(long cost, int a, int b, int c) {
            this.cost = cost;
            this.a = a;
            this.b = b;
            this.c = c;
        }

        @Override
        public int compareTo(V o) {
            return (o.cost - cost) > 0 ? 1: -1;
        }
    }

    void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

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


Measured memory_bytes: 30024
//be naame khodaa
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
#define F first
#define pb push_back
#define sz(x) ((int)(x).size())

inline int in(){ int x, y; y = scanf("%d", &x); return x; }

const int N = 1000*100 + 100;

int a[N], b[N], c[N], d[N], e[N], f[N], g[N], h[N], A[N], B[N], C[N], D[N]; 

int n;

void rev(int* a, int* b) { 
    fill(b, b + n, 0);
    for(int i = 0; i < n; i++) 
        b[a[i]] = i; 
}

void mul(int* a, int* b, int* c) {
    fill(c, c + n, 0); 
    for(int i = 0; i < n; i++) 
        c[i] = a[b[i]]; 
}


void pr(int *a) { 
    for(int i = 0; i < n; i++)
        cout << a[i]+1 << ' ';
    cout << endl;
}
void bpow(int* a, int b, int* c) {
    int* tmp = new int[n]; 
    int* tmp2 = new int[n]; 
    int* corig = c; 

    for(int i = 0; i < n; i++) 
        c[i] = i;

    copy(a, a + n, tmp); 

    for(; b ; b/= 2) { 
        if( b % 2 == 1 ) { 
            mul( c , tmp , tmp2 ); 
            swap( c , tmp2 ); 
        }
        mul( tmp , tmp , tmp2 ); 
        swap( tmp , tmp2 ); 
    }

    copy( c , c + n , tmp ); 
    copy( tmp, tmp + n, corig ); 
}


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

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

    for(int j = 0; j < n; j++) {
        cin >> b[j];
        b[j]--; 
    }

    if( k < 6 ) { 
        for(int t = 3; t <= k; t++) { 
            rev(a, d); 
            mul(b, d, c); 
            swap(a, b); 
            swap(b, c); 
        }
        if( k == 1 ) 
            swap(a, b);
        for(int i = 0; i < n; i++)
            cout << 1+b[i] << ' '; 
        cout << endl;
        return 0;
    } else { 
        rev(a, c);
        rev(b, d); 

        mul(b, c, e);
        mul(e, d, f); 
        mul(f, a, A);

        mul(a, d, e);
        mul(e, c, f);
        mul(f, b, B); 

        int st = k/6;


        bpow(A, st, e); 
        bpow(B, st-1, f); 

        mul(e, f, g); 
        mul(g, a, h); 
        mul(h, d, C);

        mul(e, b, g);
        mul(g, f, h);
        mul(h, a, g);
        mul(g, d, D);

        for(int x = 0; x < k%6; x++) { 
            rev( C , e ); 
            mul( D , e , f ); 
            swap( C , D );
            swap( D , f ); 
        }

        for(int i = 0; i < n; i++)
            cout << C[i]+1 << ' ';
        cout << endl;
    }
    return 0;
}


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

int main(){
    int n,ans=0; cin>>n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<n; i++) {
        if(a[a[i]-1] == i+1) ans++;
    }
    cout<<ans/2;
}

Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

double prim(int n, vector< vector<double> > &G){
  double ans = 0.0;
  priority_queue< pair<double,int> > wait;
  bool connected[n];
  fill(connected,connected+n,false);
  wait.push(make_pair(0.0,0));
  while(!wait.empty()){
    double cost = -wait.top().first;
    int v = wait.top().second;
    wait.pop();
    if(connected[v]) continue;
    ans += cost;
    connected[v] = true;
    for(int i = 0; i < n; ++i){
      if(!connected[i]){
        wait.push(make_pair(-G[v][i],i));
      }
    }
  }
  return ans;
}

int main(){
  int n;
  while(cin >> n, n){
    double x[n], y[n], z[n], r[n];
    for(int i = 0; i < n; ++i){
      cin >> x[i] >> y[i] >> z[i] >> r[i];
    }
    vector< vector<double> > dist(n,vector<double>(n,0));
    
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        dist[i][j] = max(0.0,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))-r[i]-r[j]);
      }
    }
    printf("%.3f\n",prim(n,dist));
  }
  return 0;
}

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const int INF = 1e9+5;
int n, m, l, a, b, c, d[305][305];
inline void chmin(int &a, int b){if(a > b) a = b;}
void wf(){rep(k,n) rep(i,n) rep(j,n) chmin(d[i][j], d[i][k] + d[k][j]);}
int main(){
	scanf("%d%d%d", &n, &m, &l); n++;
	fill(d[0], d[n], INF);
	rep(i,m){
		scanf("%d%d%d", &a, &b, &c);
		d[a][b] = d[b][a] = c;
	}
	wf();
	rep(i,n) rep(j,n) d[i][j] = d[i][j] <= l ? 1 : INF;
	wf();
	scanf("%d", &c);
	rep(i,c){
		scanf("%d%d", &a, &b);
		printf("%d\n", d[a][b] == INF ? -1 : d[a][b] - 1);
	}
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define fori(n)			for(int i = 0; i < n; ++i)
#define nl          '\n'
using ll = long long; using ld = long double; using pii = pair<int,int>; using pll = pair<ll,ll>;
using VI = vector<int>; using VB = vector<bool>; using VL = vector<ll>;
#define DEBUG 0
#if     DEBUG
#define trace(var)  {cerr << "Line " << __LINE__ << ": " << #var << "=" << var << nl;}
#else
#define trace(var)	{}
#endif

static int oft[][2] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1}
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// Emily <3	
	int h, w;
	cin >> h >> w;
	vector<vector<char>> grid(h, vector<char>(w));
	
	queue<pii> wk;
	fori(h)
		for (int j = 0; j < w; ++j){
			cin >> grid[i][j];
			if (grid[i][j] == '#') {
				wk.push(pii(i,j));
			}
		}
	trace(wk.size());
	//simulate
	int steps = -1;
	while (!wk.empty()) {
		steps++;
		trace(steps);
		queue<pii> wk2;
		while (!wk.empty()) {
			pii cur = wk.front();
			wk.pop();
			//add neighbors
			fori(4) {
				int x = cur.first + oft[i][0];
				int y = cur.second + oft[i][1];
				trace(x);trace(y);
				if (x < 0 || x >= h) continue;
			  if (y < 0 || y >= w) continue;
				if (grid[x][y] == '#') continue;
				grid[x][y] = '#';
				wk2.push(pii(x,y));	
			}
		}
		wk.swap(wk2);
	}

	cout << steps << nl;

	return 0;
}



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

string a;

int n;
int t,x,sblyf;
char sb;

int main(){
	std::ios::sync_with_stdio(false);
	cin>>a;
	cin>>n;
	while(n--){
		cin>>t;
		if(t == 1) sblyf++;
		else{
			cin>>x>>sb;
			if(sblyf % 2 == 1) x = (x+1) % 2;
			if(x == 1){
				a.insert(a.begin(),sb);
			}
			else{
				a.push_back(sb);
			}
		}
	}
	if(sblyf % 2 == 1) reverse(a.begin(),a.end());
	cout<<a<<endl;
	return 0;
}

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

using namespace std;

int main()
{
    int n;
    int cont = 0;
    int cont2 = 0;
    cin>>n;

    for (int i = 0 ; i < n ; i++){
        long in;
        cin>>in;
        if (in % 4 == 0)cont++;
        else if (in % 2 == 0)cont2++;
    }
    n-= cont;
    if (cont2) n-= (cont2-1);

    if (cont >= n-1)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


    return 0;
}


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

template <int MOD_>  struct modnum {
private:
	using lint = long long;
	lint v;
	static int modinv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - lint(modinv(m, a)) * lint(m) / a);
	}
public:
	static constexpr int MOD = MOD_;
	modnum() : v(0) {}
	modnum(lint v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream &operator<<(std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream &operator>>(std::istream& in, modnum& n) { lint v_; in >> v_; n = modnum(v_); return in; }
	friend bool operator==(const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator!=(const modnum& a, const modnum& b) { return a.v != b.v; }
	modnum inv() const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	modnum operator-() const { return neg(); }
	modnum operator+() const { return modnum(*this); }
	modnum& operator+=(const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator-=(const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator*=(const modnum& o) {
		v = int(lint(v) * lint(o.v) % MOD);
		return *this;
	}
	modnum& operator/=(const modnum& o) { return *this *= o.inv(); }
	friend modnum operator+(const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator-(const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator*(const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator/(const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<int(1e9)+7>;

template <typename T> T pow(T a, int b) {
	assert(b >= 0);
	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

int main() {
    cout.tie(nullptr)->sync_with_stdio(false);
    using ll = long long;
    ll N; cin >> N;
    cout << pow(num(10), N) + pow(num(8), N) - 2 * pow(num(9), N) << '\n';    
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 131072
#define ll long long
#define dmp make_pair
#define dpb push_back
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);
const int inf = 2147483647;

int n, dat[2*MAX];
void init(int m){
	n = 1;
	while(n < m)n *= 2;
	for(int i = 0;i < 2*n;i++)dat[i] = 0;
}

void change(int x, int y){
	x += n-1;
	dat[x] += y;
	while(x > 0){
		x = (x-1)/2;
		dat[x] += y;
	}
}

int query(int a, int b, int k, int l, int r){
	if(b <= l || r <= a)return 0;
	if(a <= l && r <= b)return dat[k];
	int vl = query(a, b, 2*k+1, l, (l+r)/2);
	int vr = query(a, b, 2*k+2, (l+r)/2, r);
	return vl+vr;
}

int main(){
	int m, q, c, x, y;
	scanf("%d%d", &m, &q);
	init(m);
	while(q--){
		scanf("%d%d%d", &c, &x, &y);
		if(!c)change(x-1, y);
		else printf("%d\n", query(x-1, y, 0, 0, n));
	}
	//for(int i = 0;i < n;i++)printf("%d ", dat[i]);
	return 0;
}

Measured memory_bytes: 4216
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
//#define INF 1e18
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;

map<P,P> m0;
ll c00,c01,c10;

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

//xのn乗
ll mod_pow(ll x, ll n){
  if(n==0) return 1;
  ll res = mod_pow(x*x%MOD,n/2);
  if(n & 1) res = res*x%MOD;
  return res;
}

int n;

int main(){
  cin >> n;
  rep(i,0,n){
    ll a,b;
    cin >> a >> b;
    if((a>0 && b>0) || (a<0 && b<0)){
      a = abs(a);
      b = abs(b);
      m0[P(a/gcd(a,b),b/gcd(a,b))].first++;
      //cout << a/gcd(a,b) << b/gcd(a,b) << endl;
    }else if((a>0 && b<0) || (a<0 && b>0)){
      a = abs(a);
      b = abs(b);
      swap(a,b);
      m0[P(a/gcd(a,b),b/gcd(a,b))].second++;
      //cout << "!" <<  a/gcd(a,b) << b/gcd(a,b) << endl;
    }else{ //0を含む
      if(a==0 && b==0){
        c00++;
      }else if(a==0){
        c01++;
      }else{
        c10++;
      }
    }
  }
  ll ans=1; //あとで選びなしの場合の-1

  for(auto p : m0){
    ll s = p.second.first;
    ll t = p.second.second;
    ll u = mod_pow(2LL,s) + mod_pow(2LL,t);
    u--;
    ans *= u;
    ans %= MOD;
  }
  ll u = mod_pow(2LL,c01) + mod_pow(2LL,c10);
  u--;
  ans *= u;
  ans %= MOD;

  ans += c00;
  ans--;

  ans %= MOD;
  if(ans<0) ans += MOD;
  cout << ans << endl;
    

  return 0;
}


Measured memory_bytes: 19224
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define ALL(a) (a).begin(),(a).end()
template<typename T>
ostream& operator <<(ostream &s, const vector<T> A){
    for(int i=0, n=A.size(); i<n; i++){
        if(i) s << " ";
        s << A[i];
    }
    return s;
}

int main(){
    int N;
    cin>>N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin>>A[i];
    sort(ALL(A));
    long long cnt = 0;
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            cnt += --lower_bound(A.begin()+j+1, A.end(), A[i]+A[j]) - (A.begin()+j+1) + 1;
        }
    }
    cout << cnt << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define cst() int __t;scanf("%d",&__t);while(__t--)
#define rep(i,s,t) for(int i=s;i<t;++i)
#define repb(i,s,t) for(int i=s;i<=t;++i)
#define lepb(i,s,t) for(int i=s;i>=t;--i)
#define mst(a,b) memset(a,b,sizeof(a))
#define mcpy(des,sor) memcpy(des,sor,sizeof(sor))
#define pt(x) cout<<#x<<"="<<x<<" "
#define ptl(x) cout<<#x<<"="<<x<<endl
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
template<class T> void Max(T &a,T b){a<b?a=b:0;}
template<class T> void Min(T &a,T b){a>b?a=b:0;}
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const ll mod = 998244353;
#define maxn 10006

int main()
{
//	freopen("1.txt","r",stdin);
    int n,a,r1,r2,r4;
    cin>>n;
    r1=r2=r4=0;
    repb(i,1,n)
    {
        cin>>a;
        if(a%4==0)++r4;
        else if(a%2==0)++r2;
        else ++r1;
    }
    if(r1)
    {
        if(r2)
        {
            if(r4)
            {
                if(r4+1>=r1+1)printf("Yes\n");
                else printf("No\n");
            }
            else printf("No\n");
        }
        else
        {
            if(r4)
            {
                if(r4+1>=r1)printf("Yes\n");
                else printf("No\n");
            }
            else printf("No\n");
        }
    }
    else printf("Yes\n");
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <array>
#include <list>
#include <unordered_set>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int n, x, ans;
    cin >> n >> x;
    vector<int> v;
    v.resize(n);
    ans = 0;
    for (int i=0; i<n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i=0; i<n; ++i){
        if(i != n-1 && v[i] <= x){
            ans++;
            x -= v[i];
        }
        if(i == n-1 && v[i] == x){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
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;}

int main(){
	ll n;
	cin >> n;
	vector<ll> L(n);
	REP(i,n) cin >> L[i];
	
	int ans=0;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			for(int k=j+1; k<n; k++){
				if(L[i]==L[j] || L[j]==L[k] || L[k]==L[i]) continue;
				if(L[i] < L[j]+L[k] && L[j] < L[k]+L[i] && L[k] < L[j]+L[i] ){
					ans++;
				}
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
double angle(double a) {
    return atan(a)*180/M_PI;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    double a, b, x;
    cin >> a >> b >> x;
    if (2*x == a*a*b) printf("%.8lf\n", angle(b/a));
    else if (2*x > a*a*b) printf("%.8lf\n", angle(2*(b-x/a/a)/a));
    else printf("%.8lf\n", angle(a*b*b/2/x));
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
	string S, T;
	cin >> S >> T;
	deque<char> s, t;
	for(auto& c : S) s.emplace_back(c);
	for(auto& c : T) t.emplace_back(c);

	bool can = false;
	rep(i, S.size()+1){
		can |= (s == t);
		char c = s.back(); s.pop_back();
		s.emplace_front(c);
	}

	if(can) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>
using namespace std;
#define All(v) (v).begin(),(v).end()
const long long mod = 1000000007;
const long long inf = mod*mod;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);

signed main(){
    long long n;
    cin>>n;
    vector<long long> v;
    for(long long i=1;i*i<n+1;i++){
        if(n%i==0){
            v.push_back(i);
            v.push_back(n/i);
        }
    }
    int res=1<<30;
    int l = v.size();
    string a,b;
    for(int i=0;i<l;i+=2){
        a=to_string(v[i]);
        b=to_string(v[i+1]);
        int c = max(a.size(),b.size());
        res=min(res,c);
    }
    cout<<res<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define pb push_back
#define f first
#define s second
#define pi 3.141592653589793238
using namespace std;

ll gcd( ll a, ll b )
{
	if(b==0)
	{
		return a;
	}
	else
	{
		return gcd( b, a%b );
	}
}
ll lcm (ll a, ll b)
{
	return (a*b)/gcd(a,b);
}

ll power(ll a, ll b)	//a is base, b is exponent
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	if(b%2 == 1)
		return (power(a,b-1)*a)%mod;
	ll q = power(a,b/2);
	return (q*q)%mod;
}

int main()
{
	std::ios::sync_with_stdio(false);
	string s;
	cin >> s;
	if(s=="keyence") return cout << "YES\n",0;
	for(int i =0;i<s.size();i++)
	{
		string a;
		for(int j = i;j<s.size();j++)
		{	
			a = "";
			for(int k = 0;k<i;k++) a+=s[k];
			for(int k = j+1;k<s.size();k++) a+=s[k];
			if(a=="keyence") return cout << "YES\n",0;
		}
	}	
	cout << "NO\n";



	return 0;
}


//Hello, this is a snippet.


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bug1( x ) {cerr << (#x) <<"="<< x << endl;}
#define bug2( x , y ) {cerr << (#x) <<"="<< (x) << "    " << (#y) << "="<< (y) << endl;}
#define bug3( x , y , z ) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << endl;}
#define bug4( x , y , z , w) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << endl;}
#define bug5( x , y , z , w ,p) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << endl;}
#define bug6( x , y , z , w ,p , q) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << "    " << (#q) <<"="<< q << endl;}
#define bugn( x , n ) {cerr << (#x) <<":";for(int i=0;i<n;i++)cerr << x[i] <<"  "; cerr << endl;}
#define bugnm( x , n , m ) {cerr << (#x)<<endl;for(int i=0;i<n;i++){cerr << "Row #" << i<< ":";for(int j=0;j<m;j++)cerr << x[i][j] << "   ";cerr << endl;}}
typedef long long ll;
typedef long double ld;
using namespace std;


struct box{
	int u,v,w;
	bool operator <(const box other){
		return w < other.w;
	}
};
int32_t main(){
	IOS
	int n;cin>>n;
	int d[n+1][n+1];
	vector<box>a;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin >> d[i][j];
			if( i < j ){
				a.push_back({i,j,d[i][j]});
			}
		}
	}
	int dis[n+1][n+1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=1e17;
		}
		dis[i][i]=0;
	}
	sort(a.begin(),a.end());
	int sum = 0;
	for(auto [u,v,w]:a){
		//bug3(u,v,w);
		if( dis[u][v] < w ){
			cout << -1 << endl; return 0;
		}else if( dis[u][v] == w ){
			continue;
		}
		sum += w;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j] = min( dis[i][j] , dis[i][u] + w + dis[v][j] );
				dis[i][j] = min( dis[i][j] , dis[i][v] + w + dis[u][j] );
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if( d[i][j] != dis[i][j] ){
				cout << -1 << endl; return 0;
			}
		}
	}
	cout << sum << endl;
}
/*
 * long long or int?
 * index out of bound?
 * Tested on own test case?corner?
 * Make more general solution.
 * Read Read Read Read ....
 */


Measured memory_bytes: 5944
/// Rustで競技プログラミングの入力をスッキリ記述するマクロ
///
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

macro_rules! eprint(
    ($($arg:tt)*) => {
        if cfg!(feature = "debug") {
            use std::io::Write;
            let r = write!(&mut ::std::io::stderr(), $($arg)*);
            r.expect("failed printing to stderr");
        }
    }
);

macro_rules! eprintln(
    ($($arg:tt)*) => {
        if cfg!(feature = "debug") {
            use std::io::Write;
            let r = writeln!(&mut ::std::io::stderr(), $($arg)*);
            r.expect("failed printing to stderr");
        }
    }
);

macro_rules! dbg {
    ($val:expr) => {
        // Use of `match` here is intentional because it affects the lifetimes
        // of temporaries - https://stackoverflow.com/a/48732525/1063961
        if cfg!(feature = "debug") {
            match $val {
                tmp => {
                    eprintln!(
                        "[{}:{}] {} = {:#?}",
                        file!(),
                        line!(),
                        stringify!($val),
                        &tmp
                    );
                    tmp
                }
            }
        } else {
            $val
        }
    };
}

fn main() {
    input! {
        s: chars,
    }
    let mut answer = 0i64;
    let mut left_point = 0usize;
    for (i, &c) in s.iter().enumerate() {
        if c == 'W' {
            answer += i as i64 - left_point as i64;
            left_point += 1;
        }
    }
    println!("{}", answer);
}


Measured memory_bytes: 4352
x = int(input())
flag = 1

while True:
    if x == 2:
        break
    for i in range(3, x):
    #print("i is " + str(i))
        if x % i == 0:
            flag = 0
            break
    if flag == 1:
        break
    else:
        flag=1
        x += 1
print(x)

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

int main()
{
    queue<long long int>q;
    for(int i=1;i<10;i++)
        q.push(i);

    int k;
    cin>>k;
    while(--k)
    {
        long long int x=q.front();
//        cout<<x<<endl;
        q.pop();
        if(x%10!=0) q.push(10*x+x%10-1);
        q.push(10*x+x%10);
        if(x%10!=9) q.push(10*x+x%10+1);
    }
    cout<<q.front();
}


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

int C[550], S[550], F[550];
int tim(int i, int sec, int n){
    if(i==n) return sec;
    else if(sec<=S[i]) return tim(i+1, S[i]+C[i], n);
    else{
        int T=(sec+F[i]-1)/F[i];
        return tim(i+1, T*F[i]+C[i], n);
    }
}
int main() {
	int N; cin >> N;
	for(int i=1; i<N; ++i) cin >> C[i] >> S[i] >> F[i];
	for(int i=1; i<=N; ++i) cout << tim(i, 0, N) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	//freopen("input.txt", "r", stdin);
	int k;
	cin >> k;
	if(k%2 == 0 || k%5 == 0){
		cout << -1 << '\n';
		return 0;
	}

	long long n = 7, i;
	for (i = 1; i <= k; ++i) {
		if(n%k == 0)
			break;
		n = (n * 10 + 7) % k;
	}

	cout << i << '\n';
	return 0;
}

Measured memory_bytes: 3612
import java.util.*;

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

		// 初めを"0"と仮定して合わない数を探す
		int correct = 0;
		for (int i = 0; i < C.length; i++) {
			char compare = i % 2 == 0 ? '0' : '1';
			if (C[i] == compare) {
				correct++;
			}
		}
		int ans = Math.min(correct, C.length - correct);
		System.out.println(ans);
	}
}


Measured memory_bytes: 39184
N = int(input())
H = list(map(int, input().split()))
#足場Nまで移動するための最小コスト
dp = [None for _ in range(N)]
dp[0] = 0
for i in range(N-1):
    if dp[i+1] == None:
        dp[i+1] = dp[i]+abs(H[i+1]-H[i])
    else:
        dp[i+1] = min(dp[i+1], dp[i]+abs(H[i+1]-H[i]))
    if i+2 >= N:
        continue
    elif dp[i+2] == None:
        dp[i+2] = dp[i]+abs(H[i+2]-H[i])

print(dp[N-1])

Measured memory_bytes: 13928
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define INF 1000000000 //1e9
#define int ll

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

    int N, K;
    cin>>N>>K;

    if (K == 0) {
        cout << N * N << endl;
        return 0;
    }

    ll ans = 0;
    FOR(b, K+1, N+1) {
        int p = N / b;
        int r = N % b;
        ans += (b - K) * p;
        ans += max(0LL, r - K + 1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OJcsharp
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int[] saihin = new int[str.Length];
            string saidai = "a";
            for (int n = 0; n < str.Length; n++)
            {
                saihin[n] = 0;
                if (saidai.Length < str[n].Length)
                {
                    saidai = str[n];
                }
            }
            for (int n = 0; n < str.Length-1; n++)
            {
                for (int m = n + 1; m < str.Length; m++)
                {
                    if (str[n] == str[m])
                    {
                        saihin[n]++;
                    }
                }
            }
            int s = 0;
            for (int n = 0; n < str.Length; n++)
            {
                if (saihin[n] > s)
                {
                    s = saihin[n];
                }
            }
            for(int n=0;;n++)
                if (saihin[n] == s)
                {
                    Console.Write(str[n]+" ");
                    break;
                }
            Console.WriteLine(saidai);
        }
    }
}

Measured memory_bytes: 5260
#include <cstdio>
#include <map>
#include <tuple>
#include <vector>

using namespace std;

int N;
map<tuple<long long, long long, long long>, int> group_size;
#define L 2154
#define SQRTL 46
bool is_prime[L + 1];
vector<int> primes;

int main() {
  for(int i = 2; i <= L; ++i) {
    is_prime[i] = true;
  }
  for(int i = 2; i <= SQRTL; ++i) {
    if(is_prime[i]) {
      for(int j = 2; j <= L / i; ++j) is_prime[j * i] = false;
    }
  }
  for(int i = 2; i <= L; ++i) {
    if(is_prime[i]) primes.push_back(i);
  }
  scanf("%d", &N);
  for(int i = 0; i < N; ++i) {
    long long s; scanf("%lld", &s);
    long long mod3_1 = 1, mod3_2 = 1;
    for(int p : primes) {
      int n = 0;
      while(s % p == 0) { ++n; s /= p; }
      n %= 3;
      if(n == 1) mod3_1 *= p;
      else if(n == 2) mod3_2 *= p;
      if(s == 1) break;
    }
    ++group_size[make_tuple(mod3_1, mod3_2, s)];
  }
  auto group_size2 = group_size;
  for(auto kv : group_size) {
    auto key = kv.first; auto val = kv.second;
    long long mod3_1 = get<0>(key), mod3_2 = get<1>(key), rest = get<2>(key);
    if(mod3_1 == 1 && mod3_2 == 1 && rest == 1) { group_size2[key] = 1; continue; }
    if(!group_size2.count(key)) continue;
    if(rest >= 100000) continue;
    auto it = group_size2.find(make_tuple(mod3_2, mod3_1, rest * rest));
    if(it == group_size2.end()) continue;
    if(it->second < val) group_size2.erase(it); else group_size2.erase(key);
  }
  int res = 0; for(auto kv : group_size2) res += kv.second;
  printf("%d\n", res);
  return 0;
}


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

int main() {
	int a[4];
	int b[4];

	while (cin >> a[0]) {
		int hit = 0, brow = 0;

		for (int i = 1; i < 4; i++) {
			cin >> a[i];
		}
		for (int j = 0; j < 4; j++) {
			cin >> b[j];
		}

		for (int k = 0; k < 4; k++) {
			for (int l = 0; l < 4; l++) {
				if (a[k] == b[l]) {
					if (k == l) {
						hit++;
					}
					else {
						brow++;
					}
				}
			}
		}

		cout << hit << " " << brow << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
N, K = gets.split(' ').map(&:to_i)
p_sum = 0
1.upto(N) do |n|
  i = 0
  while n * (2 ** i) < K do
    i += 1
  end
  p_sum += (1.0 / N) * (0.5 ** i)  
end
puts p_sum

Measured memory_bytes: 1788
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	var N int
	fmt.Scan(&N)

	if ok := sc.Scan(); !ok {
		return
	}
	t := sc.Text()

	inputs := strings.Split(t, " ")

	output := 0
	maxHeight := 0
	for _, i := range inputs {
		height, err := strconv.Atoi(i)
		if err != nil {
			return
		}

		if height >= maxHeight {
			output += 1
			maxHeight = height
		}
	}

	fmt.Println(output)
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void){
    int N,i,j,pareCount = 0,tmp;
    scanf("%d",&N);
    int a[N],b[N],c[N],d[N];
    for(i = 0;i < N;i++){
        scanf("%d %d",&a[i],&b[i]);
    }
    for(i = 0;i < N;i++){
        scanf("%d %d",&c[i],&d[i]);
    }

    for(i = 0;i < N - 1;i++){
        for(j = 0;j < N - i - 1;j++){
            if(a[j] > a[j + 1]){
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                tmp = b[j];
                b[j] = b[j + 1];
                b[j + 1] = tmp;
            }
            if(c[j] > c[j + 1]){
                tmp = c[j];
                c[j] = c[j + 1];
                c[j + 1] = tmp;
                tmp = d[j];
                d[j] = d[j + 1];
                d[j + 1] = tmp;
            }
        }
    }

    for(i = 0;i < N;i++){
        tmp = -1;
        for(j = 0;a[j] < c[i];j++){
            if(b[j]<d[i] && b[j]>(tmp==-1 ? -1 : b[tmp])) tmp=j;
        }
        if(tmp >= 0){
            pareCount++;
            b[tmp] = 200;
        }
    }

    printf("%d\n",pareCount);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define int3(x, y, z) int x, y, z; scanf("%lld %lld %lld", &x, &y, &z);
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    int3(n, w, h);
    w += w; h += h;
    vi wid(w+w+2, 0), hei(h+h+2, 0);
    rep(i, n) {
        int3(a, b, c);
        a += a; b += b; c += c;
        wid[ ( ( a-c > 0) ? a-c : 0 )] += 1;
        wid[ ( ( a+c+1 < w+1 ) ? a+c+1 : w+1 )] += -1;
        hei[ ( ( b-c > 0) ? b-c : 0 )] += 1;
        hei[ ( ( b+c+1 < h+1 ) ? b+c+1 : h+1 )] += -1;
/*
cout <<  ( ( a-c > 0) ? a-c : 0 ) << endl;
cout <<  ( ( a+c+1 < w+1 ) ? a+c+1 : w+1 ) << endl;
cout <<  ( ( b-c > 0) ? b-c : 0 ) << endl; 
cout <<  ( ( b+c+1 < h+1 ) ? b+c+1 : h+1 ) << endl;
*/
    }
/*
    rep(i, w+1) {cout << wid[i] << " "; } cout << endl;
    rep(i, h+1) {cout << hei[i] << " "; } cout << endl;
  */  

    bool ans = true;
    rep(i, w+1) {
        wid[i+1] += wid[i];
        ans &= wid[i] > 0;
    }
    if ( ans ) {
        cout << "Yes" << endl;
        return 0;
    }
    ans = true;
    rep(i, h+1) {
        hei[i+1] += hei[i];
        ans &= hei[i] > 0;
    }
/*
    rep(i, w+1) {cout << wid[i] << " "; } cout << endl;
    rep(i, h+1) {cout << hei[i] << " "; } cout << endl;
 */  


    cout << ((ans)?"Yes":"No") << endl;
    return 0;
}

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

int main(){
    int n,t;
    cin>>n>>t;
    vector<int>c;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        
        if(b<=t){
            c.push_back(a);
        }else c.push_back(10000);

    }
    sort(c.begin(),c.end());
    if(c[0]==10000)cout<<"TLE"<<endl;
    else cout<<c[0]<<endl;

}

Measured memory_bytes: 256
N, K, L = [int(_) for _ in input().split()]


class UFT():
    def __init__(self):
        self.par = [i for i in range(N + 1)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get(
        (Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)])
               for i in range(1, N + 1)))


Measured memory_bytes: 63248
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]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


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


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N = int(input())
    ans = []
    for i in range(N):
        S, P = input().split()
        ans.append((S, -int(P), i + 1))

    ans.sort()
    for t in ans:
        print(t[2])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3948
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi vector<ll>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<ll,ll>
#define vv vector
//#define endl '\n'
using namespace std;
const int MAXN = 700 + 5;

vi g[MAXN];
bool adj[MAXN][MAXN];
int n,m;

vv<ii> all;
bool vis[MAXN];
int color[MAXN];
bool bad = 0;
int cnt[2];
void dfs(int node,int c=0){
	vis[node] = 1;
	color[node] = c;
	cnt[c]++;
	FOR(i,n){
		if(node == i)continue;
		if(adj[node][i]){
			
			if(vis[i]){
				if(color[i] == c){
					//cout << node+1 << " " << i+1 << endl;
					bad = 1;
				}
			}else{
				dfs(i,1-c);
			}
		}
	}
}

int nc2(int n){
	return (n*(n-1))/2;
}
int dp[MAXN][MAXN];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	FOR(i,MAXN)FOR(j,MAXN)adj[i][j] = 1;
	cin >> n >> m;    
	FOR(i,m){
		int a,b;
		cin >> a >> b;
		a--;b--;
		adj[a][b] = 0;
		adj[b][a] = 0;
	}

	FOR(i,n){
		if(vis[i])continue;
		cnt[0] = cnt[1] = 0;
		dfs(i);
		all.pb({cnt[0],cnt[1]});
	}
	//FOR(i,n)cout << color[i] << " ";cout << endl;
	if(bad){
		//cout << all.size() << endl;
		cout << -1 << endl;
		return 0;
	}
	int l = all.size();
	
	FOR(i,l){
		if(i == 0){
			dp[i][all[i].ff] = 1;
			dp[i][all[i].ss] = 1;
		}else{
			FOR(j,MAXN){
				if(j >= all[i].ff)dp[i][j] |= dp[i-1][j-all[i].ff];
				if(j >= all[i].ss)dp[i][j] |= dp[i-1][j-all[i].ss];
			}
		}
	}
	int mx = 0;
	FOR(i,n/2+1){
		if(dp[l-1][i])mx= i;
	}
	
	cout << nc2(mx) + nc2(n-mx) << endl;
    return 0;
}


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

int s(int x) {
  int ans = 0;
  for (; x > 0; x /= 10)
    ans += x % 10;
  return ans;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 10; i <= n; i *= 10)
    if (i == n)
      return 0 * puts("10");
  printf("%d\n", s(n));
  return 0;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = 3;
			int [][] data = new int[n][n];
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					data[i][j] = sc.nextInt();
				}
			}
			
//			int [] a = new int[n];
//			int [] b = new int[n];
			boolean flg = false;
			for(int i = 0; i < 101; i++){
				for(int j = 0; j< 101; j++){
					for(int k = 0; k < 101; k++){
						
						if(data[0][0] - i == data[0][1] - j && 
								data[0][0] - i == data[0][2] - k &&
								data[0][1] - j == data[0][2] - k){
							
							if(data[1][0] - i == data[1][1] - j && 
									data[1][0] - i == data[1][2] - k &&
									data[1][1] - j == data[1][2] - k){
								
								if(data[2][0] - i == data[2][1] - j && 
										data[2][0] - i == data[2][2] - k &&
										data[2][1] - j == data[2][2] - k){
									
									flg = true;
									break;
								}
							}
						}
					}
					if(flg) break;
				}
				if(flg) break;
			}
			System.out.println(flg ? "Yes":"No");
			
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

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

}


Measured memory_bytes: 24404
#include <iostream>
#include <cstdlib>

int main() {
    int32_t a, b, c, x, y;
    std::cin >> a >> b >> c >> x >> y;
    
    int32_t cost = 0;
    
    if (a + b <= 2 * c) {
        cost = a * x + b * y;
    } else {
        int32_t a_or_b = ((x > y) ? a : b);
        if (a_or_b > 2 * c) {
            cost = 2 * c * std::max(x, y);
        } else {
            int32_t min = std::min(x, y);
            cost += 2 * c * min;
            int32_t left = std::max(x, y) - min;
            cost += a_or_b * left;
        }
    }

    std::cout << cost << std::endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INF 1000000000
int main(){
  int n,ma,mb,i,j,k,a,b,c;
  int dp[41][401][401];
  scanf("%d%d%d",&n,&ma,&mb);
  for(i=0;i<41*401*401;i++)dp[i/401/401][i/401%401][i%401]=INF;dp[0][0][0]=0;
  for(i=1;i<=n;i++){
    scanf("%d%d%d",&a,&b,&c);
    for(j=0;j<401;j++)for(k=0;k<401;k++){
      dp[i][j][k]=dp[i-1][j][k];
      if(j-a>=0&&k-b>=0)dp[i][j][k]=dp[i][j][k]<dp[i-1][j-a][k-b]+c?dp[i][j][k]:dp[i-1][j-a][k-b]+c;
    }
  }
  c=INF;
  for(i=1;i<=n;i++)c=dp[n][i*ma][i*mb]<c?dp[n][i*ma][i*mb]:c;
  printf("%d",c==INF?-1:c);
}


Measured memory_bytes: 25856
package main

import (
	"bufio"
	"fmt"
	basicIO "io"
	"os"
	"strconv"
)

func main() {
	protagonist(os.Stdin, os.Stdout)
}

func protagonist(r basicIO.Reader, w basicIO.Writer) {
	io := NewIO(r, w)
	ANum := io.readInt()
	BNum := io.readInt()
	K := io.readInt()

	A := io.readIntSlice(ANum)
	B := io.readIntSlice(BNum)

	count := 0
	sumA := 0
	sumB := 0
	for _, v := range A {
		if sumA+v > K {
			break
		}
		count++
		sumA += v
	}

	maxCount := count
	A = A[:count]

	for i, b := range B {
		sumB += b

		//範囲内になるようAを減らす
		for sumA+sumB > K {
			if len(A) == 0 {
				io.putInt(maxCount)
				return
			}

			//Aの範囲を後ろから一個減らす
			sumA -= A[len(A)-1] //Aの合計の対象範囲が1縮小
			A = A[:len(A)-1]
		}

		if len(A)+i+1 > maxCount {
			maxCount = len(A) + i + 1
		}
	}

	io.putInt(maxCount)
}

type IO struct {
	Scanner *bufio.Scanner
	Writer  basicIO.Writer
}

func NewIO(r basicIO.Reader, w basicIO.Writer) *IO {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	return &IO{
		Scanner: s,
		Writer:  w,
	}
}

func (io *IO) readString() string {
	io.Scanner.Scan()
	return io.Scanner.Text()
}

func (io *IO) readStringSlice(num int) []string {
	slice := make([]string, num)
	for i, _ := range slice {
		slice[i] = io.readString()
	}
	return slice
}

func (io *IO) readInt() int {
	io.Scanner.Scan()
	i, _ := strconv.Atoi(io.Scanner.Text())
	return i
}

func (io *IO) readIntSlice(num int) []int {
	slice := make([]int, num)
	for i, _ := range slice {
		slice[i] = io.readInt()
	}
	return slice
}

func (io *IO) putInt(v int) {
	fmt.Fprintf(io.Writer, "%d\n", v)
}

func (io *IO) putString(s string) {
	fmt.Fprintf(io.Writer, "%s\n", s)
}


Measured memory_bytes: 7856
#include <iostream>
using namespace std;
int main(void){
    int n, b[100];
    cin >> n;
    for(int i=0;i<n-1;i++){
        cin >> b[i];
    }
    
    int ans = b[0] + b[n-2];
    for(int i=1;i<n-1;i++){
        ans += min(b[i-1], b[i]);
    }
    cout << ans << endl;
    
}


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

int main() {
    int x;
    cin>>x;
    long long num[200];
    // 200以上のnはpow(n+1,5)-pow(n,5)>1e9
    rep(i,200) num[i]=pow(i,5);
    //rep(i,200) cout<<i<<" "<<num[i]<<endl;
    rep(i,200){
        int f=find(num,num+200,x+num[i])-num;
        int g=find(num,num+200,x-num[i])-num;
        //cout<<i<<" "<<f<<" "<<g<<endl;
        if(f!=200){
            cout<<f<<" "<<i<<endl;
            break;
        }
        if(g!=200){
            cout<<g<<" "<<-1*i<<endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 4008
def main():
    N, C = map(int, input().split())
    l = []
    for _ in range(N):
        s, t, c = map(int, input().split())
        l.append((s,t,c))
    l.sort(key=lambda x: x[0])
    r = []
    for i in l:
        if not r:
            r.append((i[1], i[2]))
            continue
        for j, v in enumerate(r):
            if v[0] < i[0] or (v[1] == i[2] and v[0] == i[0]):
                r[j] = (i[1], i[2])
                break
        else:
            r.append((i[1], i[2]))
        r.sort(key=lambda x:x[0])
    print(len(r))
main()


Measured memory_bytes: 19016
#include<string>  
#include<algorithm>  
#include<iostream>
using namespace std;  
string S;  
int main(){  
    cin>>S;  
    int res=S.size();  
    int a=S.size();  
    for(int i=1;i<S.size();i++){  
        if(S[i]!=S[i-1])  
            res=min(res,max(i,a-i));  
    }  
    cout<<res<<endl;  
    return 0;  
}

Measured memory_bytes: 512