akhauriyash/Code-Regression huggingface dataset:
using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <functional>

typedef long long ll;



int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    long long n, d;
    cin >> n >> d;
    long long tot = 0;
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        if (x * x + y * y <= d * d) tot++;
    }
    cout << tot << endl;
}

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

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


Measured memory_bytes: 3184
#include <stdio.h>

int main()
{
  int n,i,sm=0,bi=0;
  int A[100000],B;

  //入力
  scanf("%d",&n);

  for(i=0;i<n;i++)
    {
      scanf("%d",&A[i]);
    }

  //並び替え
  for(i=0;i<n;i++)
    {
      if(A[i]<=A[n-1])
	{
	  B=A[i];
	  A[i]=A[sm];
	  A[sm]=B;
	  sm++;
	}
    }
  //出力
  printf("%d",A[0]);
  for(i=1;i<sm-1;i++)printf(" %d",A[i]);
  printf(" [%d]",A[sm-1]);
  for(i=sm;i<n;i++)printf(" %d",A[i]);
  printf("\n");
  return 0;
}



Measured memory_bytes: 2144
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
using namespace std;
 
int main() {
    int n; cin >> n;

    for(int i=0 ;i < n ;i++){
            int d1;
    int d2;
        cin >> d1;
        cin >> d2;
        if(d1 == d2){
            int d3;int d4;
            cin >> d3; cin >> d4;
            if(d3 == d4){
                int d5; int d6;
                cin >> d5; cin >> d6;
                if(d5 == d6){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }

    }
    cout << "No" << endl;
    

}

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

//------------------- mod ----------------------
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

//----------------combination---------//
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<bool> a(n);
    rep(i,m) {
        int tmp;
        cin >> tmp;
        a[tmp] = true;
    }


    vector<mint> dp(n+1);
    dp[0] = 1;
    if(a[1]) dp[1] = 0;
    else dp[1] = 1;

    rep(i,n-1){
        if(a[i+2]) dp[i+2] = 0;
        else dp[i+2] = dp[i+1] + dp[i];
    }

    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 1024
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 100001;

int n;
int a[MAX];
long long sum[MAX];

void solve() {
	sum[n] = 0;
	for (int i = n - 1; i >= 0; i--)
	    sum[i] = sum[i + 1] + a[i + 1];
	
	long long ans = 0, cur = 1;
	for (int i = 0; i <= n; i++) {
	    // fprintf(stderr, "At level %d with cur = %lld (required %d leaves)\n", i, cur, a[i]);
	    ans += cur;
	    if (cur < a[i]) {
	        fprintf(out, "-1\n");
	        return;
        }
        cur -= a[i];
        cur = min(sum[i], cur * 2);
    }
    fprintf(out, "%lld\n", ans);
}

int main(void) {
	// in = fopen("C.in", "rt");
	
	fscanf(in, "%d", &n);
	for (int i = 0; i <= n; i++)
	    fscanf(in, "%d", &a[i]);
	
	solve();
	
    return 0;
}

Measured memory_bytes: 2896
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        int s = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        int ans = 1;
        while (true) {
            set.add(s);
            if (s % 2 == 0) {
                s /= 2;
            } else {
                s = 3 * s + 1;
            }
            ans++;
            if (set.contains(s)) {
                System.out.println(ans);
                return;
            }
        }
    }
}


Measured memory_bytes: 23252
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = "";
		
		while((input = br.readLine()) != null){
			String[] arr = input.split(" ");
	
			int a = Integer.parseInt(arr[0]);
			int b = Integer.parseInt(arr[1]);
	
			int inputAngka = a + b;
	
			System.out.println(count(inputAngka));
		}

	}

	public static int count(int a) {
		if (a < 10) {
			return 1;
		} else {
			return 1 + count(a / 10);
		}
	}

}

Measured memory_bytes: 15160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication32
{
    class Program
    {  
      static void Main()
      {
		int a = int.Parse(Console.ReadLine());
		var b = Console.ReadLine().Split().Select(int.Parse).ToArray();
		long d =0;
		Array.Sort(b);
		for(int c =0;c<a;c++)
		 d+=b[c];
		 Console.WriteLine("{0} {1} {2}",b[0],b[a-1],d);
       }
	 }
 }

Measured memory_bytes: 10684
#include <bits/stdc++.h>
////////////////////////////////////////////////////////////
#define all(x) x.begin(), x.end()
#define inf 1e9
#define INF 1e15
#define fastio ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
#define for_n(i,n) for(int i=0;i<n;i++)

////////////////////////////////////////////////////////////
using namespace std;
 
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<ii> vii;

int di[5];
int main() {
	int n, m; cin >> n >> m;
	vii c(m);
	for_n(i,m) cin >> c[i].first >> c[i].second;
	auto cnt = [](int k) {
		int ret = 1;
		while(k >= 10) {
			k/=10;
			ret++;
		}
		return ret;
	};
	auto get = [](int k, int d) {
		while(d > 0) {
			k /= 10;
			d--;
		}
		return k%10;
	};
	int mini = -1;
	for_n(i, 1000) {
		if(cnt(i) != n) continue;
		bool ok = true;
		for_n(j, m) {
			if(get(i, n-c[j].first) != c[j].second) ok = false;
		}
		if(ok) {
			mini = i;
			break;
		}
	}
	cout << mini;
}

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

