akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
using ll = long long;
using namespace std;
typedef pair<int, int> P;

bool pc1(const P& firstElof, const P& secondElof)
{//first降順
	return firstElof.first > secondElof.first;
}
bool pc2(const P& firstElof, const P& secondElof)
{//first昇順
	return firstElof.first < secondElof.first;
}
bool pc3(const P& firstElof, const P& secondElof)
{//second降順
	return firstElof.second > secondElof.second;
}
bool pc4(const P& firstElof, const P& secondElof)
{//second昇順
	return firstElof.second < secondElof.second;
}
int main() {
	ll A, B;
	cin >> A >> B;
	ll ans = A;
	ll count = 0;
	if (A % 2 == 0 && B % 2 == 0) {
		//OK
		count = (B - A - 1) / 2;
		if (A == B) {
			ans = ans;
		}
		else {
			if (count % 2 == 0) {
				count = 0;
			}
			else {
				count = 1;
			}
			ans = A xor count xor B xor  A+1;
		}

	}
	else if (A % 2 == 0 && B % 2 != 0) {
		//OK?
		count = (B - A + 1) / 2;
		if (A + 1 == B) {
			ans = A xor B;
		}
		else {
			if (count % 2 == 0) {
				count = 0;
			}
			else {
				count = 1;
			}
			ans = count;
		}

	}
	else if (A % 2 != 0) {
		if (B % 2 == 0) {
			//OK
			count = (B - A) / 2;
		
				if (count % 2 == 0) {
					count = 0;
				}
				else {
					count = 1;
				}
				ans = count xor A xor B;
			
		}
		else if (B % 2 != 0) {
			//OK?
			count = (B - A - 1) / 2;
			if (A == B) {
				ans = ans;
			}
			else {
				if (count % 2 == 0) {
					count = 0;
				}
				else {
					count = 1;
				}
				ans = B xor count xor A xor (B - 1);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a==b&&a!=c)
    {
        printf("%d",c);
    }
    else if(a==c&&a!=b)
    {
        printf("%d",b);
    }
    else
    {
        printf("%d",a);
    }
    return 0;










}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double a = sc.nextDouble();
        double b = sc.nextDouble();
        double h = sc.nextInt();
        double m = sc.nextInt();
        double mm = -Math.toRadians(m)*6;
        double hh = -Math.toRadians(h+m/60)*30;
        double x = Math.cos(hh)*a-Math.cos(mm)*b;
        double y = Math.sin(hh)*a-Math.sin(mm)*b;
        System.out.println(Math.sqrt(x*x+y*y));
    }
}


