akhauriyash/Code-Regression huggingface dataset:
H, W = map(int, input().split())
grid = [input() for _ in range(H)]

paintable = True

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            if i == 0:
                if j == 0:
                    if grid[i][j+1] == '.' and grid[i+1][j] == '.':
                        paintable = False
                elif j == W - 1:
                    if grid[i][j-1] == '.' and grid[i+1][j] == '.':
                        paintable = False
                else:
                    if grid[i][j+1] == '.' and grid[i+1][j] == '.' and grid[i][j-1] == '.':
                        paintable = False
            elif i == H - 1:
                if j == 0:
                    if grid[i][j+1] == '.' and grid[i-1][j] == '.':
                        paintable = False
                elif j == W - 1:
                    if grid[i][j-1] == '.' and grid[i-1][j] == '.':
                        paintable = False
                else:
                    if grid[i][j+1] == '.' and grid[i-1][j] == '.' and grid[i][j-1] == '.':
                        paintable = False
            else:
                if j == 0:
                    if grid[i][j+1] == '.' and grid[i-1][j] == '.' and grid[i+1][j] == '.':
                        paintable = False
                elif j == W - 1:
                    if grid[i][j-1] == '.' and grid[i-1][j] == '.' and grid[i+1][j] == '.':
                        paintable = False
                else:
                    if grid[i][j+1] == '.' and grid[i+1][j] == '.' and grid[i][j-1] == '.' and grid[i-1][j] == '.':
                        paintable = False
                    
if paintable:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <cctype>
using namespace std;
 
#define MD 1000000007
typedef long long int ll;

int main(){
    int n;
    cin>>n;
    ll mn=MD;
    for(int i=0;i<n;i++){
        ll tmp;
        cin>>tmp;
        ll cnt=0;
        while(tmp%2==0){
            tmp/=2;
            cnt++;
        }
        mn=min(mn,cnt);
    }
    cout<<mn<<endl;
    return 0;
}

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

#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)

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



int main() {
  int x,a,b;
  cin >>x>>a>>b;
  if(abs(a-x)>abs(b-x)) cout << "B" << endl;
  else cout << "A" << endl;
}

Measured memory_bytes: 3592
n = int(input())
l1 = [0] * n
l2 = [int(n) for n in input().split()]
b = 0
for p in range(1, n):
    s = l2[b] - l2[p] + l1[b]
    if s > 0:
        l1[p] = s
    b = p
print(sum(l1))


Measured memory_bytes: 33752
#include <iostream>

using namespace std;

int main(){
  string s;
  std::cin >> s;
  int ans = 0;
  for(int i=0; i<4; i++){
    if(s.at(i) == '+') ans++;
    else ans--;
  }
  std::cout << ans << '\n';
  return 0;
}


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

int N, K;
int INF = 1e9;
int mod = 1e9 + 7;

int power(int a, int n){
    if (n == 0) {
        return 1;
    } else if (n % 2 == 0) {
        int b = power(a, n / 2);
        return 1ll * b * b % mod;
    } else {
        return 1ll * a * power(a, n - 1) % mod;
    }
}

int inverse(int a) {
    if (a == 1) {
        return 1;
    }
    return power(a, mod - 2);
}

