akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
     
    public class Main{
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int M = sc.nextInt();
            int[] path_count  = new int[N];
            for(int i=0;i<M;i++){
                path_count[sc.nextInt()-1]++;
                path_count[sc.nextInt()-1]++;
            }
            for(int path:path_count)
                System.out.println(path);
        }
    }

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef long long ll;
stack<char> sta;

int main(){
    string s, t;
    cin >> s >> t;
    int cnt = 0;
    for(int i=0; i<s.size(); ++i){
        if(s[i]!=t[i]){cnt++;}
    }
    cout << cnt << endl;
    return 0;
}

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

using namespace std;
mt19937_64 rng(58);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    long long ans = 1;
    bool larger = false;
    for (int i=0; i<n; i++) {
        long long a;
        cin >> a;
        if (ans && a >= (1000000000000000001ll) / ans + (1000000000000000001ll % ans > 0)) {
            larger = true;
        } else {
            ans *= a;
        }
    }
    if (ans != 0 && larger) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }
}

Measured memory_bytes: 3576
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long int;
using ULL = unsigned long long;

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    int cnt = 0;
    for (int i = min(a, b); i >= 1; i--) {
        if ((a % i == 0) and (b % i == 0)) {
            cnt++;

            if (cnt == k) {
                cout << i << endl;
                return 0;
            }
        }
    }
}


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

using namespace std;

int main(void){
    int N;
    cin>>N;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    int dict[100005];
    for(int i=0;i<N;i++){
        dict[A[i]-1]=i+1;
    }
    for(int i=0;i<N;i++){
        cout<<dict[i]<<endl;
    }
    return 0;
}

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n;
	vector<int> a(n);
	for (int i=0; i<n; i++) cin>>a[i];
	sort(a.begin(), a.end());
	cout << a.back()-a.front() << endl;
	return 0;
}


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

const int D=365;
int csum;
int c[26];
int s[D][26];
int last[26];

set<int>se[26];

int ans[D];

int cur_score;

int score(){
	memset(last,-1,sizeof(last));
	int sum=0;
	int diff=0;
	rep(i,D){
		sum+=s[i][ans[i]];
		diff+=csum;
		diff-=(i-last[ans[i]])*c[ans[i]];
		sum-=diff;
		last[ans[i]]=i;
	}
	cur_score=sum;
	return sum;
}

inline int SUM(int b,int n){
	return (b*(n-1))*n/2;
}
int update(int pos,int d){
	int x=ans[pos];
	auto it=se[x].find(pos);
	int diff=0;
	diff-=s[pos][x];
	diff+=s[pos][d];

	int prv=*prev(it),nx=*next(it);
	diff+=SUM(c[x],pos-prv);
	diff+=SUM(c[x],nx-pos);
	diff-=SUM(c[x],nx-prv);

	it=se[d].lower_bound(pos);
	prv=*prev(it),nx=*it;
	diff+=SUM(c[d],nx-prv);
	diff-=SUM(c[d],pos-prv);
	diff-=SUM(c[d],nx-pos);

	cur_score+=diff;
	return cur_score;
}

int main(){
	rep(i,26){
		se[i].insert(-1);
		se[i].insert(D);
	}
	scanf("%*d");
	rep(i,26)scanf("%d",&c[i]),csum+=c[i];
	rep(i,D)rep(j,26)scanf("%d",&s[i][j]);
	rep(i,D){
		ans[i]=max_element(s[i],s[i]+26)-s[i];
		se[ans[i]].insert(i);
	}
	random_device rnd;
	mt19937 mt(rnd());
	uniform_real_distribution<double>Real(0,1);
	int Max=score();
	double stmp=10000,etmp=0;
	int upd=0;
	int LOOP=9000000;
	rep(loop,LOOP){
		int pos=mt()%D;
		int sum=0;
		rep(i,26)sum+=s[pos][i];
		int ch,d=-1;
		do{
			ch=mt()%sum;
			rep(i,26){
				ch-=s[pos][i];
				if(ch<0){d=i;break;}
			}
		}while(d==ans[pos]);
		int old=ans[pos],old_score=cur_score;
		int nx=update(pos,d);
		double tmp=stmp+(etmp-stmp)/LOOP*loop;
		double p=exp(-double(abs(Max-nx))/tmp);
		if(Max<nx||Real(mt)<p){
			se[old].erase(pos);
			se[d].insert(pos);
			ans[pos]=d;
			Max=nx;upd++;
		}
		else{
			cur_score=old_score;
		}
	}
	cerr<<upd<<endl;
	rep(i,D){
		cout<<ans[i]+1<<endl;
	}
	cerr<<"score: "<<Max<<' '<<score()<<endl;
}

Measured memory_bytes: 4468
x,y=map(int,raw_input().split(' '))

a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
c=[2]

if (x in a and y in a) or (x in b and y in b) or x==y==2:
    print "Yes"
else:
    print "No"


Measured memory_bytes: 2568
#include <bits/stdc++.h>
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,b) for(ll i=0;i<b;i++)
#define RFOR(i,a,b) for(ll i=b-1;i>=a;i--)
#define rsort(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(),(v).end()
using namespace std;
ll mod=1000000007;

