akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double x1, x2, x3, y1 ,y2 ,y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    double a, b, c;
    a = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
    b = sqrt((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2));
    c = sqrt((x3-x1)*(x3-x1) + (y3-y1)*(y3-y1));

    double s = (a + b + c) / 2.0;
    double S = sqrt(s * (s-a) * (s-b) * (s-c));
    double r = (2.0 * S) / (a + b + c);
    double ma = max({a,b,c});

    printf("%.12lf\n",ma /(2.0 + ma / r));
}

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

int R,G,B,n;
int main(){
    cin>>R>>G>>B>>n;
    int ans = 0;
    for (int i=0;i<=n;i++){
        for (int j=0;j<=n;j++){
            int now = R * i + G * j;
            if (now > n) continue;
            now = n - now;
            if (now % B == 0) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("atcoder-problems/abc058_b.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v) \
rep(l, v.size()) { cout << v[l] << " "; } \
cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18+100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  string O, E;
  cin >> O >> E;

  int i = 0, j = 0;
  while (true) {
    int befi = i;
    int befj = j;
    if (O.size() > i) cout << O[i++];
    if (E.size() > j) cout << E[j++];
    if (befi == i && befj == j) return 0;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 305
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;

int num[100005];
vector<int> p;

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&num[i]);
	}
	sort(num,num+n);
	for(int i=n-1;i>0;i--)
	{
		if(num[i]==num[i-1])
			p.push_back(num[i]);
	}
	if(p.size()>1&&p[0]!=p[1])
		printf("%lld\n",(LL)p[0]*(LL)p[1]);
	else if(p.size()>2&&p[0]==p[1]&&p[0]!=p[2])
		printf("%lld\n",(LL)p[0]*(LL)p[2]);
	else if(p.size()>2&&p[0]==p[2])
		printf("%lld\n",(LL)p[0]*(LL)p[0]);
	else
		printf("0\n");
}

Measured memory_bytes: 1276
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e5+7;
int n,a[maxn],log[maxn],f[2][18][maxn],pos[maxn];

int rmq(int k,int l,int r){
    
    int j = log[r-l+1];
    return min(f[k][j][l],f[k][j][r-(1<<j)+1]);
}
pair<int,int> cal(int l,int r){
    int x = rmq(l&1,l,r);
    int y = rmq((pos[x]+1)&1,pos[x]+1,r);
    
    return {-x,-y};
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        pos[a[i]]=i;
    }
    for(int i=2;i<=n;i++){
        log[i]=log[i>>1]+1;
    }
    for(int l=0;l<2;l++){
        for(int i=0;i<n;i++){
            f[l][0][i]=(i%2==l)?a[i]:1<<30;
        }
        for(int k=1;1<<k<=n;k++){
            for(int j=0;j+(1<<k)-1<n;j++){
                f[l][k][j]=min(f[l][k-1][j],f[l][k-1][j+(1 << k - 1)]);
            }
        }
    }
    priority_queue< pair<pair<int,int> ,pair<int,int> > > Q;
    Q.push({cal(0,n-1),{0,n-1}});
    while(!Q.empty()){
        auto it = Q.top();Q.pop();
        int x = -it.first.first;
        int y = -it.first.second;
        printf("%d %d ",x,y);
        int l = it.second.first;
        int r = it.second.second;
        x = pos[x],y = pos[y];
        if(l<x-1){
            Q.push({cal(l,x-1),{l,x-1}});
        }
        if(x+1<y-1){
            Q.push({cal(x+1,y-1),{x+1,y-1}});
        }
        if(y+1<r){
            Q.push({cal(y+1,r),{y+1,r}});
        }
    }
    
}

Measured memory_bytes: 32504
import java.util.Arrays;
import java.util.Collections;
import java.util.*;
class Main
{
	public static void main (String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int i;
		int n=sc.nextInt(); int k=sc.nextInt();
		int a[]=new int[n];
		for(i=0;i<n;i++)
			a[i]=sc.nextInt();
		Arrays.sort(a);
		int dp[]=new int[k+1];
		dp[0]=0;
		for(i=0;i<=k;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i>=a[j]&&dp[i-a[j]]==0)
					dp[i]=1;
			}
		}
		if(dp[k]==1)
			System.out.println("First");
		else
			System.out.println("Second");
		
		
	}
}

Measured memory_bytes: 36936
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        sc.close();
        int sum = 0;
        sum+=Math.min(k,a);
        k-=a;
        if(k>0){
            k-=b;
        }
        if(k>0){
            sum-=k;
        }
        System.out.println(sum);
    }
}

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

