akhauriyash/Code-Regression huggingface dataset:
let count s b =
  let rec count' s i b cnt =
    if i >= String.length s then cnt
    else if b = (s.[i] = '0') then count' s (i + 1) (not b) cnt
    else count' s (i + 1) (not b) (cnt + 1) in
  count' s 0 b 0
;;

let () = Scanf.scanf "%s" (fun s -> 
  min (count s true) (count s false) |> print_int
);;

Measured memory_bytes: 2560
#include <stdio.h>

int main(void) {

	int diceo[6];
	int dicet[6];
	int copy[4];
	int tatea[7] = { 0, 1, 5, 4, 0, 1, 5 };
	int tateb[7] = { 0, 4, 5, 1, 0, 4, 5 };
	int yokoa[7] = { 1, 2, 4, 3, 1, 2, 4 };
	int yokob[7] = { 1, 3, 4, 2, 1, 3, 4 };
	int hokaa[7] = { 0, 2, 5, 3, 0, 2, 5 };
	int hokab[7] = { 0, 3, 5, 2, 0, 3, 5 };
	int ue[6] = { 2, 3, 0, 5, 4, 1 };
	int sita[6] = { 3, 2, 5, 0, 1, 4 };
	int choice[7];
	int co = 0;
	int coo = 0;
	int cot = 0;
	int i, j, k;

	for (i = 0; i < 6; i++) {
		scanf("%d", &diceo[i]);
		coo += diceo[i];
	}

	for (i = 0; i < 6; i++) {
		scanf("%d", &dicet[i]);
		cot += dicet[i];
	}

	if (coo != cot) {
		printf("No\n");
		return 0;
	}

	for (i = 0; i < 6; i++) {
		for (j = 0; j < 7; j++) {
			switch (i) {
			case 0:choice[j] = tatea[j];
				break;
			case 1:choice[j] = tateb[j];
				break;
			case 2:choice[j] = yokoa[j];
				break;
			case 3:choice[j] = yokob[j];
				break;
			case 4:choice[j] = hokaa[j];
				break;
			case 5:choice[j] = hokab[j];
				break;
			}
		}
		for (j = 0; j < 4; j++) {
			for (k = 0; k < 4; k++) {
				copy[k] = choice[k + j];
			}
			for (k = 0; k < 4; k++) {
				coo = diceo[yokoa[k]];
				cot = dicet[copy[k]];
				if (coo == cot) co++;
			}
			if (co == 4) {
				if (diceo[0] == dicet[ue[i]]) co++;
				if (diceo[5] == dicet[sita[i]]) co++;
			}
			if (co == 6) {
				printf("Yes\n");
				return 0;
			}
			co = 0;
		}
	}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 580
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<iomanip>

#define rep(i, n) for (int i = 0; i < n; i++) 
#define rrep(i, n) for(int i = n-1; i>=0; i--)
#define range(i, n, m) for (int i = n; i < m; i++) 
#define rrange(i, n, m) for (int i = n - 1; i => m; i--) 
#define MOD 1000000007

typedef long long int ll;
typedef unsigned long long int ull;


using namespace std;

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

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

	ll N, M;
	ll A, B, C;
	string S, T;

	vector<ll> in(5);
	ll max = 10;
	ll sum = 0;


	rep(i, 5) {
		cin >> in[i];
		if (max > in[i]%10) {
			if(in[i]%10 != 0) max = in[i]%10;
		}

		in[i] = (ll)(round(in[i] * 0.1 + 0.4) * 10);
		sum += in[i];
	}


	cout << sum-10+max << endl;


	





	
	return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	cout << N * (N % 2 + 1) << "\n";

	return 0;
}

Measured memory_bytes: 256
// Author : Chi
// created : Sunday 2020-05-31
// Sawal : https://www.codechef.com/LTIME84B/problems/TREDIFF

//header files
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//namespaces
using    namespace __gnu_pbds;
using    namespace std;
typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set;

//macros
#define ll 		    long long
#define ss          second
#define ff          first
#define vi          vector<int>
#define vll         vector<long long>
#define pb(x)       push_back(x)
#define TEST  	    int TesT;cin>>TesT;while(TesT--)solve();
#define TEST1       solve();
#define mod         998244353
#define r0n(i,n)    for(ll i = 0; i < n; ++i)
#define r1n(i,n)    for(ll i = 1; i <= n; ++i)
#define pdp(d,i)    fixed<<setprecision(i)<<d
#define CHI         ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define db(...)     __f(#__VA_ARGS__, __VA_ARGS__)                      //for debugging
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
//LOVE ALGO
ll maxi(ll *a,ll s,ll e);
ll dpma[3000][3000];
ll dpmi[3000][3000];
ll mini(ll *a,ll s,ll e){
    if(s==e)
        return 0;
    if(dpmi[s][e]!=-1)
        return dpmi[s][e];
    ll ans1=maxi(a,s+1,e);
    ll ans2=maxi(a,s,e-1);
    return dpmi[s][e]=min(ans1,ans2);
}
ll maxi(ll *a,ll s,ll e){
    if(s==e)
        return a[s];
    if(dpma[s][e]!=-1)
        return dpma[s][e];
    ll ans1=a[e]+mini(a,s,e-1);
    ll ans2=a[s]+mini(a,s+1,e);
    return dpma[s][e]=max(ans1,ans2);
}
void solve(){
    ll n;
    cin>>n;
    ll a[n];
    ll s=0;
    memset(dpma,-1,sizeof dpma);
    memset(dpmi,-1,sizeof dpmi);
    r0n(i,n){
        cin>>a[i];
        s+=a[i];
        }
    ll A=maxi(a,0,n-1);
    ll B=s-A;
    cout<<A-B;
}

// Driver Code
int main(){
    CHI
    TEST1
    return 0;
}



Measured memory_bytes: 141056
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
N = int(input())

D = [int(input()) for j in range(N)]
D = list(set(D))


for i in range(len(D)):
    if D[i] == A[0]:
        A[0] = -1
    elif D[i] == A[1]:
        A[1] = -1
    elif D[i] == A[2]:
        A[2] = -1
    elif D[i] == B[0]:
        B[0] = -1
    elif D[i] == B[1]:
        B[1] = -1
    elif D[i] == B[2]:
        B[2] = -1
    elif D[i] == C[0]:
        C[0] = -1
    elif D[i] == C[1]:
        C[1] = -1
    elif D[i] == C[2]:
        C[2] = -1
    else:
        continue
    



