akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	vector<vector<int> >dp(N, vector<int>(N, 0));
	if (N % 2 == 0) {
		for (int i = 0; i < N; i++) {
			dp[i][i] = -A[i];
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			dp[i][i] = A[i];
		}
	}
	for (int l = 2; l <= N; l++) {
		for (int i = 0; i + l - 1 < N; i++) {
			if ((l + N) % 2 == 0) {
				dp[i][i + l - 1] = max(A[i] + dp[i + 1][i + l - 1],
					A[i + l - 1] + dp[i][i + l - 1 - 1]);
			}
			else {
				dp[i][i + l - 1] = min(-A[i] + dp[i + 1][i + l - 1],
					-A[i + l - 1] + dp[i][i + l - 1 - 1]);
			}
		}
	}
	cout << dp[0][N - 1] << endl;
}

Measured memory_bytes: 70784
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<complex>
#include<unordered_map>
#define deg(x) cout<<#x<<"="<<x<<endl;
#define fd(x) for(int i=0;i<x;i++)
#define fdd(a,x) for(int i=a;i<x;i++)
#define fx(x,n) for(int i=n-1;i>=x;i--)
#define mst(x) memset(x,0,sizeof(x));
#define fi first
#define se second
#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ok "ok"
#define HH puts("");
#define ls rt<<1
#define rs rt<<1|1
#define pb(a,b) a.push_back(b);
#define FIN  freopen("1.in","r",stdin);
#define FOUT freopen("1.out","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> pss;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=1e18;
const long double eps=1e-8;
ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
const double pi=acos(-1);

ll f[202][20];
ll sum=9,n;
string s;
int sou(int g,int q){
    cout<<q;
    //s+=(char)(q+'0');
    g--;
    if(g==0) return 1;
    n-=sum;sum=0;
//    deg(n)deg(g)deg(q)
//    deg(f[2][0])
    int i=-1;
    if(q==0) i++;
    while(i<2&&q+i<10&&sum+f[g][i+q]<n) sum+=f[g][q+i++];
    //deg(i+q)
    //deg(sum)
    sou(g,i+q);
    return 0;
}

int main(){
    //TB
    fd(10) f[1][i]=1;
    for(int g=2;g<11;g++){
        f[g][0]=f[g-1][0]+f[g-1][1];
        f[g][9]=f[g-1][8]+f[g-1][9];
        fdd(1,9) f[g][i]=f[g-1][i-1]+f[g-1][i]+f[g-1][i+1];
    }
        cin>>n;
        //s="";
        sum=9;
    if(n<=9){
        cout<<n<<'\n';
        return 0;
    }
    int g=2,flag=0;
    int i=1;
    while(n&&sum<n){
        i=1;
        while(i<10&&sum+f[g][i]<n) sum+=f[g][i++];
        //deg(sum)deg(i)
        if(i==10){
            g++;
        }else{
            break;
        }
//            if(!flag) flag=1;
//            cout<<i;
//            if(g==1) break;
//            n-=sum;
//            sum=0;
//            g--;
//        }
    }
    //deg(g)deg(i)deg(sum)
        sou(g,i);
        //cout<<s;
    return 0;
}


Measured memory_bytes: 256
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-01-11 19:30:40
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#else
#define debug(_) 1728
#endif

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

  int n; cin >> n;
  vector<string> s(n); vector<int> t(n);
  for (int i = 0; i < n; ++i) cin >> s[i] >> t[i];
  string x; cin >> x;

  int ans = 0;
  bool flag = false;

  for (int i = 0; i < n; ++i) {
    if (flag) ans += t[i];
    if (s[i] == x) flag = true;
  }

  cout << ans << endl;

  return 0;
}

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


int main(void){

    long long n; cin >> n;
    long long N = n;
    long long fx = 0;

    while(n > 0){
        fx += n % 10;
        n = n / 10;
    }

    //cout << N << " " << fx << endl;

    if(N % fx){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }

    return 0;


}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>

using namespace std;
#define ll          long long
#define endl        "\n"
#define inf         10000000002
#define pb          push_back
#define pf          push_front
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(a)      a.begin(),a.end()
#define mp          make_pair
#define MAX         100
#define yes         cout<<"YES"<<endl
#define no          cout<<"NO"<<endl
#define bye         return 0

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

int main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cout.tie(NULL);
      //freopen("inputNew.txt", "r", stdin);

      string a,b;
      cin>>a;
      cin>>b;
      ll mv=0;
      for(int i=0; a[i]!='\0'; i++){
            if(a[i]!=b[i]) mv++;
      }
      cout<<mv<<endl;


      bye;
}