int main() {
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<int> factorial(N + 1, 1);
    for (int i = 1; i < N + 1; i++) {
        factorial[i] = 1ll * i * factorial[i - 1] % mod;
    }
    sort(A.begin(), A.end());
    long long ans = 0;
    int cnt;
    long long tmp;
    for (int i = 0; i < N; i++) {
        cnt = 0;
        int inv_f = inverse(factorial[K - 1]);
        if (i >= K - 1) {
            cnt = 1ll * factorial[i] * inv_f % mod * inverse(factorial[i - K + 1]) % mod;
        }
        if (i <= N - K) {
            cnt -= 1ll * factorial[N - 1 - i] * inv_f % mod * inverse(factorial[N - i - K]) % mod;
        }
        tmp = A[i] * cnt % mod;
        if (tmp < 0) {
            tmp += mod;
        }
        ans += tmp;
        ans %= mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1408
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

const int INF = 1000000007;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int mx = -INF, mi = INF;
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    rep(i,n){
        cin >> l[i] >> r[i];
        --l[i];
        chmax(mx, l[i]);
        chmin(mi, r[i]);
    }
    int ans = 0;
    rep(i,n) chmax(ans, max(mi - mx, 0) + r[i] - l[i]);
    vector<P> v;
    rep(i,n){
        int a = max(mi - l[i], 0);
        int b = max(r[i] - mx, 0);
        v.emplace_back(b, -a);
    }
    sort(v.begin(), v.end());
    int left = INF;
    rep(i,n){
        if(i > 0) chmax(ans, left + v[i].first);
        chmin(left, -v[i].second);
    }
    cout << ans << endl;
    return 0;
}


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

const int MOD=1000000007;
int INF=100100100;
int a[100010];
int main(){
  int n,k;cin>>n>>k;
  int p[3];cin>>p[0]>>p[1]>>p[2];
  string s;cin>>s;
  for(int i=0;i<n;i++){
    if(s[i]=='r')a[i]=2;
    if(s[i]=='s')a[i]=0;
    if(s[i]=='p')a[i]=1;
  }
  
  int ans=0;
  int ima=-1;
  for(int i=0;i<k;i++){
    for(int j=i;j<n;j+=k){
      if(j==i){
        ans+=p[a[j]];
        ima=a[j];
      }
      else{
        if(ima!=a[j]){
          ans+=p[a[j]];
          ima=a[j];
        }
        else{
          ima=-1;
        }
      }
    }
  }
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 896
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


s = S()
k = I()
counts = [1]
for i in range(1, len(s)):
    if s[i - 1] == s[i]:
        counts[-1] += 1
    else:
        counts.append(1)

# 文字が 1 種類
if len(counts) == 1:
    print(len(s) * k // 2)

else:
    ans = 0
    # 語頭と語尾が同じ文字でない
    if s[0] != s[-1]:
        for cnt in counts:
            ans += cnt // 2
        ans *= k

    # 語頭と語尾が同じ文字
    else:
        # 語頭と語尾(の連続する文字)を除いて考える
        for cnt in counts[1:-1]:
            ans += cnt // 2
        ans *= k
        # 一番初めの先頭の変換のぶんを足す
        ans += counts[0] // 2
        # 一番最後の末尾の変換のぶんを足す
        ans += counts[-1] // 2
        length = counts[0] + counts[-1]
        # k-1個あるsの境目の変換の回数
        ans += (length // 2) * (k - 1)

    print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long n; cin >>n;
  vector<long long>a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a.rbegin(),a.rend());
  long long kotae=0;
  for(int i=1;i<n;i++){
    kotae+=a[i/2];
  }
  cout<<kotae<<endl;
}

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

#define N 100

void print(int *, int);

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

    int n, key, j;
    cin>>n; // データの数の入力

    int array[N];
    for(int i = 0; i < n; i++) cin>>array[i]; //データの入力

    // insertionSort
    for(int i = 1; i < n; i++) {
        print(array, n); //出力
        
        key = array[i];
        j = i - 1;
        while(j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }

    print(array, n);  //出力
    return 0;
}

void print(int *a, int n) {
    //出力
    for(int i = 0; i < n - 1; i++) cout<<a[i]<<' ';
    cout<<a[n - 1]<<endl;
}



Measured memory_bytes: 3224
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		HashSet<Long> ha = new HashSet<Long>();

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {

			long tmp = sc.nextLong();

			if (ha.remove(tmp)) {
			} else {
				ha.add(tmp);
			}

		}

		System.out.println(ha.size());


	}

}


Measured memory_bytes: 62648
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 1000000007
int main(){
  string N;
  int K;
  cin>>N>>K;
  int n=N.size();

  vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(2,vector<ll>(K+1,0)));

  ll x=N.at(0)-'0';
  dp.at(0).at(0).at(1)=1;
  dp.at(0).at(1).at(1)=x-1;
  dp.at(0).at(1).at(0)=1;
  for(int i=1;i<n;i++){
    x=N.at(i)-'0';
    for(int j=1;j<=K;j++){
      dp.at(i).at(1).at(j)+=9*dp.at(i-1).at(1).at(j-1)+dp.at(i-1).at(1).at(j);
    }
    dp.at(i).at(1).at(0)+=dp.at(i-1).at(1).at(0);
    if(x!=0){
      for(int j=1;j<=K;j++){
        dp.at(i).at(1).at(j)+=(x-1)*dp.at(i-1).at(0).at(j-1);
        dp.at(i).at(0).at(j)+=dp.at(i-1).at(0).at(j-1);
      }
      for(int j=0;j<=K;j++){
        dp.at(i).at(1).at(j)+=dp.at(i-1).at(0).at(j);
      }
    }else{
      for(int j=0;j<=K;j++){
        dp.at(i).at(0).at(j)+=dp.at(i-1).at(0).at(j);
      }
    }
  }
  cout<<dp.at(n-1).at(1).at(K)+dp.at(n-1).at(0).at(K)<<endl;
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
//#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define PB push_back
#define MP make_pair
#define INF 1073741824
#define inf 1152921504606846976
#define pi 3.14159265358979323846
//#pragma comment(linker,"/STACK:10240000,10240000")
//mt19937 rand_(time(0));
const int N=3e5+7,M=2e6;
const long long mod=1e9+7;
inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元
//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}

ll dp[N];
int wi[N];
ll vi[N];
ll Max(ll x,ll y){
    if(x<y) return y;
    return x;
}
int main(){
    //freopen("1.txt","r",stdin);
    //ios::sync_with_stdio(false);
    int n,w;
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++){
        scanf("%d%lld",&wi[i],&vi[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=w;j>=wi[i];j--){
            dp[j]=Max(dp[j-wi[i]]+vi[i],dp[j]);
        }
    }
    printf("%lld\n",dp[w]);
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}




Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1000000000000000000;
long long mod=998244353;
using namespace std;


int main(){

int N;
cin>>N;
vector<int>d(N);
rep(i,N)cin>>d[i];

long long ans=1;
if(d[0]!=0)ans=0;

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

map<int,int>mp;
for(int i=1;i<N;i++){
    if(d[i]>1){
        ans*=mp[d[i]-1];
    }
    else if(d[i]==0)ans=0;

    mp[d[i]]++;
    if(ans>mod)ans%=mod;

}

cout<<ans<<endl;
return 0;
}
/*
4
0 1 1 2

2

4
1 1 1 1

0

7
0 3 2 1 2 2 1

24
*/


