akhauriyash/Code-Regression huggingface dataset:
def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)

def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max,mod=DIV):
    fac,finv,inv = [0]*max, [0]*max, [0]*max
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod -inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    class CONV:
        def __init__(self):
            pass
        def ncr(self,n,k):
            if(n<k):
                return 0
            if(n<0 or k<0 ):
                return 0
            return fac[n]*(finv[k]*finv[n-k]%mod)%mod
    return CONV()



def main():
    n,k = isRaw()
    As = list(isRaw())
    As.sort()
    ct = CONV_TBL(n)
    ans = 0

    for i in range(n):
        ans += As[i]*ct.ncr(i, k-1) - As[i]*ct.ncr(n-(i+1), k-1)
        ans = ans%DIV
    return ans

if __name__ == "__main__":
    print(main())


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

#define STR_MAX 1000

int mat[STR_MAX+1][STR_MAX+1];

int common_subsequence(int len1, int len2, string str1, string str2){
  int i, j;

  for(i=1; i<=len1; i++){
    for(j=1; j<=len2; j++){
      if(str1[i-1] == str2[j-1]) mat[i][j]=mat[i-1][j-1]+1;
      else mat[i][j]=max(mat[i-1][j], mat[i][j-1]);
    }
  }

  return mat[len1][len2];
}

int main(void){
  int i, n;
  string str1, str2;

  scanf("%d", &n);
  for(i=0; i<n; i++){
    cin >> str1 >> str2;

    int len1=str1.size(), len2=str2.size();
    printf("%d\n", common_subsequence(len1, len2, str1, str2));
  }
  
  return 0;
}




Measured memory_bytes: 7060
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    int N;cin>>N;
    vector<ll> a(3*N);
    REP(i, 3*N) cin >> a[i];
    multiset<ll> L;
    multiset<ll,greater<ll>> R;
    ll s=0;
    vector<ll> sl(3*N+1),sr(3*N+1);
    REP(i,N){
        sl[i+1]=sl[i]+a[i];
        sr[3*N-i-1]=sr[3*N-i]+a[3*N-i-1];
        s+=a[3*N-i-1];
        L.insert(a[i]);
        R.insert(a[3*N-i-1]);
    }
    rep(i,N,2*N){
        ll tmp=*L.begin();
        if(a[i]>tmp){
            sl[i+1]=sl[i]+a[i]-tmp;
            L.erase(L.begin());
            L.insert(a[i]);
        }
        else sl[i+1]=sl[i];
        tmp=*R.begin();
        if(a[3*N-i-1]<tmp){
            sr[3*N-i-1]=sr[3*N-i]+a[3*N-i-1]-tmp;
            R.erase(R.begin());
            R.insert(a[3*N-i-1]);
        }
        else sr[3*N-i-1]=sr[3*N-i];
    }
    ll ans=-1e18;
    rep(i,N,2*N+1){
        ans = max(ans,sl[i]-sr[i]);
    }
    cout<<ans<<endl;
}


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

struct StDtl
{
  int m_nLeft;

  StDtl(int nLeft) :
    m_nLeft(nLeft)
  { }
};

struct StSum
{
  int m_nLeft;
  int m_nRight;
  int m_nArea;

  StSum(int nLeft, int nRight, int nArea) :
    m_nLeft(nLeft), m_nRight(nRight), m_nArea(nArea)
  { }
};

void fnCroSecSet(stack<StDtl>& rskoDtl, vector<StSum>& rvoSum, int& rnTotalArea)
{
  string sCrossSect;
  cin >> sCrossSect;

  for (int i = 0; i < sCrossSect.size(); i++)
  {
    if (sCrossSect[i] == '\\')
    {
      StDtl oDtl(i);
      rskoDtl.push(oDtl);
    }
    else if (sCrossSect[i] == '/')
    {
      if (rskoDtl.size() > 0)
      {
        int nLeft = rskoDtl.top().m_nLeft; rskoDtl.pop();
        int nSum = i - nLeft; 
        rnTotalArea += nSum;

        while (rvoSum.size()  &&
               nLeft < rvoSum.back().m_nLeft  &&
               rvoSum.back().m_nRight < i       )
        {
          nSum += rvoSum.back().m_nArea;
          rvoSum.pop_back();
        }
        StSum oSum(nLeft, i, nSum);
        rvoSum.push_back(oSum);
      }
      else;
    }
  }
}

void  fnCroSecGet(const vector<StSum>& cnrvoSum, int nTotalArea)
{
  cout << nTotalArea << endl;
  cout << cnrvoSum.size();
  if (cnrvoSum.size() > 0)
  {
    cout << " ";
    for (auto itvoSum = begin(cnrvoSum); itvoSum != end(cnrvoSum); ++itvoSum)
    {
      if (itvoSum != begin(cnrvoSum)) cout << " ";
      cout << itvoSum->m_nArea;
    }
  }
  cout << endl;
}

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

  stack<StDtl> skoDtl;
  vector<StSum> voSum;
  int nTtlAra = 0;

  fnCroSecSet(skoDtl, voSum, nTtlAra);
  fnCroSecGet(voSum, nTtlAra);

  return 0;
}

