akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

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

int main(int argc, char **argv)
{
    int N, M;
    cin >> N >> M;
    ll A[N];
    REP(i, N) cin >> A[i];
    int B[M];
    ll C[M];
    REP(i, M) cin >> B[i] >> C[i];

    map<ll, int> m;
    REP(i, N) {
        if (m.find(A[i]) != m.end()) m[A[i]] += 1;
        else m[A[i]] = 1;
    }

    pair<ll, int> p[M];
    REP(i, M) p[i] = make_pair(C[i], B[i]);
    sort(p, p + M);

    REP(i, M) {
        int c = 0;
        for (auto itr = m.begin(); itr != m.end();) {
            if (itr->first >= p[i].first) break;
            else if (c >= p[i].second) break;
            else {
                if (itr->second + c <= p[i].second) {
                    c += itr->second;
                    itr = m.erase(itr);
                }
                else {
                    itr->second -= p[i].second - c;
                    c = p[i].second;
                    itr++;
                }
            }
        }
        if (c > 0) {
            if (m.find(p[i].first) != m.end()) m[p[i].first] += c;
            else m[p[i].first] = c;
        }
    }
    ll score = 0;
    for (auto itr = m.begin(); itr != m.end(); ++itr) {
        score += (itr->first) * (itr->second);
    }
    cout << score << endl;

    return 0;
}


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

#define Pb push_back
#define Mp make_pair
#define ff first
#define ss second
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define db1(x) cout<<#x<<" : "<<x<<endl;
#define db2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define db3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;

typedef long long int ll;
typedef long double ld;

const int  N = 1e5+7;
const int inf = INT_MAX;
const int MOD = 1e9+7;

void solve()
{
   int a;
   cin >> a;
   a = a+a*a+a*a*a;
   cout << a;
}

int32_t main()
{
   IOS;
   //freopen("input.txt", "rt", stdin);
   //freopen("output.txt", "wt", stdout);
   int t=1;
   //cin >> t;
   for(int i=1;i<=t;i++)
   {
      //cout<<"Case #"<<i<<": ";
      solve();
   }
   return 0;
}
/*==============================================================================================================================================================*/


Measured memory_bytes: 3648
program main
  implicit none
  integer(8) :: N
  integer(8) :: i,j
  integer :: out
  integer :: F
  read(*,*) N
  out = 30
  do i = 1, int ( sqrt(real(N)) )
     if ( mod(N,i) == 0) then
        F = max( digit(i), digit(N/i) )
        if ( out > F) then
           out = F
        end if
     end if
  end do
  write(*,'(i0)') out
  stop
contains
  integer function digit(N)
    integer(8) :: N
    integer(8) :: N_tmp
    N_tmp = N
    digit = 0
    do
       N_tmp = N_tmp/10
       digit = digit + 1
       if (N_tmp == 0) exit
    end do
    !digit = int(log10(real(N,8))+1)
  end function digit
end program main


Measured memory_bytes: 512
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000 * 1000 + 10;
int arr[MAXN];
int main(){
int a, b, c, k;
cin >> a>>b>>c>>k;
int sum = 0;
if(k <= a){
	cout << k;
}else{
	sum += a;
	k -= a;
	if(k <= b){
		cout << sum;
		return 0;
	}else{
		k = k - b;
		sum -= k;
		cout << sum;
	}
}

return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define ll long long
#define pb push_back
#define x first
#define ld long double
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) a.begin(),a.end()

using namespace std;

using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a;
    cin >> a;
    int n = (int)a.length(), ans1 = 0, ans2 = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) ++ans1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] != a[i + 1]) ++ans2;
    }
    cout << min(ans1, ans2) << '\n';
}


Measured memory_bytes: 512
#include <stdio.h>

int main(void) {
    int m, f, r;
    while(scanf("%d %d %d", &m, &f, &r) + m + f + r) {
        if(m < 0 || f < 0) {
            printf("F\n");
        } else if(m + f > 79) {
            printf("A\n");
        } else if(m + f > 64) {
            printf("B\n");
        } else if(m + f > 49) {
            printf("C\n");
        } else if(m + f > 29) {
            printf("%s\n", r > 49 ? "C" : "D");
        } else {
            printf("F\n");
        }
    }
    return 0;
}

Measured memory_bytes: 584
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main(){
    int r,d,x;
    cin >>r>>d>>x;
    for (int i=0; i<10;i++){
        x = r*x - d;
        cout << x << endl;
    }
    return 0;
}

Measured memory_bytes: 256
//by OIerC
//Forca Barcelona!
#include<cstdio>
#include<algorithm>
using namespace std;

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

int main()
{
	int a = read();
	int b = read();
	printf("%d\n", max(max(a + b, a - b), a * b));
	return 0;
}


Measured memory_bytes: 128
n, k = list(map(int, input().split()))
mod = 1000000007
nums = [i for i in range(n + 1)]
ans = 0

for i in range(k, n + 2):
	mx = n * (n + 1) // 2 - (n - i) * (n - i + 1) // 2
	mn = i * (i - 1) // 2
	ans += (mx - mn + 1) % mod
	ans %= mod
print(ans)