vl a;ll q,p;
signed main(){
    ll n;
    cin>>n;
    rep(i,n) {
    cin>>q;
    if(q==0){
        cin>>p;
        a.push_back(p);
    }else if(q==1){
        cin>>p;
        cout<<a.at(p)<<endl;
    }else{
        a.pop_back();
    }
    }
}


Measured memory_bytes: 4968
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define ll long long
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mt make_tuple
#define eb emplace_back
using namespace std;
const int N=1e5+5;
const ll inf=3e18;

void solve(){
    int k;
    cin>>k;
    int a,b;
    cin>>a>>b;
    for(int i=1;i<10000;i++){
        if(i*k>=a && i*k<=b){
            cout<<"OK"<<endl;
            return;
        }
    }
    cout<<"NG"<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll t,p;
    t=1;
    //cin>>t;
    for(p=1;p<=t;p++){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <limits.h>
#include <string>
using namespace std;

int main(void){
    int n, s[1000][1000];
    cin >> n;
    
    int k = 1;
    while (k * (k - 1) != 2 * n) {
        k++;
        if (k > 500) {
            cout << "No";
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    int p = 1, q = 2, l = 1;
    int sc[400];
    for (int i = 1; i <= 980; i++) sc[i] = 1;
    while (p != k) {
        s[p][sc[p]] = l;
        s[q][sc[q]] = l;
        sc[p]++;  sc[q]++;
        l++;
        q++;
        if (q == k + 1) {p++; q = p + 1;}
    }
    
    cout << k << endl;
    
    for (int i = 1; i <= k; i++) {
        cout << k - 1 << " ";
        for (int j = 1; j < k - 1; j++) {
            cout << s[i][j] << " ";
        }
        cout << s[i][k - 1] << endl;
    }
    
}


Measured memory_bytes: 5120
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
	// cin>>TESTS;
	while(TESTS--)
	{
		ll int n,d,a;
		cin>>n>>d>>a;
		vector<pii> v(n);
		for(ll int i=0;i<n;i++)
		{
			cin>>v[i].F>>v[i].S;
			v[i].S=(v[i].S+a-1)/a;
		}
		sort(all(v));
		int pre[n+1],sm=0;
		memset(pre,0,sizeof(pre));
		ll int ans=0;
		for(int i=n-1;i>=0;i--)
		{
			pii p={v[i].F-2*d,-hell};
			ll int lidx=lower_bound(all(v),p)-v.begin();
			ll int left=v[i].S+sm;
			if(left>0)
			{
				ans+=left;
				pre[lidx]+=left;
				sm-=left;
			}
			sm+=pre[i];
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 4224
la=[]
lb=[]
n=int(input())
kari=[]
tak=0
ao=0
s=-1
for i in range(n):
    a,b=map(int,input().split())
    la.append(a)
    lb.append(b)
    kari.append(a+b)
    ao+=b
kari.sort()
if n%2==0:
    for v in range(int(n/2)):
        tak+=kari[s]
        s+=-2
else:
    for k in range(int(n/2)+1):
        tak+=kari[s]
        s+=-2
print(tak-ao)

Measured memory_bytes: 15340
#include <bits/stdc++.h>
using namespace std;
long long int max1(long long int a,long long int b,long long int c)
{
	if(a>b && a>c)
	{
		return a;
	}
	if(b>a&&b>c)
	{
		return b;
	}
	return c;
}
int main(void)
{
	int n;
	cin >> n;
	long long int h[100001][3];
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cin >> h[i][j];
		}
	}
	// for (int i = 0; i < n; ++i)
	// {
	// 	for (int j = 0; j < 3; ++j)
	// 	{
	// 		printf("%lld ",h[i][j] );
	// 	}
	// 	printf("\n");
	// }
	long long int cost[100001][3];
	cost[0][0]=h[0][0];
	cost[0][1]=h[0][1];
	cost[0][2]=h[0][2];

	for (int i = 1; i < n; ++i)
	{
		cost[i][0]=h[i][0]+max(cost[i-1][1],cost[i-1][2]);
		cost[i][1]=h[i][1]+max(cost[i-1][0],cost[i-1][2]);
		cost[i][2]=h[i][2]+max(cost[i-1][0],cost[i-1][1]);
	}

	printf("%lld\n",max1(cost[n-1][0],cost[n-1][1],cost[n-1][2]) );
}

Measured memory_bytes: 4992
fun main(args: Array<String>) {

    val (N, W) = readLine()!!.split(" ").map(String::toInt)
    val WV = Array(N) { readLine()!!.split(" ").map(String::toInt) }
    val w = WV.map { it[0] }
    val v = WV.map { it[1] }

    val dp = Array(N + 1) { LongArray(W + 1) }

    for (i in 0 until N) {
        val weight = w[i]
        val value = v[i]
        for (currentSumWeight in 0..W) {

            if (currentSumWeight - weight >= 0) {
                //　入れる、入れない
                dp[i + 1][currentSumWeight] =
                    Math.max(dp[i][currentSumWeight - weight] + value, dp[i][currentSumWeight])
            } else {
                dp[i + 1][currentSumWeight] = dp[i][currentSumWeight]
            }
        }
    }

//    dp.forEach {
//        it.joinToString(",") { it.toString().padStart(3, ' ') }.let(::println)
//    }

    println(dp.last().last())
}


Measured memory_bytes: 125124
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, readline().split()))
    wv = [list(map(int, readline().split())) for _ in range(n)]
    dp = [10 ** 10] * (10 ** 3 * n + 1)
    dp[0] = 0
    max_v = 0
    for ww, vv in wv:
        for i in range(max_v, -1, -1):
            dp[i+vv] = min(dp[i+vv], dp[i] + ww)
            max_v = max(max_v, i+vv)
    mt = 0
    for i in range(len(dp)):
        if dp[i] <= w:
            mt = max(mt, i)
    print(mt)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 40304
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
bool judge(vector<int>const& a,vector<int>const& b,int x,int k){
  int sm=0;
  bool res=false;
  int n=a.size();int m=b.size();
  rep(i,min(x,n)){
    sm+=a[i];
  }
  int nxt=0;
  if(x>n){
    rep(i,x-n){
      sm+=b[i];
    }
    nxt=x-n;
  }
  if(sm<=k)res=true;
  for(int i=min(x,n)-1;i>=0;--i){
    if(nxt==m)break;
    sm+=b[nxt];
    sm-=a[i];
    if(sm<=k)res=true;
    ++nxt;
  }
  return res;
}
signed main(){
  int n,m,k;cin>>n>>m>>k;
  vector<int> a(n);
  vector<int> b(m);
  int sm=0;
  rep(i,n){
    cin>>a[i];
    sm+=a[i];
  }
  rep(i,m){
    cin>>b[i];
    sm+=b[i];
  }
  int d=0;int u=n+m+1;
  while(u-d>1){
    int mid=(u+d)/2;
    if(judge(a,b,mid,k))d=mid;
    else u=mid;
  }
  cout<<d<<"\n";
  return 0;
}


Measured memory_bytes: 6368
import math
def pcount(n, r):
    return math.factorial(n) // (math.factorial(r)* math.factorial(n - r))

n, a, b = map(int, input().split())
L = [int(i) for i in input().split()]
L.sort(reverse=True)

T = L[:a]
print(sum(T)/a)

s = 0
Tmin = min(T)
countTminT = T.count(Tmin)
countTminL = L.count(Tmin)

if a == 1 and countTminL == 1:
  s = 1
elif countTminT == a:
  for i in range(a,b+1):
    if countTminL+1 == i:
      break
    s += pcount(countTminL, i)
else:
  s += pcount(countTminL, countTminT)

print(s)

Measured memory_bytes: 3188
#include <iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2],R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;
    for(int i=0;i<n1;i++) L[i]=A[left+i];
    for(int i=0;i<n2;i++) R[i]=A[mid+i];
    L[n1]=R[n2]=SENTINEL;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        cnt++;
        if(L[i]<=R[j]) A[k]=L[i++];
        else A[k]=R[j++];
    }
}
void mergeSort(int A[],int n,int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergeSort(A,n,left,mid);
        mergeSort(A,n,mid,right);
        merge(A,n,left,mid,right);
    }
}
int main(){
    int A[MAX],n,i;
    cnt=0;
    cin>>n;
    for(i=0;i<n;i++) cin>>A[i];
    mergeSort(A,n,0,n);
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<A[i];
    }
    cout<<endl<<cnt<<endl;
    return 0;
}



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