Measured memory_bytes: 3324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
struct edge{ll to,cost;};
const int inf = 1<<28;
const ll INF = 1LL<<53;
const int COMBMAX = 500005;
const ll MOD = 1e9+7;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;++i)
#define repf(i,n) for(int i=0;i<=n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eachdo(v, e) for(const auto& e : v)
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance(v.begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance(v.begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n,ll mod=MOD){ll res=1;while(n>0){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v,a)-lower_index(v,a);} 
template<class T> bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<class T> 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;}
template<class T> void debug2(T v){rep(i,v.size()){rep(j,v[i].size())cout<<v[i][j]<<" ";cout<<endl;}}
template<class T> void rdv(T &v){rep(i,v.size())cin>>v[i];}
template<class T> void rdvv(T &v){rep(i,v.size()){rep(j,v[i].size())cin>>v[i][j];}}
// multimap
// mmap.emplace(key,value);
// auto ngw = list.equal_range("");
// for(auto e = ngw.first; it != ngw.second ; ++e)



int main(){
    ll N; cin >> N;
    vl a(N); rdv(a);
    vl s(N+1,0);
    vl x(N+1,0);
    rep(i,N){
        s[i+1] = s[i] + a[i];
        x[i+1] = x[i] ^ a[i];
    }
    ll ans = 0;
    ll l = 0, r = 1;
    while(r < N+1){
        if((s[r] - s[l]) == (x[r] ^ x[l])){ 
            ans += r-l;
            ++r;
        }else{
            ++l;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main (){
  ll n,a,b,c,d;
  cin >> n >> a >> b >> c >> d;
  bool ans = false;
  for(int x=0;x<n-1;x++){
    ll y = (n-1)-x;
    ll top = d*x-c*y+a;
    ll bottom = c*x-d*y+a;
    if(top>=b&&b>=bottom){
      ans = true;
      break;
    }
  }
  if(ans){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    d, t, s = nm()
    if d / s <= t:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9012
s = int(input())
 
a = s
l = set()
cnt = 1
for i in range(1, 1000000):
  l.add(int(a))
  if a%2 == 0:
    a = a//2
  else:
    a = 3*a + 1
  cnt += 1
  if a in l:
    break

  i += 1
 
print(int(cnt))

Measured memory_bytes: 3060
N, M = map(int, input().split())
L_list = []
for i in range(M):
    A = list(map(int, input().split()))
    L_list.append(A)
min_range = L_list[0][0]
max_range = L_list[0][1]
for i in range(1, M):
    if L_list[i][0] >= min_range:
        min_range = L_list[i][0]
    if L_list[i][1] <= max_range:
        max_range = L_list[i][1]
print(max_range-min_range+1) if max_range>=min_range else print(0)

Measured memory_bytes: 27344
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {
	ll N,an=0;
	cin >> N;
	vector<int> a(N);
	rep(i, N) {
		cin >> a.at(i);
	}
	vector<ll> B(N, 0);
	for (ll i = N; i > 0;i--) {
		ll j = i;
		ll k = 0;
		while (j <= N) {
			k += B[j - 1];
			j += i;
		}
		if (k % 2 != a[i - 1]) { 
			B[i - 1] = 1; 
			an++;
		}
		else B[i - 1] = 0;
	}
	cout << an << endl;
	rep(i, N) {
		if (B[i] == 1) {
			an--;
			cout << i + 1;
			if (an != 0) {
				cout << " ";
			}
		}
	}
}

Measured memory_bytes: 5544
#include<iostream> 
using namespace std;
long long n,a,b,c[100005],low=0,high=1000000010,mid,count;
int main()
{	
	cin>>n>>a>>b;
	for(long long i=0;i<n;i++)
	    cin>>c[i];
	while(low<high-1)
	{
	    mid=(low+high)/2;
	    for(long long i=0;i<n;i++)
	        if(c[i]-mid*b+a-b-1>0)count+=(c[i]-mid*b+a-b-1)/(a-b);
	    if(count<=mid)
	        high=mid;
	    else
	        low=mid;
	    count=0;
	}
	cout<<high;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,m;
  while(cin>>n>>m,n||m){
    int i,j,k;
    vector<int> v;
    for(i=1;i<=n;i++) v.push_back(i);
    int p=n-1;
    while(v.size()>1){
      p=(p+m)%v.size();
      //cout << v[p] << endl;
      v.erase(v.begin()+p);
      p=(v.size()+p-1)%v.size();
    }
    cout << v[0] << endl;
  }
  return 0;
}

Measured memory_bytes: 1228
import math


def main():
    A, B, H, M = map(int, input().split())
    short_angle = math.pi * 2 * (H + M / 60) / 12
    long_angle = math.pi * 2 * M / 60
    acute_angle = min(abs(short_angle - long_angle),
                      math.pi * 2 - abs(short_angle - long_angle))
    ans = math.sqrt(A**2 + B**2 - 2 * A * B * math.cos(acute_angle))
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 62392
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		int[] ball = new int[10];
		int N = scan.nextInt();
		for(int i = 0; i < N; i++){
			for(int j = 0; j < 10; j++){
				ball[j] = scan.nextInt();
			}
			int min1 = 0;
			int min2 = 0;
			boolean flag = true;
			for(int j = 0; j < 10; j++){
				if(min1 < ball[j]){
					min1 = ball[j];
				} else if(min2 < ball[j]){
					min2 = ball[j];
				} else{
					flag = false;
					break;
				}
			}
			System.out.printf("%s\n", flag? "YES" : "NO");
		}
	}
}

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

using namespace std;
using ll = long long;



class Osa_k {
private:
	int n;
	vector<int> factor;
public:

	//O(NloglogN)
	Osa_k(int _n):n(_n) {
		factor.assign(n, 0);
		iota(factor.begin(), factor.end(), 0);
		for(int i = 2; i*i < n; i++) {
			if(factor[i] < i)continue;
			for(int j = i * i; j < n; j += i) {
				if(factor[j] == j)factor[j] = i;
			}
		}
	}

	//O(logV)
	map<int, int> sieve(int v) {
		map<int, int> ret;
		while(v != factor[v]) {
			ret[factor[v]]++;
			v /= factor[v];
		}
		if(v != 1)ret[v]++;
		return ret;
	}

	vector<int> divisor(int v) {
		
	}


	//O(N)
	vector<int> get_list() {
		vector<int> prime;
		for(int i = 2; i < n; i++)if(factor[i] == i)prime.emplace_back(i);
		return prime;
	}

	//O(1)
	bool is_prime(int v) {
		if(v <= 1)return false;
		return (factor[v] == v);
	}

}fact(10000001);


int main()
{
	int n; cin >> n;
	ll sum = 0;
	for(int i = 1; i <= n; i++) {
		auto v = fact.sieve(i);
		ll ans = 1;
		for(auto j : v)ans *= j.second+1;
		sum += ans * i;
	}
	cout << sum << endl;
}

Measured memory_bytes: 42128
#include <bits/stdc++.h>
 
using namespace std;
 
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
 
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
 


ll n, m, k, q, l, r, x, y, z;
const ll template_array_size = 1000625;
ll a[template_array_size];
ll b[template_array_size];
ll c[template_array_size];
string s, t;
ll ans = 0;

vector<ll> in_row[300005];
multiset<ll> best;

void upd(ll pos, ll delta) {
	best.erase(best.find(c[pos]));
	c[pos] += delta;
	best.insert(c[pos]);
}

void solve(int tc = 0) {
	cin >> n >> m >> k;
	
	for (ll i = 0; i < m; i++) {
		c[i] = 0;
		best.insert(0);
	}
	
	for (ll i = 0; i < k; i++) {
		cin >> x >> y;
		--x; --y;
		in_row[x].push_back(y);
		upd(y, 1);
	}
	
	ans = 0;
	for (ll i = 0; i < n; i++) {
		ll cur = in_row[i].size();
		
		for (ll x: in_row[i]) {
			upd(x, -1);
		}
		
		if (best.size()) {
			cur += *best.rbegin();
		}
		
		ans = max(ans, cur);
		
		for (ll x: in_row[i]) {
			upd(x, 1);
		}
	}
	
	cout << ans << '\n';
}
 
int main() {
	#ifdef galen_colin_local
		auto begin = std::chrono::high_resolution_clock::now();
	#endif
	
	send help
 
	#ifndef galen_colin_local
		// usaco("cowland");
	#endif
	
	// usaco("cowland");
 
	int tc = 1;
	// cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
	
	#ifdef galen_colin_local
		auto end = std::chrono::high_resolution_clock::now();
		cout << setprecision(4) << fixed;
		// cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
	#endif
} 

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

/*** Template Begins ***/

typedef long long    ll;
typedef pair<ll,ll>  pll;
typedef pair<ll, pair<int, int> > plll;
typedef vector<long long>  vll;
typedef vector<pll>  vp;

#define pb           push_back
#define INF          INT_MAX/10
#define F            first
#define S            second
#define mp           make_pair
#define ios          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hell         1000000007
#define all(a)       (a).begin(),(a).end()
ll power(ll x, ll y, ll p){ ll res = 1;x = x % p;while (y > 0){ if (y & 1) res = (res*x) % p;y = y>>1;x = (x*x) % p;} return res; } 

// Debug //

#define trace(x)                 cerr << #x << ": " << x << endl;
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

// Constants //

const int N = 1e5+7;
const int xinc[] = {0, 0, 1, -1};
const int yinc[] = {1, -1, 0, 0};

/*** Template Ends ***/
std::vector<string> p;
void permute(string str, string out) 
{ 
    // When size of str becomes 0, out has a 
    // permutation (length of out is n) 
    if (str.size() == 0) 
    { 
        p.push_back(out);
        return; 
    } 
  
    // One be one move all characters at 
    // the beginning of out (or result) 
    for (int i = 0; i < str.size(); i++) 
    { 
        // Remove first character from str and 
        // add it to out 
        permute(str.substr(1), out + str[0]); 
  
        // Rotate string in a way second character 
        // moves to the beginning. 
        rotate(str.begin(), str.begin() + 1, str.end()); 
    } 
} 

   void solve()
{
    ll n,k;
    cin>>n>>k;
    std::vector<ll> v(n+1);
    ll i;
    std::vector<ll> dp(n+1);
    for(i=1;i<n+1;i++)
      cin>>v[i];
    for(i=1;i<=n;i++)
      dp[i]=INT_MAX;
    dp[1]=0;
    for(i=2;i<=n;i++)
    {
      for(ll j=1;j<=min(i-1,k);j++)
        dp[i]=min(dp[i-j]+abs(v[i]-v[i-j]),dp[i]);
    }
    cout<<dp[n];
}
  
int main(){
  
  ios;
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  int t;
  //cin >> t;
  t = 1;
  while(t--)
    solve();

  return 0;
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using static System.Math;
class Program
{
    public static void Main(string[] args)
    {
        var n = long.Parse(Console.ReadLine());
        var v = Enumerable
            .Range(0, 5)
            .Select(_ => long.Parse(Console.ReadLine()))
            .ToArray();

        var min = v.Min();

        var div = (n + min - 1) / min;

        Console.WriteLine(div + 4);
    }
}

Measured memory_bytes: 13396
#include<stdio.h>

int A[100000], n;

int binarySearch(int key){
  int left = 0;
  int right = n;
  int mid;
  while(left < right){
    mid = (left+right)/2;
    if(key==A[mid]) return 1;
    if(key<A[mid]) right=mid;
    else if(key>A[mid]) left=mid+1;
  }
  return 0;
}

int main(){
  int i, q, k, sum=0;
  scanf("%d", &n);
  for(i=0;i<n;i++) scanf("%d", &A[i]);
  scanf("%d", &q);
  for(i=0;i<q;i++){
    scanf("%d", &k);
    if(binarySearch(k)) sum++;
  }
  printf("%d\n", sum);
  return 0;
}

Measured memory_bytes: 988
// Author: πα

#include <bits/stdc++.h>
using namespace std;
#define long int64_t
const int MOD = 1000000007;

long modexp(long x, long y, long mod = MOD)
{
    long res = 1;
    x = (x % mod + mod) % mod;
    while(y)
    {
        if(y & 1)
            res = (res*x) % mod;
        y >>= 1;
        x = (x*x) % mod;
    }
    return res;
}

int main()
{
    int x, y;
    cin >> x >> y;
    if((x+y) % 3)
        return cout << 0, 0;
    int n = (x+y)/3;
    int r = (n-x+y)/2;
    if(r < 0 or r > n)
        return cout << 0, 0;
    vector<long> f(n+1);
    f[0] = 1;
    for(long i = 1; i <= n; ++i)
        f[i] = i*f[i-1] % MOD;
    long ans = f[n];
    ans *= modexp(f[r], MOD-2), ans %= MOD;
    ans *= modexp(f[n-r], MOD-2), ans %= MOD;
    cout << ans;
    return 0;
}


Measured memory_bytes: 5504
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val a, b, c, d, e, f = sc.nextInt()

  var ansSum = a*100
  var ansSugar = 0
  for {
    ac <- 0 to f / (a*100)
    bc <- 0 to (f - a*100*ac) / (b*100)
  } {
    val water = (a*ac + b*bc) * 100
    val limit = (f - water).min((water / 100) * e)
    for (cc <- 0 to limit / c) {
      val dc = (limit - c*cc) / d
      val sugar = c*cc + d*dc
      val sum = water + sugar
      if (ansSugar * sum < sugar * ansSum) {
        ansSugar = sugar
        ansSum = sum
      }
    }
  }

  println(s"$ansSum $ansSugar")
}


Measured memory_bytes: 55404
#include <bits/stdc++.h>
using namespace std;
/* {{{ */
/*-------------------------------*/
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)

#define all(i) (i).begin(),(i).end()
#define rall(i) (i).begin(),(i).end(),greater<int>()
#define PB push_back
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
//#define int long long

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<long long> llv;
typedef vector<pint> vpint;

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1}; 

inline int in(){int x;std::cin>>x;return x;}

struct FAST {FAST(){cin.tie(0);ios::sync_with_stdio(false);}} Fast;

template <class X> void print(X hoge){ cout << hoge << '\n'; }
/*-------------------------------*/
/* }}} */ 

signed main(void)
{
  int d, a;
  int now = 90;
  double x = 0, y = 0;

  while (scanf("%d,%d", &d, &a), d || a) {
    x += d * cos(M_PI * now / 180.0);
    y += d * sin(M_PI * now / 180.0);

//    now = (now - a + 360) % 360;
    now -= a;
  }

  print((int)x);
  print((int)y);

  return (0);
}

Measured memory_bytes: 3484
#include <bits/stdc++.h> 
 
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define fi first
#define se second
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef long double ld;
typedef string st;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
const ll MOD = 1e9 + 7 ;
const ll INF=1e14;                                                                                           
ll mpow(ll a,ll b,ll p=MOD){a=a%p;ll res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}             
const ll N=51;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll a,b,k;
  cin>>a>>b>>k;
  forn(i,k)
  {
    if(i%2==0)
    {
      if(a%2==1) a--;
      b+=a/2;
      a/=2;
    }
    else{
      if(b%2==1) b--;
      a+=b/2;
      b/=2;
    }
    //cout<<a<<" "<<b<<"\n";
  }
  cout<<a<<" "<<b;
}
//nothing is impossible

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
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int  ll;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int nxt() {int x;scanf("%d", &x);return x;}


