akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n, m, s[MAX_N];
vector<ll> a;

signed main(){
    cin >> n >> m;
    a.resize(n);
    REP(i, n) cin >> a[i];
    sort(ALL(a));
    REP(i, n) s[i+1] = s[i] + a[i]; //s[0] = 0, s[1] = a[1], s[2] = a[1] + a[2],

    auto check = [&](ll v){
        ll num = 0, sum = 0;
        REP(i, n){
            ll pos = lower_bound(ALL(a), v-a[i]) - a.begin();
            num += n - pos;
            sum += s[n] - s[pos];
            sum += (n - pos) * a[i];
        }
        return P(num, sum);
    };

    int ok = 200001, ng = -1;
    while(ok - ng > 1) {
        int mid = (ok + ng) / 2;
        if(check(mid).first <= m) ok = mid;
        else ng = mid;
    }
    // cout << ok  << " " << ng << endl;
    auto ret = check(ok);
    cout << ret.second + (m - ret.first) * (ok - 1) << endl; 
    // cout << m << " " << ret.first << " " << ok - 1 << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(void) {
	int LIM = 499500;
	int a,b; 
	cin >> a >> b;
	int dis = b-a;

	int sum = 0;
	for (int i = 1; i < dis; ++i) {
		sum += i;
	}
	cout << sum-a << endl;

	return 0;
}


Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    string s;
    cin >> s;
    stack<char> st;
    int n = sz(s);
    rep(i, n) {
        if (!st.empty() && st.top() == 'S' && s[i] == 'T') {
            st.pop();
        } else {
            st.push(s[i]);
        }
    }
    cout << st.size() << endl;
}


Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
//stoi(s) : string→int stoll(s) :string→longlong
const double PI=3.14159265358979323846;
const int MAXN = 200;
const int MAXS = 100100;
ll dp[MAXN][MAXS] = {0};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
    int N,W;
    cin >> N >> W;
    vector<ll> w(N),v(N);
    for(int i=0;i<N;i++){
        cin >> w[i] >> v[i];
    }
    for(int i=0;i<N;i++){
        for(int sum_w = 0;sum_w<=W;sum_w++){
            if(sum_w - w[i] >= 0){
                chmax(dp[i+1][sum_w],dp[i][sum_w-w[i]] + v[i]);
            }
            chmax(dp[i+1][sum_w],dp[i][sum_w]);
        }
    }
    cout << dp[N][W] << endl;
}

Measured memory_bytes: 79360
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    ll n,a,b,c;
    cin>>n>>a>>b;
    vector<ll>v;
    for(int i=0; i<n; i++)
    {
        ll x;
        cin>>x;
        v.push_back(x);
    }
    sort(all(v));
    ll l=0,r=1e10;
    c=a-b;
    while((r-l)>1)
    {
        ll mid=(l+r)>>1,cnt=0;
        vector<ll>t;
        for(int i=0; i<n; i++)
            t.push_back(v[i]-(mid*b));

        for(int i=0; i<n; i++)
        {
            if(t[i]>0)
            {
                cnt+=((t[i]-1)/c)+1;
            }
        }
        if(mid>=cnt)
            r=mid;
        else
            l=mid;
    }

    cout<<r<<endl;

    return 0;
}


Measured memory_bytes: 5880
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		int[] a = new int[m];
		int[] b = new int[m];
		for (int i = 0; i < m; i++) {
			sa = br.readLine().split(" ");
			a[i] = Integer.parseInt(sa[0]) - 1;
			b[i] = Integer.parseInt(sa[1]) - 1;
		}
		br.close();

		UnionFind uf = new UnionFind(n);
		for (int i = 0; i < m; i++) {
			uf.union(a[i], b[i]);
		}

		int max = 0;
		for (int i = 0; i < n; i++) {
			max = Math.max(max, uf.size(i));
		}
		System.out.println(max);
	}

	static class UnionFind {
		int[] parent, size;
		int num = 0; // 連結成分の数

		UnionFind(int n) {
			parent = new int[n];
			size = new int[n];
			num = n;
			for (int i = 0; i < n; i++) {
				parent[i] = i;
				size[i] = 1;
			}
		}

		void union(int x, int y) {
			int px = find(x);
			int py = find(y);
			if (px != py) {
				parent[px] = py;
				size[py] += size[px];
				num--;
			}
		}

		int find(int x) {
			if (parent[x] == x) {
				return x;
			}
			parent[x] = find(parent[x]);
			return parent[x];
		}

		/**
		 * xとyが同一連結成分か
		 */
		boolean same(int x, int y) {
			return find(x) == find(y);
		}

		/**
		 * xを含む連結成分のサイズ
		 */
		int size(int x) {
			return size[find(x)];
		}
	}
}