Measured memory_bytes: 5376
#include<iostream>
long long int MOD=1e9+7;
using namespace std;
long long int fact(long long int val)
{
    long long int te = 1;
    for (long long int i = 1; i <= val; i++)
    {


        te = (te*i);
        te = te%MOD;
    }
    return te;
}
int main() {
         int  n,m;
	cin>>n>>m;
	int N,M;
	N=max(n,m);
	M=min(n,m);
	if (N-M>1) {
        cout<<0;
        return 0;
	}
	else if (N-M==0){
        cout<<(2*fact(N)*fact(M)%MOD);
        return 0;
	}
	     cout<<(fact(N)*fact(M)%MOD);
		return 0;



}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(N: int, M: int, S: str, T: str):
    n = fractions.gcd(N, M)
    x = N * M // n

    flag = True
    for i in range(n):
        if S[i * x // M] == T[i * x // N]:
            pass
        else:
            flag = False
            break

    if flag:
        print (x)
    else:
        print (-1)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, M, S, T)

if __name__ == '__main__':
    main()


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

int main(){
	int N, x, i, j;
	scanf("%d%d", &N, &x);
	if(x == 1 || x == 2 * N - 1){
		printf("No\n");
	}
	else{
		printf("Yes\n");
		int *is_used = (int *)malloc(sizeof(int) * 2 * N);
		int *ans = (int *)malloc(sizeof(int) * 2 * N);
		for(i = 1; i < 2 * N; i++){
			is_used[i] = 0;
			ans[i] = -1;
		}
		if(x == 2){
			ans[N] = 2;
			ans[N + 1] = 1;
			is_used[2] = 1;
			is_used[1] = 1;
		}
		else{
			ans[N] = x;
			ans[N + 1] = x + 1;
			ans[N - 1] = x - 1;
			ans[N + 2] = x - 2;
			is_used[x] = 1;
			is_used[x + 1] = 1;
			is_used[x - 1] = 1;
			is_used[x - 2] = 1;
		}
/*		for(i = 1; i < 2 * N; i++){
			printf("%d  ", is_used[i]);
		}
		printf("\n");
		for(i = 1; i < 2 * N; i++){
			printf("%d  ", ans[i]);
		}
		printf("\n");
*/		for(i = 1, j = 1; i < 2 * N; i++){
			if(ans[i] > 0){
				printf("%d\n", ans[i]);
			}
			else{
				while(is_used[j] == 1 && j < 2 * N){
					j++;
				}
				printf("%d\n", j);
				j++;
			}
		}
	}
	return 0;
}

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

int main(){
  int x,a,b;
  cin >> x>>a>>b;
  if(b<=a){cout << "delicious" << endl;
          return 0;}
  if(b>a && b-a<=x){cout << "safe" << endl;
                   return 0;}else if(b>a && b-a>x){cout << "dangerous" << endl;}
}


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

using namespace std;

int main(void)
{
        string sp;
        string t;
        cin >> sp >> t;
        int spsize = sp.size();
        int tsize = t.size();
        int ichange = 0;
        int i;
        int j;

        for(i = spsize-1; i >= tsize-1; i--){
                for(j = 0; j < tsize; j++){
                        if(sp[i-j] == t[tsize-1-j] || sp[i-j] == '?')
                                continue;
                        break;
                }
                if(j == tsize){
                        for(j = 0; j < tsize; j++){
                                sp[i-j] = t[tsize-1-j];
                        }
                        for(j = 0; j < spsize; j++){
                                if(sp[j] == '?') sp[j] = 'a';
                        }
                        cout << sp << endl;
                        return 0;
                }
        }
        cout << "UNRESTORABLE";
        return 0;
}

Measured memory_bytes: 256
// C - Strange Bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

int dp[100001]; // dp[k]: k円引き出すのに必要な最小の回数

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

	vector<int> withdraw;

	withdraw.push_back(1);

	for (int i=1; pow(6, i) <= 100000; i++) {
		withdraw.push_back(pow(6, i));
	}

	for (int i=1; pow(9, i) <= 100000; i++) {
		withdraw.push_back(pow(9, i));
	}

	for (int i=1; i<=N; i++) {
		dp[i] = INF;
	}

	for (int w : withdraw) {
		for (int i=0; i<N; i++) {
			if (i + w <= 100000) {
				dp[i + w] = min(dp[i + w], dp[i] + 1);
			}
		}
	}

	cout << dp[N] << endl;

	return 0;
}

Measured memory_bytes: 4348
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N; cin >> N;
    long long ans = 1;
    vector<long long> A(N);

    for(auto &it:A){
        cin >> it;
        if(it == 0){
            cout << 0 << endl;
            return 0;
        }
    }

    for(int i=0; i<N; i++){
        if(1000000000000000000/ans < A.at(i)){
            cout << -1 << endl;
            return 0;
        }


        ans *= A.at(i);
        if(ans > 1000000000000000000){
            cout << -1 << endl;
            return 0;
        }
    }

    cout << ans << endl;


}

Measured memory_bytes: 3964
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <cassert>
#include <string>
using namespace std;

#define N1 3
#define N2 9  
#define LIMITMAX 100
//#define false 0
//#define true 1

struct PUZZLE{
  int f[N2], kuuhaku ,MD;/*マンハッタン距離*/
  //int cost;
};

static const int dx_123[4] = {0, -1, 0, 1};//４方向
static const int dy_123[4] = {1, 0, -1, 0};//４方向
static const char houkou[4] ={'r', 'u', 'l', 'd'};//右:right,　上:up,　左:left,　下:down

