akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  int K, S;
  cin >> K >> S;
  int co = 0;
  rep(i, K) {
    rep(j, K) {
      if(max(0, S - K) <= i + j && i + j <= S) {
        co++;
      }
    }
  }
  cout << co << endl;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int suf[100005][26];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s,t;
    cin>>s>>t;
    int n=s.size();
    bool h[26];
    memset(h,false,sizeof(h));
    memset(suf,-1,sizeof(suf));
    for(int i=0;i<n;i++){
        suf[i][s[i]-'a']=i;
        h[s[i]-'a']= true;
    }
    long long int curr;
    for(int j=0;j<26;j++){
        curr=-1;
        for(int i=n-1;i>=0;i--){
            if(suf[i][j]!=-1) curr=suf[i][j];
            else suf[i][j]=curr;
        }
    }
    int flag=0;
    long long int ans=0;
    curr=0;
    int temp,minusflag=0;
    for(int i=0;i<t.size();i++){
        minusflag=0;
        if(h[t[i]-'a']==false){
            flag=1;
            break;
        }
        temp=suf[curr][t[i]-'a'];
        if(temp==-1){
            ans+=n;
            curr=(suf[0][t[i]-'a']+1)%n;
        }
        else{
            if(temp==n-1){
                ans+=n;
                minusflag=-1;
            }
            curr=(temp+1)%n;
            
        }
    }
    if(flag==0){
        cout<<(long long int)curr+ans<<"\n";
    }
    else cout<<"-1\n";
}



Measured memory_bytes: 10704
using System;

class Program{
    class Node{
        public int parent;
        public int sibling;
        public int degree;
        public int depth;
        public int height;
        public string type;
        public int left;
        public int right;
    }

    static void CalcDepth(Node[] nodes, int idx, int depth){
        nodes[idx].depth=depth;
        if(nodes[idx].left!=-1){
            CalcDepth(nodes, nodes[idx].left, depth+1);
        }
        if(nodes[idx].right!=-1){
            CalcDepth(nodes, nodes[idx].right, depth+1);
        }
    }

    static void CalcHeight(Node[] nodes, int idx){
        var maxHeight=-1;
        if(nodes[idx].left!=-1){
            CalcHeight(nodes, nodes[idx].left);
            if(nodes[nodes[idx].left].height>maxHeight){
                maxHeight=nodes[nodes[idx].left].height;
            }
        }
        if(nodes[idx].right!=-1){
            CalcHeight(nodes, nodes[idx].right);
            if(nodes[nodes[idx].right].height>maxHeight){
                maxHeight=nodes[nodes[idx].right].height;
            }
        }
        nodes[idx].height=maxHeight+1;
    }

    public static void Main(){
        var n=int.Parse(Console.ReadLine());
        var nodes=new Node[n];
        for(var i=0; i<n; i++){
            nodes[i]=new Node();
            nodes[i].parent=-1;
            nodes[i].sibling=-1;
        }
        for(var i=0; i<n; i++){
            var s=Console.ReadLine().Split(' ');
            var id=int.Parse(s[0]);
            var left=int.Parse(s[1]);
            var right=int.Parse(s[2]);
            nodes[id].left=left;
            nodes[id].right=right;
            nodes[id].degree=Convert.ToInt32(left!=-1)+Convert.ToInt32(right!=-1);
            if(nodes[id].degree>0){
                nodes[id].type="internal node";
            } else{
                nodes[id].type="leaf";
            }
            if(nodes[id].left!=-1){
                nodes[nodes[id].left].parent=id;
                nodes[nodes[id].left].sibling=right;
            }
            if(nodes[id].right!=-1){
                nodes[nodes[id].right].parent=id;
                nodes[nodes[id].right].sibling=left;
            }
        }

        for(var i=0; i<n; i++){
            if(nodes[i].parent==-1){
                CalcDepth(nodes, i, 0);
                CalcHeight(nodes, i);
                nodes[i].type="root";
            }
        }

        var sout=new System.Text.StringBuilder();
        for(var i=0; i<n; i++){
            sout.Append("node "+i+": parent = "+nodes[i].parent+", ");
            sout.Append("sibling = "+nodes[i].sibling+", ");
            sout.Append("degree = "+nodes[i].degree+", ");
            sout.Append("depth = "+nodes[i].depth+", ");
            sout.Append("height = "+nodes[i].height+", ");
            sout.Append(nodes[i].type);
            sout.Append("\n");
        }
        Console.Write(sout);
    }
}

Measured memory_bytes: 9276
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define INF 1e8
typedef long long int ll;
const double PI = acos(-1);