int main(){
    int a=nxt();
    string op;
    cin>>op;
    int b=nxt();
    int out;
    if(op=="+"){
        out=a+b;
    } else if(op=="-"){
        out=a-b;
    }
    printf("%d",out);
    return 0;
}



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

using namespace std;

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    ll m;
    cin >> m;
    vector<ll> a(n), sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + a[i];
    }

    ll ok = 0, ng = 200005;
    while (ng - ok > 1) {
        ll mid = (ok + ng) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; ++i) {
            int idx = lower_bound(a.begin(), a.end(), mid - a[i]) - a.begin();
            cnt += (n - idx);
        }
        (cnt >= m ? ok : ng) = mid;
    }

    ll ans = 0;
    ll cnt = 0;
    for (int i = 0; i < n; ++i) {
        int idx = lower_bound(a.begin(), a.end(), ok - a[i]) - a.begin();
        cnt += n - idx;
        ans += sum[n] - sum[idx] + a[i] * (n - idx);
    }
    ans -= (cnt - m) * ok;
    cout << ans << "\n";
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  cout << A[N/2] - A[(N/2)-1] << endl;
}


Measured memory_bytes: 640
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

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

// ここまで

fn run() {
    input! {
        n: i32,
        a: i32,
        b: i32,
    }
    let ans = std::cmp::min (n * a, b);
    println! ("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
	int n; cin >> n;
	std::vector<int> v;
	for (int i = 0; i < n; ++i)
	{
		int a; cin >> a;
		v.push_back(a);
	}
///////////////////////////////////////
	std::vector<int> s(n);
	s[0] = v[0];
	for (int i = 1; i < n; ++i)
	{
		s[i] = v[i] + s[i - 1];
	}
////////////////////////////////////////
    int ans = 1000000;
	for (int i = 0; i < n; ++i)
	{
		ans = min(   ans, abs(s[n - 1]- 2 * s[i])    );
	}

	
	cout << ans << endl;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        A: u32,
        B: u32,
        S: String
    }

    if S.chars().count() != (A + B + 1) as usize {
        println!("No");
        return;
    }

    for (index, value) in S.chars().enumerate() {
        if index != A as _ && value == '-' {
            println!("No");
            return;
        }

        if index == A as _ && value != '-' {
            println!("No");
            return;
        }
    }

    println!("Yes");
}