int ManhattanDistance[N2][N2];
PUZZLE jyoutai;
int limit;//深さのlimit
int miti[LIMITMAX];

int GetallManhattanDistance(PUZZLE);
bool dfs(int, int);
//int max(int, int);
//int min(int, int);
string  iterative_deepning(PUZZLE); //反復深化


int main(){

  int i,j,k;
  PUZZLE in;
  
  for(i=0;i<N2;i++){
    for(j=0;j<N2;j++){
      ManhattanDistance[i][j] = abs( i/N1 - j/N1 ) + abs(i%N1 -j%N1); 
    }
  }

   
  for(i=0;i<N2;i++){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] =  N2;
      in.kuuhaku = i;
    }
  }

  string kotae = iterative_deepning(in);

  cout << kotae.size();
  cout << endl;
 
  return 0;
}

/*
  void  swap(int *a , int *b){
  int *tmp;
  
  tmp = a;
  a = b ;
  b = tmp;
  
  }
*/
int GetallManhattanDistance(PUZZLE p){//全てのマンハッタン距離を取得する

  int goukei = 0;
  int i,j,k;

  for(i=0;i<N2;i++){
    if(p.f[i] == N2)continue;
    goukei += ManhattanDistance[i][p.f[i]-1];
  }

  return goukei;
}

bool dfs(int depth, int prev){

  int i,j,k;
  int r;
  int sx,sy;
  PUZZLE tmp;
  int tx,ty;
  
  if(jyoutai.MD == 0) return true ;
  //現在の深さにヒューリスティックを足して制限を超えたら枝を切る

  if( depth + jyoutai.MD > limit ) return false;

  sx = jyoutai.kuuhaku / N1;
  sy = jyoutai.kuuhaku % N1;

  for(r=0;r<4;r++){
    tx = sx + dx_123[r];
    ty = sy + dy_123[r];

    if(tx < 0 || tx >= N1 || ty < 0 || ty >= N1 ) continue;
    if(max(prev, r) - min(prev, r) == 2 ) continue;
    tmp = jyoutai;
    //マンハッタン距離の差分を計算しつつ、ピースをスワップ
    jyoutai.MD -= ManhattanDistance[tx * N1 + ty][jyoutai.f[tx * N1 + ty]-1];
    jyoutai.MD += ManhattanDistance[sx * N1 + sy][jyoutai.f[tx * N1 + ty]-1];
    swap(jyoutai.f[tx * N1 + ty], jyoutai.f[sx * N1 + sy]);
    jyoutai.kuuhaku = tx * N1 + ty;
    if( dfs(depth + 1, r) ){
      miti[depth] = r;
      return true;
    }
    jyoutai = tmp;
  }
  
  return false;
}
/*
  int max(int a, int b){
  if(a<b) return b;
  return a;
  }

  int min(int a, int b){
  if(a<b) return a;
  return b;
  }
*/




string  iterative_deepning(PUZZLE in){//反復深化

  int i,j,k;
  //string  kotae = "";
  //char kotae2[] = "unsolvable";
  
  in.MD = GetallManhattanDistance(in);//初期のマンハッタン距離

  for(limit = in.MD; limit <= LIMITMAX; limit++ ){
    jyoutai = in;
    if( dfs(0, -100) ){
      string kotae = "";
      for(i = 0; i < limit; i++) kotae += houkou[miti[i]];
      return kotae;
    } 
  }
  
  return "できませんでした";
  
}



Measured memory_bytes: 3228
#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;

int const MAX = 200002;
long long const MAX_A = 1000000000000002;
long long a[MAX];
long long l[MAX / 2 + 2], r[MAX / 2 + 2];

long long Merge(long long a[], int left, int mid, int right) {
	int i, j;
	long long cnt = 0;
	int n1 = mid - left;
	int n2 = right - mid;
	for (i = 0; i < n1; i++) {
		l[i] = a[left + i];
	}
	for (i = 0; i < n2; i++) {
		r[i] = a[mid + i];
	}
	l[n1] = MAX_A; r[n2] = MAX_A;
	i = 0; j = 0;
	for (int k = left; k < right; k++) {
		if (l[i] < r[j]) {
			a[k] = l[i];
			i++;
		}
		else {
			a[k] = r[j];
			j++;
			cnt += n1 - i;
		}
	}
	return cnt;
}
long long MergeSort(long long A[], int left, int right) {
	int mid;
	long long v1, v2, v3;
	if (left + 1 < right) {
		mid = (left + right) / 2;
		v1 = MergeSort(A, left, mid);
		v2 = MergeSort(A, mid, right);
		v3 = Merge(A, left, mid, right);
		return v1 + v2 + v3;
	}
	else { return 0; }
}
ll b[MAX];
ll c[MAX];
bool check(ll mid, ll n) {
	c[0] = 0;
	REP(i, 1, n) {
		if (b[i] <= mid) {
			c[i] = c[i - 1] + 1;
		}
		else {
			c[i] = c[i - 1];
		}
	}
	a[0] = 0;
	REP(i, 1, n) {
		a[i] = 2 * c[i] - i;
	}

	ll v = MergeSort(a, 0, n + 1);
	ll p = (n + 1)*n / 2 - v;	
	//cout << v <<  " "<< p << " " << mid << endl;

	return p > v;
}