typedef long long LL;

const int N=100000;

int n;

void into(){
  scanf("%d",&n);
}

int ca,ans[N*2+9][2];

void Get_ans(){
  if ((n&-n)==n) return;
  for (int i=3;i<=n;i+=2){
	int x=i-1,y=i;
	ans[++ca][0]=x;ans[ca][1]=y;
	ans[++ca][0]=x+n;ans[ca][1]=y+n;
	ans[++ca][0]=1;ans[ca][1]=x;
	ans[++ca][0]=1;ans[ca][1]=y+n;
  }
  ans[++ca][0]=n+1;ans[ca][1]=3;
  if (n&1) return;
  int x=n&-n,y=n-x;
  ans[++ca][0]=n;ans[ca][1]=x;
  ans[++ca][0]=n<<1;ans[ca][1]=y+n+1;
}

void work(){
  Get_ans();
}

void outo(){
  if ((n&-n)==n) puts("No");
  else{
	puts("Yes");
    for (int i=1;i<n<<1;++i)
	  printf("%d %d\n",ans[i][0],ans[i][1]);
  }
}

int main(){
  into();
  work();
  outo();
  return 0;
}

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

// boost
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)

const long long INF = 1LL << 60;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ll n;
  cin >> n;

  vll a(n);
  rep(i, n) {
    string s;
    cin >> s;

    auto pit = s.find(".");
    ll p, q;
    ll v;
    if (pit == string::npos) {
      p = std::atoll(s.c_str());
      q = 0;
    } else {
      ll k = 9 - (s.size() - pit) + 1;
      rep(i, k) {
        s += '0';
      }
      p = std::atoll(s.c_str());
      q = std::atoll(s.substr(pit + 1).c_str());
    }
    v = p * (ll)1e9;
    v += q;
    a.push_back(v);
  }

  vvll m(19, vll(19));
  for (auto it : a) {
    ll t = 0, f = 0;
    while (it > 0 && it % 2 == 0) {
      it /= 2;
      t++;
    }
    while (it > 0 && it % 5 == 0) {
      it /= 5;
      f++;
    }
    chmin(t, (ll)18);
    chmin(f, (ll)18);
    m[t][f]++;
  }

  ll ans = 0;
  for (auto it : a) {
    ll t = 0, f = 0;
    while (it > 0 && it % 2 == 0) {
      it /= 2;
      t++;
    }
    while (it > 0 && it % 5 == 0) {
      it /= 5;
      f++;
    }
    chmin(t, (ll)18);
    chmin(f, (ll)18);
    FOR(i, 18 - t, 19) {
      FOR(j, 18 - f, 19) {
        ans += m[i][j];
        if (i == t && j == f) {
          ans--;
        }
      }
    }
    m[t][f]--;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6336
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int N,M,p[15],n[15],i,j,t,q,R,s[16];
int main()
{
	for(i=s[0]=1;i<16;i++)s[i]=s[i-1]*3;
	for(;scanf("%d%d",&N,&M),N;)
	{
		memset(n,0,sizeof(n));
		for(i=R=0;i<3;i++)
			for(scanf("%d",&t),j=0;j<t;p[N-q]=i,j++)
				scanf("%d",&q);
		for(i=N-1;i>=0;i--)
		{
			t=abs(p[i]-n[i]);
			R+=t*s[i];
			for(j=0;j<i;j++)
			if(t==1)n[j]=2-n[i];
		}
		R=R>s[N]-1-R?s[N]-1-R:R;
		printf("%d\n",R>M?-1:R);
	}
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int a[100000+5]={0};

int main()
{
	long long n;
	cin>>n;
	int num=0;
	if(n==0)
	{
		cout<<0<<"\n";
		return 0;
	}
		while(n!=0)
		{
			a[num]=abs(n%(-2));
			n=(n-a[num])/(-2);
			num++;
		}
		for(int i=num-1;i>=0;i--)
		cout<<a[i];
		cout<<"\n";
	
	return 0;
}

Measured memory_bytes: 256
import java.util.*
fun main(args: Array<String>){
	val cin = Scanner(System.`in`)
    val n = cin.nextInt()

    val a = Array<Int>(n, { it + 1 })

    var sum = 0

    for (i in 0..n-1) {
        if (a[i] != cin.nextInt()) {
            sum += 1
        }
    }

    if (sum > 2) {
        println("NO")
    } else {
        println("YES")
    }
}

Measured memory_bytes: 31520
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
    int k,n;
    cin>>k;
    string s,ans;
    cin>>s;
    n=s.size();
    if(n<=k) {
        cout<<s<<"\n";
    }
    else {
        ans=s.substr(0,k);
        ans+="...";
        cout<<ans<<"\n";
    }
}

Measured memory_bytes: 3632
#include<iostream>

using namespace std;

int main(){
 int a,b,c;
  cin >> a >> b >> c;
  
  bool res=false;
  for(int i=1;i<=b;i++){
   if((i*a)%b==c) {
     res=true;
    break;
   }
  }
  
  
 if(res) cout << "YES" << endl;
 else cout << "NO" << endl;

}

Measured memory_bytes: 256
/// Source : https://atcoder.jp/contests/abc042/tasks/abc042_b
/// Author : liuyubobobo
/// Time   : 2020-09-22

#include <iostream>
#include <vector>

using namespace std;


/// Sorting
/// Time Complexity: O(nlogn * L)
/// Space Complexity: O(n * L)
class Solution{

public:
    string getString(vector<string>& v){

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

        string res = "";
        for(const string& s: v) res += s;
        return res;
    }
};

int main() {

    int N, L;
    cin >> N >> L;

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

    cout << Solution().getString(v) << endl;

    return 0;
}


Measured memory_bytes: 3124
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#define int long long
#define mod 1000000007
using namespace std;
int n, k, a[600], sum, ans;
bool f(int p) {
	vector<int>v; int cnt = 0;
	for (int i = 0; i < n; i++) {
		v.push_back(a[i] % p);
		cnt += a[i] % p;
	}
	sort(v.begin(), v.end());
	int c1 = 0;
	for (int i = 0; i < v.size() - cnt / p; i++)c1 += v[i];
	return c1 <= k;
}
signed main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i]; sum += a[i];
	}
	for (int i = 1; i*i <= sum; i++) {
		if (sum%i == 0) {
			if (f(i))ans = i;
			if (f(sum / i)) {
				cout << sum / i << endl;
				return 0;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a<c) { a=c; }
    if(b>d) { b=d; }
    if(b-a<0) { cout << 0 << endl; }
    else { cout << b-a << endl; }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int K = sc.nextInt();

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

			//A
			if (i % 2 == 0) {
				if (A % 2 == 1) {
					--A;
				}
				A /= 2;
				B += A;
			} else {
				if (B % 2 == 1) {
					--B;
				}
				B /= 2;
				A += B;
			}
		}
		System.out.println(A + " " + B);
	}

}


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int n,k,c;
    string s;
    cin>>n>>k>>c;
    cin>>s;
    vector<int>pos(k+1);
    pos[k]=200005;
    int crpos=-200005;
    int crk=0;
    for(int i=0;i<n;i++){
        if(s[i]=='o'){
            if(crk<k&&i-crpos>c){
                pos[crk]=i;
                crpos=i;
                crk++;
            }
        }
    }
    vector<int>ans;
    int crvld=n-1;
    for(int i=k-1;i>=0;i--){
        while(s[crvld]=='x'||pos[i+1]-crvld<=c) crvld--;
        if(crvld==pos[i]){
            ans.push_back(pos[i]+1);
        }else{
            pos[i]=crvld;
        }
    }
    for(int i=ans.size()-1;i>=0;i--)
        cout << ans[i] << '\n';
    return 0;
}
/***
11 3 2
ooxxxoxxxoo
*/


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