Measured memory_bytes: 2188
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl
typedef long long ll;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;

using namespace std;

int main(){
    vector<int> c(26,0), e(26,0);
    string s;   cin >> s;
    if(s == "zyxwvutsrqponmlkjihgfedcba"){print(-1); return 0;}
    int l = s.length();
    for(int i=0; i<l; i++)  c[s[i] - 'a']++;
    for(int i=0; i<26; i++) if(c[i] == 0){
        s += char(i + 'a');
        print(s);
        return 0;
    }
    map<string,int> mp;
    string t;
    for(int i=0; i<l; i++){
        e[s[i] - 'a'] = 1;
        for(int j=0; j<26; j++){
            if(e[j] == 0) t = s.substr(0,i) + char(j + 'a');
            mp[t] = 1;
        }
    }
    for(auto it = mp.begin(); it != mp.end(); it++) if(it -> first > s){print(it -> first); return 0;}
}

Measured memory_bytes: 3632
import math


def main():
    N = int(input())
    SP = [list(input().split()) + [i + 1] for i in range(N)]
    SP.sort(key=lambda x: (x[0], -int(x[1])))
    for i in map(lambda x: x[2], SP):
        print(i)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
def solve()
  n = readline.to_i
  p = readline.split.map!(&:to_i)
  cnt = 0
  array = []
  for i in 1..n-2 do
    array.push(p[i-1], p[i], p[i+1])
    if array.max != p[i] && array.min != p[i] then
      cnt += 1
    end
    array = []
  end
  print(cnt)
