akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

template <typename T> class SparseTable {
    vector<vector<T>> st;
    vector<int> lookup;

  public:
    SparseTable(const vector<T> &v) {
        int b = 0;
        while((1U << b) <= v.size())
            ++b;
        st.assign(b, vector<T>(1 << b));
        rep(i, v.size()) st[0][i] = v[i];
        FOR(i, 1, b) rep(j, (1 << b) - (1 << i) + 1) {
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        }
        lookup.resize(v.size() + 1);
        FOR(i, 2, lookup.size()) lookup[i] = lookup[i >> 1] + 1;
    }

    constexpr T rmq(const int &l, const int &r) {
        int b = lookup[r - l];
        return min(st[b][l], st[b][r - (1 << b)]);
    }
};

struct kukan {
    int l, r, mn;
    kukan(int l, int r, int mn) : l(l), r(r), mn(mn) {}
    inline bool operator<(const kukan &x) const { return mn > x.mn; }
};

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

    vector<int> dat[2], ans, pos;
    int N;
    cin >> N;
    pos.resize(N);
    rep(i, N) {
        int p;
        cin >> p;
        p--;
        pos[p] = i;
        dat[i & 1].push_back(p);
        dat[i + 1 & 1].push_back(1e9);
    }
    vector<SparseTable<int>> RMQ;
    RMQ.push_back(SparseTable<int>(dat[0]));
    RMQ.push_back(SparseTable<int>(dat[1]));
    priority_queue<kukan> pque;
    pque.push(kukan(0, N, RMQ[0].rmq(0, N)));
    while(!pque.empty()) {
        kukan x = pque.top();
        pque.pop();
        ans.push_back(x.mn);
        int a = pos[x.mn];
        int mn = RMQ[a + 1 & 1].rmq(a + 1, x.r);
        ans.push_back(mn);
        int b = pos[mn];
        kukan k1(x.l, a, RMQ[x.l & 1].rmq(x.l, a));
        kukan k2(a + 1, b, RMQ[a + 1 & 1].rmq(a + 1, b));
        kukan k3(b + 1, x.r, RMQ[b + 1 & 1].rmq(b + 1, x.r));
        if(k1.l < k1.r) pque.push(k1);
        if(k2.l < k2.r) pque.push(k2);
        if(k3.l < k3.r) pque.push(k3);
    }
    rep(i, ans.size()) cout << ans[i] + 1 << " ";

    return 0;
}

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

int main(){
    double a, b, angle, radian, S, L, h;
    scanf("%lf %lf %lf", &a, &b, &angle);

    radian = (angle * M_PI) / 180;
    S = a * b * sin(radian) / 2;
    L = a + b + sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(radian));
    h = 2 * S / a;

    printf("%lf\n%lf\n%lf\n", S, L, h);
    return 0;
}


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

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

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    cout << 800 * N - (200 * (N/15)) << endl;
}


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

int main()
{
    string Map;
    cin>>Map;
    stack <int> s1;
    stack < pair<int,int> > s2;
    int sum=0;
    int a,j;
    for(int i=0;i<Map.length();i++){
        if(Map[i]=='\\'){
            s1.push(i);
        }
        else if(Map[i]=='/'){
            if(!s1.empty()){
                j=s1.top();
                s1.pop();
                a=i-j;
                sum+=a;
                while(!s2.empty()&&s2.top().first>j){
                a+=s2.top().second;
                s2.pop();
                }
                s2.push(make_pair(j,a));
            }
        }
    }
    vector <int> out;
    while(!s2.empty()){
        out.push_back(s2.top().second);
        s2.pop();
    }
    reverse(out.begin(),out.end());
    cout<<sum<<endl;
    cout<<out.size();
    for(int i=0;i<out.size();i++)
        cout<<" "<<out[i];
    cout<<endl;
    return 0;
}