long num=0;
int c,m,sum=0;
char n[9];

int main()
  {
  	scanf("%s",n);
  	m=strlen(n)-1;
  	for (int i=0;i<=m;++i)
  	  {
  	  	sum+=(n[i]-'0');
  	  	num=num*10+(n[i]-'0');
		}
	if (num%sum==0)
	  cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
  }

Measured memory_bytes: 256
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/random.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::integer;
namespace rnd = boost::random;

using ll = long long;
namespace bst = boost;
namespace icl = boost::icl;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<ll> D;

  invec<int> c(26);
  vector<vector<int>> s(D, vector<int>(26));
  for (auto&& i : s)
    for (auto&& j : i)
      cin >> j;
  vector<int> t(D), highest;
  ll high = -9999999999, cost = 0;
  rnd::mt19937 mt;
  rnd::uniform_int_distribution rnd_plan(1, 26);
  rnd::uniform_real_distribution<> dist2(0.0, 1.0);

  REP(i, 26) {
    cost += c[i];
  }

  const int tier = cost;
  
  int lastf[26] = {0};
  REP(i, D) {
    pair<int, int> cand = {-999999999, 0};
    
    REP(j, 26)
      cand = max(cand, make_pair(s[i][j] + c[j] * (i + 1 - lastf[j]), j));
    t[i] = cand.second + 1;
    
    const int plan = t[i] - 1;
    lastf[plan] = i + 1;
  }  
  
  const int ITER = 977721600 / D;
  long double temp = 0.5;
  const long double temp_down = temp * pow(0.1, 1.0 / (double)ITER);
  
  REP(loop, ITER) {
    int r = 0;
    int last[26] = {0};
    
    const int update = loop % D;
    const int told = t[update];
    t[update] = rnd_plan(mt);
    
    REP(i, D) {
      const int plan = t[i] - 1;
      r += s[i][plan];
      cost -= c[plan] * (i + 1 - last[plan]);
      last[plan] = i + 1;
      r -= cost;
      cost += tier;
    }
    
    if (r > high) {
      high = r;
      highest = t;
    }
    else if (dist2(mt) > exp((double)(r - high) / 128.0 / temp))
      t[update] = told;
    cost = tier;
    temp *= temp_down;
  }
  
  for (auto i : highest)
    cout << i << endl;
}