end
solve()

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

ll calc_gcd(ll x,ll y){
    if(y==0) return x;
    return calc_gcd(y,x%y);
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll a, b;
cin >> a >> b;
ll gcd = calc_gcd(a, b);
vector<ll> div;
ll num = gcd;
for (ll i=2; i * i < gcd; i++)
{
    if(num%i==0){
        div.pb(i);
        while(num%i==0){
                num /= i;
            }
    }
}
if(num>1)
    div.pb(1);
cout << div.size()+1 << endl;
//system("pause");
return 0;
}

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

int main() {
    ll n, energy = 1;
    cin >> n;
    for (ll i = 1 ; i <= n ; i++){
        energy *= i;
        energy %= ll(pow (10, 9) + 7);
    }
    
    cout << energy % ll(pow (10, 9) + 7)<< endl;
    return 0;
}




Measured memory_bytes: 256
N, M = map(int, input().split())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))
A.sort()
count = 0
nedan = 0
for s in range(N):
	count += A[s][1]
	if(count < M):
		nedan += A[s][0]*A[s][1]
	elif(count >= M):
		nedan += A[s][0]*A[s][1]
		nedan -= A[s][0]*(count - M)
		print(nedan)
		exit()


Measured memory_bytes: 27760
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int n,cnt;
    vector<int> v,w;
    cin>>n;
    v.resize(n);
    w.resize(n);
    for(int i=0; i<n; i++){
        cin>>v[i];
        w[i]=v[i];
    }
    sort(v.begin(),v.end());
    cnt=0;
    for(int i=0; i<n; i++){
        if(v[i]!=w[i]){
            cnt++;
        }
    }
 
    if(cnt<3){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define el "\n"
#define F first
#define S second
#define PI 3.14159265358979323846  /* pi */
#define FOR(i,a,b) for(int i = a; i < b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define RI(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(n)-1)
#define SQR(x) (x)*(x)
#define all(v)  	((v).begin()),((v).end())
#define degreesToRadians(angleDegrees) (angleDegrees * PI / 180.0) // Converts degrees to radians.
#define radiansToDegrees(angleRadians) (angleRadians * 180.0 / PI) // Converts radians to degrees.
typedef long long ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double ld;
typedef vector<int>		vi;
typedef vector<ll>		vll;
typedef vector<pii>		vpii;
typedef vector<pll>		vpll;
const double EPS = 1e-9;
const int N = 1e3+2, M = 3e5+5, OO = 0x3f3f3f3f;
// int dx[] = {1,-1,0,0} , dy[] = {0,0,1,-1}; // 4 Direction
// int dx[] = {1,-1,0,0,1,1,-1,-1}, dy[] = {0,0,1,-1,1,-1,1,-1}; // 8 Direction
// int dx[] = {1,-1,1,-1,2,2,-2,-2} , dy[] = {2,2,-2,-2,1,-1,1,-1}; // Knight Direction
// int dx[] = {2,-2,1,1,-1,-1} , dy[] = {0,0,1,-1,1,-1}; // Hexagonal Direction

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
  int k,a,b;
  cin>>k>>a>>b;
  bool ans = false;
  for(int i=a;i<=b;i++){
    if(i%k==0){
      ans = true;
      break;
    }
  }
  if(ans){
    cout<<"OK"<<endl;
  }
  else{
    cout<<"NG"<<endl;
  }
	return 0;

}