if (A[0] == -1 and A[1] == -1 and A[2] == -1)or(B[0] == -1 and B[1] == -1 and B[2] == -1)or(C[0] == -1 and C[1] == -1 and C[2] == -1)or(A[1] == -1 and B[1] == -1 and C[1] == -1)or(A[0] == -1 and B[0] == -1 and C[0] == -1)or(A[2] == -1 and B[2] == -1 and C[2] == -1)or(A[0] == -1 and B[1] == -1 and C[2] == -1)or(A[2] == -1 and B[1] == -1 and C[0] == -1):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 62176
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int simulate(const string &S, int color)
{
	int ans = 0;
	for (auto c : S) {
		if (c - '0' != color) {
			++ans;
		}
		color = 1 - color;
	}
	return ans;
}

int main()
{
	string S;
	cin >> S;
	
	int ans = min(simulate(S, 0), simulate(S, 1));
	cout << ans << endl;
}


Measured memory_bytes: 512
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int gcd(int a,int b){if(a<b){swap(a,b);}if(b==0){return a;}return gcd(a%b,b);}
int main(void){
	int w,a,b;
	cin>>w>>a>>b;
	if(a>b){swap(a,b);}
	if(a+w>b){cout<<0<<endl;}
		else{cout<<(b-a-w)<<endl;}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <tuple>
#include <algorithm>
#include <memory>
#include <numeric>
#include <queue>
#include <functional>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>

using namespace std;
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 long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

const ll INF = 1LL << 60;

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

	ll N;

	cin >> N;

	vector<bool> prime_numbers_flag(N+1, true);
	prime_numbers_flag[0] = false;
	prime_numbers_flag[1] = false;

	for (ll i = 2; i <= N; ++i)
	{
		if (prime_numbers_flag[i])
		{
			for (ll j = i * 2; j <= N; j += i)
			{
				prime_numbers_flag[j] = false;
			}
		}
	}

	vector<ll> prime_numbers;
	for (ll i = 0; i <= N; ++i)
	{
		if (prime_numbers_flag[i]) prime_numbers.push_back(i);
	}



	vector<vector<ll>> elements(N+1);
	elements[0] = vector<ll>(prime_numbers.size(), 0);

	for (ll i = 1; i <= N; ++i)
	{
		elements[i] = elements[i - 1];
		ll tmp = i;
		for (ll p_i = 0; p_i < (ll)prime_numbers.size(); ++p_i)
		{
			if (tmp % prime_numbers[p_i] == 0)
			{
				tmp /= prime_numbers[p_i];
				elements[i][p_i] += 1;
				p_i--;
			}
		}
	}



	ll tmp2 = 0;
	ll tmp4 = 0;
	ll tmp14 = 0;
	ll tmp24 = 0;
	ll tmp74 = 0;
	for (auto e : elements[N])
	{
		if (e >= 2) tmp2++;
		if (e >= 4) tmp4++;
		if (e >= 14) tmp14++;
		if (e >= 24) tmp24++;
		if (e >= 74) tmp74++;
	}

	ll ans = tmp4*(tmp4 - 1)*(tmp2 - 2) / 2;
	ans += max(0LL, tmp14 * (tmp4 - 1));
	ans += max(0LL, tmp24 * (tmp2 - 1));
	ans += tmp74;

	cout << max(0LL, ans) << endl;

	system("pause");
}


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

#define MAX_N 100

void init(int*,int[10][4]);
int getMark(char);
int selectionSort(char*,int*,int,int[10][4]);
int bubbleSort(char*,int*,int,int[10][4]);
void print(char*,int*,int,int);

int main(){
  int idx[10],data[10][4];
  int N,A[MAX_N],A2[MAX_N],i,isStable;
  char M[MAX_N],M2[MAX_N],ch;

  init(idx,data);

  scanf("%d%c",&N,&ch);
  for(i = 0 ; i < N ; i++){
    scanf("%c%d%c",&M[i],&A[i],&ch);
    M2[i] = M[i];
    A2[i] = A[i];
    data[A[i]][idx[A[i]]++] = getMark(M[i]);
  }
  isStable = bubbleSort(M,A,N,data);
  print(M,A,N,isStable);
  isStable = selectionSort(M2,A2,N,data);
  print(M2,A2,N,isStable);
  return 0;
}

void init(int *idx,int data[10][4]){
  int i,j;
  for(i = 0 ; i < 10 ; i++){
    idx[i] = 0;
    for(j = 0 ; j < 4 ; j++){
      data[i][j] = -1;
    }
  }
}

int getMark(char M){
  if(M == 'H'){ return 0; }
  if(M == 'C'){ return 1; }
  if(M == 'S'){ return 2; }
  if(M == 'D'){ return 3; }
  return -1;
}

int selectionSort(char *M,int *A,int N,int data[10][4]){
  int i,j,temp,min,idx,cur[10],isStable = 1;
  char temp2;
  memset(cur,0,sizeof(cur));
  for(i = 0 ; i < N ; i++){
    min = A[i]; idx = i;
    for(j = i+1 ; j < N ; j++){
      if(A[j] < min){
        min = A[j];
        idx = j;
      }
    }
    if(A[idx] < A[i]){
      temp = A[i];
      A[i] = A[idx];
      A[idx] = temp;
      temp2 = M[i];
      M[i] = M[idx];
      M[idx] = temp2;
    }
  }
  for(i = 0 ; i < N ; i++){
    if(data[A[i]][cur[A[i]]] != getMark(M[i])){
      isStable = 0;
      break;
    }
    ++cur[A[i]];
  }
  return isStable;
}

int bubbleSort(char *M,int *A,int N,int data[10][4]){
  int i,j,temp,cur[10],isStable = 1;
  char temp2;
  memset(cur,0,sizeof(cur));
  for(i = 0 ; i < N ; i++){
    for(j = N-1 ; j > i ; j--){
      if(A[j-1] > A[j]){
        temp = A[j];
        A[j] = A[j-1];
        A[j-1] = temp;
        temp2 = M[j];
        M[j] = M[j-1];
        M[j-1] = temp2;
      }
    }
  }
  for(i = 0 ; i < N ; i++){
    if(data[A[i]][cur[A[i]]] != getMark(M[i])){
      isStable = 0;
      break;
    }
    ++cur[A[i]];
  }
  return isStable;
}

