akhauriyash/Code-Regression huggingface dataset:
#define ll long long
#define ull unsigned long long
#define lld long double
#define cn(n)  ll n;cin >> n;
#define tes(t) ll t;cin>>t;while(t--) 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define al(v) v.begin(), v.end()
#define oset(X) tree<X, null_type, less<X>, rb_tree_tag, tree_order_statistics_node_update>
#define roset(X) tree<X, null_type, greater<X>, rb_tree_tag, tree_order_statistics_node_update>
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll INF = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 7;
const ll MOD2 = 998244353;
const long double PI = 3.141592653589793;
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
ll power(ll x, ll y, ll p){ll res = 1;x %= p;while (y > 0){if (y & 1)res = (res * x) % p;y = y >> 1;x = (x * x) % p;}return res;}
ull po(ull base, ull powerRaised){if (powerRaised != 0)return (base * po(base, powerRaised - 1));else return 1;}
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
ll lcm(ll a, ll b){return (a * b) / gcd(a, b);}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
// #ifndef ONLINE_JUDGE
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
// #endif //*
//   tes(t)
//   {
    
//   }
string s;
cin>>s;
int n=s.length();
if(s[n-1]=='s')
s+="es";
else s+="s";

cout<<s;

}
	

  


Measured memory_bytes: 3664
L = gets.to_i
n = (0 .. 20).find{|x| 1<<(x + 1) > L} + 1
ans = []
(1 ... n).each{|i| ans << "#{i} #{i + 1} 0"}
(1 ... n).each{|i| ans << "#{i} #{i + 1} #{1<<(i - 1)}"}
d = (1<<(n - 1))
while L - d > 0
  i = (0 .. n).find{|x| 1<<(x + 1) > L - d}
  ans << "#{i + 1} #{n} #{d}"
  d += (1<<i)
end
puts "#{n} #{ans.length}"
ans.each{|l| puts l}

Measured memory_bytes: 1788
#include <iostream>
#include <stdio.h>
using namespace std;

static const int MAX_COUNT = 200000;

int main()
{
	int n;
	int R[MAX_COUNT];
	
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> R[i];
	}

	int max = R[1] - R[0];
	int min = R[0];

	for (int i = 1; i < n; i++)
	{
		if (max < R[i] - min)
			max = R[i] - min;

		if (min > R[i])
			min = R[i];
	}

	cout << max << endl;


	return 0;
}

Measured memory_bytes: 3868
n = int(input())
a = [0]*60001
for i in range(1,100):
  for j in range(1,100):
    for k in range(1,100):
      a[i**2+j**2+k**2+i*j+j*k+k*i]+=1
for i in a[1:n+1]:
  print(i)

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

int main() {
  int n, input;
  int i, j;
  for (i = 0; i < 5; i++) {
    cin >> n;
    if (n == 0) {
      return 0;
    }
    for (j = 0; j < 9; j++) {
      cin >> input;
      n -= input;
    }
    cout << n << endl;
  }
  return 0;
}



Measured memory_bytes: 3096
n = int(input())
sps = {}
for i in range(n):
  s, p = input().split()
  p = int(p)
  if s not in sps:
    sps[s] = []
  sps[s].append((p, i+1))

for city in sorted(sps.keys()):
  for p, i in sorted(sps[city], key=lambda x: -x[0]):
    print(i)


Measured memory_bytes: 3060
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(ll i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
#define p(s) std::cout << s ;
#define pl(s)  std::cout << s << endl;
using namespace std;

class UnionFind {
public:
    vector<ll> par;
    void init(ll n) {
        rep(i, 0, n) {
            //par[i] == iのとき、iの親はiとなるから初期化では全て根であるとする。
            par.push_back(i);
        }
    }
    void clear() {
        rep(i, 0, par.size()) {
            par[i] = i;
        }
    }

    ll root(ll x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = root(par[x]);
        }
    }

    // これは併合するために使う
    bool unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        // 併合済ならばfalse
        if (x == y) return false;

        par[y] = x;
        return true;
    }

    bool isSame(ll x, ll y) {
        return root(x) == root(y);
    }
};