Measured memory_bytes: 3652
import sys
input=sys.stdin.readline
N,K=map(int,input().split())
P=[0 for i in range(N+1)]
C=[0 for i in range(N+1)]

L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append((a,b))
    L[b].append((b,a))
    
P[1]=-1
Q=L[1]
#print(Q)
#print(L)
for i in range(N-1):
    #print(i,Q)
    if P[Q[i][1]]==0:
        P[Q[i][1]]=Q[i][0]
        C[Q[i][0]]+=1
        for j in L[Q[i][1]]:
            if P[j[1]]==0:
                Q.append(j)
    #print(i)
#print(P,C,Q)
mod=10**9+7
ans=K
for i in range(C[1]):
    ans*=(K-i-1)
    ans%=mod
    
#print(ans)
ANS=[0 for i in range(N+1)]
ANS[1]=ans
for i in range(2,N+1):
    if C[i]!=0:
        for j in range(C[i]):
            ans*=(K-j-2)
            #print(i,j)
            ans%=mod
            ANS[i]=ans
#print(ANS)
print(ans)

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

int n,m,maxv=-1;
char a[25][25];
int GA[25][25][25][25];

int main()
{
	cin>>n>>m;
	memset(a,' ',sizeof(a));
	memset(GA,inf,sizeof(GA));
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)  cin>>a[i][j];
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			if (a[i][j]==a[i][j-1]&&a[i][j]=='.')  GA[i][j][i][j-1]=GA[i][j-1][i][j]=1;
			if (a[i][j]==a[i][j+1]&&a[i][j]=='.')  GA[i][j][i][j+1]=GA[i][j+1][i][j]=1;
			if (a[i][j]==a[i+1][j]&&a[i][j]=='.')  GA[i][j][i+1][j]=GA[i+1][j][i][j]=1;
			if (a[i][j]==a[i-1][j]&&a[i][j]=='.')  GA[i][j][i-1][j]=GA[i-1][j][i][j]=1;
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)  GA[i][j][i][j]=0;
	}
	for (int ki=1;ki<=n;ki++)
	{
		for (int kj=1;kj<=m;kj++)
		{
			if (a[ki][kj]=='#')  continue;
			for (int ii=1;ii<=n;ii++)
			{
				for (int ij=1;ij<=m;ij++)
				{
					if (a[ii][ij]=='#')  continue;
					for (int ji=1;ji<=n;ji++)
					{
						for (int jj=1;jj<=m;jj++)
						{
							if (a[ji][jj]=='#')  continue;
							if (GA[ii][ij][ji][jj]>GA[ii][ij][ki][kj]+GA[ki][kj][ji][jj])
							{
								GA[ii][ij][ji][jj]=GA[ii][ij][ki][kj]+GA[ki][kj][ji][jj];
								GA[ji][jj][ii][ij]=GA[ii][ij][ki][kj]+GA[ki][kj][ji][jj];
							}
						}
					}
				}
			}
		}
	}
	for (int ii=1;ii<=n;ii++)
	{
		for (int ij=1;ij<=m;ij++)
		{
			for (int ji=1;ji<=n;ji++)
			{
				for (int jj=1;jj<=m;jj++)
				{
					if (GA[ii][ij][ji][jj]>n*m)  continue;
					else maxv=max(maxv,GA[ii][ij][ji][jj]);
				}
			}
		}
	}
	cout<<maxv<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
int main() {
    int n, a, b; cin >> n >> a >> b;
    if ((b-a)%2) {
        cout << "Borys" << endl;
    }
    else {
        cout << "Alice" << endl;
    }
    return 0;
}


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

int main(){
  int d, t, s;
  cin >> d >> t >> s;
  int count = t * s;
  if(count >= d){
    std::cout << "Yes" << '\n';
  }
  else{
    std::cout << "No" << '\n';
  }
  return 0;
}

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

using namespace std;

typedef long long ll;