Measured memory_bytes: 3332
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int dp[1001][1001];
int main(){
    int n;
    string s,t;
    cin>>n;
    rep(i,n){
        cin>>s>>t;
        memset(dp,0,sizeof(dp));
        int ss=s.size(),st=t.size();
        rep(i,ss){
            rep(j,st){
                if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;
                else{
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        cout<<dp[ss][st]<<endl;
    }
    return 0;
}


Measured memory_bytes: 7128
import itertools
n = int(input())
l = [i for i in range(1, n+1)]
l = list(itertools.permutations(l))

p = input()
q = input()
p = p.split(" ")
q = q.split(" ")
p, q = tuple(map(int, p)), tuple(map(int, q))
print(abs(l.index(p) - l.index(q)))

Measured memory_bytes: 8052
#include <stdio.h>
#include <string.h>
int main()
{
    char a[100000],b[50000];
    int i,j=0;
    gets(a);
    for(i=0;a[i];i++)
        if((i+3)%2==1)
            b[j++]=a[i];
    b[j]='\0';
    puts(b);
    return 0;
}


Measured memory_bytes: 384
//https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_a
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(void)
{
	int A, B, C;

	cin >> A;
	cin >> B;
	cin >> C;

	int pos = A - B >= 0;

	if (pos)
	{
		if (C < A && C > B)
		{
			cout << "Yes";
		}
		else
		{
			cout << "No";
		}
	}
	else
	{
		if (C > A && C < B)
		{
			cout << "Yes";
		}
		else
		{
			cout << "No";
		}
	}




}

Measured memory_bytes: 256
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
keys = [i for i in range(N)]
hands = {key: 0 for key in keys}  # n回目の手を記録

for i in range(N):
    if i < K:
        if T[i] == 'r':
            hands[i] = P
        elif T[i] == 's':
            hands[i] = R
        else:
            hands[i] = S
    elif i >= K:
        if T[i] == T[i-K] == 'r':
            if hands[i-K] == 0:
                hands[i] = P
        elif T[i] == T[i-K] == 's':
            if hands[i-K] == 0:
                hands[i] = R
        elif T[i] == T[i-K] == 'p':
            if hands[i-K] == 0:
                hands[i] = S
        else:
            if T[i] == 'r':
                hands[i] = P
            elif T[i] == 's':
                hands[i] = R
            else:
                hands[i] = S

total = sum(hands.values())
print(total)


Measured memory_bytes: 94168
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {
			
			long a = sc.nextLong();
			long b = sc.nextLong();
			long c = sc.nextLong();
			long d = sc.nextLong();
			
			List<Long> lst = new ArrayList<>();
			
			lst.add(a*c);
			lst.add(a*d);
			lst.add(b*c);
			lst.add(b*d);
			
			Collections.sort(lst, Collections.reverseOrder());
			
			System.out.println(lst.get(0));
			
		}
	}

}

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

struct BipartiteMatching {
  vector< vector<int> > graph;
  vector<int> matched;
  vector<bool> used;
  BipartiteMatching(int V):graph(V), matched(V, -1), used(V, false){}
  void add_edge(int u, int v) {
    graph[u].emplace_back(v);
    graph[v].emplace_back(u);
  }
  bool dfs(int u) {
    used[u] = true;
    for(auto& v : graph[u]) {
      int w = matched[v];
      if(w < 0 || (!used[w] && dfs(w))) {
        matched[u] = v;
        matched[v] = u;
        return true;
      }
    }
    return false;
  }
  int match() {
    int res = 0;
    for(int u = 0; u < (int)graph.size(); u++) {
      if(matched[u] < 0) {
        used.clear(); used.resize(graph.size(), false);
        if(dfs(u)) res++;
      }
    }
    return res;
  }
};

int main(){
    int x,y,m;
    cin>>x>>y>>m;
    BipartiteMatching BP(x+y);
    while(m--){
        int a,b;
        cin>>a>>b;
        BP.add_edge(a,b+x);
    }
    cout<<BP.match()<<endl;
}


Measured memory_bytes: 3296
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <cassert>
using namespace std;
#define MOD 1000000007

void add(long long &x, long long y){
    x = (x + y) % MOD;
}
void sub(long long &x, long long y){
    x = (x + (MOD - y) % MOD) % MOD;
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> S(N), T(M);
    for(int i=0; i<N; i++) cin >> S[i];
    for(int i=0; i<M; i++) cin >> T[i];

    vector<vector<long long>> dp(N+1, vector<long long>(M+1));
    vector<vector<long long>> sm(N+1, vector<long long>(M+1));
    dp[0][0] = 1;
    for(int i=0; i<=N; i++)
        sm[i][0] = 1;
    for(int i=0; i<=M; i++)
        sm[0][i] = 1;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(S[i-1] == T[j-1])
                dp[i][j] = sm[i-1][j-1];
            add(sm[i][j], sm[i-1][j]);
            add(sm[i][j], sm[i][j-1]);
            sub(sm[i][j], sm[i-1][j-1]);
            add(sm[i][j], dp[i][j]);
        }
    }
    long long ans = 0;
    for(int i=0; i<=N; i++)
        for(int j=0; j<=M; j++)
            add(ans, dp[i][j]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 62976
import numpy as np
n = input()
a = map(int, raw_input().split())
max_i = np.argmax(a)
min_i = np.argmin(a)
ans = []
if abs(a[max_i]) >= abs(a[min_i]):
    for i in range(n):
        ans.append((max_i, i))
    for i in range(n-1):
        ans.append((i, i+1))
else:
    for i in range(n):
        ans.append((min_i, i))
    for i in range(n-1, 0, -1):
        ans.append((i, i-1))
print len(ans)
for x, y in ans:
    print (x+1), (y+1)

Measured memory_bytes: 17416
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [(input_raw[0])]
    count = 0
    for s in N:
        if s == "2":
            count += 1

    print count

if __name__ == '__main__':
    main()


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

char A[223],B[123];
int main()
{
	//freopen("/home/zz7/CFInput","r",stdin);
	scanf("%s %s",A,B);int la=strlen(A);
	strcpy(A+la,A);
	bool p=false;
	for(int i=0;i<la;i++){
		if(strncmp(&A[i],B,la)==0){p=true;break;}
	}if(!p)cout<<"No\n";
	else cout<<"Yes\n";
}



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

int main(){
    int D;
    cin >> D;
    switch(D) {
        case 25:
            cout << "Christmas" << endl;
        break;
        case 24:
            cout << "Christmas Eve" << endl;
        break;
        case 23:
            cout << "Christmas Eve Eve" << endl;
        break;
        case 22:
            cout << "Christmas Eve Eve Eve" << endl;
        break;
    }
}

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

int main() {

int a,b, W;
  cin>>W>>a>>b;
  if(a<=b&&b<W+a){cout<<0<<endl;}
  else if(b<=a&&a<W+b){cout<<0<<endl;}
  else if(a+W<b){cout<<b-(a+W)<<endl;}
  else if(b+W<a){cout<<a-(b+W)<<endl;}
  else{cout<<0<<endl;}
}


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

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n,m,count=0;
    cin >> n>> m;
    vector<int> a(m,0);
    
    for(ll i=0;i<(ll)(n);i++){
        int temp;
        cin >> temp;
        for(ll i=0;i<(ll)(temp);i++){
            int temp2;
            cin >> temp2;
            a[temp2-1]++;
        }
    }
    
    for(ll i=0;i<(ll)(m);i++){
        if(a[i]==n) count++;
    }
    cout << count << endl;
    return 0;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
        #include <chrono>
      
        using namespace std;
        using namespace std::chrono; 
     
        typedef long long int ll;
     
        #define MOD (ll)(1e9+7)
        #define endl "\n"
        #define pb push_back
        #define TEST_CASES  ll t;cin>>t;while(t--)
        #define forn(i,a,n) for (int i = a; i < n; ++i)
        #define f first
        #define s second
        #define all(x) x.begin(), x.end()


        
        ll powD(ll x,ll y){
          ll res = 1;
          while(y > 0){
            if(y & 1)
              res = (res*x);
            x = (x*x);
            y = y>>1;
          }
          return res;
        }
        int main()
        {
          ios_base::sync_with_stdio(false);
          cin.tie(NULL);
          char c;
          cin>>c;
          if(isupper(c))
            cout<<'A'<<endl;
          else
            cout<<'a'<<endl;

        }

        
      


Measured memory_bytes: 3636
K = int(input())
s = 7
flg = False
cnt = 0

for i in range(K+1):
    cnt += 1
    if s % K == 0:
        flg = True
        break
    s *= 10
    s %= K
    s += 7

if flg:
    print(cnt)
else:
    print(-1)


Measured memory_bytes: 63424
using System;
using System.Linq;

class C
{
	static int[] Read() => Console.ReadLine().Split().Select(int.Parse).ToArray();
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var a = Read();
		var b = Read();

		values = Enumerable.Range(1, n).ToArray();
		int i = 0, j = 0, c = 0;
		action = () =>
		{
			++c;
			if (p.SequenceEqual(a)) i = c;
			if (p.SequenceEqual(b)) j = c;
		};
		Perm(n);
		Console.WriteLine(Math.Abs(i - j));
	}

	static int[] values;
	static Action action;
	static int[] p;
	static bool[] u;
	static void Perm(int r)
	{
		p = new int[r];
		u = new bool[values.Length];
		if (r > 0) Dfs(0); else action();
	}
	static void Dfs(int i)
	{
		for (int j = 0; j < u.Length; ++j)
		{
			if (u[j]) continue;
			p[i] = values[j];
			u[j] = true;
			if (i + 1 < p.Length) Dfs(i + 1); else action();
			u[j] = false;
		}
	}
}