void print(char *M,int *A,int N,int isStable){
  int i;
  for(i = 0 ; i < N ; i++){
    printf("%c%d%c",M[i],A[i],(i < N-1 ? ' ' : '\n'));
  }
  if(isStable == 1){
    printf("Stable\n");
  }else{
    printf("Not stable\n");
  }
}

Measured memory_bytes: 1040
N=int(input())
P=[int(x) for x in input().split()]
Q=[int(x) for x in input().split()]

def fact(n):
    s2=1
    while(n!=0):
        s2=s2*n
        n=n-1
    return(s2)

def count(A):
    s=0
    for i in range(0,N):
        B=sorted(A)
        key=[j for j,e in enumerate(B) if e==A[0]]
        flag=key[0]
        del(A[0])
        del(B[flag])
        s+=flag*(fact(N-1-i))
    return s

p=count(P)
q=count(Q)

if(p>q):
    print(p-q)
else:
    print(q-p)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] AN = new int[N];
        int[] AN2 = new int[N];
        int changeCount = 0;
        int min = 2147483647;
        long S = 0;

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

            AN[i] = sc.nextInt();

            if(AN[i] < 0) {

                AN2[i] = -AN[i];
                changeCount++;
            } else {

                AN2[i] = AN[i];
            }

            min = (AN2[i] < min) ? AN2[i] : min;
        }

        if (changeCount % 2 == 0) {

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

                S += AN2[i];
            }
            System.out.println(S);
        } else {

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

                S += AN2[i];
            }
            System.out.println(S-min*2);
        }
        sc.close();
    }

}


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

using namespace std;

map <int, int> mp;

int main()
{
	cin.sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) 
	{
		int x; cin >> x;
		mp[x]++;
	}
	int ans = 0;
	for (auto u : mp)
	{
		int p = u.first;
		int cnt = 0;
		if (mp.count(p)) cnt += mp[p];
		if (mp.count(p - 1)) cnt += mp[p - 1];
		if (mp.count(p + 1)) cnt += mp[p + 1];
		
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int m=1e9+7;
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    fastio
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(b/a,c);
	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, s, e) for(ll i=s; i>=e; i--)
#define reps(i, s, e) for(ll i=s; i<=e; i++)
#define inf 1e18
#define all(v) v.begin(),v.end()
#define vsort(v) sort(v.begin(), v.end())
#define vsortr(v) sort(v.begin(), v.end(), greater<ll>())
#define sz(x) x.size()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
using namespace std;
template<typename T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){ a=b; return true; } return false; }
template<typename T> T gcd(T a, T b){ if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b){ return a*(b/gcd(a, b)); }
template<typename T> T keta(T num){ T k=0; while(num>0){ num/=10; k++; } return k; }
template<typename T> void vdebug(vector<T> v){ for(auto vv : v){ cout << vv << " "; } cout << endl; }
template<typename T> void adebug(T arr[], ll n){ reps(i, 0, n){ cout << arr[i] << " "; } cout << endl; }
void ans(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; }
void ans2(bool b){ if(b) cout << "YES" << endl; else cout << "NO" << endl; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};


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

    ll n, tmpa, k;
    vector<ll> a;

    cin >> n >> k;
    rep(i, n){
        cin >> tmpa;
        a.push_back(tmpa);
    }

    vsort(a);

    ll g = a[0];
    reps(i, 1, n-2){
        g = gcd(g, a[i]);
    }

    bool res;
    if(a[n-1] < k) res = false;
    else{
        ll cnt = 0;
        rep(i, n){
            if(a[i]%g == 0) cnt++;
        }
        if(cnt == n && k%g != 0) res = false;
        else res = true;
    }

    auto answer = [](bool res){
        if(res) cout << "POSSIBLE" << endl;
        else cout << "IMPOSSIBLE" << endl;
    };

    answer(res);

    return 0;
}


Measured memory_bytes: 1400
// AOJ 1316: The Sorcerer's Donut
// 2017.12.4 bal4u@uu

#include <stdio.h>
#include <string.h>

#define HASHSIZ 500009
typedef struct { unsigned x; int w; } HASH;
HASH hash[HASHSIZ+2], *hashend = hash+HASHSIZ;			// Hash table
char ans[500]; int len;
char buf[1000];

void lookup(unsigned x, int w)
{
	int i = (int)(x % HASHSIZ);
	HASH *tp = hash + i;

	while (tp->x) {
		if (w == tp->w && x == tp->x) {
			if (w > len || (w == len && memcmp(buf, ans, w) < 0))
				memcpy(ans, buf, w), len = w;
			return;
		}
		if (++tp == hashend) tp = hash;
	}
	tp->x = x, tp->w = w;
}

#define M 4294967291
int h, w, sr, sc, dir;
char m[10][22];
int mv[8][2] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};


void rec(int r, int c, unsigned x, int len)
{
	int r2, c2;

	buf[len++] = m[r][c];
	x = (((long long)x << 5) | (m[r][c]-0x40)) % M;
	lookup(x, len);

	r2 = r + mv[dir][0]; if (r2 < 0) r2 = h-1; else if (r2 >= h) r2 = 0;
	c2 = c + mv[dir][1]; if (c2 < 0) c2 = w-1; else if (c2 >= w) c2 = 0;

	if (r2 == sr && c2 == sc) return;
	rec(r2, c2, x, len);
}

int main()
{
	int r;

	while (scanf("%d%d", &h, &w) && h > 0) {
		memset(hash, 0, sizeof(hash));
		for (r = 0; r < h; r++) scanf("%s", m[r]);

		len = 0;
		for (sr = 0; sr < h; sr++) for (sc = 0; sc < w; sc++) for (dir = 0; dir < 8; dir++) {
			rec(sr, sc, 0, 0);
		}

		if (len < 2) puts("0");
		else ans[len] = 0, puts(ans);
	}
	return 0;
}

