akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;

#define INF 1000000
using namespace std;

int n,m;
int cost[100][100];
int mincost[100];
bool used[100];

int Prim(){
	for(int i = 0; i < n; i++){
		mincost[i] = INF;
		used[i] = false;
	}
	mincost[0] = 0;
	int res = 0;
	while(true){
		int v = -1;
		for(int u = 0; u < n;u++){
			if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}
		if(v == -1) break;
		used[v] = true;
		res += mincost[v] / 100;
		for(int u = 0; u < n; u++){
		mincost[u] = min(mincost[u], cost[v][u]);
		}
	}
	return res;
}

int main(){
	while(scanf("%d",&n)){
	if(n == 0)break;
	scanf("%d", &m);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n;j++){
			cost[i][j] = INF;
		}
	}
	for(int i = 0; i < n; i++) cost[i][i] = 0;
	for(int i = 0; i < m; i++){
		int a,b,c;
		scanf("%d,%d,%d", &a,&b,&c);
		cost[a][b] = cost[b][a] = c;
	}
	printf("%d\n", Prim()-n+1);
	}
	return 0;
}

Measured memory_bytes: 3228
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int w, h, n;
  cin >> w >> h >> n;
  int x[n], y[n], a[n];
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> a[i];
  }

  int min_x = 0;
  int max_x = w;
  int min_y = 0;
  int max_y = h;
  for (int i = 0; i < n; i++) {
    switch (a[i]) {
    case 1:
      min_x = max(min_x, x[i]);
      break;
    case 2:
      max_x = min(max_x, x[i]);
      break;
    case 3:
      min_y = max(min_y, y[i]);
      break;
    case 4:
      max_y = min(max_y, y[i]);
      break;
    }
  }
  if (max_x > min_x && max_y > min_y) {
    cout << max(0, (max_x - min_x) * (max_y - min_y)) << endl;
  } else {
    cout << "0" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
/*
Hanit Banga
Problem: 
*/

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
// #include <climits>
#include <iomanip>
#include <queue>

using namespace std;

#define pb push_back
#define node second
#define weight first

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <double, int> edge;
typedef pair <ll, ll> pll;

const int maxNodes = 1e4 + 10, N = 1e4 + 10; //Set this value
const double maxDist = 1e18;

vector <edge> g[maxNodes];
priority_queue <edge, vector <edge>, greater <edge> > q;
bool visited[maxNodes];
double dist[maxNodes];

void init(int);
void dijkstra(int);
double distance(int, int);

double x[N], y[N], r[N];

int main()
{
    int n;
    cin >> x[0] >> y[0] >> x[1] >> y[1] >> n;
    r[0] = r[1] = 0;
    n += 2;

    init(n);

    for (int i = 2; i < n; ++i)
        cin >> x[i] >> y[i] >> r[i];

    for (int i = 0; i < n; ++i)
    {
        for (int j = i+1; j < n; ++j)
        {
            double d = max(0.0, distance(i,j) - r[i] - r[j]);
            g[i].pb({d, j});
            g[j].pb({d, i});
        }
    }

    dijkstra(0);
    cout << setprecision(10) << fixed << dist[1];
}

void init(int n = maxNodes-1)
{
    //Initializes everything to empty, can be optimized by passing n
    //Include <climits>

    while (!q.empty())
        q.pop();

    for (int i = 0; i <= n; ++i)
    {
        g[i].clear();
        visited[i] = false;
        dist[i] = maxDist;
    }
}

void dijkstra(int startNode)
{
    //Stores shortest distance from startNode to every node in array dist
    //Time complexity is O(Elog2(V))

    dist[startNode] = 0.0;
    q.push({0.0, startNode});

    while (!q.empty())
    {
        while (!q.empty() and visited[q.top().node])
            q.pop();

        if (q.empty())
            break;

        int temp = q.top().node;
        q.pop();

        // if (temp == destNode)
        //     return;

        for (auto i : g[temp])
        {
            if (!visited[i.node])
            {
                if (dist[temp] + i.weight < dist[i.node])
                {
                    dist[i.node] = dist[temp] + i.weight;
                    q.push({dist[i.node], i.node});
                }
            }
        }

        visited[temp] = true;
    }
}

double distance(int i, int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}

Measured memory_bytes: 21012
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << (ele) << endl
#define print10(ele) cout << fixed << setprecision(10) << (ele) << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int f(int n) {
  if (n % 2)
    return 3 * n + 1;
  else
    return n / 2;
}