int main()
{
  int k,n;

  scanf("%d %d",&k,&n);
 
  int a[n+2];
  int i;
  int l[n+2];
  int max_l=0;
  int num=1;
  long long sum=0;
  
  for(i=0;i<=n+1;i++)
  {
    a[i]=0;
    l[i]=0;
  }
  
  for(i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
  }
  
  for(i=1;i<n;i++)
  {
   l[i]=a[i+1]-a[i];
  }
  l[n]=k-a[n]+a[1];
  
 /* for(i=1;i<=n;i++)
  {
    printf("l[%d]=%d\n",i,l[i]);
  }*/
  
  max_l=l[1];
  for(i=2;i<=n;i++)
  {
    if(max_l<l[i])
    {
      max_l=l[i];
      num=i;
    }
  }
// printf("%d\n",num);
  
  
  for(i=1;i<=n;i++)
  {
    if(i!=num)
    {
    sum+=l[i];
    }
    
  }
  
  printf("%lld\n",sum);
  return 0;
}

Measured memory_bytes: 1664
ans (t:n:_)
  | t == 1 = 6000 * n
  | t == 2 = 4000 * n
  | t == 3 = 3000 * n
  | t == 4 = 2000 * n

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = map ans i
  mapM_ print o
  

Measured memory_bytes: 3620
N = int(input())
A=[int(x) for x in input().split()]
k=0
if N==1:
    print("OK")
else:
     if A[0]//int(N) == A[1]//int(N)  and A[0]%int(N)!=0  and A[1]%int(N)!=0:
        print("NG")
     else:
         print("OK")

