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

using namespace std;

int main()
{
  int n;
  scanf("%d",&n);
  int sum =0;
  int max =0;
  int element;
  for(int i=0;i<n;i++)
  {
     scanf("%d",&element);
     sum+=element;
     if(element>=max)
     max= element;
  }
  sum -= (max/2);
  printf("%d",sum);


}

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

typedef long long ll;
const int N = 1e5;

int main()
{
    //ifstream cin("input.txt");

    int n;
    ll mnx = 2, mxx = 2, a[N];
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    if (a[n - 1] != 2)
    {
        cout << -1;
        return 0;
    }
    for (int i = n - 2; i >= 0; --i)
    {
        //cout << mnx << ' ' << mxx << '\n';
        mnx = ((mnx + a[i] - 1) / a[i]) * a[i];
        mxx = ((mxx + a[i + 1] - 1) / a[i]) * a[i];
        if (mnx > mxx)
        {
            cout << -1;
            return 0;
        }
    }
    cout << mnx << ' ' << mxx + a[0] - 1;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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

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

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void comb_init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long comb(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    comb_init();
    ll ans = 0;
    for(int i=0;i<k;i++){
        ans = comb(n-k+1,i+1) * comb(k-1,i);
        ans %= MOD;
        cout<<ans<<endl;
    }
}

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

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    ll ans = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
        ll t = s[i] - '0';
        for (int j = i + 1; j <= n; ++j) {
            ll l = 1 << i;
            ll r = 1 << max(0, n - j - 1);
            ans += t * l * r;
            t *= 10;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
 
int main() {
  int h, m, s;
  cin >> s;
  
  h = s / 3600;
  m = s % 3600 / 60;
  s = s % 60;

  cout << h << ":" << m << ":" << s << endl;

  return 0;		 
}


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

int main() {
	string in;
	int n,m,i,ans=0;
	cin>>in;
	n=in.size();
	m=n/2;
	if(n%2) {
		if(in[m]=='('||in[m]==')') {
			ans++;
		}
	}
	for(i=0;i<m;i++) {
		if(!(
			(in[i]=='w'&&in[n-1-i]=='w')
			||
			(in[i]=='i'&&in[n-1-i]=='i')
			||
			(in[i]=='('&&in[n-1-i]==')')
			||
			(in[i]==')'&&in[n-1-i]=='(')
			)) {
				ans++;
			}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1184
package main

import (
	"bufio"
	"container/list"
	"fmt"
	"os"
	"strconv"
)

var graph map[int]map[int]bool

func initGraph(x int) {
	graph = make(map[int]map[int]bool, x)
}

func add(from, to int) {
	if _, ok := graph[from]; !ok {
		graph[from] = make(map[int]bool)
	}
	graph[from][to] = true
}

func main() {
	var n, x, y int
	fmt.Scan(&n, &x, &y)

	initGraph(n)
	for i := 1; i < n; i++ {
		add(i, i+1)
		add(i+1, i)
	}
	add(x, y)
	add(y, x)

	ans := make([]int, n+1)
	for i := 1; i <= n; i++ {
		seen := make([]int, n+1)
		seen[i] = 1
		ls := list.New()
		ls.PushBack(i)
		for ls.Len() > 0 {
			v := ls.Remove(ls.Front()).(int)
			for t := range graph[v] {
				if seen[t] > 0 {
					continue
				}
				seen[t] = seen[v] + 1
				ans[seen[t]-1]++
				ls.PushBack(t)
			}
		}
	}

	var wr = bufio.NewWriter(os.Stdout)
	for i := 1; i < n; i++ {
		wr.WriteString(strconv.Itoa(ans[i]/2) + "\n")
	}
	wr.Flush()
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++) 
#define fs first
#define sc second

// 1次元vectorの出力
template <class S>
void print(vector<S> &v) {
  for (ll i = 0; i < (ll)v.size(); i++) {
    cerr << v[i] << ' ';
  }
  cerr << endl;
}

// 2次元vectorの出力
template <class S>
void print(vector<vector<S>> &v) {
  for (ll i = 0; i < (ll)v.size(); i++) {
    for (ll j = 0; j < (ll)v[i].size(); j++) {
      cerr << v[i][j] << ' ';
    }
    cerr << endl;
  }
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int gcd3(int a, int b, int c){
	return gcd(gcd(a,b),c);
}

int main(void) {
	int k;
	cin >> k;
	ll ans = 0;
	for(int i=1; i<=k; i++){
		for(int j=1; j<=k; j++){
			for(int l=1; l<=k; l++){
				ans += gcd3(i,j,l);
			}
		}
	}
	cout  << ans << endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;

int N, K;
vector<int> A;

bool check(int d){
    vector<int> a(N, 0);
    for(int i=0; i<N; i++){
        a[i] = A[i]%d;
    }
    sort(a.begin(), a.end());

    vector<int> accum(N, 0);
    accum[0] = a[0];
    for(int i=1; i<N; i++){
        accum[i] = accum[i-1] + a[i];
    }

    for(int i=0; i<N-1; i++){
        ll minus = accum[i];
        ll plus = d*(N-i-1) - (accum[N-1] - accum[i]);
        if(minus > plus) swap(minus,plus);

        if((plus - minus)%d == 0 && plus <= K) return true;
    }
    return false;
}

int main(){
    cin >> N >> K;
    A.resize(N);
    int sum = 0;
    for(int i=0; i<N; i++){
        cin >> A[i];
        sum += A[i];
    }
    vector<int> div;
    for(int i=1; i*i <= sum; i++){
        if(sum%i==0){
            div.push_back(i);
            if(i != sum/i) div.push_back(sum/i);
        }
    }

    int ans = 0;
    for(int d: div){
        if(check(d)){
            ans = max(ans, d);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
/*=======================
Author    : Shounak Dey
Filename  : a.cpp
=======================	*/

#include<bits/stdc++.h>

using namespace std;

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

#define PB push_back
#define MK make_pair 
#define SZ(a) (int)(sizeof(a))
#define F first
#define S second
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define read(n) scanf("%d",&n)
#define readl(n) scanf("%lld",&n)
#define readul(n) scanf("%llu",&n);


#define SORTV(a) sort(a.begin(),a.end())
#define TEST int Test;cin >> Test;while(Test--)
#define gcd(a,b) __gcd(a,b)
#define ffs(a) __builtin_ffs(a) // find first set
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)


#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

vector<string> split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

int main()
{
	fast_io;
	ll n,m;
	cin >> n >> m;
	ll ans = (n*(n-1))/2 + (m*(m-1))/2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
// ABC045 A - 台形

#include <stdio.h>

int main(void)
{
    int a, b, h;
    int result = 0;

    // input
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &h);

    result = (a + b) * h / 2;

    // output
    printf("%d\n", result);

    return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python3
A, B, C = map(int, input().split())
m = min(B, C)
ans = m * 2
B = max(0, B - m)
C = max(0, C - m)
ans += B
ans += min(A, C)
C = max(0, C - A)
ans += C > 0
print(ans)


Measured memory_bytes: 3060
/*;

THE BEST IS YET TO COME
*/
#include <bits/stdc++.h>
using namespace std;
#define r(i, s, l) for (int i = s; i < l; i++)
#define mod 1000000007
#define int long long
#define INT_BITS 32
#define ld long double
#define pp pair<int,int>
#define ss second
#define ff first
#define INF 1e18
#define N 2000005
#define all(a) a.begin(), a.end()
#define pb push_back
using namespace std;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

signed main()
{


    int x,y;
    cin>>x>>y;
    cout<<x*y;
	return 0;
}


Measured memory_bytes: 3636
#include<stdio.h>
#include <stdlib.h>
#define NIL NULL
struct Node{
  int key;
  struct Node *p,*l,*r;
};

 struct Node* root;

void insert(int);
void inorder(struct Node*);
void preorder(struct Node*);
struct Node* find(struct Node*,int);
int main(){
  int m,x;
  int i,j=0,c=0;
  char k[10];

  scanf("%d",&m);
  for(i=0; i < m; i++){
    scanf("%s",k);
     if(k[0]=='f'){
      scanf("%d",&x);
      if(find(root,x)!=NIL)
        printf("yes\n");
      else printf("no\n");
     }
     else if(k[0]=='i'){
      scanf("%d",&x);
      insert(x);
     }

     else if(k[0]=='p'){
      if(root !=NIL)
      inorder(root);
      printf("\n");
      if(root!=NIL)
      preorder(root);
      printf("\n");
       }
       }

  return 0;
  }



void insert(int a){
  struct Node *y=NIL;
  struct Node *x=root;
  struct Node *z;

  z=malloc(sizeof(struct Node));
  z->key=a;
  z->l=NIL;
  z->r=NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key) x=x->l;
    else x=x->r;
  }
  z->p=y;

  if(y==NIL) root=z;
  else if(z->key < y->key){
      y->l=z;
    }
  else y->r =z;

}

void inorder(struct Node *x){
  if(x == NIL) return;
  inorder(x->l);
  printf(" %d",x->key);
 inorder(x->r);
}

void preorder(struct Node *x){
  if(x==NIL) return;
  printf(" %d",x->key);
  preorder(x->l);
  preorder(x->r);
}

struct Node* find(struct Node *x,int k){
  while(x !=NIL && k !=x->key){
    if(k < x->key) x=x->l;
    else x=x->r;
  }
  return x;
}

Measured memory_bytes: 19360
inputs = []
while True:
  try:
    inputs.append(input())
  except EOFError:
    break

# print(inputs)

people = eval(inputs[0].split(" ")[0])
snack = eval(inputs[0].split(" ")[1])

having_snacks = [[eval(i) for i in a.split(" ")] for a in inputs[2::2]]
having_snacks = set(sum(having_snacks, []))

print(people - len(having_snacks))


Measured memory_bytes: 9148
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	A, B, C, D := nextInt(), nextInt(), nextInt(), nextInt()

	if A + B > C + D {
		fmt.Println("Left")
	} else if A + B == C + D {
		fmt.Println("Balanced")
	} else {
		fmt.Println("Right")
	}
}


Measured memory_bytes: 640
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
while(a>0&&c>0){
    c-=b;
    if(c>0)a-=d;
}
if(a>0)cout<<"Yes";
else cout<<"No";
return 0;
}


Measured memory_bytes: 3672
import java.io.FileInputStream;
import java.io.InputStream;
import java.util.Scanner;

public class Main {
	static Scanner sc;

	public static void main(String[] args) throws Exception {
		//InputStream in = new FileInputStream("src/input.txt");
		InputStream in = System.in;

		sc = new Scanner(in);

		String N = sc.next();

		int a = N.charAt(0) - '0';
		int b = N.charAt(1) - '0';
		int c = N.charAt(2) - '0';
		int d = N.charAt(3) - '0';

		for(int i = 0; i < 16; i++){
			String bin = String.format("%4s",Integer.toBinaryString(i)).replaceAll(" ", "0");
			//System.out.println(bin);
			int aa = bin.charAt(0) - '0';
			int bb = bin.charAt(1) - '0';
			int cc = bin.charAt(2) - '0';
			int dd = bin.charAt(3) - '0';
			//aa=check(aa);
			bb=check(bb);
			cc=check(cc);
			dd=check(dd);
			//System.out.println(a*aa+b*bb+c*cc+d*dd);
			if(a+b*bb+c*cc+d*dd == 7){
				System.out.println(a + out(bb) + b + out(cc) + c + out(dd) + d + "=7");
				break;
			}
		}
	}
	static int check(int i){
		if(i == 0){
			return -1;
		}else{
			return 1;
		}
	}

	static String out(int i){
		if(i == -1){
			return "-";
		}else{
			return "+";
		}
	}

}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i = 0; i<(ll)(n); i++)
#define REPS(i,n) for (ll i = 1; i<=(ll)(n); i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353
#define PI 3.141592653
#define INF 100000000000000

int main(){
	vector<vector<vector<ll>>> conn(50);
	vector<vector<ll>> exch(50,vector<ll>(2));
	vector<ll> ansl(250000,INF);
	priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> q;
	ll n, m, s, u, v, x, y, a, b, c, d; cin >> n >> m >> s;
	ll slim = 4999;
	s = min(s,slim);
	REP(i,m){
		cin >> u >> v >> a >> b; u--; v--;
		conn[u].pb({v,a,b});
		conn[v].pb({u,a,b});
	}
	REP(i,n) cin >> exch[i][0] >> exch[i][1];
	q.push({0,s});
	while(q.size()){
		ll nmin = q.top().at(0);
		ll nnod = q.top().at(1);
		//cout << nmin << " " << nnod << "check" << endl;
		ll nowat = nnod/5000;
		x = min(nnod+exch[nowat][0],5000*nowat+4999);
		y = nmin+exch[nowat][1];
		if (y<ansl[x]){
			ansl[x]=y;
			q.push({y,x});
			//cout << y << " " << x << endl;
		}
		REP(i,conn[nowat].size()){
			if (nnod%5000>=conn[nowat][i][1]){
				x = nnod-conn[nowat][i][1]+5000*(conn[nowat][i][0]-nowat);
				y = nmin+conn[nowat][i][2];
				if (y<ansl[x]){
					ansl[x]=y;
					q.push({y,x});
				}
			}
		}
		q.pop();
	}
	FOR(i,1,n-1){
		ll ans = INF;
		REP(j,5000){
			ans = min(ans,ansl[i*5000+j]);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 15576
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);

int extgcd(int a, int b, int &x, int &y){
    int d = a;
    if(b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1;
        y = 0;
    }
    return d;
}

bool ans(int A, int B, int C, int D){
    if(A < B || D < B) return false;
    if(C > B) return true;

    int a = A % B;
    int d = D % B;

    // C < (a + kd) mod B < B とできるならfalse
    if(d == 0){
        if(C < a){
            return false;
        }else{
            return true;
        }
    }
    int x, y;
    int g = extgcd(d, B, x, y);
    int h = (B - 1 - a) / g;
    //(a + kd) mod Bの最大値はa+hg
    if(C < a + h * g){
        return false;
    }else{
        return true;
    }
}

signed main(){

    int T;
    cin >> T;
    int A, B, C, D;
    REP(i, T){
        cin >> A >> B >> C >> D;
        if(ans(A, B, C, D)){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 256
n = int(input())

a_input = list(map(int,input().split()))

min_sum = 1000000000

for i in range(min(a_input), max(a_input)+1):
    tmp_sum=0
    for j in range(n):
        tmp_sum += (a_input[j]-i)**2
    
    min_sum = min(min_sum, tmp_sum)

print(min_sum)

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

using namespace std;

int main() {
  int N, K; cin >> N >> K;
  string S; cin >> S;
  string ans;
  for(int i = 0; i < N; ++i) {
    if(i == K-1) ans.push_back(tolower(S[i]));
    else ans.push_back(S[i]);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {

    public static void main(String args[]){
        Main main = new Main();
    }

    public Main(){
        Scanner SC = new Scanner(System.in);
        int N = Integer.parseInt(SC.next());
        int M = Integer.parseInt(SC.next());

        int[] NUM = new int[N];
        boolean[] T = new boolean[N];
        for(int i=0;i<N;i++) T[i] = false;

        int A = 0;
        int P = 0;
        for(int i=0;i<M;i++){
            int p = Integer.parseInt(SC.next())-1;
            boolean S = SC.next().equals("AC");
            if(T[p]) continue;

            if(S){
                A++;
                P += NUM[p];
            }
            else {
                NUM[p]++;
            }

            T[p] = S;
        }

        System.out.println(A + " " + P);
    }

}


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

const int MOD = 1000000007;

class ModInt
{
public:
    int64_t x;
    ModInt(int64_t x = 0) : x((x % MOD + MOD) % MOD) {}
    ModInt operator-() const { return ModInt(-x); }
    ModInt &operator+=(const ModInt a)
    {
        if ((x += a.x) >= MOD)
            x -= MOD;
        return *this;
    }
    ModInt &operator-=(const ModInt a)
    {
        if ((x += MOD - a.x) >= MOD)
            x -= MOD;
        return *this;
    }
    ModInt &operator*=(const ModInt a)
    {
        (x *= a.x) %= MOD;
        return *this;
    }
    ModInt operator+(const ModInt a) const { return ModInt(*this) += a; }
    ModInt operator-(const ModInt a) const { return ModInt(*this) -= a; }
    ModInt operator*(const ModInt a) const { return ModInt(*this) *= a; }
    ModInt pow(int64_t n) const
    {
        if (n == 0)
            return 1;
        ModInt t = pow(n >> 1);
        t *= t;
        if (n & 1)
            t *= *this;
        return t;
    }
    ModInt inv() const { return pow(MOD - 2); }
    ModInt &operator/=(const ModInt a) { return *this *= a.inv(); }
    ModInt operator/(const ModInt a) const { return ModInt(*this) /= a; }
};
istream &operator>>(istream &is, const ModInt &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x; }

vector<ModInt> fac;
vector<ModInt> fac_inv;
vector<ModInt> inv;
void init_comb(int mx)
{
    fac = vector<ModInt>(mx + 1), fac_inv = vector<ModInt>(mx + 1), inv = vector<ModInt>(mx + 1);
    fac.at(0) = fac.at(1) = 1;
    fac_inv.at(0) = fac_inv.at(1) = 1;
    inv.at(1) = 1;
    for (int i = 2; i <= mx; i++)
    {
        fac.at(i) = fac.at(i - 1) * i;
        inv.at(i) = -inv.at(MOD % i) * (MOD / i);
        fac_inv.at(i) = fac_inv.at(i - 1) * inv.at(i);
    }
}
ModInt comb(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac.at(n) * fac_inv.at(k) * fac_inv.at(n - k);
}

void solve(int S)
{
    init_comb(4000);
    ModInt res = 0;
    for (int l = 1; l <= S / 3; l++)
    {
        int t = S - 3 * l;
        res += comb(t + l - 1, l - 1);
    }
    cout << res << endl;
}

int main()
{
    int S;
    cin >> S;
    solve(S);
    return 0;
}


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

int gcd(int a, int b)
{
    if(a<b)
    {
        swap(a,b);
    }
    if(b <= 0)
    {
        return a;
    }
    int x,y;
    x = a;
    y = b;
    while(x%y!=0)
    {
        a = y;
        b = x%y;
        x = a;
        y = b;
    }
    return y;
}

int main()
{
    int n;
    cin >> n;
    vector<int> num(n);
    vector<int> l(n+1);
    vector<int> r(n+1);
    for(int i = 0; i < n; ++i)
    {
        int t;
        cin >> t;
        num[i] = t;
        l[i+1] = gcd(t,l[i]);
    }
    for(int i = n-1; i >= 0; --i)
    {
        int t = num[i];
        r[i] = gcd(t,r[i+1]);
    }
    int ans = 1;
    for(int i = 0; i < n; ++i)
    {
        int t = gcd(l[i],r[i+1]);
        ans = ans < t ? t : ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define ll long long
#define debug(x) cout<<x<<endl;
ll lcm(ll x,ll y){
	return x*y/(ll)(__gcd(x,y));
}
int main(){
	ll a,b,c,d; cin>>a>>b>>c>>d;
	ll tn=b-a+1;
	ll dc=b/c-(a-1)/c;
	ll dd=b/d-(a-1)/d;
	ll lc=lcm(c,d);
	ll dbc=b/(lc)-(a-1)/(lc);
	ll td=dd+dc-dbc;
/*	debug(tn);
	debug(dc);
	debug(dd);
	debug(dbc);
	debug(td);*/
	cout<<tn-td<<endl;
}


Measured memory_bytes: 3592
use std::io;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let iter = buf.split_whitespace();
	let mut v: Vec<T> = Vec::new();
	for i in iter {
		v.push(i.parse().ok().unwrap());
	}
	v
}

fn main() {
	let x:i32 = procon_read()[0];
	if x < 1200 {
		println!("ABC");
	}else{
		println!("ARC");
	}
}

Measured memory_bytes: 4352
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  string s,t,u;
  int ans=0;
  cin >> s;
  t="",u="";
  for(int i=0; i<s.size(); i++) {
    t+=s[i];
    if(t!=u) {
      u=t;
      t="";
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;cin>>S;int N=S.length();
  vector<int>A(N,0);
  int rl=-1;
  for(int i=1;i<N;i++){
    if(S[i-1]=='R'&&S[i]=='L')rl=i;
    if(S[i]=='L')A[rl-(i-rl)%2]++;
  }
  int lr=-1;
  for(int i=N-2;i>=0;i--){
    if(S[i]=='R'&&S[i+1]=='L')lr=i;
    if(S[i]=='R')A[lr+(lr-i)%2]++;
  }
  for(int i=0;i<N;i++)cout<<A[i]<<" "; 
}

Measured memory_bytes: 1024
R,G,B,N = map(int, input().split())
count = 0

for r in range(N//R+1):
    if R*r> N:
         break
    for g in range(N//G+1):
        aa = N-R*r- G*g
        if aa < 0:
            break
        if aa %B == 0 :
            count += 1
print(count)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    long long x,y,a,b,c,z,s=0;
    priority_queue<pair<int,int>> aa;
    cin>>x>>y>>a>>b>>c;
    for(int i=0;i<a;i++){
        cin>>z;
        aa.push(make_pair(z,1));
    }
    for(int i=0;i<b;i++){
        cin>>z;
        aa.push(make_pair(z,2));
    }
    for(int i=0;i<c;i++){
        cin>>z;
        aa.push(make_pair(z,3));
    }
    a=b=c=0;
    while(a+b+c<x+y){
        if(aa.top().second==1){
            if(a<x){
                a++;
                s+=aa.top().first;
            }
        }else if(aa.top().second==2){
            if(b<y){
                b++;
                s+=aa.top().first;
            }
        }else{
            c++;
            s+=aa.top().first;
        }
        aa.pop();
    }
    
    cout<<s<<'\n';
    return(0);
}


Measured memory_bytes: 7404
S = gets.chomp

class String
  def c1?
    self[0] == "A"
  end

  def c2?
    self[2..(self.length - 2)].chars.select { |c| c == "C" }.size == 1
  end

  def c3?
    tmp = self.sub("A", "").sub("C", "")
    tmp == tmp.downcase
  end
end

puts S.c1? && S.c2? && S.c3? ? "AC" : "WA"


Measured memory_bytes: 1788
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <math.h>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

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

    int K, S;
    cin >> K >> S;
    int cnt=0;
    rep(i,K+1){
        rep(j,K+1){
            int k = S - (i + j);
            if(k <= K && k >= 0) cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;

int n, x; 
int a[60];
int p[60];

int f(int n, int x){
    if(n==0){
        if(x<=0) return 0;
        else return 1;
    }
    if(x<=a[n-1]+1) return f(n-1, x-1);
    if(x==a[n-1]+2) return p[n-1] + 1;
    if(x<=2*a[n-1]+1) return p[n-1] + 1 + f(n-1, x-a[n-1]-2);
    else return 2*p[n-1] + 1;
}

signed main(){
    cin >> n >> x;
    a[0] = 1;
    p[0] = 1;
    for(int i=1; i<=n; ++i){
        a[i] = 2*a[i-1] + 3;
        p[i] = 2*p[i-1] + 1;
    }
    cout << f(n, x) << endl;

    return 0;
}

Measured memory_bytes: 256
import Data.List
import Control.Monad
main=do
 n<-readLn
 a<-group.sort<$>replicateM n getLine
 m<-readLn
 b<-group.sort<$>replicateM m getLine
 print.maximum$0:(map(\s->(length s)+sum(map(\t->if (head s)/=(head t)then 0 else -length t)b))a)++
  (map(\t-> -(length t)+sum(map(\s->if (head s)/=(head t)then 0 else length s)a))b)


Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long int
#define fi first
#define se second
#define pub push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for(int i=(int)(l);i<(int)(r);i++)
#define repd(i, l, r) for (int i=(int)(l);i>=(int)(r);i--)
#define clrg(i, l, r) for(int i=(int)(l);i<(int)(r);i++)vis[i]=0,v[i].clear();
int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}
#define print2d(mat,n,m){for(int i=0;i<(int)(n);i++){for(int j=0;j<(m);j++){cout<<mat[i][j]<<" ";}cout<< endl;}}
#define clr(a,x) memset(a,x,sizeof(a))
#define rr(v) for(auto &val:v)
#define print(v) for (const auto itr : v){cout<<itr<<' ';}cout<<"\n";
#define ln length()
#define sz size()
#define mod 1000000007
#define elif else if
int dp[100005][5],n;
vector<int> a,b,c;
int solve(int i,int act){
  if(i==n)return 0;
  if(dp[i][act]!=-1)return dp[i][act];
  int ans=0;
  if(act==0){
    ans=max(ans,solve(i,1));
    ans=max(ans,solve(i,3));
    ans=max(ans,solve(i,2));
  }
  elif(act==1){
      ans=max(ans,a[i]+solve(i+1,3));
      ans=max(ans,a[i]+solve(i+1,2));
  }
  elif(act==2){
       ans=max(ans,b[i]+solve(i+1,3));
        ans=max(ans,b[i]+solve(i+1,1));
  }
  elif(act==3){
       ans=max(ans,c[i]+solve(i+1,1));
      ans=max(ans,c[i]+solve(i+1,2));
  }
  dp[i][act]=ans;
  return ans;
}
int32_t main(){
   cin>>n;
   rep(i,0,n){
     int t; cin>>t;
     a.pub(t);
     cin>>t; b.pub(t);
     cin>>t; c.pub(t);
   }
   clr(dp,-1);
   cout<<solve(0,0);
   return 0;
}
/*
Edge cases? n=1? a[i]<=0?
long vs int? 1LL? 64bits?
Re-read problem. Is it as easy as it seems?
KEEP CORRECTING AND SUBMITTING!
*/


Measured memory_bytes: 14224
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iomanip>
#include <queue>
#include <algorithm>
#include <functional>
#include <vector>
#include <math.h>
#include <numeric>
#include <stack>
#include <map>
using namespace std;

int K, X;

int main(){
    cin >> K >> X;
    for (int i=X-K+1; i<=X+K-1; i++){
        cout << i << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Y;
    cin >> N >> Y;
    rep(i, N+1) {
        rep(j, N+1) {
            if (i + j > N) break;
            int k = N - i - j;
            int tmp = 10000*i + 5000*j + 1000*k;
            //dump(tmp);
            if (tmp == Y) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1" << " " <<"-1" << " " <<"-1" << endl;

    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
f=0
mi=0
pr=[]
for i in range(n):
  if a[i]-b[i]<0:
    mi+=(b[i]-a[i])
    f+=1
  else:
    pr.append(a[i]-b[i])
if f==0:
  print(0)
  exit()
if sum(pr)<mi:
  print(-1)
  exit()
pr.sort(reverse=True)
p=0
for i in range(len(pr)):
  p+=pr[i]
  f+=1
  if p>=mi:
    break
print(f)

Measured memory_bytes: 18356
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int a, b; cin >> a >> b;
    rep(i,2000) {
        // cout << i << " " << (int)(i*0.08) << " " << (int)(i*0.1) << endl;
        if ((int)(i*0.08) == a && (int)(i*0.1) == b) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
typedef long long int ll;
typedef unsigned long long int ull;
const long long int m=pow(10,9)+7;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,c;
    ull k;
    cin>>a>>b>>c>>k;
    if(a==b)
        cout<<0<<endl;
    else
    {
        if(k%2==0)
            cout<<a-b<<endl;
        else
            cout<<b-a<<endl;
    }
    return 0;
}

Measured memory_bytes: 3636
N = int(input())
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
X = list(pf.values())
ans = 0
for i in X:
    temp = 1
    while i>=temp:
        i -= temp
        temp += 1
        ans += 1
print(ans) 

Measured memory_bytes: 9464
#include <bits/stdc++.h>
using namespace std;
#define MAX_I 32
typedef long long ll;
typedef pair<ll, ll> P;
ll N;
string s;
P p[MAX_I];
bool rec = false;

int main(void){
	p[0].first = 0; p[0].second = 1;
	ll a = 1;
	for(ll i=1; i<MAX_I; i++){
		a *= -2;
		p[i].first = (i%2==1) ? p[i-1].first + a : p[i-1].first;
		p[i].second = (i%2!=1) ? p[i-1].second + a : p[i-1].second;
		// cout << p[i].first << ' ' << p[i].second << endl;
	}
	cin >> N;
	for(ll i=MAX_I-1; i>=1; i--){
		if(p[i].first <= N && N <= p[i].second){
			if(p[i-1].first <= N && N <= p[i-1].second){
				if(rec) s += '0';
			}else{
				rec |= true;
				s += '1';
				N -= pow(-2, i);
			}
		}
	}
	if(N == 1) s += '1';
	else s += '0';
	cout << s << endl;
}

Measured memory_bytes: 256
// Kongo Type

// 素直に実装
// ffffffff = -16777215.9921875

#include<iostream>
#include<bitset>
#include<cmath>
using namespace std;

bitset<32> hexToBin(string hex) {
    bitset<32> bin;
    for(int i=0; i<hex.size(); i++) {
        int dec;
        if(isdigit(hex[i])) dec = hex[i]-'0';
        else dec = hex[i]-'a'+10;
        bitset<32> bits(dec);
        bits <<= (hex.size() - 1 - i)*4;
        bin |= bits;
    }
    return bin;
}

int main()
{
    int Q;
    string s;
    cin>>Q;
    while(Q-->0) {
        cin>>s;
        bool sign;
        int integer=0;
        int decimal=0;
        bitset<32> bin = hexToBin(s);
        int pow;
        sign = bin[31];
        pow = 1;
        for(int i=7; i<31; i++) {
            integer += pow*bin[i];
            pow <<= 1;
        }
        pow = 5000000;
        for(int i=0; i<7; i++) {
            decimal += pow*bin[6-i];
            pow /= 10;
            pow *= 5;
        }
        int digits=7-log10(decimal);
        while((decimal%10==0) && decimal!=0) decimal/=10;
        cout<<(sign?"-":"")<<integer<<".";
        while(digits-->0) cout<<"0";
        cout<<decimal<<endl;
    }
}

Measured memory_bytes: 1256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
  long long ans=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      ans+=(v[i]*v[j]);
    }}
  cout<<ans;
}

Measured memory_bytes: 256
import bisect

n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for b in B:
    ans += bisect.bisect_left(A, b) * (n - bisect.bisect_right(C, b))
    
print(ans)

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

int main(){
  int n;
  cin >> n;
  for(int i=1;i<10;i++){
    if(n%i == 0 && n/i <= 9){
      cout<<"Yes";
      return 0;
    }
  }
  cout<<"No";
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
#define fi first
#define se second

signed main(){
	int a,b,s=0,sum=0;
	cin>>a>>b;
	r(i,a){
		int x;
		cin>>x;
		s+=x;
	}
	r(j,b){
		int x;
		cin>>x;
		sum+=s*x;
	}
	cout<<sum<<endl;
}


Measured memory_bytes: 3108
#include <iostream>                                                                                                                                           
    
int main() {    
    int max = 0;    
    char c;    
    int tmp = 0;    
    while (std::cin >> c) {    
        switch(c) {    
            case 'A': case 'T':    
            case 'G': case 'C':    
                tmp++;    
                max = (tmp > max) ? tmp : max;    
                break;    
            default:    
                tmp = 0;    
                break;    
        }    
    }    
    std::cout << max << std::endl;    
}    


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
char arr[n];
int count=1;
scanf("%c",&arr[0]);
scanf("%c",&arr[0]);
char current=arr[0];
for(int i=1;i<n;i++)
{
  scanf("%c",&arr[i]);
  if(arr[i]!=current)
    count++;
  current=arr[i];
}
printf("%d",count);
  return 0;
}

  

Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100005
#define NIL -1

struct Node {
    int p, l, r;
};

struct Node T[MAX];
int n, D[MAX];

void depth(int, int);
void printree(int);


int main() {
    int i, j, d, v, c, l, r;
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        T[i].p = NIL;
        T[i].l = NIL;
        T[i].r = NIL;
    }
    for (i = 0; i < n; i++) {
        scanf("%d%d", &v, &d);
        for (j = 0; j < d; j++) {
            scanf("%d", &c);
            if (j == 0) T[v].l = c;
            else T[l].r = c;
            l = c;
            T[c].p = v;
        }
    }
    for (i = 0; i < n; i++) {
        if (T[i].p == NIL) r = i;
    }
    depth(r, 0);

    for (i = 0; i < n; i++) printree(i);

    return 0;
}


void depth(int u, int p) {
    D[u] = p;
    if (T[u].r != NIL) depth(T[u].r, p);
    if (T[u].l != NIL) depth(T[u].l, p+1);
}


void printree(int u) {
    int i, c;
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].p);
    printf("depth = %d, ", D[u]);

    if (T[u].p == NIL) printf("root, ");
    else if (T[u].l == NIL) printf("leaf, ");
    else printf("internal node, ");

    printf("[");

    for (i = 0, c = T[u].l; c != NIL; i++, c = T[c].r) {
        if (i) printf(", ");
        printf("%d", c);
    }
    printf("]\n");
}


Measured memory_bytes: 6404
function Main(input) {
  input = input.split("\n");
  const K = parseInt(input[0], 10);

  var s = '';

  for (var i = 0; i < K; i++) {
    s = s + 'ACL'
  }
  console.log(s)
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29572
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    int r;
    cin >> r;
    cout << r * r << endl;
}


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

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

    vector<int> arr(n);
    rep(i,n) cin >> arr[i];
    sort(arr.begin(),arr.end());

    int ans = 0;
    for(int i = 1; i < n; i++){
        if((arr[i] - arr[i-1]) * a < b){
            ans += (arr[i] - arr[i-1]) * a;
        } else {
            ans += b;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [1e10] * N
dp[0] = 0
for i in range(N):
    for j in range(i+1, i+K+1):
        if j >= N:
            break
        dp[j] = min([dp[j], dp[i]+abs(h[j]-h[i])])
print(dp[N-1])

Measured memory_bytes: 85556
/*  AtCoder Beginner Contest 133 D - Rain Flows into Dams
    2019.07.28 by meyon */

#include <stdio.h>
#include <stdlib.h>

void err()
{
  printf("Error!\n");
  exit(1);
}

int main()
{
  // input N
  int N;
  scanf("%d", &N);
  if(3>N || 99999<N || 0==N%2) {
    err();
  }

  // input A
  int A[N];
  for(int i=0; i<N; i++) {
    scanf("%d", &A[i]);
    if(0>A[i] || 1000000000<A[i]) {
      err();
    }
  }

  // rainfall X
  int X[N];
  for(int i=0; i<N; i++) {
    X[i]=0;
  }

  int S=0;
  for(int i=0; i<N; i++) {
    S += A[i];
  }
  int P=0;
  for(int i=1; i<N; i+=2) {
    P += A[i];
  }
  X[0]=S-2*P;   // X1=S-2(A2+A4+...+A[n-1])

  for(int i=0; i<N-1; i++) {
    X[i+1]=2*A[i]-X[i];   // X[i+1]=2Ai-Xi
  }

  // display answer
  for(int i=0; i<N; i++) {
    printf("%d ", X[i]);
  }
  printf("\n");

  return 0;
}


Measured memory_bytes: 2048
n = int(input())
a = list(map(int, input().split()))
p = a[0]
ans = 1
stat = 'None'
for i, ai in enumerate(a, 1):
    if stat == 'None':
        if ai < p:
            stat = 'Down'
        elif ai > p:
            stat = 'Up'
    else:
        if ai < p and stat == 'Up':
            ans += 1
            stat = 'None'
        elif ai > p and stat == 'Down':
            ans += 1
            stat = 'None'
    p = ai
print(ans)


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

int main() {
    int n;
    cin >> n;
    vector<int> w(n);
    int sum_all = 0;
    for(int i = 0; i < n; i++) {
        cin >> w.at(i);
        sum_all += w.at(i);
    }
    
    int ans = sum_all;
    int s2 = sum_all;
    for(int i = 0; i < n; i++) {
        s2 -= w.at(i);
        ans = min(ans, abs(sum_all - 2 * s2));
    }
    cout << ans << endl;
}

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

int c =0;

void func(int parr [] ,int iarr[], int len , int res[]){
  if (len == 0 ){return;}
  int root = parr[0];
  if (len >= 1){
    int i;
    for ( i = 0; i < len; i++){
      if (iarr[i] == root){break;}
    }
    int repre[i] , rein[i];
    for ( int j = 0; j <= i; j++){
      repre[j] = parr[ j +1];
      rein[j] = iarr[j];
    }
  
    func( repre,rein, i ,res);
  
    if (len - i - 1 > 0){
      int k = len - i -1;
      int rirepre[k] , rirein[k];
      for ( int j = 0; j < k; j++){
	rirepre[j ] = parr[i+ j +1];
	rirein[j] = iarr[j +i+1];
  
      }
      func( rirepre,rirein, k ,res);
    }
  }  
  //printf("%d " , root);
  res[c] = root;
  c++;
  return;
  
};



int main(){

  int n ;
  scanf ("%d\n",&n);
  int pre_arr[n];
  int in_arr[n];
  int resarr[n];
  for (int i = 0; i < n; i++){
    scanf("%d",&pre_arr[i]);
  }

    for (int i = 0; i < n; i++){
    scanf("%d",&in_arr[i]);
  }
    
    func(pre_arr , in_arr, n ,resarr);

   for (int i = 0; i < n; i++){
     printf("%d",resarr[i]);
     if (i != n-1){printf(" ");}
  }

  printf("\n");

  return 0;
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
	int N,M;
	cin >> N >> M;
	set<int> P; // 所属前のiの集合
	vector<int> G(N+1,0); // G[i]=a ... iさんはaのグループに所属、a>0, 所属無しは0
	vector<set<int> > L(N+1); // L[i] は、iから出る友達ネットワーク
	for(int i = 1; i <= M; i++){
		int a,b;
		cin >> a >> b;
		L[a].insert(b);
		L[b].insert(a);
	}
	for(int i = 1; i <= N; i++){
		P.insert(i);
	}

	int maxsz = 0;
	while(!P.empty()){
		int p = *P.begin();
		P.erase(p);
		int sz = 1;
		set<int> C;
		C.insert(p);
		while(!C.empty()){
			int c = *C.begin();
			C.erase(c);
			for(auto it = L[c].begin(); it != L[c].end(); it++){
				if(P.find(*it) != P.end()){
					C.insert(*it);
					P.erase(*it);
					sz++;
				}
			}
		}
		maxsz = (maxsz < sz ? sz :maxsz);
	}

	cout << maxsz << endl;
	return(0);
}


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

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn solve(n: usize, c3: usize, c2: usize, c1: usize, dp: &mut Vec<Vec<Vec<Option<f64>>>>) -> f64 {
    if dp[c3][c2][c1].is_some() {
        return dp[c3][c2][c1].unwrap();
    }
    if c3 == 0 && c2 == 0 && c1 == 0 {
        dp[c3][c2][c1] = Some(0.0);
        return 0.0;
    }

    let mut res = 0.0;
    res += n as f64;
    if c3 > 0 {
        res += c3 as f64 * solve(n, c3 - 1, c2 + 1, c1, dp);
    }
    if c2 > 0 {
        res += c2 as f64 * solve(n, c3, c2 - 1, c1 + 1, dp);
    }
    if c1 > 0 {
        res += c1 as f64 * solve(n, c3, c2, c1 - 1, dp);
    }
    res /= (c1 + c2 + c3) as f64;

    dp[c3][c2][c1] = Some(res);
    // println!("{}, {}, {}, {}", c3, c2, c1, res);
    return res;
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let c3 = a.iter().filter(|&v| *v == 3).count();
    let c2 = a.iter().filter(|&v| *v == 2).count();
    let c1 = a.iter().filter(|&v| *v == 1).count();

    let mut dp: Vec<Vec<Vec<Option<f64>>>> = vec![vec![vec![None; n + 1]; n + 1]; n + 1];

    println!("{}", solve(n, c3, c2, c1, &mut dp));
}


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

int main(){
    string s;
    cin >> s;
    
    int m;
    cin >> m;
    
    for(int i = 0; i < m; i++){
        string check;
        cin >> check;
        
        if(check == "replace"){
            int a, b;
            string p;
            cin >> a >> b >> p;
            s.replace(a, b-a+1, p);
        }
        else if(check == "reverse"){
            int a, b;
            cin >> a >> b;
            string t = s.substr(a, b-a+1);
            reverse(t.begin(), t.end());
            s.replace(a, b-a+1, t);
        }
        else if(check == "print"){
            int a, b;
            cin >> a >> b;
            string p = s.substr(a, b-a+1);
            cout << p << endl;
        }
    }
}


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

int main() {
  int N;
  double T,A;
  scanf("%d",&N);
  scanf("%lf %lf",&T,&A);
  int p=1;
  double min;
  for (int i = 0; i < N; i++) {
    int hight;
    double dif;
    if (i == 0) {
      scanf("%d",&hight);
      min=fabs((T-(double)hight*0.006)-A);
      //printf("%d %lf\n",hight,min);
    }
    else {
      scanf("%d",&hight);
      //printf("%d %lf %lf\n",hight,T,A);
      //printf("%lf\n",fabs(T-(double)hight*0.006)-A);
      dif=fabs((T-(double)hight*0.006)-A);
      //printf("%d %lf\n",hight,dif);
      if (min > dif) {
        min = dif;
        p = i+1;
      }
    }
  }
  printf("%d\n",p);
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define fr(i,n,m) for(ll i=n;i<m;i++)
int main()
{
    ll a,b;
    char s[10];
    scanf("%lli %s %lli", &a,s,&b);
    if(s[0] == '+') printf("%lli",a+b);
    if(s[0] == '-') printf("%lli",a-b);
    return 0;
}

Measured memory_bytes: 1684
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <numeric>

using ll = long long;

using namespace std;

string merge_two(string &s, string &t, int len) {
    string ans = s;
    auto itr = ans.begin();
    for (auto &ti:t) {
        for (itr = ans.insert(itr, ti) + 1; true; itr++) {
            cout << "? " << ans << endl;
            int resp; cin >> resp;
            if (len - resp == ans.size()) {
                break;
            }
            iter_swap(itr - 1, itr);
        }
    }
    return ans;
}

int main() {
    string chars(62, ' ');
    iota(chars.begin(), chars.begin() + 26, 'a');
    iota(chars.begin() + 26, chars.begin() + 52, 'A');
    iota(chars.begin() + 52, chars.end(), '0');
    int sum = 0;
    vector<string> parts;
    for (auto &c:chars) {
        cout << "? " << string(128, c) << endl;
        int len;
        cin >> len;
        len = 128 - len;
        sum += len;
        parts.push_back(string(len, c));
    }
    int n = parts.size();
    while (parts.size() > 1) {
        vector<string> buff;
        for (int i=0; i+1<n; i+=2) {
            buff.push_back(merge_two(parts[i], parts[i+1], sum));
        }
        if (n & 1) buff.push_back(parts.back());
        parts.swap(buff);
        n = parts.size();
    }
    cout << "! " << parts[0] << endl;
    return 0;
}

Measured memory_bytes: 3800