int main() {
  int s;
  set<int> a;
  cin >> s;
  a.insert(s);
  int count = 1;
  while (1) {
    count++;
    int sb = a.size();
    s = f(s);
    a.insert(s);
    int sa = a.size();
    if (sb == sa) {
      print(count);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <utility>
#include <functional>
#include <map>
#include <string>
#include <set>
#include <math.h>

using namespace std;

// a, bの最大公約数を求める関数
// ユークリッドの互除法を使う
int gcd(int a, int b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}

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

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

  int l[n];
  l[0] = a[0];
  for (int i = 0; i < n - 1; i++) {
    l[i + 1] = gcd(l[i], a[i + 1]);
  }

  int r[n];
  r[n - 1] = a[n - 1];
  for (int i = n - 2; i >= 0; i--) {
    r[i] = gcd(r[i + 1], a[i]);
  }

  int m[n];
  for (int i = 0; i < n; i++) {
    if (i == 0) {
      m[i] = r[i + 1];
    }
    else if (i == n - 1) {
      m[i] = l[i - 1];
    }
    else {
      m[i] = gcd(l[i - 1], r[i + 1]);
    }
  }

  int maxM = 0;
  for (int i = 0; i < n; i++) {
    maxM = max(maxM, m[i]);
  }

  cout << maxM << endl;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef long double ld;
#define A 1000000007
#define D 100000000000000ll
#define B 998244353ll
#define C 1000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,less_equal<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

int main() 
{
    FAST;
    ll a;
    cin>>a;
    cout<<(a+(a*a)+(a*a*a));
    subt;
    return 0;
}

Measured memory_bytes: 3800
#include <stdio.h>

int main(){
  unsigned long int a,b,c,i,tmp, r;

  scanf("%lu %lu %lu",&a,&b,&c);

  unsigned long int s[3] = {a ,b, c};

  for(i=0;i<3;i++){
    if(s[i]>=a &&s[i]>=b && s[i]>=c){
      tmp = s[0];
      s[0] = s[i];
      s[i] = tmp;
    }
  }

  if(s[0]%2==0 || s[1]%2==0 || s[2]%2==0){
    r=0;
    printf("%lu",r);
  }
  else{
    r = s[1]*s[2];
    printf("%lu",r);
  }

return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(x, to) for (int x = 0; x < (to); x++)
#define REP(x, a, to) for (int x = (a); x < (to); x++)
#define EPS (1e-14)
#define _PA(x,N) rep(i,N){cout<<x[i]<<" ";}cout<<endl;
#define _PA2(x,H,W) rep(i,(H)){rep(j,(W)){cout<<x[i][j]<<" ";}cout<<endl;}

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef complex<double> Complex;
typedef vector< vector<int> > Mat;

int X;

bool ok(ll t) {
	ll x = X;
	while (t > 0 && x > 0) {
		x -= t;
		t--;
	}
	return x <= 0;
}

void solve() {
	ll mn = 0;
	ll mx = 1e+9 + 5;
	while (mx - mn > 1) {
		ll mid = (mx + mn) / 2;
		if (ok(mid)) {
			mx = mid;
		} else {
			mn = mid;
		}
	}
	cout << mx << endl;
}

int main() {
	cin >> X;
	solve();
	return 0;
}




Measured memory_bytes: 256
'use strict'
function Main(input) {
  let a = input.split("\n");
  let b = a[1].split(" ");
  // ソートしたもの
  let c = b.sort(function(a,b){return (parseInt(a) < parseInt(b)) ? 1 : -1;});
  
  // それぞれの数
  let alice = 0;
  let bob = 0;
  
  for(let i = 0; i < a[0]; i++){
  	if((i % 2) == 0){
    	alice += Number(c[i]);
    } 
    else{
    	bob += Number(c[i]);
    }
  }
  console.log(alice - bob);
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define dbgmint(n,arr) rep(i,n){cerr<<arr[i].x<<" ";}cerr<<endl;
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

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

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

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll a,b;
    cin>>a>>b;
    Vs vs(2);
    string x;
    string y;
    rep(i,b){
        x += to_string(a);
    }
    rep(i,a){
        y += to_string(b);
    }
    vs[0]=x;
    vs[1]=y;
    sort(ALL(vs));
    cout<<vs[0]<<endl;
    return  0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;

struct X{
    LL a,b,c;

    X(){

    }

    X(LL i,LL j,LL k):a(i),b(j),c(k){

    }

    bool operator <(const X& right)const{
        return c < right.c;
    }
};

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

    LL n,m;
    cin >> n >> m;
    vector<LL> count(n+1,1);

    vector<X> inp(m);
    for(int i = 0; i < m; i++){
        LL a,b;
        cin >> a >> b;
        inp[i] = X(i,a,b);
    }

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

    vector<string> ans(m,"            ");

    for(int i = 0; i < m; i++){
        string tmp = "";
        LL x = inp[i].b;
        LL s = 0;
        while(x > 0){
            x /= 10;
            s++;
        }
        for(int j = 0; j < 6-s; j++){
            tmp += '0';
        }
        tmp += to_string(inp[i].b);
        LL y = count[inp[i].b]++;
        s = 0;
        while(y > 0){
            y /= 10;
            s++;
        }
        for(int j = 0; j < 6-s; j++){
            tmp += '0';
        }
        tmp += to_string(count[inp[i].b]-1);
        ans[inp[i].a] = tmp;
    }

    for(int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 10880
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)

             
def multi_lcm(array, m):
    """arrayのLCMを求める"""
    ans = array[0] 
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
        if ans > 5*m:
            return 5*m
    return ans 

import sys
input = sys.stdin.readline

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

l = [0] * n
for i in range(n):
    cnt = 0
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            cnt += 1
            tmp //= 2
        else:
           break
    l[i] = cnt
if max(l) != min(l):
    print(0)
    exit()
    
div = multi_lcm(a, m)
ans = 0
if m - div // 2 >= 0:
    ans += 1
m = m - div // 2 
ans += m // div
if m < 0:
    print(0)
else:
    print(ans)


Measured memory_bytes: 59632
#include <iostream>
#include <algorithm>
#include<vector>
#include <utility>
#include <string>

using namespace std;

int main(){
  int n,a,b,c,i,j,k;
  string s;
  cin >> a >> b >> c;
  if(a<=c && c <=a+b){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#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 fr(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<<#x<<" = "<<(x)<<endl
#define F first
#define S second

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

typedef complex<double> P;
bool sameline(int a,int b,int c,int p,int q,int r){
	if(a*q!=b*p)return 0;
	if(a==0)return b*r==c*q;
	return a*r==c*p;
}
void push(vector<P> &v,const P &p){
	rep(i,v.size())if(abs(v[i]-p)<EPS)return;
	v.pb(p);
}
P crosspoint(const pair<pi,int> &a,const pair<pi,int> &b){
	int a1=a.F.F,b1=a.F.S,c1=a.S,a2=b.F.F,b2=b.F.S,c2=b.S;
	double x=(-b2*c1+b1*c2)*1.0/(a1*b2-a2*b1),y=(a2*c1-a1*c2)*1.0/(a1*b2-a2*b1);
	return P(x,y);
}

int n,a,b,c,d,e,f;
vector<pair<pi,int> > ls;
vector<P> cps[20],cp;
vector<P> pts;

vector<P> cpLC(const pair<pi,int> &l){
	int a1=a,b1=b,c1=c,d1=d,e1=e,f1=f,d2=l.F.F,e2=l.F.S,f2=l.S;
	if(e2==0){
		swap(a1,c1); swap(d1,e1); swap(d2,e2);
	}
	vector<P> res;
	int p=a1*e2*e2-b1*e2*d2+c1*d2*d2;
	int q=-b1*e2*f2+2*c1*d2*f2+d1*e2*e2-e1*e2*d2;
	int r=c1*f2*f2-e1*e2*f2+f1*e2*e2;
	if(p==0){
		double x=-r*1.0/q, y=(-f2-d2*x)/e2;
		res.pb(P(x,y));
	}
	else{
		ll D=(ll)q*q-4ll*p*r;
		if(D==0){
			double x=-q/2.0/p,y=(-f2-d2*x)/e2;
			res.pb(P(x,y));
		}
		else if(D>0){
			double x1=(-q+sqrt(q*1.0*q-4.0*p*r))/2/p,y1=(-f2-d2*x1)/e2;
			double x2=(-q-sqrt(q*1.0*q-4.0*p*r))/2/p,y2=(-f2-d2*x2)/e2;
			res.pb(P(x1,y1)); res.pb(P(x2,y2));
		}
	}
	if(d2==0)rep(i,res.size())swap(res[i].real(),res[i].imag());
	
	return res;
}

int main(){
	cin>>n>>a>>b>>c>>d>>e>>f;
	rep(i,n){
		int a,b,c;
		cin>>a>>b>>c;
		rep(j,ls.size())if(sameline(ls[j].F.F,ls[j].F.S,ls[j].S,a,b,c)){
			n--;
			goto NEXT;
		}
		ls.pb(mp(mp(a,b),c)); NEXT:;
	}
	rep(i,n)rep(j,i)if(ls[i].F.F*ls[j].F.S!=ls[i].F.S*ls[j].F.F){
		push(cps[i],crosspoint(ls[i],ls[j]));
		push(cps[j],crosspoint(ls[i],ls[j]));
	}
	rep(i,n){
		vector<P> tmp=cpLC(ls[i]);
		rep(j,tmp.size())push(cp,tmp[j]), push(cps[i],tmp[j]);
	}
	rep(i,n)rep(j,cps[i].size())push(pts,cps[i][j]);

	int ans=1-(int)pts.size();
	rep(i,n)ans+=cps[i].size()+1;
	if(b*b<4*a*c)ans+=max(1,(int)cp.size());
	else if(b*b==4*a*c)ans+=cp.size()+1;
	else ans+=cp.size()+2;
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 0
#                         author:  kagemeka 
#                         created: 2019-11-07 11:52:43(JST)
import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator

def main():
    a, b, x = (int(i) for i in sys.stdin.readline().split())
    print('YES' if x >= a and b >= x - a else 'NO') 


if __name__ == "__main__":
    # execute only if run as a script
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define INF 0x3f3f3f3f
int n,dp[N][2];char a[N];
int main()
{
	scanf("%s",a+1);n=strlen(a+1);dp[n+1][1]=INF;
	for(int i=n,t;i>=0;--i)
	{
		t=a[i]&15;
		if(t==9)
		{
			dp[i][0]=dp[i+1][0]+t;
			dp[i][1]=min(dp[i+1][0]+10-t,dp[i+1][1]+9-t);
		}
		else
		{
			dp[i][0]=min(dp[i+1][0]+t,dp[i+1][1]+t+1);
			dp[i][1]=min(dp[i+1][0]+10-t,dp[i+1][1]+9-t);
		}
	}printf("%d\n",min(dp[0][0],dp[0][1]));return 0;
}

Measured memory_bytes: 9088
X = dict()
cc = 0
for _ in range(3):
    a, b, c = map(int, input().split())
    X[a] = cc
    cc += 1 
    X[b] = cc
    cc += 1 
    X[c] = cc
    cc += 1 

Q = int(input())
ss = set()
for _ in range(Q):
    c = int(input())
    if c in X:
        ss.add(X[c])
if 0 in ss and 1 in ss and 2 in ss:
    print("Yes")
elif 3 in ss and 4 in ss and 5 in ss:
    print("Yes")
elif 6 in ss and 7 in ss and 8 in ss:
    print("Yes")
elif 0 in ss and 3 in ss and 6 in ss:
    print("Yes")
elif 1 in ss and 4 in ss and 7 in ss:
    print("Yes")
elif 2 in ss and 5 in ss and 8 in ss:
    print("Yes")
elif 0 in ss and 4 in ss and 8 in ss:
    print("Yes")
elif 2 in ss and 4 in ss and 6 in ss:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 38256
/*
        FFFFFFFFFFFFFFFFFFFFFF
        F::::::::::::::::::::F
        F::::::::::::::::::::F
        FF::::::FFFFFFFFF::::F
          F:::::F       FFFFFF
          F:::::F
          F::::::FFFFFFFFFF
          F:::::::::::::::F
          F:::::::::::::::F
          F::::::FFFFFFFFFF
          F:::::F
          F:::::F
        FF:::::::FF
        F::::::::FF
        F::::::::FF
        FFFFFFFFFFF
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(...) cout<<__FUNCTION__<<":"<<__LINE__<<": ";debugger(#__VA_ARGS__, __VA_ARGS__);
template<typename arg>
void debugger(const char* varname, arg&& var) { cout<<varname<<" = "<<var<<endl; }
template<typename arg, typename... args>
void debugger(const char* varnames, arg&& var, args&&... vars) {
    const char* comma = strchr(varnames + 1, ',');
    cout.write(varnames, comma - varnames)<<" = "<<var<<" | ";
    int sz = 1; if(isspace(comma[sz])) sz++;
    debugger(comma + sz, vars...);
}
using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
extern const int INF = INT_MAX - 5;
extern const int MOD = 1e9 + 7;
extern const int N = 1e5 + 200;
int n;
int v[N], l[N], r[N];
int gcd(int a, int b) {
    while(b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &v[i]);
    }
    l[0] = v[0];
    for(int i = 1; i < n - 1; ++i) {
        l[i] = gcd(l[i - 1], v[i]);
    }
    int ans = l[n - 2];
    r[n - 1] = v[n - 1];
    for(int i = n - 3, k = n - 2; i >= 0; --i, --k) {
        int cur = gcd(l[i], r[k + 1]);
        ans = max(cur, ans);
        r[k] = gcd(r[k + 1], v[k]);
    }
    ans = max(ans, r[1]);
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <ios>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <iomanip>
#include <cmath>

using namespace std;

const int N = (int) 1e4 + 5;
const int M = (int) 1e9 + 7;

typedef long long ll;

int l;

int main() {
    cin >> l;

    cout << fixed << setprecision(8) << pow(1.0 * l / 3, 3) << endl;

    return 0;
}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define reps(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

signed main() {
    int n;
    cin >> n;
    rep(i, n) {
        vint a;
        do {
            a.push_back(0);
            cin >> a.back();
        } while (a.back() != 0);
        a[0] += 1;
        vpint p{{0, 1}};
        vvint ans{vint()};
        int cur = 1;
        rep(i, a.size()) {
            if (a[i] > 0) {
                ans.push_back(vint());
                ans[p.back().first].push_back(cur);
                if (i > 0) { ans[cur].push_back(p.back().first); }
                p.back().second--;
                p.push_back({cur, a[i] - 1});
                cur++;
            } else if (a[i] < 0) {
                ans[p.back().first].push_back(p[p.size() + a[i] - 1].first);
                ans[p[p.size() + a[i] - 1].first].push_back(p.back().first);
                p.back().second--;
                p[p.size() + a[i] - 1].second--;
            } else {
                break;
            }
            while (p.back().second == 0) { p.pop_back(); }
        }
        for (int i = 1; i < ans.size(); i++) {
            cout << i;
            sort(all(ans[i]));
            rep(j, ans[i].size()) { cout << " " << ans[i][j]; }
            cout << endl;
        }
    }
}



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

class DisjointSet {
public:
	vector<int> rank, p;
	DisjointSet(int size) {
		rank.resize(size, 0);
		p.resize(size, 0);
		for (int i = 0; i < size; i++) {
			makeSet(i);
		}
	}
	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}
	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}
	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}
	void link(int x, int y) {
		if (rank[x] < rank[y]) {
			p[x] = y;
		}
		else {
			p[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
	}
	int findSet(int x) {
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
		
	}
};

int main() {
	int n,q;
	bool com;
	int x, y;
	cin >> n >> q;
	DisjointSet djs = DisjointSet(n);
	for (int i = 0; i < q; i++) {
		cin >> com >> x >> y;
		if (com) {
			cout << djs.same(x, y) << endl;
		}
		else {
			djs.unite(x, y);
		}
	}
	return 0;
}

Measured memory_bytes: 3152
import itertools
n,m,q=map(int,input().split())
A,B,C,D=[],[],[],[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
ans=0
 
L=[i+1 for i in range(m)]
for l in itertools.combinations_with_replacement(L, n):
#for l in itertools.product(L, repeat=n):
    s=0
    for j in range(q):
        if int(l[B[j]-1])-int(l[A[j]-1])==C[j]:
            s+=D[j]
    ans=max(ans,s)
    if ans==sum(D):
        print(ans)
        exit()
print(ans)


Measured memory_bytes: 9176
N = int(input())
a1 = 0
a2 = 0
a1_ind = -1

for i in range(0,N):
    x = int(input())
    if a1 < x:
        a2 = a1
        a1 = x
        a1_ind = i
    elif a2 < x:
        a2 = x

for i in range(0,N):
    if i == a1_ind:
        print(a2)
    else:
        print(a1)

Measured memory_bytes: 4540
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	a := nextInt()
	b := nextInt()
	k := nextInt()
	l := make([]int, 101)

	for i := 1; i <= 100; i++ {
		if a%i == 0 && b%i == 0 {
			l[i] = i
		}
	}

	sort.Ints(l)
	fmt.Println(l[101-k])

}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


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

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

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  string s;
  cin >> s;

  string res = "";
  rep(i, s.size()) {
    char c;
    switch (s[i]) {
      case 'A':
        c = 'T';
        break;
      case 'T':
        c = 'A';
        break;
      case 'G':
        c = 'C';
        break;
      case 'C':
        c = 'G';
        break;
    }
    res.push_back(c);
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<iomanip>
#include<stack>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<limits>
using namespace std;

int main() {
	string s1, s2;
	cin >> s1 >> s2;
	s1 = s1 + s1;
	int sz = s2.size();
	for( int i=0;i<sz;i++)
		if (s1.compare(i,sz, s2) == 0) {
			cout << "Yes";
			return 0;
		}
	cout << "No";
	return 0;
}

Measured memory_bytes: 256
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func searchIdx(array []int, value int) int {
	for i := range array {
		if array[i] == value {
			return i
		}
	}
	return -1
}

func reconstruct(preorder []int, inorder []int) string {
	if len(preorder) == 0 {
		return ""
	}

	// fmt.Println(preorder, inorder)

	mid := preorder[0]
	idxSplitAt := searchIdx(inorder, mid)

	l := inorder[:idxSplitAt]
	result := []string{}
	leftResult := reconstruct(preorder[1:(len(l)+1)], l)
	if leftResult != "" {
		result = append(result, leftResult)
	}
	rightResult := reconstruct(preorder[(len(l)+1):], inorder[(idxSplitAt+1):])
	if rightResult != "" {
		result = append(result, rightResult)

	}
	result = append(result, strconv.Itoa(mid))

	return strings.Join(result, " ")
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	preorder := make([]int, nNodes)
	for iNode := 0; iNode < nNodes; iNode++ {
		preorder[iNode] = nextInt()
	}
	inorder := make([]int, nNodes)
	for iNode := 0; iNode < nNodes; iNode++ {
		inorder[iNode] = nextInt()
	}
	// fmt.Println(preorder)
	// fmt.Println(inorder)
	fmt.Println(reconstruct(preorder, inorder))
}



Measured memory_bytes: 1136
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 2000+5

typedef long long ll;

using namespace std;

int main() {
	ll n;
	scanf("%lld",&n);
	ll f1=2,f2=1;
	if(n==0){
		printf("%lld",f1);
	}
	else if(n==1){
		printf("%lld",f2);
	}
	else {
		for(int i=2;i<=n;i++){
			ll f=f1+f2;
			f1=f2;
			f2=f;
		}
		printf("%lld",f2);
	}
	return 0;
}

Measured memory_bytes: 128
//list index out of rangeエラー表示用
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep1(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main(){
  int n;
  cin >> n;
  string s;
  int AC = 0;
  int WA = 0;
  int TLE = 0;
  int RE = 0;
  rep1(i, n){
    cin >> s;
    if(s == "AC")AC += 1;
    if(s == "WA")WA += 1;
    if(s == "TLE")TLE += 1;
    if(s == "RE")RE += 1;
  }
  cout << "AC" << " " << "x" << " " << AC << endl;
  cout << "WA" << " " << "x" << " " << WA << endl;
  cout << "TLE" << " " << "x" << " " << TLE << endl;
  cout << "RE" << " " << "x" << " " << RE << endl;
}



Measured memory_bytes: 3640
N = int(input())
def get_sieve_of_eratosthenes(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

ans = []
li = get_sieve_of_eratosthenes(55555)
for i in li:
  if i % 5 == 1:
    ans.append(i)
  if len(ans) >= N:
    break
print(*ans)

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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

map<ll, ll> primefact(ll n) {
    map<ll, ll> res;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}

ll N;
VL A;

int main() {
    cin >> N;
    A.resize(N);
    VECCIN(A);
    ll cnt = 0;
    int dir = 0;
    REP(i, N - 1) {
        if(dir) {
            if((A[i + 1] > A[i] && dir == -1) || (A[i + 1] < A[i] && dir == 1)) {
                cnt++;
                dir = 0;
            }
        } else {
            if(A[i + 1] > A[i])
                dir = 1;
            else if(A[i + 1] < A[i])
                dir = -1;
        }
    }
    cout << cnt + 1 << "\n";
    return 0;
}


Measured memory_bytes: 1024
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    for i in range(n-1):
        u, v, w = mi()
        u -= 1
        v -= 1
        edge[u].append((v, w))
        edge[v].append((u, w))
    dist = [0]*n
    parent = [-1]*n
    que = deque([0])
    while que:
        v = que.pop()
        for nv, nx in edge[v]:
            if parent[v] == nv:
                continue
            parent[nv] = v
            dist[nv] = dist[v]+nx%2
            dist[nv]%= 2
            que.append(nv)
    print(*dist, sep='\n')
    


if __name__ == '__main__':
    main()

Measured memory_bytes: 45276
from collections import Counter
S = list(input())
T = list(input())
change = [-1]*27
ans = "Yes"
for i in range(len(S)):
    s = ord(S[i])-97
    if S[i] == T[i]:
        change[s] = s
    elif change[s] == -1:
        change[s] = ord(T[i])-97
    else:
        t = ord(T[i])-97
        if change[s] != t:
            ans = "No"
            break
change=Counter(change)
del change[-1]
for i in change.values():
    if i==1:
        continue
    else:
        ans="No"
print(ans)

Measured memory_bytes: 12436
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,cnt,max=0;
  vector<string> s(101),t(101);
  string a;
  cin>>n;
  for(int i=0; i<n; i++)cin>>s.at(i);
  cin>>m;
  for(int i=0; i<m; i++)cin>>t.at(i);
  
  for(int i=0; i<n; i++){
    a=s.at(i);
    cnt=0;
    for(int j=0; j<n; j++)
      if(a==s.at(j))cnt++;
    for(int j=0; j<m; j++)
      if(a==t.at(j))cnt--;
    //cout<<a<<" "<<cnt<<endl;
    if(max<cnt)max=cnt;
  }
  cout<<max<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
typedef pair<pii,pii> piiii;
typedef vector<pii> vii;
typedef vector<ll> vi;
typedef queue<ll> qi;
typedef queue<char> qc;
typedef queue<string> qs;
typedef vector<char> vc;
typedef vector<string> vs;
typedef map<char,ll> mpci;
typedef map<ll,ll> mpii;
typedef map<string,ll> mpsi;
typedef set<ll> sei;
typedef set<char> sec;
typedef set<string> ses;
typedef stack<ll> si;
typedef stack<char> sc;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pll> vpll;
typedef vector<pdd> vdd;
typedef unsigned int uint;
typedef long double ld;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vii> vvii;
/*=====================================================================*/
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define sz(a) (int)(a.size())
#define len(a) (int)(a.length())
#define all(s) (s).begin(),(s).end()
#define fi first
#define se second
#define be begin
#define en end
#define m_p make_pair
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define forn(i,p,n) for(int i=p;i<=n;i++)
#define ford(i,p,n) for(int i=n-1;i>=p;i--)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define zero(a) memset(a,0,sizeof(a))
#define number(a,num) memeset(a,num,sizeof(a))

/*=====================================================================*/

inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
inline void write(long long x) {
  static long long sta[35];
  long long top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);
  puts("");
}
/*======================================================================*/
bool prime(int n)
{
	if(n==0||n==1)
	  return false;
	for(int i=2;i*i<=n;i++)
	  if(n%i==0)
	    return false;
	return true;
}
/*======================================================================*/
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
/*======================================================================*/
int main()
{
  /*
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
  */
  /*====================================================================*/
  int a,b,c,d;
  read(a);
  read(b);
  read(c);
  read(d);
  if(d==1)
    cout<<1<<endl;
  else
    cout<<0<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main()
{
    double a,b,x;
    double height,r;
    double s;
    double deg;
    scanf("%lf %lf %lf",&a,&b,&x);
    height=x/a/a;
    //printf("%f",height);
    if(a*a*b < x*2.){
        deg=180.*(atan((b-height)*2./a))/M_PI;
    }
    else{
        s=a*height;
        deg=90.-180.*(atan(2.*s/b/b))/M_PI;
    }
    printf("%f\n",deg);
    
    

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
char buf[1145141];
signed main(){
  //cin.tie(0);
  //ios::sync_with_stdio(0);
  int n;
  while(scanf("%lld",&n),n){
    int m;
    scanf("%lld",&m);
    scanf("%s",buf);
    string s(buf);
    int ans=0;
    for(int i=0;i<m;i++){
      if(s[i]!='I') continue;
      int k=0;
      while(i+k*2+2<m&&s[i+k*2+1]=='O'&&s[i+k*2+2]=='I') k++;
      ans+=max(0LL,k-n+1);
      //cout<<i<<" "<<k<<endl;
      if(k) i+=k*2-1;
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 4816
#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>;

int main(){
   int n,d; cin>>n>>d;
   vector<vector<int>> x(n,vector<int>(d));
   rep(i,n){
      rep(j,d){
         cin>>x[i][j];
      }
   }
   int ans=0;
   rep(i,n){
      for(int j=i+1;j<n;j++){
         int norm=0;
         rep(k,d){
            int diff=abs(x[i][k]-x[j][k]);
            norm+=diff*diff;
         }
         bool flag=false;
         for(int k=0;k<=norm;k++){
            //√normが整数になる
            if(k*k==norm){
               flag=true;
            }
         }
         if(flag) ans++;
      }
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
max_n=2 * 10**5
mod=998244353
fact, inv_fact = [0] * (max_n + 1), [0] * (max_n + 1)
fact[0] = 1
for i in range(max_n):
    fact[i + 1] = fact[i] * (i + 1) % mod

inv_fact[-1] = pow(fact[-1], mod - 2, mod)
for i in reversed(range(max_n)):
    inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

def nCr_mod(n, r):
    res = 1
    while n or r:
        a, b = n % mod, r % mod
        if a < b:
            return 0
        res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
        n //= mod
        r //= mod
    return res
n,m,k = map(int,input().split())


mm1 = [1]

for i in range(1, n+1):
    mm1 += [(mm1[-1] * (m-1)) % mod]

mm = [1]
for i in range(1, n+1):
    mm += [(mm[-1] * (m)) % mod]

ans = 0
for i in range(k+1):
    if i == 0:
        ans += (mm1[n-1] * m ) % mod
        continue
    if i == n-1:
        ans += (m)
        break
    ans += (mm1[n-1-i] * nCr_mod(n-1,i) * m) % mod

ans = (ans)%mod
print(ans)



Measured memory_bytes: 91060
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let mut sum = 0_f64;
    for _ in 0..n {
        let a: f64 = scan(tokens);
        sum += 1.0 / a;
    }
    println!("{}", 1.0 / sum);
}


Measured memory_bytes: 4476
#include <bits/stdc++.h> 
    //#define M_PI 3.14159265358979323846



using namespace std;

#define rep(i,a,b) for(int i=a;i<b;++i)
#define repb(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vl vector<long long int>
#define vc vector<char>
#define vld vector<ld>
#define vvi vector<vector<int> >
#define vvl vector<vector<long long> >
#define vvld vector<vector<ld> >
#define vpii vector<pii>
#define vpll vector<pll>
#define ld long double
#define ll long long
#define sz(a) (ll)a.size()
#define ssortA(arr)   stable_sort(arr.begin(),arr.end())
#define ssortB(arr)   stable_sort(arr.begin(),arr.end(),greater<ll >());
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ff first
#define ss second
#define search(arr,c)  binary_search(arr.begin(),arr.end(),c)
#define pb   push_back
#define pf push_front
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define endl "\n" 
#define PI acos(-1.0)
#define GCD(a,b) __gcd(a,b)
#define popcount(x) __builtin_popcountll(x)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define r1(x) cin>>x
#define r2(x,y) cin>>x>>y
#define r3(x,y,z) cin>>x>>y>>z
#define r4(a,b,c,d) cin>>a>>b>>c>>d
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define fix(f,n) fixed<<setprecision(n)<<f<<endl
#define check(ds, a) (ds.find(a)!=ds.end()?1:0)
#define mem(arr)  memset(arr,0,sizeof(arr))
const int M=(int)1e9+7;
string s,t;
int mini=1005;
void cmp(int x){
    int c=0;
    rep(j,x,x+sz(t)){
        if(s[j]!=t[j-x])++c;
       
    }
 mini=min(c,mini);
}
int main(){
    cin>>s>>t;
    rep(i,0,sz(s)-sz(t)+1){
        cmp(i);
    }
    cout<<mini<<endl;
}

Measured memory_bytes: 3640
n = int(input())

if n == 0:
  print("2")
elif n == 1:
  print("1")
else:
  l = [2, 1, ]
  for i in range(2, 87):
    lucas = l[i-2] + l[i-1]
    if i == n:
      print(lucas)
      exit()
    else:
      l.append(lucas)


Measured memory_bytes: 3060
#include <stdio.h>
#include <iostream>

using namespace std;

int T;
int w[10][10];

int test(int r, int c) {
	for(int i=0; i<8; i++) {
		if(i == c)continue;
		if(w[r][i])return 0;
	}
	for(int i=0; i<8; i++) {
		if(i == r)continue;
		if(w[i][c])return 0;
	}
	for(int i=-7; i<8; i++) {
		if(i == 0 || r+i < 0 || r+i>7 || c-i < 0 || c-i > 7)continue;
		//cout<<r+i<<" "<<c-i<<" "<<w[r+i][c-i]<<endl;
		if(w[r+i][c-i])return 0;
	}
	for(int i=-7; i<8; i++) {
		if(i == 0 || r+i < 0 || r+i>7 || c+i < 0 || c+i > 7)continue;
		//cout<<r+i<<" "<<c-i<<" "<<w[r+i][c-i]<<endl;
		if(w[r+i][c+i])return 0;
	}
	return 1;
}

int dfs(int r) {
	if(r == 8)return 1;
	for(int c=0; c < 8 ;c++) {
		//if(r==4)cout<<r<<" "<<c<<" "<<w[r][c]<<endl;
		if(test(r, c)) {
			int f=0;
			if(w[r][c])f=1;
			w[r][c] = 1;
			if(dfs(r+1))return 1;
			if(!f)w[r][c] = 0;
		}
	}
	return 0;
}

int main() {
	int k, r, c;
	scanf("%d", &k);
	for(int i=0; i<8; i++)
		for(int j=0; j<8; j++)w[i][j] = 0;
	for(int i=0; i<k; i++) {
		scanf("%d%d", &r, &c);
		w[r][c] = 1;
	}
	dfs(0);
	for(int i=0; i<8; i++) {
		for(int j=0; j<8; j++) {
			if(w[i][j] == 0)printf(".");
			if(w[i][j] == 1)printf("Q");
		}
		puts("");
	}
	return 0;
}



Measured memory_bytes: 3152
fun main (args: Array<String>) {
  val n = readLine()!!.split(" ").map(String::toInt)
  val Ai = readLine()!!.split(" ").map(String::toInt)
  var lis = Array<Int>(n[0], {it})
  for ((i, v) in Ai.withIndex()) lis[v-1] = i+1
  for (l in lis) println("$l")
}


Measured memory_bytes: 56388
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 15;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

ll in[200050];
int main() {
	ll T, i;
	int N;
	scanf("%d %lld", &N, &T);
	for (i = 1; i <= N; i++) scanf("%lld", &in[i]);
	in[N + 1] = LL_INF;

	ll ans = 0;
	for (i = 1; i <= N; i++) ans += min(T, in[i + 1] - in[i]);
	return !printf("%lld\n", ans);
}

Measured memory_bytes: 1792
#include<stdio.h>

int main(void)
{
	int a, b, x;
	while(scanf("%d %d", &a, &b)!=EOF)
	{
		x=a+b;
		if(x<10)
		printf("1\n");
		else if(x<100)
		printf("2\n");
		else if(x<1000)
		printf("3\n");
		else if(x<10000)
		printf("4\n");
		else if(x<100000)
		printf("5\n");
		else if(x<1000000)
		printf("6\n");
		else if(x<10000000)
		printf("7\n");
	}
	
	return 0;
}


Measured memory_bytes: 2548
class Problem
  attr_accessor :a, :b, :n, :m, :h, :w, :ans, :c ,:x, :y
  def initialize
    @x,@y,@a,@b,@c = gets.to_s.split.map{ |v| v.to_i }
    @p = gets.to_s.split.map{ |v| v.to_i }.sort!.reverse!.take(x)
    @q = gets.to_s.split.map{ |v| v.to_i }.sort!.reverse!.take(y)
    @r = gets.to_s.split.map{ |v| v.to_i }
    @all = (@p + @q + @r).sort!.reverse!.take(x+y)
  end

  def solve
    puts @all.sum
  end
end

pb = Problem.new
pb.solve
# pp pb if ENV['USER'] == 'tamura'

Measured memory_bytes: 30468
#include<stdio.h>
#include<iostream>
#include<string>
#include<math.h>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<time.h>
#include<ctime>
#include<functional>
using namespace std;
typedef long long ll;
int inf = 1000000000;
template<typename T>
T GCD(T a, T b) {
	while (max(a, b) % min(a, b)) {
		if (a > b)a = a % b;
		else b = b % a;
	}
	return min(a, b);
}
template<typename T>
T LCM(T a, T b) {
	return a / GCD(a, b)*b;
}
int main() {
	int n;
	cin >> n;
	while (n >= 0) {
		if (n % 4 == 0) {
			cout << "Yes" << endl;
			return 0;
		}
		n -= 7;
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int n,A[50];

int solve(int i,int m)
{
    if(m==0)return 1;
    if(i>=n)return 0;
    int res=solve(i+1,m)||solve(i+1,m-A[i]);
    return res;
}


int main()
{
    int q,M,i;

    scanf("%d",&n);
    for (i=0;i<n;i++)scanf("%d",&A[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++)
    {
        scanf("%d",&M);
        if(solve(0,M))printf("yes\n");
        else printf("no\n");
    }

    return 0;
}


Measured memory_bytes: 2588
def dfs(s,l):
  if s!="":
    if len(s)>10 or s[0]=="0":
      return
  if s!="":
    l.append(int(s))
  for c in "0123456789":
    if s!="":
      if abs(int(s[-1])-int(c))<=1:
        dfs(s+c,l)
    else:
      if c!="0":
        dfs(s+c,l)

k=int(input())
l=[]
dfs("",l)
l.sort()
print(l[k-1])


Measured memory_bytes: 17332