int main() {
	ll n;
	cin >> n;
	REP(i, 1, n) {
		cin >> b[i];
	}
	ll lb = 0; ll ub = 1000000001;
	while (ub - lb > 1) {
		ll mid = (ub + lb) / 2;
		if (check(mid,n)) {
			ub = mid;
		}
		else {
			lb = mid;
		}
	}
	cout << ub << endl;
}

Measured memory_bytes: 5632
package main

import (
	"fmt"
)

func main() {

	var A, B, K int64
	fmt.Scan(&A, &B, &K)

	if (K<A) {
		A -= K
	} else if (K<A+B) {
		B = B-(K - A)
		A = 0
	} else {
		A = 0
		B = 0
	}

	fmt.Println(A, B)

}


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

int main(){
	int N,L;
	cin>>N>>L;
	vector<string> S(N);
	rep(i,N){
		cin>>S.at(i);
	}
	string strmin="";
	//rep(i,N){
	//	strmin=min(S.at(i)+strmin,strmin+S.at(i));
	//}
	sort(S.begin(),S.end());
	rep(i,N){
		cout<<S.at(i);
	}
	//cout<<strmin<<endl;
return 0;}

/*compile
g++ code.cpp
./a.out
run*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  int sum_a = 0;
  int sum_b = 0;
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) sum_a += vec.at(i);
    else sum_b += vec.at(i);
  }
  cout << sum_a - sum_b;
}
  


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(x, vis, c):
  global tmp
  if x == 1:
    tmp = min(tmp, c)
    return
  for i in range(10):
    if str(i) in vis:
      continue
    else:
      tami(i, vis+str(i), c+data[x][i])
    
H,W = IL()
data = [IL() for _ in range(10)]
wall = [IL() for _ in range(H)]
cost = [0]*10

for i in range(10):
  if i == 1:
    continue
  else:
    tmp = 100000
    tami(i, str(i), 0)
    cost[i] = tmp
#print(cost)

ans = 0
for h in range(H):
  for w in range(W):
    if abs(wall[h][w]) == 1:
      continue
    else:
      ans += cost[wall[h][w]]
print(ans)

Measured memory_bytes: 49756
package main

import "fmt"

func main() {
	var n, a, b int
	fmt.Scan(&n, &a, &b)

	var ans int
	for i := 1; i <= n; i++ {
		v := i
		s := 0
		for v > 0 {
			s += v % 10
			v /= 10
		}
		if s >= a && s <= b {
			ans += i
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
package main

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

var (
	timer                  int
	prenum, parent, lowest []int
	visited                []bool
)

type Graph [][]int

func (g *Graph) dfs(current, prev int) {
	prenum[current], lowest[current] = timer, timer
	timer++

	visited[current] = true

	next := 0
	for i := 0; i < len((*g)[current]); i++ {
		next = (*g)[current][i]
		if !visited[next] {
			parent[next] = current
			g.dfs(next, current)
			lowest[current] = min(lowest[current], lowest[next])
		} else if next != prev {
			lowest[current] = min(lowest[current], prenum[next])
		}
	}
}

func (g *Graph) artPoints(n int) string {
	g.dfs(0, -1)

	ap := make(map[int]struct{}, n)
	np := 0
	for i := 1; i < n; i++ {
		p := parent[i]
		if p == 0 {
			np++
		} else if prenum[p] <= lowest[i] {
			ap[p] = struct{}{}
		}
	}

	if np > 1 {
		ap[0] = struct{}{}
	}

	keys := make([]int, len(ap))
	idx := 0
	for k := range ap {
		keys[idx] = k
		idx++
	}

	sort.Ints(keys)

	var out bytes.Buffer
	for _, k := range keys {
		out.WriteString(fmt.Sprintln(k))
	}

	return out.String()
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	m, _ := strconv.Atoi(sc.Text())

	timer = 1
	visited = make([]bool, n)
	prenum = make([]int, n)
	parent = make([]int, n)
	lowest = make([]int, n)

	g := make(Graph, n)

	for i := 0; i < m; i++ {
		sc.Scan()
		s, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		t, _ := strconv.Atoi(sc.Text())
		g[s] = append(g[s], t)
		g[t] = append(g[t], s)
	}

	return g.artPoints(n)
}

func main() {
	fmt.Print(answer(os.Stdin))
}



Measured memory_bytes: 5048
/*input
10
*/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>
 
using namespace std; 
 
int GCD(int x,int y){return y?GCD(y,x%y):x;}
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,n) for(int i=0;i<(n);i++)
#define repl(i,a,b) for(int i=(a);i<(b);i++)
#define repm(i,a,b) for(int i=(a);i>(b);i--)
#define rept(v) for(auto it=v.begin();it<v.end();it++)
#define all(v) v.begin(),v.end()
const int INF = 1<<30;
typedef long long ll;
typedef pair<int,int> pii;
 
int const CONS = 1e7+3;
int sv[CONS];
ll dp[CONS];
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	rep(i, CONS){sv[i]=INF;dp[i]=0;}
	repl(i, 2, n+1) {
		if(sv[i]!=INF) continue;
		for(int j=i+i; j<=n; j+=i) sv[j]=min(sv[j],i);
	}
	rep(i, n+1) if(sv[i]==INF) dp[i]=2;
	dp[1]=1;
	repl(i, 4, n+1) {
		if(sv[i]==INF) dp[i]=2;
		else {
			int v=i,cnt=0;
			while(v%sv[i]==0){v/=sv[i];cnt++;}
			dp[i]=dp[v]*(1+cnt);
		}
	}
	ll ans=0;
	repl(i, 1, n+1) ans+=dp[i]*i;
	cout << ans;
	return 0;
}