Measured memory_bytes: 17372
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <numeric>
#include <sstream>
#include <set>
#include <map>
#include <tuple>
#include <iomanip>

using namespace std;
#define MAX 1LL << 60
#define MOD 1000000007

typedef long long ll;

#define rep(i, s, e) for(unsigned int i = s; i < e; i++)
#define repR(i, s, e) for(ll i = s; i > e; i--)
#define reft0(i, j) setfill('0') << setw(i) << j
#define fix(i) fixed << setprecision(i)
#define so(a) sort(begin(a), end(a))
#define soR(a) sort(begin(a), end(a), greater<ll>())
#define sum(a) accumulate(begin(a), end(a), 0)


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; }

int gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int gcd(ll a, ll b, ll c) {
	return gcd(a, gcd(b, c));
}


int main() {
	ll N, K;
	cin >> N >> K;

	ll cnt = 1;
	while (N / K > 0) {
		N = N / K;
		cnt++;
	}
	cout << cnt << endl;
	return 0;
}

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

pair<int, int> ma;

struct Graph {
    struct Vertex { int n; };
    struct Edge { int i, n; };
    Graph(int n, int m) : v(n, { -1 }), e(m), n(n), m(0) {}
    void add_edge(int i, int j) {
        e[m] = { j, v[i].n };
        v[i].n = m;
        m++;
    }
    void dfs(int i, int p, int d) {
        ma = max(ma, pair<int, int>(d, i));
        for (int j = v[i].n; j >= 0; j = e[j].n) {
            Edge &o = e[j];
            if (o.i == p) continue;
            dfs(o.i, i, d + 1);
        }
    }
    vector<Vertex> v;
    vector<Edge> e;
    int n, m;
};

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

    int n;
    cin >> n;

    Graph g(n, (n - 1) * 2);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;

        g.add_edge(a, b);
        g.add_edge(b, a);
    }
    ma = { -1, -1 };
    g.dfs(0, -1, 0);
    int i = ma.second;
    ma = { -1, -1 };
    g.dfs(i, -1, 0);
    int d = ma.first;

    cout << (d % 3 != 1 ? "First" : "Second") << endl;

    //選んだ頂点の次数のぶんだけコイン（が置いてある頂点の数）が減る そこを根として葉ノードがなくなる
    //次数が1より大きい頂点ならどこを選んでも同じ結果となりそう 次数1の頂点を選ぶとそこは残る 合法手は葉ノードの数+1 残り2にして相手に渡せば勝ち
    //直径は1か2減る 2減らすことはできる 1減らすこともできる 直径を1にしたら負け 0にしたら勝ち 2にしたら勝ち 逆では
    //10110110

    return 0;
}