Measured memory_bytes: 17032
n, a, b = [ int(v) for v in input().split() ]
if (a + b) % 2 == 0:
    print(abs(a-b)//2)
else:
    if a > b:
        a, b = b, a
    
    up = (b + a - 1) // 2
    down = (2 * n - b - a + 1) // 2
    print(min(up, down))

Measured memory_bytes: 3060
/*
  Author - KISHAN TIWARI
  Dream bigger. Do bigger.
  Wake up with determination. Go to bed with satisfaction.
*/
//Sometimes later becomes never. Do it now.
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define f(i,a,b)     for(ll i=a;i<b;i++)
#define mod          1000000007
#define fi           first
#define se           second
#define pa           pair <ll,ll>
#define mp           make_pair
#define pb           push_back
#define ve           vector<ll>
#define vep          vector< pa >
#define all(a)       a.begin(), a.end()
#define sz(x)        (ll)x.size()
#define c(t)         cout<<t<<"\n"
using namespace std;
void solve()
{  ll n;
cin>>n;
multiset<double> s;
f(i,0,n)
{
    double d;
    cin>>d;
    s.insert(d);
}
while(s.size()>1)
{   multiset<double> :: iterator p=s.begin();
    double x=*(p);
    p++;
    double y=*(p);
    p--;
    s.erase(p);
    multiset<double> :: iterator pr=s.begin();
    s.erase(pr);
    double z=(double)(((double)(x)+(double)(y))/(double)2);
    //cout<<z<<"\n";
    s.insert(z);
}
multiset<double> :: iterator p=s.begin();
printf("%.8lf\n",*p);
}
int main()
{
    ios::sync_with_stdio(true);
   //freopen ("input.txt","r",stdin);
   //freopen ("output.txt","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--)
    {

        solve();
    }
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace   std;
#define ff        first
#define ss        second
#define ll        long long
#define int       long long
#define inf       ((ll)1e18)
#define double    long double
#define ull       unsigned long long
#define mod       1000000007
#define vi        vector<ll>
#define extreme   inline
#define ppi       pair<ll,pair<ll,ll>>
#define pb        push_back
#define mp        make_pair
#define str       string
#define pi        2*acos(0.0)
#define pr(a,x,n) for(int i=x;i<n;i++){cout<<a[i]<<" ";}
#define p(a)      cout<<a;
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define all(v)    v.begin(), v.end()
#define test      cout<<"THIS_AND_THIS"<<endl;
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
void solve(){
	ll a,b,c;
	cin>>a>>b>>c;
	swap(a,b);
	swap(a,c);
	cout<<a<<" "<<b<<" "<<c;
}
int32_t main(){
	kehsihba();
	ll t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
  int n ; 
  cin >> n ; 
  vector<tuple<string,int,int>> data ;
  
  rep(i,n){
    string s ; 
    int p ; 
    cin >> s >> p ; 
    data.push_back(make_tuple(s,100-p,i+1));
  }
  sort(all(data)) ;
       
  for(auto p :data){
    string a ;
    int b, c ;
    tie(a,b,c) = p ;
    cout << c <<endl ;
  }

}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
lli gcd(lli a, lli b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 

int main() 
{
    
    lli n, k = 1, c;
    cin >> n;
    lli a[n];
    for(lli i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i] == k)
        {
            k++;
        }
    }
    if(k == 1)
        cout << -1;
    else
        cout << n - k +1;
    
    return 0;
    
}

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

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; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod = 1e9+7;

int d;
vector<int> c;
vector<vector<int>> s;
vector<int> last(26, 0);

ll calculate(int date, int choice) {
    ll ans = 0;
    ans += s[date][choice];
    last[choice] = -1;
    rep (i, 26) {
        last[i]++;
        ans -= last[i] * c[i];

    }
    return ans;
}

vector<int> argsort(vector<int> v) {
    vector<int> indices(v.size());
    iota(indices.begin(), indices.end(), 0);
    // ソートする。
    sort(indices.begin(), indices.end(), [&v](int i1, int i2) {
        return v[i1] < v[i2];
    });
    return indices;
}

int greedy(int date) {
    vector<int> score(26, 0);
    rep (i, 26) {
        score[i] = s[date][i] + last[i] * c[i];
    }
    vector<int> indices = argsort(score);
    last[indices[25]] = 0;
    return indices[25];
}

int main() {
    cin >> d;
    c.resize(26);
    rep (i, c.size()) {
        scanf("%d", &c[i]);
    }
    s.resize(d, vector<int>(26));
    rep (i, d) {
        rep (j, c.size()) {
            cin >> s[i][j];
        }
    }
    ll default_score = 0;
    vector<int> default_res(d);
    rep (i, d) {
        default_res[i] = greedy(i);
        default_score += calculate(i, default_res[i]);
    }
    random_device rnd;
    mt19937 mt(rnd());
    uniform_int_distribution<> rand26(0, 25), rand365(0, 364);

    rep (i, 10000) {
        int p = rand26(mt);
        int q = rand365(mt);
        auto changed_res = default_res;
        changed_res[q] = p;
        ll changed_score = 0;
        rep (j, 26) {
            last[j] = 0;
        }
        rep (j, d) {
            changed_score += calculate(j, changed_res[j]);
        }
        if (changed_score > default_score) {
            default_res = changed_res;
            default_score = changed_score;
        }
    }

    rep (i, d) {
        cout << default_res[i] + 1 << endl;
    }
}




Measured memory_bytes: 3788
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);
		String S = sc.nextLine();

		boolean flag = true;

		int c=0;
		for(int i=0;i<S.length();i++) {

			if(i == 0) {
				if(S.charAt(0) != 'A') {
					flag = false;
					break;
				}
			}else if(i >= 2 && i < S.length() - 1) {
				if(S.charAt(i) == 'C') {
					c++;
				}else if(Character.isUpperCase(S.charAt(i))) {
					flag = false;
					break;
				}
			}else {
				if(Character.isUpperCase(S.charAt(i))) {
					flag = false;
					break;
				}
			}
		}

		if(c != 1) flag = false;

		if(flag) {
			System.out.println("AC");
		}else {
			System.out.println("WA");
		}
	}

}