Measured memory_bytes: 37536
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#define rep(i,n) for(int i = 0;i<(n);i++);
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 10010010010;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll gcd(ll a, ll b) {//a>b
	if (a < b)swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
int main() {
	ll N;
	cin >> N;
	vector<string> word(N);
	string S;
	for (int i = 0; i < N; i++) {
		cin >> S;
		sort(all(S));
		word[i] = S;
	}
	map<string, ll> kaisu;
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		ans += kaisu[word[i]];
		kaisu[word[i]]++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 11904
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Product of Arithmetic Progression
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MOD = 1000003;
const int MAX_K = MOD * 2;

/* typedef */

typedef long long ll;

/* global variables */

int fracs[MAX_K + 1], invfs[MAX_K + 1];

/* subroutines */

ll powmod(ll a, int n) {  // a^n % MOD
  ll pm = 1;
  while (n > 0) {
    if (n & 1) pm = (pm * a) % MOD;
    a = (a * a) % MOD;
    n >>= 1;
  }
  return pm;
}

/* main */

int main() {
  fracs[0] = invfs[0] = 1;
  for (int i = 1; i <= MAX_K; i++) {
    fracs[i] = (ll)fracs[i - 1] * i % MOD;
    invfs[i] = powmod(fracs[i], MOD - 2);
  }

  int q;
  scanf("%d", &q);

  while (q--) {
    int x, d, n;
    scanf("%d%d%d", &x, &d, &n);

    int sum = 0;
    if (d == 0) sum = powmod(x, n);
    else if (n < MOD) {
      int y = (ll)x * powmod(d, MOD - 2) % MOD;
      sum = fracs[y + n - 1];
      if (y > 0) sum = (ll)sum * invfs[y - 1] % MOD;
      sum = (ll)sum * powmod(d, n) % MOD;
    }

    printf("%d\n", sum);
  }
  return 0;
}


Measured memory_bytes: 16512
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int N;
char c[212345];

int main() {

	cin >> N;
	cin >> c;

	int l = 0, r = N - 1, ans = 0;

	while (l <= r) {
		while (c[l] == 'R') ++l;
		while (c[r] == 'W') --r;
		if (l <= r) {
			swap(c[l], c[r]);
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

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

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String str = br.readLine();
    	final int H = Integer.parseInt(str.split(" ")[0]);
    	final int W = Integer.parseInt(str.split(" ")[1]);
    	str = br.readLine();
    	final int h = Integer.parseInt(str.split(" ")[0]);
    	final int w = Integer.parseInt(str.split(" ")[1]);

    	
		if (H == h || W == w) {
			System.out.println(0);
    	} else {
    		System.out.println((H - h) * (W - w));
    	}
	}
}


Measured memory_bytes: 21844
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools

def main():
    s = list(input().rstrip())
    n = len(s)
    k = s.copy()
    k.reverse()
    if k != s:
        print("No")
        exit()
    k = s[0:(n-1)//2]
    l = k.copy()
    l.reverse()
    if k != l:
        print("No")
        exit()
    k = s[(n-1)//2+1:]
    l = k.copy()
    if k != l:
        print("No")
        exit()
    print("Yes")

if __name__=="__main__":
    main()


Measured memory_bytes: 62452
import math

a,b,x=list(map(int, input().split()))

if x/(a**2)/b < 1/2:
    print(180*math.atan((a*b**2)/(2*x))/math.pi)

else:
    print(180*math.atan(2*(a*b-x/a)/(a**2))/math.pi)
    


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define x first
#define y second
#define mod 1e9+7
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rof(i,a,b) for(ll i=a;i>b;i--)
int no=1;
//int a[1001][1001] //aise global me hi
bool firstone=true;
ll lcm(ll a, ll b){
    return a / __gcd(a, b) * b;
}
 int a[10][1000];int h,w,k;bool cut[10];
//memset can initialize to 0 or -1 ONLY
// memset(a,0,sizeof(a[0][0])*n*n); //2D array
//memset(a, 0, sizeof(a));  //1D array
//memset(str, 't', sizeof(str)); // string
int ans=-1;
void ch(int ii)
{
//i ko kaato 
// i ko mat kaato

if(ii<=h-1)
{
cut[ii]=0; ch(ii+1);
cut[ii]=1; ch(ii+1);
return;
}

//i == h-1 
// end aaagya bhaya

bool exists=true;int vcuts=0;

int p=0;//partitians
f(i,0,h) if(cut[i]==1) p++;
p++;
int tmp[p][w]; 
f(i,0,p)
{
    f(j,0,w) tmp[i][j]=0;
}

int index=0;



f(i,0,h)
{
	f(j,0,w) tmp[index][j]+=a[i][j];
	if(cut[i]==1) index++;
}


f(i,0,p)
f(j,0,w)
{
if(tmp[i][j]>k) {return;}
}

// check if with vertical cuts u can make it in = parts
//individual col ka sum>k retuen
vcuts=0;
f(j,1,w)
{
//check if we can combine
bool ad=true;
f(i,0,p)
if(tmp[i][j]+tmp[i][j-1]>k) {ad=false;break;}

if(ad==true)
{
	f(i,0,p)
	tmp[i][j]+=tmp[i][j-1];
}
else
{
  //cout<<" "<<vcuts;
	vcuts++;
	  //if(firstone){vcuts++; cout<<"QDW"<<j<<" SD "<<vcuts<<endl;}
}

}
//if(firstone) cout<<ans<<" "<<vcuts<<endl;
if(ans==-1||vcuts+p-1<ans)
{ans=vcuts+p-1;
//
// if(ans==1)
// {
    
//     cout<<no<<" "<<p<<" "<<vcuts<<endl;
//     f(i,0,10) cout<<cut[i]<<" ";cout<<endl;
//     f(i,0,w) cout<<tmp[0][i]<<" "; cout<<endl;
//     firstone=false;
// }
//
}

}
void solve()
{
	
// 	memset(a,0,sizeof(a[0][0]*10*1000));
//   memset(cut,-1,sizeof(cut));
  cin>>h>>w>>k;
 
 
 
f(i,0,h)
{
    f(j,0,w)
    a[i][j]=0;

}
f(i,0,10) cut[i]=-1;
 
 
 
string s;

  f(i,0,h)
  {cut[i]=0;
  cin>>s;
  f(j,0,w) 
  a[i][j]=s[j]-'0';
  }
  
  
  

ch(0);

cout<<ans;

}





int main()
{

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

    int t=1;
  //
      while(t--)
    {
   // cout<<"EDAS";
    solve();
    
    }

}

Measured memory_bytes: 384
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

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

int main() {
  int N;
  vector<int> a(N);
  int res = 0;

  cin >> N;
  REP(i, N) { cin >> a[i]; }
  sort(a.begin(), a.end(), greater<int>());

  for (int i = 0; i < N; i += 2) {
    res += a[i];
  }
  for (int i = 1; i < N; i += 2) {
    res -= a[i];
  }
  cout << res << endl;
}


Measured memory_bytes: 3736
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unsigned long long int ull;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const int INF=1e9;
const ll MOD=1e9+7;

struct UnionFind {
    vector<int> par,rank;
    vector<ll> cnt;
    UnionFind(int n):par(n),rank(n,0),cnt(n,1){
        for(int i=0;i<n;++i) par[i]=i;
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x]=root(par[x]);
    }
    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry) return ;
        if(rank[rx]<rank[ry]){
            par[rx]=ry;
            cnt[ry]+=cnt[rx];
        }else{
            par[ry]=rx;
            cnt[rx]+=cnt[ry];
        }
        if(rank[rx]==rank[ry]) rank[rx]++;
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    int count(int x){
        return cnt[root(x)];
    }
};
struct edge{
    int a,b,y;
    edge(){};
    edge(int a,int b,int y):a(a),b(b),y(y){};
    bool operator<(const edge& rhs){
        return y<rhs.y;
    }
};

int main(){
    string s;cin>>s;
    int n=(int)s.size();
    int ans=0;
    for(int i=0;i<n-1;++i){
        if(s[i]!=s[i+1]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);

    int ret = n / 11 * 2;
    if (n % 11) {
        ret += (n % 11) < 7 ? 1 : 2;
    }

    cout << ret << endl;


    return 0;
}



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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

int main() {
    vector<int> ans;
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;

        vector<int> v(n);
        for (int &x : v) cin >>x;

        for (int i = 1; i < n; i++) {
            v[i] = v[i] + v[i-1];
        }

        int Max = v[0];    
        int a = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                Max = max(Max, v[j] - a);
            }
            a = v[i];
        }

        ans.push_back(Max);
    }

    for (int x : ans) {
        cout << x << endl;
    }

    return 0;
}

Measured memory_bytes: 3164
import java.util.Scanner;

public class Main {

	private static int M = 1000000007;

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

		long n = sc.nextInt();
		long m = sc.nextInt();
		long answer = 1;

		for (int i = 2; i * i <= m; i++) {
			if (m % i != 0) continue;
			long t = 0;
			while (m % i == 0) {
				t++;
				m /= i;
			}
			answer = (answer * comb(t + n - 1, n - 1)) % M;
		}

		if (m != 1) answer = (answer * comb(n, n - 1)) % M;
		System.out.println(answer);
	}

	private static long comb(long a, long b) {
		if (b > a - b) return comb(a, a - b);

		long x = 1;
		long y = 1;
		for (int i = 0; i < b; i++) {
			x = (x * (a - i)) % M;
			y = (y * (i + 1)) % M;
		}

		return (x * pow(y, M - 2) % M);
	}

	private static long pow(long x, long n) {
		long a = 1;
		while (n > 0) {
			if ((n & 1) == 1) {
				a = (a * x) % M;
			}
			x = (x * x) % M;
			n >>= 1;
		}
		return a;
	}
}