Measured memory_bytes: 3840
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int x,y,i,j,k,ii,map[16][16][2],data[16][16];
	int n,p;
	int x1,y1,x2,y2;
	scanf("%d",&n);
	for(i=0;i<n;i++)	{
		scanf("%d %d",&x,&y);
		for(j=0;j<=y;j++)	{
			for(k=0;k<=x;k++)	{
				map[j][k][0]=1;
				map[j][k][1]=1;
				data[j][k]=0;
			}
		}
		scanf("%d",&p);
		
		for(j=0;j<p;j++)	{
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			if(x1>x2)	swap(x1,x2);
			if(y1>y2)	swap(y1,y2);
			if(x1==x2)	map[y1][x1][1]=0;
			if(y1==y2)	map[y1][x1][0]=0;
		}
		data[0][0]=1;
		for(j=0;j<=y;j++)	{
			for(k=0;k<=x;k++)	{
				if(k!=x)	{
					if(map[j][k][0]==1)	{
						data[j][k+1]+=data[j][k];
					}
				}
				if(j!=y && map[j][k][1]==1)	{
					data[j+1][k]+=data[j][k];
				}
			}
		}
		if(data[y][x]!=0)	{
			printf("%d\n",data[y][x]);
		}
		else {
			printf("Miserable Hokusai!\n");
		}
	}
	return 0;
}


Measured memory_bytes: 1040
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
#define mod 1e9 + 7;
ll gcd(ll x, ll y)
{
	ll r;
	while ((r = x % y) != 0)
	{
		x = y;
		y = r;
	}
	return y;
}
ll lcm(ll x, ll y)
{
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x * y);
}


int main()
{
	ios_base::sync_with_stdio(false);

	ll a,b,c,n, h, ret = 0;
	string s;
	cin >> n;
	rep(i, n+1) {
		int cnt = 0;
		if (i % 2 == 0) continue;
		else {
			REP(j, 1, n+1) {
				if (i % j == 0)  cnt++;
			}
			if (cnt == 8) ret++;
		}
	}
	cout << ret << endl;
	return 0;
}

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

max = 1000000
min = -1000000 

num = Array.new

k.times{ |i|
    if ( min <= x-k+i+1 ) then num.push(x-k+i+1) end

}

(k-1).times{ |i|
    if ( max >  x+i+1 ) then num.push(x+i+1) end
}

num.each{ |i|
    print(i)
    if i != num[-1] then print(" ") end
}
print("\n")

Measured memory_bytes: 1788
import math
a, b, h, m = map(int, input().split())
H = 60 * h + m

h_fra = H / 720
m_fra = m / 60

theta = (h_fra - m_fra) * 2 * math.pi
c = math.sqrt(a**2 + b**2 - 2 * a * b * math.cos(theta))
print(c)

Measured memory_bytes: 9368
#include<bits/stdc++.h>
#define ll long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
const int N=200005;
const ll mod=998244353;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0',ch=getchar();}
    return x*f;
}
int n,m,l[N],r[N];
ll f[N],g[15];
void solve()
{
	n = read(); m = read();
	for(int i=1; i<=m; i++) {
		l[i] = read(); r[i] = read();
	}
	ll ans = 0; f[1] = 1;
	for(int i=2; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(i - l[j] >= 1) g[j] += f[i - l[j]];
			if(i - r[j] > 1) g[j] -= f[i - r[j] - 1];
			g[j] = (g[j] + mod) % mod;
			f[i] = (f[i] + g[j]) % mod;
		}
	}
	cout << f[n] << endl;
}
int main()
{
	int T=1;
	while(T--) solve();
}