Measured memory_bytes: 22608
N = int(input())
MOD = 10**9 + 7

# DP[n][a][b][c] := n-2文字目がa, n-1文字目がb, n文字目がcであるような長さnの文字列の数
DP = [[[[0 for _ in range(4)] for _ in range(4)]
       for _ in range(4)] for _ in range(N + 1)]

# T=0, A=1, G=2, C=3　とする

# DP初期化（3文字）
# AGC(123), GAC(213), ACG(132)を除外
for a in range(4):
    for b in range(4):
        for c in range(4):
            if (a, b, c) not in ((1, 2, 3), (2, 1, 3), (1, 3, 2)):
                DP[3][a][b][c] = 1

# 4~N文字の文字列について
# AGC(123), GAC(213), ACG(132)に加え、A*GC(1*23), AG*C(12*3)も除外
for i in range(4, N + 1):
    for a in range(4):
        for b in range(4):
            for c in range(4):
                # 末尾が T or A の場合は特に制限はない
                DP[i][b][c][0] += DP[i - 1][a][b][c]
                DP[i][b][c][1] += DP[i - 1][a][b][c]
                # 末尾が G の場合、ACGになってはならない
                if (b, c) != (1, 3):
                    DP[i][b][c][2] += DP[i - 1][a][b][c]
                # 末尾がCの場合、AGC, GAC, A*GC, AG*Cは不適
                if (b, c) != (1, 2) and (b, c) != (2, 1) and (a, c) != (1, 2) and (a, b) != (1, 2):
                    DP[i][b][c][3] += DP[i - 1][a][b][c]

ans = 0
# 末尾3文字（計64通り）の総和
for a in range(4):
    for b in range(4):
        for c in range(4):
            ans += DP[N][a][b][c]
            ans %= MOD

print(ans % MOD)


Measured memory_bytes: 75264
N, K = map(int, input().split())  # N個の足場, K段飛ぶことができる

H = list(map(int, input().split()))

dp = [1e+9]*N
dp[0] = 0
dp[1] = abs(H[1]-H[0])

for i in range(2, N):
    # Kステップ前まで考慮する必要
    for j in range(1, min(i, K)+1):
        dp[i] = min(dp[i], dp[i-j]+abs(H[i]-H[i-j]))

print(dp[-1])


Measured memory_bytes: 55008
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
//using namespace __gnu_pbds;
using namespace std;
typedef long long  L;

#define max_(x, y) (((x) > (y)) ? (x) : (y))
#define min_(x, y) (((x) < (y)) ? (x) : (y))
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Mx 2000001
#define inf 1e15
const L MOD = 1e9+7;
const double pi = 2 * acos (0.0);

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/


//typedef tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

L a1,a2,a3,b1,b2,b3,c,c1,c2,c3,d,d1,d2,d3,d4,d5,e1,e2,e3,f,h,k,l,m,n,m1,m2,n1,n2,o,p,p1,p2,p3,p4,q,q1,q2,q3,q4,r,s,t,
u,v,x,y,z,sum,mx=-inf,mn=inf,flg,flg1,flg2,id1,id2,id3,id4,lim;

//double rat;
L A[Mx+5],B[Mx+5];
void solve(){
    sort(A,A+n);
    c=0;
    mx=A[n-1]+1;
    for(L i=0;i<n;i++){
        // printf("%lld ",A[i]);
        if(A[i]==1){
            if(i+1<n&&A[i+1]==1){
                printf("0\n");
            }else{
                printf("1\n");
            }
            return;
        }
        if(i+1<n&&A[i+1]==A[i]){
            i++;
            while(i+1<n&&A[i+1]==A[i]){
                i++;
            }
        }else if(B[A[i]]==0){
            c++;
            // printf(">> %lld\n",A[i]);
        }

        for(L j=A[i];j<mx;j+=A[i]){
            B[j]=1;
        }
    }
    // printf("\n");
    printf("%lld\n",c);
}

int main()
{
    scanf("%lld",&n);
    for(L i=0;i<n;i++){
        scanf("%lld",&A[i]);
    }
    solve();
    return 0;
}
/// empty() lld I64d push_back() top() pop() insert() upper_bound() lower_bound() memset() max() min() scanf continue


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