int main() {
  int n, q;
  cin >> n >> q;
  dsu d(n);
  for (int i = 0; i < q; i++) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 0) {
      d.merge(u, v);
    } else {
      cout << (d.leader(u) == d.leader(v)) << endl;
    }
  }
}


Measured memory_bytes: 4068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll n;
	cin >> n;
	print(n/3)
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<double> v(n);
  REP(i, n)
    cin >> v.at(i);
  sort(v.begin(), v.end());
  
  while (n > 1) {
    v.at(1) = (v.at(0) + v.at(1)) / 2.0;
    v.erase(v.begin());
    --n;
  }
  
  cout << fixed << setprecision(5) << v.at(0) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }

int n,k,c;
string S;
int kolikOdpracuje[422222];
void solve(istream& cin, ostream& cout) {
	cin >> n >> k >> c;
	cin >> S;
	for(int i = n-1; i >= 0; i--) {
		kolikOdpracuje[i] = kolikOdpracuje[i+1];
		if(S[i]== 'o') {
			kolikOdpracuje[i] = max(
				kolikOdpracuje[i],
				1+kolikOdpracuje[i+c+1]
			);
		}
	}
	int last = -c-10;
	int mam = 0;
	REP(i, n) {
		if(S[i]== 'o') {
	//		cout << "i = " << i << ", mam: " << mam << endl;
			bool kanz = mam+kolikOdpracuje[max(last+c+1, i)] >= k;
			if(kanz && mam+kolikOdpracuje[max(last+c+1, i+1)] < k) {
				cout << i+1 << endl;
			}
			if(i >= last+c+1) {
				mam++;
				last = i;
			}
		}
	}
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 2580
N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10 ** 9

dp = [INF] * N
dp[0] = 0

for i in range(N - 1):
    for k in range(1, K + 1):
        if i + k > N - 1:
            break
        dpp = dp[i] + abs(h[i + k] - h[i])
        dp[i + k] = min(dp[i + k], dpp)

print(dp[-1])

Measured memory_bytes: 52448
W, H, x, y, r = map(int, input().split())

#xまたはyがマイナスの場合、No
if x < 0 or y < 0 :
    print("No")

#(x, y)が長方形上、もしくは長方形の外にある場合、NO
elif W <= x or H <= y :
    print("No")

elif x < W and y < H and r <= x and r <= y :
    print("Yes")

else :
    print("No")



Measured memory_bytes: 5596
import java.util.Scanner;

class Main {
	int a,b,c;
	int x,y;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Main m = new Main(sc);
		m.solve();
		sc.close();
	}
	Main(Scanner sc){
		a = sc.nextInt();
		b = sc.nextInt();
		c = sc.nextInt();
		x = sc.nextInt();
		y = sc.nextInt();
	}
	void solve(){
		int cost = 0;
		if(a + b > 2 * c){
			while(x > 0 && y > 0){
				cost += 2 * c;
				x--;y--;
			}
			if(x > 0){
				if(a > 2 * c){
					while(x > 0){
						cost += 2 * c;
						x--;
					}
				} else {
					while(x > 0){
						cost += a;
						x--;
					}
				}
			} else if(y>0) {
				if(b > 2 * c){
					while(y > 0){
						cost += 2 * c;
						y--;
					}
				} else {
					while(y > 0){
						cost += b;
						y--;
					}
				}
			}
		} else {
			cost += a * x;
			x = 0;
			cost += b * y;
			y = 0;
		}
		System.out.println(cost);
	}
}

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

int main(){
	int N, K, ans=0;
  	cin >> N >> K;
	vector<int> p(N);
	
  	for(int i=0; i<N; i++){
    	cin >> p[i];
    }
  	sort(p.begin(),p.end());
  	
  	for(int i=0; i<K; i++){
    	ans+=p[i];
    }
  	cout << ans << endl;
	return 0;
}

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

long long N, H;
long long a[100005];
long long b[100005];
vector<long long> vecb;
long long maxia;

int main(){
	cin >> N >> H;
	for(long long i = 0; i < N; i++){
		cin >> a[i] >> b[i];
		maxia = max(maxia, a[i]);
	}

	for(long long i = 0; i < N; i++){
		if(b[i] > maxia)
			vecb.push_back(b[i]);
	}

	sort(vecb.begin(), vecb.end(), greater<long long>());

	long long num = 0;

	for(long long i = 0; i < vecb.size(); i++){
		H -= vecb[i];
		num++;
		if(H<=0) {
			cout << num << endl;
			return 0;
		}
	}

	if(H%maxia==0){
		cout << num + H/maxia << endl;
	}else{
		cout << num + H/maxia + 1 << endl;
	}
}

Measured memory_bytes: 2936
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}