Measured memory_bytes: 8320
#!/usr/bin/env python3
import sys
import math
MOD = 1000000007  # type: int
from collections import Counter

# 素因数分解
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

def solve(N: int):
    soinsuu = prime_decomposition(math.factorial(N))
    counter = Counter(soinsuu)
    answer =1
    for value in counter.values():
        answer = answer*(value+1)
        answer%=MOD
    print(answer%MOD)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


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

int main(){
    int a;
    string s;
    cin >> a;
    cin >> s;
    if(a>=3200){
        cout << s << endl;
    }
    else{
        cout << "red" << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
// by Batrrr
// This will be Accepted!
// Happy new year !!!
 
#include <bits/stdc++.h>
 
#define jyldam ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
#define pb push_back
#define mp make_pair
 
#define B begin()
#define E end()
#define sz size()
#define skip continue
#define all(x) (x).begin(), (x).end()
 
#define F first
#define S second          
 
#define st(x) st+=x
#define pii pair<int, int>
#define pli pair<long long, int>
#define pil pair<int, long long>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;     
 
const int N = 2e5 + 17, M = N * 4, D = 2e3 + 17, mod = 1e9 + 7;
const ll INF = 1e9 + 17;
 
int tt = 1;
ll a[N];
ll dp[N];
int n;
int t[M];
 
void upd () {
		for (int i = 1; i <= M; i++) {
			t[i] = 0;
		}
}
 
void build (int v, int tl, int tr, int a[]) {
		if (tl == tr) {
			t[v] = a[tl];
			return;
		}
		int tm = (tl + tr) >> 1;
		build(v + v, tl, tm, a);
		build(v + v + 1, tm + 1, tr, a);
		t[v] = max(t[v + v], t[v + v + 1]);
}
 
int get (int v, int tl, int tr, int l, int r) {
		if (l > tr || tl > r) {
			return -INF;
		}
		if (l <= tl && tr <= r) {
			return t[v];
		}
		int tm = (tl + tr) >> 1;
		return max(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}
                                                
void solve () {                      
		cin >> n;
		for (int i = 1; i <= n; i++) {
				cin >> a[i];                                    	
				dp[i] = INF;
		}             
		dp[1] = 0;
		for (int i = 1; i <= n; i++) {
				dp[i+1] = min(dp[i+1], dp[i] + abs(a[i+1] - a[i]));
				dp[i+2] = min(dp[i+2], dp[i] + abs(a[i+2] - a[i]));
		}
		cout << dp[n];
}
		    
int main() {
		jyldam;
						                  
		while (tt--) {   
			solve();
		}
   	
		return 0;
}

Measured memory_bytes: 4352
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                rows[x:min_col] = [min_row] * (min_col - x)
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                cols[x:min_row] = [min_col] * (min_row - x)
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

Measured memory_bytes: 41840
N, K = map(int, input().split())
S = input()
ts = []

s1 = 0
s0 = 0

if N < K:
    print(N)
    exit(0)
# Create 01 array
for c in S:
    if c == '1':
        s1 += 1
        if not s0 == 0:
            ts.append((0, s0))
        s0 = 0
    else:
        s0 += 1
        if not s1 == 0:
            ts.append((1,s1))
        s1 = 0

if s1 != 0:
    ts.append((1,s1))
if s0 != 0:
    ts.append((0,s0))

# print("TS:", ts)

# top/bottom
top0 = False
bottom0 = False

if ts[0][0] == 0:
    top0 = True

if ts[-1][0] == 0:
    bottom0 = True

# print(top0, bottom0)
## pre calc
if len(ts) >= 2:
    ans = 1
else:
    ans = ts[0][1]
# print(ans)

sp = 0
ep = len(ts)

if top0:
    ans = sum(x[1] for x in ts[:K*2])
    # print("t0:", ans)
    sp = 1

if bottom0:
    ans = max(ans, sum(x[1] for x in ts[-K*2:]))
    # print("b0:", ans)
    ep = len(ts)-1

# Calc
# print(sp, ep)
if ep - sp > 1:
    W = 2 * K + 1
    temp = sum([x[1] for x in ts[sp:sp+W]])
    # print("temp:", temp)
    ans = max(temp, ans)

    for ix in range(sp+2, ep-W+1, 2):
        temp = temp - ts[ix-1][1] - ts[ix-2][1] + ts[ix+W-1][1] + ts[ix+W-2][1]
        # print(ix, temp)
        ans = max(temp, ans)

print(ans)

Measured memory_bytes: 82692
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    l = list(S)
    while (True):
        sl = []
        cur = ''
        for v in l:
            if cur == v:
                continue
            sl.append(v)
            cur = v
        if len(l) == len(sl):
            print(len(l))
            break
        l = sl
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 4956
import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = in.nextInt();

Pair[] ps = new Pair[k];

id = new int[n];

size = new int[n];

for(int i = k-1; i >= 0; i--) {

ps[i] = new Pair(in.nextInt(), in.nextInt());

}

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

id[i] = i;

} 

Arrays.fill(size,1);

  

long count = ((long) n) *((long) n-1)/2L;

long max = count;

long[] ans = new long[k-1];

for( int i = 0; i < k-1; i++) {

int a = ps[i].x-1;

int b = ps[i].y-1;

int id_a = root(a);

int id_b = root(b);

if(id_a != id_b) {

count -= ((long) size[id_a]) *((long) size[id_b]) ;

}

ans[i] = count;

union(a,b);

} 

  

for(int i = k-2; i >= 0; i--) {

System.out.println(ans[i]);

} 

System.out.println(max);

  

}

static int[] id; // inst to i

static int[] size; // inst to 1

static int root( int i ) {

if(id[i] != i) // find root

id[i] = root(id[i]);

return id[i];

}

static boolean find( int p, int q) {

return root(p) == root(q);

} 

static void union( int p, int q ) {

int i = root(p); // group of p

int j = root(q); // group of q  
  
if( i != j ) {
  
if( size[i] < size[j] ) {
  
id[i] = j;
  
size[j] += size[i];
  
} else {
  
id[j] = i;
  
size[i] += size[j];
  
}   

} 

}

public static class Pair {

int x, y;

public Pair (int x, int y) {

this.x = x;

this.y = y;

} 

} 

} 