template<typename T> void plot(const T& func) { cout << setprecision(9) << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }

int main() {
  plot(solve);

  return 0;
}




Measured memory_bytes: 4188
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: u64,
        b: u64,
        c: u64,
        d: u64,
    }
    println!(
        "{}",
        if a + b < c + d {
            "Right"
        } else if a + b > c + d {
            "Left"
        } else {
            "Balanced"
        }
    );
}


Measured memory_bytes: 4352
n = int(input())
p = list(map(int,input().split()))
ans = 1
p_min = p[0]
i = 1
while i <= n-1:
    if  p_min >= p[i]:
        p_min = p[i]
        ans += 1
        i += 1      
    else:
        i += 1
print(ans)

Measured memory_bytes: 24744
#include <iostream>
#include <math.h>

using namespace std;

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

long dfs(string s, long prev, long sum, int level) {
  if (level == s.length()) {
    return sum + prev;
  }

  long ans = 0;

  ans += dfs(s, (prev*10)+ctoi(s.at(level)), sum, level+1);
  ans += dfs(s, ctoi(s.at(level)), sum+prev, level+1);

  return ans;
}

long solve(string s) {
  return dfs(s, ctoi(s.at(0)), 0, 1);
}

int main() {
  string s;
  cin >> s;
  long ans = solve(s);
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 211;
const int mod = 998244353;
int n;
LL base[N];
struct ddd{
    int x, y;
}nd[N];
LL sq(LL x){return x * x;}
bool check(LL x1, LL y1, LL x2, LL y2){
    LL a = x1 * x2 + y1 * y2;
    LL b = (sq(x1) + sq(y1)) * (sq(x2) + sq(y2));
    return a > 0 && b == sq(a);
}
int main(){
    cin>>n;
    for(int i = 1;i <= n; i++){
        scanf("%d%d", &nd[i].x, &nd[i].y);
    }
    base[0] = 1;
    for(int i = 1;i <= 200; i++)base[i] = base[i-1] * 2 % mod;
    LL ans = (base[n] - 1 - n + mod) % mod;
    for(int i = 2;i <= n; i++){
        for(int j = 1;j < i; j++){
            int tot = 0;
            for(int k = 1;k <= n; k++){
                if(i == k || j == k)continue;
                if(check(nd[i].x - nd[k].x, nd[i].y - nd[k].y, nd[k].x - nd[j].x, nd[k].y - nd[j].y))tot++;
            }
            ans = (ans + mod - base[tot]) % mod;
            //printf("i=%d j=%d tot=%d\n", i, j, tot);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; } value
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<int> vec(m);
  int sum = 0;
  REP(i,m) {
    cin >> vec[i];
    sum += vec[i];
  }
  if(sum > n) cout << -1 << endl;
  else cout << n - sum << endl;
}

Measured memory_bytes: 3660
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,=I()
l=[];dp=[[0,0,0] for i in range(n)]
for i in range(n):
	l.append(I())
dp[0]=list(l[0])
for i in range(1,n):
	dp[i][0]=l[i][0]+max(dp[i-1][1],dp[i-1][2])
	dp[i][1]=l[i][1]+max(dp[i-1][0],dp[i-1][2])
	dp[i][2]=l[i][2]+max(dp[i-1][1],dp[i-1][0])
print(max(dp[n-1]))

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

int main(){
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 1; i < s.length(); i++){
        if(s[i] == '0') continue;
        int x = stoi(s.substr(0, i)), y = stoi(s.substr(i));
        if(x%2 == y%2){
            int a = (x+y)/2;
            if(a-x >= 0)    ans++;
        }
    }
    cout << ans+(s[s.length()-1]+1)%2 << endl;
    return 0;
}


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

using namespace std;

int a[35][100005];
int main() {
  //freopen("date.in", "r", stdin);
  //freopen("date.out", "w", stdout);

  int n, c;
  scanf("%d%d", &n, &c);
  for (int i = 1; i <= n; ++i) {
    int s, f, c;
    scanf("%d%d%d", &s, &f, &c);
    a[c][s]++;
    a[c][f + 1]--;
  }
  for (int i = 1; i <= 30; ++i)
    for (int j = 1; j <= 100000; ++j)
      a[i][j] += a[i][j - 1];
  int ans = 0;
  for (int i = 1; i <= 100000; ++i) {
    int aux = 0;
    for (int j = 1; j <= 30; ++j)
      if (a[j][i])
      aux++;
    ans = max(ans, aux);
  }
  printf("%d\n", ans);

  return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

signed main(){
	int N,K;
	cin>>N>>K;
	vint V(N);
	rep(i,N)cin>>V[i];

	int ans=-1001001001;
	for(int i=0;i<N;i++){
		for(int j=0;i+j<=N&&i+j<=K;j++){
			vint lis;
			rep(k,i)lis.pb(V[k]);
			for(int k=N-j;k<N;k++)lis.pb(V[k]);
			sort(all(lis));
			int sum=accumulate(all(lis),0ll);
			for(int k=0;k<K-i-j&&k<lis.size()&&lis[k]<0;k++)sum-=lis[k];
			chmax(ans,sum);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import copy
class Strawberry():
    def __init__(self,id, h, w):
        self.id = id
        self.h = h
        self.w = w

def main():
    h, w, k = map(int, input().split())
    strawberry_area = [[0 for _ in range(w)] for _ in range(h)]
    strawberry_id = 0
    first_row_strawberries = []
    for h_index in range(h):
        line = input()
        line_list = list(line)
        row_strawberries = 0
        strawberries = []
        for w_index in range(w):
            if line_list[w_index] == "#":
                strawberry_id += 1
                row_strawberries += 1
                strawberries.append(Strawberry(strawberry_id, h_index, w_index))
        if len(first_row_strawberries) == 0 and len(strawberries) != 0:
            first_row_strawberries = copy.copy(strawberries)

        if row_strawberries == 0 and h_index != 0:
            for w_index in range(w):
                strawberry_area[h_index][w_index] = strawberry_area[h_index-1][w_index]

        if row_strawberries != 0:
            for strawberry_index in range(len(strawberries)):
                strawberry = strawberries[strawberry_index]
                if strawberry_index == 0:
                    for w_index in range(0, strawberry.w + 1):
                        strawberry_area[h_index][w_index] = strawberry.id

                if strawberry_index != len(strawberries)-1:
                    next_strawberry = strawberries[strawberry_index+1]
                    for w_index in range(strawberry.w, next_strawberry.w):
                        strawberry_area[h_index][w_index] = strawberry.id

                if strawberry_index == len(strawberries)-1:
                    for w_index in range(strawberry.w, w):
                        strawberry_area[h_index][w_index] = strawberry.id
    first_h = first_row_strawberries[0].h
    for h_index in range(first_h-1, -1, -1):
        for w_index in range(w):
            strawberry_area[h_index][w_index] = strawberry_area[h_index+1][w_index]

    for strawberry_line in strawberry_area:
        print(" ".join(map(str, strawberry_line)))


main()

Measured memory_bytes: 49132
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


std::vector<int> a;


void dfs(int x, int i, int j, int k, int l)
{
  if (i == 0) {
    if (j && k && l)
      a.push_back(x);

    return;
  }

  dfs(x * 10 + 3, i - 1, j + 1, k,     l);
  dfs(x * 10 + 5, i - 1, j,     k + 1, l);
  dfs(x * 10 + 7, i - 1, j,     k,     l + 1);
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  for (int i = 3; i < 10; i ++)
    dfs(0, i, 0, 0, 0);

  int N, c = 0;

  std::cin >> N;

  for (const auto& i : a)
    if (i <= N)
      c ++;

  std::cout << c << std::endl;
  
  return 0;
}


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

int main(){
	int n,Mx=0,cnt=0;
	string s;
	cin >> n >> s;
	for(int i=0;i<n;i++){
		if(s[i]=='D') cnt--;
		else cnt++;
		
		Mx=max(Mx,cnt);
	}
	cout << Mx << endl;
	return 0;
}

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

using namespace std;
int main(){
    int x,n;cin>>x>>n;
    vector<int> a;
    for(int i=0;i<n;i++){
        int q;
		cin>>q;
		a.push_back(q);}
		int i=x,j=x,ans;
		vector<int>:: iterator w,e;
      while(true){
         w=find(a.begin(),a.end(),i);
         e=find(a.begin(),a.end(),j);
		  if(e==a.end()){
		  	ans=j;
		  	break;
		  }
		   if(w==a.end()){
         	ans=i;
         	break;
		 }
		  if(w!=a.end()) i++;
		  if(e!=a.end()) j--;
 	  }
    cout<<ans<<"\n";
}

Measured memory_bytes: 3644
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

using Weight=long long;
static const Weight INF=1LL<<57;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

struct UndirComp {
    bool operator()(const Edge &e, const Edge &f) const {
        if (min(e.src, e.dst) != min(f.src, f.dst)) {
            return min(e.src, e.dst) < min(f.src, f.dst);
        } else {
            return max(e.src, e.dst) < max(f.src, f.dst);
        }
    }
} undircomp;

void visit(
    const Graph &g, size_t v ,size_t u, Edges &bridge,
    stack<size_t> &roots, stack<size_t> &s, vector<bool> &stacked,
    vector<size_t> &num, int &time
) {
    num[v] = ++time;
    s.push(v), stacked[v] = true;
    roots.push(v);
    for (const Edge &e: g[v]) {
        size_t w=e.dst;
        if (!num[w]) {
            visit(g, w, v, bridge, roots, s, stacked, num, time);
        } else if (u != w && stacked[w]) {
            while (num[roots.top()] > num[w]) roots.pop();
        }
    }

    if (v == roots.top()) {
        bridge.push_back(Edge(u, v));
        while (true) {
            size_t w=s.top(); s.pop(), stacked[w]=false;
            if (v == w) break;
        }
        roots.pop();
    }
}

Edges get_bridge(const Graph &g) {
    size_t V=g.size();
    vector<size_t> num(V);
    vector<bool> stacked(V);
    stack<size_t> roots, s;
    int time=0;

    Edges bridge;
    for (size_t u=0; u<V; ++u) if (!num[u]) {
        visit(g, u, V, bridge, roots, s, stacked, num, time);
        bridge.pop_back();
    }

    return bridge;
}

int main() {
    size_t V, E;
    scanf("%zu %zu", &V, &E);

    Graph g(V);
    for (size_t i=0; i<E; ++i) {
        size_t s, t;
        scanf("%zu %zu", &s, &t);

        join(g, s, t);
    }

    Edges bridge=get_bridge(g);
    for (Edge &e: bridge)
        if (e.src > e.dst)
            swap(e.src, e.dst);

    sort(bridge.begin(), bridge.end(), undircomp);

    for (Edge &e: bridge)
        printf("%zu %zu\n", e.src, e.dst);

    return 0;
}

Measured memory_bytes: 8036
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <bitset>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int

#include <nmmintrin.h>
#ifdef _MSC_VER

#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to, w;
};
  

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

	vector<int> ans;
	if (k % 2 == 0) {
		ans.push_back(k / 2);
		REP(i, n - 1)
			ans.push_back(k);
	}
	else {

		REP(i, n)
			ans.push_back((k+1)/2);

		int bk = n / 2;
		int cc = 0;
		REP(i, bk) {
			if (ans[cc] > 1) cc = 0;
			ans[cc]--;
			rep(i, cc, n) {
				if (ans[i] < 0) {
					ans[i + 1]--;
					ans[i] = k;
				}
				else {
					if (ans[i] == 0) cc = i + 1;
					break;
				}
			}
		}
		reverse(ALL(ans));
	}
	for (auto itr : ans) {
		if (itr == 0) break;
		cout << itr << " ";
	}
	return 0;
}

Measured memory_bytes: 3568
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <functional>

using namespace std;
using ll = long long;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	ll x, y, c = 0;

	cin >> x >> y;

	while (x <= y) {
		x *= 2;
		c++;
	}

	cout << c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define y1 y1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

// Driver program
void Main() {

  int A,B,C,X;
  cin>>A>>B>>C>>X;
  int ct=0;

  rep(i,A+1){
    rep(j,B+1){
      rep(k,C+1){
        if(i*500+j*100+k*50==X) ++ct;
      }
    }
  }

  cout<< ct<<"\n";

}


//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 256
from fractions import gcd
def get_result(L, N):
    Gl = [0]*N
    Gr = [0]*N
    Gl[0] = L[0]
    Gr[N-1] = L[N-1]
    for i in range(1, N):
        Gl[i] = gcd(Gl[i-1], L[i])
    for j in range(N-2, -1, -1):
        Gr[j] = gcd(Gr[j+1], L[j])
    #print(Gl, Gr)
    full_gcd = Gr[0]
    result = full_gcd
    for i in range(N):
        if i == 0:
            x = Gr[1]
        elif i == N-1:
            x = Gl[N-2]
        else:
            x = gcd(Gl[i-1], Gr[i+1])
        if x > full_gcd:
            result = max(result, x)
    return result



N = int(input())
L = [int(s) for s in input().split(" ")]
result = get_result(L, N)
print(result )


Measured memory_bytes: 16120
#include <iostream>
#include<string>
#include<string.h>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<climits>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    double n,k;
    cin>>n>>k;
    cout<<fixed;
    cout<<setprecision(12);
    double ans = 0;
    for(int i=1;i<=n;i++){
        double y=i;
        double sum = 1/n;
        while(y<=k-1){
            sum*=0.5;
            y*=2;
        }
        ans+=sum;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e16;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define RREP(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

ll N, A, B;
vl sumbtw;

bool ok(ll K){
    ll tport = min(K/B, N-1);
    REP(i, tport+1){
        ll rem = N-1-i;
        ll walk_cost = sumbtw[rem] * A;
        if(walk_cost + i *B <= K) return true;
    }
    return false;
}

int main(){
    cin >> N >> A >> B;
    vl X(N); REP(i, N) cin >> X[i];
    vl btw(N-1, 0);
    REP(i, N-1){
        btw[i] = X[i+1]-X[i];
    }
    sort(btw.begin(), btw.end());
    sumbtw = vl(N,0);
    REP(i, N-1){
        sumbtw[i+1] = sumbtw[i] + btw[i];
    }
    
    ll l = 0, r = 1e16;
    while(abs(r-l) > 1){
        ll mid = (r+l)/2;
        bool flag = ok(mid);
        if(flag) r = mid;
        else l = mid;
    }
    
    ll ans = 0;
    if(ok(l)) ans = l;
    else if(ok(r)) ans = r;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> A(n + 1);
    A[0] = -1;
    vector<int> asc(n + 1, 1), desc(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        cin >> A[i];
        if (i == 1) {
            continue;
        }
        if (A[i] >= A[i - 1]) {
            asc[i] = min(asc[i - 1], desc[i - 1] + 1);
        } else {
            asc[i] = min(asc[i - 1] + 1, desc[i - 1] + 1);
        }
        if (A[i] <= A[i - 1]) {
            desc[i] = min(asc[i - 1] + 1, desc[i - 1]);
        } else {
            desc[i] = min(asc[i - 1] + 1, desc[i - 1] + 1);
        }
    }
    cout << min(asc[n], desc[n]) << '\n';
}


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

#define M 1000000007

using namespace std;


int main() {
	int n;
	vector<long long> a;
	long long fact = 0;
	long long sum = 0;
	
	cin >> n;

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

		a.push_back(next);
		fact = (fact + next) % M;
	}

	for (int i = 0; i < n; i++) {
		fact = (fact - a[i] + M) % M;
		sum = (sum + (a[i] * fact) % M) % M;
	}

	cout << sum % M << endl;
}


Measured memory_bytes: 5332
s = input()
t = input()

n = len(t)

ans = 100100100100
for i in range(len(s)-n+1):
    cnt = 0
    a = s[i:i+n]
    for j in range(n):
        if t[j] != a[j]:
            cnt += 1
    
    ans = min(ans,cnt)
    
print(ans)


Measured memory_bytes: 9020
h, w = map(int, input().split())
L = []
for h in range(h):
    L.append(input())
for i in range(w+2):
    print("#", end="")
print()
for j in range(h+1):
    print("#", end="")
    print(L[j], end="")
    print("#")
for k in range(w+2):
    print("#", end="")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (b); i >= (a); --i)
#define DEBUG(x) cerr << #x << ": " << (x) << '\n';

const int N = 1e5 + 5;
int n, p[N], pos[N], lb[2][N], ub[2][N];

int main() {
  cin >> n;
  FI(i,1,n) scanf("%d", &p[i]), pos[p[i]] = i;
  set<int> se;
  for (int x = n; x >= 1; --x) {
    lb[0][x] = lb[1][x] = 0;
    ub[0][x] = ub[1][x] = n + 1;
    auto it = se.lower_bound(pos[x]);
    if (it != se.begin()) {
      lb[0][x] = *prev(it, 1);
      if (prev(it, 1) != se.begin()) lb[1][x] = *prev(it, 2);
    }
    if (it != se.end()) {
      ub[0][x] = *it;
      if (next(it, 1) != se.end()) ub[1][x] = *next(it, 1);
    }
    se.insert(pos[x]);
  }
  LL ans = 0;
  for (int x = 1; x <= n; ++x) {
    int i = pos[x];
    LL cnt = 1LL * (lb[0][x] - lb[1][x]) * (ub[0][x] - i)
      + 1LL * (ub[1][x] - ub[0][x]) * (i - lb[0][x]);
    ans += x * cnt;
  }
  cout << ans << endl;
}


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

int main(void)
{
	char c;
	string s;
	while(1)
	{
		cin.get(c);
		if( !(isalpha(c) || c==' ' || c=='.') )
			break;

		if(islower(c))c=toupper(c);
		s.push_back(c);
	}
	cout << s.c_str() << endl;
	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
using namespace std;
#define ld double
#define ll long long
#define pb emplace_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) x.begin(),x.end()
ll power(ll a, ll b) {ll res = 1; a = a % mod; while (b) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b /= 2;} return res;}
ll invmod(ll a) {return power(a, mod - 2);}
vector<ll> ans;
void dfs(ll num, int dig) {
	if (dig > 10) return;
	int back = num % 10;
	ans.pb(num);
	for (auto i : { -1, 0, 1}) {
		int tmp = back + i;
		if (tmp < 0 || tmp > 9) continue;
		dfs(num * 10 + tmp, dig + 1);
	}
}
int main(void)
{
	FIO
	int t = 1;
	// cin >> t;
	while (t--)
	{
		int k;
		cin >> k;
		for (int i = 1; i <= 9; i++) dfs(i, 1);
		sort(all(ans));
		cout << ans[k - 1] << "\n";
	}
	return 0;
}

Measured memory_bytes: 5272
import math

# 入力を取得
A, B, H, M = map(int, input().split())

# 時針の角度を求める。
deg_H = (H + M / 60) / 12 * 360

# 分針の角度を求める。
if M != 0:
    deg_M = M / 60 * 360
else:
    deg_M = 360

# 針の角度の差を求める。
t = abs(deg_H - deg_M)

# 余弦定理の公式に当てはめる。
ans = math.sqrt(A*A + B*B - 2*A*B*math.cos(math.radians(t)))
print(ans)

Measured memory_bytes: 9516
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x,m[1000010],g=0,cnt=0;
    cin>>n>>x;
    for(int i=0; i<n; i++){
        cin>>m[i];
    }
    for(int i=0; i<n; i++){
        g=g+m[i];
        x=x-m[i];
        cnt++;
    }
    sort(m,m+n);
    x=x/m[0];
    cnt=cnt+x;
    cout<<cnt<<'\n';
    return(0);
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline

switch,denkyu=map(int,input().split())
connect=[]
for i in range(denkyu):
  l=list(map(int,input().split()))
  connect.append(l)
amari=list(map(int,input().split()))
okcombcounter=0
for i in range(2**switch):
  state=format(i,'b').zfill(switch)
  tentoucounter=0
  for j in range(denkyu):
    oncounter=0
    for k in range(connect[j][0]):
      if state[connect[j][k+1]-1]=='1':
        oncounter+=1
    if oncounter%2==amari[j]:
      tentoucounter+=1
  if tentoucounter==denkyu:
    okcombcounter+=1
print(okcombcounter)

Measured memory_bytes: 3064
class UnionFind:
    def __init__(self,n):
        self.table = [-1]*n

    def root(self,x):
        stack = []
        tbl = self.table
        while tbl[x]>=0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self,x,y):
        return self.root(x)==self.root(y)
    def union(self,x,y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -=1
        else:
            self.table[r1] = r2
N,M = map(int,input().split())
AB = []
for i in range(M):
    AB.append(list(map(int,input().split())))
uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
r = [0]*N
for i in range(N):
    r[i]=uf.root(i)
print(len(set(r))-1)

Measured memory_bytes: 30444
#include <bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
#define MAXX 500005
 
#define PI   3.14159265358979323846264338327950
 
#define PB push_back 
#define PF push_front
#define F first
#define S second
 
#define fixx(n) fixed << setprecision(n)
 
#define ll 	  long long int
 
#define mod  1000000007



int main()
{
	FAST;
	ll n;
	cin >> n;
	ll  k = 0;
	ll  h = 1;
	while(n >= 1){
		
		k += h;
		h *= 2;
		n /= 2;
	}
	cout << k;
	return 0;
}

Measured memory_bytes: 3584