int main() {
    ll N, M;;
    cin >> N >> M;
    vector<pair<ll, ll> > e(M);
    ll u, v;
    rep(i, 0, M) {
        cin >> u >> v;
        --u; --v;
        e[i] = make_pair(u, v);
    }

    UnionFind T;
    T.init(N);
    int ans = 0;
    rep(i, 0, M) {
        T.clear();
        bool flag = true;
        rep(j, 0, M) {
            if (i == j) continue;
            T.unite(e[j].first, e[j].second);
        }

        rep(j, 0, N) {
            if (!T.isSame(0, j)) {
                flag = false;
            }
        } 
        if (!flag) ++ ans;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())

g = [[False for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = map(lambda x:int(x)-1, input().split())
    g[a][b] = g[b][a] = True

def print_set(s):
    for e in s:
        print(e + 1, end=" ")
    print()

checker = N*(N - 1)//2
cnt = 0
def dfs(visited: set, stack: list):
    global cnt
    if sum(list(visited)) == checker:
        cnt += 1
    elif len(stack) > 0:
        v = stack.pop()
        for i in range(N):
            if g[v][i] and not (i in visited):
                dfs(visited | set([i]), stack + [i])

dfs(set([0]), [0])
print(cnt)

Measured memory_bytes: 3064
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int k = sc.nextInt();
		int d = gcd(a, b);
		int x = d;
		for (; ; d--) {
			if (x % d == 0) {
				k--;
				if (k == 0) {
					break;
				}
			}
		}
		System.out.println(d);
	}
	
	static int gcd(int x, int y) {
		if (x % y == 0) {
			return y;
		}
		return gcd(y, x % y);
	}
}


Measured memory_bytes: 23380
n,k = gets.strip.split.map(&:to_f)
m = n
array = []

coin = 0

while n > 0 do
  x = k / n
  while x > 2 ** coin do
    coin += 1
  end
  array << coin
  n -= 1
end

ans = 0.0.to_f
array.each do |ele|
  ans += (1.to_f / ((2 ** ele) * m).to_f)
end
p ans

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

/*
struct Edge
{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
*/

using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S, T;
    cin >> S >> T;
    int ans = INT_INF;
    for (int i = 0; i + T.size() - 1 < S.size(); i++)
    {
        string t = S.substr(i, T.size());
        // cerr << t << endl;
        int tmp = 0;
        for (int j = 0; j < t.size(); j++)
        {
            if (t[j] != T[j])
                tmp++;
        }
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>
int n, l, s;
int main(void){
	scanf("%d%d", &n, &l);
	s = n*l + (n*(n-1)>>1);
	if(l>=0){
		printf("%d\n", s-l);
	}else if(n+l<=0){
		printf("%d\n", s-n-l+1);
	}else{
		printf("%d\n", s);
	}
}


Measured memory_bytes: 128
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
 
#include <stdio.h>
#include <bits/stdc++.h>
 
using namespace std;
 
#include <x86intrin.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  
#define pb push_back
#define mp make_pair
#define in insert
#define f first
#define s second
#define ll long long
#define dd double
  
const int mod = 1e9 + 7;
const int N = 2e5 + 7;
const int inf = 2e9;
const ll INF = 1e18;
 
ll a[200], dp[200][202020];
ll sum[200][202020];
 
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen("*.in", "r", stdin);freopen("*.out", "w", stdout);
	ll n, k;
	cin >> n >> k;
	for (ll i = 1; i <= n; i++) cin >> a[i];
 
	for (ll i = 0; i <= a[1]; i++) dp[1][i] = 1;
 
	for (ll i = 2; i <= n; i++) {
		for (ll j = 0; j <= k; j++) {
			if (j == 0) 
				sum[i - 1][j] = dp[i - 1][j] % mod;
			else 
				sum[i - 1][j] = (sum[i - 1][j - 1] + dp[i - 1][j]) % mod;
		}
		for (ll j = 0; j <= k; j++) {
			if (j - a[i]) 
				dp[i][j] = (sum[i - 1][j] - sum[i - 1][j - a[i] - 1] + mod) % mod;
			else 
				dp[i][j] = sum[i - 1][j] % mod;
		}
	}
 
	cout << dp[n][k];
}

Measured memory_bytes: 316160
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long K = sc.nextLong();
		sc.close();
		if(A > K){
			A -= K;
		}else{
			K -= A;
			A = 0;
			B = B - K > 0 ? B - K : 0;
		}
		System.out.println(A + " " + B);
	}
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
bool ip[1000001];
int main(){
	memset(ip,1,sizeof ip);
	ip[0]=0,ip[1]=0;
	for(ll i=2;i<=sqrt(1000001);i++){
		if(ip[i]){
			for(ll j=i*i;j<1000001;j+=i){
				ip[j]=0;
			}
		}
	}
	ll x; cin>>x;
	for(ll i=x;i<1000001;i++){
		if(ip[i]){
			cout<<i;
			return 0;
		}
	}
}


Measured memory_bytes: 4600
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());

        // 主処理
        String result = (a % 2 != 0 && b % 2 != 0) ? "Yes" : "No";

        // 出力
        System.out.println(result);
        sc.close();
    }
}