Measured memory_bytes: 97560
import sys

#input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
d=[]
for i in range(h):
    for j in range(w):
        if a[i][j]%2==1:
             d.append((i,j))
n=len(d)
if n==0:
  print(0)
  exit()
d_s=set(d)
ans=[]
f=False
y=d[0][0]
x=d[0][1]
xp=x+1
yp=y
while True:
    if y%2==0:
      xp=x+1
    else:
      xp=x-1
    yp=y
    if (y,x) in d_s:
      while True:
          if (yp,xp) not in d_s and -1<xp<w and yp<h:
              if yp%2==0:
                  ans.append([y+1,x+1,yp+1,xp+1])
                  x=xp
                  xp+=1
              else:
                  ans.append([y+1,x+1,yp+1,xp+1])
                  x=xp
                  xp-=1
              y=yp
          elif (yp,xp) not in d_s and xp>w-1:
              xp=w-1
              yp+=1
          elif (yp,xp) not in d_s and xp<0:
              xp=0
              yp+=1
          elif (yp,xp) in d_s:
              ans.append([y+1,x+1,yp+1,xp+1])
              if yp%2==0:
                x=xp+1
                y=yp
              else:
                x=xp-1
                y=yp
              break
          elif yp>h-1:
            f=True
            break
      if f:
        break
    else:
      if y%2==0:
        x+=1
      else:
        x-=1
      if x>w-1:
        x=w-1
        y+=1
      elif x<0:
        x=0
        y+=1
    if y>h-1:
      break
print(len(ans))
for i in ans:
  print(*i)

Measured memory_bytes: 88724
//////////////////////////////
// Author: whatisit
// Date: 2020-05-18 03:00 
//////////////////////////////
#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) 
		cin >> a[i];
	map<int, int> m;
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		int sa = i-a[i];
		int wa = i+a[i];
		ans += m[sa];
		m[wa]++;
	}
	cout << ans;
}