Measured memory_bytes: 5176
#include <cstdio>
#include <bitset>
using namespace std;
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
bitset<702> f;
int e[702][702], vis[702], q[702], cnt[3];
int main(){
	register int n, m, i, j, u, v, qh, qt, ans;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) if (i != j) e[i][j] = 1;
	for (i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		e[u][v] = e[v][u] = 0;
	}
	f.set(0);
	for (i = 1; i <= n; ++i) if (vis[i] == 0) {
		q[qh = qt = 0] = i;
		vis[i] = 1;
		cnt[1] = cnt[2] = 0;
		while (qh <= qt) {
			u = q[qh];
			++qh;
			++cnt[vis[u]];
			for (v = 1; v <= n; ++v) if (e[u][v]) {
				if (vis[v]) {
					if ((vis[u] ^ vis[v]) != 3) {
						puts("-1");
						return 0;
					}
				}
				else {
					vis[v] = vis[u] ^ 3;
					q[++qt] = v;
				}
			}
		}
		f = f << cnt[1] | f << cnt[2];
	}
	ans = n * n;
	for (i = 1; i <= n; ++i) if (f[i]) {
		cmin(ans, i * (i - 1) + (n - i) * (n - i - 1) >> 1);
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 2048
#include<map>
#include<queue>
#include<utility>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<numeric>
#include<functional>
#include<string>
#include<iostream>
using namespace std;
const long long int one = 1;
const long long int big = (one<<40);
typedef long long int llint;
bool solve(void){
	int h,i,N,ans,gen,up,down,moto,kesu,Ckesu;
	int C[10005];
	scanf("%d",&N);
	if(N==0){return false;}
	ans=N;
	C[0]=4;
	for(i=1;i<=N;i++){
		scanf("%d",&C[i]);
	}
	C[N+1]=4;
	for(h=1;h<=N;h++){
		moto=C[h];
		C[h]=1;
		up=h;
		down=h+1;
		gen=0;
		while(C[up]==C[down]){
			kesu=0;
			Ckesu=C[up];
			while(Ckesu==C[up]){
				up--;kesu++;
			}
			while(Ckesu==C[down]){
				down++;kesu++;
			}
			if(kesu<4){ break; }
			gen+=kesu;
		}
		ans=min(ans,N-gen);
		C[h]=2;
		up=h;
		down=h+1;
		gen=0;
		while(C[up]==C[down]){
			kesu=0;
			Ckesu=C[up];
			while(Ckesu==C[up]){
				up--;kesu++;
			}
			while(Ckesu==C[down]){
				down++;kesu++;
			}
			if(kesu<4){ break; }
			gen+=kesu;
		}
		ans=min(ans,N-gen);
		C[h]=3;
		up=h;
		down=h+1;
		gen=0;
		while(C[up]==C[down]){
			kesu=0;
			Ckesu=C[up];
			while(Ckesu==C[up]){
				up--;kesu++;
			}
			while(Ckesu==C[down]){
				down++;kesu++;
			}
			if(kesu<4){ break; }
			gen+=kesu;
		}
		ans=min(ans,N-gen);
		C[h]=moto;
	}
	printf("%d\n",ans);
	return true;
}
int main(void){
	while(solve()){}
	return 0;
}

Measured memory_bytes: 3224
#include<cstdio>  /**!!!  注意此??数据一般?大 使用scanf printf?出?入*/
#include<algorithm>
#include<vector>//使用??数?存??果

using namespace std;

class Node{//?的?点
public:
    int location;//表示?点在数?中的索引
    int p,l,r;//
    Node(){}
};

class Point{
public:
    int id,x,y;//x,y?坐?
    Point(){}
    Point(int id,int x,int y):id(id),x(x),y(y){}
    bool operator < (const Point &p) const{
        return id<p.id;//用于按点的?入?序?出
    }
};

static const int MAX=1000000;//数?大小 用数???二叉搜索?
static const int NIL=-1;//定???

int N;//??点的数量
Point P[MAX];//存?点的集合
Node T[MAX];//??二叉搜索?的数?
int np;//生出??的索引??
int root;//存?根?点的索引
vector<Point> ans;//存?答案的数?

bool lessX(const Point&p1,const Point&p2){return p1.x<p2.x;}//按照x排序?使用
bool lessY(const Point&p1,const Point&p2){return p1.y<p2.y;}//按照y排序?使用

void init(){//初始化
    np=0;
    ans.clear();//清零
}
int makeKDTree(int l,int r,int depth){/**K代表几?的搜索  !!!不包括r*/
    if(!(l<r))
        return NIL;
    int mid=(l+r)/2;//?次都从中点?始
    int t=np++;//??移?
    if(depth%2==0){//?数?偶数?
        sort(P+l,P+r,lessX);//按照x升序排序 不包括r
    }
    else{
        sort(P+l,P+r,lessY);//当?数?奇数? 按照y升序排序 不包括r
    }
    T[t].location=mid;//??当前?点在数?P中的位置
    T[t].l=makeKDTree(l,mid,depth+1);//生出左子?
    T[t].r=makeKDTree(mid+1,r,depth+1);//生出右子?

    return t;//返回?位置在P中的索引
}

void find(int v,int sx,int tx,int sy,int ty,int depth,vector<Point> &ans){
    int x=P[T[v].location].x;//v?点在数?P中的横坐?x
    int y=P[T[v].location].y;//v?点在数?P中的?坐?

    if(sx<=x&&x<=tx&&sy<=y&&y<=ty){
        ans.push_back(P[T[v].location]);//如果在范?内就放入答案数?中
    }

    if(depth%2==0){//此??按照x升序排序
        if(T[v].l!=NIL){
            if(sx<=x) find(T[v].l,sx,tx,sy,ty,depth+1,ans);
        }
        if(T[v].r!=NIL){
            if(x<=tx) find(T[v].r,sx,tx,sy,ty,depth+1,ans);
        }
    }
    else{
        if(T[v].l!=NIL)
            if(sy<=y) find(T[v].l,sx,tx,sy,ty,depth+1,ans);
        if(T[v].r!=NIL)
            if(y<=ty) find(T[v].r,sx,tx,sy,ty,depth+1,ans);
    }

}

int main(void){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d %d",&P[i].x,&P[i].y);
        P[i].id=i;
    }
    int q;
    root=makeKDTree(0,N,0);
    scanf("%d",&q);
    for(int j=0;j<q;j++){
        int sx,tx,sy,ty;
        scanf("%d %d %d %d",&sx,&tx,&sy,&ty);
        init();
        find(root,sx,tx,sy,ty,0,ans);
        sort(ans.begin(),ans.begin()+ans.size());
        for(int i=0;i<ans.size();i++)
            printf("%d\n",ans[i].id);
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 15828
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


def main():
    S = input()
    for i in range(len(S)):
        t = S[:-i - 1]
        if len(t) % 2 == 0:
            if t[:len(t) // 2] == t[len(t) // 2:]:
                print(len(t))
                return


if __name__ == '__main__':
    main()


Measured memory_bytes: 3944
# abc168_a.py
# https://atcoder.jp/contests/abc168/tasks/abc168_a

# A - ∴ (Therefore) /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点: 100点

# 問題文
# いろはちゃんは、人気の日本製ゲーム「ÅtCoder」で遊びたい猫のすぬけ君のために日本語を教えることにしました。
# 日本語で鉛筆を数えるときには、助数詞として数の後ろに「本」がつきます。この助数詞はどんな数につくかで異なる読み方をします。
# 具体的には、999以下の正の整数 N について、「N本」と言うときの「本」の読みは
#     Nの 1 の位が 2,4,5,7,9のとき hon
#     Nの 1 の位が 0,1,6,8のとき pon
#     Nの 1 の位が 3のとき bon
# です。
# Nが与えられるので、「N本」と言うときの「本」の読みを出力してください。

# 制約
#     Nは 999以下の正の整数

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N

# 出力
# 答えを出力せよ。

# 入力例 1
# 16

# 出力例 1
# pon

# 16の 1 の位は 6なので、「本」の読みは pon です。

# 入力例 2
# 2

# 出力例 2
# hon

# 入力例 3
# 183

# 出力例 3
# bon


global FLAG_LOG
FLAG_LOG = False


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


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

    amari = N % 10

    result = 'hon'
    if amari == 3:
        result = 'bon'
    elif amari in [0, 1, 6, 8]:
        result = 'pon'

    return [result]


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


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['16']
        lines_export = ['pon']
    if pattern == 2:
        lines_input = ['2']
        lines_export = ['hon']
    if pattern == 3:
        lines_input = ['183']
        lines_export = ['bon']
    return lines_input, lines_export


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


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

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

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


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


Measured memory_bytes: 9288
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <math.h>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}*/

#define MAX 300

int dp[MAX * MAX + 1];
int h, w;
int d;
vector<vector<int>>a(MAX + 1, vector<int>(MAX + 1));

vector<pair<int, int>> pa(MAX * MAX + 1);

int rec(int i) {
	if (dp[i] != 0) {
		return dp[i];
	}

	if (i + d > h * w) {
		return 0;
	}

	dp[i] = abs(pa[i + d].first - pa[i].first) + 
		abs(pa[i + d].second - pa[i].second) +
		+ rec(i + d);
	return dp[i];

}

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

	cin >> h >> w >> d;
	rep(i, h) {
		rep(j, w) {
			cin >> a[i][j];
			pa[a[i][j]].first = i;
			pa[a[i][j]].second = j;
		}
	}
	int q;
	cin >> q;
	vector<int> l(q), r(q);
	rep(i, q) {
		cin >> l[i] >> r[i];
	}

	// dpだわこれ
	// メモ型の方がよさそう

	// iから始まるときの消費する魔法

	rep(i, h * w) {
		rec(i + 1);
	}

	rep(i, q) {
		cout << dp[l[i]] - dp[r[i]] << endl;
	}

	return 0;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n; 
  auto isprime = [](auto k){
    int div;
    div = 0;
    for(int j=2 ; j<k; j++){
      if(k % j == 0){
        div = j;
      }
    }
    if (div==0 || k==2){
      return(true);
    }
    else{
      return (false);
    }
  };
  int ans = n;
  while (!isprime(ans)){
    ans +=1;
  }
  cout << ans;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

int dx[] = { -1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};


int main() {

	long long w, h, x, y; cin >> w >> h >> x >> y;
	cout << fixed << setprecision(15) ;
	cout << ((w * h) / 2.0L) << " ";

	cout <<	(
	         ((w & 1) == 0) and
	         ((h & 1) == 0) and
	         (x == (w >> 1)) and
	         (y == (h >> 1))
	     );

	return 0;
}

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

void printv(vector<ll> v) {
  for (ll i : v)
    cout << i << endl;
}

int main() {
	string s;
	cin>>s;
	int l=s.size()/2-1;
	while(true){
		string s1=s.substr(0,l);
		string s2=s.substr(l,l);
		if(s1==s2){
			cout<<l*2<<endl;
			break;
		}
		l--;
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<set>
#include<vector>
using namespace std;

#define INF 1<<21
#define MOD 1000000007

int main(){
    int n;
    long long ans=INF;
    long long sum=0;
    int a[101];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=-100;i<=100;i++){
        sum=0;
        for(int j=0;j<n;j++){
            sum+=(i-a[j])*(i-a[j]);
        }
        ans=min(sum,ans);
    }
    cout<<ans<<endl;

    return 0;
}


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

int main()
{
  string s, t;
  cin >> s >> t;
  s += t;
  double n = (double)stoi(s);
  n = sqrt(n);
  if(ceil(n) == floor(n)) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

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


int main(){
  ll N, T, A;
  cin >> N >> T >> A;
  vector<ll> H(N);

  rep(i, N) cin >> H[i];

  rep(i, N) H[i] = abs(T*1000 - H[i]*6 - A*1000);

  auto index = min_element(H.begin(), H.end());
  int ans = distance(H.begin(), index);
  cout << ans + 1 << endl;
}


Measured memory_bytes: 3552
use std::io::Read;

fn main() {
    let mut buf = String::new();

    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let squares: Vec<Vec<u32>> = vec![
        (0..n)
            .map(|_| iter.next().unwrap().parse().unwrap())
            .collect(),
        (0..n)
            .map(|_| iter.next().unwrap().parse().unwrap())
            .collect(),
    ];

    let mut answers = Vec::new();
    for i in (0..n) {
        answers.push(
            squares[0][0..(i + 1)].iter().fold(0, |acc, num| acc + num)
                + squares[1][i..].iter().fold(0, |acc, num| acc + num),
        );
    }

    println!("{}", answers.iter().max().unwrap());
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

struct edge{
    int from, to, cost;
    edge() {}
    edge(int from, int to, int cost) :from(from), to(to), cost(cost) {}
};

int N;
int M;
edge es[900010];
ll L;
ll d[310][310];


void build(){
    for(int i = 1; i <= N; i++){
        for(int j =1; j <= N; j++){
            d[i][j] = linf;
        }
    }

    for(int i = 0; i < M; i++){
        edge e = es[i];
        d[e.from][e.to] = e.cost;
        d[e.to][e.from] = e.cost;
    }

    for(int k = 1;k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                chmin(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            d[i][j] = (d[i][j] <= L ? 0 : linf);
        }
    }

    for(int k = 1;k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                chmin(d[i][j], d[i][k] + d[k][j] + 1);
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> L;
    for(int i = 0; i < M; i++){
        int A, B, C;
        cin >> A >> B >> C;
        es[i] = {A, B, C};
    }

    build();

    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int s, t;
        cin >> s >> t;
        cout << (d[s][t] == linf ? -1 : d[s][t]) << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
 
ll pwr(ll base, ll p, ll mod=MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}
 
 
ll gcd(ll a, ll b){
    if(b == 0)  return a;
    return gcd(b, a%b);
}



int n;
string str;


int solve(int ch){
	string temp = str;
	int len = n;
	while(len > 1){

		bool ok = true;
		for(int i=0;i<len;i++)
			if(temp[i]-'a' != ch)
				ok = false;
		if(ok)	break;

		string newtemp = temp.substr(0, len-1);
		for(int i=0;i<len-1;i++)
			if(temp[i]-'a' == ch)
				newtemp[i] = temp[i];
			else if(temp[i+1]-'a' == ch)
				newtemp[i] = temp[i+1];
			else
				newtemp[i] = temp[i];
		temp = newtemp;
		len--;				
	}

	if((int)temp.length() == 1 && temp[0]-'a' != ch)	return MOD;
	return n - len;
}


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

    cin>>str;
    n = (int)str.length();

    int ans = MOD;
    for(int ch=0;ch<26;ch++)
    	ans = min(ans, solve(ch));

// cout<<solve('v'-'a')<<endl;

    cout<<ans;
    return 0;
}












Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  lines.push(line);
});

reader.on('close', () => {
 var sandw = lines[0].split(' ');
 var s = Number(sandw[0]);
 var w = Number(sandw[1]);

 if(s <= w){
   console.log("unsafe");
 }else{
   console.log("safe");
 }

 
});

Measured memory_bytes: 30072
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};

//全二点間の距離
//ヨ i,d[i][i]<0なら負の閉路
int MAX_dist=1e9+7;
int V=0;
vector<vector<int>> d(0,vector<int>(0,MAX_dist));//d[x][y]:=x->yのcost,枝が無ければMAX_dist,d[i][i]=0

void init(int n){
    d=vector<vector<int>>(n,vector<int>(n,MAX_dist));
    rep(i,n) d[i][i]=0;
    V=n;
}

void warshall(){
    rep(k,V){
        rep(i,V){
            if(d[i][k]==MAX_dist) continue;
            rep(j,V){
                if(d[k][j]==MAX_dist) continue;
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int h,w;
    cin>>h>>w;
    vector<string> a(h);
    rep(i,h) cin>>a[i];
    init(h*w);
    rep(i,h-1)rep(j,w){
        if(a[i][j]=='.'&&a[i+1][j]=='.'){
            d[i*w+j][i*w+j+w]=1;
            d[i*w+j+w][i*w+j]=1;
        }
    }
    rep(i,w-1)rep(j,h){
        if(a[j][i]=='.'&&a[j][i+1]=='.'){
            d[j*w+i][j*w+i+1]=1;
            d[j*w+i+1][j*w+i]=1;
        }
    }
    warshall();
    int ans=0;
    rep(i,h*w)rep(j,h*w){
        if(d[i][j]!=MAX_dist) ans=max(ans,d[i][j]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    using namespace std;

    struct Node{
      int key;
      Node *prev;
      Node *next;
    };

    Node *head;

    Node *listSearch(int key){
      Node *cur = head->next;
      while(cur != head && cur->key != key){
        cur = cur->next;
      }
      return cur;
    }

    void init(){
      head = new Node;
      head->prev = head;
      head->next = head;
    }

    void printlist(){
      Node *cur = head->next;
      int isf = 0;
      while(1){
        if(cur == head)break;
        if(isf++ > 0)printf(" ");
        printf("%d",cur->key);
        cur = cur->next;
      }
      printf("\n");
    }

    void insert(int key){
      Node *x = new Node;
      x->key = key;
      x->next = head->next;
      head->next->prev = x;
      head->next = x;
      x->prev = head;
    }

    void deleteNode(Node *t){
      if(t == head)return;
      t->prev->next = t->next;
      t->next->prev = t->prev;
      free(t);
    }

    void deleteFirst(){
      deleteNode(head->next);
    }

    void deleteLast(){
      deleteNode(head->prev);
    }

    void deletekey(int key){
      deleteNode(listSearch(key));
    }

    int main(){
      int key,n,i;
      char com[20];
      scanf("%d",&n);
      init();
      for(i = 0;i < n; i++){
        scanf("%s%d",com,&key);
        if(com[0] == 'i'){insert(key);}
        else if(com[0] == 'd'){
          if(strlen(com) > 6){
            if(com[6] == 'F')deleteFirst();
            else if(com[6] == 'L')deleteLast();
          }
          else{
            deletekey(key);
          }
        }
      }
      printlist();
      return 0;
    }

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;

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

    for(int i = 0; i < n; i++) cin >> arr[i];
    
    for(int i = k; i < n; i++) {
        if(arr[i] > arr[i-k]) cout << "Yes\n";
        else cout << "No\n";
    }
    
    return 0;
}

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


int main()
{
	int N,K,Q ;
	cin >> N >> K >> Q;

	vector<int> A(Q);
	for (int &a : A)
	{
		cin >> a;
	}

	vector<int> B(N, K);
	for (int& a : A)
	{
		B.at(a - 1) += 1;
	}
	for (int&b : B)
	{
		if (b - Q > 0)
			cout << "Yes";
		else
			cout << "No";
		cout << "\n";
	}

}

Measured memory_bytes: 1408
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


m=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


def comb(n, k, mod):
	a=1
	b=1
	for i in range(1,k+1):
		a*=i
		b*=n-i+1
		a%=m
		b%=m
	
	return (b*pow(a,m-2,m))%m
	

def main():
	n,a,b=map(int,input().split())
	ans=pow(2,n,m)-1-comb(n,a,m)-comb(n,b,m)
	ans%=m
	print(ans)
	
if __name__ == "__main__":
	main()


Measured memory_bytes: 38512
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;


struct K {
  ll t, d;
};
bool operator<(const K& k1, const K& k2) {
  return k1.d < k2.d;
}
bool operator>(const K& k1, const K& k2) {
  return k1.d > k2.d;
}

K vs[100000+10];
int cnt[100000+10];

int main(void) {
  int n, k;
  scanf("%d%d", &n, &k);
  REP(i, n) {
    scanf("%lld%lld", &vs[i].t, &vs[i].d);
  }
  sort(vs, vs + n);
  reverse(vs, vs + n);
  priority_queue<K, vector<K>, greater<K> > q; // 小さい順に出てくる
  ll res = 0;
  ll x = 0;
  ll sum = 0;
  REP(i, n) {
    const K& cur = vs[i];
    if(i < k) {
      q.push(cur);
      cnt[cur.t]++;
      if(cnt[cur.t] == 1) {
        ++x;
      }
      sum += cur.d;
      res = max(res, sum + x * x);
      continue;
    }
    if(cnt[cur.t] > 0) { // 新しい種類じゃないなら採用する価値無し
      continue;
    }
    while(!q.empty()) {
      K tmp = q.top(); q.pop();
      if(cnt[tmp.t] > 1) { // 2個以上あるやつ以外は入れ替えちゃだめ。
        --cnt[tmp.t];
        sum -= tmp.d;
        ++cnt[cur.t];
        ++x;
        sum += cur.d;
        res = max(res, sum + x * x);
        break;
      }
    }
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 4468
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_5_B
  * Structured Program I - Print a Frame
  */
object Main {
  def main(args: Array[String]): Unit = {
    Iterator.continually(io.StdIn.readLine()).takeWhile(_ != null).map(_.split(" ").map(_.toInt))
      .map { case Array(h, w) => (h, w) }
      .takeWhile(_ != (0, 0))
      .map { case (h, w) => createAFrame(h, w) }
      .foreach(_.foreach(println))
  }

  def createAFrame(h: Int, w: Int): Seq[String] = {
    (1 to h).map {
      case y if y == 1 || y == h => "#" * w
      case _ => "#" + "." * (w - 2) + "#"
    } :+ ""
  }
}

Measured memory_bytes: 45460
use std::io::Read;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();

    const INF: usize = 10000;
    let mut c: Vec<usize> = vec![INF; n + 1];
    for _ in 0..m {
        let s: usize = itr.next().unwrap().parse().unwrap();
        let t: usize = itr.next().unwrap().parse().unwrap();
        if c[s] != INF && c[s] != t {
            println!("-1");
            return;
        }
        c[s] = t;
    }
    if c[1] == 0 && n != 1 {
        println!("-1");
        return;
    }

    for i in 1..n + 1 {
        if c[i] == INF {
            if i == 1 && n != 1 {
                print!("1");
            } else {
                print!("0");
            }
        } else {
            print!("{}", c[i]);
        }
    }
}


Measured memory_bytes: 4352
#include<cstdio>
#include<algorithm>
using namespace std;

int value[100000];
int dp[100000];

int main(){

  int n;
  int m;

  while(~scanf("%d%d",&n,&m)){
  for(int i=0;i<m;i++) scanf("%d",&value[i]);
  for(int i=0;i<=n;i++){
  dp[i]=i+1;
  }

  dp[0]=0;

  for(int i=0;i<=n;i++)
      for(int j=0;j<m;j++){
          if(i-value[j]>=0)
            dp[i] = min(dp[i],dp[i-value[j]]+1);
      }

   //for(int i=0;i<n;i++) printf("%d ",dp[i]);


  printf("%d\n",dp[n]);
  }
  return 0;
}

Measured memory_bytes: 1224
#include<iostream>
#include<cmath>
#include<cassert>
using namespace std;
  
int calc(int);
long long cnt;
int X;
void insertionSort(int A[],int n,int g){
  int v,j;
  for(int i=g;i<n;i++){
    v=A[i];
    j=i-g;
    while(j>=0&&A[j]>v){
      A[j+g]=A[j];
      j=j-g;
      cnt++;
    }
    A[j+g]=v;
  }
}
 
int Gt[1000000],gt=0;
int  G[1000000], g=0;
 
void shellSort(int A[],int n){
  
 
  int Z =pow(n,1.5),flg,y;
  X=n;
  cnt=0;
 
  for(int i=n;i>=1;i--){
    if(n%i==0){
      Gt[gt++]=i;
      //cout<<i<<" - "<<endl;
    }else{
      if(i*i<=n&&n<=(i+1)*(i+1))Gt[gt++]=y=i;
    }
  }
   
  for(int i=0;i<gt;i++){
    if(i%2==1||i==y){
    
      G[g++]=Gt[i];
    }
  }
  G[g++]=1;
   
  int ng;
  while(1){
    if(g<100)break;
    ng=0;
    for(int i=0;i<g;i++){
      if(i==y||i%2==1){
    G[ng++]=G[i];
      }
    }
    g=ng;
  }
  for(int i=0;i<g;i++){
    insertionSort(A, n,G[i]);
  }
   
  cout<<g<<endl;
  for(int i=0;i<g;i++){
    if(i)cout<<' ';
    cout<<G[i];
  }
  cout<<endl;
  cout<<cnt<<endl;
   
  assert(g<100);
  assert(cnt<Z);
  //cout<<cnt<<" cnt"<<endl;
  //cout<<Z<<" Z"<<endl;
  //cout<<(int)pow(n,1.5)<<endl;
}
  
  
int main(){
  
  int n;
  int A[1000000];
  
  cin>>n;
  for(int i=0;i<n;i++)cin>>A[i];
    
    
  shellSort(A,n);
  
  for(int i=0;i<n;i++){
    cout<<A[i]<<endl;
  }
  
  return 0;
}
  
int calc(int n){
  for(int i=sqrt(n);i>=0;i--){
    if(n%i==0)return n/i;
  }
}

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

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

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

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

//------------------
using pii = pair<int,int>;
template<class T> inline bool chmax(T& a, T b) {if(a<b) {a=b;return true;} return false;}

struct LeastCommonSubsequence {
    pair<int, string> LCS(string& s, string& t, bool return_str = false) {
        ll ns = s.size(), nt = t.size();
        vector<vector<int>> dp(ns+1, vector<int>(nt+1));
        vector<vector<pii>> prev;
        if ( return_str ) prev.assign(ns+1, vector<pii>(nt+1, pii(-1,-1)));
        for ( int i = 0; i < ns; i++ ) {
            for ( int j = 0; j < nt; j++ ) {
                if ( s[i] == t[j] ) {
                    if ( chmax(dp[i+1][j+1], dp[i][j] + 1) ) {
                        if ( return_str ) prev[i+1][j+1] = pii(i,j);
                    }
                }
                if ( chmax(dp[i+1][j+1], dp[i+1][j]) ) {
                    if ( return_str ) prev[i+1][j+1] = prev[i+1][j];
                }
                if ( chmax(dp[i+1][j+1], dp[i][j+1]) ) {
                    if ( return_str ) prev[i+1][j+1] = prev[i][j+1];
                }
            }
        }
        string r = "";
        if ( return_str ) {
            auto p = prev[ns][nt];
            while ( p.first >= 0 ) {
                r.push_back(s[p.first]);
                p = prev[p.first][p.second];
            }
            reverse(r.begin(), r.end());
        }
        return pair<int,string>(dp[ns][nt], r);
    }
};

string solve() {
    string S, T;
    cin >> S >> T;
    LeastCommonSubsequence lcs;
    string ans = lcs.LCS(S,T,true).second;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 106112
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main()
{
	int n, b[100], sum = 0, i;
	cin >> n;
	for(i = 0; i < n-1; i++)
		cin >> b[i];
	sum += b[0];
	for(i = 0; i < n-2; i++)
	{
		if(b[i] <= b[i+1])
			sum += b[i];
		if(b[i] > b[i+1])
			sum += b[i+1];
	}
	sum += b[n-2];
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;

class Solve
{
    static void Main(string[] args) {
        _ = Console.ReadLine();
        var S = Console.ReadLine();
        var x = 0;
        var answer = 0;
        foreach (var let in S) {
            x += let == 'I' ? 1 : -1;
            answer = Math.Max(answer, x);
        }
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();
    }
}

Measured memory_bytes: 25860
import sys

nyuukyosha = []

for tou in range(4):
	nyuukyosha.append([])
	for kai in range(3):
		nyuukyosha[tou].append([])
		for heya in range(10):
			nyuukyosha[tou][kai].append(0)

n = int(raw_input())

for i in range(n):
	data = map(int, raw_input().split())
	a = data[0] - 1
	b = data[1] - 1
	c = data[2] - 1
	nyuukyosha[a][b][c] += data[3]

for tou in range(4):
	for kai in range(3):
		for heya in range(10):
			sys.stdout.write(" {:}".format(nyuukyosha[tou][kai][heya]))
		print("")
	if tou < 3:
		print("####################")

Measured memory_bytes: 6420
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};

#[allow(unused_imports)]
use std::iter::FromIterator;

#[allow(unused_macros)]
macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        min($x, min!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($z: expr),+) => {{
        max($x, max!($($z),*))
    }}
}

#[allow(unused_macros)]
macro_rules! get { 
    ([$t: ty]) => { 
        { 
            let mut line = String::new(); 
            stdin().read_line(&mut line).unwrap(); 
            line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    };
    ([$t: ty];$n: expr) => {
        (0..$n).map(|_|get!([$t])).collect::<Vec<_>>()
    };
    ($t: ty) => {
        {
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t: ty),*) => {
        { 
            let mut line = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
    ($t: ty; $n: expr) => {
        (0..$n).map(|_|get!($t)).collect::<Vec<_>>()
    };
    ($($t: ty),*; $n: expr) => {
        (0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! debug { 
    ($($a: expr),*) => { 
        println!(concat!($(stringify!($a)," = {:?}, "),*), $($a),*);
    } 
}

const BIG_STACK_SIZE: bool = true;

#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}

#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

fn solve() {
    let _n = get!(usize);
    let s = get!(String);

    let mut vec = vec![0u64; 26];
    for c in s.chars() {
        vec[(c as u8 -'a' as u8) as usize] += 1;
    }
    let vec = vec.into_iter().filter(|e| *e != 0).collect::<Vec<_>>();

    let mut count = vec[0];
    for i in 1..(vec.len()) {
        count = (vec[i]*(1+count) + count) % 1000000007;
    }
    println!("{}", count);
}


Measured memory_bytes: 8572
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <ctype.h>
using namespace std;
typedef long long LL;
LL i,j,k,n,m;
LL mod=1000000007;
string s;

int main() {
  cin >> n >> k;
  cin >> s;
  s[k-1] = tolower(s[k-1]);
  cout << s << endl;
  return 0;
}


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

int main(int argc, const char * argv[]) {
    // insert code here...
    double a,b;
    int C;
    scanf("%lf %lf %d",&a,&b,&C);
    
    printf("%f\n",a*b*sin(M_PI * C / 180)/2);
    printf("%f\n",a+b+sqrt(a*a+b*b-2*a*b*cos(M_PI*C/180)));
    printf("%f\n",b*sin(M_PI * C / 180));
    
    return 0;
}

Measured memory_bytes: 700
N, M = map(int, input().split())
S = ['a'] * (N+1)
for i in range(M):
    s, c = list(map(int, input().split()))
    if S[s] != 'a' and S[s] != str(c):
        print(-1)
        exit()
    S[s] = str(c)
if S[1] == '0' and N > 1:
    print(-1)
    exit()
for i in range(1, N+1):
    if S[i] == 'a':
        if i == 1 and N > 1:
            S[i] = '1'
        else:
            S[i] = '0'
print(int(''.join(S[1:])))


Measured memory_bytes: 61940
#include <stdio.h>
#define N 100000

int n, m, data[N], tmp[N];

void MergeSort(int data[], int left, int right){
  int mid, i, j, k;
  if(left >= right) return;
  mid = (left + right) / 2;
  MergeSort(data, left, mid);
  MergeSort(data, mid+1, right);
  for(i=left;i<=mid;i++) tmp[i] = data[i];
  for(i=mid+1, j=right;i<=right;i++, j--) tmp[i] = data[j];
  i = left;
  j = right;
  for(k=left;k<=right;k++){
    if(tmp[i] <= tmp[j]) data[k] = tmp[i++];
    else data[k] = tmp[j--];
  }
}

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

main(){
  int i, in, ans = 0;
  scanf("%d", &n);
  for(i=0;i<n;i++){
    scanf("%d", &data[i]);
  }
  MergeSort(data, 0, n-1);
  scanf("%d", &m);
  for(i=0;i<m;i++){
    scanf("%d", &in);
    if(find(in)) ans++;
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 0
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

int main() {
  vector<int> a(5);
  int ret = 0, best = INF;
  for (int i = 0; i < 5; ++i) {
    scanf("%d", &a[i]);
    ret += (a[i] + 9) / 10 * 10;
    int cur = a[i] % 10;
    if (cur == 0) cur = 10;
    best = min(best, cur);
  }
  printf("%d\n", ret - 10 + best);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        long n ,x;
        cin >> n >> x;
        long ans = 1;
        long t , l;
        t = 0;
        for(int i = 0 ; i < n ; i++ ){
            cin >> l;
            t += l;
            if(t > x){
                break;
            }else{
                ans += 1;
            }
        }
        
        cout << ans << endl;
        
        return 0;
    }

Measured memory_bytes: 256