Measured memory_bytes: 23764
n = int(input())
a = list(map(int, input().split()))
x = sum(a)
b = list(map(int, input().split()))
for i in range(n):
    if a[i] < b[i]:
        if a[i+1] >= b[i] - a[i]:
            a[i+1] = a[i+1] - b[i] + a[i]
        else:
            a[i+1] = 0
        a[i] = 0
    else:
        a[i] = a[i] - b[i]
print(x - sum(a))

Measured memory_bytes: 24156
#include<stdio.h>
int MAX(int a,int b){return a<b?b:a;}
int q[1000000],C[100010];
int ta[100010],nt[200010],to[200010],co[200010];
int f[100010];
int dfs(int v,int e,int s){
  int i,max=0;
  for(i=ta[s];i+1;i=nt[i]){
    if(f[to[i]])continue;
    f[to[i]]=1;
    C[to[i]]=C[s]+co[i];
    max=MAX(max,C[to[i]]);
    max=MAX(max,dfs(v,e,to[i]));
  }//printf("s%d m%d\n",s,max);
  return max;
}
/*int bfs(int v,int e,int s,int *g){
  int t,r,i,max=0;
  for(i=0;i<v;i++)C[i]=1000000000;
  C[q[0]=s]=t=0;//printf("a\n");
  for(r=1;r-t;t++){
    for(i=ta[q[t]];i+1;i=nt[i]){//printf("%d %d\n",fr[i],to[i]);
      if(C[to[i]]>C[s]+co[i]){
	C[to[i]]=C[s]+co[i];
        if(max<C[to[i]]){
	  max=C[to[i]];
	  *g=to[i];
	}
	q[r++]=to[i];
      }
    }//printf("\n");
  }//printf("%d\n",r);
  return max;
  }//*/
int tyokkei(int v,int e,int *a){
  int i,max=0,g;
  for(i=0;i<v;i++){
    ta[i]=-1;
    C[i]=1000000000;
    f[i]=0;
  }
  C[0]=0;
  f[0]=1;
  for(i=0;i<e;i++){
    nt[i]=ta[a[i]];
    ta[a[i]]=i;
    nt[i+e]=ta[to[i]];
    to[i+e]=a[i];
    co[i+e]=co[i];
    ta[to[i]]=i+e;    
  }//printf("a\n");
  //for(i=0;i<2*e;i++)printf("%d %d\n",fr[i],to[i]);printf("\n");
  max=dfs(v,e*2,0);//printf("m%d\n",max);
  for(i=0;i<v;i++){
    if(max==C[i])g=i;
    C[i]=1000000000;
    f[i]=0;
  }
  C[g]=0;
  f[g]=1;//printf("%d\n",g);
  return dfs(v,e*2,g);
}
int main(){
  int n,a[100010],i;
  scanf("%d",&n);
  for(i=0;i<n-1;i++)scanf("%d %d %d",&a[i],&to[i],&co[i]);
  printf("%d\n",tyokkei(n,n-1,a));
  return 0;
}

Measured memory_bytes: 10548
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int32_t;
using Pair = pair<int32_t, int32_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int32_t N;
  cin >> N;
  // const int32_t L = static_cast<int32_t>(T.length());
  map<int32_t, int32_t> counts_map;
  int32_t max_value = INT32_MIN;
  for (int32_t i = 0; i < N; ++i) {
    int32_t a;
    cin >> a;
    if (counts_map.find(a) == counts_map.end()) {
      counts_map[a] = 1L;
    } else {
      ++counts_map[a];
    }
    if (a > max_value) {
      max_value = a;
    }
  }
  vector<Pair> counts;
  vector<int64_t> m(1000001, -1);
  int32_t i = 0;
  for (const auto p : counts_map) {
    counts.emplace_back(p);
    m[p.first] = i;
    ++i;
    // cerr << p.first << ", " << p.second << endl;
  }
  const int32_t Z = static_cast<int32_t>(counts.size());
  for (int32_t i = 0; i < Z; ++i) {
    if (counts[i].second > 0) {
      for (int32_t j = 2 * counts[i].first; j <= max_value; j += counts[i].first) {
        if (m[j] > 0) {
          counts[m[j]].second = -1;
        }
      }
    }
  }
  int32_t result = 0;
  for (int32_t i = 0; i < Z; ++i) {
    if (counts[i].second == 1) {
      ++result;
    }
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 22524
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    for (int i = 1; i < s.size(); ++i)
        if (s[i - 1] == 'B' && s[i] == 'C')
            s[i - 1] = 'D';

    string z;
    vector<string> vz;
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] != 'A' && s[i] != 'D')
        {
            vz.push_back(z);
            z.clear();
        }
        else
        {
            z.push_back(s[i]);
            if (s[i] == 'D')
                i++;
        }
    }
    vz.push_back(z);
    ll sol = 0;
    for (string& z : vz)
    {
        ll dc = 0;
        for (int i = 0; i < z.size(); ++i)
            if (z[i] == 'D')
                sol += i - dc, dc++;
    }
    cout << sol;
}