int main() {
	//cin.tie(0); ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

Measured memory_bytes: 21020
#include<stdio.h>

int main(){
  int a,n;
  scanf("%d",&n);
  printf("%d:",n);
  a=2;
  while(n>=a*a){
    if(n%a==0){
      printf(" %d",a);
      n=n/a;
    } else {
      a++;
    }
  }
  printf(" %d\n",n);
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
int main()
{
  int n;
  cin>>n;
  vector<int> a(n),b(n),c(n);
  for (int i=0;i<n;i++)
  {
    int p,q,r;
    cin>>p>>q>>r;
    a[i]=p;
    b[i]=q;
    c[i]=r;
  }
  vector<int> M(3),dp(3);
  dp[0]=a[0];
  dp[1]=b[0];
  dp[2]=c[0];
  for (int i=1;i<n;i++)
  {
    M[0]=max(dp[1]+a[i],dp[2]+a[i]);
    M[1]=max(dp[0]+b[i],dp[2]+b[i]);
    M[2]=max(dp[0]+c[i],dp[1]+c[i]);
    dp=M;
  }
  cout<<max(dp[0],max(dp[1],dp[2]));
  
}

Measured memory_bytes: 4480
class DoublyLinkedList():
    """双方向連結リスト"""

    def __init__(self):
        self.first = self.last = None
        
    def insert(self, x):
        """リストの先頭に x を挿入

        O(1) の計算量
        """
        if self.first is None:
            self.first = self.last = {'prev': None, 'next': None, 'key': x}
        else:
            self.first = {'prev': None, 'next': self.first, 'key': x}
            self.first['next']['prev'] = self.first
    
    def deleteFirst(self):
        """リストの先頭要素を削除

        削除できれば True, 空で削除できない場合、False を返す。
        O(1) の計算量
        """
        if self.first is None:
            return False
        else:
            self.first = self.first['next']
            if self.first is not None:
                self.first['prev'] = None
            else:
                self.last = None
            return True
    
    def deleteLast(self):
        """リストの最後尾を削除

        削除できれば True, 空で削除できない場合 False を返す。
        O(1) の計算量
        """
        if self.last is None:
            return False
        else:
            self.last = self.last['prev']
            if self.last is not None:
                self.last['next'] = None
            else:
                self.first = None
            return True
    
    def delete(self, x):
        """値が x に等しい最初の要素を削除する。

        削除できれば True, 存在しないので削除できなかった場合 False を返す。
        O(n) の計算量になる。
        """
        current = self.first
        while current is not None:
            if x == current['key']:
                prev = current['prev']
                next = current['next']
                if prev is None:
                    self.first = next
                else:
                    prev['next'] = next
                
                if next is None:
                    self.last = prev
                else:
                    next['prev'] = prev
                
                break
            current = current['next']
        else:
            return False
        return True

    def __iter__(self):
        current = self.first
        while current is not None:
            yield current['key']
            current = current['next']

    
if __name__ == '__main__':
    import sys

    dl_list = DoublyLinkedList()

    n = int(input())

    for _ in range(n):
        # command_x = input().split()
        command_x = sys.stdin.readline().split()
        if command_x[0] == 'insert':
            x = int(command_x[1])
            dl_list.insert(x)
        elif command_x[0] == 'delete':
            x = int(command_x[1])
            dl_list.delete(x)
        elif command_x[0] == 'deleteFirst':
            dl_list.deleteFirst()
        else:
            dl_list.deleteLast()
    
    print(*dl_list)




Measured memory_bytes: 275524
program main
  implicit none
  integer :: N,M
  integer,allocatable :: A(:)
  integer :: out
  read(*,*) N, M
  allocate(A(M))
  read(*,*) A(:)
  out = N-sum(A)
  if (out < 0) then
     write(*,'(i0)') -1
  else 
     write(*,'(i0)') out
  end if
end program main

Measured memory_bytes: 3012
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define S second
#define F first
using namespace std;
const ll mod = 1e9+7;
ll h,w,n;
ll dp[3009];
pll arr[3009];
ll fact[300009];
ll ifact[300009];
bool cmp(pll a,pll b){
    return a.F+a.S < b.F+b.S;
}
ll inv(ll x,ll p){
    if(p == 0) return 1;
    if(p%2) return (x*inv(x,p-1))%mod;
    return inv((x*x)%mod,p/2)%mod;
}
ll c(ll n,ll k){
    if(n < 0 || k < 0 || n < k) return 0;
    ll ret = (fact[n]*ifact[k])%mod;
    return (ret*ifact[n-k])%mod;
}
ll solve(ll x1,ll y1,ll x2,ll y2){
    if(x1 > x2 || y1 > y2) return 0;
    ll N = x2-x1+1,M = y2-y1+1;
    return c(N+M-2,N-1);
}
int main(){
    fast,cin>>h>>w>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i].F>>arr[i].S;
    }
    fact[0] = ifact[0] = 1;
    for(ll i=1;i<=3e5;i++){
        fact[i] = (fact[i-1]*i)%mod;
        ifact[i] = inv(fact[i],mod-2);
    }
    arr[n++] = {h,w};
    sort(arr,arr+n,cmp);
    for(int i=0;i<n;i++){
        dp[i] = solve(1,1,arr[i].F,arr[i].S);
        for(int j=0;j<i;j++){
            ll x = (dp[j]*solve(arr[j].F,arr[j].S,arr[i].F,arr[i].S))%mod;
            dp[i] = (dp[i]-x+mod)%mod;
        }
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define SORT(x) (sort(x.begin(),x.end()))
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main() {
    double N,ans,A[107];cin >> N;
    rep(i,N){
        cin >> A[i];
        ans+=(1/A[i]);
    }
    printf("%lf",1/ans);
}


Measured memory_bytes: 256
S = input()
#文字列Sの隙間の2乗
#bit表記で0なら-,1なら+を挿入
for i in range(2**(len(S)-1)):
  x = ''
  for j in range(len(S)-1):
    x += S[j]
    if ((i>>j)&1):
      x += "+"
    else:
      x += "-"
  x += S[-1]
  if eval(x)==7:
    print(x + "=7")
    break

Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: u32 = read();
    let k: usize = read();
    let mut a: Vec<u32> = (0..n).map(|_| read()).collect();
    a.sort();
    let mut ans = 0;
    let a = &a[0..k];
    for n in a{
        ans += n;
    }
    print!("{}", ans);
}

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

int main() {
  string s;
	int N,M;
  	cin >> N;
  if (N<10){
    if(N==2||N==4||N==5||N==7||N==9){
      s="hon";
      cout <<s<<endl;
    }
    if(N==0||N==1||N==6||N==8){
      s="pon";
      cout <<s<<endl;
    }
    if(N==3){
      s="bon";
      cout <<s<<endl;
    }
  }
  else{
    M=N%10;
  if(M==2||M==4||M==5||M==7||M==9){
      s="hon";
      cout <<s<<endl;
    }
    if(M==0||M==1||M==6||M==8){
      s="pon";
      cout <<s<<endl;
    }
    if(M==3){
      s="bon";
      cout <<s<<endl;
    }
  }
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll g = __gcd(c, d);
  ll l = c / g * d;
  a--;
  ll mi = a - a/c - a/d + a/l;
  ll ans = b - b/c - b/d + b/l;
  // cerr << b << " " << b/c << " " << b/d << " " << b/l << endl;
  // cerr << mi << " " << ans << endl;
  ans -= mi;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
x=sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0])
ans=0
for s,t in x:
#    print(s,t,m)
    if m>=t:
        m-=t
        ans+=s*t
    else:
        ans+=m*s
        break
print(ans)