Measured memory_bytes: 9184
N=int(input());*T,=map(int,input().split());*A,=map(int,input().split());a=int(A[0]==T[-1])
for p,q,r,s in zip(T,T[1:],A[1:],A[2:]):
 if(p==q)&(r==s):a=a*min(q,r)%(10**9+7)
 elif(p!=q)&(q>r)|(r!=s)&(q<r):a*=0
print(a)

Measured memory_bytes: 19136
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #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 REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

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

int n,l;
int a;
vi va;

signed main(){
    I(n); I(l);
    deque<int> ai;
    REP(i,n){
        I(a);
        ai.pb(a);
        va.pb(a);
    }
    int keep = -1;
    REP(i,n-1){
        if (va[i] + va[i+1] >= l){
            keep = i+1;
            break;
        }
    }
    if (keep == -1){
        cout << "Impossible" << endl;
    } else {
        printf("Possible\n");
        REPS(i,keep-1) printf("%lld\n", i);
        for(int i=n-1; i>keep; i--) printf("%lld\n", i);
        printf("%lld\n", keep);
    }
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define int long long
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;
const int INF = sizeof(int) == sizeof(long long) ? LLONG_MAX : INT_MAX;
const int MOD = 1000000007;
const long double EPS = 1e-8;

signed main() {
	string s;
	cin >> s;
	cout << ((s.size() % 2 == 0) xor (s.front() == s.back()) ? "Second" : "First") << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(n) (n).begin(), (n).end()


int main()
{
    int n, q;
    cin >> n;
    vector<bitset<64>> mask(n);
    bitset<64> bit;

    rep(i, n)
    {
        int k;
        int flag;
        cin >> k;
        rep(j, k)
        {
            cin >> flag;
            mask[i] |=  (1LL << flag);
        }
    }
    cin >> q;
    rep(n, q)
    {
        ll que, i, m;
        cin >> que;
        if (que == 0)
            cin >> i;
        else
            cin >> m;

        switch (que) {
        case 0://test
            //(bit & (1LL << i))
            cout << bit.test(i) << endl;
            break;
        case 1://set
            bit |= mask[m];
            break;
        case 2://clear
            bit &= ~(mask[m]);
            break;
        case 3:
            //XOR_ 0 0 = 0, 0 1 = 1, 1 1=0,
            bit ^= mask[m];
            break;
        case 4:
            cout << ((bit & mask[m]) == mask[m]) << endl;
            break;
        case 5:
            cout << (bit & mask[m]).any() << endl;
            break;
        case 6:
            cout << (bit & mask[m]).none() << endl;
            break;
        case 7:
            cout << (bit & mask[m]).count() << endl;
            break;
        case 8:
            cout << (bit & mask[m]).to_ulong() << endl;
            break;
        }

    }

}


Measured memory_bytes: 3084
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


d = {'Sunny':'Cloudy','Cloudy':'Rainy','Rainy':'Sunny'}
print(d[S()])


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

int main() {
  int N;
  cin >> N;
  int count = 0;

  for(int i = 1;i < N;++i){
    int t = N / i - 1 + (N % i != 0);
    
    count += t;
  }
  cout << count << endl;
}


Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramD
    {
        static void Main()
        {
            long n = NextInt;

            System.Console.WriteLine(n * (n - 1) / 2);
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


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

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

	vector<int> A(N);
	for (int i = 0; i < N; ++i)
		cin >> A[i];

	for (int i = 0; i < N - K; ++i)
		if (A[K + i] > A[i]) cout << "Yes" << endl;
		else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3612
/// sultanov

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
     
#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
 
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type,
less<T>, rb_tree_tag, 
tree_order_statistics_node_update>;

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

const int N = 2e5 + 1e2;
const int MOD = 1e9 + 7;
const int INF32 = 1e9 + 1e2;

int d[N];

vector<int> adj[N];

void bfs(int v = 0) {
    queue<int> q;
    q.push(v);
    fill(d, d + N, INF32);
    d[v] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int to : adj[x]) {
            if (d[to] > d[x] + 1) {
                d[to] = d[x] + 1;
                q.push(to);
            }
        }
    }
    for (int i = 0; i < N; ++i)
        if (d[i] == INF32)
            d[i] *= -1;
}

bool dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    bfs();
    int v = max_element(d, d + N) - d;
    bfs(v);
    int dia = *max_element(d, d + N);
    dp[0] = 1;
    dp[2] = 1;
    for (int i = 2; i <= dia; ++i) 
        if (!dp[i - 1] || !dp[i - 2])
            dp[i] = 1;
    cout << (dp[dia] ? "First" : "Second");
    return 0;
}

Measured memory_bytes: 13556
from sys import stdin, stdout
from math import sqrt
from collections import defaultdict
def getCount(i):
    c = 0
    while i > 0:
        if i%2 == 0:
            c += 1
        else:
            break
        i//=2
    return c
n = int(input())
arr = [int(x) for x in input().split()]
count = 0
for i in arr:
    count += getCount(i)
print(count)


Measured memory_bytes: 4532
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a>=13){
        cout<<b<<endl;
    }
    else if(a>=6 && a<=12){
        cout<<(b/2)<<endl;
    }
    else{
        cout<<0<<endl;
    }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#include <assert.h>