Measured memory_bytes: 5608
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <deque>
#include <math.h>
#include <map>
#include <bitset>
#include <queue>
#include <list>
#include <utility>

//#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using p = pair<int, int>;
using Graph = vector<vector<char>>;
#define rep(i,n)  for(int i = 0; i < n ; i++)
int dx[4]{ -1,0,1,0 };
int dy[4]{ 0,1,0,-1 };

ll chose2(ll	 n)
{
	return (n * (n - 1)) / 2;
}

int main()
{
	int N;
	cin >> N;
	vector<int> A(N);
	rep(i,N)cin >> A[i];

	rep(i, N)A[i]--;
	vector<int>	cnt(N);
	rep(i, N)cnt[A[i]]++;
	ll tot = 0;
	rep(i, N) {
		tot += chose2(cnt[i]); // 同じ番号の個数から2つ選ぶ　組み合わせ
	}
	rep(i, N) {
		ll ans = tot;
		ans -= chose2(cnt[A[i]]);
		ans += chose2(cnt[A[i]]-1); // -1個した時から2個選ぶ組み合わせ
		cout << ans << endl;
	}
}


Measured memory_bytes: 4096
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int N = sc.nextInt();
        final int Y = sc.nextInt();

        for (int a = 0; a <= N; a++) {
            for (int b = 0; a+b <= N; b++) {
                int c = N - a - b;
                if (Y == 10000 * a + 5000 * b + 1000 * c) {
                    System.out.println(a + " " + b + " " + c);
                    return;
                }
            }
        }
        System.out.println("-1 -1 -1");
    }
}


Measured memory_bytes: 23764
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i);
      if (Character.isLowerCase(ch)) {
        sb.append(Character.toUpperCase(ch));
      } else {
        sb.append(Character.toLowerCase(ch));
      }
    }
    System.out.println(sb.toString());
  }
}



Measured memory_bytes: 26176
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;

int main() {
  int N, M, X; cin >> N >> M >> X;
  vi A(M); rep(i,M) cin >> A.at(i);
  
  int sumL = 0, sumR = 0;
  rep(i,M) {
    if (0<A.at(i) && A.at(i)<X) {
      sumL++;
    }
    else
      sumR++;
  }
  
  cout << min(sumL,sumR) << endl;
}

Measured memory_bytes: 256
inp = list(map(int,input().split(" ")))
i = min(inp[0],inp[1])
k_=0
k_list = list()
for k in range(1,i+1):
    if inp[0]%k ==0:
        if inp[1]%k==0:
            k_+=1
            k_list.append(k)
print(k_list[-inp[2]])

Measured memory_bytes: 3060
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char gc() {
	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void rd(T &x) {
	x=0; int f=1,ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=gc();}
	x*=f;
}
const int maxK=100+5,maxn=1000+5;
int n,K,a[maxK],an[maxn];
bool vis[maxK];
inline bool cmp(const vector<int> &a,const vector<int> &b) {
	for(int i=0;i<a.size()&&i<b.size();++i) if(a[i]!=b[i]) return a[i]<b[i];
	return a.size()<b.size();
}
void fail(vector<int> &re) {
	for(int i=0;i<=K;++i) re.push_back(K+1);
}
void sol(int s,int m,vector<int> &re) {
	static int b[maxK]; memcpy(b,a,sizeof(b));
	memset(vis,0,sizeof(vis));
	for(int i=1;i+m<=K;++i) vis[an[s-i]]=1;
	for(int i=1;i<=K;++i) if(!vis[i]) {
		if(!b[i]) {fail(re); return;}
		--b[i];
	}
	int x=*max_element(b+1,b+K+1),y=*min_element(b+1,b+K+1);
	if(x>2*y+1) {fail(re); return;}
	vector<int> A,B,C;
	if(x==2*y+1) {
		bool flag=0;
		for(int i=1;i+m<=K;++i) {
			if(b[an[s-i]]==x) flag=1;
			else if(b[an[s-i]]==y) {
				if(flag) {fail(re); return;}
			}
		}
		for(int i=K;i>=1;--i) if(!vis[i]) {
			if(b[i]==x) A.push_back(i);
			else if(b[i]==y) B.push_back(i);
			else C.push_back(i);
		}
	}
	else for(int i=K;i>=1;--i) if(!vis[i]) C.push_back(i);
	for(int i=1;i<=m;++i) {
		if(A.size()) {
			int t=C.size()?C.back():K+1;
			if(A.back()<t) re.push_back(A.back()),A.pop_back();
			else re.push_back(t),C.pop_back();
		}
		else {
			int a=B.size()?B.back():K+1,b=C.size()?C.back():K+1;
			if(a<b) re.push_back(a),B.pop_back();
			else re.push_back(b),C.pop_back();
		}
	}
}
int main() {
	rd(K);
	for(int i=1;i<=K;++i) rd(a[i]),n+=a[i];
	if(*max_element(a+1,a+K+1)>2*(*min_element(a+1,a+K+1))) {puts("-1"); return 0;}
	for(int i=1;i<=n;) {
//		debug("---\n");
		vector<int> Q[maxK];
		if(i==1) sol(i,K,Q[1]);
		else {
			for(int j=1;j<=K;++j) sol(i,j,Q[j]);
			int k=1;
			for(int j=2;j<=K;++j) if(cmp(Q[j],Q[k])) k=j;
			if(k!=1) swap(Q[1],Q[k]);
		}
		for(int j=0;j<Q[1].size();++j) an[i+j]=Q[1][j],--a[Q[1][j]];
		i+=Q[1].size();
//		for(int j=1;j<i;++j) debug("%d ",an[j]); debug("\n");
	}
	for(int i=1;i<=n;++i) {
		if(i!=1) printf(" ");
		printf("%d",an[i]);
	}
	printf("\n");
	return 0;
}

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

using namespace std;


int n,m,cnt;
long long a[1000005];

int main (){
	cin >> n;
	a[0] = 2;
	a[1] = 1;
	for (int i = 2; i <= n; i++){
		a[i] = a[i - 1] + a[i - 2];
	}
	cout << a[n];
	return 0;
}

