akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <set>

using namespace std;

constexpr int MAX_N = 200000;

int n;
int h[MAX_N];

int L[MAX_N], R[MAX_N];
int st[MAX_N];

void solve()
{
    int t = 0;
    for (int i = 0; i < n; i++) {
        while (t > 0 && h[st[t - 1]] >= h[i]) t--;
        L[i] = t == 0 ? 0 : (st[t - 1] + 1);
        st[t++] = i;
    }

    t = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (t > 0 && h[st[t - 1]] >= h[i]) t--;
        R[i] = t == 0 ? n : st[t - 1];
        st[t++] = i;
    }

    int res = 0;
    set<pair<int, int>> used;
    for (int i = 0; i < n; i++) {
        if (used.count(make_pair(L[i], R[i])) == 0) {
            used.insert(make_pair(L[i], R[i]));
            res++;
        }
    }

    cout << res << endl;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    solve();
    return 0;
}

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

int main()
{
	double w;
	string s;

	while (cin >> w) {
		if (w <= 48)
			s = "light fly";
		else if (w <= 51)
			s = "fly";
		else if (w <= 54)
			s = "bantam";
		else if (w <= 57)
			s = "feather";
		else if (w <= 60)
			s = "light";
		else if (w <= 64)
			s = "light welter";
		else if (w <= 69)
			s = "welter";
		else if (w <= 75)
			s = "light middle";
		else if (w <= 81)
			s = "middle";
		else if (w <= 91)
			s = "light heavy";
		else
			s = "heavy";

		cout << s << endl;
	}

	return 0;
}


Measured memory_bytes: 3280
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 +c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}

int N,Q;
char s[MAXN];
pii op[MAXN];
int getplace(int p) {
    for(int i = 1 ; i <= Q ; ++i) {
        if(s[p] == 'A' + op[i].fi) {
            p += op[i].se;
        }
    }
    return p;
}
int findL() {
    int L = 0,R = N;
    while(L < R) {
        int mid = (L + R + 1) >> 1;
        if(getplace(mid) == 0) L = mid;
        else R = mid - 1;
    }
    return L;
}
int findR() {
    int L = 1,R = N + 1;
    while(L < R) {
        int mid = (L + R) >> 1;
        if(getplace(mid) == N + 1) R = mid;
        else L = mid + 1;
    }
    return L;
}
void Solve() {
    read(N);read(Q);
    scanf("%s",s + 1);
    char t[5],d[5];
    for(int i = 1 ; i <= Q ; ++i) {
        scanf("%s%s",t + 1,d + 1);
        int a,b;
        if(d[1] == 'L') b = -1;
        else b = 1;
        a = t[1] - 'A';
        op[i] = mp(a,b);
    }
    int L = findL(),R = findR();
    out(R - L - 1);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;
/* ちゃんと考えてわかって実装 */

int main(void){
    ll a;
    cin >> a;
    string b;
    cin >> b;

    ll B100 = (b[0] - '0')*100LL + (b[2] - '0')*10LL + (b[3] - '0');
    ll ans = a*B100/100LL;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596
N, M = map(int, input().split())
H = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N+1)]
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])


ans = 0
for i in range(1,N+1):
    highest = True
    for j in graph[i]:
        if H[i-1] <= H[j-1]:
            highest = False
    if highest:
        ans += 1

print(ans)

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

int main() {
	int a, b, maxn = -1000000000;
	cin >> a >> b;
	maxn = max(a + b, maxn);
	maxn = max(a - b, maxn);
	maxn = max(a*b, maxn);
	cout << maxn << endl;
	return 0;
}

Measured memory_bytes: 256
N, K, Q = map(int, input().split())
As = [ int(input()) for _ in range(Q) ]
Points = [ 0 ] * (N + 1)

for A in As:
  if A == 1:
    Points[1] = Points[1]  + 1
  elif A == N:
    Points[0] = Points[0] + 1
    Points[N-1] = Points[N-1] - 1
  else:
    Points[0] = Points[0] + 1
    Points[A-1] = Points[A-1] - 1
    Points[A] = Points[A] + 1

for i in range(N):
  Points[i+1] = Points[i+1] + Points[i]

for i in range(N):
  if Points[i] >= K:
    print("No")
  else:
    print("Yes")

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

typedef long long ll;

#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define clr(a, b) memset(a, b, sizeof(a))
#define forn(i, n) for(int i=0; i<(int)(n); ++i)
#define forab(i, a, b) for(int i=(int)(a); i<=(int)(b); ++i)
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef LOCAL
    clock_t tStart = clock();
#endif
    int r;
    cin >> r;
    cout << r*r << "\n";
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * (clock() - tStart)/ CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	a := nextInts(n)

	for i := range a {
		if a[i]%2 == 1 {
			puts("first")
			return
		}
	}
	puts("second")
}


Measured memory_bytes: 3200
#include <iostream>
#include <algorithm>
#include <vector>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    printf(k <= (n + 1) / 2 ? "YES\n" : "NO\n");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int p[11];
int main(){
	int n,i,mx=0,mxx,ans=0;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>p[i];
		ans+=p[i];
		if(p[i]>mx) mx=p[i];
	}
	mxx=mx/2;
	ans-=mxx;
	cout<<ans;
	return 0;
}

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