#define FOR(i,a,n) for(i=(a);i<(n);i++)
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0)
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define LOCAL
#ifdef LOCAL
    #define DEBUG(...) printf(" "__VA_ARGS__)
#else
    #define DEBUG(...)
#endif /* LOCAL */
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int a[100000];
int main(void)
{
	int n,res=0,num,s,i;
	scanf("%d",&n);
	FOR(i,0,n) scanf("%d",a+i);
	qsort(a,n,sizeof(int),comp);
	for(i=0;i<n;){
		num=a[i]; s=0;
		while(a[i]==num) s++,i++;
		if(s>num) res+=(s-num);
		else if(s<num) res+=s;
	}
	printf("%d\n",res);
	return 0;
}
    
    


Measured memory_bytes: 892
n = int(input())
d = {}
for v in list(map(int, input().split())):
    if v in d:
        d[v] += 1
    else:
        d[v] = 1

m = int(input())
for v in list(map(int, input().split())):
    if v in d and d[v] > 0:
        d[v] -= 1
    else:
        print("NO")
        exit()
print("YES")


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

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int>A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	int ans = A[0];

	for (int i = 1; i < N; i++) {
		ans = __gcd(ans,A[i]);
	}

	cout << ans << endl;

	return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main(){
    int N,S; cin >> N >> S;
    VI a(N); REP(i,N) cin >> a[i];
    VI s(N+1,0); REP(i,N) s[i+1] = s[i]+a[i];

    int ans = INF;
    int l = 0;
    FOR(r,1,N+1){
        while(l<r && S<=s[r]-s[l+1]) l++;
        if(l==r) continue;
        if(s[r]-s[l]>=S) chmin(ans, r-l);
    }
    cout << (ans<INF ? ans : 0) << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}


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

def is_753(a):
    check = {'7': 0, '5': 0, '3': 0}
    string = str(a)
    for i in range(len(str(a))):
        if not string[i] in ['7', '5', '3']:
            return False
        check[string[i]] += 1
    for v in check.values():
        if v == 0:
            return False
    return True
    

q = [3, 7, 5]
count = 0

while len(q) > 0:
    # print(q)
    front = q.pop(0)
    # print('front:', front, end=' ')
    if len(str(front)) >= 3 and is_753(front):
        count += 1
    # create next
    for i in [3, 5, 7]:
        cand = int(str(i) + str(front))
        if cand <= n:
            q.append(cand)

print(count)

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

int main() {
    long long N, K, Q;
    cin >> N >> K >> Q;
    vector <long long> P(N, K-Q);
    for (long long i=0; i<Q; i++) {
        long long tmp;
        cin >> tmp;
        P.at(tmp-1)++;
    }
    for (long long i=0; i<N; i++) {
        if (P.at(i)>0) {
            cout << "Yes\n";
        }
        else cout << "No\n";
    }
}

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

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

using namespace std;

int rnd(int a,int b,int c,int& x){
  return x = (a*x+b) % c;
}

int main()
{
  while(1){
    int n,a,b,c,x;
    cin>>n>>a>>b>>c>>x;
    if(!n) break;
    vector<int> y(n);
    REP(i,n)cin>>y[i];
    int j=0;
    int64_t p=-1;
    REP(i,10001){
      if(x==y[j]){
        ++j;
        if(j==n){
          p=i;
          break;
        }
      }
      rnd(a,b,c,x);
    }
    cout<<p<<endl;
  }
  return 0;
}

Measured memory_bytes: 1196
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	num, e := strconv.Atoi(sc.Text())
	if e != nil {
		log.Fatal(e)
	}
	return num
}

func scanSlice() []int {
	sc.Scan()
	s := sc.Text()
	sArray := strings.Split(s, " ")
	var sIntArray []int
	for i := 0; i < len(sArray); i++ {
		sInt, e := strconv.Atoi(sArray[i])
		if e != nil {
			log.Fatal(e)
		}
		sIntArray = append(sIntArray, sInt)
	}
	return sIntArray
}

func printSlice(s []int) {
	for i := 0; i < len(s); i++ {
		fmt.Print(s[i])
		if i != len(s)-1 {
			fmt.Print(" ")
		}
	}
	fmt.Print("\n")
}

func insertionSort(list []int) []int {
	/**

	**/
	// i番目まではソート完了領域
	for i := 1; i < len(list); i++ {
		v := list[i]
		j := i - 1
		for j >= 0 && list[j] > v {
			list[j+1] = list[j]
			j--
		}
		list[j+1] = v
		printSlice(list)
	}
	return list
}

func main() {
	scanInt()
	sort := scanSlice()
	printSlice(sort)
	insertionSort(sort)
}


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

//定数
const long long MOD1=1000000007;
const long long MOD2=998244353;
const long double PI=3.1415926535897932;
const long long MAXLL=9223372036854775807;
const long long INF=2305843009213693951;
const long long dx[]={0,1,0,-1,1,-1,1,-1};
const long long dy[]={1,0,-1,0,1,1,-1,-1};