Measured memory_bytes: 29788
#![allow(
  non_snake_case,
  unused_variables,
  unused_assignments,
  unused_mut,
  unused_imports,
  dead_code
)]
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::*;
//use std::num;
//use petgraph::unionfind::UnionFind;
//use permutohedron::LexicalPermutation as _;

const MOD: i64 = 1000_000_007;
//#[fastout()]
fn main() {
  input! {
      N:usize,
      A:[i64;N]
  }
  let A: Vec<i64> = A;
  let mut ans = 0i64;
  let mut tmp = A[0];
  let mut S = vec![0; N + 1];
  for i in (1..N).rev() {
    S[i] = (S[i + 1] + A[i]) % MOD;
  } // S2=3, S1=5
  for i in 0..(N - 1) {
    ans += (A[i] * S[i + 1]) % MOD;
    ans %= MOD;
  }
  println!("{}", ans);
}


Measured memory_bytes: 7180
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
int INF=1<<29;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll N,K;
	cin>>N>>K;
	vector<pair<ll,ll>> axis(N);
	vector<ll> x(N),y(N);
	vector<ll> ans;
	for(int i=0;i<N;i++){
		cin>>x[i]>>y[i];
		axis[i].first=x[i];
		axis[i].second=y[i];
	}
	for(int i=0;i<N;i++){ //left
		for(int j=0;j<N;j++){ //right
			for(int k=0;k<N;k++){ //up
				for(int l=0;l<N;l++){ //down
					if(x[i]>=x[j] || y[l]>=y[k]) continue;
					ll c=0;
					for(int m=0;m<N;m++){
						if(x[i]<=axis[m].first && axis[m].first<=x[j] && y[l]<=axis[m].second && axis[m].second<=y[k]) c++;
					}
					if(c>=K) ans.push_back((x[j]-x[i])*(y[k]-y[l]));
				}
			}
		}
	}
	sort(ans.begin(),ans.end());
	cout<<ans[0]<<endl;
	return 0;
}

Measured memory_bytes: 17768
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> t(N);
  for (int i=0; i<N; i++) cin >> t[i];
  int M;
  cin >> M;
  vector<int> p(M); vector<int> x(M);
  for (int i=0; i<M; i++) cin >> p[i] >> x[i];
  
  int sum = 0;
  for (int i=0; i<N; i++) {
    sum += t[i];
  }
  
  for (int i=0; i<M; i++) {
    int dt=t[p[i]-1]-x[i];
    cout << sum-dt << endl;
  }
}

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

int main() {
  long N, K;
  cin >> N >> K;
  long A[100010], B[100010];
  for (int i = 0; i < N; i++)
    cin >> A[i] >> B[i];
  
  map<long, long> mp;
  for (int i = 0; i < N; i++)
    mp[A[i]] += B[i];
  
  long ans;
  for (auto p: mp) {
    long pf = p.first, ps = p.second;
    K -= ps;
    if (K <= 0) {
      ans = pf;
      break;
    }
  }
  
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main()
{
  int N;
  long long K;
  cin >> N >> K;
  vector<long long> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];
  int cnt[40] = {};
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < 40; j++)
      if (A[i] & (1LL << j))
        cnt[j]++;
  }
  long long tmp = 0;
  for (int i = 39; - 1 < i; i--)
  {
    if (cnt[i] < N - cnt[i] && (tmp | (1LL << i)) <= K)
      tmp |= (1LL << i);
  }
  long long ans = 0;
  for (int i = 0; i < N; i++)
    ans += tmp ^ A[i];
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1152
N, K = map(int, input().split(' '))
R, S, P = map(int, input().split(' '))
T = input()

point = 0
unPointed = []

for i in range(len(T)):
    ifAdd = True
    if i - K >= 0:
        if T[i] == T[i - K]:
            if unPointed[i - K] == 0:
                ifAdd = False
    if ifAdd is True:
        if T[i] == 'r':
            point += P
        elif T[i] == 's':
            point += R
        elif T[i] == 'p':
            point += S
        unPointed.append(0)
    else:
        unPointed.append(1)