int main()
{
    vector < pair <int,int> > v;
    vector < pair <int,int> >::iterator it;

    int n;

    cin>>n;

    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        v.push_back( make_pair(x,i+1) );
    }

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

    for(int i=0;i<n;i++)
    {
        cout<<v[i].second<<" ";
    }

    cout<<endl;

}


Measured memory_bytes: 1780
/*
* Note: This template uses some c++11 functions , so you have to compile it with c++11 flag.
*       Example:-   $ g++ -std=c++11 c++Template.cpp
*
* Author : Akshay Pratap Singh
* Handle: code_crack_01
*
*/
 
/********   All Required Header Files ********/
#include <iostream>
#include <string>
#include <vector>
// #include <unordered_map>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <climits>

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCC(t) scanf("%c",&t)
#define SCS(t) scanf("%s",t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for(int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for(int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define read(type) readInt<type>()
typedef long long int ll;
typedef unsigned long long int  ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<vi> vvi;

#define MOD 1000000007
#define MAX 200010

long long int f[MAX] = {};  
long long int rf[MAX] = {};  
  
long long int pw(long long int x, long long int y) {  
    long long ret = 1LL;  
  
    REP(mask, 30) {  
        if (y >> mask & 1)  
            ret = ret * x % MOD;  
        x = x * x % MOD;  
    }  
    return ret % MOD;  
}  
  
long long int getC(int n, int k){
    if (k > n) return 0;
    long long int ret = f[n];
    ret = ret * rf[k] % MOD;  
    ret = ret * rf[n-k] % MOD;  
    return ret;
}

long long int Comb(int n, int k) {  
    rf[0] = f[0] = 1;  
    for (int i = 1; i < n+1; i++){  
        f[i] = f[i-1] * i % MOD;  
        rf[i] = pw(f[i], MOD-2);  
    }  
    return 1;  
}  

int main() {

    int N; cin >> N;
    int r, l, a;
    vi used(N, -1);

    REP(i, N+1) {
        cin >> a; a--;
        if (used[a] >= 0) {
            l = used[a];
            r = i;
        } else {
            used[a] = i;
        }
    }

    Comb(N+5, N+5);
    
    for (int k = 1; k <= N+1; k++) {
        ll ans = getC(N+1, k) - getC(N-r+l, k-1);
        if (ans < 0 ) ans += MOD;
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3200
A = input().split()

matchflg = False
result = False
for i, d in enumerate(A):
    for f in A[(i + 1):]:
        if d == f:
            if matchflg == True:
                result = False
            elif matchflg == False:
                result = True
                matchflg = True

if result:
    print('Yes')
elif not result:
    print('No')


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

#define SZ 1000
#define MAX(X,Y) ((X)>(Y)?(X):(Y))

int main(void){
  int n;
  int d[SZ+1][SZ+1], ans;
  
  cin >> n;
  for (int i=0; i<=SZ; i++){
    for (int j=0; j<=SZ; j++) d[i][j] = 0;
  }
  for (int i=0; i<n; i++){
    int x0, y0, x1, y1;
    cin >> x0 >> y0 >> x1 >> y1;
    d[x0][y0]++; d[x1][y1]++;
    d[x0][y1]--; d[x1][y0]--;
  }
  // Y-acc
  for (int x=0; x<=SZ; x++){
    for (int y=1; y<=SZ; y++){
      d[x][y] += d[x][y-1];
    }
  }
  // X-acc
  ans = d[0][0];
  for (int y=0; y<=SZ; y++){
    ans = MAX(ans, d[0][y]);
    for (int x=1; x<=SZ; x++){
      d[x][y] += d[x-1][y];
      ans = MAX(ans, d[x][y]);
    }
  }
  cout << ans << endl;    
  return 0;
}
  
  



Measured memory_bytes: 7036
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    ll n;cin>>n;
    vector<ll> a(n);
    map<ll,ll> mp;
    For(i,0,n) {
        cin>>a[i];
    }
    For(i,0,n){
        ans+=mp[i-a[i]];
        mp[a[i]+i]++;
    }
    cout << ans << endl;
}
int main(){
    Main();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}


Measured memory_bytes: 27424
#include<iostream>
#include<string>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int i,j,k;
  string st[51];
  for(i=0;i<n;i++) cin >> st[i];
  int ch[51][3]={{}};
  for(i=0;i<n;i++){
    int c[3]={};
    for(j=0;j<m;j++){
      if(st[i][j]=='W') c[0]++;
      if(st[i][j]=='B') c[1]++;
      if(st[i][j]=='R') c[2]++;
    }
    for(k=0;k<3;k++) {
      ch[i][k]=m-c[k];
      //cout << ch[i][k] << endl;
    }
  }
  int dp[51][3]={{}};
  int inf = 1 << 20;
  fill(dp[0],dp[50],inf);
  dp[0][0]=ch[0][0];
  for(i=1;i<n-1;i++){
    for(j=0;j<3;j++){
      for(k=j;k<3;k++){
        dp[i][k]=min(dp[i][k],dp[i-1][j]+ch[i][k]);
      }
    }
  }
  int o=inf;
  for(k=1;k<3;k++) o=min(o,dp[n-2][k]+ch[n-1][2]);

  cout << o << endl;
  return 0;
}