int main(){
  int n;cin>>n;
  string s;cin>>s;
  int a = 0;
  for(int i = 0; s.size()-2 > i; i++){
    if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
      a++;
      i+=2;
    }
  }
  cout << a << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string o, e;
	cin >> o;
	cin >> e;
	for (int i = 0; i < e.length(); i++) {
		cout << o.at(i) << e.at(i);
	}
	if (o.length() > e.length())cout << o.at(o.length() - 1);
	cout << endl;
}

Measured memory_bytes: 256
// In the name of GOD
 
#include <bits/stdc++.h>
#define ll long long
#define pp pair <int, int>
using namespace std;
const int N = 3e3 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

void solve() {
	int h1, m1, h2, m2;
	cin >> h1 >> m1 >> h2 >> m2;
	int k;
	cin >> k;
	int ans = (h2 - h1)*60;
	if (m1 <= m2)
		ans += m2 - m1;
	else
		ans += (m2 - m1);
	cout << ans - k;
}

int main () {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    }
}                                  

Measured memory_bytes: 3652
n=int(input())
pl=list(map(int,input().split()))

count=1
temp=pl[0]
l=[pl[0]]
for i in range(1,n):
    if pl[i]<temp:
        temp=pl[i]
        l.append(temp)
    else:
        l.append(temp)
    if pl[i]<=temp:
        count+=1
print(count)

   

Measured memory_bytes: 26012
// package app;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

    public static void main(final String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];

        Map<Integer, Long> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();

            if (!map.containsKey(a[i])) {
                map.put(a[i], (long) 1);
            } else {
                map.put(a[i], map.get(a[i]) + 1);
            }
        }

        long all = 0;

        for (int key : map.keySet()) {
            all += map.get(key) * (map.get(key) - 1) / 2;
        }

        for (int i = 0; i < n; i++) {
            long tmp = map.get(a[i]);
            System.out.println(all - (tmp - 1));
        }
    }
}

Measured memory_bytes: 108492
# Z-Algorithm
# 計算量はO(N) ：各要素高々2回しか走査しない
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    while (i < N):
        while (i + j < N and S[j] == S[i + j]):
            j += 1 # 一致している限りj(共通接頭辞の右端)を右に伸ばす
        A[i] = j
        # 一致が無ければ次へ
        if j == 0:
            i += 1
            continue
        
        # 共通接頭辞があった場合、それを利用する
        k = 1
        while (i + k < N and k + A[k] < j):
            # i + k < N の意味：i からkだけ離れた場所がS内に収まる
            # k+A[k] < j の意味：SとA[i]との最大共通接頭辞の長さに収まる
            A[i + k] = A[k]
            k += 1
        i += k # 後ろがはみ出していた共通接頭辞の開始位置に移動
        j -= k # はみ出しはじめに移動(S[j:]~とS[i+j:]がさっきまでの共通接頭辞からはみ出している)

    return A

def main():
    N = int(input())
    S = input()
    res = 0
    # 各iに対してS[i:]を考え、それについてZ_algoを適用する。
    # 各suffixに対して完全一致を除いた最長共通接頭辞の長さを求めれば良い。
    for i in range(N):
        lcp = z_algo(S[i:])
        for j in range(len(lcp)):
            l = min(j, lcp[j])
            res = max(res, l)
    print(res)

if __name__ == "__main__":
    main()

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

int main() {
  int n; cin >> n;
  vector<double> v;
  for(int i=0; i < n; i++){
    int a; cin >> a;
    v.push_back(a);
  }
  sort(v.begin(), v.end());
  double result = 0;
  for(int i=0; i < n-1; i++){
    v[i+1] = (v[i] + v[i+1]) / 2.0;
  }
  cout << v[v.size()-1] << endl;
}


