akhauriyash/Code-Regression huggingface dataset:
if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    sum = 0

    if a[0] >= a[3] :
        sum = a[3]
        a[3] = 0
    else:
        sum = a[0]
        a[3] =a[3]-a[0]
    if a[3] > 0:
        a[3] = a[3]-a[1]
    if a[3] >0:

        sum =sum -a[3]


    print(sum)

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

bool check(ll a, ll b, ll c) {
	//?sqrt(a)+sqrt(b)<sqrt(c)
	if (c - a - b >= 0 && 4 * a * b < (c - a - b) * (c - a - b)) {
		return true;
	}
	return false;
}

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	if (check(a, b, c)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

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

using namespace std;

#define ll long long
typedef complex<double> P;

int main() {
  int n = 'z' - 'a' + 1;
  bool a[n] = {};
  string s;
  cin >> s;
  for (size_t i = 0; i < s.size(); i++) {
    int ix = s[i] - 'a';
    if(a[ix]) {
      cout << "no" << endl;
      break;
    }
    else if(i == s.size() - 1) {
      cout << "yes" << endl;
    }
    a[ix] = true;
  }

}


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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const lb PI=3.14159265359;

int main(){

  ll n;cin>>n;
  lb x[n],y[n];rep(i,0,n)cin>>x[i]>>y[i];

  ll per[n];
  rep(i,0,n)per[i]=i;

  lb sum=0;
  ll count=0;
  do{
    count++;
    rep(i,0,n-1){
      sum+=sqrt((x[per[i]]-x[per[i+1]])*(x[per[i]]-x[per[i+1]])+(y[per[i]]-y[per[i+1]])*(y[per[i]]-y[per[i+1]]));
    }

  }while(next_permutation(per,per+n));

  out(fixed<<setprecision(10)<<sum/count);

  return 0;
}


Measured memory_bytes: 384
//
//  main.cpp
//  D - Prediction and Restriction
//
//  Created by Hashizo on 2019/12/29.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
int main(int argc, const char * argv[]) {
	ll ans = 0;


	ll n,k;
	cin >> n >> k;

	ll r,s,p;
	cin >> r >> s >> p;

	
	vector<char> term(n);
	char point;
	REP(i, n) {
		
		cin >> point;

		if (point == 'r') {
			term[i] = 'p';
		}
		else if (point == 's') {
			term[i] = 'r';
		}
		else {
			term[i] = 's';
		}
	}

	FOR(i, k, n) {
		if (term[i] == term[i-k]) {
			
			char kari;
			if (term[i] == 'r') {
				kari = 'p';
			}
			else if (term[i] == 's') {
				kari = 'r';
			}
			else {
				kari = 's';
			}
			
			if (kari == term[i+k]) {
				if (term[i] == 'r') {
					kari = 's';
				}
				else if (term[i] == 's') {
					kari = 'p';
				}
				else {
					kari = 'r';
				}
			}
			
			term[i] = 'X';
		}
	}

	REP(i, n) {
		if (term[i] == 'r') {
			ans += r;
		}
		else if (term[i] == 's') {
			ans += s;
		}
		else if (term[i] == 'p') {
			ans += p;
		}
	}

	cout << ans << endl;
	return 0;
}


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

int h[100010],dp[100010];
using namespace std;
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	
	for(int i=2;i<=n;i++){
		dp[i]=dp[i-1]+abs(h[i-1]-h[i]);
		for(int j=2;j<=k;j++){
			if(i>j && dp[i]>dp[i-j]+abs(h[i-j]-h[i]))
				dp[i]=dp[i-j]+abs(h[i-j]-h[i]);
		}
	}
	
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

//// B
int main(){
    int k, x; cin >> k >> x;
    vector<int> ans;
    ans.push_back(x);
    for(int i=1; i<k; i++){
        ans.push_back(x-i);
        ans.push_back(x+i);
    }
    sort(ans.begin(), ans.end());
    for(int x: ans){
        cout << x << ' ';
    }
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from math import gcd

N = int(input())
a = list(map(int, input().split()))
l = [0]

for ai in a:
    l.append(gcd(l[-1], ai))

r = [0]

for ai in a[::-1]:
    r.append(gcd(r[-1], ai))

ans = 0

for i in range(N):
    ans = max(ans, gcd(l[i], r[N-1-i]))

print(ans)

Measured memory_bytes: 97540
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

int main() {
    fastIO;
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
}

Measured memory_bytes: 3636
use proconio::input;

fn main() {
    input!{
        k: u32,
    }

    let mut ans = 0;

    for a in 1 .. (k+1) {
        for b in 1 .. (k+1) {
            let gcd_a_b = gcd(a, b);
            for c in 1 .. (k+1) {
                ans += gcd(gcd_a_b, c);
            }
        }
    }

    println!("{}", ans);
}

fn gcd(x: u32, y: u32) -> u32 {
    if x < y {
        _gcd(y, x)
    } else {
        _gcd(x, y)
    }
}

fn _gcd(x: u32, y:u32) -> u32 {
    if x == 0 {
        y
    } else {
        _gcd(y % x, x)
    }
}


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

string solve(int N, int A, int B, int C, int D, string S) {
      // (1) CHECK IF THERE ARE ANY 2 CONSECUTIVE WALLS
      for(int i=A; i<=C; i++) {      // no need to consider anything before A, since A and B can only move right, and A always <B
            if(S[i] == '#' && S[i+1] == '#') {
                  return "No";
            }
      }

      for(int i=B; i<=D; i++) {
            if(S[i] == '#' && S[i+1] == '#') {
                  return "No";
            }
      }

      // (2) CHECK IF (A CAN REACH C) AND (B CAN REACH D)
      if(C<D) return "Yes";
      for(int i=B; i<=D; i++) {  // else C>D
            // (3) CHECK IF THERE ARE ANY 3 CONSECUTIVE EMPTY SPACES
            if(S[i-1] == '.' && S[i] == '.' && S[i+1] == '.') return "Yes";
      }
      return "No";
}

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

      int N, A, B, C, D;
      string S;
      cin >> N >> A >> B >> C >> D >> S;

      cout << solve(N, A-1, B-1, C-1, D-1, S) << endl;
}

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

int main (void){
  char s[99];
  scanf("%s",&s);
  int N=0;
  N=strlen(s);
  for(int i=0;i<(N-1)/2;i++){
    if(s[i]!=s[((N-1)/2)-1-i]){
      printf("No\n");
      return 0;
    }
  }

  for(int i=0;i<N;i++){
    if(s[i]!=s[N-1-i]){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}


Measured memory_bytes: 128
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
As = list(mapint())
sortedAs = sorted(As)
mod = 10**9+7

cnt = 0
for i in range(N):
    for j in range(N-1, i, -1):
        if As[j-1]>As[j]:
            As[j-1], As[j] = As[j], As[j-1]
            cnt += 1

from bisect import bisect_right
dub = 0
for a in As:
    bigger = N-bisect_right(sortedAs, a)
    dub += ((K-1)*K//2)*bigger
    dub %= mod
print((cnt*K + dub)%mod)


Measured memory_bytes: 74180
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<=int(b);++i)
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for(int j=0;j<N;++j) {

int main(void) {
  int r;cin>>r;
  pr(r*2*3.1415926535);
  return 0;
}


Measured memory_bytes: 3736
//
// author  : Abhishek
//
#include <bits/stdc++.h>

#define ll long long
#define db double
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)

using namespace std;

const ll mod = 1000000007;
const ll N = 300005;  // array size
const ll inf = 10000000000000000;


void print(vector<ll> v) {
    ll i;
    fo(i, v.size())cout << v[i] << " ";
    cout << "\n";
}

vector<ll> read(ll n) {
    ll i;
    vector<ll> arr(n, 0);
    fo(i, n)cin >> arr[i];
    return arr;
}

vector<ll> read(ll n, ll k) {
    ll i;
    vector<ll> arr(n + k, 0);
    Fo(i, k, n + k)cin >> arr[i];
    return arr;
}

bool isEven(ll n) {
    return n % 2 == 0;
}

bool isOdd(ll n) {
    return n % 2 != 0;
}


void solve() {
    ll t;
    cin >> (t);
    while (t--) {

        ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    cin>>n;
    vector<ll>arr(n);
    arr = read(n);
    ll ans = 0;
    fo(i,n){
        Fo(j,i+1,n){
            ans+=arr[i]*arr[j];
        }
    }

    cout<<ans;

    return 0;
}




Measured memory_bytes: 3584
import java.util.*;

public class Main {
    public static void sort(int array[], int array2[], int left, int right){
        if(left <= right){
            int p = array[(left + right) >>> 1];
            int l = left;
            int r = right;
            while(l <= r){
                while (array[l] < p){
                    l++;
                }
                while (array[r] > p){
                    r--;
                }
                if (l <= r){
                    int tmp = array[l];
                    array[l] = array[r];
                    array[r] = tmp;
                    
                    int tmp2 = array2[l];
                    array2[l] = array2[r];
                    array2[r] = tmp2;
                    l++;
                    r--;
                }
            }
            Main.sort(array, array2, left, r);
            Main.sort(array, array2, l, right);
        }
    }
    
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int c[] = new int[26];
        int s[][] = new int[n][26];
        int ind[] = new int[26];
        
        for(int i = 0; i < 26; i++){
            c[i] = stdIn.nextInt();
            ind[i] = i;
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 26; j++){
                s[i][j] = stdIn.nextInt();
            }
        }
        
        Main.sort(c, ind, 0, 25);
        
        int rev[] = new int[26];
        
        for(int i = 25; i >= 0; i--){
            rev[i] = ind[25 - i] + 1;
        }
        
        for(int i = 0; i < n; i++){
            System.out.println(rev[i % 26]);
            
        }

        //System.out.println("XXXXXXXX");
    }
}


Measured memory_bytes: 46576
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a;
  cin >> a;
    int b = a%999/100;
    int c = a%999%100/10;
    int d = a%999%10;
  if (a <= 999) cout << "ABC"<<endl;
  else cout << "ABD"<<endl;
}

Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;


vvl matmul(vvl &a, vvl &b){
	vvl c(a.size(), vl(b[0].size()));
	for(int i=0; i<a.size(); i++){
		for(int k=0; k<b.size(); k++){
			for(int j=0; j<b[0].size(); j++){
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
			}
		}
	}
	return c;
}

vvl matpow(vvl a, ll n){
	vvl b(a.size(), vl(a.size()));
	for(int i=0; i<a.size(); i++) b[i][i] = 1;
	while(n > 0){
		if(n & 1) b = matmul(b,a);
		a = matmul(a,a);
		n >>= 1;
	}
	return b;
}

int main(){
	ll n,k; cin >> n >> k;
	vvl a(n,vl(n));
	rep(i,n) rep(j,n) cin >> a[i][j];
	vvl b = matpow(a,k);
	ll ans = 0;
	rep(i,n){
		rep(j,n) (ans += b[i][j]) %= mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <limits.h>

int main(void){
   
   long int N;
   
   scanf("%ld",&N);
   
   long int Hito[5];
   
   int i;
   for(i = 0;i < 5;i++){
      scanf("%ld",&Hito[i]);
   }
   
   long int min = LONG_MAX;
   
   for(i = 0;i < 5;i++){
      if(Hito[i] < min){
         min = Hito[i];
      }
   }
   
   long int count = 5;
   
   if(min >= N){
      printf("%ld\n",count);
      return 0;
   }
   else {
      
      count = count + N/min;
      if(N%min == 0){
         count = count - 1;
      }
      
      printf("%ld\n",count);
      return 0;
   }

   
   
   return 0;
}


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

int main(){
  int a1, a2, a3;
  cin >> a1 >> a2 >> a3;

  if (a1+a2+a3 >= 22){
      cout << "bust" << endl;
  }
  else
  {
      cout << "win" << endl;
  }
  

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

int N, M;
vector<int> G[50];
vector<bool> v;
P p;

void dfs(int s) {
    v[s] = true;
    for (int i = 0; i < G[s].size(); i++) {
        int next = G[s][i];
        if (!v[next] && P(s, next) != p && P(next, s) != p) dfs(next);
    }
}

int main() {
    cin >> N >> M;
    vector<P> bridge(M);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
        bridge[i] = P(a, b);
    }
    int cnt = 0;
    for (int i = 0; i < M; i++) {
        p = bridge[i];
        v.assign(N, false);
        dfs(0);
        bool check = false;
        for (int i = 0; i < N; i++) {
            if (!v[i]) check = true;
        }
        if (check) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
kai = list(input())

#回文かどうか
flag = 0
for i in range(len(kai)):
    if kai[i] != kai[-i-1]:
        flag = 1

a = kai[:int(len(kai)/2)]
#1~半分，後半半分回文
for i in range(len(a)):
    if a[i] != a[-i-1]:
        flag = 1
b = kai[int(len(kai)/2)+1:]

for i in range(len(b)):
    if b[i] != b[-i-1]:
        flag = 1

if flag == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define llong long long
#define fr(i,l,r) for(i=(l);i<(r);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define INF 1000000000000//10^12

int main(void)
{
	//変数の宣言
	char s[5010];
	char anschar[10];
	int sint[5010];
	int n,m;
	static int map1[30];
	static int map2[30][30];
	static int map3[30][30][30];
	static int map4[30][30][30][30];
	static int map5[30][30][30][30][30];
	
	//よく使う変数
	int i,j,k,l,p;
	int flag=0;
	llong int ans=0;
	int count=0;
	int temp,temp1,temp2;
	llong int max,min;
	int len;
	int sum=0;
	//データの読み込み
	scanf("%s",&s);
	scanf("%d",&m);
	
	
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	n=strlen(s);
	
	for(i=0;i<n;i++){
		sint[i]=s[i]-'a';
	}
	for(i=0;i<n;i++){
		map1[sint[i]]++;
		if(i<n-1)map2[sint[i]][sint[i+1]]++;
		if(i<n-2)map3[sint[i]][sint[i+1]][sint[i+2]]++;
		if(i<n-3)map4[sint[i]][sint[i+1]][sint[i+2]][sint[i+3]]++;
		if(i<n-4)map5[sint[i]][sint[i+1]][sint[i+2]][sint[i+3]][sint[i+4]]++;
	}
	
	for(i=0;i<26;i++){
		if(map1[i]>0){
			count++;
			if(count==m){
				printf("%c",i+'a');
			}
		}
		for(j=0;j<26;j++){
			if(map2[i][j]>0){
				count++;
				if(count==m){
					printf("%c%c",i+'a',j+'a');
				}
			}
			for(k=0;k<26;k++){
				if(map3[i][j][k]>0){
					count++;
					if(count==m){
						printf("%c%c%c",i+'a',j+'a',k+'a');
					}
				}
				for(l=0;l<26;l++){
					if(map4[i][j][k][l]>0){
						count++;
						if(count==m){
							printf("%c%c%c%c",i+'a',j+'a',k+'a',l+'a');
						}
					}
					for(p=0;p<26;p++){
						if(map5[i][j][k][l][p]>0){
							count++;
							if(count==m){
								printf("%c%c%c%c%c",i+'a',j+'a',k+'a',l+'a',p+'a');
							}
						}
					}
				}
			}
		}
	}
	
//	printf("計算部分終了\n");
	//出力
	
	//printf("%lld",ans);
	
//	printf("結果の出力終了\n");
	
	return 0;
	
}



Measured memory_bytes: 83968
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
int n,m,ans,_empty=0,_empty1=0,top=1,cnt1=0;
struct node{int l,r;
friend bool operator <(node a,node b){ return b.r<a.r;}
}p[200010],p1[200010],c;
bool cmp(node a,node b){return a.l<b.l;}
bool cmp1(node a,node b){return a.r<b.r;}
priority_queue<node>q;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d%d",&p[i].l,&p[i].r);
    sort(p+1,p+n+1,cmp);
    for(;p[top].l==0&&top<=n;top++) p1[++cnt1]=p[top];
    for (int i=1;i<=m;i++) 
    {
        _empty++;
        for(;p[top].l==i;top++)
        {
            if (_empty) _empty--,q.push(p[top]),ans++;
            else 
            {
                c=q.top();if (p[top].r>c.r) q.pop(),q.push(p[top]),p1[++cnt1]=c;
                else p1[++cnt1]=p[top];
            }
        }
    }
    sort(p1+1,p1+cnt1+1,cmp1);
    top=1;
    if (cnt1)
    {
        for (int i=m-_empty+1;i<=m;i++)
        {
            if (p1[top].r<=i&&top<=cnt1)ans++,top++;
        }        
    }

    printf("%d\n",n-ans);
    
}

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

int main()
{
    int a,b,c=0;

        cin >> a >> b >> c;

        if( a <= b ){
            if( c <= b && c >= a){
                cout << "Yes";
            }else{
                cout << "No";
            }
        }else if( b <= a ){
            if( c <= a && c >= b){
                cout << "Yes";
            }else{
                cout << "No";
            }
        }
}

Measured memory_bytes: 256
# AOJ 0009
import sys

ps = [0]*10**6
used = [False]*10**6
p = 0

def sieve():
  global p
  used[0] = used[1] = True

  for i in xrange(0,10**6):
    if not used[i]:
      ps[p] = i
      p+=1
      for j in xrange(i,10**6,i):
        used[j] = True

def upper_bound(x):
  lb = -1
  ub = p

  while ub-lb > 1:
    mid = lb+ub>>1

    if ps[mid] > x:
      ub = mid
    else:
      lb = mid

  return ub

sieve()

for i in sys.stdin:
  print upper_bound(int(i))

Measured memory_bytes: 21488
n=int(input())
min=10**10
max=-10**10
profit=max-min
for i in range(0,n):
    x=int(input())
    if(max < x and i!=0):
        max=x
        if(profit < max-min):
            profit=max-min
    if( x < min):
        min=x
        max=-10**10
print(profit)


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


int main() {

    int x, a, b;
    cin >> x >> a >> b;
    cout << (x - a) % b << endl;
    return 0;
}

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

int target;
int ans;
int maxv;

void dfs(int a, int sum, int cnt)
{
//      cout << "a= " << a << ",sum= " << sum << ",cnt= " << cnt << endl;
        if (cnt != 3 && a == maxv) {
                return;
        }
        sum += a;
        if (cnt == 3) {
//              cout << "sum= " << sum << endl;
                if (sum == target) {
                        ans++;
                }
                return;
        }

        for (int i = a+1; i <= maxv; ++i) {
                dfs(i, sum, cnt+1);
        }


}

int main()
{
        vector<int> n;
        vector<int> x;

        while (1) {
                int tmp1, tmp2;
                cin >> tmp1 >> tmp2;
                if (tmp1 == 0 && tmp2 == 0) {
                        break;
                }
                n.push_back(tmp1);
                x.push_back(tmp2);
        }
        int N = n.size();
        for (int i = 0; i < N; ++i) {

                maxv = n[i];
                target = x[i];

                ans = 0;
                for (int j = 0; j < maxv-2; ++j) {
                        int sum = 0;
                        dfs(j+1, sum, 1);

                }
                cout << ans << endl;


        }



}



Measured memory_bytes: 3144
import sys
input = lambda: sys.stdin.readline().rstrip()
n=int(input())
a=[] ; b=[]
for _ in range(n):
    a.append(input())
m=int(input())
for _ in range(m):
    b.append(input())
from collections import Counter
a=Counter(a)
b=Counter(b)
for i in b:
    if i in a:
        a[i]=max(0,a[i]-b[i])
print(max(a.values()))
        


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

int main() {
	int N; cin >> N;
	int max=0;
	int sum=0;
	for(int i=0; i<N; i++){
		int p; cin >> p;
		sum += p;
		if(p > max) max = p;
	}
	
	sum -= max/2;
	
	cout << sum;
	cout << endl;
	
	
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		long X = scn.nextLong();
		long[] A = new long[N + 1];
		long[] P = new long[N + 1];
		A[0] = 1;
		P[0] = 1;
		for(int i = 1;i <= N;i++) {
			A[i] = 2 * A[i-1] + 3;
			P[i] = 2 * P[i-1] + 1;
		}

		long ans = 0;
		int k = N;
		int n = N;
		while(X >0) {
			for(;k >= 0;k--) {
				if(X >= A[k] + (n-k)) {
					ans += P[k];
					X -= A[k] + (n - k);
					n = k;
					if(X > 0) {
						ans++;
						X--;
					}
					break;
				}
			}
			if(k == -1) {
				break;
			}
		}

		System.out.println(ans);

	}
}


Measured memory_bytes: 23252
from itertools import product
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        self.dist = [INF] * self.N # the distance of each vertex from s
        self.prev = [-1] * self.N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * self.N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            self.dist[v] = d; self.prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == self.N: break
            for u, c in self.E[v]:
                if visited[u]: continue
                temp = d + c
                if self.dist[u] > temp: heappush(heap, (temp, v, u))
        return self.dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

H, W = map(int, input().split())
dijkstra = Dijkstra(H * W)

def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)

grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
ans = 0 if grid[0][0] == '.' else 1
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            dijkstra.add_edge(v, u, 1)
        else:
            dijkstra.add_edge(v, u, 0)
dist = dijkstra.distance(0)
ans += dist[vtx(H-1, W-1)]
print(ans)

Measured memory_bytes: 7156
import sys
import copy
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

s = input()
c = Counter(s)
print('yes' if max(c.values()) < 2 else 'no')

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

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; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  multiset<int> res{};
  for (size_t i = 0; i < 3; ++i)
  {
    int k; cin >> k;
    res.emplace(k);
  }
  int K; cin >> K;
  for (int i = K; i > 0; --i)
  {
    auto it = res.end();
    --it;
    auto n = *it * 2;
    res.erase(it);
    res.emplace(n);
  }
  auto ans = boost::accumulate(res, 0);
  cout << ans << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
s = list(input())
ss = []
ss.append(s[0])
score = 0
for i in range(1,n):
    if(s[i] != s[i-1]):ss.append(s[i])
    else:score+=1

for i in range(k):
    if(len(ss) <=1):
        break
    if(len(ss) >2):
        ss.pop()
        ss.pop()
        score+=2
    else:
        ss.pop()
        score+=1


print(score)

Measured memory_bytes: 4648
#include<iostream>
using namespace std;
int main()
{
  unsigned  long long int n,i,sum=0,m;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if((i%3)!=0&&(i%5)!=0)
        {
            sum+=i;
            //cout<<i<<endl;
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3624
#include<stdio.h>
#define MOD 1000000007
typedef long long ll;
int main(){
	int n,m,i;
	scanf("%d%d",&n,&m);
	ll a=0,b=0,x;
	for(i=0;i<n;i++){
		scanf("%lld",&x);
		a+=x*(i-(n-i-1));
		a%=MOD;
	}
	for(i=0;i<m;i++){
		scanf("%lld",&x);
		b+=x*(i-(m-i-1));
		b%=MOD;
	}
	printf("%lld\n",(a*b)%MOD);
	return 0;
} 

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include<iomanip>
#define ll long long
#define pb push_back
#define mp make_pair
#define MOD 1000000007
using namespace std;
 
ll f[2000002];
 
ll p(ll x, ll n) {
	ll res = 1;
	while(n) {
		if(n&1) {
			res=(res*x)%MOD;
		}
		x=(x*x)%MOD;
		n/=2;
	}
	return res;
}
 
ll nCr(ll n, ll r) {
	ll ans=1;
	ans=(ans*f[n])%MOD;
	ans=(ans*p(f[r],MOD-2))%MOD;
	ans=(ans*p(f[n-r],MOD-2))%MOD;
	return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll r1,c1,r2,c2,sum=0,i;
    f[0]=1; 
    for(i=1;i<2000002;i++) f[i]=(f[i-1]*i)%MOD;
    
	cin >> r1 >> c1 >> r2 >> c2;
	for(i=c1;i<=c2;i++) {
		ll temp=nCr(r2+1+i,r2)-nCr(r1+i,r1-1);
		temp = (temp+MOD)%MOD;
		sum=(sum+temp)%MOD;
	}
    cout << sum << "\n";
    return 0;
}

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

using i64 = long long int;

i64 repeated_squaring(i64 x, i64 n) {
    i64 res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * x;
        x = x * x;
        n >>= 1;
    }
    return res;
}

int main(){
    i64 n, p;
    cin >> n >> p;
    i64 ans = 1;
    if(n >= 40){
        cout << 1 << endl;
    }else if(n == 1){
        cout << p << endl;
    }else{
        for(i64 i=2;i<10000000;++i){
            i64 tmp = repeated_squaring(i, n);
            if(tmp > p)break;
            if(p % tmp == 0)ans = i;
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
                        
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long

const int inf = (int)1e9;
int n, m, total;
int cost[1005], mask[1005];
vector <vector <int>> dp;


int solve(int idx, int cur) {
    if (idx == m + 1) {
        if (cur == total) 
            return 0;
        else 
            return inf;
    }
    int &ans = dp[idx][cur];
    if (ans != -1) 
        return ans;

    ans = min(solve(idx + 1, cur | mask[idx]) + cost[idx], solve(idx + 1, cur));

    return ans;
}
 
int32_t main()
{
    IOS
 
    cin >> n >> m;
    total = (1 << n) - 1;
    dp.resize(m + 5, vector <int> (total + 5, -1));
    for (int i = 1; i <= m; i++) {
        int a, b, temp = 0;
        cin >> a >> b;
        for (int j = 1, x; j <= b; j++) {
            cin >> x;
            temp |= ((1LL << (x - 1)));
        }
        cost[i] = a, mask[i] = temp;
    }
    int ans = solve(1, 0LL);
    
    if (ans == inf) ans = -1;
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 32640
N=int(input())
A=list(map(int,input().split()))
A1=max(A)
A2=(-1)
for i in range(N):
    if A[i]==A1:
        pass
    elif abs(A1/2-A[i])<abs(A1/2-A2):
        A2=A[i]
print(A1,A2)

Measured memory_bytes: 14052
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string a;
  cin>>a;
  int f=0;
  int ans=0;
  if(a.size()>1){
    for(int i=0;i<a.size();i++){
      if(f||a[i]=='9')ans+=9;
      else {
	f=1;
	if(i==0){
	  int ff=0;
	  for(int j=1;j<a.size();j++)if(a[j]!='9')ff=1;
	    if(ff)ans+=a[i]-'0'-1;
	    else ans+=a[i]-'0';
	}
	else ans+=a[i-1]-'0'-1;
      }
    }
  }else ans=a[0]-'0';
  cout<<ans<<endl;
  return 0;
}


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

int main() {
    
    int N, M, t[100], score[101] = { 0 };
    
    cin >> N >> M;
    for(int i = 0; i < M; i++)
        cin >> t[i];
    for(int i = 0; i < M; i++) {
        int f, cnt = 0;
        for(int j = 0; j < N; j++) {
            cin >> f;
            if(f == t[i]) score[j + 1]++;
            else cnt++;
        }
        score[t[i]] += cnt;
    }
    for(int i = 1; i <= N; i++)
        cout << score[i] << endl;
}

Measured memory_bytes: 1160
import collections

N = int(input())
a = list(map(int,input().split()))
b = collections.Counter(a)
dp = [0] * (max(a)+1)
if len(b) == 1 and a[0] == 0:
    print(N)
    exit()
dp[0] = b[0] + b[1]
dp[1] = dp[0] + b[2]

for i in range(2, max(a)+1):
    dp[i] = dp[i-1] + b[i+1] - b[i-2]
print(max(dp))


Measured memory_bytes: 14564
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod

#include <bits/stdc++.h>
using namespace std;
signed main(){
    int A,B,C,K; cin>>A>>B>>C>>K;
    if(K%2==0) cout<<A-B<<endl;
    else cout<<B-A<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    int n, m;
    cin >> n >> m;
    cout << (n - 1) * (m - 1) << endl;
}




Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>

int sp,A[1000];
void sou (int x);
int re();
int main()
{
int i,j;
char hi[100];
sp=0;

while(scanf ("%s",hi)!=EOF){
if (hi[0]=='+'){
i=re();
j=re();
sou(i+j);
}else if (hi[0]=='-'){
j=re();
i=re();
sou(i-j);
}else if (hi[0]=='*'){
i=re();
j=re();
sou(i*j);
}else {
sou(atoi(hi));
}
}
printf ("%d\n",re());
      
return 0;
}
void sou (int x){
A[++sp]=x;
}
int re() {
sp--;
return A[sp+1];
}
    



Measured memory_bytes: 2104
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 11000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;

int num[110000];

int main(){
  int X,A,B;
  cin>>X>>A>>B;

  X-=A;

  X-=(X/B)*B;

  cout<<X<<endl;
}


Measured memory_bytes: 256
A, B, H, M = map(int,input().split())

import math

a = H*360/12+M*(360/12)/60
b = M*360/60

n = math.radians(abs(b-a) if abs(b-a) <=180 else 360-abs(b-a))

print(math.sqrt(A**2+B**2-2*A*B*math.cos(n)))

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
typedef long long ll;
const int INT_INF = 1e9;
const ll INF = 1LL << 30;
const ll MOD = 1e9 + 7;


int main() {
    int n; cin >> n;
    V<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];

    V<int> dp(n + 1, INT_INF);
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i]);
        if(1 < i){
            dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i]);
        }
    }
    cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1024
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Leonardo Da Vinchchi
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABallDistribution solver = new ABallDistribution();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABallDistribution {
        public void solve(int testNumber, InputReader sc, PrintWriter out) {
            int n = sc.nextInt();
            int k = sc.nextInt();

            if (k == 1) {
                out.print("0");
                return;
            }

            int max = n - k + 1;
            int min = 1;
            out.print((max - min));
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21588
#include <iostream>
#include<algorithm>
#include<string>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main(){
	string s;
	cin>>s;
	
	bool alp[26];
	REP(i,26) alp[i]=false;
	
	REP(i,s.size()) alp[s[i]-'a']=true;
	
	REP(i,26){
		if(!alp[i]){
			cout<<char('a'+i)<<endl;
			return 0;
		}
	}
	
	cout<<"None"<<endl;
	return 0;
}//解説参考.

Measured memory_bytes: 512
#import<bits/stdc++.h>
#define f i].first
#define s i].second
using namespace std;pair<long,long>p[1<<18];long I,A,n,r,b,d,t,i;main(){d=I=b=1e9;for(cin>>n;i<n;i++){cin>>p[f>>p[s;if(p[f>p[s)swap(p[f,p[s);I=min(I,p[f),A=max(A,p[s),r=max(r,p[f),b=min(b,p[s);}i=~0;sort(p,p+n);t=(r-I)*(A-b);b=p[1+f,r=p[n+f;for(t=min(t,(A-I)*(r-b));++i<n;t=min(t,(A-I)*(r-b)))b=min(min(p[s,i-n+1?p[1+f:A),d),d=min(d,p[s),r=max(r,p[s);cout<<t;}

Measured memory_bytes: 4352
#include<stdio.h>

int cnt;

void insertion(int a[], int n, int g){
	int i, j, tmp;
	for(i=g; i<n; i++){
		tmp=a[i];
		j=i-g;
		while(j>=0&&a[j]>tmp){
			a[j+g]=a[j];
			j=j-g;
			cnt++;
		}
		a[j+g]=tmp;
	}
}

void shell(int a[], int n){
	int i;
	cnt=0;
	int m=1;
	int g[n];
	g[0]=1;
	while(1){
		g[m]=g[m-1]*3+1;
		if(g[m]>n)break;
		m++;
	}

	for(i=m-1; i>=0; i--){
		insertion(a, n, g[i]);
	}
	//出力
	printf("%d\n", m);
	for(i=m-1; i>=0; i--){
		if(i==0){
			printf("%d\n", g[i]);
		}else if(i>0){
			printf("%d ", g[i]);
		}
	}
	printf("%d\n", cnt);
	for(i=0; i<n; i++){
		printf("%d\n", a[i]);
	}	
}


int main(){
	int n, i;
	scanf("%d", &n);
	int nx[n];

	for(i=0; i<n; i++){
		scanf("%d", &nx[i]);
	}

	shell(nx, n);

	return 0;
}


Measured memory_bytes: 5592
#include <cstdio>

int main()
{
  int n;
  scanf("%d", &n);
  int s = 0;
  for (int i = 0, m = n; i < 10; ++i)
  {
    s += m % 10;
    m /= 10;
  }
  puts(n % s == 0 ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 128
import sys

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n, x = map(int, input().split())
    llist = list(map(int, input().split()))
    llist.insert(0, 0)

    res = 0
    sum = 0
    for l in llist:
        if (sum + l) <= x:
            res += 1
            sum += l
        else:
            break
    
    print(res)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
int main() {
	int N;
	cin >> N;
	vector<int>a(N);
	rep(i,N)cin >>a[i];
	int ans = 0;
	rep(i,N){
		if ( (i+1)%2 == 1 && a[i]%2 == 1 ) ans++;

	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3624
#[test]
fn test_solve() {
    assert_eq!(solve("3\n1 2 3\n"), "6\n");
    assert_eq!(solve("10\n3 1 4 1 5 9 2 6 5 3\n"), "237\n");
    assert_eq!(
        solve("10\n3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820\n"),
        "103715602\n"
    );
    assert_eq!(solve("2\n1152921504606846975 0"), "536396503\n");
    assert_eq!(solve("2\n1000000007 0"), "0\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let a: Vec<Vec<bool>> = (0..n)
        .map(|_| {
            let a: u64 = sc.read();
            (0..60).map(|i| a & (1 << i) != 0).collect()
        })
        .collect();
    let mut s = Finite(0);
    for i in 0..60 {
        let one = a.iter().filter(|&a| a[i]).count();
        let zro = n - one;
        s = s + Finite(one as u64) * Finite(zro as u64) * Finite((1 << i)%MOD);
    }
    format!("{}\n", s)
}
const MOD: u64 = 1_000_000_007;
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
struct Finite(u64);
impl std::fmt::Display for Finite {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}
impl std::ops::Sub for Finite {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        Finite((self.0 + MOD - rhs.0) % MOD)
    }
}
impl std::ops::Mul for Finite {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Finite(self.0 * rhs.0 % MOD)
    }
}
impl std::ops::Add for Finite {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Finite((self.0 + rhs.0) % MOD)
    }
}

fn main() {
    let mut buf = String::new();
    use std::io;
    use std::io::{Read, Write};
    io::stdin().read_to_string(&mut buf).unwrap();
    io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}

struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}


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

int main(void)
{
	char s[1000]; scanf("%s", s);
	int n = strlen(s);
	int r = 0;
	int cnt[30] = { 0 };
	cnt['A' - 'A'] = cnt['C' - 'A'] = cnt['G' - 'A'] = cnt['T' - 'A'] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			int ok = 1;
			for(int k=i;k<=j;k++)
				if (cnt[s[k]-'A'] == 0) ok = 0;
			if (ok)r = max(r, j - i + 1);
		}
	}
	printf("%d\n", r);
	return 0;
}

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



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

	long long n, m; cin >> n >> m;
	string s, t; cin >> s >> t;
	long long g = __gcd(m, n);
	long long l = m / g * n;
	for(long long i = 0; i < g; i++){
		long long p = n / g * i, q = m / g * i;
		if(s[p] != t[q]){
			cout << -1 << endl;
			return 0;
		}
	}
	cout << l << endl;
	return 0;	
}
  

Measured memory_bytes: 764
#define _DEBUG 1
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#ifdef _DEBUG
#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                         \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z     \
       << endl
#define check(s) cerr << s << endl
#else
#define dump(x)
#define dump2(x, y)
#define dump3(x, y, z)
#define check(s)
#endif

#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

void solve(ll A, ll B) {
  ll a = A == 1 ? A + 13 : A;
  ll b = B == 1 ? B + 13 : B;

  if (a > b)
    cout << "Alice" << endl;
  else if (a < b)
    cout << "Bob" << endl;
  else
    cout << "Draw" << endl;
}

int main() {
  ll A;
  scanf("%lld", &A);
  ll B;
  scanf("%lld", &B);
  solve(A, B);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


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

void YN(bool ans){
    if(ans)cout<<"Yes"<<endl;
    else cout <<"No"<<endl;
    return;
}

int main(){
    char x;
    cin>>x;
    if('A'<= x && x <= 'Z')cout<<'A';
    else cout<<'a';
    return 0;
}

Measured memory_bytes: 3608
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String indx = "abcdefghijklmnopqrstuvwxyz";
    int n = indx.indexOf(S);
    System.out.println(indx.charAt(n+1));
  }
}

Measured memory_bytes: 35856