akhauriyash/Code-Regression huggingface dataset:
/*
[abc165] F - LIS on Tree
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
#define ALL(c) (c).begin(), (c).end()

const int MAX_N = 2e5;
const int INF = 1e9 + 7;

int N;
int a[MAX_N];
vector<int> g[MAX_N];
int ans[MAX_N];

void dfs(vector<int> &path, int v, int par = -1) {
    int idx = lower_bound(ALL(path), a[v]) - path.begin();
    int org = path[idx];
    path[idx] = a[v];
    int len = lower_bound(ALL(path), INF) - path.begin();
    ans[v] = len;
    for (int to : g[v]) {
        if (to == par) continue;
        dfs(path, to, v);
    }
    path[idx] = org;
}

void solve() {
    vector<int> path(N, INF);
    dfs(path, 0);
    for (int i = 0; i < N; i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    solve();

    return 0;
}


Measured memory_bytes: 30736
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int mimorinn(const void* x, const void* y) {
	int64_t a = *(const int64_t*)x, b = *(const int64_t*)y;
	return a < b ? -1 : a > b;
}

int N;
int64_t a[64];

int64_t sousa(void) {
	int64_t no, yes;
	int64_t limit;
	int i;
	int target, num;
	qsort(a, N, sizeof(*a), mimorinn);
	if (a[N - 1] <= N - 1) return 0;
	if (a[0] >= N) {
		target = N - 2;
		num = 1;
		for (i = 1; i < N; i++) {
			if (a[N - 1] - N + (i - 1) > a[N - 1 - i] + i) {
				target = N - 1 - i;
				num = i;
				break;
			}
		}
	} else {
		target = N - 2;
		num = 1;
	}
	if (a[target] + N > a[N - 1]) {
		yes = 1;
	} else {
		no = 0;
		yes = a[N - 1] / N + 1;
		while (no + 1 < yes) {
			int64_t m = no + (yes - no) / 2;
			if (a[target] + m * num + N <= a[N - 1] - N * m + (num - 1) * m) no = m; else yes = m;
		}
	}
	/* limit = (a[N - 1] - (N - 1) + (N - 1)) / N; */
	limit = a[N - 1] / N;
	if (yes > limit) yes = limit;
	for (i = 0; i <= target; i++) a[i] += num * yes;
	for (i = target + 1; i < N; i++) {
		a[i] -= N * yes;
		a[i] += (num - 1) * yes;
	}
	qsort(a, N, sizeof(*a), mimorinn);
	return yes * num;
}

int main(void) {
	int i;
	int64_t miyukiti = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%" SCNd64, &a[i]) != 1) return 1;
	}
	qsort(a, N, sizeof(*a), mimorinn);
	while (a[0] + N < a[N - 1]) {
		int64_t delta = sousa();
		if (delta <= 0) {
			printf("%" PRId64 "\n", miyukiti);
			return 0;
		}
		miyukiti += delta;
	}
	if (a[0] > N) {
		int64_t delta = a[0] - N;
		miyukiti += delta * N;
		for (i = 0; i < N; i++) a[i] -= delta;
	}
	for (;;) {
		int64_t delta = sousa();
		if (delta <= 0) {
			printf("%" PRId64 "\n", miyukiti);
			return 0;
		}
		miyukiti += delta;
	}
	return 0;
}


Measured memory_bytes: 1736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    
    int a,b,k;
    scanf("%d%d%d",&a,&b,&k);
    for(int i=1;i<=k;i++) {
      if(i&1) {
       if(a&1)
       a--;
       b+=a/2;
       a/=2;
      }
      else {
        if(b&1)
       b--;
       a+=b/2;
       b/=2;
      }
    }
    printf("%d %d\n",a,b);
    
}

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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;