Measured memory_bytes: 120788
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define LL long long
#define mod 1000000007
#define hmod 300007
using namespace std;

LL n;
LL info[300007],Prev[1000000],val[1000000],cnt_e;
LL key[2][1000000];

LL Insert(LL u,LL v,LL cst)
{
    LL k = (u % hmod + v % hmod) % hmod;
    if(cst==-1)
    {
        for(LL i=info[k];i;i=Prev[i])
            if(key[0][i] == u && key[1][i] == v)
                return val[i];
        return -1;
    }
    else Prev[++cnt_e] = info[k] , info[k] = cnt_e , val[cnt_e] = cst , key[0][cnt_e] = u , key[1][cnt_e] = v;
}

LL dfs(LL u,LL v)
{
	//printf("in:%lld %lld\n",u,v);
	u=min(u,v);
    if(v<0) return 0;
    if(v==0) return 1;
    LL tmp;
    if((tmp=Insert(u,v,-1))!=-1) return tmp;
    //printf("%lld %lld\n",u,v);
    //printf("%lld %lld %lld %lld %lld %lld\n",u>>1,v>>1,(u-1)>>1,(v-1)>>1,u>>1,(v-2)>>1);
    tmp = ((dfs(u >> 1 ,v >> 1) + dfs((u-1) >> 1 , (v-1) >> 1)) % mod + dfs(u>>1 , (v-2)>>1)) % mod;
    // 从低到高枚举数位，三种情况：a & 1 == b & 1 = 0 , (a & 1 == 1) ^ (b & 1 == 1) = 1 , a & 1 == b & 1 = 1
    Insert(u,v,tmp);
    //printf("%lld %lld:%lld\n",u,v,tmp);
    return tmp;
}

int main()
{
    scanf("%lld",&n);
    printf("%lld",dfs(n,n));
}

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

#define LEN(x) (int)x.size()
#define ALL(x) x.begin(), x.end()

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

const int MOD = 1000'000'007;
const double EPS = 0.000'000'001;

inline int fcmp(double x, double y)
{ return (x < y + EPS ? (x < y - EPS ? -1 : 0) : 1);}

const int N = 3010;
double dp[N][N];
double h[N], t[N];
int n;

double solve(int i, int j)
{
	if(i == n)
	{
		if(n - j < j)
			return 1;
		return 0;
	}

	double& r = dp[i][j];

	if(r == -20.0)
	{
		r = h[i] * solve(i + 1, j + 1) + t[i] * solve(i + 1, j);
	}

	return r;
}

int main()
{
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);
	cout.precision(10);
	
	cin >> n;

	for(int i = 0; i < n; i++) cin >> h[i], t[i] = 1 - h[i];

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
	 		dp[i][j] = -20.0;

	cout << solve(0, 0) << endl;
	
	//cerr << "Tempo de execucao: " << (double)clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

Measured memory_bytes: 71040
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
#define dmp(x) cerr << __LINE__ << " " << #x << " " << x << endl;
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
template<class T>
using MaxHeap = priority_queue<T>;
template<class T>
using MinHeap = priority_queue<T,vector<T>,greater<T> >;
template<class T,class U>
ostream& operator << (ostream& os,pair<T,U>& p){
  os << p.fi << ',' << p.sec; return os;
}
template<class T,class U>
istream& operator >> (istream& is,pair<T,U>& p){
  is >> p.fi >> p.sec; return is;
}
template<class T>
ostream& operator << (ostream &os,const vector<T> &vec){
  for(int i=0;i<vec.size();i++){
    os << vec[i];
    if(i+1<vec.size())os << ' ';
  }
  return os;
}
template<class T>
istream& operator >> (istream &is,vector<T>& vec){
  for(int i=0;i<vec.size();i++)is >> vec[i];
  return is;
}
void fastio(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout<<fixed<<setprecision(20);
}
int N;
int dp[100100];
int main(){
  fastio();
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++)cin >> A[i];
  reverse(all(A));
  for(int i=1;i<=N;i++)dp[i] = INF;
  dp[0] = -1;
  int ans = 0;
  for(int i=0;i<N;i++){
    int k = upper_bound(dp,dp+N+1,A[i])-dp;
    dp[k] = A[i];
    chmax(ans,k);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m,K=IA()
a=["" for i in range(0,n)]
for i in range(0,n):
    a[i]=input()

ans=n*m+1
for k in range(0,1<<(n-1)):
    res=0
    temp=[]
    for j in range(0,(n-1)):
        if (k&(1<<(j)))!=0:
            temp.append(j)
            res+=1
    le=len(temp) 
    if le==0:
        temp.append(n-1)
        
    if temp[le-1]!=n-1:
        temp.append(n-1)
        
    le=len(temp) 
  


    
    sum1=[0 for i in range(0,11)]
    flag=0
    for j in range(0,m):
        if flag==1:break
        last=0
        for t in range(0,le):
            for w in range(last,temp[t]+1):
                if a[w][j]=='1':
                    sum1[t]+=1
            last=temp[t]+1
            
            if sum1[t]>K:
                res+=1
                last=0
                sum1=[0 for i in range(0,11)]
                for t1 in range(0,le):
                    if flag==1:break
                    for w1 in range(last,temp[t1]+1):
                        if a[w1][j]=='1':
                            sum1[t1]+=1
                    
                    if sum1[t1]>K:
                        flag=1
                        res=n*m+1
                        break
                    last=temp[t1]+1
                break
        if flag==1:break
     
    ans=min(res,ans)
                
            
    
print(ans)
    
    
    




            



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

int D;
long long G;
vector<long long> p, c;

int main() {
  cin >> D >> G;
  p.resize(D); c.resize(D);
  for (int i = 0; i < D; ++i) cin >> p[i] >> c[i];

  long long res = 1<<29;
  for (int bit = 0; bit < (1<<D); ++bit) {
    long long sum = 0;
    long long num = 0;
    for (int i = 0; i < D; ++i) {
      if (bit & (1<<i)) sum += c[i] + p[i] * 100 * (i+1), num += p[i];
    }
    if (sum >= G) res = min(res, num);
    else {
      for (int i = D-1; i >= 0; --i) {
        if (bit & (1<<i)) continue;
        for (int j = 0; j < p[i]; ++j) {
          if (sum >= G) break;
          sum += 100 * (i+1);
          ++num;
        }
      }
      
      
      
      
      
      
      
      res = min(res, num);
    }
  }
  cout << res << endl;
}

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

int main() {
	double v, t, y;
	while (scanf("%lf", &v) != EOF) {
		printf("%d\n", (int)ceil((4.9 * (v / 9.8) * (v / 9.8) + 5.0) / 5.0));
	}
	return 0;
}

Measured memory_bytes: 632
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	bool ans=true;
	vl v(n);
	rep(i,n)cin>>v[i];
	if(n%3!=0){
		rep(i,n)ans&=(v[i]==0);
	}
	else{
		map<ll,ll> mp;
		rep(i,n)mp[v[i]]++;
		if(mp.size()==1){
			ans=v[0]==0;
		}
		else if(mp.size()==2){
			ll cnt=0;
			for(auto x:mp){
				if(x.fs==0){
					ans&=(x.sc==(n/3));
					cnt++;
				}
				else ans&=(x.sc==(n*2/3));
			}
			ans&=(cnt==1);
		}
		else if(mp.size()==3){
			ll tmp=0;
			for(auto x:mp){
				tmp^=x.fs;
				ans&=(x.sc==(n/3));
			}
			ans&=(tmp==0);
		}
		else ans=false;
	}
	Yn(ans);
}


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