int main()
{
    int N, M;
    cin >> N >> M;
    int A[1000];
    double threshould = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        threshould += A[i];
    }
    threshould /= 4.0 * M;
    int num = 0;
    for (int i = 0; i < N; i++) {
        if (!(A[i] < threshould)) {
            num++;
        }
    }
    if (num >= M) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

int main(){
  char temp, out ='a';
  map<char,string> mp;
  for(int i=0;i<3;++i) {
    string s;
    cin >> s;
    mp['a'+i] = s;
  }
  while(1){
    if(mp[out]=="") break;
    temp=mp[out][0];
    mp[out].erase(mp[out].begin());
    out = temp;
  }
  out -=32;
  cout << out << endl;
}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;
std::string S;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> S; N = S.size();
	int64_t count = 0;
	int last = N - 1;
	for (int i = N - 1; i >= 0; i--)
	{
		if (S[i] == 'B') {
			count += last - i;
			--last;
		}
	}
	out << count << endl;

	return 0;
}
#endif


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

#include <vector>
int main(){
    int K,a = 7;cin >> K;
    for(int i=1; i<=K; i++) {
        a %= K;
        if(a==0){
            cout << i << endl;
            return 0;
        }
        a = 10*a+7;
    }
    cout << -1 << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <set>
#include <vector>

#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n)                       _range(i, 0, n)
#define _range(i, a, b)                  for (int i = int(a); i < int(b); ++i)
#define rep(...)                         _overload(__VA_ARGS__, _range, _rep, )(__VA_ARGS__)

#define _rrep(i, n)      _rrange(i, n, 0)
#define _rrange(i, a, b) for (int i = int(a) - 1; i >= int(b); --i)
#define rrep(...)        _overload(__VA_ARGS__, _rrange, _rrep, )(__VA_ARGS__)

using ll = long long;
using namespace std;

const int limit = 200010;
int nxt[18][limit];
ll nsum[18][limit];

int prv[18][limit];
ll psum[18][limit];


int main(void) {
    ll n, d;
    cin >> n >> d;
    vector<int> x(n);
    rep(i, n) cin >> x[i];

    {
        int pos = 0;
        rep(i, n) {
            while (pos < n and x[pos] - x[i] < d) {
                pos++;
            }
            nxt[0][i] = pos;
            nsum[0][i] += i;
        }
    }

    {
        int pos = n - 1;
        rrep(i, n) {
            while (pos >= 0 and x[i] - x[pos] < d) {
                pos--;
            }
            prv[0][i] = pos;
            psum[0][i] += i;
        }
    }

    rep(k, 1, 18) {
        rep(i, n) {
            nxt[k][i]  = (nxt[k - 1][i] == n) ? n : nxt[k - 1][nxt[k - 1][i]];
            nsum[k][i] = (nxt[k - 1][i] == n)
                             ? nsum[k - 1][i]
                             : nsum[k - 1][nxt[k - 1][i]] + nsum[k - 1][i];

            prv[k][i]  = (prv[k - 1][i] == -1) ? -1 : prv[k - 1][prv[k - 1][i]];
            psum[k][i] = (prv[k - 1][i] == -1)
                             ? psum[k - 1][i]
                             : psum[k - 1][prv[k - 1][i]] + psum[k - 1][i];
        }
    }

    int q;
    cin >> q;

    rep(loop, q) {
        int l, r;
        cin >> l >> r;
        l--, r--;

        ll num  = 1LL;
        int cur = l;
        rrep(k, 18) {
            if (nxt[k][cur] <= r) {
                cur = nxt[k][cur];
                num += 1 << k;
            }
        }

        ll ans = num;

        int cl = l;
        int cr = r;
        rrep(k, 18) {
            if (num >> k & 1) {
                ans -= nsum[k][cl];
                cl = nxt[k][cl];
                ans += psum[k][cr];
                cr = prv[k][cr];
            }
        }

        cout << ans << endl;
    }


    return 0;
}

Measured memory_bytes: 88156
#include <stdio.h>

int n,a[10000];
//int Culc(int, int);

int main()
{
  int i,j,q,m;

  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",&a[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&m);
    if(Culc(0,m)) printf("yes\n");
    else printf("no\n");
    }
  return 0;
}

int Culc(int s,int m){
  int res;
  
  if(m==0) return 1;
  if(n<=s) return 0;
  res=(Culc(s+1,m) || Culc(s+1,m-a[s]));
  return res;
}

Measured memory_bytes: 580
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

long long K, P = 7;

int main() {
	cin >> K;
	P = 7 % K;
	for (int i = 1; i <= 10000000; i++) {
		if (P == 0) { cout << i << endl; return 0; }
		P = P * 10LL + 7LL;
		P %= K;
	}
	cout << "-1" << endl;
	return 0;
}

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