Measured memory_bytes: 1212
#include<stdio.h>
int main(){
	int a;
	scanf("%d",&a);
	if(a<1200&&a>=0){
		printf("ABC\n");
	}
	else if(a>=1200&&a<2800){
		printf("ARC\n");
	}
	else if (a>=2800&&a<=4208)
	{
		printf("AGC\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <math.h>
using namespace std;

struct rec{
	int t,m,s;
};

int main(){
	
	int N,M,r,t,n,m,s,ts,te,in,start,pd,q,sw,sw2;
	rec rec[1000];
	
	while(cin>>N>>M,N||M){
		cin>>r;
		for(int i=0;i<r;i++){
			cin>>t>>n>>m>>s;
			rec[i].t=t;rec[i].m=m;rec[i].s=s;
		}
		cin>>q;
		for(int h=0;h<q;h++){
			cin>>ts>>te>>m;
			in=0;pd=0;sw=0;sw2=0;
			for(int i=0;i<r;i++){
				if(rec[i].m!=m)continue;
				if(rec[i].t>=ts&&sw==0){
					if(in>0)start=ts;sw=1;}
				if(rec[i].t>=te){
					if(in>0)pd+=te-start;sw2=1;
					break;
				}
				if(rec[i].s==1){
					if(rec[i].t>=ts&&in==0)start=rec[i].t;
					in++;
				}
				else {
					if(rec[i].t>ts&&in==1)pd+=rec[i].t-start;
					in--;
				}
			}
		if(sw2==0&&in>0)pd+=te-start;
		cout<<pd<<endl;
		}
	}
}

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

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
struct Point {
    ll x, y;
    bool operator < (const Point& op2) const {
        return x < op2.x;
    }
} p[maxn];
int n, K;

int main(void) {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n >> K) {
        for(int i = 0; i < n; ++i)
            cin >> p[i].x >> p[i].y;
        sort(p, p + n);
        ll area = LLONG_MAX;
        for(int i = 0; i < n - 1; ++i) {
            for(int j = i + 1; j < n; ++j) {
                ll miny = min(p[i].y, p[j].y);
                ll maxy = max(p[i].y, p[j].y);
                for(int k = 0; k < n; ++k) {
                    if(p[k].y < miny || p[k].y > maxy) continue;
                    int cnt = 0;
                    for(int l = k; l < n; ++l) {
                        if(p[l].y > maxy || p[l].y < miny) continue;
                        ++cnt;
                        if(cnt >= K) area = min(area, (maxy - miny) * (p[l].x - p[k].x));
                    }
                }
            }
        }
        cout << area << endl;
    }
}

Measured memory_bytes: 256
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd(b ,a%b)

def lcm(a,b):
  return a*b / gcd(a,b)

while True:
  try:
    a = map(int,raw_input().split())
    a,b = a[0],a[1]
    print gcd(a,b)
  except EOFError:
    break

Measured memory_bytes: 4220
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			String s = sc.next();
			if(s.compareTo("#")==0) break;
			boolean flag;
			int count = 0;
			int p ;
			
			p = s.codePointAt(0);
			if((104<=p && p<=112) || p==117 || p==121) flag = true;
			else flag = false;
			
			for(int i=1;i<s.length();i++){
				p = s.codePointAt(i);
				if((104<=p && p<=112) || p==117 || p==121){
					if(flag==false){
						flag = true;
						count++;
					}
				}else{
					if(flag==true){
						flag = false;
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}	
}

Measured memory_bytes: 19896
#include "bits/stdc++.h"

using namespace std;

void solve()
{
	vector<int> as(4);
	for (int i = 0; i< 4; i++) cin >> as[i];
	sort(as.begin(), as.end());
	if (as[0] == 1 && as[1] == 4 && as[2] == 7 && as[3] == 9)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
}

int main(void)
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 45
#define NIL -1
int dp[45];

int fibb(int n){
  if(n == 0 || n == 1)return dp[n] = 1;
  if(dp[n] != NIL)return dp[n];
  return dp[n] = fibb(n - 1) + fibb(n - 2);
}

int main(){
  int n,i;
  scanf("%d",&n);
  for(i=0;i<=n;i++){
    dp[i] = NIL;
  }
 
  printf("%d\n",fibb(n));
  return 0;
}





Measured memory_bytes: 2104
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
const int N=2e5+10;
ll n,a[N],x[N],num[N],cnt,add1[N],add2[N],sum;
ll C(ll m){return (m-1)*m/2;}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i],x[a[i]]++;
		if(x[a[i]]==1)num[cnt++]=a[i];
	}
	for(int i=0;i<cnt;i++)add1[num[i]]=C(x[num[i]]),add2[num[i]]=C(x[num[i]]-1),sum+=add1[num[i]];
	for(int i=0;i<n;i++){
		ll ans=0;
		ans=sum-add1[a[i]]+add2[a[i]];
		cout<<ans<<'\n';
	}
	return 0;
}


Measured memory_bytes: 9472
N,M=[int(i) for i in input().split()]
a=[]
b=[]
c=[]
for i in range(M):
    x,y=[int(i) for i in input().split()]
    if x==1 :
        c.append(y)
    if y==N:
        c.append(x)