print(point)

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin >> n >> m;
    VLL a(n);
    vector<PLL> v(m);
    priority_queue< ll, vector<ll>, greater<ll>> que;
    rep(i,n){
      cin >> a[i];
      que.push(a[i]);
    }
    rep(i,m){
      cin >> v[i].second >> v[i].first;
    }
    sort(v.rbegin(),v.rend());
    int idx = 0;
    rep(i,n){
      if(que.top() >= v[idx].first) break;
      else if(que.top() < v[idx].first){
        que.pop();
        que.push(v[idx].first);
        v[idx].second --;
        if(v[idx].second == 0) idx++;
        if(idx == m) break;
      }
    }
    ll ans = 0;
    while(!que.empty()){
      ans += que.top();
      que.pop();
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3832
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

class Node {
    long key;
    Node parent, left, right;

    Node(long key) {
        this.key = key;
    }
}

class BinarySearchTree {
    Node root = null;

    void insert(Node node) {
        if (root == null) {
            root = node;
        } else {
            Node parent = null;
            Node curr = root;
            while (curr != null) {
                parent = curr;
                if (node.key < parent.key)
                    curr = curr.left;
                else
                    curr = curr.right;
            }
            // Insert the node
            node.parent = parent;

            // Set the node as a child of the parent
            if (node.key < parent.key)
                parent.left = node;
            else
                parent.right = node;
        }
    }

    Optional<Node> find(long key) {
        Node curr = root;
        while (curr != null && curr.key != key) {
            if (key < curr.key)
                curr = curr.left;
            else
                curr = curr.right;
        }
        return Optional.ofNullable(curr);
    }

    private void inorderTreeWalk(List<Long> ret, Node curr) {
        if (curr == null) return;
        inorderTreeWalk(ret, curr.left);
        ret.add(curr.key);
        inorderTreeWalk(ret, curr.right);
    }

    private void preorderTreeWalk(List<Long> ret, Node curr) {
        if (curr == null) return;
        ret.add(curr.key);
        preorderTreeWalk(ret, curr.left);
        preorderTreeWalk(ret, curr.right);
    }

    void print() {
        List<Long> arr = new ArrayList<>();
        inorderTreeWalk(arr, root);
        System.out.println(" " + arr.stream().map(String::valueOf).collect(Collectors.joining(" ")));

        arr.clear();
        preorderTreeWalk(arr, root);
        System.out.println(" " + arr.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

public class Main {
    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            final int n = Integer.parseInt(in.readLine());
            BinarySearchTree btree = new BinarySearchTree();

            for (int i = 0; i < n; i++) {
                String[] line = in.readLine().split(" ");
                if (line[0].charAt(0) == 'i') {
                    Node node = new Node(Long.parseLong(line[1]));
                    btree.insert(node);
                } else if (line[0].charAt(0) == 'f') {
                    if (btree.find(Long.parseLong(line[1])).isPresent())
                        System.out.println("yes");
                    else
                        System.out.println("no");
                } else {
                    btree.print();
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}



Measured memory_bytes: 210032
#include<iostream>
#include<map>

using namespace std;

map<int,int> mp;
int N;
int a,d;

int &ref(int x){
  x--;
  if(mp.count(x)){
    return mp[x];
  }else{
    return mp[x]=a+d*x;
  }
}

int main(){
  cin>>N;
  cin>>a>>d;
  int M;
  cin>>M;
  while(M--){
    int x,y,z;
    cin>>x>>y>>z;
    if(x){
      ref(y)=ref(z);
    }else{
      swap(ref(y),ref(z));
    }
  }
  int K;
  cin>>K;
  cout<<ref(K)<<endl;
}

Measured memory_bytes: 1200
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W, x, y, z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

Pa problems[10];
int main() {
	cin >> D >> G;
	rep(i, D){
		cin >> P >> C;
		problems[i] = Pa(P, C);
	}
	ll ans = MAX;
	rep(i, pow(2, D)){
		int curr = i;
		int rest_max = 0;
		int score = 0;
		ll slv = 0;
		rep(j, D){
			if(curr%2 == 1){
				score += problems[j].first * (j+1) * 100 + problems[j].second;
				slv += problems[j].first;
			}else{
				rest_max = j;
			}
			curr /= 2;
		}
		if(score < G){
			if(G - score > (problems[rest_max].first-1) * (rest_max+1)*100){
				continue;
			}else{
				slv += ((G - score)/100 - 1)/(rest_max+1) + 1;
			}
		}
		ans = min(ans, slv);
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) ((x).begin(), (x).end())
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    int x;
    int a, b;
    cin >> x;
    a = x / 100;
    b = x % 100;
    if(1 <= a && a <= 12 && 1 <= b && b <= 12)
        cout << "AMBIGUOUS";
    else if(1 <= a && a <= 12)
        cout << "MMYY";
    else if(1 <= b && b <= 12)
        cout << "YYMM";
    else
        cout << "NA";

    return 0;
}

Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * a.cc: 
 */

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

/* constant */

const int MAX_N = 100;
const int INF = 1 << 30;

/* typedef */

/* global variables */

int as[MAX_N];

/* subroutines */

/* main */

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

  int sum = 0;
  for (int i = 0; i < n; i++) (cin >> as[i]), sum += as[i];
  int av = sum / n;

  int minsum2 = INF;
  for (int y = av; y <= av + 1; y++) {
    int sum2 = 0;
    for (int i = 0; i < n; i++) {
      int d = y - as[i];
      sum2 += d * d;
    }
    if (minsum2 > sum2) minsum2 = sum2;
  }

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


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

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0 && m==0 ) break;
        long long c[m],x[n+1];
        for(int i=0;i<m;i++){
            cin>>c[i];
        }
        for(int i=1;i<=n;i++){
            cin>>x[i];
        }
        long long dp[n+1][256]={};
        long long INF=1e9;
        for(int j=0;j<=n;j++)for(int i=0;i<256;i++){
            dp[j][i]=INF;
        }
        dp[0][128]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<256;j++){
                for(int k=0;k<m;k++){
                    if(j+c[k]>=0 && j+c[k]<256) dp[i][j+c[k]]=min(dp[i][j+c[k]],dp[i-1][j]+(x[i]-j-c[k])*(x[i]-j-c[k]));
                    else if(j+c[k]<0) dp[i][0]=min(dp[i][0],dp[i-1][j]+x[i]*x[i]);
                    else dp[i][255]=min(dp[i][255],dp[i-1][j]+(x[i]-255)*(x[i]-255));
                }
            }
        }
        long long ans=1e18;
        for(int i=0;i<256;i++) ans=min(ans,dp[n][i]);
        cout<<ans<<endl;
    }
    
}


Measured memory_bytes: 43216