Measured memory_bytes: 256
n,e[999],*p,*r,d[21];
B(s){
	memset(d,1,84);
	d[s]=0;
	for(s=n;--s;){
		for(p=e;r-p;p+=4){
			d[p[0]]=fmin(d[p[0]],d[p[1]]+p[3]);
			d[p[1]]=fmin(d[p[1]],d[p[0]]+p[2]);
		}
	}
}
main(t,s){
	scanf("%d%*d",&n);
	for(r=e;~scanf("%d,",r++););
	r-=5;
	B(r[0]),t=d[s=r[1]],B(s);
	n=!printf("%d\n",r[2]-r[3]-t-d[r[0]]);
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    string s, t; cin>>s>>t;
    int n = s.size(), m = t.size();
    vector<int> ssum(n+10, 0), tsum(m+10, 0);

    for(int i=0; i<n; i++){
        if(s[i] == 'A') ssum[i+1] = ssum[i] + 1;
        else ssum[i+1] = ssum[i] + 2;
    }
    
    for(int i=0; i<m; i++){
        if(t[i] == 'A') tsum[i+1] = tsum[i] + 1;
        else tsum[i+1] = tsum[i] + 2;
    }

    int q; cin>>q;
    while(q--){
        int a, b, c, d; cin>>a>>b>>c>>d;
        int snum = ssum[b] - ssum[a-1];
        int tnum = tsum[d] - tsum[c-1];

        if(snum % 3 == tnum % 3){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
}

Measured memory_bytes: 1664
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break
    count = 0
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            for k in range(j+1, n+1):
                if i + j + k == x:
                    count += 1
    print(count)


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

using namespace std;

#define db(m)  cout<<#m<<" = "<<m<<"\n"

#define MAX 10005
typedef long long ll;

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

    ll n; cin>>n;
    ll k = (n + 1000 - 1) / 1000;
    cout<<(k * 1000) - n<<"\n";
    return 0;
}
// Check corner case for 1
//Check constraint & SIZE

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
//ABC146のB
int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	rep(i, s.size()) {
		s[i] = (s[i] - 'A' + n) % 26 + 'A';
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int cnt;
int L[250002],R[250002];

void merge(int A[],int n,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;
    for(int i=0;i<n1;i++)L[i]=A[left+i];
    for(int i=0;i<n2;i++)R[i]=A[mid+i];
    L[n1]=2000000000;
    R[n2]=2000000000;

    int i=0,j=0;
    for(int k=left;k<right;k++){
        cnt++;
        if(L[i]<=R[j]){
            A[k]=L[i++];
        }
        else{
            A[k]=R[j++];
        }
    }
}
void mergeSort(int A[],int n,int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergeSort(A,n,left,mid);
        mergeSort(A,n,mid,right);
        merge(A,n,left,mid,right);
    }
}

int main(){
    int A[500000];
    int n,i;
    cnt=0;
    cin>>n;
    for(i=0;i<n;i++)cin>>A[i];

    mergeSort(A,n,0,n);

    for(i=0;i<n;i++){
        if(i)cout<<" ";
        cout<<A[i];
    }
    cout<<endl;
    cout<<cnt<<endl;

    return 0;
}


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

int main() {
  int a,b,ans;
  cin >> a >> b;
  bool flag = false;
  for(int i=1; i<2000; i++) {
    int aa = i*0.08;
    int bb = i*0.1;
    if(aa == a && bb == b) {
      ans = i;
      flag = true;
      break;
    }
  }
  if(flag) cout << ans << endl;
  else cout << -1 << endl;
}

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

#define what_is(x) cerr << #x << " is " << x << endl;

const ll LMAX = (1LL<<61);
const int IMAX = (1<<29);
const int BIG = 104206970;
const int PRIME = 104206969;

const int N = 200001;
const int MOD = 1e9+7;

set<int> category[10][10];

int main () {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// cout.precision(9); cout << fixed;
	for (int i = 1; i < N; i++) {
		int start = -1, end = i%10;
		int prev = end;
		int temp = i;
		while (temp > 0) {
			prev = temp%10;
			temp /= 10;
		}
		start = prev;
		if (start == 0 or end == 0)
			continue;
		category[start][end].insert(i);
	}
	for (int i = 1; i < 10; i++)
		for (int j = 1; j < 10; j++)
			category[i][j].insert(MOD);
	int n; cin >> n;
	int ans = 0;
	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			// for (int ii = 1; ii < 10; ii++) {
			// 	for (int jj = 1; jj < 10; jj++) {
					int A = distance(category[i][j].begin(),category[i][j].upper_bound(n));
					int B = distance(category[j][i].begin(),category[j][i].upper_bound(n));
					ans += A*B;
			// 	}
			// }
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 8704
import math

oneYear = 20*5 + 19*5
threeYears = oneYear*2 + 20*10
millennium = 196471

N = int(input())
for i in range(N):
    data = input().split()
    birthYear = int(data[0])
    birthMonth = int(data[1])
    birthDay = int(int(data[2]))

    day = 0
    #Calc passed years
    passedYears = birthYear - 1
    day += (passedYears%3 * oneYear) + (math.floor(passedYears/3)*threeYears)
    if birthYear%3 == 0:
        passedMonth = birthMonth-1
        day += passedMonth*20
        day += birthDay
    else:
        passedMonth = birthMonth-1
        day += math.floor(passedMonth/2) * 39
        day += passedMonth%2 * 20
        day += birthDay
    ans = millennium - day
    print(ans)



Measured memory_bytes: 5660
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll n,k;cin>>n>>k;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    ll l=0,r=inf;
    while(r-l>1){
        ll mid=(r+l)/2;
        ll cnt=0;
        rep(i,n){
            cnt+=(a[i]-1)/mid;
        }
        //cout<<mid<<' '<<cnt<<endl;
        if(cnt<=k)r=mid;
        else l=mid;
    }
    cout<<r<<endl;
}


Measured memory_bytes: 4732
#include <bits/stdc++.h>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

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 vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int N;
int prime[1001];//i番目の素数の数
ll MOD = 1000000007;
int factorization(int n){
  int i = 2;
  int temp = n;
  while (i*i <= n){
    while (temp % i == 0){
      prime[i]++;
      temp /= i;
    }
    i++;
  }
  if (temp != 1){
    prime[temp]++;
  }
}

    
int main(){
  cin >> N;
  rep(i, N+1) prime[i] = 0;
  rep(i, N) factorization(i + 1);
  ll ans = 1;
  rep(i, N+1){
    if (prime[i] != 0){
      ans *= (prime[i] +1);
      ans %= MOD;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
H,N = map(int,input().split());INF = float("inf")
A=[];B=[]
for i in range(N):
  a,b = map(int,input().split())
  A.append(a);B.append(b)
#print(A,B)

dp = [INF for _ in range(H+1)] #dp[i] HPがi残っているときの、魔力の消費最小
dp[H] = 0
for i in reversed(range(H+1)):
  #print(i)
  #print(dp)
  for j in range(N):
    if i - A[j] >= 0:
      dp[i-A[j]] = min(dp[i-A[j]], dp[i] + B[j])
    else:
      dp[0] = min(dp[0], dp[i] + B[j])
ans = dp[0]
print(ans)

Measured memory_bytes: 74156
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
 
struct Puddle{
    int start, end, area;
};
 
int main(){
    string str;
    cin >> str;
    int n = str.size(), overall = 0;
    stack<Puddle> S;
    stack<int> slope;
 
    for(int i = 0; i < n; i++){
        if(str[i] == '\\'){
            slope.push(i);
        } else if(str[i] == '/'){
            if(!slope.empty()){
                int b = slope.top();
                Puddle temp;
                temp.start = b;
                slope.pop();
                temp.end = i;
                temp.area = i-b;
                overall += temp.area;
                while( !S.empty() ){
                    if(temp.start < S.top().start){
                        temp.area += S.top().area;
                        S.pop();
                    } else {
                        break;
                    }
                }
                S.push(temp);
            }
        }
    }
    cout << overall << endl;
    int m = S.size(), A[m];
    cout << m;
    for(int i = 0; i < m; i++){
        A[m - i - 1] = S.top().area;
        S.pop();
    }
    for(int i = 0; i < m; i++)
        cout << " " << A[i];
    cout << endl;
}

Measured memory_bytes: 1312
//https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0512?year=2007

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); ++i) {
        s[i] -= 3;
        if (s[i] < 'A') s[i] += 26;
    }

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

/*
 *
 */


Measured memory_bytes: 3196
S = input()
A = []
for i in range(len(S)):
    if S[i] == '0':
        A.append('0')
    elif S[i] == '1':
        A.append('1')
    else:
        if len(A) != 0:
            A.pop(-1)
        else:
            pass
print(''.join(A))

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

int main(){
    int H,W;cin>>H>>W;
    vector<string>field(H);
    vector<int>dx={-1,0,1,0};
    vector<int>dy={0,1,0,-1};
    rep(i,H){
        cin>>field.at(i);
    }
    int ans=0;
    rep(i,H){
        rep(j,W){
            if(field.at(i).at(j)=='#'){
                continue;
            }
            else{
                vector<vector<int>>data(H,vector<int>(W,-1));
                queue<pair<int,int>>que;
                que.push(make_pair(i,j));
                data[i][j]=0;
                while(!que.empty()){
                    int y=que.front().first;
                    int x=que.front().second;
                    que.pop();
                    rep(k,4){
                        int ny=y+dy[k]; int nx=x+dx[k];
                        if(ny>=H||ny<0||nx>=W||nx<0){
                            continue;
                        }
                        if(field.at(ny).at(nx)=='#'){
                            continue;
                        }
                        if(data[ny][nx]!=-1){
                            continue;
                        }
                        data[ny][nx]=data[y][x]+1;
                        que.push(make_pair(ny,nx));
                    }
                }
                rep(s,H){
                    rep(t,W){
                        ans=max(ans,data[s][t]);
                    }
                }

            }
        }
    }
    cout<<ans<<endl;
}

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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define SORT(v, n) sort(v, v + n)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define ddvi vector<vector<int>>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

// べき剰余 (x^k) % n
ll powMod(ll x, ll k, ll m)
{
    if (k == 0)
        return 1;
    if (k % 2 == 0)
        return powMod(x * x % m, k / 2, m);
    else
        return x * powMod(x, k - 1, m) % m;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ここに処理を記述

    ll N, P;
    string S;

    cin >> N >> P;
    cin >> S;

    reverse(S.begin(), S.end());

    ll ans = 0;
    if (P == 2 || P == 5)
    {
        REP(i, S.size())
        {
            if ((S[i] - '0') % P == 0)
            {
                ans += (N - i);
            }
        }
    }
    else
    {
        map<ll, ll> count;
        ll prev_amari = 0;
        REP(i, S.size())
        {
            ll num = S[i] - '0';
            num = num * powMod(10, i, P);
            num %= P;

            count[(prev_amari + num) % P]++;
            prev_amari = (prev_amari + num) % P;
        }

        for (auto itr = count.begin(); itr != count.end(); itr++)
        {
            ll temp = itr->second;
            if (itr->first == 0)
            {
                ans += temp;
            }
            ans += (temp) * (temp - 1) / 2;
        }
    }

    cout << ans << "\n";

    return 0;
}


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

int main() {
  int N;
  string s;
  cin >> N;
  for (int i=1; i <= N; i++){
    cin >> s;
    if (s == "Y"){
      cout << "Four" << endl;
      break;
    }
    else 
      if (i != N)
        continue;
      if (i == N)
      cout << "Three" << endl;
      
  }
}    

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

int main() {
  int n;
  int value =0;
  cin >> n;
  for(int i=0; i<n; i++){
    int a,b;
    cin >> a >> b;
    value += b-a+1;
  }
  cout << value << endl;
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;
using System.IO;

class Solve
{
	const int mod = 1000000007;
	static void Main(string[] args)
	{
        var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
		Console.SetOut(sw);

		int N = int.Parse(Console.ReadLine());
		string[] s = new string[N];
        for(var i = 0; i < N; i++)
		{
			s[i] = Console.ReadLine();
		}
		int M = int.Parse(Console.ReadLine());
		string[] t = new string[M];
        for(var i = 0; i < M; i++)
		{
			t[i] = Console.ReadLine();
		}

		List<int> ans = new List<int>();
        for(var i = 0; i < N; i++)
		{
			int sc = s.Where(x => x == s[i]).Count();
			int tc = t.Where(x => x == s[i]).Count();
			if (sc - tc > 0) { ans.Add(sc - tc); }
		}
		Console.WriteLine(ans.Count > 0 ? ans.Max() : 0);

		Console.Out.Flush();
	}
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
    int N;cin>>N;
    int A[N];
    REP(i,N)cin>>A[i];
    int ans=N;
    int back=0;
    int top=0;
    int sum=A[0];
    while(back<N){
        while(top<N-1&&(sum+A[top+1])==(sum^A[top+1])){
          	top++;
          	sum+=A[top];
        }
        ans+=top-back;
        sum-=A[back];back++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>

using namespace std;

typedef long long int ll;

const ll MOD = 1000000007;

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

  string S;
  cin >> S;

  int n = S.size();
  vector<int> bucket(n);
  int e = 0, o = 0;
  int point = 0;
  bool rnow = true;
  for (int i = 0; i < n; i++) {
    if (rnow && S[i] == 'L') {
      point = i;
      rnow = false;
    }
    else if (!rnow && S[i] == 'R') {
      if (point % 2 == 0) {
        bucket[point-1] = e;
        bucket[point] = o;
      }
      else {
        bucket[point-1] = o;
        bucket[point] = e;
      }
      e = 0;
      o = 0;
      rnow = true;
    }
    if (i % 2 == 0) o++;
    else e++;
  }
  if (point % 2 == 0) {
    bucket[point-1] = e;
    bucket[point] = o;
  }
  else {
    bucket[point-1] = o;
    bucket[point] = e;
  }

  for (int i = 0; i < n; i++) {
    cout << bucket[i];
    if (i < n-1) cout << " ";
    else cout << endl;
  }

  return 0;
}


Measured memory_bytes: 1104
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define it ::iterator
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double ESP=1e-10;
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  vector<vector<int> >in(a);
  rep(i,a){
    rep(j,b){
      int tmp;
      cin>>tmp;
      in[i].pb(tmp);
    }
  }
  vector<int>out(b);
  rep(i,b)cin>>out[i];
  rep(i,a){
    int ans=0;
    rep(j,b){
      ans+=in[i][j]*out[j];
    }
    cout<<ans<<endl;
  }



}

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

int n,l;
int s[86402],t[86402],u[86402];

bool C(long double v){
	long double st=(long double)l;
	long double ss=0.0;
	for(int j=0;j<2;j++){
		int koko=0;
		for(int i=0;i<86400;i++){
			if(koko<n && t[koko]<=i)koko++;
			if(koko<n && s[koko]<=i){
				st-=(long double)u[koko];
			}
			st+=v;
			if(st<0.0)return false;
			st=min(st,(long double)l);
		}
		if(j==0)ss=st;
		if(j==1){
			if(st>=ss)return true;
			else return false;
		}
	}
}

int main(void){
	while(1){
		scanf("%d%d",&n,&l);
		if(n==0 && l==0)break;
		for(int i=0;i<n;i++){
			scanf("%d%d%d",&s[i],&t[i],&u[i]);
		}
		double lv=0.0,rv=1000000;
		for(int i=0;i<50;i++){
			long double mid=(lv+rv)/2.0;
			if(C(mid))rv=mid;
			else lv=mid;
		}
		printf("%.10f\n",(double)rv);
	}
	return 0;
}

Measured memory_bytes: 4192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define printYes() cout << "Yes" << endl;
#define printNo() cout << "No" << endl;
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int N;
  cin >> N;
  bool is_ok = true;
  rep(i, N)
  {
    int A;
    cin >> A;
    if (A % 2 == 0)
    {
      if (!(A % 3 == 0 || A % 5 == 0))
        is_ok = false;
    }
  }
  if (is_ok)
  {
    cout << "APPROVED" << endl;
  }
  else
  {
    cout << "DENIED" << endl;
  }
  return 0;
}

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

#define int long long

signed main() {
	int n;
	cin >> n;
	string str;
	vector<string> v;
	for(int i = 0; i < n; i++) {
		cin >> str;
		sort(str.begin(),str.end());
		v.push_back(str);
	}
	sort(v.begin(),v.end());
	int count = 0;
	int i = 0;
	while(i<(n-1)) {
		int p = 0;
		for(int j = i+1; j < n; j++) {
			if(v[i]==v[j]) {
				p++;
			}
			else {
				i=j;
				break;
			}
			if(j==(n-1)) {
				i=j;
			}
		}
		int q = p*(p+1)/2;
		count += q;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 5748
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    ll k; cin >> k;
    ll now = 0;
    int ans = 0;
    while (true) {
        bool ok = false;
        rep(i,10) {
            ll tmp = now + k * i;
            if (tmp % 10 == 7) {
                swap(tmp,now);
                now /= 10;
                ans++;
                ok = true;
                break;
            }
        }
        if (!ok) {cout << -1 << endl; return 0;}
        if (now == 0) break;
    }
    cout << ans << endl;
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

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

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

    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
    }

    vector<int> b = a;
    SORT(b);

    int d = 0;
    vector<bool> dif(n);
    rep(i, n){
        dif[i] = (a[i] != b[i]);
        d += (int)dif[i];
    }

    int Q;
    cin >> Q;
    int ans = IINF;
    rep(q, Q){
        if(d == 0){
            chmin(ans, q);
        }
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        swap(a[x], a[y]);
        d -= dif[x] - (int)(a[x] != b[x]) + dif[y] - (int)(a[y] != b[y]);
        dif[x] = (a[x] != b[x]);
        dif[y] = (a[y] != b[y]);
    }
    if(d == 0){
        chmin(ans, Q);
    }

    if(ans < IINF){
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}


Measured memory_bytes: 5440
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;

const int INF=0x3f3f3f3f;
const int N=5e5+5;
const int LOG=20;

int n, q;
char s[N];
int dp[N][30];
int nxt[N][LOG];

int main() {
    memset(nxt, -1, sizeof nxt);
    scanf("%s", s);
    n=strlen(s);
//    printf("n == %d\n", n);
    for (int i=0; i<=26; ++i) {
        dp[n][i]=n;
        dp[n+1][i]=n;
    }
    for (int i=0; i<LOG; ++i) nxt[n][i]=n;

    for (int i=n-1; i>=0; --i) {
        dp[i][s[i]-'a']=i;
//        printf("%d ", dp[i][s[i]-'a']);
        for (int j=s[i]-'a'+1; j<=26; ++j) {
            if (dp[i][j-1]==n) dp[i][j]=n;
            else {
                dp[i][j]=dp[dp[i][j-1]+1][j-1];
//                dp[i][j]=min(dp[i][j], dp[dp[i+1][26]+1][j]);
            }
            if (dp[i][j]>n) dp[i][j]=n;
//            printf("%d ", dp[i][j]);
        }
        for (int j=0; j<s[i]-'a'; ++j) {
            dp[i][j]=dp[dp[i][26]+1][j];
            if (dp[i][j]>=n) dp[i][j]=n;
        }
//        printf("\n");
        nxt[i][0]=dp[i][26];
//        printf("%d ", nxt[i][0]);
        for (int j=1; j<LOG; ++j) nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];
    }
//    for (int i=0; i<n; ++i) printf("%d ", nxt[i][0]);
//    printf("\n");
    scanf("%d", &q);
    for (int j=0; j<q; ++j) {
        int l, r;
        scanf("%d %d", &l, &r); l--; r--;
        if (l==r) {
            printf("No\n");
            continue;
        }
        for (int i=LOG-1; i>=0; --i) {
            if (nxt[l][i]<=r && nxt[l][i]!=-1) {
                l=nxt[l][i];
                l++;
            }
        }
//        printf("l == %d\n", l);
        printf("%s\n", l==r+1 ? "Yes": "No");
    }
	return 0;
}

/*
yzyyyzyzyyyz
1
1 12
*/


Measured memory_bytes: 98816
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define N 100001
#define INF 1000000009
using namespace std;

struct Heap{
  int key,cost;
};

struct node{
  int key,cost;
  node *prev,*next;
};

node *nil[N];
int n,d[N];
Heap A[N];

void init(){
  for(int i=0;i<n;i++){
  nil[i] = (node *)malloc(sizeof(node));
  nil[i]->next =nil[i];
  nil[i]->prev=nil[i];
  }
}

void insert(int i,int key,int cost){
  node *x= (node *)malloc(sizeof(node));
  x->key = key,x->cost=cost;
  x->next = nil[i]->next;
  nil[i]->next->prev = x;
  nil[i]->next = x;
  x->prev = nil[i];
}

int size;
void increase(int i,int key,int cost){
  Heap tmp;
  A[i].key=key,A[i].cost=cost;
  while(i>1 && A[i/2].cost > A[i].cost)tmp=A[i],A[i]=A[i/2],A[i/2]=tmp,i=i/2;
}

void insert(int key,int cost){
  size++,A[size].key=INF,A[size].cost=INF;
  increase(size,key,cost);
  }

void minHeapify(int i){
  int l,r,min;
  Heap tmp;
 l=i*2;
  r=i*2+1;
  if(l<=size && A[l].cost<A[i].cost)min=l;
  else min=i;
  if(r<=size && A[r].cost<A[min].cost)min=r;
  if(min!=i){tmp=A[i],A[i]=A[min],A[min]=tmp; minHeapify(min);}
}


Heap extractMin(){
  Heap min;
  min=A[1],A[1]=A[size],size--,minHeapify(1);
  return min;
}

void dijkstra(int s){
  Heap u;
  int used[N];
  for(int i=0;i<n;i++) used[i]=0,d[i]=INF;
  d[s]=0;
  while(size>=1){
    u=extractMin();
    used[u.key]=2;
    if(d[u.key] <u.cost)continue;
    node *v=nil[u.key]->next;
    while(v!=nil[u.key]){
      if(used[v->key]!=2)
	if(d[u.key]+v->cost<d[v->key])
	  d[v->key]=d[u.key]+v->cost,used[v->key]=1,insert(v->key,d[v->key]);
      v=v->next;
    }
  }
}

int main(){
  cin>>n;
  init();
  int u,k,v,c;
  size=n;
  for(int i=0;i<n;i++){
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin>>v>>c;
      insert(u,v,c);
    }
  }
   dijkstra(0);
  for(int i=0;i<n;i++)cout<<i<<" "<<d[i]<<endl;
  
  return 0;
}

Measured memory_bytes: 16888
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound

int main(){
  int H,W;
  cin>>H>>W;
  VS S(H);
  rep(i,H) cin>>S[i];
  VVI X(H,VI(W));
  rep(i,W-1) X[0][i+1]=10000;
  rep(i,H){
    rep(j,W){
      if(i) if(S[i][j]!=S[i-1][j]){
        X[i][j]=X[i-1][j]+1;
      }else X[i][j]=X[i-1][j];
      if(j) if(S[i][j]!=S[i][j-1]){
        X[i][j]=min(X[i][j],X[i][j-1]+1);
      }else X[i][j]=min(X[i][j],X[i][j-1]);
    }
  }
  int ans=(X[H-1][W-1]+1)/2;
  if(S[0][0]=='#'&&S[H-1][W-1]=='#') ans++;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
SS = input()
T = input()

L_S = len(SS)
L_T = len(T)

COND = 0
ANS = []
for i in range(L_S-L_T+1):
	cond = 1
	t = ('?' * i) + T + ('?' * (L_S-L_T-i))

	ans = ''
	for j in range(L_S):
		if SS[j] == '?' and t[j] == '?':
			ans += 'a'
			
		elif SS[j] == '?' and t[j] != '?':
			ans += t[j]
		elif SS[j] != '?' and t[j] == '?':
			ans += SS[j]
		else:
			if SS[j] != t[j]:
				cond = 0
				ans = ''
				break
			else:
				ans += t[j]

	if cond == 0:
		continue
	else:
		ANS.append(ans)

if len(ANS) == 0:
	print('UNRESTORABLE')
else:
	ANS.sort()
	print(ANS[0])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,cnt=0;
  cin>>n;
  for(int i=1;i<=n;++i)
    if((i>=1&&i<10)||(i>=100&&i<1000)||(i>=10000&&i<100000)) ++cnt;
  cout<<cnt<<endl;
  return 0;
 } 

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;


public class Main {
	public static void main(String[] args) throws IOException{

		Scanner sc = new Scanner(new InputStreamReader(System.in));
		int n = sc.nextInt();
		int k = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();

		if(n>k){
			 System.out.println((k*x)+((n-k)*y));
		}else {
			 System.out.println(n*x);
		}
		
	}
}


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

int main(){
  int x, a;
  cin >> x >> a;
  if(x<a){
    cout << 0 << endl;
  }
  else{
    cout << 10 << endl;
  }

  return 0;
}

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

int main() {
  int N, M, sum=0;
  cin >> N;
  vector<int> t(N), p(M), x(M);
  
  for(int i=0; i<N; i++) {
    cin >> t.at(i);
    sum += t.at(i);
    }
  
  cin >> M;
  
  for(int i=0; i<M; i++) {
    cin >> p.at(i) >> x.at(i);
    int ans = sum-t.at(p.at(i)-1)+x.at(i);
    cout << ans << endl;
    }
  }

Measured memory_bytes: 512
main :: IO ()
main = do
  (n : k : _) <- map read . words <$> getLine :: IO [Int]
  print . fromRational $ solve n k

solve :: Int -> Int -> Rational
solve n k = sum (map f [1..n]) / toRational n
  where
    f :: Int -> Rational
    f i = (1 :: Rational) / toRational (g i)
    g :: Int -> Int
    g i = until (\l -> k <= i * l) (2 *) 1


Measured memory_bytes: 1020