Measured memory_bytes: 5388
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef complex<double> comp;
const ll inf=1e9+7;
const ll mod=1e9+7;
const int MAX=1010;

//dijkstra(O(ElogV))
//0-indexed
ll n;
vector<vector<pll> >G(1000010);
vector<ll> d(1000010);
void dijkstra(ll s,vector<vector<pll> >&G,vector<ll> &d){
    priority_queue<pll,vector<pll>,greater<pll> >pq;
    rep(i,n){
        d[i]=inf*inf;
    }
    d[s]=0;
    pq.push(mp(0,s));
    while(!pq.empty()){
        pll k=pq.top();pq.pop();
        ll v=k.second;
        if(d[v]<k.first)continue;
        for(auto e:G[v]){
            if(d[e.first]>d[v]+e.second){
                d[e.first]=d[v]+e.second;
                pq.push(mp(d[e.first],e.first));
            }
        }
    }
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

signed main(){
    ll h,w;cin>>h>>w;
    n=h*w;
    ll sx,sy;cin>>sx>>sy;
    sx--;sy--;
    ll gx,gy;cin>>gx>>gy;
    gx--;gy--;
    vector<string>s(h);
    rep(i,h)cin>>s[i];
    rep(i,h){
        rep(j,w){
            if(s[i][j]=='#')continue;
            ll now=i*w+j;
            rep(l,4){
                ll nx=i+dx[l];
                ll ny=j+dy[l];
                if(nx<0||nx>=h||ny<0||ny>=w)continue;
                if(s[nx][ny]=='#')continue;
                G[now].pb(mp(nx*w+ny,0));
            }
            rep(p,5){
                rep(q,5){
                    ll nx=i-2+p;
                    ll ny=j-2+q;
                    if(nx<0||nx>=h||ny<0||ny>=w)continue;
                    if(s[nx][ny]=='#')continue;
                    G[now].pb(mp(nx*w+ny,1));
                }
            }
        }
    }
    dijkstra(sx*w+sy,G,d);
    ll ans=d[gx*w+gy];
    if(ans==inf*inf)ans=-1;
    cout<<ans<<endl;
}

Measured memory_bytes: 206676
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]A - Three-letter acronym

            Console.WriteLine(GetAcronym());
        }

        static string GetAcronym()
        {
            var s = Console.ReadLine();
            var array = s.Split(' ');
            var acronym = "";
            
            foreach(var a in array)
            {
                acronym += GetInitial(a);
            }

            return acronym;
        }

        static string GetInitial(string s)
        {
            return s[0].ToString().ToUpper();
        }
    }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define      fastt       ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define      debug       printf("\n<<CameHere>>\n")
#define      mem(x,y)    memset(x, y, sizeof(x))
#define      all(qz)     qz.begin(),qz.end()
#define      rall(qz)    qz.rbegin(),qz.rend()
#define      inf         1000000000000000000
#define      mod         1000000007
#define      Sqr(x)      ((x)*(x))
#define      ll          long long
#define      mk          make_pair
#define      pb          push_back
#define      pi          acos(-1.0)
#define      cos(a)      cos(a*pi/180)
#define      sin(a)      sin(a*pi/180)
#define      tan(a)      tan(a*pi/180)

#define toll(a) atoll(a.c_str())
string tostr(ll a) {stringstream rr;rr<<a;return rr.str();}
ll pow(ll c,ll d){return d==0?:c*pow(c,d-1);}
ll gcd(ll a,ll b) {return b==0? a:gcd(b,a%b);}
ll lcm(ll a,ll b) {return ((a*b)/gcd(a,b));}
/*---------AL ASAD NUR RIYAD------------*/


int main()
{
    fastt

    ll x,k,d;
    cin>>x>>k>>d;
    ll ab=abs(x);
    ll rem=ab%d;
    ll xx=ab-rem;
    ll tm=xx/d;
    //cout<<rem<<endl;
    if(tm>=k){
        cout<<ab-(k*d)<<endl;
        return 0;
    }
    else{
        k-=tm;
        if(k%2==0) cout<<rem<<endl;
        else cout<<abs(rem-d)<<endl;
    }
    return 0;
}





















Measured memory_bytes: 3624
#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 MOD = 998244353, INF = 1e9 * 1e9 + 10, eps = 1e-7;

ll dp[405][405][405];

vector<pair<ll, ll>> vec;

int main()
{
	fastInp;

	string s;
	ll k;
	cin >> s >> k;

	ll n = s.size();
	ll pr = -1, cnt = 0;
	s.push_back('a');
	k = min(k, ll(400));
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '0') {
			vec.push_back({ cnt, 1 });
			cnt = 0;
		}
		else if (s[i] == 'a') {
			vec.push_back({ cnt, 1 });
		}
		else if (s[i] == '1') {
			cnt++;
		}

		pr = s[i] - '0';
	}

	dp[0][0][0] = 1;
	ll ind = 1;

	ll sm = 0;
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i].second == 0) continue;
		vector<vector<ll>> pref(k + 1);
		for (int j = 0; j <= k; j++) {
			pref[j].push_back(0);
			for (int t = 0; t <= k; t++) pref[j].push_back(pref[j].back() + dp[ind - 1][j][t]);
		}
		for (int t = 0; t <= k; t++) {

			ll cnt = 0;
			for (int j = 0; j <= k; j++) {  // j + t -
				if (j < t) continue;
				
				ll vl = 0;
				if (t + 1 < pref[j].size()) vl = pref[j][t + 1] - pref[j][max(0ll, t - vec[i].first)];
				dp[ind][j][t] += cnt + vl;
				cnt += dp[ind - 1][j][t];
				cnt %= MOD;
				dp[ind][j][t] %= MOD;
				if (i == vec.size() - 1 && j == t && j <= k) sm += dp[ind][j][t];
				sm %= MOD;
				//cout << dp[ind][j][t] << " ";
			}
			//cout << "\n";
		}

		ind++;
		//cout << "-\n";
	}

	cout << sm;
	return 0;
}