Measured memory_bytes: 71392
n = int(input())
a = list(map(int, input().split()))
ans = True
for i in range(n):
    if a[i]%2==0 and (a[i]%3==0 or a[i]%5==0):
        continue
    elif a[i]%2!=0 or (a[i]%3==0 or a[i]%5==0):
        continue
    else:
        ans = False
        exit
if ans:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, a, b;
    cin >> W >> a >> b;
    cout << max(0, abs(b-a) - W) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
void inline swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
void inline swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }

int n;
string s;

int main()
{
	cin >> n >> s;
	ostringstream oss;
	string pre, suf;

	char last = ' ';
	int cnt = 0;
	REP(i, n)
	{
		if (last == ')' && s[i] == '(')
		{
			if (cnt < 0)
			{
				REP(j, -cnt)
					pre.PB('(');
				cnt = 0;
			}
		}

		if (s[i] == '(')
			++cnt;
		else
			--cnt;

		last = s[i];

		//cout << "i = " << i << ", cnt = " << cnt << endl;
	}

	if (cnt < 0)
	{
		REP(j, -cnt)
			pre.PB('(');
		cnt = 0;
	}
	if (cnt)
	{
		REP(j, cnt)
			suf.PB(')');
	}
	oss << pre << s << suf;

	cout << oss.str() << endl;
}


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

public class hello
{
    public static void Main()
    {

        var t = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < t; i++)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            var dansa = new int[n - 1];
            string[] line = Console.ReadLine().Trim().Split(' ');
            for (int j = 0; j < n - 1; j++)
                dansa[j] = int.Parse(line[j]) - int.Parse(line[j + 1]);
            int upmax; int downmax;
            if (dansa.Min() > 0) upmax = 0;
            else upmax = -dansa.Min();
            if (dansa.Max() < 0) downmax = 0;
            else downmax = dansa.Max();

            Console.WriteLine("{0} {1}", upmax,downmax);
        }
    }
}

Measured memory_bytes: 9692
import java.util.Scanner;
import java.util.Stack;

class Main {

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