Measured memory_bytes: 256
import heapq
N, M = map(int, input().split())
jobs = [[] for _ in range(M)]
for _ in range(N):
    a,b = map(int, input().split())
    if a > M: continue
    jobs[M-a].append(b)

q = []
ans = 0
for i in range(M - 1, -1, -1):
    for b in jobs[i]:
        heapq.heappush(q, -b)
    if q:
        ans += heapq.heappop(q) * (-1)
print(ans)


Measured memory_bytes: 18592
// C++ program to compute LCM of array elements modulo M 
#include <bits/stdc++.h> 
#define F first 
#define S second 
#define MAX 10000003 
#define MOD mod
using namespace std; 

typedef long long ll; 
const int mod = 1000000007; 

int prime[MAX]; 
unordered_map<int, int> max_map; 

// Function to return a^n 
int power(int a, int n) 
{ 
   if (n == 0) 
      return 1; 
   int p = power(a, n / 2) % mod; 
   p = (p * p) % mod; 
   if (n & 1) 
      p = (p * a) % mod; 
   return p; 
} 

ll power1(ll x, ll y){
   ll ans=1;
   if(y==1) return x%MOD;
   x=x % MOD,y=y % (MOD-1);
   while(y){
      if(y & 1) ans = (ans*x) %MOD;
      x *= x;
      x = x % MOD;
      y >>= 1;
   }
   return ans;
}
 
ll inv(ll x){
   return power1(x,MOD-2);
}


// Function to find the smallest prime factors 
// of numbers upto MAX 
void sieve() 
{ 
   prime[0] = prime[1] = 1; 
   for (int i = 2; i < MAX; i++) { 
      if (prime[i] == 0) { 
         for (int j = i * 2; j < MAX; j += i) { 
            if (prime[j] == 0) { 
               prime[j] = i; 
            } 
         } 
         prime[i] = i; 
      } 
   } 
} 

// Function to return the LCM modulo M 
ll lcmModuloM(const int* ar, int n) 
{ 

   for (int i = 0; i < n; i++) { 
      int num = ar[i]; 
      unordered_map<int, int> temp; 

      // Temp stores mapping of prime factor to 
      // its power for the current element 
      while (num > 1) { 

         // Factor is the smallest prime factor of num 
         int factor = prime[num]; 

         // Increase count of factor in temp 
         temp[factor]++; 

         // Reduce num by its prime factor 
         num /= factor; 
      } 

      for (auto it : temp) { 

         // Store the highest power of every prime 
         // found till now in a new map max_map 
         max_map[it.first] = max(max_map[it.first], it.second); 
      } 
   } 

   ll ans = 1; 

   for (auto it : max_map) { 

      // LCM is product of primes to their highest powers modulo M 
      ans = (ans * power(it.F, it.S)) % mod; 
   } 

   return ans; 
} 

// Driver code 
int main() 
{ 
   sieve(); 
   int n;
   cin >> n;
   int arr[n];
   for(int i=0;i<n;i++){
      cin >> arr[i];
   }
   ll lc = lcmModuloM(arr,n);
   // cout << lc << '\n';
   ll ans = 0;
   for(int i = 0;i<n;i++){
      ans += ((lc*inv(arr[i]))%mod);
      // cout << ans << '\n';
      ans %= mod;
   }
   cout << ans << '\n';
   return 0; 
} 

Measured memory_bytes: 39808
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

char ans_c(int c){
	if (c < 10)
		return '0'+c;
	return 'A' + c - 10;
}

int main() {
	int N, M, Q;
	while (cin >> N >> M >> Q, N){
		string switch_s;
		string light_s;
		string blight_s;
		vector<vector<bool>> vvb(M,vector<bool>(N,true));
		REP(i, M)
			blight_s.append(i,'0');

		REP(i, Q){
			cin >> switch_s;
			cin >> light_s;
			//-----------//
			REP(j, N){
				REP(k, M){
					if ((switch_s[j]=='0') != (light_s[k] == blight_s[k])){
						vvb[k][j]=false;
					}
				}
			}
			//-----------//
			blight_s = light_s;
		}

		REP(i,M){
			int count = 0;
			int ans = 0;
			REP(j, N){
				if (vvb[i][j]){
					count++;
					ans = j;
				}
			}
			if (count == 1)cout << ans_c(ans);
			else cout << '?';
		}
		cout << endl;
	}
}

Measured memory_bytes: 2196
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<62;
const double eps=1e-5;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct UnionFind{
	vector<ll> par,siz,s;
	UnionFind(int n){
		s.resize(n,0);
		par.resize(n);
		siz.resize(n,1);
		for(int i=0;i<n;i++)par[i]=i;
	}
	int find(int x){
		return (par[x]==x?x:find(par[x]));
	}
	void unite(int u,int v,ll c){
		u=find(u);v=find(v);
		if(u==v)return;
		if(siz[u]<siz[v])swap(u,v);
		par[v]=u;
		s[u]+=siz[v]*c;
		s[v]+=siz[u]*c;
		s[v]-=s[u];
		siz[u]+=siz[v];
	}
	ll ans(int x){
		return (par[x]==x?s[x]:ans(par[x])+s[x]);
	}
};
int main(){
	int n;cin>>n;
	vector<pair<ll,P>> v;
	for(int i=0;i<n-1;i++){
		int a,b,c;cin>>a>>b>>c;--a;--b;
		v.push_back(mp(c,mp(b,a)));
	}
	sort(all(v));
	reverse(all(v));
	UnionFind uf(n);
	for(int i=0;i<n-1;i++){
		ll c=v[i].first;int a=v[i].second.first,b=v[i].second.second;
		uf.unite(a,b,c);
	}
	for(int i=0;i<n;i++){
		cout<<uf.ans(i)<<endl;
	}
}


Measured memory_bytes: 7024
#include <set>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
	int n,x;
	set<int>s,t,r;
	for(scanf("%d",&n);n--;s.insert(x))scanf("%d",&x);
	for(scanf("%d",&n);n--;t.insert(x))scanf("%d",&x);
	set_intersection(s.begin(),s.end(),t.begin(),t.end(),inserter(r,r.end()));
	printf("%d\n",r.size());
}

Measured memory_bytes: 7428
#include<bits/stdc++.h>
#define int long long int
using namespace std;