const int MAX_v=110;
ll dist[MAX_v][MAX_v];
ll v;
void warshall_floyd(){
  for(int k=0;k<v;k++)
    for(int i=0;i<v;i++)
      for(int j=0;j<v;j++)
	dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
int dist2[200][200]={};
void warshall_floyd2(){
  for(int k=0;k<v;k++)
    for(int i=0;i<v;i++)
      for(int j=0;j<v;j++)
	dist2[i][j]=min(dist2[i][j],dist2[i][k]+dist2[k][j]);
}

int main(){
  ll n,m,l,k,a,h;
  while(cin>>n>>m>>l>>k>>a>>h,n+m+l+k+a+h){
    vector<ll>cold(l);
    ll ans=0;
    for(int i=0;i<l;i++){
      cin>>cold[i];
      cold[i];
    }
    for(int i=0;i<MAX_v;i++)
      for(int j=0;j<MAX_v;j++){
	dist[i][j]=INF;
	dist2[i][j]=INF;
      }
    for(int i=0;i<k;i++){
      int x,y,t;cin>>x>>y>>t;
      if(t>m)continue;
      dist[x][y]=t;
      dist[y][x]=t;
    }
    v=n;
    warshall_floyd();
   
    if(dist[a][h]<=m){
      cout<<dist[a][h]<<endl;
      continue;
    }

    for(int i=0;i<l;i++){
      for(int j=0;j<l;j++){
	if(dist[cold[i]][cold[j]] <= m)
	  dist2[i][j]=dist[cold[i]][cold[j]];
	if(dist[a][cold[j]] <= m){
	  dist2[l][j]=dist[a][cold[j]];
	}
	if(dist[cold[j]][h] <= m)
	  dist2[j][l+1]=dist[cold[j]][h];
      }
    }
    v=l+2;
    warshall_floyd2();
  
    if(dist2[l][l+1] <= m){
      cout<<dist2[l][l+1]<<endl;
    }else if(dist2[l][l+1]==INF){
      cout<<"Help!"<<endl;
    }else{
      cout<<dist2[l][l+1]*2-m<<endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

vector <vector <char> > mem[10];
const int N = 2007;
bool dp[N];
int last[N];
char ans[N][N];
vector <int> can = {4, 5, 7};

void paste(int x, int y, int e) {
    for (int i = 0; i < e; ++i)
        for (int j = 0; j < e; ++j)
            ans[x + i][y + j] = mem[e][i][j];
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

                        mem[3] = { {'a', 'a', 'b'}, 
                                 {'d', '.', 'b'},
                                 {'d', 'c', 'c'} };

                        mem[4] = { {'a', 'a', 'b', 'c'},
                                 {'d', 'd', 'b', 'c'},
                                 {'e', 'f', 'g', 'g'},
                                 {'e', 'f', 'h', 'h'} };

                        mem[5] = { {'a', 'b', 'c', '.', '.'},
                                 {'a', 'b', 'c', '.', '.'},
                                 {'d', 'd', 'e', 'f', 'f'},
                                 {'g', '.', 'e', 'h', 'h'},
                                 {'g', 'i', 'i', 'j', 'j'} };

                        mem[7] = { {'a', 'a', 'b', 'b', 'c', 'c', '.'},
                                 {'d', 'd', 'e', '.', '.', '.', 'f'},
                                 {'g', '.', 'e', '.', '.', '.', 'f'},
                                 {'g', 'h', 'h', '.', '.', '.', 'i'},
                                 {'.', '.', '.', 'j', 'j', 'k', 'i'},
                                 {'.', '.', '.', 'l', '.', 'k', 'm'},
                                 {'.', '.', '.', 'l', 'n', 'n', 'm'} };

    int n;
    cin >> n;
    if (n == 2) {
        cout << "-1\n";
        exit(0);
    }   

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            ans[i][j] = '.';

    if (n == 3) {
        paste(0, 0, 3);
    }   
    else if (n == 6) {
        paste(0, 0, 3);
        paste(3, 3, 3);
    }   
    else {
        dp[0] = 1;
        for (int i = 1; i < N; ++i) {
            for (int e : can) {
                if (e <= i && dp[i - e]) {
                    dp[i] = 1;
                    last[i] = e;
                }   
            }   
        }   

        if (!dp[n])
            exit(1);
                    
        vector <int> a;
        int t = n;
        while (t) {
            a.app(last[t]);
            t -= last[t];
        }   
        int cur = 0;
        for (auto e : a) {
            for (int i = 0; i < e; ++i) {
                for (int j = 0; j < e; ++j) {
                    ans[cur + i][cur + j] = mem[e][i][j];
                }
            }   
            cur += e;
        }   
    }   
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cout << ans[i][j];
        cout << '\n';
    }   
}   

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define ff first
#define ss second
#define int long long 
#define endl "\n"
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	

const int inf = 1e9;
const int MOD = 998244353;
const int N = 2e5+4;

int n , x , m;
int a[N];

void solve(){	
	cin >> n;
	for(int i=1 ; i<=n ; i++)
		cin >> a[i];
	
	map<int,int> mp;
	int ans = 0;
	for(int i=1 ; i<=n ; i++){
		if(mp.find(i-a[i]) != mp.end())
			ans += mp[i-a[i]];
		
		mp[i+a[i]]++;
	}
	cout << ans << endl;
}

	
int32_t main(){
	FAST;
	int t=1;
	//cin>>t;
	while(t--)
		solve();
	return 0;
}	

Measured memory_bytes: 17556
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define int int64_t
#define pcnt __builtin_popcount
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define vec vector<int>
#define mat vector<vector<int>> //mat データ名(縦,vec(横));
#define F first
#define S second
int INF = 1000000000000000001; //10^18+1
int MOD = 1000000007; //10^9+7
//cout << fixed << setprecision(15); (小数点以下表示)

signed main () {
  int N,ans=-1,on=1;
  cin >> N;
  vec a(N+1);
  for(int i=0;i<N;i++)cin >> a.at(i+1);
  for(int i=0;i<2*N;i++){
    on=a.at(on);
    if(on==2){
      ans=i+1;
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main () {
  ll a, b;
  cin >> a >> b;

  ll n = a/4;
  ll l = 4*(n+1)-a;
  ll m = b/4;
  //ll r = b-4*m+1;
  ll ans = 0;
  for (ll i = a; i < a+l; ++i) {
    ans ^= i;
  }
  for (ll i = 4*m; i <= b; ++i) {
    ans ^= i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
count=0
i=1
while i<len(a)-1:
    if (a[i]>a[i+1] and a[i]<a[i-1]) or (a[i]<a[i+1] and a[i]>a[i-1]):
        count+=1
    i+=1
print(count)

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

using namespace std;

int main() {
	int n; cin >> n;
	string s, t; cin >> s >> t;
	vector<int> u;

	u.push_back(0);
	for(int i = 1; i < s.size()+1; i++) {
		string s1 = s.substr(s.size()-i);
		if(t.find(s1) == 0) {
			u.push_back(i);
		}
	}

	cout << 2*s.size()-u[u.size()-1] << endl;

	return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <fstream>

#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

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/GCD(a,b)*b;
}

class CMultiplication3 {
public:
	void solve(std::istream& in, std::ostream& out) {
	    ll a;
	    double b;
	    in>>a>>b;
	    ll b2 = b*100.0+0.5;
	    string s = to_string(a*b2/100);
	    out<<s<<endl;
	}
};


int main() {
	CMultiplication3 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3204
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    int N,x;
    cin >> N >> x;
    int A[N];
    rep(i,N) cin >> A[i];
    sort(A,A+N);
    int ans=0;
    rep(i,N-1){
        if(x>=A[i]) ans++,x-=A[i];
        else break;
    }
    if(A[N-1]==x) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Rep(i,n,m) for(int i = (int)(n);i < (int)(m);i++)
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl 
 
int main()
{
    string s;
    cin >> s;
    bool is = true;
    if(s[0] != 'A')
    {
        is = false;
    }
    int count = 0;
    Rep(i,1,s.size())
    {
        if(isupper(s[i]))
        {
            if(i == 1 || i == (int)s.size() - 1 || s[i] != 'C')
                is = false;
            count++;
        }
    }
    if(count != 1)
        is = false;
    cout << (is ? "AC" : "WA") <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;
typedef pair<int, int> P;

int A[200010];
int main()
{
	int N; cin >> N;
	int sum = 0, Xsum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	ll ans = 0;
	int j = 0, cnt = 0;
	for (int i = 0; i < N; i++) {
		sum += A[i];
		Xsum ^= A[i];
		cnt++;
		while (sum != Xsum) {
			sum -= A[j];
			Xsum ^= A[j];
			j++;
			cnt--;
		}
		ans += cnt;
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
# coding: utf-8

n = int(input().rstrip())

v_list = list(map(int, input().rstrip().split(" ")))
c_list = list(map(int, input().rstrip().split(" ")))

ans = sum([j for j in [v_list[i] - c_list[i] for i in range(n)] if j > 0])
print(ans)

Measured memory_bytes: 3060
#include <cstdio>

int main() {
    int N, a;
    scanf("%d",&N);
    for (int i=0; i<N; i++) {
        scanf("%d",&a);
        if (a % 2 == 1) {
            printf("first\n");
            return 0;
        }
    }
    printf("second\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define MAX_N 100005

int prime[MAX_N];
bool is_prime[MAX_N+1];

int sieve(int n){
    int p=0;
    for(int i=0;i<=n;i++){
        is_prime[i] = true;
    }
    is_prime[0] = false;
    is_prime[1] = false;
    for(int i=2;i<=n;i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j=2*i; j <= n; j+=i){
                is_prime[j] = false;
            }
        }
    }
    return p;
}

int sum[100003];
bool ans[100006];

int main(){
    sieve(100005);
    
    for (int i = 1; i <= 100004; i+=2){
        ans[i] = is_prime[i] && is_prime[(i+1)/2];
    }
    rep(i, 100002){
        if(i%2==0) continue;
        if(ans[i]){
            sum[i+2] = sum[i] + 1;
        }else{
            sum[i+2] = sum[i];
        }
    }

    int q;
    cin >> q;
    rep(i, q){
        int l, r; cin >> l >> r;
        // printf("%d %d\n",sum[l], sum[r]);
        cout << sum[r+2] - sum[l] << endl;
    } 
    return 0;
}

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

int main(){
  vector<int> a(3);
  for (int i=0;i<3;++i) cin >> a.at(i);
  int ans=0;
  sort(a.begin(),a.end());
  for (int i=0;i<2;++i) ans+=a.at(i+1)-a.at(i);
  cout << ans << endl;
}

Measured memory_bytes: 256
_, k = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

counter = Hash.new(0)
nums.each{|x|
  counter[x] += 1
}

size = counter.size
if size <= k
  p 0
else
  p counter.sort_by{|x| x[1]}.first(size - k).inject(0){|res, x| res + x[1]}
end



Measured memory_bytes: 41856
#include<bits/stdc++.h>
using namespace std;
int f[1<<18] , a[1<<18];
bool operator < (pair<int,int> a,pair<int,int> b)
{
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}
set<pair<int,int> > b[1<<18];
int n;
int main()
{
    srand(time(NULL));
    scanf("%d",&n);
    for(int i = 0;i < (1<<n);i++){
        int x;
        scanf("%d",&a[i]);b[i].insert(pair<int,int>{a[i] , i});
    }
    for(int i = 0;i < (1<<n);i++){
        if(b[i].size() > 1){
            set<pair<int,int> >::iterator it = b[i].end();it--;f[i] = it->first;
            it--;f[i] += it->first;
        }
        for(int j = 0;j < 18;j++){
            if((i | (1<<j)) == i) continue;
            b[i | (1<<j)].insert(b[i].begin() , b[i].end());
            while(b[i | (1<<j)].size() > 2){
                b[i | (1<<j)].erase(b[i | (1<<j)].begin());
            }
        }
    }
    int ans = 0;
    for(int i = 1;i < (1<<n);i++){
        ans = max(ans , f[i]);
        printf("%d\n",ans);
    }
    return 0;
}


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,ll> P;
typedef pair<ll,P> PP;

//-----------------------------------------------------------------------------

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

	int a,b,c,d,e,f;
	while(cin>>a>>b>>c>>d>>e>>f) {
		double y=(double)(c*d-a*f)/(double)(b*d-a*e);
		double x=(c-b*y)/a;
		printf("%.3f %.3f\n",x,y);
	}

	return 0;
}



Measured memory_bytes: 3124
#include<stdio.h>
#define INF 1000000000
#define NMAX 200
int dist[NMAX][NMAX], visit[NMAX], r[NMAX];

void Floyd(int);
int Dfs(int, int, int, int);
int main(void)
{
  int i, j, v, e, vr, s, t, d, res;
  scanf("%d %d %d", &v, &e, &vr);
  for (i = 0; i < v; i++) {
    for (j = 0; j < v; j++) {
      dist[i][j] = ((i == j) ? 0 : INF);
    }
  }
  for (i = 0; i < vr; i++) {
    scanf("%d", &r[i]);
    r[i]--;
  }
  for (i = 0; i < e; i++) {
    scanf("%d %d %d", &s, &t, &d);
    if (dist[s-1][t-1] > d) dist[s-1][t-1] = dist[t-1][s-1] = d;
  }
  Floyd(v);
  res = Dfs(0, -1, 0, vr);
  printf("%d\n", res);
  return 0;
}

void Floyd(int size)
{
  int k, i, j;
  for (k = 0; k < size; k++) {
    for (i = 0; i < size; i++) {
      for (j = 0; j < size; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
}

int Dfs(int n, int prev, int path, int size)
{
  int i, rtemp, res = INF;
  if (n == size) return path;
  for (i = 0; i < size; i++) {
    if (!visit[i]) {
      visit[i] = 1;
      if (prev == -1) {
        rtemp = Dfs(n + 1, i, 0, size);
        if (res > rtemp) res = rtemp;
      }
      else {
        rtemp = Dfs(n + 1, i, path + dist[r[prev]][r[i]], size);
        if (res > rtemp) res = rtemp;
      }
      visit[i] = 0;
    }
  }
  return res;
}

Measured memory_bytes: 256
a,b=map(int,input().split())
c,d=map(int,input().split())
e,f=map(int,input().split())
lst=[a,b,c,d,e,f]
ans='NO'
if lst.count(1)==1:
  if lst.count(2)==2:
    if lst.count(3)==2:
      if lst.count(4)==1:
        ans='YES'
print(ans)

Measured memory_bytes: 9200
# C - Sum of gcd of Tuples (Easy)
from math import gcd


def main():
    K = int(input())
    gcd_three = lambda x, y, z: gcd(gcd(x, y), z)
    ans = sum(
        gcd_three(i, j, k)
        for i in range(1, K + 1)
        for j in range(1, K + 1)
        for k in range(1, K + 1)
    )
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 68244
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.close();
        System.out.println(n * (n - 1) / 2 + m * (m - 1) / 2);
    }
}

Measured memory_bytes: 35720
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		long k = Long.parseLong(sc.next());
		
		for(int i = 0; i < k; i++) {
			if(s.charAt(i) >= '2') {
				System.out.println(s.charAt(i));
				return;
			}
		}
		System.out.println(1);
		
	}
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

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

void Main()
{
	int a, b, c;
  	cin >> a >> b >> c;
	if(a==b) cout << c << endl;
	else if(b==c) cout << a << endl;
	else cout << b << endl;
  	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


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


int main( void )
{
    int lim ;
    scanf( "%d" ,&lim ) ;
    
    int i ;
    for( i = 3 ; i <= lim ; ++i )
    {
        char str[ 256 ] ;
        sprintf( str ,"%d" ,i ) ;
        
        if( i % 3 == 0 || strstr( str ,"3" ) != NULL )
        {
            printf( " %d" ,i ) ;
        }
    }
    
    puts( "" ) ;
    
    
    return 0 ;
}



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

using namespace std;

int main(){
    int h, w;
    cin >> h >> w;
    vector<vector<bool>> mat(h, vector<bool>(w));
    for(int hi=0; hi<h; ++hi){
        for(int wi=0; wi<w; ++wi){
            char c;
            cin >> c;
            if(c=='.') mat[hi][wi]=true;
            else mat[hi][wi]=false;
        }
    }
    bool changed;
    do{
        changed=false;
        for(int hi=0; hi<h; ++hi){
            bool found=true;
            for(int wi=0; wi<w; ++wi){
                if(!mat[hi][wi]){
                    found=false;
                    break;
                }
            }
            if(found){
                --h;
                for(; hi<h; ++hi){
                    for(int wi=0; wi<w; ++wi){
                        mat[hi][wi]=mat[hi+1][wi];
                    }
                }
                changed=true;
                break;
            }
        }
        for(int wi=0; wi<w; ++wi){
            bool found=true;
            for(int hi=0; hi<h; ++hi){
                if(!mat[hi][wi]){
                    found=false;
                    break;
                }
            }
            if(found){
                --w;
                for(; wi<w; ++wi){
                    for(int hi=0; hi<h; ++hi){
                        mat[hi][wi]=mat[hi][wi+1];
                    }
                }
                changed=true;
                break;
            }
        }
    } while(changed);
    for(int hi=0; hi<h; ++hi){
        for(int wi=0; wi<w; ++wi){
            cout << (mat[hi][wi] ? '.' : '#');
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL x;
    scanf("%lld", &x);
    if(x<7) puts("1");
    else
    {
         LL rem = x-6;
         LL ans = rem/11*2;
         int s = rem%11;
         if(s>5) ans+=2;
         else if(s>0) ans+=1;
         printf("%lld\n", ans+1);
     }
}

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

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

void solve() {
    int N, M;
    cin >> N >> M;

    vector<int> p(N);
    rep(i, N) {
        cin >> p[i];
        p[i]--;
    }
    UnionFind uf = UnionFind(N);
    rep(i,M) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        uf.unite(x,y);
    }

    map<int, vector<int>> mp;
    rep(i,N) mp[uf.find(i)].push_back(p[i]);

    ll ans = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        vector<int> val = itr->second;
        vector<int> cand;
        rep(i,val.size()) cand.push_back(p[val[i]]);
        sort(val.begin(), val.end());
        sort(cand.begin(), cand.end());

        vector<int> result;
        set_intersection(begin(val), end(val),
                  begin(cand), end(cand),
                  inserter(result, end(result)));

        ans += result.size();
    }

    cout << ans << endl;
}

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


Measured memory_bytes: 11904
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define Mod 1000000007
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
#define INF 999999999999999999
#define NN (ll)(1e6+5)
int mod(string s,int a) 
{ 
    int ans=0; 
    for (int i=0;i<s.length();i++) 
         ans=(ans*10+(int)s[i]-'0')%a; 
    return ans; 
}
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {    
       ll n,f=0,x,i,ans=1;
       cin>>n;
       vector <ll> v(n);
       for(auto &u:v)
       {
        cin>>u;
        if(u==0)
         f=1;
       }
       if(f)
       {
           cout<<"0\n";
           continue;
       }
       for(auto u:v)
       {
           ans*=u;
           if(ans>(ll)1e18||ans<=0)
            {
                ans=-1;
                break;
            }
       }
       cout<<ans;
   }
}

Measured memory_bytes: 3980
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define each(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

int main(){
	int n;
	while(cin >> n, n){
		cin.ignore();
		string in;
		map<string, int> cnt;
		
		rep(i, n){
			getline(cin, in);
			stringstream ss(in);
			while(ss >> in) cnt[in]++;
		}
		
		char c;
		int mx = 0;
		vector<pair<int, string> > ans;
		
		cin >> c;
		each(i, cnt){
			if(i->first[0] == c) ans.pb(mp(-i->second, i->first));
		}
		sort(all(ans));
		bool f = 1;
		
		rep(i, min(5, (int)ans.size())){
			if(!f) cout << " ";
			f = 0;
			cout << ans[i].second;
		}
		if(!ans.size()) cout << "NA";
		cout << endl;
	}
	return 0;
}

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


#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amin(T& a,T2 b){ if(a > b) a = b;}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;;
	cin >>n;
	VI a(n);
	rep(i, n) cin >>a[i];
	
	VI dt(10);
	rep(i, n) dt[min(a[i], 3200)/400]++;
	
	int ct =0;
	rep(i, 8) ct += dt[i] > 0;
	int mn = ct;
	if(ct == 0 && dt[8]>0) mn = 1;
	int mx = ct + dt[8];
	cout<<mn <<" "<<mx <<"\n";
	
	return 0;
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
F = list(map(int,readline().split()))
A.sort()
F.sort(reverse=True)

ng = -1
ok = 10**12+100
while ok - ng > 1:
    mid = (ok + ng) // 2
    if sum(max(0,a-mid//f) for a,f in zip(A,F)) <= K:
        ok = mid
    else:
        ng = mid
print(ok)


Measured memory_bytes: 106956
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if((a+b)>(c+d)){
		cout << "Left" << endl;
	}else if((a+b)<(c+d)){
		cout << "Right" << endl;
	}else if((a+b)==(c+d)){
		cout << "Balanced" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import bisect
A, B, Q = [int(i) for i in input().split()]
S=list()
T=list()
X=list()
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
for i in range(Q):
    X.append(int(input()))

for Q in X:
    SS=list()
    TT=list()
    i = bisect.bisect_left(S,Q)
    #print(i)
    if i>0:
        SS.append(S[i-1])
    if i<A:
        SS.append(S[i])
    i = bisect.bisect_left(T, Q)
    #print(i)
    if i > 0:
        TT.append(T[i - 1])
    if i<B:
        TT.append(T[i])
    minlen=9999999999999
    #print(SS,TT)
    for i in SS:
        for j in TT:
            len=min(abs(Q-i)+abs(i-j),abs(Q-j)+abs(i-j))
            minlen=min(minlen,len)
    print(minlen)



Measured memory_bytes: 88152
n = int(input())
a = list(map(int,input().split()))

a.sort()
li = [True] * (10**6 + 10)
ans = 0

for i in range(n):
    if not li[a[i]]:
        continue
    li[a[i]] = False
    tmp = a[i]
    while tmp < len(li):
        li[tmp] = False
        tmp += a[i]
    if i < n-1:
        if a[i+1] == a[i]:
            continue
    ans += 1


print(ans)


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

using namespace std;

int n, ans = 0;
int p[20];

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> p[i];
	for(int i = 1; i < n - 1; ++i){
		if(p[i] > p[i - 1] && p[i] < p[i + 1] || p[i] < p[i - 1] && p[i] > p[i + 1]){
			ans++;
		}
	}
	cout << ans << endl;
}

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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		var UF = new UnionFind(N);
		Dictionary<int,int> D = new Dictionary<int,int>();
		for(int i=0;i<N;i++){
			for(int j=0;j<K[i];j++){
				if(D.ContainsKey(L[i][j]) == false) D.Add(L[i][j],i);
				UF.Unite(D[L[i][j]],i);
			}
		}
		
		Console.WriteLine(UF.Compo == 1 ? "YES" : "NO");
		
		
		
		
	}
	int N,M;
	int[] K;
	int[][] L;
	
	public Sol(){
		var d = ria();
		N = d[0]; M = d[1];
		K = new int[N];
		L = new int[N][];
		for(int i=0;i<N;i++){
			d = ria();
			K[i] = d[0];
			L[i] = new int[K[i]];
			for(int j=0;j<L[i].Length;j++) L[i][j] = d[j+1];
		}
		
		
		
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}
class UnionFind{
	
	int[] parent;
	int[] mem;
	int compo;
	int N;
	public UnionFind(int n_){
		Initialize(n_);
	}
	
	public void Initialize(int n_){
		N=n_;
		parent=new int[N];
		mem=new int[N];
		for(int i=0;i<N;i++){
			parent[i]=i;
			mem[i]=1;
		}
		compo=N;
	}
	
	public int Parent(int a){
		if(parent[a]==a)return a;
		return parent[a]=Parent(parent[a]);
	}
	
	public bool IsUnited(int a,int b){
		return Parent(a)==Parent(b);
	}
	
	public void Unite(int a,int b){
		a=Parent(a);b=Parent(b);//Parent()を呼ぶことでa以上のノードは全てparentがrootになる
		if(a==b)return;
		parent[a]=b;
		mem[b]+=mem[a];
		compo-=1;
	}
	
	public bool IsRoot(int x){
		return x==parent[x];
	}
	public int MemCnt(int x){
		return mem[Parent(x)];
	}
	
	public void Dump(){
		for(int i=0;i<parent.Length;i++){
			Console.Write(i==0?"{0}":" {0}",parent[i]);
		}
		Console.WriteLine("");
	}
	
	public int Compo{
		get{
			return compo;
		}
	}
	
}


Measured memory_bytes: 16448
S = input()
s0 = int(S[0])
s1 = int(S[1])
s2 = int(S[2])
s3 = int(S[3])
num1 = s0*10 + s1
num2 = s2*10 + s3
if (num1 == 0 or 13 <= num1) and 1 <= num2 and num2 <=12:
    print("YYMM")
elif 1 <= num1 and num1 <= 12 and (num2 == 0 or 13 <= num2):
    print("MMYY")
elif 1 <= num1 and num1 <= 12 and 1 <= num2 and num2 <= 12:
    print("AMBIGUOUS")
else:
    print("NA")


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

int main(){ 
  int n;
  cin>>n; 
  int ct=1;
  string s;
  cin>>s;
  for(int i=0;i<s.size()-1;i++){ 
    if(s.at(i)!=s.at(i+1)){ 
      ct++; 
    } 
  } 
  cout<<ct; 
  return  0; 

 }


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

int solve(int a, int b) {
    if (a % b == 0) {
        int k = a / b;
        return b * (2 * k - 1);
    }   

    int k = a / b;
    int ans = b * 2 * k;
    ans += solve(b, a % b);

    #ifdef HOME
    cout << "solve " << a << ' ' << b << " : " << ans << endl;
    #endif

    return ans;
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif    
    int a, b;
    cin >> a >> b;
    
    int t = a;
    a -= b;
    if (a < b)
        swap(a, b);
        
    cout << t + solve(a, b) << endl;
}

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

#define pb push_back
#define eb emplace_back
#define mk make_pair
#define fi first
#define se second
#define mset(a, b) memset(a, b, sizeof(a))
#define DBG(x) cout << "[" << #x << "]: " << x << endl
using ll = long long;
using pii = pair<int, int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

template<class Ty> Ty randint(Ty a, Ty b) { return uniform_int_distribution<Ty>(a, b)(rng); }
template<class num> inline void rd(num& x) {
	char c, neg = 0; while(isspace(c = getchar_unlocked()));
	if(!isdigit(c)) neg = (c == '-'), x = 0;
	else x = c - '0';
	while(isdigit(c = getchar_unlocked())) x = (x << 3) + (x << 1) + c - '0';
	x = neg ? -x : x; }
template <class... Args> inline void rd(Args&... args) { (rd(args), ...); }

const int MAXN = 3e5 + 5, INF = 0x3f3f3f3f;

int main() {
	ll n; rd(n);
	n--;

	string ans;
	while(n >= 0) {
		ans += char(n%26 + 'a');
		n /= 26;
		n--;
	}
	reverse(ans.begin(), ans.end());
	printf("%s\n", ans.c_str());
}

Measured memory_bytes: 3548