int main()
{
	int A, B, C, week, ans;

	scanf("%d%d%d", &A, &B, &C);
	week = (C-1) / (7*A+B);
	if (week * (7 * A + B) + 7 * A < C) ans = 7 * (week + 1);
	else ans = 7 * week + ((C - week * (7 * A + B) - 1) / A + 1);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2100
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

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

  vector<vector<char>> s(n);

  string temp;
  for(int i=0; i<n; ++i){
    cin >> temp;
    for(int j=0; j<temp.size(); ++j){
      s[i].push_back(temp[j]);
    }
  }

  for(int i=1; i<n; ++i){
    vector<char> temp = s[0];
    for(int j=0; j<s[0].size(); ++j){
      int moto = count(temp.begin(), temp.end(), s[0][j]);
      int saki = count(s[i].begin(), s[i].end(), s[0][j]);

      if(moto == saki){
        
      }else if(saki < moto){
        int era = moto - saki;
        char e = s[0][j];
        for(int k=0; k<era; ++k){
          vector<char>::iterator it = find(temp.begin(), temp.end(), e);
          temp.erase(it);
        }
      }
    }
    s[0] = temp;
  }

  sort(s[0].begin(), s[0].end());

  string out="";
  for(int i=0;i<s[0].size();++i){
    out += s[0][i];
  }

  cout << out << endl;
        return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#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
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
const int mod=1e9+7;
//Combination
long long extGCD(long long a,long long mod,long long &x,long long &y){
    if(mod==0){
        x=1;
        y=0;
        return a;
    }
    long long d=extGCD(mod,a%mod,y,x);
    y-=(a/mod)*x;
    return d;
}
long long invmod(long long a,long long mod){
    long long x,y;
    extGCD(a,mod,x,y);
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
ll fac[200010],finv[200010],inv[200010];
void combinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    REP(i,2,200010){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=invmod(i,mod);
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll comb(ll n,ll k){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
int main(){
    combinit();
    ll n;cin>>n;
    vector<ll>a(n);
    rep(i,n)cin>>a[i];
    vector<ll>b(60);
    rep(i,n){
        rep(j,60){
            if((1LL<<j)&a[i])b[j]++;
        }
    }
    ll ans=0;
    rep(i,60){
        rep(j,n){
            if((1LL<<i)&a[j]){
                ans+=(((n-b[i])%inf)*((1LL<<i)%inf));
                ans%=inf;
            }else{
                ans+=(((b[i])%inf)*((1LL<<i)%inf));
                ans%=inf;
            }
        }
    }
    ans*=invmod(2,inf);
    ans%=inf;
    if(ans<0)ans+=inf;
    cout<<ans<<endl;
}

Measured memory_bytes: 7296
o=998244353
f=[1]
for i in range(1,2500100):f.append(f[-1]*i%o)
def c(n,k):return f[n]*pow(f[n-k],o-2,o)*pow(f[k],o-2,o)%o
n,m=map(int,input().split())
w=3*m
u=n-1
a=c(w+u,u)-n*c(n+m-2,u)
if u>m:
 for i in range(m+1,min(w,n)+1):
  if w-i+1&1:a=(a-c(n,i)*c((w-i)//2+u,u))%o
print(a%o)

Measured memory_bytes: 107420
#include <bits/stdc++.h>
using namespace std;
const int maxn = 101;
int u[maxn][maxn];
int main(){
	for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) u[i][j] = 1<<29;
	for(int i = 0; i < maxn; i++) u[i][i] = 0;
	int n, m; cin >> n >> m;
	vector<tuple<int,int,int> > ed;
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c;
		u[a][b] = c;
		u[b][a] = c;
		ed.push_back(make_tuple(a, b, c));
	}
	for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) u[j][k] = min(u[j][k], u[j][i] + u[i][k]);
	int ans = 0;
	for(auto e : ed){
		int a, b, c; tie(a, b, c) = e;
		bool good = false;
		for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) if(u[i][a] + c + u[b][j] == u[i][j]) good = true; 
		swap(a, b);
		for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) if(u[i][a] + c + u[b][j] == u[i][j]) good = true;
	       	if(!good) ans++;
	}
	cout << ans << endl;
	return 0;
}	


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define pri 1000000007
#define all(x) x.begin(),x.end()
#define mx 32
using namespace std;

void masterstroke(){
ll r;
cin>>r;
cout<<3*r*r;

}


int main() {
	ll t=1;
	//cin>>t;
	for(ll i=0;i<t;i++)masterstroke();
	
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
 
n = int(input())
connect_list = [[] for i in range(n)]

for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append(b)
    connect_list[b].append(a)
 

def djkstra(in_connect_list):
    out_parent_list = [-1 for i in range(n)]
    out_shortest_list = [-1 for i in range(n)]
    out_shortest_list[0] = 0
    searching_list = [0]
    
    while searching_list != []:
    
        new_search_list = []
        for i in searching_list:
            for j in in_connect_list[i]:
                if out_shortest_list[j] == -1:
                    out_shortest_list[j] = 1 + out_shortest_list[i]
                    out_parent_list[j] = i
                    new_search_list.append(j)
        searching_list = new_search_list


    return out_shortest_list, out_parent_list

shortest_list, parent_list = djkstra(connect_list)

nto1_list = [n-1]
while nto1_list[-1] != 0:
    nto1_list.append(parent_list[nto1_list[-1]])
nto1_list = list(reversed(nto1_list))


shortest_length = len(nto1_list) 
if shortest_length % 2 == 0:
    p = nto1_list[(shortest_length//2)-1]
    q = nto1_list[shortest_length//2]
else:
    p = nto1_list[shortest_length//2]
    q = nto1_list[(shortest_length//2)+1]

del connect_list[p][connect_list[p].index(q)]
del connect_list[q][connect_list[q].index(p)]


shortest_list, parent_list = djkstra(connect_list)

snu, fen = shortest_list.count(-1), n - shortest_list.count(-1)
if fen > snu:
    print("Fennec")
else:
    print("Snuke")

Measured memory_bytes: 69460