    void compute() {
        Scanner sc = new Scanner(System.in);
        int denom = (int) Math.pow(10, 9) + 7;
        int N = sc.nextInt();
        long ans = 1;
        for (int i = 1; i <= N; i++) {
            ans = ans * i % denom;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 22100
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7

dp = [[0] * W for _ in range(H+1)]

dp[0][0] = 1


for h in range(H):
    for x in range(W):
        for b in range(2**(W-1)):
            if not '11' in bin(b):
                if x >= 1 and (b>>(x-1)) & 1:
                    dp[h+1][x-1] += dp[h][x]
                    dp[h+1][x-1] %= MOD
                elif x <= W-2 and (b>>x) & 1:
                    dp[h+1][x+1] += dp[h][x]
                    dp[h+1][x+1] %= MOD
                else:
                    dp[h+1][x] += dp[h][x]
                    dp[h+1][x] %= MOD

print(dp[H][K-1])

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
using namespace std;
int main() {
	int n, min = 0, ans = 0;
	int p[2000000];
	cin >> n;
	for (int a = 0; a < n; a++) {
		cin >> p[a];
	}
	min = p[0];
	for (int i = 1; i < n; i++) {
		if (min >= p[i]) {
			min = p[i];
			ans++;
			continue;
		}
		else {
			continue;
		}
	}
	cout << ans+1 << endl;
	return 0;
}

Measured memory_bytes: 3072
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>

#define INF (1ll<<60)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;

#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)

template<class T>bool umax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool umin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}
// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);

    return result;
}
template<typename T>
T lcm( T m, T n )
{
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

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

// sort big to small
// sort(A,A+N, greater<int>());

// v.front() = -BOUND;
// v.back() = BOUND;

// Iterator
// v.begin
// v.end

int main() {
    long long N,M;
    long long useN=0;
    cin >> N >> M;

    useN=min(N, M/2);
    M-=useN*2;


    cout << useN+M/4 << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long mod=1e9+7;

long long power(long long a, long long n, long long mod){
  long long res=1;
    while(n>0){
     if(n&1)
         res=(res*a)%mod;
     a=(a*a)%mod;
     n>>=1;
  }
return res;
}

long long inverse(long long a, long long mod){
  return power(a,mod-2,mod);
}

int main(){
  long long n,k,arr[100005];
  long long a[100005], b[100005];
  cin>>n>>k;
  for(int i=0;i<n;i++)
       cin>>arr[i];
  a[0]=1;
  b[0]=1;
  for(int i=1;i<=n;i++){
    a[i]=(i*a[i-1])%mod;
    b[i]=inverse(a[i],mod);
  }
  sort(arr,arr+n);
  long long ans=0;
  for(int i=0;i<n-k+1;i++){
    long long x=1;
    x=(x*a[n-i-1])%mod;
    x=(x*b[k-1])%mod;
    x=(x*b[n-i-k])%mod;
    x=(arr[n-i-1]*x)%mod;
    ans=(ans+x+mod)%mod;
   }
  for(int i=0;i<n-k+1;i++){
    long long x=1;
    x=(x*a[n-1-i])%mod;
    x=(x*b[k-1])%mod;
    x=(x*b[n-i-k])%mod;
    x=(arr[i]*x)%mod;
    ans=(ans-x+mod)%mod;
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 5980
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  ll a, b, c, k;
  cin >> a >> b >> c >> k;

  auto isOK = [](auto x, auto y, auto z) { return (x < y) && (y < z); };

  string ans = "No";

  // Cをi選ぶ、Bをj選ぶ全通り
  for (ll i = 0; i <= k; i++) {
    ll choseC = i;
    ll choseB = k-i;

    // memo
    ll a_ = a;
    ll b_ = b;
    ll c_ = c;

    while (choseC) {
      c_ *= 2;
      choseC--;
    }
    while (choseB) {
      b_ *= 2;
      choseB--;
    }
    if (isOK(a_, b_, c_)) {
      ans = "Yes";
      break;
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
// #define endl '\n';
#define fi first
#define se second
#define NONVOID [[nodiscard]]
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
template <class T> inline void dump(T &v){irep(i, v){cout<<*i<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr double EPS = 1e-9;



int main() {

    int ans=0;
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k>0){
        if(k-a>=0){
            k-=a;
            ans+=a;
        } else {
            ans+=k;
            k=0;
        }
    }
    if(k>0){
        if(k-b>=0){
            k-=b;
        } else {
            k=0;
        }
    }
    if(k>0){
        if(k-c>=0){
            k-=c;
            ans-=c;
        } else {
            ans-=k;
            k=0;
        }
    }
    fin(ans);
}

Measured memory_bytes: 3636
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  ll r, d, x;
  cin >> r >> d >> x;
  REP(i,10){
    x = r*x-d;
    cout << x << endl;
  }
  return 0;
}


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

const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    cout << ((a*100+b*10+c)%4 == 0 ? "YES" : "NO") << endl;

    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())



int n;
long long k;
int a[200000];
int f[200000];

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

	cin >> n >> k;
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> f[i];

	sort(a, a + n);
	sort(f, f + n);

	reverse(a, a + n);

	long long lb = -1, ub = 1LL << 60;
	while (ub-lb>1) {
		auto mid = (lb + ub) / 2;

		long long m = 0;
		rep(i, n) {
			if (m > k)break;
			long long t = mid / f[i];
			if (t < a[i]) {
				m += a[i] - t;
			}
		}
		if (m <= k) {
			ub = mid;
		}
		else {
			lb = mid;
		}
	}
	cout << ub << endl;



	return 0;
}

Measured memory_bytes: 1792
//https://atcoder.jp/contests/dp/tasks/dp_c
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};


int main(){
    int N;
    cin>>N;
    vector<LL> dp(3);
    for(int i:range(N)){
        vector<LL> nxt(3);
        vector<LL> v(3);
        cin>>v;
        for(int j:range(3)){
            for(int k:range(3)){
                if(j!=k)chmax(nxt[k],dp[j]+v[k]);
            }
        }
        swap(dp,nxt);
    }
    cout<<*max_element(ALL(dp))<<endl;
    return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(10) << setiosflags(ios::fixed);

    int n;
    cin >> n;

    vector<double> x(n), y(n), dx(n), dy(n);
    for (int i = 0; i < n; ++i) {
        char d;
        cin >> x[i] >> y[i] >> d;

        if (d == 'R') dx[i] = 1;
        else if (d == 'L') dx[i] = -1;
        else if (d == 'U') dy[i] = 1;
        else if (d == 'D') dy[i] = -1;
    }

    const double INF = numeric_limits<double>::max();
    const double NINF = numeric_limits<double>::lowest();

    auto f = [&](const ld t) {
        pair<double, double> seg_x(INF, NINF), seg_y(INF, NINF);

        for (int i = 0; i < n; ++i) {
            double vx = x[i] + t * dx[i], vy = y[i] + t * dy[i];

            seg_x.first = min(seg_x.first, vx);
            seg_x.second = max(seg_x.second, vx);
            seg_y.first = min(seg_y.first, vy);
            seg_y.second = max(seg_y.second, vy);
        }
        return (seg_x.second - seg_x.first) * (seg_y.second - seg_y.first);
    };

    double min_v = f(0), lb = 0, ub = 1e9;
    for (int i = 0; i < 200; ++i) {
        const double t1 = (2.0 * lb + ub) / 3.0;
        const double t2 = (lb + 2.0 * ub) / 3.0;

        min_v = min(min_v, f(t1));
        min_v = min(min_v, f(t2));

        if (f(t1) > f(t2)) lb = t1;
        else ub = t2;
    }

    cout << min_v << endl;

    return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}

long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }


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

    pair<pair<string,int>,int> resu[110];

    rep(i,N){
        string s;
        int p =0;

        cin >> s >> p;
        resu[i]=make_pair(make_pair(s,-p),i);

    }

    sort(resu,resu+N);
    rep(i,N){
        cout << resu[i].second + 1 << endl;
    }

}



Measured memory_bytes: 3616
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, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

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

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	m := make(map[string]int)
	for i := 0; i < n; i++ {
		s := next()
		m[s]++
	}

	if len(m) == 3 {
		fmt.Println("Three")
	} else {
		fmt.Println("Four")
	}
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
//777...の約数にkがあるか->mod kでやる
//(7をkで割ったあまり)*10+7をkで割ったあまりをループでみる
//0になったら正解、同じあまりになったら答え収束しないので-1

class Program
{
    static void Main()
    {
        int k = int.Parse(Console.ReadLine());
        int x = 7 % k;
        var H = new HashSet<int>();
        int i=1;
        bool flag = false;
        while (!H.Contains(x))
        {
            if (x == 0) { flag = true; break; }
            H.Add(x);
            x = (x * 10 + 7) % k;
            i++;
        }
        if (flag) Console.WriteLine(i);
        else Console.WriteLine(-1);
    }
}

//namespace C
//{
//    class Program
//    {
//        static void Main(string[] args)
//        {
//            k = int.Parse(Console.ReadLine());
//            //L = new List<int>();
//            Console.WriteLine(F(7,0));
//        }
//        static int k;
//        //static List<int> L;
//        static int F(int x, int cnt)
//        {
//            int t = x % k;
//            cnt++;
//            if (t == 0) return cnt;
//            if (cnt>k) return -1;
//            else return F(t * 10 + 7,cnt);
//        }
//        //static bool Chk(int t)
//        //{
//        //    if (L.Contains(t)) return true;
//        //    else
//        //    {
//        //        L.Add(t);
//        //        return false;
//        //    }
//        //}
//    }
//}


Measured memory_bytes: 60448
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(readline().rstrip().decode("utf-8"))
S = readline().rstrip().decode("utf-8")

ans = 0
for i in range(N-1):
    left = S[:i+1] 
    right = S[i+1:]
    # print("left: {} right: {}".format(left, right))

    tmp = len(set(left) & set(right))
    ans = max(tmp, ans)
print(ans)



Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

int *read(int &n) {
    cin >> n;
    int *v = new int[n + 1];
    for (int i = 1; i <= n; ++i)
        cin >> v[i];

    return v;
}

int main() {
    int n;
    int *h = read(n);
    int *dp = new int[n + 1];
    for (int i = 0; i <= n; ++i) {
        dp[i] = 0;
    }

    dp[1] = 0;
    dp[2] = abs(h[1] - h[2]);
    for (int i = 3; i <= n; ++i) {
        dp[i] += min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    cout << dp[n] << '\n';
    free(h);
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int main(){
	
	string str;
	cin >> str;
	
	if(str[0] == str[2]){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int s,count[10000],i=1;
	scanf("%d", &s);
	for (int i = 0; i < 10000; i++) {
		count[i] = 0;
	}
	count[s]++;
	while (true) {
		i++;
		if (s % 2 == 0) {
			s /= 2;
		}
		else if (s % 2 == 1) {
			s = s * 3 + 1;
		}
		count[s]++;
		if (count[s] == 2) {
			printf("%d", i);
			return 0;
		}
	}
}

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

int main()
{
    int a,b,c,d,flag=0;
    char e[11];
    char s[100][11];
    // 整数の入力
    scanf("%d", &a);
    // 文字列の入力
     for(b=0;b<a;b++){
    	scanf("%s",e);
     	strcpy(s[b],e);
     }
    // 出力
  for(b=0;b<a;b++){
    for(d=0;s[b][d]!='\0';d++);
    if(s[b][d-1]!=s[b+1][0]&&b<(a-1))
    {
    flag=1;
    }
	for(c=b+1;c<a;c++){
    if(strcmp(s[b],s[c])==0){
     flag=1; 
     break;
    }      
    }
    if(flag==1){
    break;
    }
  }
  if(flag==0){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
typedef long long ll;

int main() {
  int N, Q;
  scanf("%d%d", &N, &Q);
  vector<tuple<int, int, int>> ST(N*2);
  for (int i = 0; i < N; i++) {
    int s, t, x;
    scanf("%d%d%d", &s, &t, &x);
    get<0>(ST[i*2]) = s - x;
    get<1>(ST[i*2]) = 2;
    get<2>(ST[i*2]) = x;
    get<0>(ST[i*2+1]) = t - x;
    get<1>(ST[i*2+1]) = 1;
    get<2>(ST[i*2+1]) = x;
  }
  vector<tuple<int, int, int>> D(Q);
  for (int i = 0; i < Q; i++) {
    scanf("%d", &get<0>(D[i]));
    get<1>(D[i]) = i;
    get<2>(D[i]) = 0;
  }
  sort(D.begin(), D.end());
  sort(ST.begin(), ST.end());
  map<int, int> r;
  int si = 0;
  for (int di = 0; di < Q; di++) {
    int d = get<0>(D[di]);
    for (; si < 2*N && get<0>(ST[si]) <= d; si++) {
      if (get<1>(ST[si]) == 1) {
        r.erase(get<2>(ST[si]));
      } else {
        r[get<2>(ST[si])] = get<0>(ST[si]);
      }
    }
    auto it = r.begin();
    if (it == r.end())
      get<2>(D[di]) = -1;
    else
      get<2>(D[di]) = it->first;
  }
  sort(D.begin(), D.end(), [](const tuple<int, int, int> &lhs, const tuple<int, int, int> &rhs){return get<1>(lhs) < get<1>(rhs);});
  for (int di = 0; di < Q; di++) {
    printf("%d\n", get<2>(D[di]));
  }
}


Measured memory_bytes: 17664
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 100;
constexpr int MOD = 1e9 + 7;

int fac[N], inv[N];

int binpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

int C(int n, int m){
    if(m < 0 or m > n) return 0;
    return 1LL * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

void Init(){
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = 1LL * fac[i - 1] * i % MOD;
    inv[N - 1] = binpow(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--) inv[i] = 1LL * inv[i + 1] * (i + 1) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Init();
    int s; 
    cin >> s;
    long long ans = 0;
    for (int i = 1; i <= s / 3; i++) {
        (ans += C(s - 3 * i + i - 1, i - 1)) %= MOD;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 11340
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
using namespace std;
using ll=long long;
#define MOD  1000000007




int main(int argc, char const *argv[]) {
  int n,T;
  std::vector<int> c,t,check;
  std::cin >> n >> T;
  for(int i=0; i<n; i++){
    int cost;
    int tim;
    std::cin >> cost >> tim;
    c.push_back(cost); t.push_back(tim);
  }
  int mini=9999,p;
  bool f=false; 
  for(int i=0; i<n; i++){
    if(t[i]<=T){
      if(mini>c[i]){
        mini=c[i];
        f=1;
         p=i+1;
      }
    }
  }
  if(f)std::cout << mini << '\n';

  else std::cout << "TLE" << '\n';
  return 0;
  
}

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

int N, M, s, t;
vector< int > graph[100000];

void bfs(int s, vector< int >& v)
{
  v.assign(N, -1);
  queue< int > que;
  que.push(s);
  v[s] = 0;
  while(!que.empty()) {
    int p = que.front(); que.pop();
    for(int to : graph[p]) {
      if(v[to] == -1) {
        v[to] = v[p] + 1;
        que.push(to);
      }
    }
  }            
}
int main()
{
  scanf("%d %d %d %d", &N, &M, &s, &t);
  --s, --t;
  for(int i = 0; i < M; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x, --y;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }

  vector< int > m1, m2;
  bfs(s, m1);
  bfs(t, m2);
  
  int sum1[100001] = {}, sum2[100001] = {};
  for(int k : m1) if(k >= 0) sum1[k]++;
  for(int k : m2) if(k >= 0) sum2[k]++;
  long long ret = 0;
  for(int i = 0; i < m1[t] - 1; i++) {
    ret += 1LL * sum1[i] * sum2[m1[t] - 2 - i];
  }
  printf("%lld\n", ret);
}

Measured memory_bytes: 10976
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define PI 3.141592653589793238
#define INF 1050000000

using vi = vector<int>;


int main() {

	int a, b;

	cin >> a >> b;

	cout << (b < a ? a - 1 : a) << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int n; cin >> n;
  int mx = 0;
  map<string, int> m;
  rep(i, n){
    string s; cin >> s;
    m[s]++;
    mx = max(mx, m[s]);
  }
  vector<string> ans;
  for(auto itr = m.begin(); itr != m.end(); itr++){
    if(itr->second == mx){
      ans.emplace_back(itr->first);
    }
  }
  sort(All(ans));
  for(string s : ans) cout << s << endl;
  system("pause");
}


Measured memory_bytes: 27492
import Control.Monad

main = do
  n <- readLn
  xy <- ([0, 0, 0] :) . map (map read . words) <$> replicateM n getLine
  putStrLn $ if and (g f xy) then "Yes" else "No"

f :: [Int] -> [Int] -> Bool
f [ax, bx, cx] [ay, by, cy]
  = let distance = abs(by - bx) + abs(cy - cx)
        time = ay - ax
     in (distance <= time) && (distance `mod` 2 == time `mod` 2)

g :: ([Int] -> [Int] -> Bool) -> [[Int]] -> [Bool]
g _ [_] = []
g f (x:y:xs) = f x y : g f (y:xs)

Measured memory_bytes: 73084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll w[1000];
ll v[1000];
ll dp[100010][2];
int main()
{
    int N,W;
    scanf("%d%d",&N,&W);
    for(int i=1; i<=N; i++)
    {
        scanf("%lld%lld",&w[i],&v[i]);
    }
    for(int i=1; i<=N; i++)
    {
        for(int j=w[i];j<=W;j++)
        {
            dp[j][1] = v[i];
        }
        for(int j=1; j<=W; j++)
        {
            if(w[i]<=j) dp[j][1] = max(dp[j][1],max(dp[j-1][0],dp[j-w[i]][0]+v[i]));
            else dp[j][1] = max(dp[j-1][0],dp[j][1]);
        }
        for(int j=0; j<=W; j++)
        {
            dp[j][0] = dp[j][1];
        }
    }
    printf("%lld\n",dp[W][1]);
}


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

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

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

    int ans = 0;
    FOR(i, 1, N+1) {
        if (i % 2 == 0) continue;

        int cnt = 0;
        FOR(j, 1, i + 1) {
            if (i % j == 0) cnt++;
        }

        if (cnt == 8) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
#define de(x) cout << #x << "=" << x << endl;
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
vector<ll> ans;
struct edge{ll to,num;};
struct graph{
    ll N;
    vector<vector<edge> > G;
    vector<bool> used;
    vector<ll> parity;

    graph(ll n): N(n), G(N), used(N,false), parity(N) {}

    void add_edge(ll s, ll t, ll num){
        G[s].emplace_back((edge){t, num});
        G[t].emplace_back((edge){s, num}); //無向ならON
    }

    void dfs(ll v=0){
        used[v]=true;
        for(auto E : G[v]){
            if(!used[E.to]){
                dfs(E.to);
                if(parity[E.to]==1){
                    ans.emplace_back(E.num);
                    parity[v]^=1;
                }
            }
        }
    }
};
//--MAIN-----------------------------------
void Main() {
    ll N,M; cin>>N>>M;
    vector<P> AB(N);
    rep(i,N) cin>>AB[i].first>>AB[i].second;
    SORT(AB);
    vector<ll> A(N);
    rep(i,N) A[i]=AB[i].first;

    graph g(N+1);

    ll x=0;
    rep(i,N){
        g.parity[i]=x^AB[i].second;
        x=AB[i].second;
    }
    g.parity[N]=x;

    rep(i,M){
        ll c,d; cin>>c>>d;
        ll citi=lower_bound(ALL(A),c)-A.begin();
        ll diti=upper_bound(ALL(A),d)-A.begin();
        g.add_edge(citi,diti,i+1);
    }

    rep(i,N+1){
        if(g.used[i]) continue;
        g.dfs(i);
        if(g.parity[i]==1) dame;
    }

    SORT(ans);

    cout<< ans.size() <<"\n";
    for(auto x: ans) cout<< x <<" ";
    cout<<"\n";
}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 20348
#include <iostream>
using namespace std;
  
int main()
{
  while(1){
    int h,w;
    cin >> h >> w;
    if(h == 0 && w == 0) break;
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
        if(i==0 || i==h-1 || j==0 || j==w-1) cout << "#";
        else cout << ".";
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define endl '\n'
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;


template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

const ll INF=1e9+7;


int main(){
    ll n;
    cin >> n;
    ll a,b;
    cin >> a >> b;
    if(n==1 && a!=b){
        cout << 0 << endl;
        return 0;
    }
    else if(a>b){
        cout << 0 << endl;
        return 0;
    }
    cout << b*(n-1)+a-(a*(n-1)+b)+1 << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 2e9;


/*
!) 0-indexed
!) [a, b)に対する演算
!) m0 / l0 : 初期化する値
!) merge, updateNode, propagateを書く
*/
template <typename Monoid>
struct LazySegtree {
    int n;
    vector<Monoid> dat, lazy;
    Monoid M0, L0;

    void init(int sz, Monoid m0, Monoid l0) {
        n = 1;
        M0 = m0;
        L0 = l0;
        while (n < sz) n *= 2;
        dat.assign(2*n-1, M0);
        lazy.assign(2*n-1, L0);
    }

    LazySegtree(int sz, Monoid m0, Monoid l0){
        init(sz, m0, l0);
    }

    LazySegtree(int sz, Monoid m0) {
        init(sz, m0, m0);
    }

    Monoid merge(Monoid a, Monoid b){
        // ##### WRITE HERE #####
        // 区間をマージする二項演算
        return max(a, b);
    }

    void updateNode(int k, Monoid x){
        // ##### WRITE HERE #####
        // 区間を更新する二項演算
        lazy[k] += x;
    }

    void propagate(int k){
        // ##### WRITE HERE #####
        // 遅延配列の伝搬のさせ方
        dat[k] += lazy[k];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] == L0) return;
        propagate(k);
        if(r-l > 1) {
            updateNode(2*k+1, lazy[k]);
            updateNode(2*k+2, lazy[k]);
        }
        lazy[k] = L0;
    }

    void update(int a, int b, Monoid x, int k, int l, int r) {
        eval(k, l, r);
        // 範囲外
        if (r <= a || b <= l) return;
        // [a, b)が[l, r)を被覆
        if (a <= l && r <= b) {
            updateNode(k, x);
            eval(k, l, r);
        }else{
            update(a, b, x, k*2+1, l, (l+r)/2);
            update(a, b, x, k*2+2, (l+r)/2, r);
            dat[k] = merge(dat[2*k+1], dat[2*k+2]);
        }
    }

    void update(int a, int b, Monoid x) {
        update(a, b, x, 0, 0, n);
    }

    Monoid query(int a, int b, int k, int l, int r) {
        eval(k, l, r);
        // 範囲外
        if (r <= a || b <= l) return M0;
        // [a, b)が[l, r)を被覆
        if (a <= l && r <= b) return dat[k];
        else {
            Monoid L = query(a, b, k*2+1, l, (l+r)/2);
            Monoid R = query(a, b, k*2+2, (l+r)/2, r);
            return merge(L, R);
        }
    }

    Monoid query(int a, int b){
        return query(a, b, 0, 0, n);
    }

    Monoid operator[](const int &k){ return dat[k + n - 1]; }
};

int main(){
    int n, q;
    cin >> n >> q;
    LazySegtree<int> seg(n+1, 0);

    rep(i, q){
        int p;
        cin >> p;
        if(p == 0){
            int s, t, x;
            cin >> s >> t >> x;
            seg.update(s, t+1, x);
        }else{
            int x;
            cin >> x;
            cout << seg.query(x, x+1) << endl;
        }
    }
}


Measured memory_bytes: 4960
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <cstring>
#include <cctype>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <complex>
using namespace std;

int main() {
	int N;
	while(cin >> N, N) {
		int map[21][21] = {};
		for(int i=0; i<N; i++) {
			int x, y;
			cin >> x >> y;
			map[x][y] = 1;
		}

		int M;
		cin >> M;
		int X=10, Y=10;
		for(int i=0; i<M; i++) {
			char d;
			int l;
			cin >> d >> l;
			for(int j=0; j<l; j++) {
				if(d=='N')
					Y++;
				else if(d=='E')
					X++;
				else if(d=='S')
					Y--;
				else if(d=='W')
					X--;
				N -= map[X][Y];
				map[X][Y] = 0;
			}
		}
		if(N) cout << "No" << endl;
		else cout << "Yes" << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e18;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll n, z, w; cin >> n >> z >> w;
    vl a(n); REP(i, n) cin >> a[i];
    if(n == 1){
        ll ans = abs(w-a[0]);
        cout << ans << endl;
        return 0;
    }
    else{
        ll ans = max(abs(a[n-1]-a[n-2]), abs(a[n-1] - w));
        cout << ans << endl;
    }
    return 0;
}


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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const ll mod = 1e9+7;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main()
{
 
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n,a,b;
	cin >>n >>a >>b;
	
	ll ans=0;
	rep2(i, 1, n+1){
		int sm =0;
		for(int w=i; w>0; w/=10) sm +=w%10;
		if(a<= sm && sm <= b) ans += i;
	}
	cout << ans <<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int X, Y, Z, ans = 0; cin >> X >> Y >> Z;
    X -= Z;
    while (true) {
        if (X < Y+Z) break;
        X -= (Y+Z);
        ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int MAXN = 100010;
int n, a[MAXN], f[MAXN];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),f[i]=0x3f3f3f3f;
	f[0] = f[1] = 0; a[0] = a[1];
	for(int i=2;i<=n;i++)
		f[i] = min(f[i-1]+abs(a[i]-a[i-1]),f[i-2]+abs(a[i]-a[i-2]));
	printf("%d\n",f[n]);
	return 0;
}

Measured memory_bytes: 1024