Measured memory_bytes: 197108
import java.io.*;
import java.util.*;
 
public class Main {
    //static final long MOD = 1000000007L;
    static final long DIV2 = 500000004L;
    static final long MOD = 998244353L;
    static final int INF = 50000000;
    static final int NINF = -500000000;
 
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);
        
        long A = sc.nl();
        long B = sc.nl();
        long C = sc.nl();
        long D = sc.nl();
        pw.println(Math.max(Math.max(A*C,A*D),Math.max(B*C, B*D)));
        pw.close();
    }
    
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int ni() {
            return Integer.parseInt(next());
        }
 
        long nl() {
            return Long.parseLong(next());
        }
 
        double nd() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 32928
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    string s;
    cin >> s;

    if (s.size() > k) {
        s.resize(k);
        s += "...";
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 3628
n,a,b,c = map(int,input().split())
mod = 10**9+7

fact = [1]*(2*n+10)
for i in range(1,2*n+10):
    fact[i] = fact[i-1]*i%mod

def mod_comb_k(n,k,mod):

    return fact[n] * pow(fact[k], mod - 2, mod) % mod * pow(fact[n-k], mod-2 , mod)

def fa(x):
    return pow(a*pow(a+b,mod-2,mod),x,mod)

def fb(x):
    return pow(b*pow(a+b,mod-2,mod),x,mod)



res = 0
for k in range(n):
    res = (res + (mod_comb_k(n+k-1,k,mod) * (fa(n)*fb(k)%mod + fa(k)*fb(n)%mod) %mod *(n+k)*100%mod) *pow(a+b,mod-2,mod) )%mod
print(res)

Measured memory_bytes: 44140
#include <stdio.h>
int main(){
	int a;
		scanf("%d",&a);	
	
		if(a/100==7||a%10==7||(a/10)%10==7){
			puts ("Yes\n");
		}
		else{
			puts ("No\n");
	
		}
	return 0;
}
	
	
	


Measured memory_bytes: 1596
import Data.List
 
wGcd x []=[]
wGcd [] x=[]
wGcd lx@(x:xs) ly@(y:ys)
  |elem x ly =x:wGcd xs (delete x ly)
  |elem y xs =y:wGcd (delete y xs) ys
  |otherwise =wGcd xs ys
 
output n a=do
  if(n==1) then putStr$sort a
              else do 
                b<-getLine
                output (n-1) (wGcd a b)
 
main=do
  n<-readLn
  a<-getLine
  output n a

Measured memory_bytes: 1020
#include <iostream>
#include <string>
 
int main(){
  int a, b, c, d;
  std::string s;
  std::cin >> s;
  a = s[0] - '0';
  b = s[1] - '0';
  c = s[2] - '0';
  d = s[3] - '0';
  
  std::string pm = "+-";
  int pmi[2] = {1, -1};
  
  for(int j = 0; j < 2; ++j)
  for(int k = 0; k < 2; ++k)
  for(int l = 0; l < 2; ++l){
   
  	const int sum = a + pmi[j]*b + pmi[k]*c + pmi[l]*d;
    
    if(sum == 7)
    {
       std::cout << a << pm[j] << b << pm[k] 
            << c << pm[l] << d << "=7" << std::endl;
       return 0;
    }
  }
  
  return 0;
}

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

using namespace std;

const int N=200005;

vector<int>e[N];
set<int>D[N];
bool in[N],vi[N];
int sg[N],sg2[N],n,p[N];

void dfs(int x){
	for(int v:e[x])if(!in[v])dfs(v),D[x].insert(sg[v]);
	while(D[x].count(sg[x]))sg[x]++;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&p[i]),e[p[i]].push_back(i);
	int x=1;
	while(!vi[x])vi[x]=true,x=p[x];
	in[x]=true;
	for(int y=p[x];y!=x;y=p[y])in[y]=true;
	for(int i=1;i<=n;i++)if(in[i]){
		dfs(i);
		sg2[i]=sg[i]+1;
		while(D[i].count(sg2[i]))sg2[i]++;
	}
	int cur=sg[x];
	for(int y=p[x];y!=x;y=p[y])if(cur==sg[y])cur=sg2[y];else cur=sg[y];
	if(cur!=sg[x])puts("POSSIBLE"),exit(0);
	cur=sg2[x];
	for(int y=p[x];y!=x;y=p[y])if(cur==sg[y])cur=sg2[y];else cur=sg[y];
	if(cur==sg[x])puts("POSSIBLE"),exit(0);
	puts("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 28672
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,i,s=0,m,mi=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>m;
        s+=m;
        if(m>mi)
            mi=m;
    }
    cout<<s-(mi/2)<<endl;
}