using Graph = vector<vector<int>>;
int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (ll i = 0; i < n; ++i) cin >> a[i];
  ll ans = 0;
  ll h = a[0];
  for (ll i = 1; i < n; i++) {
    if (a[i] < h) {
      ans += h - a[i];
    } else
      h = a[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 4760
from collections import Counter

n = int(input())
ns = list(map(int, input().split()))
C = Counter(ns)
s = sum(key * value for key, value in C.items())
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s += (c - b) * C[b]
    C[c] += C[b]
    C[b] = 0
    print(s)

Measured memory_bytes: 90484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int main() {
    int n;
    cin >> n;
    string w[n];
    for (int i = 0; i < n; i++) cin >> w[i];
    string used[n], ans = "Yes";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (w[i] == used[j]) {
                ans = "No";
                break;
            }
        }
        if (i > 0) {
            if (w[i][0] != w[i-1][w[i-1].size()-1]) {
                ans = "No";
                break;
            }
        }
        used[i] = w[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){

	int x, y, z,l=0;
	cin >> x >> y >> z;
	l = x;

	for (int i = 0; i < x; i++){
		l -= y;
		l -= z;

		if (l < z){
			cout << i << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int comp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

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

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;
const long double EPS = 1e-10;
const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

class UnionFind {
    public:
    int n;
    vector<int> par, rank,size;  //親, 深さ, その木の要素数

    UnionFind(int n){
        this->n = n;
        for(int i=0;i<n;++i){
            par.push_back(i);
            rank.push_back(0);
            size.push_back(1);
        }
    }

    //根を求める
    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            int p = find(par[x]);
            size[x] = size[p];
            return par[x] = p;
        }
    }

    //xとyの属する集合の併合
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        
        size[x] += size[y];
        size[y] = size[x];
        if(rank[x] < rank[y]){
            par[x] = y;
        }else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    //同じ集合に属するか否か
    bool is_same(int x, int y){
        return find(x) == find(y);
    }
};

int main() {
    ll n, m;
    cin >> n >> m;
    UnionFind uf = UnionFind(n+1);
    
    vector<Pii> bridges(m);
    for(int i=0;i<m;++i) {
        cin >> bridges[i].first >> bridges[i].second;
    }

    vector<ll> ans(m, n*(n-1)/2);
    for(int i=m-1;i>0;--i) {
        bool united = uf.is_same(bridges[i].first, bridges[i].second);
        if(!united) {
            Pll old_size = {uf.size[uf.find(bridges[i].first)], uf.size[uf.find(bridges[i].second)]};
            uf.unite(bridges[i].first, bridges[i].second);
            ll new_size = uf.size[uf.find(bridges[i].first)];
            ans[i-1] = ans[i] + old_size.first * (old_size.first-1) / 2 + old_size.second * (old_size.second-1) / 2 - new_size * (new_size-1) / 2;
        } else {
            ans[i-1] = ans[i];
        }
    }

    for(int i=0;i<m;++i) cout << ans[i] << endl;
}


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

typedef long long ll;

int main() {
    int N;cin>>N;
    vector<ll> a(N),b(N);
    rep(i,N)cin>>a[i];
    rep(i,N)cin>>b[i];
    ll cnt = 0;
    rep(i,N){
        //包容力が貯まる
        if(a[i]<=b[i]){
            if((b[i]-a[i])%2 == 0){
                cnt += (b[i]-a[i])/2;
            }
            else{
                cnt += (b[i]-a[i]-1)/2;
            }
        }
        //包容力が使われる
        else{
            cnt-=a[i]-b[i];
        }
    }
    cerr<<cnt<<endl;
    bool flag = (cnt>=0);
    cout<<(flag? "Yes": "No")<<endl;
}

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

int main() {
  int N,K;
  cin >> N >> K;
  vector<int> x(N);
  
  for(int i=0; i<N; i++)cin >> x.at(i);
  
  int64_t minimum = 10000000000;
  for(int i=0; i+K-1<N; i++){
    int left =i, right =i+K-1;
    int64_t far = 10000000000;
    
    if(x.at(left)>=0){
      far = x.at(right);
    }else if(x.at(right)<=0){
      far = -1*x.at(left);
    }else{
      far = x.at(right) + -1*x.at(left) + min(x.at(right),-1*x.at(left));
    }
    
    minimum = min(minimum, far); 
  }
  cout << minimum << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a,b) memset(a,b,sizeof (a))
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll ksm(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main(){
	string a;
	cin>>a;
	if(a=="ARC"){
		printf("ABC");
	}
	else{
		printf("ARC");
	}
    return 0;
}


Measured memory_bytes: 3720
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

#define FAST   ios_base :: sync_with_stdio(false); cin.tie(NULL); 
#define endl   "\n"

typedef long long int  ll;


int main()
{
	FAST;
	string str;
	cin >> str;

	int maxCount = 0;
	int count = 0;
	for(int i=0 ; i<str.size() ; i++)
	{
		if(str[i] == 'A' || str[i] == 'C' || str[i] == 'G' || str[i] == 'T')
			count++;
		else
		{
			maxCount = max(maxCount , count);
			count = 0;
		}
	}
	maxCount = max(maxCount , count);
	cout << maxCount;
	return 0;
}

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

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int num=1e9+7;
int main(){
    int a,b,x;
    cin >> a >> b >> x;
    double pi=3.14159265358979323;
    double s=(double)x/a;
    if((double)a*a*b/2>=x){
        double c=2*s/b;
        cout << fixed<< setprecision(10) << 90-(double)asin(2*s/(b*sqrt(b*b+c*c)))/pi*180;
    }
    else{
        double c=2*s/a-b;
        double ans=atan((b-c)/a);
        cout << fixed << setprecision(10) << ans/pi*180;
    }
    cout << endl;
}

Measured memory_bytes: 384
'use strict'

const main = (input) => {
    input = input.split(' ').map(i => parseInt(i))
    let c5 = 0
    let c7 = 0
    input.forEach(i => {
        if(i === 5){
            c5++
        }else{
            c7++
        }
    })
    if(c5 === 2 && c7 === 1){
        console.log('YES')
    }else{
        console.log('NO')
    }
}

main(require('fs').readFileSync('/dev/stdin', 'utf-8'))

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

int main() {
	int n, x;
	cin >> n >> x;
	while (n != 0 || x != 0) {
		int c = 0;
		for (int i = 1; i <= n - 2; i++){
			for (int j = i + 1; j <= n - 1; j++){
				for (int k = j + 1; k <= n; k++){
					if (i + j + k == x)
						c = c + 1;
				}
			}
		}
		cout << c << endl;
		cin >> n >> x;
	}
	return 0;
}


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

int main() {
	double a,b,h,m,c,d,e,f,g;
	cin >> a >> b >> h >> m;
	c = 30*h+(m/2);
	d = 6*m;
	e = max(c-d,d-c);
	if(e>180){
		e=360-e;
	}
	f = e/180*3.141592653589793238;
	g = a*a+(b*b)-2*a*b*cos(f);
	cout << setprecision(10) << sqrt(g) << endl;

}



Measured memory_bytes: 4160
#include <iostream>

using namespace std;

int main()
{
        int S,h,m,s;

        cin>>S;

        h = S / 3600;
        m = (S - h*3600)/60;
        s = (S - h*3600)%60;

        cout<<h<<':'<<m<<':'<<s<<'\n';
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
typedef vector<bool> vb;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}
ll llpow(ll e,ll x){ll res=1LL;while(x){if(x&1)res*=e;e*=e;x/=2;}return res;}
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007 //998244353

ll gcd(ll A, ll B){
    if(A<B) swap(A,B);
    while(B){
        ll w = A%B;
        A = B;
        B = w;
    }
    return A;
}

ll lcm(ll A, ll B){return A/gcd(A,B)*B;}

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

    // solution comes here

    ll N;
    cin >> N;
    vl T(N);
    rep(i, N) cin >> T[i];

    if(1==N) {
        cout << T[0] << nl;
        return 0;
    }

    ll ans = lcm(T[0], T[1]);
    rep(i, N-2) ans = lcm(ans, T[i+2]);
    cout << ans << nl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>

using namespace std;

int main(){
    double w,h,x,y;
    cin >> w >> h >> x >> y;

    int c;
    if(w == 2*x && h ==2*y) c=1;
    else c=0;
    cout << w * h /2 ;
    cout << setw(2)<< c <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)
// ----------------------------------------------------------------------

// ----------------------------------------------------------------------
int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N; cin >> N;
  ll answer = 0;
  int level = 0;
  for (int i = 0; i < N; i++) {
    int a; cin >> a;
    if (i == 0) {
      answer = a - 1;
      level = 1;
      continue;
    }
    if (a <= level) continue;
    if (a == level + 1) {
      level = a;
      continue;
    }
    answer += (a - 1) / (level + 1);
  }
  cout << answer << endl;

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
ll N, K;
ll a[100000];
vector<int> E[100000];
int h[100000];
ll ans=0;
void dfs(int x){
    if(sz(E[x])==0){
        h[x]=0;
        return;
    }
    for(auto i: E[x]){
        dfs(i);
        if(h[i]==K-1&&x!=0){
            ans++;
            h[i]=-1;
        }
    }
    for(auto i: E[x]){
        h[x]=max(h[x], h[i]+1);
    }
    if(h[x]==K&&x!=0){
        ans++;
        h[x]=0;
    }
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>K;
    rep(i,0,N){
        cin>>a[i];
        if(i>0){
            E[a[i]-1].pb(i);
        }
    }
    if(a[0]!=1) ans++;
    rep(i,0,N) h[i]=-2;
    dfs(0);
    cout <<ans<<"\n";
}

Measured memory_bytes: 14848
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << endl;
#else
	#define DBG(X)
	#define endl '\n'
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const ll mod = 1e9 + 7;
const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }

const int MAX_N = 2007;

int a[MAX_N], n;
ll k;

void solve()
{
	cin >> n >> k;

	for(int i = 0; i < n; ++i)
		cin >> a[i];

	ll cnt1 = 0, cnt2 = 0;

	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < i; ++j)
			cnt1 += (a[j] > a[i]);		

		for(int j = 0; j < n; ++j)
			cnt2 += (a[j] > a[i]);
	}

	ll answ = k * cnt1 + (((k * (k - 1)) / 2) % mod) * cnt2;
	cout << answ % mod << endl;
}

int main()
{
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

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


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

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

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;

int main () {
	SpeedForce;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (int i = 2; i < n; i ++) {
		vector < int > w;
		w.pb(a[i-1]);
		w.pb(a[i+1]);
		w.pb(a[i]);
		sort(every(w));
		if (w[1] == a[i]) ans ++;
	}

	cout << ans << '\n';

	return Accepted;
}

// B...a

Measured memory_bytes: 18688
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;

public class Main
{
    int n, m;
    String a[] = new String[51];
    String b[] = new String[51];
    
    public static void main(String args[])
    {
	new Main().solve();
    }
    
    void solve()
    {
	in();

	boolean flg = false;
	
	for(int i = 0; i <= n - m; i++) {
	    for(int j = 0; j <= n - m; j++) {

		boolean sflg = true;

		for(int k = 0; k < m; k++) {
		    String line = a[i + k].substring(j, j + m);
		    if(!b[k].equals(line)) sflg = false;
		}

		if(sflg) flg = true;
		
	    }
	}
	
	if(flg) out("Yes");
	else    out("No");
    }

    void in()
    {
	Scanner sc = new Scanner(System.in);
	n = sc.nextInt();
	m = sc.nextInt();
	for(int i = 0; i < n; i++) a[i] = sc.next();
	for(int i = 0; i < m; i++) b[i] = sc.next();
    }

    void out()
    {
	
    }
    
    void out(int n)
    {
	System.out.println(n);
    }

    void out(char c)
    {
	System.out.print(c);
    }
    
    void out(String s)
    {
	System.out.println(s);
    }
}


Measured memory_bytes: 22612
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
int main(){
	std::ios::sync_with_stdio(false);
	string s;
	int w;
	cin>>s>>w;
	int i=0;
	while(i<s.length()){
		cout<<s[i];
		i+=w;
	}	
} 
	

Measured memory_bytes: 256
/*** 𝕒𝕜𝕤𝕙𝕒𝕪𝕜𝕦𝕞𝕒𝕣𝟡𝟡 ***/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
 
#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD=1e9+7;
const long double PI = acos(-1);
const long long INF=INT_MAX;
const long long LINF=LLONG_MAX;
const long long N=1e6+1;
 
typedef long long ll;
typedef long double ld;

void test_case()
{
    string s;
    cin>>s;
    if(s[0]=='7'|| s[1]=='7' || s[2]=='7')
        cout<<"Yes\n";
    else
        cout<<"No\n";

}

int main()
{
    IOS();
   
    int tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}

Measured memory_bytes: 3648
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
using namespace std;

#define INF 1e9
#define rep(i,j,n) for(int (i)=(j);(i)<(n);(i)++)
#define rep2(i,j,n) for(int (i)=(j);(i)<=(n);(i)++)
#define all(i) (i).begin(),(i).end()
#define rall(i) (i).rbegin(),(i).rend()

typedef long long i64;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<vs> vvs;

int main(){
  string s;
  cin>>s;
  cout<<s[0]<<s.size()-2<<s[s.size()-1]<<endl;
}


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

using namespace std;

int main() {
  string s;
  long long k;
  cin >> s >> k;
  char ans;
  for(int i = 0; i <= k-1; i++) {
    if(s[i] == '1') {
      ans = '1';
      continue;
    }else {
      ans = s[i];
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
h, w, k = map(int, input().split())
c = []
a = 0


ww = []
hh = []
def count(c, hh, ww):
    ans = 0
    for i in range(h):
        for j in range(w):
            if not i in hh:
                if not j in ww:
                    if c[i][j]=="#":
                        ans+=1
    return ans
            
for _ in range(h):
    c.append(input())

for i in range(2**h):
    for j in range(2**w):
        cc = c
        hh = []
        ww = []
        for x in range(h):#行
            if ((i>>x)&1):
                hh.append(x)
        for y in range(w):
            if ((j>>y)&1):
                ww.append(y)
        if count(cc, hh, ww)==k:
            a += 1
print(a)

Measured memory_bytes: 68744
SA = list(input())
SB = list(input())
SC = list(input())

x = 'a'

while True:
    if x == 'a':
        if len(SA)==0:
            print('A')
            exit()
        x = SA[0]
        SA.remove(x)
    if x == 'b':
        if len(SB)==0:
            print('B')
            exit()
        x = SB[0]
        SB.remove(x)
    if x == 'c':
        if len(SC)==0:
            print('C')
            exit()
        x = SC[0]
        SC.remove(x)



Measured memory_bytes: 9056
"use strict"
function main(arg) {
    var text = arg.trim().split("\n")[1].split(" ")
    var result = ""
    for (var i = 0; i < text[0].length; i++) {
        result += text[0][i] + text[1][i]
    }
    console.log(result)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using ll = long long;
using namespace std;
typedef unsigned long long ull;
typedef pair<ll, ll>P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
string abc = "abcdefghijklmnopqrstuvwxyz";
struct edge { ll to, cost; };
struct etree { ll from, to, cost; };
struct people { ll v, k, year; };
bool comp(const etree& e1, const etree& e2) {
	return e1.cost < e2.cost;
}
bool comp2(const people& e1, const people& e2) {
	return e1.year < e2.year;
}
#define ALL(x) (x).begin(),(x).end()

ll FACT[101100] = { 0 }, IFACT[101100] = { 0 };
ll extgcd(ll a, ll b, ll &x, ll &y) {
	ll g = a;
	x = 1;
	y = 0;
	if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
	return g;
}
ll invMod(ll a, ll m) {
	ll x, y;
	if (extgcd(a, m, x, y) == 1) return (x + m) % m;
	else                         return 0;
}
ll mpow(ll a, ll n) {
	if (n == 0) return 1;
	if (n % 2 == 0) {
		ll d = mpow(a, n / 2);
		return d * d % MOD;
	}
	return a * mpow(a, n - 1) % MOD;
}
void inverse(ll N) {
	FACT[0] = 1;
	IFACT[0] = 1;
	for (int i = 1;i <= N;i++) {
		FACT[i] = FACT[i - 1] * i % MOD;
		IFACT[i] = invMod(FACT[i], MOD);
	}
}
ll combi(ll n, ll r) {
	if (n < 0 || r < 0 || r > n)return 0;
	if (r > n / 2)r = n - r;
	return FACT[n] * IFACT[n - r] % MOD*IFACT[r] % MOD;
}


int main() {
	ll n, a[101100], cou[101100], itl, itr;
	cin >> n;
	for (int i = 1;i <= n + 1;i++) {
		cin >> a[i];
		if (cou[a[i]] == 0)cou[a[i]]++;
		else itr = i;
	}
	for (int i = 1;i <= n;i++) {
		if (a[i] == a[itr]) {
			itl = i;
			break;
		}
	}
	inverse(n + 2);
	for (int i = 1;i <= n + 1;i++) {
		cout << (MOD + combi(n + 1, i) - combi(itl + n - itr, i - 1)) % MOD << endl;
	}
}

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

int main(){
  string s;
  cin >>s;
  int count =0;
  if(s[0]=='1') ++count;
  if(s[1]=='1') ++count;
  if(s[2]=='1') ++count;

  cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <sstream>
#include <istream>
#include <iomanip>
#include <typeinfo>
#include <stack>
#include <queue>
#include <functional> 

using namespace std;
typedef long long ll;

int main(){

    ll N, K;
    cin >> N >> K;


    vector<ll > V(N, 0);
    for(ll i = 0; i < N; i++){
        cin >> V[i];
    }

    ll ans = 0;
    for(ll l = 0; l <= min(K, N); l++){
        for(ll r = 0; l + r <= min(K, N); r++){
            //ぷらいおりてぃきゅー
            //昇順
            priority_queue<ll, vector<ll >, greater<ll > > que;
            ll sum = 0;
            for (ll i = 0; i < l; i++){
                que.push(V[i]);
                sum += V[i];
            }
            for(ll i = 0; i < r; i++){
                que.push(V[N-i-1]);
                sum += V[N-i-1];
            }
            //マイナスの価値の宝石を消す
            for(ll i = 0; i < K - l - r; i++){
                if(que.empty()) break;
                if(que.top() > 0) break;
                if(que.top() < 0){
                    sum -= que.top();
                    que.pop();
                }
            }
            ans = max(ans, sum);
        }
    }

    cout << ans << endl;

} 

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
const int MAX=1e5+5;

int N,M;
vi G[MAX];

int col[MAX];
bool dfs(int v,int c){
	col[v]=c;
	rep(i,sz(G[v])){
		if(col[G[v][i]]==c)return false;
		if(col[G[v][i]]==0 && !dfs(G[v][i],-c))return false;
	}
	return true;
}

int main(){
	cin>>N>>M;
	rep(i,M){
		int a,b;
		cin>>a>>b;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	if(dfs(0,1)){
		int w=0;
		rep(i,N)if(col[i]==1)w++;
		ll ans=(ll)w*(N-w);
		ans-=M;
		cout<<ans<<endl;
		
	}
	else{
		ll ans=(ll)N*(N-1)/2;
		ans-=M;
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define pb push_back
#define pp pop_back
#define ubo upper_bound
#define lbo lower_bound
#define VI vector<int>
#define VL vector<ll>
#define VP vector<pii >
#define all(x) x.begin(), x.end()
#define M vector<VI >

using namespace std;

int main(){

	map<string, int> mp;

	int n;
	cin >> n;

	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		mp[s]++;
	}

	for(string s : {"AC", "WA", "TLE", "RE"}){
		cout << s << " x " << mp[s] << '\n';
	}

	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cmath>

using namespace std;

int main(void) {
	int N, T, A;
	cin >> N >> T >> A;

	float diff;
	float min_diff;
	int num = 1;
	int ans;
	while(N--) {
		int H;
		cin >> H;
		diff = abs(A - (T - H * 0.006));
		if (num == 1) {
			min_diff = diff;
			ans = 1;
		}
		if (diff < min_diff) {
			min_diff = diff;
			ans = num;
		}
		num++;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

std::string lowercase(std::string& t) {
	for (std::string::iterator it = t.begin(); it < t.end(); it++) {
		if (*it >= 'A' && *it <= 'Z')
			*it += ('a' - 'A');
	}
	return t;
}

int main()
{
	int count = 0;
	std::string w, t;
	std::cin >> w >> t;
	while (t != "END_OF_TEXT") {
		if (w == lowercase(t))
			count++;
		std::cin >> t;
	}
	std::cout << count << "\n";
    return 0;
}




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


#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  string str;
  int count['z'-'a'+1] = {};
  
  while(getline(cin,str)){
    for(char &ch:str){
      if('A'<=ch && ch<='Z') count[ch-'A'] += 1;
      else if('a'<=ch && ch<='z') count[ch-'a'] += 1;
    }
  }
  for(int i=0;i<'z'-'a'+1;i++){
      cout << (char)(i+'a') << " : " << count[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 3052
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

int main()
{
    int a,b;
    cin>>a>>b;
    if(a%3==0||b%3==0||(a+b)%3==0)
    {
        puts("Possible");
    }
    else{
        puts("Impossible");
    }
    return 0;
}


Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define debug(x) cout << #x <<" = " << x << endl
void solve()
{
ll int n;
cin>>n;
ll int ans=0;
for (ll int i = 1; i < n; i++)
{
    if(n%i==0)
    {
        ans+=(n/i);
        ans--;
    }
    else
    {
      ans+=(n/i);
    }
}
cout<<ans<<endl;
}
int main()
{
//      #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
FASTIO
 long long int t=1;
 //cin>>t;
 while(t--)
  solve();
  return 0;
}


Measured memory_bytes: 3604
N = int(input())
H = list(map(int, input().split()))
ans = 0

for i in range(N):
  if i == 0:
    ans += 1
  else:
    h = H[i]
    tmp = True
    
    for j in range(i-1, -1, -1):
      # print(i, j, h)
      tmp = tmp and h >= H[j]
    
    if tmp:
	    ans += 1

print(ans)

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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;


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

    int ans=0;

    while(n>0){
        n/=k;
        ans++;
    }

    cout<<ans<<endl;

}


Measured memory_bytes: 256
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**89-1
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    a = LI()
    b = LI()

    ax = []
    bx = []
    for i in range(N):
        ax.append(a[i-1] ^ a[i])
        bx.append(b[i-1] ^ b[i])

    az = 0
    bz = 0
    m = 2**30
    for i in range(N):
        az = (az * m + ax[i]) % MOD
        bz = (bz * m + bx[i]) % MOD

    for i in range(N):
        if az == bz:
            print(i,a[i] ^ b[0])
        az = ((az - ax[i] * pow(m,N-1,MOD)) * m + ax[i]) % MOD

if __name__ == '__main__':
    main()

Measured memory_bytes: 139984
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;

int main() {
    long long n;
    cin>>n;
    string s;
    while(n){
        int x = n%26;
        char c;
        n/=26;
        if(x)
            c = 'a'+(x-1);
        else{
            c = 'z';
            n--;
        }
        s = c+s;

    }
    cout<<s<<endl;
	return 0;
}


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


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

    long long N,A,B;
    cin >> N >> A >> B;
    long long x,y;
    x=N/(A+B);
    y=min(N%(A+B),A);
    cout << x*A+y << endl;

}


Measured memory_bytes: 256
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m,x;
    cin>>n;
    m=(n+999)/1000;
    cout<<m*1000-n<<"\n";
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main()
{
   // freopen("in.c","r",stdin);
    int a,b;
    cin>>a>>b;
    char n[a+b+4];
    cin>>n;
    int l=strlen(n);
    if(l!=a+b+1 || n[a]!='-') cout<<"No"<<endl,exit(0);
    for(int i=0;i<l;i++)
        if(!isdigit(n[i]) && i!=a) cout<<"No"<<endl,exit(0);
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<queue>
#include<ctime>
#include<map>
#define ll long long
#define pr(x) cerr<<#x<<"="<<x<<endl
using namespace std;
#define N 2000010
int n,m,i,j,dis[N],to[N],tp[N],tq[N],size,cnt,g[N],vis[N],o,p,q;
vector<int> col[N];
#define pa pair<int,int>
map<pair<int,int>,int>mp;
struct node
{
	int to,next,v;
}e[N*2];
inline void add(int o,int p,int q)
{
	e[++size].to=p;
	e[size].next=g[o];
	g[o]=size;
	e[size].v=q;
}
inline void dij()
{
	for (i=1;i<=cnt;i++)dis[i]=100000000;
	priority_queue<pa,vector<pa>,greater<pa> >que;
	dis[1]=0;
	que.push(make_pair(0,1));
	while (!que.empty())
	{
		int x=que.top().second;
		que.pop();
		if (vis[x]) continue;
		vis[x]=1;
		for (int k=g[x];k;k=e[k].next)
		{
			int y=e[k].to;
			if (dis[x]+e[k].v<dis[y])
			{
				dis[y]=dis[x]+e[k].v;
				que.push(make_pair(dis[y],y));
			}
		}
	}
}
inline int read()
{
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int main()                   
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;i++)
	{
		o=read(),p=read(),q=read();
		col[o].push_back(q);
		col[p].push_back(q);
		to[i]=o,tp[i]=p,tq[i]=q;
	}
	cnt=n;
	for (i=1;i<=n;i++)
	{
		for (j=0;j<(int)col[i].size();j++)
		{
			if (mp[make_pair(i,col[i][j])]==0)
			{
				mp[make_pair(i,col[i][j])]=++cnt;
				//printf("point %d color %d --> %d\n",i,col[i][j],cnt);
				add(cnt,i,1);
				add(i,cnt,1);
			}
		}
	}
	for (i=1;i<=m;i++)
	{
		int tmpa=mp[make_pair(to[i],tq[i])],tmpb=mp[make_pair(tp[i],tq[i])];
		add(tmpa,tmpb,0);
		add(tmpb,tmpa,0);
	}
	//for (i=1;i<=size;i+=2)printf("%d--%d %d\n",e[i].to,e[i+1].to,e[i].v);
	dij();
	if (dis[n]==100000000)
	printf("-1\n");
	else 
	printf("%d\n",dis[n]/2);
	return 0;
}

Measured memory_bytes: 110456
n = int(input())
a = list(map(int, input().split()))

left = 0
right = sum(a)

ans = 10000
for i in range(1, n):
    left += a[i - 1]
    right -= a[i - 1]
    if abs(left - right) < ans:
        ans = abs(left - right)
    else:
        break

print(ans)

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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* na, Arg1&& arg1, Args&&... args) {
  const char* c = strchr(na + 1, ',');
  cerr.write(na, c - na) << " : " << arg1 << " , ";
  __f(c + 1, args...);
}
#define endl "\n"
#define all(v) v.begin(), v.end()
#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())
typedef long long LL;
typedef pair <int,int> pii;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 1e5 + 5;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif // LOCAL
  int n;
  cin >> n;
  vector <double> p (n + 1);
  for (int i = 1; i <= n; i++) cin >> p[i];
  vector <vector <double> > dp (n + 1, vector <double> (n + 1, 0.0));
  dp[0][0] = 1.0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      if (j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1] * p[i];
      dp[i][j] += dp[i - 1][j] * (1 - p[i]);
    }
  }
  double ans = 0.0;
  for (int i = 1; i <= n; i++) {
    if (i > n - i) ans += dp[n][i];
  }
  cout << setprecision(10) << fixed;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 70784
#include<stdio.h>
#include<string.h>
int main(void){
  int a,b,k,c=0;
  scanf("%d",&k);
  scanf("%d",&a);
  scanf("%d",&b);
  while(a<=b){
    if(a%k==0){
      c++;
    }
    a++;
  }
  if(c==0){
    printf("NG");
  }else if(c>=1){
    printf("OK");
  }
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long ll;

int main(){
  int a,b;
  cin >> a >> b;

  int count = 0;
  int tap=1;

  while(tap<b){
    tap--;
    tap+=a;
    count++;
  }

  cout << count;
}

Measured memory_bytes: 3612
n,x,y = map(int,input().split())

ans = [0] * n
for i in range(1, n+1):
  for j in range(i+1, n+1):
    dist = min(abs(j-i),abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))
    ans[dist] += 1
for i in range(1,n):
  print(ans[i])


Measured memory_bytes: 3444
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define blue ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007;

int main() {
  blue;
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];

  int dp[n];
  dp[0]=0;
  int allMin;
  for(int i=1;i<n;i++) {
    allMin=dp[i-1]+abs(a[i]-a[i-1]);
    for(int j=1;j<=k;j++) {
      if(i-j < 0) break;
      allMin = min(allMin, dp[i-j]+abs(a[i]-a[i-j]));
    }
    dp[i] = allMin;
  }

  cout<<dp[n-1];
}

/*
  
*/

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

#define N 100
// 未訪問
#define WHITE 0
// 訪問中
#define GRAY 1
// 訪問済み
#define BLACK 2

int n,M[N][N];
int color[N];
// 訪問時間
int d[N];
// 探索終了時間
int f[N];
// 時間
int t = 0;
// 探索済みの頂点を一から探索しないように、nt[u]にすでに探索済みの番号を入れ、次回は探索した移行の頂点から探索されるようにする
int nt[N];

/**
    uに隣接するvを番号順に取得する
*/
int next(int u){
    // 探索済み移行の頂点から探索を始める
    for(int v = nt[u];v < n;++v){
        nt[u] = v + 1;
        if(M[u][v]){
            return v;
        }
    }
    return -1;
}

/**
    スタックを用いた深さ優先探索
*/
void dfs(int u){
    for(int i = 0;i < n;++i){
        nt[i] = 0;
    }
    
    stack<int> S;
    S.push(u);
    color[u] = GRAY;    // 訪問中
    d[u] = ++t;      // 訪問時間
    
    while(!S.empty()){
        int topU = S.top();
        // 隣接する頂点
        int v = next(topU);
        // 隣接する頂点が見つかった場合
        if(v != -1){
            // 未探索のケース
            if(color[v] == WHITE){
                color[v] = GRAY;
                // 訪問時間
                d[v] = ++t;
                S.push(v);
            }
        }else{
            // 未訪問の頂点が見つからなかった
            S.pop();
            // 探索終了
            color[topU] = BLACK;
            // 探索終了時間
            f[topU] = ++t;
        }
    }
}

int main(){
    int u,k,v;
    cin >> n;
    
    // 初期化
    for(int i = 0;i < n;++i){
        color[i] = WHITE;
        for(int j = 0;j < n;++j){
            M[i][j] = 0;
        }
    }
    
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        // 頂点を移動する
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            --v;    // ずらす
            M[u][v] = 1;
        }
    }
    for(int i = 0;i < n;++i){
        if(color[i] == WHITE){
            dfs(i);
        }
    }
    
    for(int i = 0;i < n;++i){
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
    
    return 0;
}



Measured memory_bytes: 3128
#include <stdio.h>
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
#include <utility>
#include <iomanip>
#define input(a) cin >> a
#define input(a,b) cin >> a >> b
#define input(a,b,c) cin >> a >> b >> c
#define print(x) cout << x << endl
#define rep(a,n) for(int i = a; i < n; i++)
#define ll long long int
using namespace std;
int iinput(int x) {cin >> x; return x;}
string sinput(string x) {cin >> x; return x;}

int main(){
    int a,b,c,ans;
    input(a,b,c);
    ans = a * b /2;
    print(ans);
    
    return 0;
}


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

int main() {
    int m,f,r;
    char s;
    cin>>m>>f>>r;
    while (m!=-1||f!=-1||r!=-1)
    {
        if (m==-1||f==-1)
            s = 'F';
        else if (m+f<30) s = 'F';
        else if (m+f<50)
        {
            s = 'D';
            if (r>=50) s = 'C';
        }
        else if (m+f<65) s = 'C';
        else if (m+f<80) s = 'B';
        else s = 'A';
        cout<<s<<endl;
        cin>>m>>f>>r;
    }
    return 0;
}


Measured memory_bytes: 3100