#undef int
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
#define int long long int
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--) {
		int n;
		cin >> n;
		int arr[n];
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		sort(arr, arr + n);
		int ans = arr[n - 1];
		int cnt = n - 2;
		for (int i = n - 2; i >= 0; i--) {
			if (cnt == 0) break;
			ans += arr[i];
			cnt--;
			if (cnt == 0) break;
			ans += arr[i];
			cnt--;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 5204
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define vi vector<int>
#define vvll vector<ll>
#define vll(a) vector<ll> a(MAXN)
#define pb push_back
#define fo(a) for(auto&a1:(a))
#define fd(a,b) for(int i=(a);i>=(b);i--)
#define fk(a,b) for(int k=(a);k<(b);k++)
#define fj(a,b) for(int j=(a);j<(b);j++)
#define f(a,b) for(ll i=(a);i<(b);i++)
#define forni(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define fdk(a,b) for(int k=(a);k>=(b);k--)
#define fdj(a,b) for(int j=(a);j>=(b);j--)
#define ri(n) scanf("%d",&(n));
#define rll(n) scanf("%lld",&(n));
#define T(t) int t;scanf("%d",&(t));while((t)--)
#define MAXN 1005
#define MAXN2 10000005
#define pll pair<ll,ll>
#define PI 3.14159265
#define mset(a) memset((a),0,sizeof((a)))
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll mod=1000000007;
vector<ll> tr[MAXN];
ll vis[MAXN][MAXN];
ll h,w;
ll dp[MAXN][MAXN];
ll cvis[MAXN][MAXN];
ll dfs(ll i,ll j)
{
    if(i==h-1 && j==w-1)
    return 1;
    if(!cvis[i][j] || i>=h || j>=w)
    return 0;
    if(vis[i][j])
    return dp[i][j];
    vis[i][j]=1;
    return dp[i][j]=(dfs(i+1,j)+dfs(i,j+1))%mod;
}
int main()
{
    cin>>h>>w;
    f(0,h)
    fj(0,w)
    {
        char ch;
        cin>>ch;
        cvis[i][j]=((ch=='.')?1:0);
    }
    if(!cvis[h-1][w-1])
    cout<<0<<"\n";
    else
    cout<<dfs(0,0)<<"\n";
    return 0;
}


Measured memory_bytes: 27112
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args){
		BufferedReader insBR = new BufferedReader(new InputStreamReader(System.in));
		while(true){
			try{
				String[] strA = insBR.readLine().split(" ");
				int[] intA = new int[strA.length];
				int i = 0;
				for(i = 0;i < strA.length ;i++){
					intA[i] = Integer.parseInt(strA[i]);
				}
				int intDiv = 0;
				if(intA[0] == 0 && intA[1] == 0){
					break;
				}else{
					for(i = 0;i < intA[0];i++){
						intDiv = i % 2;
						if(intDiv == 0){
							for(int j = 0; j < intA[1];j++){
								intDiv = j % 2;
								if(intDiv == 0){
									System.out.print("#");
								}else{
									System.out.print(".");
								}

							}
						}else{
							for(int j = 0; j < intA[1];j++){
								intDiv = j % 2;
								if(intDiv == 1){
									System.out.print("#");
								}else{
									System.out.print(".");
								}

							}
						}

						System.out.println();
					}
					System.out.println();
				}
			}catch(IOException e){
				e.printStackTrace();
			}catch(NumberFormatException e){
				e.printStackTrace();
			}
		}
	}

}



Measured memory_bytes: 35924
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class Task
    {
        static long mod = 1_000_000_000 + 7;

        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            long n = in.nextInt();
            long a = in.nextInt();
            long b = in.nextInt();

            long ans = power(2, n, mod) - 1;
            ans -= C(n, a, mod) % mod;
            ans -= C(n, b, mod) % mod;

            while (ans < 0)
            {
                ans += mod;
            }

            out.print(ans);
        }

        static long power(long a, long n, long m)
        {
            long ret = 1;
            for (; n > 0; n >>= 1, a = a * a % m)
            {
                if (n % 2 == 1)
                {
                    ret = ret * a % m;
                }
            }
            return ret;
        }

        static long C(long N, long K, long mod)
        {
            long x = 1, y = 1;
            for (int i = 1; i <= K; i++)
            {
                x = x * (N - i + 1) % mod;
                y = y * i % mod;
            }
            return x * power(y, mod - 2, mod) % mod;
        }

    }
}



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

const long long int mod=1e9+7;


long long int dfs(int K,const vector<vector<int>>&graph, int now,int from) {

 int can_use_color_num;
 if (from==-1) {
 can_use_color_num=K-1;
 }
 else {
 can_use_color_num=K-2;
 }
 if (K<graph[now].size()) {
 return 0;
 }
 else {
 long long int case_num=1;
 for (auto e : graph[now]) {
 if(e==from)continue;

 case_num*=can_use_color_num;
 can_use_color_num--;
 case_num%=mod;
 }
 for (auto e : graph[now]) {
 if(e==from)continue;


 case_num *=dfs(K,graph,e,now);
 case_num %= mod;
 }
 return case_num;
 }
 }



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

 vector<vector<int>>graph(N);
 for (int i = 0; i < N - 1; ++i) {
 int a,b;cin>>a>>b;a--;b--;

 graph[a].push_back(b);
 graph[b].push_back(a);
 }

 long long int answer=K*dfs(K,graph,0,-1);
 answer%=mod;
 cout<<answer<<endl;
 return 0;
 }