//省略
#define ll long long
#define ull unsigned long long
#define ld long double
#define uld unsigned long double
#define pll pair<long long,long long>
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define vvvl vector<vector<vector<long long>>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector<string>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vp vector<pair<long long,long long>>
#define umap unordered_map
#define uset unordered_set
#define Lqueue priority_queue<long long>
#define Squeue priority_queue<long long,vector<long long>,greater<long long>>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

//マクロ
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rbf(a,x) for(auto& a:x)
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s);i<(long long)(n);i++)
#define bitrep(i,s,n) for(long long i=(s);i<(1LL<<(n));i++)
#define bitcheck(bit,i) (bit)&(1LL<<(i))
#define Maxe(x) *max_element((x).begin(),(x).end())
#define Mine(x) *min_element((x).begin(),(x).end())
#define Size(x) ((long long)(x).size())
#define Lin(s) getline(cin,(s))

//Yes,No
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}

//MAX,MIN
template<class T,class U> auto max(T a,U b){return a>b?a:b;}
template<class T,class U> auto min(T a,U b){return a<b?a:b;}

//最大公約数,最小公倍数
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a,long long b){return a/gcd(a,b)*b;}

//切り上げ除算
long long cutup(long long a,long long b){return (a+b-1)/b;}

//累乗
template<typename t>
constexpr t my_pow(t a,long long b){
    if(b==0)return 1;
    if(a==0)return 0;
    t x=1;
    while(b>0){
        if(b&1LL)x*=a;
        a*=a;
        b>>=1LL;
    }
    return x;
}
#define pow my_pow

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

//組み合わせ O(r)
template<typename t>
constexpr t nCr(t n,long long r){
    if(r==0)return 1;
    if(n==0)return 0;
    if(n<r)return 0;
    t x=1;
    for(long long i=1;i<=r;i++){
        x*=n-i+1;
        x/=i;
    }
    return x;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string n;
    cin>>n;
    ll res=0;
    rep(i,Size(n)){
        res+=n[i]-'0';
        res%=9;
    }
    Yes(!res);
}

Measured memory_bytes: 3740
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

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

    int a,b; cin>>a>>b;
    int N=__gcd(a,b);

    set<int> st;
    st.insert(1);
    for(int i=2;i*i<=N;i++){
        while(N%i==0){
            N/=i; st.insert(i);
        }
    }
    if(N>1) st.insert(N);
    cout<<st.size()<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<double> p(n);
    for(int i=0;i<n;i++) cin>>p[i];
    vector<vector<double>> dp(n+1,vector<double>(n+1,0));
     dp[1][0]=(1-p[0]);dp[1][1]=p[0];
     for(int i=2;i<=n;i++){
        for(int j=0;j<=i;j++){
              dp[i][j]=dp[i-1][j]*(1-p[i-1]);
            if(j-1>=0) dp[i][j]+=dp[i-1][j-1]*p[i-1];
        }
     }
     /*
      for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++) cout<<dp[i][j]<<" ";
        cout<<"\n";
      }*/
     int half=n/2+1;
     double ans=0;
      for(int i=half;i<=n;i++) ans+=dp[n][i];
      cout<<fixed<<setprecision(10)<<ans;

}


Measured memory_bytes: 73776
#include <bits/stdc++.h>
using namespace std;
vector<int>DP(100001,1000000000);
int main(){
  int H,N;cin>>H>>N;
  vector<pair<int,int>>A(N);
  for(int i=0;i<N;i++)cin>>A[i].first>>A[i].second;
  DP[0]=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<N;j++)
      DP[min(i+A[j].first,H)]=min(DP[min(i+A[j].first,H)],DP[i]+A[j].second);
  }
  cout<<DP[H]<<endl;
}

Measured memory_bytes: 3732
S = gets.chomp
S.reverse!
size = S.size
a = Array.new(13){Array.new(2,0)}
a[0][0] = 1
b = Array.new(6)
b = [1,10,9,12,3,4]
c = 0
d = 0
h,i,j,k = 0,0,0,0
while h < size
    i = h%6
    if S[h] == "?"
        j = 0
        d = 0
        while j < 13
            d += a[j][i%2]
            j += 1
        end
        j = 0
        while j < 13
            a[j][(i+1)%2] = d
            k = 10
            while k < 13
                a[j][(i+1)%2] -= a[(j-k*b[i%6])%13][i%2]
                k += 1
            end
            a[j][(i+1)%2] %= 10**9+7
            j += 1
        end
    else
        c = S[h].to_i
        j = 0
        while j < 13
            a[(j+c*b[i%6])%13][(i+1)%2] = a[j][i%2]
            j += 1
        end
    end
    h += 1
end
puts a[5][size%2]

Measured memory_bytes: 2044
// Standard I/O
#include <iostream>
#include <sstream>
#include <cstdio>
// Standard Library
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
// Template Class
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
// Container Control
#include <algorithm>

using namespace std;