if len(c)==len(set(c)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


Measured memory_bytes: 74072
#include<iostream>
#include<string.h>
#include<queue>
#include<vector>
#include <cstdlib>
#include<algorithm>
#include <cstdio>
#include <cctype>
using namespace std;
const long long INF=1000000000LL;
typedef long long ll;
typedef pair<int,int> Q;
typedef pair<int,Q> Pa;
ll N,A[100005],D[100005]={},B[200005]={},C[200005];
ll L[55],ans=0;
int k=0,s=0;
int h;

int main(){
	cin>>N;
	for(int i=0;i<N;++i){
		cin>>A[i];
		if(A[i]>100000)++ans;
		else D[A[i]]++;
	}
	for(int i=1;i<=100000;++i){
		if(D[i]<i)ans+=D[i];
		if(D[i]>i)ans+=D[i]-i;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main(void){
  int r, g, b;
  scanf("%d%d%d",&r, &g, &b);
  if((100*r+10*g+b)%4==0){
    printf("YES\n");
  }else{
    printf("NO\n");
  }
  return 0;
  
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

void FIO()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int n;
int dp[2001];

int solve(int n)
{
	if (n == 0)
		return 1;

	if (dp[n] != -1)
	{
		return dp[n];
	}

	int ans = 0;

	for (int i = 3; i <= n; ++i)
	{
		if (n >= i)
		{
			ans = (ans + solve(n - i)) % mod;
		}
	}

	return dp[n] = ans;
}

int32_t main()
{
	FIO();
	memset(dp, -1, sizeof(dp));
	cin >> n;
	cout << solve(n) << '\n';
	return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
#define Max(a) (*max_element(ALL(a)))
#define Min(a) (*min_element(ALL(a)))
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  ll ans = 0;
  for(int i=0;i<n;i++){
    ans += (n-i)*(n-i+1)/2;
  }

  for(int i=0;i<n-1;i++){
    ll a,b;cin>>a>>b;
    ans -= min(a,b)*(n-max(a,b)+1);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3568
n = int(input())
a = list(map(int,input().split()))
b = [a[i]-i-1 for i in range(n)]
b.sort()
if n%2 == 0:
    c = (b[(n-2)//2] + b[n//2])//2
else:
    c = b[(n - 1) // 2]
ans = 0
for i in range(n):
    ans += abs(b[i]-c)
print(ans)


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

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

	vector<int> v(n);
	for (auto& i : v) {
		cin >> i;
	}

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

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

	m = max(m, k - v[n-1] + v[0]);

	cout << k - m << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
typedef long long ll;
const int MAX = 999999999;

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

    vector<vector<char>> field(h, vector<char>(w));
    rep(i, h){
        rep(j, w) cin >> field[i][j];
    }

    rep(i, h){
        rep(j, w){
            if(field[i][j] == '#') continue;

            int cnt = 0;
            repi(a, -1, 2){
                repi(b, -1, 2)
                    if(0 <= i+a && i+a < h && 0 <= j+b && j+b < w && field[i+a][j+b] == '#') cnt++;
            }
            field[i][j] = cnt + 48;
        }
    }

    rep(i, h){
        rep(j, w) cout << field[i][j];
        cout << endl;
    }
}

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

const int maxr = 96;
const int maxc = 100;

char a[maxr][maxc];
int main()
{
    int A, B;
    scanf("%d%d", &A, &B);

    int mx = min(17, min(A, B)), tempA = A, tempB = B, cnt = 0;
    for(int i = 0; i < maxr; i ++) {
        if(i % 6 == 0)
            tempA --;
        if(i % 6 == 3)
            tempB --;
        if(i % 6 == 2) {
            cnt ++;
            if(cnt == mx) {
                if(A <= B) {
                    for(int k = i; k < maxr; k ++)
                        for(int j = 0; j < maxc; j ++)
                            a[k][j] = '.';
                } else {
                    tempB --;
                    for(int k = i; k < maxr; k ++)
                        for(int j = 0; j < maxc; j ++)
                            a[k][j] = '#';
                }
                break;
            }
        }
        for(int j = 0; j < 100; j ++) {
            if((i % 6 ) <= 2)
                a[i][j] = '.';
            if((i % 6) > 2)
                a[i][j] = '#';
        }
    }

    int resW = tempA, resB = tempB;
    for(int i = 1; i < maxr; ) {
        if((i % 6) == 1) {
            for(int j = 0; j < maxc; j += 2)
                if(resB)
                    resB --, a[i][j] = '#';
        } else {
            for(int j = 0; j < maxc; j += 2)
                if(resW)
                    resW --, a[i][j] = '.';
        }
        i += 3;
    }
    int row = maxr;
    printf("%d %d\n", row, 100);
    for(int i = 0; i < row; i ++) {
        for(int j = 0; j < maxc; j ++)
            printf("%c", a[i][j]);
        puts("");
    }
    return 0;
}


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

int main(){
    string S;
    cin >> S;
    bool sec = true;
    for(int i = 0; i < 3; ++i){
        if(S[i] == S[i+1]) sec = false;
    }
    if(sec) cout << "Good" << endl;
    else cout << "Bad" << endl;
}

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

const int MAX = 11000;
bool isPrime[MAX];

void next(int& k) {
    do {
        k++;
    } while (isPrime[k] == false);
}

int main() {
    fill_n(isPrime, MAX, true);
    for (int i = 4; i < MAX; i += 2) {
        isPrime[i] = false;
    }
    for (int i = 3; i * i <= MAX; i += 2) {
        if (isPrime[i]) {
            for (int j = i * 2; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        int min = 2, max = 2, res = 0, sum = 2;
        while (min <= n) {
            if (sum < n) {
                next(max);
                sum += max;
            } else {
                if (sum == n) {
                    res++;
                }
                sum -= min;
                next(min);
            }
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;

class RangeFind {
    int n;
    vector<i64> data;
    
    int find(int a, int b, const i64 x, int k, int l, int r) {
        if (data[k] > x || r <= a || b <= l) return -1;
        if (k >= n) {
            return k - n;
        }
        int t = find(a, b, x, 2 * k + 1, (l + r) >> 1, r);
        if (t != -1) return t;
        return find(a, b, x, 2 * k, l, (l + r) >> 1);
    }
    
public:
    RangeFind(const vector<i64>& as) {
        n = 1;
        while (n < as.size()) n <<= 1;
        data.assign(2 * n, 1e18);
        for (int i = 0; i < as.size(); i++) {
            data[n + i] = as[i];
        }
        for (int i = n - 1; i > 0; i--) {
            data[i] = min(data[2 * i], data[2 * i + 1]);
        }
    }
    
    void update(int k, const i64& x) {
        k += n;
        data[k] = x;
        while (k >>= 1) {
            data[k] = min(data[2 * k], data[2 * k + 1]);
        }
    }
    
    i64 query(int a, int b) {
        i64 L = 1e18, R = 1e18;
        for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
            if (a & 1) {
                L = min(L, data[a++]);
            }
            if (b & 1) {
                R = min(data[--b], R);
            }
        }
        return min(L, R);
    }
    
    // [a, b)でx以下の値をもつ最右の要素の位置
    int find(int a, int b, const i64& x) {
        return find(a, b, x, 1, 0, n);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.setf(ios::fixed);
    cout.precision(10);
    int n, q;
    cin >> n >> q;
    vi sum(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> sum[i + 1];
        sum[i + 1] += sum[i];
    }
    RangeFind rf(sum);
    while (q--) {
        i64 x;
        cin >> x;
        i64 ret = 0;
        for (int i = 1; i <= n; i++) {
            int k = rf.find(i, n + 1, x + sum[i - 1]);
            if (k != -1) {
                ret += k - i + 1;
            }
        }
        cout << ret << endl;
    }
}



Measured memory_bytes: 5752
#include <bits/stdc++.h>
typedef long long int ll;
#define vaibhavv06               \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(0);
#define int long long
#define MM(a,b) memset(a,b,sizeof(a))
const ll MOD = 1000000007;
using namespace std;



int32_t main(){
    vaibhavv06;
	char c; cin>>c;
	cout<<(char)(c+1)<<endl;
	
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
typedef long long LL;
char a[105];
int main()
{
	int n, ans = 0, flag = 0, flag1 = 0, flag2 = 0, flag3 = 0;
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
	{
		scanf(" %c",&a[i]);
		if(a[i] == 'P' && flag != 1)
		{
			flag = 1;
			ans++;
		}
		if(a[i] == 'W' && flag1 != 2)
		{
			flag1 = 2;
			ans++;
		}	
		if(a[i] == 'G' && flag2 != 3)
		{
			flag2 = 3;
			ans++;
		}	
		if(a[i] == 'Y' && flag3 != 4)
		{
			flag3 = 4;
			ans++;
		}
	}
	if(ans == 1)
	{
		printf("One\n");
	}	
	if(ans == 2)
	{
		printf("Two\n");
	}	
	if(ans == 3)
	{
		printf("Three\n");
	}	
	if(ans == 4)
	{
		printf("Four\n");
	}
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define INF 1e9
typedef long long ll;
using namespace std;

int main() {
    string s1,s2; cin >> s1 >> s2;
    sort(s1.begin(),s1.end());
    sort(s2.rbegin(),s2.rend());
    if(s1<s2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

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

bool IsPrime(long long num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    for (long long i = 3; i*i <= num; i += 2){
        if (num % i == 0) return false;
    }

    return true;
}

int main(){
  long long n;
  cin >> n;
  
  map<long long, long long> cnt;
  set<long long> ans;
  for(long long i = 1; i*i <= n; i++){
    if(n%i != 0) continue;
    bool ok = IsPrime(i);
    if(ok){
      long long k = n;
      while(k%i == 0){
        cnt[i]++;
        k /= i;
      }
    }
    
    long long l = n / i;
    ok = IsPrime(l);
    if(ok){
      long long k = n;
      while(k%l == 0){
        cnt[l]++;
        k /= l;
      }
    }
  }
  
  for(auto now : cnt){
    long long num = now.first, c = now.second - 1;
    long long l = num;
    long long j = 1;
    while(c >= 0){
      if(ans.count(l)){
        l *= num;
        j++;
        c--;
      }
      if(c < 0) break;
      if(!ans.count(l)){
        ans.insert(l);
        c -= j;
      }
    }
  }
  
  cout << ans.size() << endl;
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    	int n;
    	int senCount=0;
    	Scanner sc=new Scanner(System.in);
    	n=sc.nextInt();
	
    	if((n%1000)!=0){
        	int amari=1000-(n%1000);
        	System.out.println(amari);
    	}else{
    	    System.out.println(0);
    	}
	}
}

Measured memory_bytes: 35720
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#ifndef ONLINE_JUDGE
#define tr(...) {__l(__LINE__);__f(#__VA_ARGS__, __VA_ARGS__);}
inline void __l(int line) { cerr << "#" << line << ": "; }template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << endl;}template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define tr(...)
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}template<typename T>inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v){bool first = true;os << "[";for(auto i: v){if(!first)os << ", ";os << i;first = false;}return os << "]";}
const int N = 5*(int)1e5 + 10;
// make sure N size is correctttt!!!!!!!!!


int n, a[N], h, w;
int32_t main(){_

   cin>>n>>h>>w;

   cout<< (n-h+1) * (n-w+1);

   //make sure N size is correct!!!!!!!!!
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  sort(all(p));
  int sum = 0;
  rep(i,k) sum += p[i];
  cout << sum << endl;
}

Measured memory_bytes: 3600
import java.util.Scanner;


import java.lang.Math;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0){
                break;
            }
            double s[] = new double[n];
            double m=0,a=0;
            for(int i=0;i<n;i++){
                s[i] = sc.nextDouble();
                m+=s[i];
            }
            m/=n;
            for(int i=0;i<n;i++){
                a+=(s[i]-m)*(s[i]-m);
            }
            a/=n;
            System.out.printf("%.8f%n",Math.sqrt(a));
        }
        sc.close();
    }
}



Measured memory_bytes: 39988
from math import log

n = int(raw_input())
x = map(int, raw_input().split())
m, k = map(int, raw_input().split())
a = map(lambda x:int(x) - 2, raw_input().split())

logk = log(k, 2)
dy = [x[i + 1] - x[i] for i in xrange(n - 1)]
swap = [range(n - 1) for _ in xrange(int(logk + 1))]

for i in xrange(m):
    swap[0][a[i]], swap[0][a[i] + 1] = swap[0][a[i] + 1], swap[0][a[i]]

j = 1
while j <= logk:
    for i in xrange(n - 1):
        swap[j][i] = swap[j - 1][swap[j - 1][i]]
    j += 1

last = range(n - 1)
j = 0
while k >> j > 0:
    if (k >> j) & 1 == 1:
        for i in xrange(n - 1):
            last[i] = swap[j][last[i]]
    j += 1

ans = x[0]
print(ans)
for i in xrange(n - 1):
    ans += dy[last[i]]
    print(ans)


Measured memory_bytes: 80576
N = int(input())

k = N*2
flag = False
tmp = 0
if N == 1:
    print("Yes")
    print(2)
    print(1, 1)
    print(1, 1)
    exit(0)
for x in range(2, int(k ** 0.5) + 1):
    if k % x == 0 and k // x == x+1:
        tmp = x
        flag = True
        break
if flag:
    print("Yes")
    print(tmp+1)
    ans = [[] for i in range(tmp+1)]
    count = 0
    for i in range(tmp+1):
        ret = [str(tmp)]
        for k in range(i):
            ret.append(ans[k][i])
        for j in range(tmp):
            if i == 0:
                count += 1
                ret.append(str(count))
            else:
                if j < tmp - i:
                    count += 1
                    ret.append(str(count))

        ans[i] = ret
    for i in range(tmp+1):
        print(" ".join(ans[i]))
else:
    print("No")


Measured memory_bytes: 11380
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int n,m,p[N],ans;
vector<int>f[N];
bool solve(int x){
	for (int i = 0; i < m; ++i){
		int tmp = 0;
		for (int it: f[i]){
			if (x >> (it - 1) & 1) tmp++;
		}
		if ((tmp & 1) != (p[i]&1)) return 0;
	}	
	return 1;
}
int main(){
	int x,y;
	scanf("%d%d",&n,&m);
	for (int i = 0; i < m; ++i){
		scanf("%d",&x);
		for (int j = 0; j < x; ++j){
			scanf("%d",&y);
			f[i].push_back(y);
		}
	}
	for (int i = 0; i < m; ++i)
		scanf("%d",&p[i]);
	int all = (1 << n);
	for (int i = 0; i < all; ++i){
		ans += solve(i);
	}
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int fi[1000010],se[1000010],th[1000010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&fi[i]);
     //   printf("%d\n",fi[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&se[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&th[i]);
    }
    sort(fi,fi+n);
    sort(se,se+n);
    sort(th,th+n);
    long long ans=0;
   // int x=upper_bound(fi,fi+n,4)-fi;
    //printf("%d\n",fi[x]);
    //printf("%d\n",*x);
    for(int i=0;i<n;i++)
    {
        int x=se[i];
     //   printf("x%d\n",x);
        int y=lower_bound(fi,fi+n,x)-fi;
     //    printf("y%d\n",y);
       // if(fi[y]==x)
         //   y--;
       
        if(y<=0)
            continue;
//        int x=se[i];
        int yy=upper_bound(th,th+n,x)-th;
      //  printf("yy%d\n",yy);
        if(yy>=n)
            continue;
       // printf("%d %d %d\n",x,y,yy);
        ans+=(long long)y*(n-yy);
    }
    printf("%lld\n",ans);
}

Measured memory_bytes: 8960
# Your code here!

arr1 = Array.new([1, 3, 5, 7, 8, 10, 12])
arr2 = Array.new([4, 6, 9, 11])
arr3 = Array.new([2])

x, y = gets.chomp.split(" ").map(&:to_i)
if (arr1.include?(x) && arr1.include?(y)) || (arr2.include?(x) && arr2.include?(y)) || (arr3.include?(x) && arr3.include?(y))
    puts "Yes"
else
    puts "No"
end

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

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  unsigned long long N,K;
  cin>>N>>K;
  
  if(K<=N)
    N=N%K;
  
  if(K>N)
  {
    if(N>K-N)
      N=K-N;
  }
  cout<<N;
  return 0;
}
    
  
  
  
  
  
  
  
  
  

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

#define pb push_back
#define ff first
#define ss second
#define N 200005
#define mod 1000000007
#define fo(n) for(int i=1;i<=n;i++)
typedef pair<int,int> pii;
typedef long long int ll;
typedef long int li;
int mod1 = 998244353;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n,m;
    cin>>n>>m;
    cout<<(n*(n-1)/2 + m*(m-1)/2);
    return 0;
}


Measured memory_bytes: 256
from itertools import accumulate
import collections


N = int(input())
A = list(map(int, input().split()))

# 累積和
B = [0] + A
B = list(accumulate(B))

# 個数を数える
c = collections.Counter(B)
cm = c.most_common()

cnt = 0
for v in cm:
    if v[1] > 1:
        cnt += (v[1]*(v[1]-1)//2)

print(cnt)


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

int main() {
  int n;
  cin >> n;
  int nab=0,nea=0,nfb=0,eafb=0;
  for(int i=0;i<n;i++) {
    string s;
    cin >> s;
    if(*s.begin()=='B'&&s[s.size()-1]!='A') nfb++;
    if(*s.begin()!='B'&&s[s.size()-1]=='A') nea++;
    if(*s.begin()=='B'&&s[s.size()-1]=='A') eafb++;
    for(int j=0;j<s.size()-1;j++) {
      if(s.substr(j,2)=="AB") nab++;
    }
  }
  int temp;
  if(nea+nfb==0) {
    temp=max(eafb-1,0);
  }
  else {
    temp=eafb+min(nea,nfb);
  }
  cout << nab + temp << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;




int main(void) {
  string str;
  cin >> str;
  ll i;
  string s="";
  
  for(i=0; i<str.size(); i++) {
    if(str[i]=='B' && str[i+1]=='C') {
      s.push_back('D');
      i++;
    }else {
      s.push_back(str[i]);
    }
  }
  
  ll ans=0;
  ll t=0;
  for(i=(ll)s.size()-1; i>=0; i--) {
    if(s[i]=='A') ans+=t;
    else if(s[i]=='D') t++;
    else t=0;
  }
  
  pt(ans);
}





Measured memory_bytes: 776
#include<cstdio>

typedef long long ll;
int h[100000],n,a,b;

bool ok(int t)
{
	int c=0;
	for(int i=0;i<n&&c<=t;i++)
		c+=h[i]<=(ll)t*b?0:(h[i]-t*b+a-1)/a;
	return c<=t;
}

int main()
{
	scanf("%d%d%d",&n,&a,&b),a-=b;
	for(int i=0;i<n;i++)scanf("%d",h+i);
	int l=1,m,r=1e9;
	while(l<r)
	{
		m=(l+r)>>1;
		if(ok(m))r=m;
		else l=m+1;
	}
	printf("%d\n",r);
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define Imposter ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long int
#define sni(x) scanf("%lld",&x) 
#define pni(x) printf("%lld ",x) 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
using namespace std;
#define f(n) for(ll i=0;i<n;i++)
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define vll vector<ll>
#define vlll vector<vll>
#define all(x) x.begin(),x.end()
#define endl "\n"
#define MX 300005
ll power(ll x, ll y, ll p) { 
    ll res = 1;    x = x % p;  
    while(y > 0) {
        if(y & 1) res = (res*x) % p; 
        y = y>>1;    x = (x*x) % p; 
    } return res; 
}
int main()
{
    
    Imposter
    
    ll n;
    cin>>n;
    ll a[n];
    input(a,n);
    ll ans=a[0];
    rep(i,1,n) ans=__gcd(a[i],ans);
    cout<<ans<<endl;
    
}

Measured memory_bytes: 4372
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
// #define int long long
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)

struct Data{
    string city;
    int ex_pos; // 元の位置
    int num; // 実際のデータ
};

bool wayToSort(const Data &SP, const Data &SP2) {
  if (SP.city == SP2.city){
    return SP.num > SP2.num;
  }else{
    return SP.city < SP2.city;
  }
};

int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

int main(int argc, const char * argv[]) {

  	string S;
    cin >> S;
    int k = S.length();
    int res=15-k;
    rep(i,k){
      if( S[i] == 'o'){
          res+=1;
      }
    }

    if ( res >= 8){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string s;
    cin >> s;
    long long k;
    cin >> k;
    long sum = 0;long i = 0;int n = 1;
    bool frag = false; 
    while(!frag and i < k){
        if(s.at(i) != '1'){
            frag = true;
            n = s.at(i) - '0';
        }
        sum += 1;
        i++;
    }
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	
	int a, b;
	cin >> a >> b;
	cout << (a+b+1)/2 << endl;
	
	return 0;
}

Measured memory_bytes: 256
import math
k=int(input())
sum1=0
sum2=0
for a in range(1,k+1):
    for b in range(1,k+1):
        sum1=math.gcd(a,b)
        for c in range(1,k+1):
            sum2+=math.gcd(sum1,c)
print(sum2)

Measured memory_bytes: 9068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	int n;cin>>n;
	ll m,a;cin>>m;
	priority_queue<ll> q;
	rep(i,n) {
		cin>>a;
		q.push(a);
	}

	rep(i,m){
		ll mx=q.top();
		q.pop();
		mx/=2;
		q.push(mx);
	}
	ll ans=0;
	rep(i,n) {
		ll j=q.top();
		q.pop();
		ans+=j;
	};

	cout<<ans<<"\n";

}

Measured memory_bytes: 1400
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,b,c;
    cin>>a>>b>>c;
    
    bool flag=0;
    if (a<b) {
        if (a<c&&c<b) flag=1;
    } else {
        if (b<c && c<a) flag=1;
    }
    if (flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

typedef struct node{
  int id;
  int k;
  int sibling;
  struct node *right;
  struct node *left;
  struct node *p;
}node;

int getsibling(node);
int getdegree(node);
int getdepth(node);
int getheight(node*);
char* gettype(node);

int main(){

  int i;
  int n,id,left,right;

  //input
  scanf("%d",&n);
  node tree[n];
  for(i=0;i<n;i++){
    tree[i].p=NULL;
  }
  for(i=0;i<n;i++){
    scanf("%d%d%d",&id,&left,&right);
    tree[id].id=id;
    tree[id].k=0;
    //left
    if(left!=-1) tree[id].k++;
    tree[id].left=malloc(sizeof(node));
    tree[id].left=&tree[left];
    tree[left].sibling=right;
    tree[id].left->id=left;
    tree[left].p=&tree[id];
   
    //right
    if(right!=-1) tree[id].k++;
    tree[id].right=malloc(sizeof(node));
    tree[id].right=&tree[right];
    tree[right].sibling=left;
    tree[id].right->id=right;
    tree[right].p=&tree[id];
  }
  //output
  for(i=0;i<n;i++){
    printf("node %d: ",i);
    if(tree[i].p==NULL) printf("parent = -1, ");
    else printf("parent = %d, ",tree[i].p->id);
    printf("sibling = %d, ",getsibling(tree[i]));
    printf("degree = %d, ",getdegree(tree[i]));
    printf("depth = %d, ",getdepth(tree[i]));
    printf("height = %d, ",getheight(&tree[i]));
    printf("%s",gettype(tree[i]));
    printf("\n");
  }
  return 0;
}

int getsibling(node tree){
  if(tree.p==NULL) return -1;
  return tree.sibling;
}

int getdegree(node tree){
  return tree.k;
}
int getdepth(node tree){
  int count=0;
  node *q;
  
  if(tree.p==NULL) return 0;
  q=&tree;
  while(q->p!=NULL){
    q=q->p;
    count++;
  }
  return count;
}

int getheight(node *tree){
  int lh=0,rh=0;
  if(tree->k==0) return 0;
  lh=1+getheight(tree->left);
  rh=1+getheight(tree->right);
  if(lh>rh) return lh;
  return rh;
}
char* gettype(node tree){
  if(tree.p==NULL) return "root";
  if(tree.k>=1) return "internal node";
  else return "leaf";
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=1e6;
int n,k,a[N],z[2]={1,-1},laz;
char s[N];
int main(){
    cin>>n>>k>>s;
    for (int i=0; i<n; ++i)
	a[i+1]=s[i]-'A';
    int l=1,r=n,cnt=0;
    while(k&&cnt<2*n){
	--k,++cnt;
	if (a[l]==laz)
	    a[l]^=1;
	else
	    ++l,++r,laz^=1,a[r]=laz;
    }
    if (k&1)
	if (a[l]==laz)
	    a[l]^=1;
	else
	    ++l,++r,laz^=1,a[r]=laz;
    for (int j=l; j<=r; ++j) putchar('A'+(a[j]^laz));
    putchar('\n');
    return 0;
}

Measured memory_bytes: 3712
N, M = map(int, input().split())
bridge = [0] * M
for i in range(M):
    bridge[i] = [0] * 2
    bridge[i][0], bridge[i][1] = map(int, input().split())
ans = 1
bridge = sorted(bridge, reverse=True)
# print(bridge)
nowcut = bridge[0][0]
for k in range(1, M):
    if bridge[k][1] <= nowcut:
        # print(nowcut)
        nowcut = bridge[k][0]
        ans += 1
print(ans)


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

int main()
{
    int n;
    cin >> n;
    vector<int> odd, even;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (i % 2 == 1)
        {
            even.push_back(x);
        }
        else
        {
            odd.push_back(x);
        }
    }

    if (n % 2 == 0)
    {
        reverse(even.begin(), even.end());
        for (int i = 0; i < even.size(); i++)
        {
            cout << even[i] << " ";
        }
        for (int i = 0; i < odd.size(); i++)
        {
            cout << odd[i] << " ";
        }
        cout << endl;
    }
    else
    {
        reverse(odd.begin(), odd.end());
        for (int i = 0; i < odd.size(); i++)
        {
            cout << odd[i] << " ";
        }
        for (int i = 0; i < even.size(); i++)
        {
            cout << even[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3188
#include<stdio.h>
int main(){
  int n,i,j,M=1000000;
  char p[1000010]={1,1};
  for(i=2;i*i<M;i++){
    if(p[i])continue;
    for(j=i*i;j<M;j+=i)p[j]=1;
  }
  while(scanf("%d",&n),n){
    for(i=j=0;n;i++){
      n-=1-p[i];
      j+=(1-p[i])*i;
    }
    printf("%d\n",j);
  }
  return 0;
}

Measured memory_bytes: 1580