Measured memory_bytes: 11520
#include<bits/stdc++.h>
using namespace std;
int main(){
	 char a;
	 cin>>a;
	 if(a=='A'){
		 cout<<'T'<<endl;
	 }
	 else if(a=='T'){
		 cout<<'A'<<endl;
	 }
	 else if(a=='C'){
		 cout<<'G'<<endl;
	 }
	 else if(a=='G'){
		 cout<<'C'<<endl;
	 }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline void read(int &x){
    char c=getchar();
    int p=1;
    x=0;
    while(!isdigit(c)){
        if(c=='-')p=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x*=p;
}
inline int Get(int a,int b){
    return b>=a?b+1:b;
}
int a,b,q;
inline bool check(int num){
    int d=num/2;
    for(register int i=d-200;i<=d+200;++i){
        if(i<=0&&i>num)continue;
        if(Get(a,i)*Get(b,num-i+1)>=a*b)return 0;
    }
    return 1;
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(q);
    while(q--){
        read(a);read(b);
        int L=0,R=2147483640;
        int ans=0;
        while(L<R){
            int mid=(L+R+1)>>1;
            if(check(mid))L=mid;
            else R=mid-1;
        }
        printf("%lld\n",L);
    }
    return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)
template<class T, class U> void umin(T& x, const U& y){ x = min(x, (T)y);}
template<class T, class U> void umax(T& x, const U& y){ x = max(x, (T)y);}
template<class T, class U> void init(vector<T> &v, U x, size_t n) { v=vector<T>(n, x); }
template<class T, class U> void init(vector<T> &v, U x, size_t n, size_t m...) { v=vector<T>(n); for(auto& a : v) init(a, x, m);}

class Fenwick{
    vector<ll> F;
public:
    Fenwick(int n){
        F.clear();
        F.resize(n+1);
    }
    int inline lsb(int pos){
        return pos & -pos;
    }
    void add(int x, int pos){
        pos++;
        while(pos<F.size()){
            F[pos] += x;
            pos += lsb(pos);
        }
    }
    ll get(int pos){
        pos++;
        ll res = 0;
        while(pos){
            res += F[pos];
            pos -= lsb(pos);
        }
        return res;
    }
};

int m;
struct ttt{
    int l, r, i;
    bool operator < (const ttt& o){
        return l < o.l;
    }
};

//#define TEST 1
int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);

    int n, q;
    cin >> n >> q;

    vector<int> c(n+1);
#if TEST
    FOR(i, n) c[i] = rand() % 100;
#else
    FOR1(i, n) cin >> c[i];
#endif

    vector<ttt> v;
    FOR(i, q){
        int l, r;
#if TEST
        l = 1 + rand() % n;
        r = l + rand() % n;
        if (r < l) swap(l, r);
#else
        cin >> l >> r;
#endif
        v.push_back({l, r, i});
    }
    sort(v.begin(), v.end());

    int pos = q-1;
    vector<int> sol(q);
    vector<int> next(n+1, n+1);
    Fenwick F(n+1);
    for(int l=n; l > 0; l--){
        F.add(-1, next[c[l]]);
        F.add(1, l);
        next[c[l]] = l;
        while(pos >= 0 && v[pos].l == l){
            sol[v[pos].i] = F.get(v[pos].r);
            pos--;
        }
    }
    FOR(i, q)
        cout << sol[i] << '\n';
    cout << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 19424
#include <stdio.h>

double dp[3000][3000];
long long n;
double arr[3000];

double solve(long long index,long long target)
{
    if(index>=n)
    {
        if(target==0) return 1.0;
        else return 0.0;
    }
    else if(dp[index][target]!=-1) return dp[index][target];
    else return dp[index][target]=solve(index+1,target-1)*arr[index]+solve(index+1,target)*(1-arr[index]);
}

int main()
{
    for(int i=0;i<3000;i++)
        for (int j = 0; j < 3000; j++)
                dp[i][j]=-1;
    scanf("%lld",&n);
    double ans=0.0;
    for(int i=0;i<n;i++) 
        scanf("%lf",&arr[i]);
    for(long long i=n/2+1;i<=n;i++)
       ans+=solve(0,i);
    printf("%.10lf\n",ans);
    return 0;
}

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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define ALL(c) (c).begin(), (c).end()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;

int main() {
    ll h, w;
    cin >> h >> w;

    if (h % 3 == 0 || w % 3 == 0) {
        cout << 0 << endl;
        return 0;
    }

    ll mn = 10000100001;

    REP1(i, h - 1) {
        ll s1 = i * w;
        if (w % 2 == 0) {
            ll s2 = (h - i) * w / 2;
            chmin(mn, abs(s1 - s2));
        } else {
            ll s2 = (h - i) * (w / 2);
            ll s3 = (h - i) * (w / 2 + 1);
            chmin(mn, max({s1, s2, s3}) - min({s1, s2, s3}));
        }
    }
    REP1(i, w - 1) {
        ll s1 = i * h;
        if (h % 2 == 0) {
            ll s2 = (w - i) * h / 2;
            chmin(mn, abs(s1 - s2));
        } else {
            ll s2 = (w - i) * (h / 2);
            ll s3 = (w - i) * (h / 2 + 1);
            chmin(mn, max({s1, s2, s3}) - min({s1, s2, s3}));
        }
    }

    cout << min({mn, h, w}) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, k) for (int i = (s); i < (int)(k); i++)

int main(){
    int a,b;
    cin >> a >> b;
    double cnt = 0.0;
    int y = b;
    while(y>0){
        cnt+=1.0;
        y/=10;
    }
    double x = pow(10.0,cnt)*(double)a + (double)b;
    cout << (((int)(sqrt(x)*10.0)%10==0) ? "Yes" : "No" )<< endl;
}

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

typedef long long ll;
#define int ll
#define pb push_back
const int INF = 1e18;

signed main(){

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

	string s,t; cin>>s>>t;

	
	vector<string> dp((int)t.size() + 1, ""),next((int) t.size()+1);

	for(int i=0;i<s.size();i++){
		string blah = "";
		for(int j=1;j<t.size()+1;j++){
			if ((int) (t[j-1] - 'a') == (int) (s[i] - 'a')) 
				next[j] = blah+s[i];
			if (dp[j].size() > blah.size())
				blah = dp[j];
		}
		for(int j =1;j<t.size()+1;j++)
			dp[j] = next[j];
	}

	string ans = "";
	for(int i=1;i<=t.size();i++)
		if (dp[i].size() > ans.size())
			ans = dp[i];

	cout<<ans;
	return 0;
}

Measured memory_bytes: 16872
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int n,m;
	cin>>n>>m;
	
	vvi v(n);
	REP(i,m){
		int a,b;
		cin>>a>>b;
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	vi ans(n);
	bool jud[n]={};
	queue<int> que;
	que.push(0);
	int cnt=0;
	while(!que.empty()){
		cnt++;
		int p=que.front();
		que.pop();
		
		REP(i,v[p].size()){
			if(jud[v[p][i]]){}
			else{
				ans[v[p][i]]=p;
				jud[v[p][i]]=true;
				que.push(v[p][i]);
			}
		}
	}
	
	if(cnt<n){
		cout<<"No"<<endl;
		return 0;
	}
	
	cout<<"Yes"<<endl;
	for(int i=1;i<n;++i) cout<<ans[i]+1<<endl;
}


Measured memory_bytes: 10368
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 2e5 + 10, INF = 1e9, MOD = 1e9 + 7;

#define int ll
vector<pair<ll, ll>> vec;

ll tree[SIZE * 8], p[SIZE * 8];

ll get(int v, int l, int r, int pos) {
	if (l == r - 1) {
		return (tree[v] + p[v]) % MOD;
	}
	else {
		int mid = (l + r) / 2;
		if (pos < mid) {
			return (get(v * 2 + 1, l, mid, pos) + p[v]) % MOD;
		}
		else {
			return (get(v * 2 + 2, mid, r, pos) + p[v]) % MOD;
		}
	}
}

void upd(int v, int l, int r, int askl, int askr, int val) {
	if (l >= askr || r <= askl) return;

	if (l >= askl && r <= askr) {
		p[v] += val;
		p[v] %= MOD;
		return;
	}

	ll mid = (l + r) / 2;
	upd(v * 2 + 1, l, mid, askl, askr, val);
	upd(v * 2 + 2, mid, r, askl, askr, val);
}

void debug(int n) {
	for (int i = 0; i < n; i++) {
		cout << get(0, 0, n, i) << " ";
	}
	cout << "\n";
}

signed main()
{
	fastInp;

	ll n, m;
	cin >> n >> m;

	set<ll> s;
	vector<ll> vec2(n), ex(m), vec;
	for (auto &cur : vec2) cin >> cur;

	map<ll, vector<ll>> mp;
	for (auto &cur : ex) {
		cin >> cur;
		s.insert(cur);
	}

	for (int i = 0; i < vec2.size(); i++) {
		if (!(vec2[i] <= ex[0] || vec2[i] >= ex.back())) {
			vec.push_back(vec2[i]);
		}
	}

	vector<ll> k;
	for (auto cur : vec) {
		ll nxt = (*upper_bound(ex.begin(), ex.end(), cur)), pr = *(--upper_bound(ex.begin(), ex.end(), cur));
		mp[cur - pr].push_back(nxt - cur);
		k.push_back(nxt - cur);
	}

	sort(k.begin(), k.end());
	auto it = unique(k.begin(), k.end());
	k.erase(it, k.end());
	map<ll, ll> ch;
	for (int i = 0; i < k.size(); i++) ch[k[i]] = i + 1;

	
	n = k.size() + 10;
	upd(0, 0, n, 0, n, 1);
	for (auto cur : mp) {
		vector<ll> c = cur.second;
		sort(c.begin(), c.end());
		auto it = unique(c.begin(), c.end());
		c.erase(it, c.end());
		reverse(c.begin(), c.end());

		for (auto t : c) {
			ll vl = get(0, 0, n, ch[t]);
			upd(0, 0, n, ch[t] + 1, n, vl);
		}
		//debug(n);
	}


	ll vl = get(0, 0, n, n - 1);
	
	cout << vl;

	return 0;
}

Measured memory_bytes: 24612
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

const int mod = 1e9+7;

int n;
int m;
int sz[N];
int parent[N];
long long ans[N];
pair < int , int > adj[N];

long long ss;

int getP(int u){
    if(parent[u] == u)
        return u;
    return parent[u] = getP(parent[u]);
}

void join(int u , int v){
    u = getP(u);
    v = getP(v);
    if(u == v)
        return;
    parent[v] = u;
    ss -= sz[u] * sz[v] * 1ll;
    sz[u] += sz[v];
}

int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= n; i++){
        sz[i] = 1;
        parent[i] = i;
    }
    for(int i = 1; i <= m; i++){
        int u , v;
        scanf("%d%d" , &u , &v);
        adj[i] = {u , v};
    }
    ss = 1ll * n * (n - 1ll) / 2;
    for(int i = m; i >= 1; i--){
        ans[i] = ss;
        join(adj[i].first , adj[i].second);
    }
    for(int i = 1; i <= m; i++){
        printf("%lld\n" , ans[i]);
    }
}

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