#define rep( i, n ) for( int i = 0; i < n; ++i )
#define irep( i, n ) for( int i = n-1; i >= 0; --i )
#define reep( i, s, n ) for ( int i = s; i < n; ++i )
#define ireep( i, n, s ) for ( int i = n-1; i >= s; --i )
#define foreach(itr, x) for( typeof(x.begin()) itr = x.begin(); itr != x.end(); ++itr)

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all( v ) v.begin(), v.end()
#define fs first
#define sc second
#define vc vector

// for visualizer.html
double SCALE = 1.0;
double OFFSET_X = 0.0;
double OFFSET_Y = 0.0;
#define LINE(x,y,a,b) cerr << "line(" << SCALE*(x) + OFFSET_X << ","	\
	<< SCALE*(y) + OFFSET_Y << ","										\
	<< SCALE*(a) + OFFSET_X << ","										\
	<< SCALE*(b) + OFFSET_Y << ")" << endl;
#define CIRCLE(x,y,r) cerr << "circle(" << SCALE*(x) + OFFSET_X << ","	\
	<< SCALE*(y) + OFFSET_Y << ","										\
	<< SCALE*(r) << ")" << endl;

typedef long long ll;
typedef complex<double> Point;

typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector< vector<int> > vii;
typedef vector< vector<double> > vdd;

typedef vector<int>::iterator vi_itr;

const int IINF = 1 << 28;
const int MOD = 1e9+7;
const double INF = 1e30;
const double EPS = 1e-10;
const double PI = acos(-1.0);

// Direction : L U R D
const int dx[] = { -1, 0, 1, 0};
const int dy[] = { 0, -1, 0, 1 };

ll dist[100000];
vector<pii> path[100000];

void calc_dist ( int root )
{
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;

	bool is_visit[100000] = { false };
	que.push(mp(0, root));
	while( !que.empty() ){
		auto p = que.top(); que.pop();

		if( is_visit[p.sc] ) continue;

		is_visit[p.sc] = true;
		dist[p.sc] = p.fs;

		rep(i, path[p.sc].size()){
			que.push(mp(p.fs+path[p.sc][i].sc, path[p.sc][i].fs));
		}
	}
}

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

	rep(i, N-1){
		int a, b, c;

		cin >> a >> b >> c;
		--a; --b;

		path[a].eb(b, c);
		path[b].eb(a, c);
	}

	int Q, K;
	cin >> Q >> K;
	--K;
	
	calc_dist(K);

	rep(i, Q){
		int x, y;
		cin >> x >> y;
		--x; --y;
		
		cout << dist[x] + dist[y] << endl;
	}
}


Measured memory_bytes: 9072
// ABC060_C
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define MIN(vec) min_element(vec.begin(), vec.end())  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(vec.begin(), vec.end())
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(vec.begin(), vec.end(), 0LL)  // 0 は初期値
#define vl vector<ll>
#define pll pair<ll, ll>
#define F first
#define S second

int main() {
    // input
    ll N, T;
    cin >> N >> T;
    vl vec(N), diff(N-1);
    REP(i, N) cin >> vec[i];
    
    if (N == 1) {
        cout << T << "\n";
        return 0;
    }
    
    REP(i, N-1) diff[i] = vec[i+1] - vec[i];
    
    // calculation
    ll res = 0;
    for (ll i = 0; i < N-1; ++i) {
        if (diff[i] <= T) {
            res += diff[i];
        } else {
            // diff[i] > T
            res += T;
        }
    }
    res += T;
    
    cout << res << "\n";
    
    return 0;
}

Measured memory_bytes: 3328
#include <iostream>

using namespace std;

int main(){
    int num;
    int array[1024];

    cin >> num;
    for(int i = 0; i < num; i++){
        cin >> array[i];
    }
    for(int k = 0; k < num; k++){
        cout << array[k];
        if(k != num - 1) cout << " ";
    }
    cout << endl;

    for(int i = 1; i < num; i++){
        int key = array[i];
        if(array[i - 1] > key){
            int j = i;
            do {
                array[j] = array[j - 1];
                j--;
            } while(j > 0 && array[j - 1] > key);
            array[j] = key;
        }
        for(int k = 0; k < num; k++){
            cout << array[k];
            if(k != num - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3108
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
ll n, ans;
int main() {
  speed;
  oprecision;
  // code
  cin >> n;
  while (n >= 500) n -= 500, ans += 1000;
  while (n >= 5) n -= 5, ans += 5;
  cout << ans;
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 256
N = int(input())
DP = [100000000] * (N+1)
DP[0] = 0
for i in range (N):
    DP[i + 1] = DP[i] + 1
    for j in range (8):
        if 6**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 6**j] + 1)
    for j in range (8):
        if 9**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 9**j] + 1)
print(DP[N])

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

using namespace std;

unsigned long long pow(long long base, long long power, long long mod){
    if(power==0)
        return 1;
    if(power==1)
        return base;

    unsigned long long ans = pow(base, power/2, mod);
    ans = ((ans%mod)*(ans%mod))%mod;

    if(power&1)
        return ((ans%mod)*(base%mod))%mod;
    return ans;
}

int n, k;
int arr[200002], freq[200002];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    //int p = pow(100, 100, 1000000007);

    cin >> n;
    for(int i=0; i<n-1; i++)
        cin >> arr[i], freq[arr[i]]++;
    for(int i=1; i<=n; i++)
        cout << freq[i] << '\n';
}