Measured memory_bytes: 256
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using INT=mp::cpp_int;
using namespace std;
using ll=long long;
using vec=vector<ll>;
using vect=vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n;i>=0;i--)
#define Pool(i, m, n) for(ll i=n;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout<<a<<endl
#define putout2(a,b) putout(a);putout(b)
#define putout3(a,b,c) putout(a);putout(b);putout(c)
#define putout4(a,b,c,d) putout(a);putout(b);putout(c);putout(d)
#define putout5(a,b,c,d,e) putout(a);putout(b);putout(c);putout(d);putout(e)
#define Gput(a,b) G[a].push_back(b)
#define cin1(a) cin>>a
#define cin2(a,b) cin>>a>>b
#define cin3(a,b,c) cin>>a>>b>>c
#define cin4(a,b,c,d) cin>>a>>b>>c>>d
#define cin5(a,b,c,d,e) cin>>a>>b>>c>>d>>e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x,y) __gcd(x,y)
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
ll lcm(ll x,ll y){
  ll z=gcd(x,y);
  return x*y/z;
}
INT LCM(INT x,INT y){
  INT z=gcd(x,y);
  return x*y/z;
}
ll primejudge(ll n){
  if(n<2)return 0;
  else if(n==2)return 1;
  else if(n%2==0)return 0;
  double sqrtn=sqrt(n);
  Loop(i,3,sqrtn+1){
     if(n%i==0){
        return 0;
     }
     i++;
  }
  return 1;
}
INT modinv(INT a, INT m) {
    INT b = m, u = 1, v = 0;
    while (b) {
        INT t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
int main() {
  cout << fixed << setprecision(30);
  ll x;
  cin>>x;
  ll ans;
  Loop(i,1,100000000000000){
    ll t=i*(i+1)/2;
    if(x-t<=0){
      ans=i;
      break;
    }
  }
  putout(ans);
}

Measured memory_bytes: 256
N,M = map(int,input().split())

a = [list(map(int,input().split())) for x in range(N)]
c = [list(map(int,input().split())) for x in range(M)]

min_cpoint = 0
num_stack = 100100100100100

for i in range(N):
    for j in range(M):
        if num_stack > abs(a[i][0]-c[j][0]) + abs(a[i][1]-c[j][1]):
            num_stack = abs(a[i][0]-c[j][0]) + abs(a[i][1]-c[j][1])
            min_cpoint = j+1
    print(min_cpoint)
    num_stack = 100100100100100


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

using ll=long long;
const ll MOD=1e9+7;

int main(){
  int N;
  cin >> N;
  ll ans=1;
  for(int i=1;i<=N;i++){
    ans=ans*i%MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
 
using namespace std;
int MOD = 1000000007;

signed main(){

    int n;
    cin >> n;
    map<int,int> a;
    rep(i,n){
        int val;
        cin >> val;
        a[val]++;
    }
    
    vector<int> p(1);
    p[0] = 1;
    rep(i,35)p.push_back(p[i]*2);

    int ans = 0;
    int cnt = 0;
    while(a.size()){
        auto maxi = a.end();
        maxi--;
        auto itr1 = lower_bound(p.begin(),p.end(),maxi->fi+1);
        auto itr2 = a.find(*itr1-maxi->fi);
        if(itr2 != a.end()){
            if(itr2 == maxi){
                if((maxi->se) < 2)a.erase(maxi);
                else{
                    (maxi->se) -= 2;
                    ans++;
                    if((maxi->se) == 0)a.erase(maxi);
                }
            }else{
                (itr2->se)--;
                (maxi->se)--;
                ans++;
                if((itr2->se) == 0)a.erase(itr2);
                if((maxi->se) == 0)a.erase(maxi);
            }
        }else{
            a.erase(maxi);
        }
        cnt++;
    }
    cout << ans << endl;
    
    return 0;   
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://agc029.contest.atcoder.jp/tasks/agc029_b
// rm -r -f test;oj dl http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_c

Measured memory_bytes: 12800
#include <stdio.h>

int A[100005];

int main(){

	int N,K;

	scanf("%d %d",&N,&K);

	int i;

	for(i=1;i<=N;i++){
	scanf(" %d",&A[i]);
	}

	int ans=0;

	int diff=N-1;
	while(1){
		if(diff<=0){break;}
		diff-=K-1;
		ans++;
	}
	printf("%d\n",ans);

return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <string.h>
void Search(double n);
void Answer(void);
int A[10]={0};
int main(void) {

	int i,m,n;
	char str[100];

	for( ; ; ){
		fgets(str,sizeof(str),stdin);
		sscanf(str,"%d",&m);
			if(!m) break;
		for(i=0;i<m;i++){
			fgets(str,sizeof(str),stdin);
			sscanf(str,"%d",&n);
			Search(n);	
		}
		Answer();
	}		
	return 0;
}

void Answer(void){
	int i;
	for(i=1;i<=7;i++){
		printf("%d\n",A[i]);
		A[i]=0;
	}
}		
void Search(double n){
	if(10>n)               A[1]+=1;
	else if(10<=n && n<20) A[2]+=1;
	else if(20<=n && n<30) A[3]+=1;
	else if(30<=n && n<40) A[4]+=1;
	else if(40<=n && n<50) A[5]+=1;
	else if(50<=n && n<60) A[6]+=1;
	else if(60<=n)         A[7]+=1;
}

Measured memory_bytes: 612
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
ans = [pow(i,2) for i in range(100000) if pow(i,2)<=N]
print(ans[-1])

Measured memory_bytes: 13264
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class union_find
{
	int  _setnum;
	vector<int> par, nume;
public:
	union_find(){
	}
	
	union_find(int x){
		par.resize(x);
		nume.resize(x);
		init();
	}
	
	~union_find(){
		//
		
	}
	
	void clear(){
		_setnum = 0;
		par.clear();
		nume.clear();
	}
	
	void init(){
		_setnum = par.size();
		for(int i = 0; i < par.size(); i++){
			par[i] = i;
			nume[i] = 1;
		}
	}
	
	void resize(int x){
		
		par.resize(x);
		nume.resize(x);
		init();
	}

	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
	
		if(x == y)return;
		
		_setnum--;
		
		if(nume[x] > nume[y]) std::swap(x,y);
		
		par[x] = y;
		nume[y] += nume[x];
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
	
	int numel(int x){
		return nume[find(x)];
	}
	
	int size(){
		return par.size();
	}
	
	int setnum(){
		return _setnum;
	}
};

int kruskal(vector<pair<int,pair<int,int>>>& edge, int V){
	union_find uf(V);
	int res = 0, count = 0;
	
	sort(edge.begin(), edge.end());
	
	for(int i = 0; i < edge.size(); i++){
		if(!uf.same(edge[i].second.first, edge[i].second.second)){
			uf.unite(edge[i].second.first, edge[i].second.second);
			res += edge[i].first;
			count++;
		}
	}
	
	if(count == V-1) return res;
	return -1;
}

int main(){
	vector<pair<int,pair<int,int>>> edge;
	int V, E;
	
	cin>>V>>E;
	
	edge.resize(E);
	
	for(int i = 0; i < E; i++){
		cin>>edge[i].second.first>>edge[i].second.second>>edge[i].first;
	}
	
	cout<<kruskal(edge, V)<<endl;
	
	return 0;
}


Measured memory_bytes: 4088
#include<cstdio>
using namespace std;
const int N=2e5+5;
int n,q,Ans[N];
int tal,Hed[N],Too[N*2],Nxt[N*2];
void AE(int u,int v){
	Nxt[++tal]=Hed[u];
	Too[tal]=v,Hed[u]=tal;
}
void DFS(int u,int fa){
	for(int i=Hed[u];i;i=Nxt[i]){
		int v=Too[i];
		if(v==fa)continue;
		Ans[v]+=Ans[u];
		DFS(v,u);
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		AE(u,v),AE(v,u);
	}
	for(int i=1,p,x;i<=q;++i){
		scanf("%d%d",&p,&x);
		Ans[p]+=x;
	}
	DFS(1,0);
	for(int i=1;i<=n;++i)printf("%d ",Ans[i]);
}

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

const int mod = 1e9 + 7;
int cnt(int mask)
{
  int ret = 0;
  while (mask)
  {
    ret += mask&1;
    mask >>= 1;
  }
  return ret;
}

bool set(int mask, int idx)
{
  return (mask >> idx) & 1;
}

void add(int& x, int y)
{
  long long res = x + y;
  if (res >= mod)
    res -= mod;
  x = res;
}


/*
int f(int idx, int mask)
{
  for (int j = 0; j < n; ++j) {
    if (match[idx][j] and !set(mask, j)) {
      ret += f(idx + 1, mask | (1 << j));
    }
  }
}

*/


int main()
{
  int n, k;
  cin >> n ;
  vector<vector<int>> dp(n + 1, vector<int>(1 << n));
  vector<vector<bool>> match(n, vector<bool>(n));
  bool x;
  for(int i = 0; i < n; ++i)
   for (int j = 0; j < n; ++j) {
     cin >> x;
     match[i][j] = x;
   }

  vector<vector<int>> masks(n + 1);
  for (int i = 0; i < (1 << n); ++i)
  {
    auto c = cnt(i);
    masks[c].push_back(i);
  }

    //cin >> match[i][j];
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
   for (auto mask : masks[i])
   {
     for (int j = 0; j < n; ++j) {
       if (match[i][j] and !set(mask, j)) {
         add(dp[i + 1][mask | 1 << j], dp[i][mask]);
       }
     }
   }
  }

   cout << dp[n][(1 << n) - 1] << '\n';


  return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i = 0; i < n; i++) {
    cin >> v[i];
  }
  int ans = 1, flg = 0;
  for(int i = 1; i < n; i++) {
    if (v[i] - v[i-1] < 0 && flg > 0) {
      flg = 0;
      ans++;
    } else if (v[i] - v[i-1] > 0 && flg < 0) {
      flg = 0;
      ans++;
    } else if (v[i] - v[i-1] < 0) {
      flg = -1;
    } else if (v[i] - v[i-1] > 0) {
      flg = 1;
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define vpp vector<pair<int,int>>
#define ll long long int
#define ull unsigned long long
#define ld long double
#define fi(i,a,b) for(ll i=a;i<b;i++)
#define fj(j,a,b) for(ll j=a;j<b;j++)
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define mpi map<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define mpl map<ll,ll>
#define pb push_back
#define MOD 1000000007
#define ub upper_bound
#define lb lower_bound
#define itr(v) for(auto it:v)
#define all(v) v.begin(),v.end()  
#define w(t)  int t; cin>>t; while(t--)
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fast_pow(ll k, ll p)
{
if (p == 0)
        return 1;
 
    ll P = fast_pow(k, p/2);
    P = (P * P) % MOD;
 
    if (p % 2 == 1)
        P = (P * k) % MOD;
 
    return P;
}
ll invmod(ll a,ll m)
{
    return fast_pow(a,m-2);
}

bool isPrime(ll n) 
{ 
   
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
  
       if (n % 2 == 0 || n % 3 == 0) 
        return false; 
  
    for (int i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
  
    return true; 
} 
ll nextPowerOf2(ll n)
{
    n>>=1;
    ll count = 0;

    if (n && !(n & (n - 1)))
        return n;

    while( n != 0)
    {
        n >>= 1;
        count += 1;
    }

    return 1 << count;
}

ll binomialCoeff(ll n, ll k) 
{ 
    ll C[k+1]; 
    memset(C, 0, sizeof(C)); 
    C[0] = 1;
  
    for (ll i = 1; i <= n; i++) 
    {
        for (ll j = min(i, k); j > 0; j--) 
            C[j] = C[j] + C[j-1]; 
    } 
    return C[k]; 
} 


//////////////////////*********CODE***********/////////////////////
int main(){
    int n;
    cin>>n;
    if(n>=30){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3596
fun main(args: Array<String>) {
    val s = readLine()?.toLong() ?: return
    val sList = mutableListOf<Long>()
    var tmp = s
    while (tmp > 0) {
        sList += (tmp % 10)
        tmp /= 10
    }

    sList.reverse()

    var total = 0L

    for (flg in 0 until Math.pow(2.0, sList.size - 1.0).toInt()) {
        val numList = mutableListOf<Long>()
        var currentNum = 0L
        for (i in 0 until sList.size) {
            currentNum *= 10
            currentNum += sList[i]
            if (flg.and(1 shl i) != 0) {
                numList += currentNum
                currentNum = 0
            }
        }
        numList += currentNum
        total += numList.sum()
    }
    println(total)
}

Measured memory_bytes: 33700
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using M = map<int, int>;
ll INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  ll sum = accumulate(a.begin(), a.end(), 0);

  bitset<(ll)5e6> dp;
  dp[0] = 1;
  rep(i, n) {
    dp |= (dp << a[i]);
  }

  long long res;
  for (res = (sum+1)/2; res < sum+1; ++res) {
      if (dp[res]) break;
  }
  cout << res << endl;
/*
  repI(i, int(sum/2), sum+1) {
    if (dp[i]) {
      cout << i << endl;
      break;
    }
  }
  */

  return 0;
}


Measured memory_bytes: 2048
use std::io;
use std::str::FromStr;

fn input_tuple() -> (u64, u64, u64) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<u64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1], vec[2])
}

fn main() {
    let (x, y, z) = input_tuple();
    println!("{} {} {}", z, x, y);
}


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

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< ll, ll >   cp2;
typedef pair< string, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789


///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////

int N, M;
int a,b;
bool p[10][10];
bool f[10];
int ans = 0;

void dfs( int v ){
    f[v] = true;
    bool flag = true;
    REP( i, N ) if( !f[i] ) flag = false;
    if( flag ){
        ans++;
        f[v] = false;
        return;
    }
    FOR( i, 1, N ){
        if( f[i] ) continue;
        if( p[v][i] ){
            dfs( i );
        }
    }
    f[v] = false;
    return;
}


int main(){
    
    fill( &p[0][0], &p[10][0], false );
    fill( f, f+10, false );
    
    cin>>N>>M;
    REP(i,M){
        cin>>a>>b;
        a--;
        b--;
        p[a][b] = true;
        p[b][a] = true;
    }
    
    dfs( 0 );
    
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 3192
#include<iostream>
using namespace std;
int  main()
{
	int a,b,c,x,t=0;
	cin>>a>>b>>c>>x;
	x/=50;
	for(int i=0;i<=a;i++)
	{
		for(int j=0;j<=b;j++)
		{
			for(int k=0;k<=c;k++)
			{
				if(10*i+2*j+k==x)
				{
					t++;
				}
			}
		}
	}
	cout<<t<<endl;
	return 0;
} 

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

int main(){
	string a, b;
	cin >> a >> b;
	
	int an = stoi(a);
	int bn = stoi(b);
	
	string as, bs;
	for(int i=0; i<bn; i++){
		as += a;
	}
	for(int i=0; i<an; i++){
		bs += b;
	}
	
	if(as < bs) cout << as << endl;
	else cout << bs << endl;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

bool isParallel(Vec2 a, Vec2 b, Vec2 c, Vec2 d) {
    auto ab = b - a;
    auto cd = d - c;
    return ab.cross(cd) == 0;
}

bool isOrthogonal(Vec2 a, Vec2 b, Vec2 c, Vec2 d) {
    auto ab = b - a;
    auto cd = d - c;
    return ab.dot(cd) == 0;
}

int calc(Vec2 a, Vec2 b, Vec2 c, Vec2 d) {
    if (isParallel(a, b, c, d))
        return 2;
    if (isOrthogonal(a, b, c, d))
        return 1;

    return 0;
}

void main() {
    int n = readint();
    for (int i = 0; i < n; i++) {
        auto ps = readints();
        auto a = Vec2(ps[0], ps[1]);
        auto b = Vec2(ps[2], ps[3]);
        auto c = Vec2(ps[4], ps[5]);
        auto d = Vec2(ps[6], ps[7]);

        writeln(calc(a, b, c, d));
    }
}

struct Vec2 {
    immutable double x;
    immutable double y;

    this(double x, double y) {
        this.x = x;
        this.y = y;
    }

    Vec2 opAdd(Vec2 other) {
        return Vec2(this.x + other.x, this.y + other.y);
    }

    Vec2 opSub(Vec2 other) {
        return Vec2(this.x - other.x, this.y - other.y);
    }

    Vec2 opMul(double d) {
        return Vec2(this.x * d, this.y * d);
    }

    double dot(Vec2 other) {
        return this.x * other.x + this.y * other.y;
    }

    double cross(Vec2 other) {
        return this.x * other.y - other.x * this.y;
    }

    double mag() {
        return sqrt(magSq());
    }

    double magSq() {
        return this.x * this.x + this.y * this.y;
    }

    Vec2 normalize() {
        auto m = mag();
        if (m != 0 && m != 1)
            return Vec2(this.x / m, this.y / m);
        return this;
    }

    static double distance(Vec2 a, Vec2 b) {
        return (a - b).mag();
    }
}

Measured memory_bytes: 2952
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count = 0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      if 500*a + 100*b + 50*c == X:
        count += 1
print(count)

Measured memory_bytes: 3060
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<iostream>
#include<algorithm>//next_permutation

using namespace std;
int main() {
	int N;
	cin >> N;
	vector<string>s(N);
	vector<int>t(N);
	for (int i = 0;i < N;i++) {
		cin >> s.at(i) >> t.at(i);
	}
	string X;
	cin >> X;
	bool F = false;
	int answer = 0;
	for (int i = 0;i < N;i++) {
		if (F) {
			answer += t.at(i);
		}

		if (s.at(i) == X && F == false) {
			F = true;
		}
	}
	cout << answer << endl;
}


Measured memory_bytes: 256
s=int(input())
S=str(s)
w=len(str(s))-1
l=[]
L=[]
if w==0:
    print(s)
else:
    for i in range(2**w):
        l.append(format(i, '0{}b'.format(w)))
    for e in l:
        q=[]
        x=int(S[0])
        for i in range(len(e)):
            if e[i]=='0':
                x=x*10+int(S[i+1])
            else:
                q.append(x)
                x=int(S[i+1])
        q.append(x)
        L.append(sum(q))
    print(sum(L))

Measured memory_bytes: 3064