Measured memory_bytes: 21204
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=200010,Mod=1e9+7;
int n,a[N],pre[N],lst[N],f[N];
int main(){
	n=gi();
	REP(i,1,n){
		a[i]=gi();
		pre[i]=lst[a[i]];lst[a[i]]=i;
	}
	f[0]=1;
	for(int i=1;i<=n;i++){
		f[i]=f[i-1];
		if(pre[i] && pre[i]!=i-1)f[i]=(f[i]+f[pre[i]])%Mod;
	}
	printf("%d\n",f[n]);
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define Nmax 500005
const long double PI = acos(-1);
string s;

int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    int a = 0, b = 0;
    for (auto it : s){
        if (it == 'C') a = 1;
        if (it == 'F' && a) b = 1;
    }
    if (b) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    #include <string>
     
    using namespace std;
     
    typedef long long int ll;
    typedef vector<ll> V;
    typedef vector<V> VV;
     
    int main() {
      // Happy hacking!
      char b;
      cin >> b;
     
      switch(b) {
      case 'A':
        cout << "T" << endl;
        break;
      case 'T':
        cout << "A" << endl;
        break;
      case 'C':
        cout << "G" << endl;
        break;
      case 'G':
        cout << "C" << endl;
        break;
      }
     
      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(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
#define ll long long int
const double mx = 2e6 + 5 ;
bool check(int num)
{
	vector<int> digits;
	while(num)
	{
		digits.push_back(num%10);
		num/=10;
	}
	int len = digits.size();
	for(int i=0; i<len; i++)
	{
		if(digits[i]!=digits[len-i-1])
			return false;
	}
	return true;
}
void solve()
{
	int a, b;
	cin>>a>>b;
	int cnt = 0;
	for(int i=a; i<=b; i++)
	{
		if(check(i))
			cnt++;
	}
	cout<<cnt<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3656
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int P = ((N + 1) / 2);
		double dN = N;
		double dP = P;

		double ans = dP / dN;

		System.out.println(String.format("%.10f",ans));
	}
}

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


// Useful container manipulation / traversal macros
#define fori(i,a,b)    for(int i=a;i<=b;i++)
#define ford(i,a,b)   for(int i=a;i>=b;i--)
#define all(a)        a.begin(), a.end()
#define in(a,b)       ( (b).find(a) != (b).end())
#define tr(c,i)       for(auto i = (c).begin(); i != (c).end(); i++)
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define pb             push_back
#define fill(a,v)      memset(a, v, sizeof a)

typedef long long int lli;
typedef vector<int> vi;
typedef vector<long long int> vlli;

int counter[100001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }

    int l, q;
    cin>>l>>q;

    string s;
    cin>>s;

    ford(i, l, 1) s[i] = s[i-1];

    fori(i, 2, l){
        if(s[i] == 'C' && s[i-1] == 'A'){
            counter[i] = counter[i-1] + 1;
        } else {
            counter[i] = counter[i-1];
        }
    }

    while(q--){
        int c = 0;
        int l, r;
        cin>>l>>r;
        cout<<counter[r] - counter[l]<<'\n';
    }
}

Measured memory_bytes: 1488
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
long int n;
long int a[200005];
long int k;
inline int log_number(int log, int mid)
{
	if (log % mid == 0)
		return log / mid;
	else
		return log / mid+1;
}
bool check(int len)
{
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans += log_number(a[i], len)-1;
	}
	if (ans <= k)
		return true;
	else
		return false;
}
int main() 
{
	cin >> n >> k;
	for (int i = 1; i <=n; i++) 
	{
		cin >> a[i];
	}
	int l = 1, r = 1e9;
	while (r - l > 1) 
	{
		int mid = (l + r) / 2;
		if (check(mid)) 
			r = mid;
		else l = mid;
	}
	cout << (check(l) ? l : r) << endl;
}





Measured memory_bytes: 5160
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(ReadLine());
            var words = new List<string>();
            for (int i = 0; i < n; i++)
            {
                var x = ReadLine();
                words.Add(x);
            }

            bool flag = true;
            var hashSet = new HashSet<string>();
            foreach (var item in words)
            {
                if (hashSet.Add(item) == false)
                {
                    flag = false;
                    break;
                }
            }

            for (int i = 0; i < n - 1; i++)
            {
                int last = words[i].Length - 1;
                if (words[i][last] != words[i + 1][0])
                {
                    flag = false;
                    break;
                }
            }
            WriteLine(flag ? "Yes" : "No");
        }
    }
}



Measured memory_bytes: 13280
R=range
l=[[[0 for i in R(10)]for j in R(3)]for s in R(4)]
for i in R(int(input())):b,f,r,v=map(int,input().split());l[b-1][f-1][r-1]+=v
for i in R(4):
 for k in l[i]:print("",*k)
 if i!=3:print("#"*20)

Measured memory_bytes: 7800
import bisect
N = int(input())
A = list(map(int,input().split()))

lis = []
hist = []

for a in A:
    i = bisect.bisect_left(lis,a)
    if i == len(lis):
        lis.append(a)
        hist.append([a])
    else:
        lis[i] = a
        hist[i].append(a)

ans = last = hist[-1][0]
for row in reversed(hist[:-1]):
    i = bisect.bisect_left(row[::-1], last)
    last = row[-i]
    ans += last
print(ans)


Measured memory_bytes: 20348
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
//#define MOD 1000000007
#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int main(){
    int N,K; cin >> N >> K;
    vector<int> a(N);
    rep(i,N) cin >> a[i];
    vector<ll> suml(N+1),sumr(N+1),sum(N+1);
    rep(i,N){
        if(a[i] > 0) suml[i+1] = suml[i]+a[i];
        else suml[i+1] = suml[i];
        sum[i+1] = sum[i]+a[i];
    }
    for(int i = N; i >= 1; i--){
        if(a[i-1] > 0) sumr[i-1] = sumr[i]+a[i-1];
        else sumr[i-1] = sumr[i];
    }
    ll ans = -LINF;
    rep(i,N-K+1){
        ll now = suml[i]+sumr[i+K];
        now += max(sum[i+K]-sum[i],0LL);
        ans = max(ans,now);
    }
    cout << ans << endl;
}