Measured memory_bytes: 5164
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long
#define pb push_back
#define endl '\n'
bool cmp(char a, char b){
	return a<b;
}
ll solve(){
	ll x;
	cin>>x;
	if(x>=30) cout<<"Yes";
	else cout<<"No";
	return 0;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3608
#include<iostream>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define N 500
int width[N][N];
char m[N][N+1];

int solve(int r,int c){
  rep(i,r){
    if (m[i][0] == '.')width[i][0]=1;
    else width[i][0]=0;
    REP(j,1,c){
      if ( m[i][j]=='*')width[i][j]=0;
      else width[i][j]=width[i][j-1]+1;
    }
  }

  int ret=0;
  rep(j,c){
    rep(i,r){
      int minwidth=width[i][j];
      if ( minwidth==0)continue;
      ret=max(ret,minwidth);
      REP(k,i+1,r){
	minwidth=min(minwidth,width[k][j]);
	if ( minwidth == 0)break;
	ret=max(ret,(k-i+1)*minwidth);
      }
    }
  }
  return ret;
}

main(){
  int r,c;
  while(cin>>r>>c && r){
    rep(i,r)cin>>m[i];
    cout << solve(r,c)<<endl;
  }
}

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	LL hm = 0, tmp = 0;
	for (int i = 0; i < n; i++) {
		tmp += (s[i] == ')' ? 1 : -1);
		hm = max(tmp,hm);
	}
	string mae = "";
	for (int i = 0; i < max(hm ,(LL)0); i++) {
		mae += '(';
	}
	LL tm = 0;
	tmp = 0;
	for (int i = n-1; i >= 0; i--) {
		tmp += (s[i] == '(' ? 1 : -1);
		tm =  max(tm, tmp);
	}
	string usiro = "";
	for (int i = 0; i < max(tm,(LL)0); i++) {
		usiro += ')';
	}
	cout << (mae + s + usiro) << endl;
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

NUM = 8
VALUE = (12121414, 21214141, 12141412, 21414121, 14141212, 41412121,
         14121214, 41212141)
RIDE = ((1, 2, 1, 2, 1, 4, 1, 4), (2, 1, 2, 1, 4, 1, 4, 1),
        (1, 2, 1, 4, 1, 4, 1, 2), (2, 1, 4, 1, 4, 1, 2, 1),
        (1, 4, 1, 4, 1, 2, 1, 2), (4, 1, 4, 1, 2, 1, 2, 1),
        (1, 4, 1, 2, 1, 2, 1, 4), (4, 1, 2, 1, 2, 1, 4, 1))

for line in stdin:
    gast = [int(s) for s in line.split()]
    remain = sum(gast)
    value = max(VALUE)
    for i in range(NUM):
        r = sum(g-n if g-n > 0 else 0 for g, n in zip(gast, RIDE[i]))
        if remain > r or (remain == r and value > VALUE[i]):
            remain = r
            index = i
            value = VALUE[i]
    print(*RIDE[index])

Measured memory_bytes: 4292
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;


int N, A, B, C;
int l[10];
ll dfs(vector<int> &vec, ll &ans){
  if ((int)vec.size()==N){
    /*ここに処理を書く*/
    int a[3] = {};
    int nonzero = 0;
    rep(i,N){
      if (vec[i]==3) continue;
      
      a[vec[i]] += l[i];
      nonzero++;
    }
    if (nonzero<3 || a[0]==0 || a[1]==0 || a[2]==0) return INF;
    ll point = 10*(nonzero - 3);
    point += abs(a[0]-A) + abs(a[1]-B) + abs(a[2]-C);
    return point;
  }

  for (int v=0;v<=3;v++){ // 狭義の場合はv=l+1とする
    vec.push_back(v);
    ll res = dfs(vec,ans);
    chmin(ans, res);
    vec.pop_back();
  }
  return ans;
}

int main(){
  cin >> N >> A >> B >> C;
  rep(i,N) cin >> l[i];

  vector<int> init;
  ll ans = INF;
  cout << dfs(init, ans) << endl;




  // cout << fixed << setprecision(10);
  
  return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 405;
int64_t dp[MAXN][MAXN]; // iからjまで合体させるための最小コスト
int64_t S[MAXN];
vector<int64_t> A(MAXN);

int64_t cost(int l, int r)
{
  if (dp[l][r] > 0)
    return dp[l][r];
  if (l == r)
    return dp[l][r] = 0;
  int64_t ret = (1LL << 62);
  for (int i = l; i < r; i++)
  {
    ret = min(ret, (cost(l, i) + (S[i + 1] - S[l]) + cost(i + 1, r) + (S[r + 1] - S[i + 1])));
  }
  return dp[l][r] = ret;
}

int main()
{
  int N;
  cin >> N;
  for (int i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++)
  {
    S[i + 1] += S[i] + A[i];
  }
  cout << cost(0, N - 1) << endl;
}


Measured memory_bytes: 4852