int main(){
    ll n,m;cin>>n>>m;
    v a(n); vector<P> c(m);
    
    rep(i,n)cin >> a[i];
    rep(i,m)cin >> c[i].second >> c[i].first;
    
    sort(a.begin(), a.end());
    sort(c.rbegin(), c.rend());
    
    ll itr = 0;
    v b(n,0);
    
    rep(i,m){
        ll len = min( c[i].second, n-itr );
        for(int j=itr; j<itr+len; j++)
            b[j] = c[i].first;
        itr += len;
        if(itr==n)break;
    }
    
    ll ans = 0;
    rep(i,n)
        ans += max(a[i], b[i]);
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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 (b<a) { a=b; return 1; } return 0; }

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );



int main(void){

  ll a,b;
  cin>>a>>b;

  if( (b-1)%(a-1)==0 ) cout << (b-1) / (a-1) << endl;
  else cout << (b-1) / (a-1) +1 << endl;

  return 0;

}

ll mod_pow(ll x,ll r){
  if(r==0) return 1;
  else if(r==1) return x%mod;
  else if(r%2==0){
    ll t=mod_pow(x,r/2)%mod;
    return t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

ll mod_div(ll a,ll b){
  return mod_mul(a,mod_pow(b,mod-2));
}

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}


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

//using namespace--------------------------------------------------------------------------------------------------------------
using namespace std;

//define-----------------------------------------------------------------------------------------------------------------------
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1 << 25
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x) cerr << #x << " = " << (x) << "\n";
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)

//typedef----------------------------------------------------------------------------------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;

//const------------------------------------------------------------------------------------------------------------------------
const double EPS = 1e-10;
const double PI = acos( -1.0 );

//global-----------------------------------------------------------------------------------------------------------------------
int a, b;

//function---------------------------------------------------------------------------------------------------------------------
int main() {
	while ( scanf( "%d %d", &a, &b ) != EOF ) {
		a += b;
		int ans = 0;
		while ( true ) {
			if ( a / 10 == 0 && a % 10 == 0 ) {
				break;
			}
			ans++;
			a /= 10;
		}
		printf( "%d\n", ans );
	}
	return 0;
}

Measured memory_bytes: 1188
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(),x.end()