Measured memory_bytes: 2944
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		int[] dp = new int[1000000];
		Arrays.fill(dp,Integer.MAX_VALUE/2);
		dp[0] = 0;

		int[] odd = new int[1000000];
		Arrays.fill(odd,Integer.MAX_VALUE/2);
		odd[0] = 0;


		for (int i=1; i<1000000; i++) {
			for (int j=1; j<=i; j++) {
				int v = j*(j+1)*(j+2)/6;
				if (i < v) break;
				dp[i] = Math.min(dp[i], dp[i-v] + 1);

				if (v%2 == 0) continue;
				if (i < v) break;
				odd[i] = Math.min(odd[i], odd[i-v] + 1);
			}
		}

		while (true) {
			int q = in.nextInt();
			if (q == 0) break;
			out.println(dp[q]+" "+odd[q]);
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 34724
# -*- coding:utf-8 -*-

def solve():
    # 式変形する
    a, b, c = list(map(int, input().split()))

    if c-a-b >= 0 and 4*a*b < (c-a-b)**2:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    solve()


Measured memory_bytes: 2940
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

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

string f( int d ){
	int q , x = 1 ;
	for( q=0 ; d/x ; q++ ) x*=10 ;
	x /= 10 ;
	string b ;
	for( int k=0 ; k<q ; k++ ){
		b += d/x + '0' ;
		d -= d/x * x ;
		x /= 10 ;
	}
	return b ;
}

main(){
	int m,n ;
	while( cin >> n >> m , n ){
		int table[10010] = {} , pre[10010] = {} , nxt[10010] = {} ;
		for( int i=1 ; i<=n ; i++ ){
			table[i] = i ;
			pre[i] = i-1 ;
			nxt[i] = i+1 ;
		}
		pre[1] = n ;
		nxt[n] = 1 ;
		
		int cnt = n-1 , pos = 1 ;
		string s ;
		for( int i=1 ; i<=m ; i++ ){
			cin >> s ;
			if( !cnt ) continue ;
			
			string num = f(i) ;
			if( !(i%15) ) num = "FizzBuzz" ;
			else if( !(i%5) ) num = "Buzz" ;
			else if( !(i%3) ) num = "Fizz" ;
			
			if( s != num ){
				nxt[pre[pos]] = nxt[pos] ;
				pre[nxt[pos]] = pre[pos] ;
				table[pos] = 0 ;
				cnt-- ;
			}
			pos = nxt[pos] ;
		}
		
		bool t = false ;
		for( int i=1 ; i<=n ; i++ ){
			if( table[i] ){
				if( t ) cout << ' ' ;
				cout << i ;
				t = true ;
			}
		}
		cout << endl ;
		
	}
}

Measured memory_bytes: 1336
N, M = map(int, input().split())
arr = []
for i in range(M):
  p, y = map(int, input().split())
  arr.append((p, y, i))

arr.sort()
ans = {}
prev = None
tmp = None
for p, y, i in arr:
  if prev == None or p != prev:
    tmp = 1
  ans[i] = '%06d%06d' % (p, tmp)
  tmp += 1
  prev = p

for i in range(M):
  print(ans[i])

Measured memory_bytes: 35352
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

H, W = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1
g = gridMan(S)
g.makeWall()
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == 0:
      ans = max(ans, g.dist([i, j])[1])

print(ans)

Measured memory_bytes: 4060
#include<iostream>
#include<string>
using namespace std;
int main()
{
  int i;
  string s;
  cin >> s;
  s.push_back('A');
  for(i=0;i<s.size()-2;i++)
    if(s.substr(i,1)==s.substr(i+1,1)){
      cout << (i+1) << " " << (i+2) << endl;
      return 0;
    } else if(s.substr(i,1)==s.substr(i+2,1)){
      cout << (i+1) << " " << (i+3) << endl;
      return 0;
    }
  cout << "-1 -1" << endl;
  return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200005;
int t[maxn];
int main(){
  int n,T;scanf("%d%d",&n,&T);
  for(int i=1;i<=n;++i)scanf("%d",&t[i]);
  int ans=0;
  for(int i=1;i<n;++i)ans+=min(t[i+1]-t[i],T);
  printf("%d\n",ans+T);
  return 0;
}


Measured memory_bytes: 896
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;


ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


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





int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin>>n;

    ll ans = 0;
    while(ans*(ans+1)/2 < n)
        ans++;

    cout<<ans;
    return 0;
}








Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int N, a, count=0;
  cin >> N;
  for (int i=1; i <= N; i++) {
    cin >> a;
    if (i%2 ==1 && a % 2==1)count++;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 3556
// Give me My Shotgun

#include <bits/stdc++.h>
using namespace std ;

#define all(x) x.begin() , x.end()

#define PB push_back
#define F first
#define S second
#define _sz(x) (int)x.size()

#define debug(x) cerr << #x << " = " << x << endl

typedef long long ll ;
typedef pair<int , int> pii ;

//const int MAX_N = -1 ;
const int inf = 2e9 + 19 ;

string s , t ;

int main() {
        ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;
        cin >> s >> t ;
        cout << t << s ;
        return (0) ;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main{
 
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		
		Scanner sc=new Scanner(System.in);
 
		//FizzBuzz列の項目数
		int N=sc.nextInt();
		long count=0;
		int constraints=(int)Math.pow(10, 6);
		
		if(N<=constraints) {
		for(int i=1;i<=N;i++) {
			if(!(i%3==0&&i%5==0)) {
				if(!(i%3==0||i%5==0)) {
					count+=i;
				}
			}
		}
		System.out.println(count);
	}
  }
}

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

int i1,i2;char ch;
inline int read()
{
	i1=i2=ch=0;
	while(!isdigit(ch))	i1|=ch=='-',ch=getchar();
	while(isdigit(ch))	i2=(i2<<1)+(i2<<3)+(ch^48),ch=getchar();
	return i1? -i2:i2;
}

int n,m;
#define mp make_pair
#define pii pair<int,int>
struct node
{
	int rankk,id,bel,y;
}e[100010];

bool cmp1(node a,node b) {return a.bel<b.bel||(a.bel==b.bel&&a.y<b.y);}
bool cmp2(node a,node b) {return a.id<b.id;}

int dig(int x)
{
	int tot=0;
	while(x)
	tot++,x/=10;
	return tot;
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		e[i].bel=read(),e[i].y=read();
		e[i].id=i;
	}
	
	sort(e+1,e+1+m,cmp1);
	int tot=0;
	for(int i=1;i<=m;i++)
	{
		if(e[i].bel^e[i-1].bel) tot=0;
		e[i].rankk=++tot;
	}
	
	sort(e+1,e+1+m,cmp2);
	
	int tmp1,tmp2;
	for(int i=1;i<=m;i++)
	{
		tmp1=6-dig(e[i].bel),tmp2=6-dig(e[i].rankk);
		for(int j=1;j<=tmp1;j++) putchar('0');
		printf("%d",e[i].bel);
		for(int j=1;j<=tmp2;j++) putchar('0');
		printf("%d\n",e[i].rankk);
	}
	
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
#define N 1000000007
using namespace std;

string s;
//累積和、累乗
long long sum[4][100005] = {0}, ans = 0, maxn[4] = {0};

int main() {
  long long i, j, cnt = 0;

  cin >> s;
  //累積和を計算
  for(i = 1; i <= s.size(); ++i) {
    for(j = 0; j < 3; ++j) {
      sum[j][i] = sum[j][i - 1];
      if(s[i - 1] == 'A' + j) ++sum[j][i];
      sum[j][i] %= N;
    }
    sum[3][i] = sum[3][i - 1];
    if(s[i - 1] == '?') ++sum[3][i];
    sum[3][i] %= N;
  }
  //累乗の計算
  for(i = 0; i < 4; ++i) maxn[i] = 1;
  for(i = 0; i < s.size(); ++i) {
    if(s[i] == '?' && cnt < 4) ++cnt;
    for(j = 0; j < cnt; ++j) {
      if(s[i] == '?') maxn[j] *= 3;
      maxn[j] %= N;
    }
  }

  //答えの計算、BをきめうちしてACおよび？のパターンを計算
  for(i = 1; i <= s.size(); ++i) {
    //cout << ans << endl;
    ans %= N;
    if(s[i - 1] == 'B') {
      long long next = maxn[0];
      next %= N;
      // AC
      next *= sum[0][i - 1];
      next %= N;
      next *= sum[2][s.size()] - sum[2][i];
      next %= N;
      ans += next;
      // cout << next << endl;
      ans %= N;

      //?C
      next = maxn[1];
      next %= N;
      next *= sum[3][i - 1];
      next %= N;
      next *= sum[2][s.size()] - sum[2][i];
      next %= N;
      ans += next;
      ans %= N;
      // cout << next << endl;

      // A?
      next = maxn[1];
      next %= N;
      next *= sum[0][i - 1];
      next %= N;
      next *= sum[3][s.size()] - sum[3][i];
      next %= N;
      ans += next;
      ans %= N;
      // cout << next << endl;
      //??
      next = maxn[2];
      next %= N;
      next *= sum[3][i - 1];
      next %= N;
      next *= sum[3][s.size()] - sum[3][i];
      next %= N;
      ans += next;
      ans %= N;
      // cout << next << endl;
    }
    else if(s[i - 1] == '?') {
      long long next = maxn[1];
      next %= N;
      // AC
      next *= sum[0][i - 1];
      next %= N;
      next *= sum[2][s.size()] - sum[2][i];
      next %= N;
      ans += next;
      ans %= N;

      //?C
      next = maxn[2];
      next %= N;
      next %= N;
      next *= sum[3][i - 1];
      next %= N;
      next *= sum[2][s.size()] - sum[2][i];
      next %= N;
      ans += next;
      ans %= N;

      // A?
      next = maxn[2];
      next %= N;
      next *= sum[0][i - 1];
      next %= N;
      next *= sum[3][s.size()] - sum[3][i];
      next %= N;
      ans += next;
      ans %= N;
      //??
      next = maxn[3];
      next %= N;
      next *= sum[3][i - 1];
      next %= N;
      next *= sum[3][s.size()] - sum[3][i];
      next %= N;
      ans += next;
      ans %= N;
    }
  }
  /*for(i = 0; i < 4; ++i) {
    for(j = 1; j <= s.size(); ++j) cout << sum[i][j] << " ";
    cout << endl;
  }*/
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3584
// Problem : D - Insertion
// Contest : AtCoder - AtCoder Beginner Contest 064
// URL : https://atcoder.jp/contests/abc064/tasks/abc064_d
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
int n;cin>>n;string s;cin>>s;
string ans=s;
int cnt=0;
for(int i=0;i<size(s);i++)
{
	if(s[i]==')')
	{
		if(cnt==0)
		ans="("+ans;
		else
		{
			cnt--;
		}
	}
	else
	cnt++;
}
while(cnt--)
ans+=")";
cout<<ans;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


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

#define int long long
#define endl  '\n'

// Tushar Goyal : Chalie Shuru karte hai

// const int N = 1e7 + 2;

#define db(...) 		__f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}

void solve()
{
	int N; cin >> N;
	int arr[N + 2];;
	memset(arr, 0, sizeof arr);

	for (int i = 1; i <= N + 2 ; i++)
	{
		for (int j = i ; j <= N + 2; j += i)
		{
			arr[j]++;
		}
	}

	int ans = 0;
	for (int i = 1 ; i <= N ; i++)
	{
		// db(i, arr[i]);
		ans += i * arr[i];
	}

	cout << ans << endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

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

int main() {
     
     long long i,j,l,r,q,t,m,n,d,p,h,x;
     long long k,z,y,p1,h1;
     string st="",s1="",s2="";
     q=1;
     for(l=0;l<q;l++)
     {
          std::cin >> st >> s1;
          n=st.length();
          m=s1.length();
          t=4000000;
          for(i=0;i<=n-m;i++)
          {
               p=0;
               for(j=i,k=0;k<m;j++,k++)
               {
                    if(st[j]!=s1[k])
                         p++;
               }
               t=min(t,p);
          }
          std::cout << t << std::endl;
     }
     return 0;
}


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

int main(){
	
	int n;
	
	cin >> n;
	
	int a[n];
	
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	double sum = 0;
	
	for (int i = 0; i < n; i++){
		sum += a[i];
	}
	
	//cout << sum << endl;
	double p;
	p = round(sum / n);
	
	//cout << p;
	int ans = 0;
	
	for (int i = 0; i < n; i++){
		ans += (a[i]-p)*(a[i]-p);
	}
	
	cout << ans;
	
}


Measured memory_bytes: 256
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    double a, b, cc;
    double s, l, h;

    a = sc.nextDouble();
    b = sc.nextDouble();
    cc = sc.nextDouble();
    cc = Math.toRadians(cc);

    s = a * b * Math.sin(cc) / 2.0;
    l = a + b + Math.sqrt(a * a + b * b - 2.0 * a * b * Math.cos(cc));
    h = b * Math.sin(cc);

    System.out.println(s);
    System.out.println(l);
    System.out.println(h);

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 18196
#include<iostream>
using namespace std;
int n, m, d;
char x[1000][1000];
int main() {
	cin >> n >> m >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)cin >> x[i][j];
	}
	int cnt = 0;
	if (n >= d) {
		for (int i = 0; i <= n - d; i++) {
			for (int j = 0; j < m; j++) {
				bool flag = true;
				for (int k = 0; k < d; k++) {
					if (x[i + k][j] == '#')flag = false;
				}
				if (flag == true)cnt++;
			}
		}
	}
	if (m >= d) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= m - d; j++) {
				bool flag = true;
				for (int k = 0; k < d; k++) {
					if (x[i][j + k] == '#')flag = false;
				}
				if (flag == true)cnt++;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll n,x;cin>>n>>x;
    vl a(n);
    rep(i,n)cin>>a[i];
    ll res = 0;
    rep(i,n-1){
        ll sum = a[i] + a[i+1];
        if(sum > x){
            res += sum-x;
            a[i+1]-=sum-x;
            a[i+1] = max(0LL,a[i+1]);
        }
    }
    out(res);
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<algorithm>
using namespace std;
long long int dp[100][100];
long long int f[100];
long long int e[100];
long long int solve(long long int a,long long int b){
	long long int ret=(1LL<<31)-1;
	if(a==b)return 0;
	if(dp[a][b])return dp[a][b];
	for(long long int i=a;i<b;i++)ret=min(ret,solve(a,i)+solve(i+1,b)+f[a]*e[i]*f[i+1]*e[b]);
	return dp[a][b]=ret;
}
int main(){
	long long int n;
	scanf("%lld",&n);
	for(long long int i=0;i<n;i++)scanf("%lld%lld",f+i,e+i);
	printf("%lld\n",solve(0,n-1));
}

Measured memory_bytes: 0
#include <stdio.h>

int main()
{
        int a[4], b[4];
        int hit, blow;
        while(scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]),
                scanf("%d%d%d%d", &b[0], &b[1], &b[2], &b[3]) != EOF) {
                int i;
                hit = blow = 0;
                for(i = 0; i < 4; i++) {
                        if(a[i] == b[i])
                                hit++;
                        else if(a[i] == b[0] ||
                                        a[i] == b[1] ||
                                        a[i] == b[2] ||
                                        a[i] == b[3])
                                blow++;
                }
                printf("%d %d\n", hit, blow);
        }
        return 0;
}

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

const int64_t MOD = 1'000'000'007;

int64_t mpow(int64_t x, int64_t y){
    if(y==0) return 1;
    if(y==1) return x%MOD;
    if(y%2==0) return mpow(x*x%MOD, y/2)%MOD;
    return mpow(x*x%MOD, y/2)%MOD*x%MOD;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);
    
    int n, x, y, z;
    cin >> n >> x >> y >> z;
    int ptn = (1<<(x+y+z-1)) | (1<<(y+z-1)) | (1<<(z-1)), mask = (1<<(x+y+z))-1;

    static int64_t dp[41][1<<17];
    dp[0][0] = 1;

    for(int i=0;i<n;i++){
        for(int j=0;j<=mask;j++){
            if(dp[i][j] == 0) continue;
            for(int k=1;k<=10;k++){
                int idx = (j<<k) & mask | (1<<(k-1));
                idx &= mask;
                if((idx&ptn) == ptn) continue;
                dp[i+1][idx] += dp[i][j];
                dp[i+1][idx] %= MOD;
            }
        }
    }

    int64_t ans = 0;
    for(int j=0;j<=mask;j++){
        ans += dp[n][j];
        ans %= MOD;
    }

    cout << (mpow(10, n) + MOD - ans) % MOD << endl;
    
    return 0;
}

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