int main() {
  int s, w;
  cin >> s >>w;
  
  if (s <= w)
    cout << "unsafe" << endl;
  else
    cout << "safe" << endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    string s;
    cin>>s;
    int n=s.size();
    if(n%2==1){
        cout<<"No"<<endl;
        return 0;
    }
    bool ok=true;
    rep(i,n){
        if(i%2==0){
            if(s[i]!='h') ok=false;
        }
        else{
            if(s[i]!='i') ok=false;
        }
    }

    if(ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline



def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    key = dict()
    if 1 in a:
        key[2] = 1
    for v in [5, 3, 2]:
        if v in a:
            key[5] = v
            break
    if 4 in a:
        key[4] = 4
    for v in [9, 6]:
        if v in a:
            key[6] = v
            break
    if 7 in a:
        key[3] = 7
    if 8 in a:
        key[7] = 8
 
    
    dp = [0]*(n+1)
   
    for i in range(n):
        if i != 0 and dp[i] == 0:
            continue
        for k, v in key.items():
            if i+k <= n:
                dp[i+k] = max(dp[i+k], 10*dp[i]+v)
    print(dp[n])
        
   
    
if __name__ == "__main__":
    main()


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

int main() {
    string s;
    cin >> s;
    int num = s.length()-1;
    long long ans = 0;
    long long total = 0;
    for(int i = 0; i < (1<<num); i++) {
        int start = 0;
        for(int j = 0; j < num; j++) {
            if(i & (1<<j)) {
                ans += stoll(s.substr(start, j+1-start));
                start = j+1;
            }
        }
        ans += stoll(s.substr(start, num+1-start));
        total += ans;
        ans = 0;
    }
    cout << total << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rt "\n"
#define sp " "
#define test(n) cout << "test" << n << endl;
#define fixsp(n) fixed << setprecision(n)
#define defsp(n) defaultfloat << setprecision(n)
#define kyopro ios::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define iikae auto&
#define zenbu(a) a.begin(), a.end()
#define rzenbu(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, N, s) for(ll i{N}; i > s; i--)
using namespace std;using ll = long long;using ld = long double;using P = pair<ll,ll>;
template<typename T> T gcd(T a, T b){return b != 0 ? gcd(b, a % b) : a;}
template<typename T> struct UnionFind{vector<T> par;UnionFind(T n) : par(n, -1){}void init(T n){par.assign(n, -1);}T root(T x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(T x, T y){return root(x) == root(y);}bool merge(T x, T y){x = root(x); y = root(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};

/* ここからコード開始 */

int main(){
  kyopro;
  string L;
  cin >> L;
  ll kake{1}, ans{1};
  rem(i, L.size()-1, -1){
    if(L.at(i) == '1'){
      ans = (kake + 2 + (ans - 1) * 2) % MOD;
    }
    kake *= 3;
    kake %= MOD;
  }
  cout << ans << rt;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
 
int main(){
    u_int a;	// width
    u_int b;	// height
    while(std::cin >> a >> b){
        if(a == 0 && b == 0){
            break;
        }
		
		// initialization
        std::vector<std::vector<u_int>> path(a+1);
        for(u_int i = 0; i < a+1; ++i){
            path[i].resize(b+1, 1);
        }
        
        // construction
        u_int n;
        std::cin >> n;
        for(u_int i = 0; i < n; ++i){
            u_int x, y;
            std::cin >> x >> y;
            path[x][y] = 0;
        }
        
        // out path
        for(u_int i = 0; i < a+1; ++i) path[i][0] = 0;
        for(u_int i = 0; i < b+1; ++i) path[0][i] = 0;
        
        
        for(u_int x = 1; x <= a; ++x){
            for(u_int y = 1; y <= b; ++y){
                if(path[x][y] != 0 && !(x == 1 && y == 1)){
                    path[x][y] = path[x-1][y] + path[x][y-1];
                }
            }
        }
         
        std::cout << path[a][b] << std::endl;
         
    }
    return 0;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl
#define dd(x) cout<<#x<<"="<<x<<" "
#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 repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp(u,v) make_pair(u,v)
#define sz(a) (int)a.size()
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
#define all(a) a.begin(),a.end()
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;

const ll mod = 1000000007;
const int N = 2e5+6;
const int M = 2e6+6;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;

bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }
bool ls(const db &a, const db &b) { return a + eps < b; }
bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }
ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); };
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//inv[1]=1;
//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
int n, k;
vi e[N];
ll dp[N];
void DP(int u, int p) {
	// dd(u);de(p);
	int cnt = 0;
	rep(i, 0, sz(e[u])) {
		int v = e[u][i];
		if(v == p) continue;
		if(p != -1) dp[v]--;
		dp[v]--;
		dp[v] -= cnt; cnt++;
		// dd(v); de(dp[v]);
		dp[v] = max(0ll, dp[v]);
		DP(v, u);
	}
	// dd(u);de(dp[u]);
}
int main() {
	while(~scanf("%d%d",&n,&k)) {
		rep(i, 1, n + 1) e[i].clear();
		rep(i, 1, n + 1) dp[i] = k;
		rep(i, 1, n) {
			int u, v; scanf("%d%d",&u, &v);
			e[u].pb(v); e[v].pb(u);
		}
		DP(1, -1);
		ll ret = 1;
		rep(i, 1, n + 1) ret *= dp[i], ret %= mod;
		printf("%lld\n", ret);
	}
    return 0;
}


Measured memory_bytes: 14720
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int N;
	cin>>N;
	for(int i=0;i<=N;i+=4)
		for(int j=0;j<=N;j+=7)
		{
			if(i+j==N)
			{
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	cout<<"No"<<endl;
	return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    int counter = 0;
    vector<int> a(n);
    a.at(0) = 0;
    for(int i = 1;i < n;i++) {
        if(s.at(i - 1) == 'A' && s.at(i) == 'C') {
            counter++;
        }
        a.at(i) = counter;
    }
    int l,r;
    for(int i = 0;i < q;i++) {
        cin >> l >> r;
        cout << a.at(r - 1) - a.at(l - 1) << endl;
    }
}


Measured memory_bytes: 1408
#include <stdio.h>

int main()
{
  char b;
  scanf("%c",&b);
  if (b == 'A')
  {
    printf("T");
  }
  else if (b == 'T')
    printf("A");
  else if (b == 'C')
  	printf("G");
  else
    printf("C");
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
	int n,b,f,r,v,i,j,k,q,a[4][3][10]={0};
	cin>>n;
	for(q=0;q<n;q++){
		cin>>b>>f>>r>>v;
		a[b-1][f-1][r-1]=a[b-1][f-1][r-1]+v;
	}
	for(i=0;i<4;i++){
		for(j=0;j<3;j++){
			for(k=0;k<10;k++){
				cout<<" "<<a[i][j][k];
			}
			if(k=10){
				cout<<endl;
			}
		}
		if(i!=3){
			cout<<"####################"<<endl;
		}
	}
	return 0;
}



Measured memory_bytes: 3100
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new java.util.Scanner(System.in);
        int n = scan.nextInt();
        int out = 0;
        if(n < 100){
            if(n > 9){
                out = 9;
            }else{
                out = n;
            }
        }else if(n < 10000){
            if(n < 1000){
                out = n - 90;
            }else{
                out = 909;
            }
        }else if(n < 100000){
            out = n - 9090;
        }else{
            out = 90909;
        }
        System.out.println(out);
    }
}

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

void solve(long long N, long long X, std::vector<long long> L){
    ll D;
    ll cnt = 0;
    for(int i = 0; i <= N; ++i){
        if(i == 0) D = 0;
        else{
            D = D + L[i-1];
        }
        if(D <= X) cnt++;
    }
    cout << cnt << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long X;
    scanf("%lld",&X);
    std::vector<long long> L(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&L[i]);
    }
    solve(N, X, std::move(L));
    return 0;
}


Measured memory_bytes: 256
a,b,c,d=map(int,input().split())
A=[]
if (d-b)>0:
  A.append('U'*(d-b))
else:
  A.append('D'*(b-d))

if (c-a)>0:
  A.append('R'*(c-a))
else:
  A.append('L'*(a-c))

if (d-b)>0:
  A.append('D'*(d-b))
else:
  A.append('U'*(b-d))

if (c-a)>0:
  A.append('L'*(c-a+1))
else:
  A.append('R'*(a-c+1))  

if (d-b)>0:
  A.append('U'*(d-b+1))
else:
  A.append('D'*(b-d+1))

if (c-a)>0:
  A.append('R'*(c-a+1))
else:
  A.append('L'*(a-c+1))  
  
if (d-b)>0:
  A.append('D')
else:
  A.append('U')

if (c-a)>0:
  A.append('R')
else:
  A.append('L')
  
if (d-b)>0:
  A.append('D'*(d-b+1))
else:
  A.append('U'*(b-d+1))  
  
if (c-a)>0:
  A.append('L'*(c-a+1))
else:
  A.append('R'*(a-c+1))  
  
if (d-b)>0:
  A.append('U')
else:
  A.append('D')
print(*A,sep='')

Measured memory_bytes: 3188
#ユークリッドの互除法を用いる
N=int(input())
T=[]
for i in range(0,N):
    T.append(int(input()))
def gcd(a,b):
    while b>0 :
        a0=a
        b0=b
        a=b0
        b=a0%b0
    return a
def lcm_base(x,y):
    return (x*y)//gcd(x,y)
def lcm_reduce(T):
    result=T[0]
    for i in range(1,len(T)):
        result=lcm_base(result,T[i])
    return result
print(lcm_reduce(T))

Measured memory_bytes: 3064
part_num = int(input())
day_num, dif_num = map(int, input().split())
eat_day_list = []
[eat_day_list.append(int(input())) for _ in range(part_num)]

num_eat_list = []
for i in range(part_num):
    num_eat_list.append(int((day_num - 1) / eat_day_list[i]) + 1)


print(sum(num_eat_list) + dif_num)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

// MOD確認

int main(){
    ll K;
    cin >> K;
    ll ans = 0;
    FOR(i,1,K+1) FOR(j,1,K+1) FOR(k,1,K+1) ans += __gcd(i,__gcd(j,k));
    cout << ans << endl;
}


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

using namespace std;

int main(void) {
	int a,b,c;
	cin >> a >> b >> c;
	int res = 0;
	for (int i = a; i < b+1; ++i) {
		if (c%i == 0) {
			++res;
		}
	}
	cout << res << endl;
	return 0;
}



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

int main(){
int N,K;
  cin>>N>>K;
  vector<int>A(N), count(N+1, 0); // A[i]>0のため、N+1にする。初期値は0
  for(int i=0; i<N; i++){
   cin>>A[i];
   count[A[i]]++;
  }
  
  int num=0;
  for(int i=0; i<N+1; i++){
   if(count[i]>0){num++;} // 整数の種類の数をnumで記録
  }
  
  sort(count.begin(), count.end()); // count数の小さいもの＝整数の書き換えの最小回数
  
  int ans=0, i=0;
  while(num>K){ // 整数の種類numがnum=Kになるまでループ
   if(count[i]>0){ans+=count[i]; num--;} // 数が少ない整数からansに入れて、
    i++;  // 書き換えたことにする。これをnum=Kになるまで続ける。
  }
  
  cout<<ans; // ansは書き換えた個数
}

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

vector <int> a;
int n;
int min_diff = INT_MAX;

void ans(){
  int s1, s2;
  for(int i = 0; i < n - 1; i++){//goes till n-2
    s1 = a[i];
    s2 = a[n-1] - s1;
    min_diff = min(min_diff, abs(s2-s1));
  }
}

int main(){
  cin >> n;
  a.clear();
  a.resize(n);
  int temp;
  cin >> temp;
  a[0] = temp;
  for(int i = 1; i < n; i++){
    cin >> temp;
    a[i] = a[i-1] + temp;
  }
  ans();
  cout << min_diff << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
const int MAXN = 1005;
const int MAXV = 1000000;
//各試合にidを割り振って、グラフを書く。DAGなら最長路をdfsで検出する
int id[MAXN][MAXN];
int list[MAXN][MAXN];
vector<int> to[MAXV];
int dp[MAXV];

int toId(int i,int j){
  if(i > j) swap(i,j);
  return id[i][j];
}

bool visited[MAXV];
bool calculated[MAXV];
int dfs(int v){
  if(visited[v]){
    if(!calculated[v]) return -1;
    return dp[v];
  }
  visited[v] = true;
  dp[v]=1;
  for(auto &u : to[v]){
    if(dfs(u) == -1) return -1;
    dp[v] = max(dp[v],dfs(u)+1);
  }
  calculated[v] = true;
  return dp[v];
}

int main(){
  int n; cin >> n;
  int a[n][n-1];
  rep(i,n){
    rep(j,n-1){
      cin >> a[i][j];
      a[i][j]--;
    }
  }
  int v = 0;
  rep(i,n){
    rep(j,n){
      if(i<j) id[i][j] = v++;
    }
  }
  rep(i,n){
    rep(j,n-1){
      list[i][j] = toId(i,a[i][j]);
    }
    rep(j,n-2){
      to[list[i][j+1]].push_back(list[i][j]);
    }
  }
  int ans = 0;
  rep(i,v){
    dfs(i);
    if(dfs(i)==-1){
      cout << -1 << endl;
      return 0;
    }
    ans = max(ans,dfs(i));  
  }
  cout << ans << endl;
  return 0;
}
  

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N; cin >> N;
    vector<ll> a(3*N); 
    for(int i=0;i<3*N;i++){
        cin >> a[i];
    }
    sort(a.rbegin(), a.rend());
    ll ans = 0;
    for(int i=1;i<2*N;i+=2){
        ans += a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <stdio.h>
int main()
{

    int i,h,j,k,a,b,d,c;
    scanf("%d%d%d",&a,&b,&c);
i=a*10;
h=b*10;
j=c*10;
    if(i>=h&&i>=j){
        printf("%d\n",i+b+c);
    }
    else if(h>=i&&h>=j){
        printf("%d\n",h+a+c);
    }
    else{
        printf("%d\n",j+a+b);
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <sstream>
#include <stdio.h>
#include<cstdio>

#include<string>
//#include<cmath>
//#include<map>
//#include<cstdlib>
#include<deque>
//#include<queue>
//#include<climits>
#include<cstring>
using namespace std;

const int N_MAX = 1000000;

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

  // table
  int** table = new int*[N];
  for(int i=0; i<N; i++){
    table[i] = new int[N];
    memset(&table[i][0], 0, N*sizeof(table[i][0]));
    // &table[i][0] can be table[i] because it only needs head address.
    
    //[..., [int, int,int], ...]
    // memset(start_addr, 0, delta_arr) fills
    // start_addr to (start_addr + delta_arr) by 0.
    // table[i] refers to the first addr of table[i],
    // for each integer to be filled by 0, size of the element
    // (not table[i]) should be given.
  }
  
  for(int i=0; i<N; i++){
    int row_num, k;
    cin >> row_num >> k;

    row_num--;
    
    for(int j=0; j<k; j++){
      int col_num;
      cin >> col_num;
      col_num--;
      table[row_num][col_num] = 1;
    }
  }

  //print table
  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      cout << table[i][j];
      if(j!=N-1) cout << " ";
      else cout << endl;
    }
  }
  
  for(int i=0; i<N; i++){
    delete[] table[i];
  }
  delete[] table;
  
  return 0;
}



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

void upd(map<int, int>& ans, int key, int val, int max) {
	if (val <= max && (!ans.count(key) || ans[key] > val)) {
		ans[key] = val;
	}
}

bool ok(const vector<int>& a, int div, int k) {
	map<int, int> can;
	for (int x : a) {
		int sub = x%div;
		int add = (div-sub)%div;
		map<int, int> tmp;
		if (can.empty()) {
			upd(tmp, add, add, 2*k);
			upd(tmp, -sub, sub, 2*k);
		} else {
			for (auto& it : can) {
				upd(tmp, it.first + add, it.second + add, 2*k);
				upd(tmp, it.first - sub, it.second + sub, 2*k);
			}
		}
		if (tmp.empty()) {
			return false;
		}
		swap(can, tmp);
	}
	return can.count(0);
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	int sum = 0;
	for (int& ai : a) {
		cin >> ai;
		sum += ai;
	}

	for (int ans = sum; ans > 0; ans--) {
		if (sum%ans == 0 && ok(a, ans, k)) {
			cout << ans << endl;
			return 0;
		}
	}
	assert(false);
	return 0;
}



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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef _DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif



signed main() {

    int N, D, X;
    cin>>N>>D>>X;
    int ans=0;
    rep(i,N){
        int A;
        cin>>A;
        ans+=(D-1)/A+1;
    }
    ans+=X;
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
using System.Collections.Generic;
using System;

public class Hiryo
{
    public int x { get; set; }
    public int y { get; set; }
}
public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var w = int.Parse(line[0]);
        var h = int.Parse(line[1]);
        var p = int.Parse(Console.ReadLine().Trim());
        var hiryos = new List<Hiryo>();
        for (int i = 0; i < p; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            hiryos.Add(new Hiryo { x = int.Parse(line2[0]), y = int.Parse(line2[1])});
        }
        var plant = new int[w,h];
        for (int i = 0; i < h; i++)
        {
            string[] line3 = Console.ReadLine().Trim().Split(' ');
            for (int j = 0; j < w; j++)
                if (line3[j] == "1") plant[j, i] = 0;
                else plant[j, i] = -1;
        }
        foreach (var a in hiryos)
            if (plant[a.x, a.y] != -1) plant[a.x, a.y]++;
        var count = 0;
        foreach (var x in plant)
            if (x != -1) count += x;
        Console.WriteLine(count);
    }
}

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

using namespace std;

#define int long long
#define PB push_back
#define PPB pop_back
typedef pair<int, int> pii;
static const int INF = 1LL<<61;
static const int MAX_N = 100005;
//static const int MOD = 1000000007;

class BIT {
public:
    int bit[MAX_N + 1] = {0}, n;

    int sum(int i) {
        int s = 0;
        while (i) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    void add(int i, int x) {
        while (i <= n) {
            bit[i] += x;
            i += i & -i;
        }
    }
};

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

    BIT bit;
    int q;
    cin >> bit.n >> q;

    for (int i = 0; i < q; ++i) {
        int c, x, y;
        cin >> c >> x >> y;

        if (c) {
            cout << bit.sum(y) - bit.sum(x - 1) << endl;
        } else {
            bit.add(x, y);
        }
    }

    return 0;
}

Measured memory_bytes: 3980
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    long long x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    if(x/d >= k){
        cout << x - k * d << endl;
        return 0;
    }else{
        ll s = x/d;
        if((k - s)%2 == 0) cout << x%d << endl;
        else cout << abs(x%d-d) << endl;
        return 0;
    }
}

Measured memory_bytes: 3676
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
class Program{
    static void Main(){
        int n = int.Parse(Console.ReadLine());
        int[] T = Console.ReadLine().Split(' ')
                                         .Select(val => int.Parse(val))
                                         .ToArray();
        int[] A = Console.ReadLine().Split(' ')
                                         .Select(val => int.Parse(val))
                                         .ToArray();
        long pat = 1;
        for (int i = 0; i < n; i++)
        {
            if(i == 0 || T[i - 1] != T[i]){
                if(T[i] > A[i]) pat = 0;
                else Console.Error.WriteLine("h{0} = {1}", i, T[i]);
            }
            if(i == n - 1 || A[i] != A[i + 1]){
                if(T[i] < A[i]) pat = 0;
                else Console.Error.WriteLine("h{0} = {1}", i, A[i]);
            }
            if(i != 0 && i != n - 1 && T[i - 1] == T[i] && A[i] == A[i + 1]){
                Console.Error.WriteLine("T[{0}] = {1}, A[{0}] = {2}", i, T[i], A[i]);
                pat *= Math.Min(T[i], A[i]);
                pat %= (long)Math.Pow(10, 9) + 7;
            }
            if(pat == 0) break;
        }
        Console.WriteLine(pat);
    }
}


Measured memory_bytes: 26812
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

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

  typedef pair<ll, ll> P;

  vector<P> ab(N);
  rep(i, N) cin >> ab[i].fi >> ab[i].se;

  sort(all(ab));
  rep(i, N) {
    if (K <= ab[i].se) {
      cout << ab[i].fi << endl;
      return 0;
    } else {
      K -= ab[i].se;
    }
  }
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#define mod 1000000007
typedef long long ll;
using namespace std;


#define MAX 100050
ll fac[MAX], finv[MAX], inv[MAX];

void COMinit(){
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i=2;i<MAX;i++){
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

ll COM(int n, int k){
  if(n < k) return 0;
  if(n < 0 || k < 0) return 0;
  return fac[n] * (finv[n-k] * finv[k] % mod) % mod;
}

int main(){
  int n,k; cin >> n >> k;
  vector<ll> A(n);
  for(int i=0;i<n;i++) cin >> A[i];
  sort(A.begin(),A.end());

  COMinit();
  ll ans = 0;

  for(int i=k-1;i<n;i++){
    ans = (ans + COM(i,k-1) * A[i]) % mod;
  }
  
  for(int i=0;i<n-k+1;i++){
    ans = ans - ((COM(n-i-1,k-1) * A[i]) % mod);
  }
  ans = (ans + mod) % mod;

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

Measured memory_bytes: 3328
#include<iostream>
#include<string>
using namespace std;
const long long mod=1e9+7;
const long long ny=5e8+4;
string s[2];
bool used[2][55];
long long n,ans,num;
void doit0(int i)
{
	if (s[1][i]==s[0][i])
	{
		used[0][i]=used[1][i]=1;
		if (i==0) num=0; 
		else if (s[0][i-1]!=s[1][i-1]) num=2;
		else num=1;
	}
	else
	{
		used[0][i]=used[0][i+1]=1;
		if (i==0) num=0;
		else num=1;
	}
}
void doit1(int i)
{
	used[1][i]=used[1][i+1]=1;
	if (i==0) num=1;
	else if (s[1][i-1]==s[1][i-2])
	{
		num=2;
		ans=(ans+ans*ny)%mod;
	}
	else num=2;
}
int main()
{
	cin>>n;
	ans=1;
	for (int i=0;i<=1;i++)
	{
		cin>>s[i];
	}
	for (int i=0;i<n;i++)
	{
		if (!used[0][i]) 
		{
			doit0(i);
			ans=ans*(3-num)%mod;
		}
		if (!used[1][i]) 
		{
			doit1(i);
			ans=ans*(3-num)%mod;	
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
      ll a,b,c;
      cin >> a >> b >> c;
      if(a>=b && a>=c)
      cout << a*10+b+c << endl;
       if(b>a && b>=c)
      cout << b*10+a+c << endl; 
      if(c>a && c>b)
      cout << c*10+b+a << endl;
  }


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define MN 100000 
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int head[MN+5],cnt=0,f[MN+5],d[MN+5],n,rt,ans,g[MN+5];
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
	e[++cnt]=(edge){t,head[f]};head[f]=cnt;++d[f];
	e[++cnt]=(edge){f,head[t]};head[t]=cnt;++d[t];
}
void dfs(int x,int fa)
{
	int num=0,gg=0,num2=0;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa) 
		{
			dfs(e[i].to,x);
			if(f[e[i].to]) f[x]=1,++num2,gg|=g[e[i].to];
			else ++num;	
		}
	if(num>1) ans+=num-1,num2+=num-1,num=1,f[x]=1;
	g[x]=(num2<2&&gg)|(fa&&num);
//	cout<<x-1<<" "<<num<<" "<<num2<<" "<<gg<<" "<<f[x]<<" "<<g[x]<<endl;
}
int main()
{
	n=read();if(n==2)return 0*puts("1");
	for(int i=1;i<n;++i) ins(read()+1,read()+1);
	for(rt=1;d[rt]<2;++rt);dfs(rt,0);
	cout<<ans+g[rt];
	return 0;
}



Measured memory_bytes: 10752
w,h,n=map(int,input().split())
l,r,u,d=0,w,h,0
for i in range(n):
  x,y,a=map(int,input().split())
  if a==1:
    l=max(l,x)
  elif a==2:
    r=min(r,x)
  elif a==3:
    d=max(d,y)
  else:
    u=min(u,y)
if u-d<0 or r-l<0:
  u=d
print((u-d)*(r-l))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()

struct point{
    int x,y;
};

int main(){
    struct point p[9];
    int n;
    cin>>n;
    REP(i,n) cin>>p[i].x>>p[i].y;
    ld sum=0;
    REP(i,n-1){
        FOR(j,i+1,n) sum+=(ld)sqrt((ld)pow((ld)p[i].x-(ld)p[j].x,2)+(ld)pow((ld)p[i].y-(ld)p[j].y,2));
    }
    sum=sum*2.0/(ld)n;
    sum*=pow(10,7);
    sum=round(sum);
    sum/=pow(10,7);
    cout<<fixed << setprecision(10)<<sum<<endl;

}


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

using std::cin;
using std::cout;

struct point {
	double x, y;
	point() = default;
	point(double x, double y) : x(x), y(y) {}
	friend double distance(const point & p1, const point & p2) {
		return sqrt(pow((p1.x - p2.x), 2) + pow((p1.y - p2.y), 2));
	}
};

int main() {
	size_t N;
	cin >> N;
	std::vector<point> points(N);
	for (size_t i = 0; i < N; ++i) {
		cin >> points[i].x >> points[i].y;
	}
	double ** b = new double *[N];
	for (size_t i = 0; i < N; ++i) {
		b[i] = new double[N];
	}
	b[0][1] = distance(points[0], points[1]);
	for (size_t j = 2; j < N; ++j)
		b[0][j] = b[0][j - 1] + distance(points[j - 1], points[j]);
	for (size_t i = 1; i < N; ++i) {
		for (size_t j = i + 1; j < N; ++j) {
			if (i < j - 1) {
				b[i][j] = b[i][j - 1] + distance(points[j - 1], points[j]);
			}
			else if (i == j - 1) {
				double min = b[0][j - 1] + distance(points[0], points[j]);
				for (size_t k = 1; k < i; ++k) {
				 double temp = b[k][j - 1] + distance(points[k],points[j]);
					if (temp < min) {
						min = temp;
					}
				}
				b[i][j] = min;
			}
		}
	}
	size_t i = N - 2;
	cout.precision(10);
	cout << b[i][i + 1] + distance(points[i], points[i + 1]) << std::endl;
	return 0;
}


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

int main(){
    int n;
    string s, c;
    cin >> n >> s;
    c = s;
    int count = 0;
    sort(c.begin(), c.end());
    for(int i=0; i<n; i++){
        if(c.at(i) == 'R'){
            continue;
        }
        if(c.at(i) != s.at(i)){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3920