int main()
{
  int N;
  cin >> N;
  int dp[N];
  int H[N];
  for (int i = 0; i < N; ++i) {
    cin >> H[i];
  }
  dp[1] = abs(H[1]-H[0]);
  for (int i = 2; i < N; ++i) {
    dp[i] = min( dp[i-1]+abs(H[i]-H[i-1]), dp[i-2]+abs(H[i]-H[i-2]));
  }
  cout << dp[N-1] << "\n";
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
using namespace std;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
const double pi = acos(-1.0);
int read()
{
	int ret=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret;
}
int main()
{
 	#ifdef TEST
	 	freopen("input.txt","r",stdin);
	#endif
	map<char,int> m;
	m.clear();
	char s[30];
	scanf("%s",s);
	for(int i=0;i<strlen(s);i++)
	{
		m[s[i]]++;
		if(m[s[i]]>=2)
		{
			puts("no");
			return 0;
		}
	 } 
	 puts("yes");
	return 0;
}



Measured memory_bytes: 256
n, *a = map(int, open(0).read().split())

cant = 0
stack = []
for i in range(n, 0, -1):
        tmp = len(a)
        for j in range(len(a)-1, -1, -1):
                if j+1==a[j]:
                        if j>i: cant = 1
                        a.pop(j)
                        stack.append(j+1)
                        break
        if len(a)==tmp: cant = 1

if cant: print(-1)
else:
        for i in stack[::-1]: print(i)

Measured memory_bytes: 3064
a = [int(input())]
i = 0
while True:
    if a[i]%2 == 0:
        a.append(int(a[i]/2))
    else:
        a.append(int((3*a[i])+1))
    if  a.count(a[i]) == 2:
        break
    i += 1

print(i+1)


Measured memory_bytes: 61860
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
  double x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;

  cout << fixed << setprecision(5);
  cout << sqrt(pow((x2 - x1), 2) + pow((y2 - y1), 2)) << endl;
}


Measured memory_bytes: 3248
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int N;
        String S;
        long MOD_NUM = 1000_000_007;
        List<Long> list = new ArrayList<>();
        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            S = sc.next();
        }

        char[] chS = S.toCharArray();
        Set<Character> set = new HashSet<>(24);
        Map<Character, Integer> map = new HashMap<>(24);
        for (Character c : chS) {
            set.add(c);
            Integer v = map.getOrDefault(c, 0);
            map.put(c, ++v);
        }

        int typeNum = set.size();
        int[] arr = new int[typeNum];
        int index = 0;
        for (Map.Entry<Character, Integer> entry :map.entrySet()) {
            int value = entry.getValue();
            arr[index] = value +1;
            index++;
        }
        long result = 1;
        for (int i = 0; i < arr.length; i++) {
            result *= arr[i];
            result = result % MOD_NUM;

        }
        System.out.println(result-1);
    }


}


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

char s[105];

int cur[30], mx[30];

int main() {
    scanf(" %s", s);
    for (int i = 0; s[i]; i++) {
        for (int j = 0; j <= 26; j++) {
            cur[j] = s[i]-'a' == j ? 0:cur[j]+1;
            mx[j] = max(mx[j],cur[j]);
        }
    }
    int ans = 1e9;
    for (int i = 0; i < 27; i++) ans = min(ans,mx[i]);
    printf("%d\n", ans);
}

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

int N;

void out(int* arr){
	for(int i=0; i<N; i++) {
		cout << arr[i];
		if(i!=N-1) cout << " ";
	}
	cout << endl;
}

int main(){
	int minj, tmp, count=0;
	cin >> N;
	int* A = new int[N];

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

//selection sort
	for(int i=0; i<N; i++){
	     minj = i;
	     for(int j=i; j<N; j++){
			 if(A[j]<A[minj]) {
				minj=j;
			 }
		 }
		 if(minj!=i) count++;
		 tmp=A[i];
		 A[i]=A[minj];
		 A[minj]=tmp;
	}
	out(A);
	cout << count << endl;

	return 0;
}



Measured memory_bytes: 3092
#include <iostream>
#include <cstdio>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>

#include <numeric>
#include <algorithm>
#include <functional>

#include <cctype>

#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(unsigned int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                                                  it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))

typedef long long ll;
typedef complex<double> P;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;
const int days[] = {31,28,31,30,31,30,31,31,30,31,30,31};
const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31};

int main(){
    while(true){
        int N,M;
        cin >> N >> M;
        if(N==0) break;
        vector<pair<int,int> > V;
        rep(i,N){
            int D,P;
            cin >> D >> P;
            V.push_back(mp(P,D));
        }
        sort(rall(V));
        int ret = 0;
        rep(i,N){
            int mi = min(M,V[i].second);
            M -= mi;
            ret += V[i].first * (V[i].second-mi);
        }
        cout << ret << endl;
    }
    return 0;
}

Measured memory_bytes: 1328
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#define REP(i,n) for(int i = 0; i < n; i++)
#define REP(j,n) for(int j = 0; j < n; j++)

using namespace std;
typedef pair<int, int> P;

int main() {
    int n,r,l;
    cin >> n;
    cin >> r;
    cin >> l;
    int list[n+1];
    int time[n+1];
    for(int i = 0; i < n+1; i++) {
        list[i] = 0;
        time[i] = 0;
    }
    int top = 0;
    int id  = 1;
    int nowtime = 0;
    int timemax = 0;
    int timemaxid = 0;
    for(int i = 0; i < r; i++) {
        int d,t,x;
        cin >> d;
        cin >> t;
        cin >> x;
        time[id] += t - nowtime;
        if(time[id] > timemax) {
            timemax = time[id];
            timemaxid = id;
        }
        nowtime = t;
        list[d] += x;
        if(id == d) {
            top += x;
        }
        if(x < 0 && d == id) {
            for(int j = 1; j < n+1; j++) {
                if(top < list[j] || (top == list[j] && j < id)) {
                    top = list[j];
                    id = j;
                }
            }
            
        }
        if(x > 0 && d != id) {
            if(top < list[d] || (top == list[d] && d < id)) {
                top = list[d];
                id = d;
            }
        }

    }
    time[id] += l - nowtime;
    if(time[id] > timemax) {
        timemax = time[id];
        timemaxid = id;
    }
    cout << timemaxid << "\n";
}

Measured memory_bytes: 1944