template<class T> inline bool chmin(T &a, T b) {
    if (b < a) {
        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;

const int MAX_N = 110;
const int MAX_V = 100100;

int N;
long long W, weight[MAX_N], value[MAX_N];

long long dp[MAX_N][MAX_V];

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        cin >> weight[i] >> value[i];

        for (int i = 0; i < MAX_N; i++) {
            for (int j = 0; j < MAX_V; j++) {
                dp[i][j] = INF;
            }
        }
    }

    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        for (int sum_v = 0; sum_v < MAX_V; sum_v++) {
            if (0 <= sum_v - value[i]) {
                chmin(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);
            }
            chmin(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }

    long long res = 0;
    for (int sum_v = 0; sum_v < MAX_V; sum_v++) {
        if (dp[N][sum_v] <= W) {
            res = sum_v;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 86400
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def get_yakusu(n):
    ans = set()
    for i in range(1, int(math.sqrt(n)) + 2):
        if n % i == 0:
            if i != 1:
                ans.add(i)
            if n // i != i:
                ans.add(n // i)
    return ans

def main():
    N = I()
    cnt = 0
    yakusu = get_yakusu(N)
    n1yakusu = get_yakusu(N-1)
    for n in yakusu:
        cpN = N
        while True:
            if n == 1:
                break
            if cpN % n == 0:
                cpN = cpN // n
            else:
                break
        if cpN % n == 1:
            cnt += 1
    cnt += len(n1yakusu)
    print(cnt)
main()



Measured memory_bytes: 65644
#include <iostream>
using namespace std;
int main() {
  int E, Y;
  cin >> E >> Y;
  if (E == 0) {
    if (1868 <= Y && Y <= 1911) {
      cout << "M" << Y - 1868 + 1 << endl;
    } else if (1912 <= Y && Y <= 1925) {
      cout << "T" << Y - 1912 + 1 << endl;
    } else if (1926 <= Y && Y <= 1988) {
      cout << "S" << Y - 1926 + 1 << endl;
    } else if (1989 <= Y && Y <= 2016) {
      cout << "H" << Y - 1989 + 1 << endl;
    }
    return 0;
  } else {
    if (E == 1) {
      cout << 1868 + Y - 1 << endl;
    } else if (E == 2) {
      cout << 1912 + Y - 1<< endl;
    } else if (E == 3) {
      cout << 1926 + Y - 1 << endl;
    } else if (E == 4) {
      cout << 1989 + Y - 1 << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3112
import numpy as np
import sys
h,w = map(int, input().split())
s = [list(input().replace(".","0").replace("#","1")) for i in range(h)]
s = [list(map(int,s[i])) for i in range(h)]
ss = np.array(s)
s_new = np.zeros((h,w))
ans_arr = np.zeros((h,w))
def around(x,y):
  ans = 0
  if x > 0:
    ans += ss[x-1,y]
  if y > 0:
    ans += ss[x,y-1]
  if x > 0 and y > 0:
    ans += ss[x-1,y-1]
  if x<h-1:
    ans += ss[x+1,y]
  if y<w-1:
    ans += ss[x,y+1]
  if x<h-1 and y<w-1:
    ans += ss[x+1,y+1]
  if x > 0 and y<w-1:
    ans += ss[x-1,y+1]
  if x<h-1 and y>0:
    ans += ss[x+1,y-1]
  return ans

for i in range(h):
  for j in range(w):
    if ss[i,j] == 0:
      s_new[i,j] = around(i,j)
    else:
      s_new[i,j] = -1

sss = s_new.tolist()
for i in range(h):
  sss[i] = list(map(str, sss[i]))
for i in range(h):
  for j in range(w):
    if float(sss[i][j]) > -1:
      sss[i][j] = sss[i][j][:1]
    else:
      sss[i][j] = "#"
  print(''.join(sss[i]))

Measured memory_bytes: 12496
import sys

w = input()
if len(w)%2!=0:
    print("No")
    sys.exit()

ww = sorted(w)
flag = True
for i in range(0,len(ww),2):
    if ww[i]!=ww[i+1]:
        flag = False
if flag:
    print("Yes")
else:
    print("No")


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

using namespace std;
using lint = long long;

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

    lint d = c - a - b;
    if (d > 0 and d * d > 4 * a * b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
from  bisect import bisect_left, bisect_right

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

cnt = 0
for b in B:
    a_cnt = bisect_left(A, b)
    c_cnt = N - bisect_right(C, b)
    cnt += a_cnt * c_cnt
print(cnt)


Measured memory_bytes: 105444
import scala.io.StdIn.readLine

object Main extends App {
  val Array(n, q) = readLine.split(" ").map(_.toInt)
  val queue = scala.collection.mutable.Queue[(String, Int)]()
  var spentTime = 0

  (0 until n).foreach { e =>
    val Array(name, timeToComplete) = readLine.split(" ")
    queue.enqueue(name -> timeToComplete.toInt)
  }

  while (queue.nonEmpty) {
    val (name, time) = queue.head
    if (time - q <= 0) {
      queue.dequeue()
      spentTime += time
      println(s"$name $spentTime")
    } else {
      spentTime += q
      queue.enqueue((name, time - q))
      queue.dequeue()
    }
  }
}



Measured memory_bytes: 140892
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (bb)) ? (a) : (bb))
#define MIN(a,b) (((a) < (bb)) ? (a) : (bb))
#define REMOVE(v,a) v.erase(remove(v.begin(), v.end(), a), v.end())
#define REP(i,n) for (int (i) = 0; (i) < (n); (i)++)
using namespace std;

int N, K;
int aa[200001];
int bb[200001];

int bit[300000];
void add(int a, int w)
{
	for (int x = a; x <= N + 1; x += x & -x) 
		bit[x] += w;
}
int range(int a)
{
	int ret = 0;
	for (int x = a; x > 0; x -= x & -x) ret += bit[x];
	return ret;
}

struct St
{
	int b;
	int index;
	int c;

	bool operator < (const St& st) const
	{
		return b < st.b;
	}
};

St st[200001];

signed main()
{
	memset(bit, 0, sizeof(bit));

	cin >> N >> K;
	aa[0] = 0;
	REP(i, N) cin >> aa[i + 1];

	int sum = 0;
	REP(i, N + 1)
	{
		sum += aa[i];
		bb[i] = sum - i * K;
	}

	REP(i, N + 1)
	{
		st[i].b = bb[i];
		st[i].index = i;
	}

	ARY_SORT(st, N + 1);

	int prev = 0;
	int ind = 0;
	REP(i, N + 1)
	{
		if (prev < st[i].b) ind++;
		st[i].c = ind;
		prev = st[i].b;
	}

	REP(i, N + 1)
	{
		aa[st[i].index] = st[i].c;
	}

	int ans = 0;
	REP(i, N + 1)
	{
		add(aa[i] + 1, 1);
		ans += range(aa[i] + 1) - 1;
	}

	cout << ans;
}

Measured memory_bytes: 10368
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>

using namespace std;
using ll = long long;

const int INF = 1001001001;

int main()
{
	string s="", t="", u="";
	ll a(0), b(0);
	cin>>s>>t>>a>>b>>u;
	if(s==u)a--;
	else b--;
	cout<<a<<" "<<b;
}

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

int main() {
    int n; cin >> n;
    ll prv_t, prv_a; cin >> prv_t >> prv_a;
    for (int i = 0; i < n - 1; i++) {
        ll cur_t, cur_a; cin >> cur_t >> cur_a;
        ll t = (prv_t + cur_t - 1) / cur_t;
        ll a = (prv_a + cur_a - 1) / cur_a;
        ll k = max(t, a);
        prv_t = cur_t * k;
        prv_a = cur_a * k;
    }
    cout << prv_t + prv_a << endl;
    return 0;
}

Measured memory_bytes: 256