int main(){
  string S;cin>>S;reverse(S.begin(),S.end());
  string T;cin>>T;reverse(T.begin(),T.end());
    if(S.size() < T.size()){
    cout << "UNRESTORABLE" << endl;
    return 0;
  }

  for (int s = 0; s <= S.size()-T.size(); s++) {
    string sbs = S.substr(s,T.size()+s);
    bool flg=true;
    for (int t = 0; t < T.size(); t++){
      if (!(sbs[t]==T[t]||sbs[t]=='?')){
        flg=false;
        break;
      }
    }
    if (flg){
      string ans=S.substr(0,s)+T+S.substr(T.size()+s,S.size());
      replace(ans.begin(),ans.end(),'?','a');
      reverse(ans.begin(),ans.end());
      cout<< ans  << "\n";return 0;
    }
  }


  cout<<  "UNRESTORABLE" << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    string s;
    cin >> s;
    ll ans = 0;
    rep(i, s.size()) {
        if (s[i] == '1') ans++;
    }

    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    string s[n];
    for(int i=0;i<n;i++)cin >> s[i];
    int c[4]={0};
    for(int i=0;i<n;i++){
        if(s[i]=="AC")c[0]++;
        else if(s[i]=="WA")c[1]++;
        else if(s[i]=="TLE")c[2]++;
        else if(s[i]=="RE")c[3]++;
    }
    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d",c[0],c[1],c[2],c[3]);
    return 0;
}

Measured memory_bytes: 6908
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int n,a[100010];
typedef long long ll;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  ll sum=0;
  for(int i=1;i<=n;i++) sum+=a[i];
  for(int i=2;i<=n;i+=2) sum-=a[i]*2;
  int x=sum;
  for(int i=1;i<n;i++)
  {
    printf("%d ",x);
    x=a[i]*2-x;
  }
  cout<<x;
  return 0;
}

Measured memory_bytes: 1664