akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

int main() {
    string s;
    cin>>s;
    replace( s.begin(), s.end(), '1', 'z');
    replace( s.begin(), s.end(), '9', '1');
    replace( s.begin(), s.end(), 'z', '9');
    cout << s;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
const int MD=1e9+7;
vector<int> G[N];
int f[N],ans[N];
int n,a,b;
int quick_pow(int x,int y) {
    int ans=1;
    while(y) {
        if(y&1) ans=1LL*ans*x%MD;
        y>>=1;
        x=1LL*x*x%MD;
    }
    return ans;
}
void dfs(int u,int fa) {
    for(auto v:G[u]) {
        if(v==fa) continue;
        dfs(v,u);
        f[u]+=f[v];
    }
    f[u]++;
}
void cal(int u,int fa) {
    for(auto v:G[u]) {
        if(v==fa) continue;
        ans[v]=1LL*ans[u]*quick_pow(f[v],MD-2)%MD*(n-f[v])%MD;
        cal(v,u);
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,-1);
    ans[1]=1;
    for(int i=1;i<=n;i++) {
        ans[1]=1LL*ans[1]*f[i]%MD;
    }
    cal(1,-1);
    int t=1;
    for(int i=1;i<=n;i++) t=1LL*t*i%MD;
    for(int i=1;i<=n;i++) {
        printf("%d\n",1LL*t*quick_pow(ans[i],MD-2)%MD);
    }
    return 0;
}

Measured memory_bytes: 15604
#include <stdio.h>
 
int main(void){
  int i, x, y;
   
  for(i = 1; i < 10001; i++){
    scanf("%d %d\n", &x, &y);
    if(x == 0 && y == 0)
      break;
    if(x < y)
      printf("%d %d\n", x, y);
    else
      printf("%d %d\n", y, x);
  }
 
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  int a=N, sum=0;
  rep(i ,9) {
    sum += a % 10;
    a /= 10;
    if (a == 0) {break;}
  }
  
  if (N % sum == 0) { cout << "Yes" << endl; }
  else {cout << "No" << endl;}
}

Measured memory_bytes: 256
s = input()
a_left = []
z_right = []
for i in range(len(s)):
    if s[i] == "A" : a_left.append(i)
    
    if s[i] == "Z" : z_right.append(i)

a = min(a_left) 
z = max(z_right) + 1
print("{}".format(z - a))


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

int main() {
  int k;
  int h = -1;
  int A[100];
  int B[100];
  while(1) {
    ++h;
    cin >> k;
    if(k == 0) break;
    int a,b;
    A[h] = 0;
    B[h] = 0;
    for(int c = 0; c < k; ++c) {
      cin >> a >> b;
      if(a > b) {
        A[h] += a + b;
      }else if(a == b) {
        A[h] += a;
        B[h] += b;
      }else if(a < b) {
        B[h] += a + b;
      }
    }
  }
  for(int ho = 0; ho < h; ++ho) {
    cout << A[ho] << " " << B[ho] << endl;
  }
}

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <cctype>
#include <algorithm>
using namespace std;
int main(void){
    char c ;
    cin >> c ;

    if(c == 'a'||c == 'u'||c == 'o'||c == 'e'||c == 'i'){
        cout << "vowel" << endl;
    }else{
        cout << "consonant" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005],ans;
int main()
{
   cin>>n>>k;
   for(int i=1;i<=n;i++) cin>>a[i];
   sort(a+1,a+n+1);
   for(int i=1;i<=k;i++) ans+=a[i];
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<map>
#include<numeric>
#include<queue>
#include<functional>
#include<cassert>
#include<set>
#define rep(a,b) for(int a=0;a<b;++a)
#define REP(a,b,c,d) for(int a=b;a<c;a+=d)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define mod 1000000007
using namespace std;
using ll = long long;
using p_i = pair<int, int>;
int main() {
	int N, P;	cin >> N >> P;
	ll ans;
	bool b = false;
	vector<int> A(N);
	rep(i, N) {
		cin >> A[i];
		if (A[i] % 2 == 1)b = true;
	}
	if (P == 1 && !b)ans = 0;
	else if (!b)ans = pow(2, N);
	else ans = pow(2, N - 1);
	cout << ans << endl;
}

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

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = vals[0];
        var K = vals[1];
        var h = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int count = 0;
        foreach (var hi in h)
        {
            if (hi >= K)
            {
                count++;
            }
        }

        Console.WriteLine(count);
    }
}

Measured memory_bytes: 19040
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

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

Measured memory_bytes: 256
//BISMILLAHIR RAHMANIR RAHIM
                                               //BY THE NAME OF ALLAH
                                               //FAISAL AHAMMED SHAWON
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<set>
#include<map>
#include<iterator>
#include<numeric>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define SQ(a) (a)*(a)
#define pi acos(-1.0)
const int MAX=1000001;
const int MOD=1e9+7;
typedef long long ll;
typedef unsigned long long ull;
ll ara[MAX],n,m;
using namespace std;
void fast()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    else
    gcd(b,a%b);
}
ll lcd(ll a,ll b)
{
    return (a*b)/gcd(a,b);
}

bool f(ll a,ll b)
{
    return a>b;
}
ll max_sum_subarrays(ll ara[],ll n)
{
    ll ans=0,sum=0;
    for(ll k=0;k<n;k++){
        sum=max(ara[k],sum+ara[k]);
        ans=max(ans,sum);
    }
    return ans;
}
ll num_divisors(ll n)
{
    long long cnt=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0 && i*i==n)
            cnt+=1;
        if(n%i==0 && i*i!=n)
                cnt+=2;
    }
    return cnt;
}
ll comb(ll m, ll n)
{
    ll x = max(m-n,n),ans = 1,i=1;
    for(ll k=m;k>=x+1;k--){
        ans*=k;
        ans/=i;
        i++;
    }
    return ans;
}
bool binsearch(ll mid,ll target)
{
   ll collected=0;

   for(ll i=0;i<n;i++)
   {
       if(ara[i]>=mid)
         collected+=(ara[i]-mid);
   }
   if(collected>=target)
    return true;
   else
   return false;

}
void solve()
{
    int n;
    cin>>n;
    vector<pair<int,int>>v(n);
    int a,b;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        v[i].F=a;
        v[i].S=b;
    }
    int c=0,ans=0;
    bool f=0;
    for(int i=0;i<n;i++)
    {

       if(v[i].F==v[i].S){
        c++;
         ans=max(ans,c);
       }
       else
        {
            c=0;
        }

    }
    if(ans>=3)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}
int main()
{
    fast();
    solve();
}


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

using ll=long long;
const ll MOD=1000000007;

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a+b>=c)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
/*   --------------------
    |       LOSER        |
    |     ~NOOBOSS~      |
     --------------------
*/
#include <bits/stdc++.h>
using namespace std;
#define      mxx                 LLONG_MAX
#define      mnn                 LLONG_MIN
#define      Y()                 cout<< "Yes" <<endl
#define      N()                 cout << "No"<<endl
#define      endl                "\n"
#define      max_3(a,b,c)        max(a, max(b,c))
#define      min_3(a,b,c)        min(a, min(b,c))
#define      gcd(a,b)            __gcd(a,b)
#define      lcm(a,b)           (a*b)/gcd(a,b)
#define      loser               return 0
#define      ll                  long long
#define      PI                  acos(-1)
#define      mem(a,v)            memset(a,v,sizeof(a))
#define      SORT(v)             sort(v.begin(),v.end())
#define      REV(v)              reverse(v.begin(),v.end())
#define      B                   begin()
#define      E                   end()
#define      V                   vector
#define      F                   first
#define      S                   second
#define      PSB                 push_back
#define      MP                  make_pair
#define      flash               cout.flush()
#define      InTheNameOfGod      ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll MOD = 998244353;
constexpr ll mod = 1e9  + 7;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*-----*/
#define bug1(a)  cerr<<a<<endl;
#define bug2(a,b)  cerr<<a<<" "<<b<<endl;
#define bug3(a,b,c)  cerr<<a<<" "<<b<<" "<<c<<endl;
/*----*/
const ll N=2e5+5;
vector<ll> adj[N];
ll power(ll n,ll p){if(p==0) return 1;if(p==1)return n;if(p%2)return power(n,p-1)*n;else{ll x=power(n,p/2);return x*x;}}
ll modpow(ll a,ll b,ll m){ll ans=1;while(b){if(b&1)ans=(ans*a)%m;b/=2;a=(a*a)%m;}return ans;}
ll nsum(ll num){return (num*(num+1))/2;}
void edge (ll u,ll v) {adj[u].PSB(v) ;adj[v].PSB(u);}
/*------------------START---------------------*/


/*-----*/
void solve(){
   ll n;
   string s;
   cin>>n;
   V<ll> a(n),b(n);
   for(ll i=0;i<n;i++) cin>>a[i]>>b[i];
   for(ll i=0;i<n-2;i++){
        ll ct=0;
    for(ll j=i;j<i+3;j++){
        if(a[j]==b[j]) ct++;
    }
    if(ct==3) {Y(); return;}
   }
N();

}
/*-----*/
int main(){
   InTheNameOfGod

   ll Test=1;
   //cin>>Test;
   while(Test--){
     solve();
    }
  loser;
}
///////   C O D I N G  I S  L I F E   ///////


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

const int MX = 100005;

int main(){
  int n; cin >> n;
  vector<ll> cnt(MX);
  rep(i,n){
    int a; cin >> a;
    cnt[a]++;
  }
  ll tot = 0;
  rep(i, MX) tot += i*cnt[i];

  int q; cin >> q;
  rep(i,q){
    int b, c; cin >> b >> c;
    tot -= b*cnt[b];
    tot -= c*cnt[c];
    cnt[c] += cnt[b]; cnt[b] = 0;
    tot += b*cnt[b];
    tot += c*cnt[c];
    cout << tot << endl;
  }
  return 0;
}


Measured memory_bytes: 4032
import math

MOD = 10 ** 9 + 7
N, M = map(int, input().split())

if N == M:
    print(2 * math.factorial(N) * math.factorial(M) % MOD)
elif abs(M - N) == 1:
    print(math.factorial(N) * math.factorial(M) % MOD)
else:
    print(0)


Measured memory_bytes: 5180
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<queue>
#include<stack>
#define Max 1000
using namespace std;

vector<pair<int,int>>vec;

bool cmp(pair<int,int>&a,pair<int,int>&b){
	return (a.first<b.first);
}

int main(){

	int n,i,x;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&x);
		vec.push_back(make_pair(x,i));
	}

	sort(vec.begin(),vec.end(),cmp);

	for(i=0;i<n;i++){
		printf("%d ",vec[i].second+1);
	}

	printf("\n");
	return 0;
}

Measured memory_bytes: 1780
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int calc2(int lo, int hi, int k, int[] xs) {
   int ans = 0;
   int x = lo;
   while (x-1 >= 0) {
       ans++;
       x -= k - 1;
   }

   x = hi;
   while (x+1 < xs.length) {
       ans++;
       x += k - 1;
   }

   // writeln(lo, " ", hi, " ans ", ans);
   return ans;
}

int calc(int k, int[] xs) {
   int p = 0;
   for (int i = 0; i < xs.length; i++) {
       if (xs[i] == 1) {
           p = i;
           break;
       }
   }

   int ans = int.max;
   int lo = max(0, p - k + 1);
   int hi = min(xs.length, p + k - 1);
   for (int i = max(0, p - k + 1); i <= p; i++) {
       ans = min(ans, 1 + calc2(i, i + k - 1, k, xs));
   }
   return ans;


}

void main() {
    auto nk = readints;
    int k = nk[1];
    auto xs = readints;

    auto ans = calc(k, xs);
    writeln(ans);
}

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

int main() {
  string A,B;
  cin >> A >> B;
  if (A.size()>B.size()) cout << "GREATER" << endl;
  else if (A.size()<B.size()) cout << "LESS" << endl;
  else {
      for (int i=0; i<A.size(); i++) {
          if (A.at(i)>B.at(i)) {
              cout << "GREATER" << endl;break;
          }
          else if (A.at(i)<B.at(i)) {
              cout << "LESS" << endl;break;
          }
          if (i==A.size()-1) cout << "EQUAL" << endl;
      }
  }
}

Measured memory_bytes: 256
public static class Program
{
  public static void Main(string[] args)
  {
     string[] input = System.Console.ReadLine().Split(' ');
     int a = int.Parse(input[0]);
     int b = int.Parse(input[1]);
     string answer = ((a % 2 == 0) || (b % 2 == 0))
       ? "Even"
       : "Odd";
     System.Console.WriteLine(answer);
  }
}


Measured memory_bytes: 11092
cnt = [0] * 11000

n = int(input())

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            value = x*x + y*y + z*z + x*y + y*z + z*x
            if value <= n:
                cnt[value] += 1

for i in range(1, n+1):
    print(cnt[i])

Measured memory_bytes: 9308
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define rep(i, n) for(int i=0; i<(n); ++i)
#define max  200001

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
    
    int n, a[max];
    long long int sum=0;
    int amax=INT_MIN, mem;
    int dai;
    
    scanf("%d", &n);
    rep(i, n){
        scanf("%d", &a[i]);
        if (i!=0&&a[i-1]>a[i]) {
            dai=a[i-1]-a[i];
            a[i]=a[i-1];
            sum+=dai;
        }
    }
    
    printf("%lld", sum);

    return 0;
}


Measured memory_bytes: 2484
A = [list(map(int, input().split())) for i in range(3)]
N = int(input())
B = [int(input())for i in range(N)]
sheet = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

for i in range(N):
  for j in range(3):
    for k in range(3):
      if B[i] == A[j][k]:
        sheet[j][k] = 1
if sheet[0][0] == 1 and sheet[0][1] == 1 and sheet[0][2] == 1:
  print('Yes')
elif sheet[1][0] == 1 and sheet[1][1] == 1 and sheet[1][2] == 1:
  print('Yes')
elif sheet[2][0] == 1 and sheet[2][1] == 1 and sheet[2][2] == 1:
  print('Yes')
elif sheet[0][0] == 1 and sheet[1][0] == 1 and sheet[2][0] == 1:
  print('Yes')
elif sheet[0][1] == 1 and sheet[1][1] == 1 and sheet[2][1] == 1:
  print('Yes')
elif sheet[0][2] == 1 and sheet[1][2] == 1 and sheet[2][2] == 1:
  print('Yes')
elif sheet[0][0] == 1 and sheet[1][1] == 1 and sheet[2][2] == 1:
  print('Yes')
elif sheet[2][0] == 1 and sheet[1][1] == 1 and sheet[0][2] == 1:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9340
N, M = map(int, input().split())
condition = []
for i in range(M):
    s, c = map(int, input().split())
    condition.append([s,c])

if N > 1:
    start = 10**(N-1)
    end = 10**(N) - 1
else:
    start = 0
    end = 9
    
end_flag = 0
for k in range(start, end+1):
    flag = 1
    for elem in condition:
        if str(k)[elem[0]-1] != str(elem[1]):
            flag = 0
    if flag == 1:
        end_flag = 1
        print(k)
        break
            
if end_flag == 0:
    print(-1)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
char buf[rlen],*ib=buf,*ob=buf;
#define gc() (((ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin)),ib==ob)?-1:*ib++)
inline int read(){
	int ans=0;
	char ch=gc();
	while(!isdigit(ch))ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return ans;
}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long Ull;
inline int Read(char*s){
	int top=0;
	char ch=gc();
	while(!isalpha(ch))ch=gc();
	while(isalpha(ch))s[++top]=ch,ch=gc();
	return top;
}
char s[105];
int main(){
	#ifdef ldxcaicai
	freopen("lx.in","r",stdin);
	#endif
	int len=Read(s),k=read();
	if(s[1]!=s[len]){
		int res=0;
		for(ri l=1,r;l<=len;l=r+1){
			r=l;
			while(r!=len&&s[r+1]==s[r])++r;
			res+=(r-l+1)/2;
		}
		cout<<(ll)res*k;
		return 0;
	}
	bool ff=1;
	for(ri i=2;i<=len;++i)if(s[i]!=s[i-1]){
		ff=0;
		break;
	}
	if(ff){
		cout<<(ll)len*k/2;
		return 0;
	}
	int ct=2,ps1,ps2;
	for(ri i=2;i<=len;++i){
		if(s[i]==s[i-1])++ct;
		else{
			ps1=i;
			break;
		}
	}
	for(ri i=len-1;i;--i){
		if(s[i]==s[i+1])++ct;
		else{
			ps2=i;
			break;
		}
	}
	int res=ct/2;
	for(ri l=ps1,r;l<=ps2;l=r+1){
		r=l;
		while(r!=ps2&&s[r+1]==s[r])++r;
		res+=(r-l+1)/2;
	}
	ll ans=(ll)res*(k-1);
	for(ri l=1,r;l<=len;l=r+1){
		r=l;
		while(r!=len&&s[r+1]==s[r])++r;
		ans+=(r-l+1)/2;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        FastReader in = new FastReader();
        test a=new test();
        a.solve(in,out);
        out.close();
    }
}
class test{
    public void solve(FastReader in, PrintWriter out){
       long  a=in.nextLong();
       long b=in.nextLong();
       long n=in.nextLong();
       if(n<b){
           out.println((a*n)/b);
       }else{
           out.println((a*(b-1))/b);
       }
    }
    public boolean src(int a[],int b[],int k,int l){
        for(int i=0;i<a.length;i++){
            if(a[i]==k && b[i]==l){
                return true;
            }
        }
        return false;
    }
    public int search(ArrayList<Integer> my){
        int max=my.get(0);
        int k=0;
        for(int i=1;i<my.size();i++){
            if(my.get(i)>max){
                max=my.get(i);
                k=i;
            }
        }
        return k;
    }
}

class FastReader{
    BufferedReader br;
    StringTokenizer st;

    public FastReader(){
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next(){
        while(st==null || !st.hasMoreElements()){
            try{
                st=new StringTokenizer(br.readLine());
            }
            catch(IOException e){
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt(){
        return Integer.parseInt(next());
    }

    Long nextLong(){
        return Long.parseLong(next());
    }

    double nextDouble(){
        return Double.parseDouble(next());
    }
    String nextLine(){
        String str="";
        try{
            str=br.readLine();
        }
        catch(IOException e){
            e.printStackTrace();
        }
        return str;
    }
}



Measured memory_bytes: 32644
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Libraries --------------------------------//

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//akari : 1D, yukari : 2D, maki : 3D vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//akane : ascending order, aoi : decending order
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Dubug Functions ---------------------------//
inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}
//------------------------------- Solver ------------------------------------//

void solve()
{
    int n, k;
    cin >> n;
    akari<int> as(n);
    for (int &a : as)
        cin >> a;
    cin >> n;
    while (n--)
    {
        cin >> k;
        cout << distance(as.begin(), lower_bound(as.begin(), as.end(), k)) << ' '
             << distance(as.begin(), upper_bound(as.begin(), as.end(), k)) << endl;
    }
}

int main()
{
    solve();
    return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s; cin >> s;
    deque<char> ds(s.size());
    for(int i=0; i<s.size(); ++i){ds[i] = s[i];}
    int q; cin >> q;
    int rev = 0;
    for(int i=0; i<q; ++i){
        int d; cin >> d;
        if(d==1){rev = 1 - rev;}
        if(d==2){
            int f; char c;
            cin >> f >> c; --f;
            if(rev) f = 1 - f;
            if(f==0){ds.push_front(c);}
            else{ds.push_back(c);}
        }
    }
    if(rev){reverse(ds.begin(), ds.end());}
    for(auto c: ds) cout << c;
    cout << endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { cout << p.first << ' ' << p.second; return os; }

void solve() {
  int n, t; cin >> n >> t;
  vi32 a(n); cin >> a;
  int ans = 0;
  int mi = a[0], ma = 0;
  reps(i, n - 1) {
    if (mi > a[i]) mi = a[i];
    else {
      if (ma == a[i] - mi) ans++;
      else if (ma < a[i] - mi) ma = a[i] - mi, ans = 1;
    }
  }
  cout << ans << '\n';
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int c11, c12, c13, c21, c22, c23, c31, c32, c33;
	cin >> c11 >> c12 >> c13 >> c21 >> c22 >> c23 >> c31 >> c32 >> c33;
	for(int a1=0; a1<=c11; a1++){
		int b1=c11-a1;
		for(int a2=0; a2<=c21; a2++){
			int b2=c22-a2;
			for(int a3=0; a3<=c31; a3++){
				int b3=c33-a3;
				if(a1+b2==c12 && a1+b3==c13 && a2+b1==c21 && a2+b3==c23 && a3+b1==c31 && a3+b2==c32){
					cout << "Yes\n";
					return 0;
				}
			}
		}
	}
	cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,vis[1000],l=0,r=0;
char str[1000];
stack<pair<int,char>> st;
int main()
{
    memset(vis,0,sizeof(vis));
    scanf("%d",&n);
    scanf("%s",str);
    for(int i=0;i<n;i++)
    {
        if(str[i]=='(')
        {
            st.push(make_pair(i,str[i]));
        }else if(str[i]==')')
        {
            if(!st.empty())
            {
                pair<int,char> top=st.top();st.pop();
                vis[top.first]=1;vis[i]=1;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            if(str[i]=='(')r++;
            else l++;
        }
    }
    for(int i=1;i<=l;i++)printf("(");
    for(int i=0;i<n;i++)printf("%c",str[i]);
    for(int i=1;i<=r;i++)printf(")");
    printf("\n");
    return 0;
}


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

using namespace std;

int main() {
    int n;cin>>n;
    int a[n+5]; for(int i=0;i<n;i++)    cin>>a[i];
    int b[n+5]; for(int i=0;i<n;i++)    cin>>b[i];
    int c[n+5]; for(int i=0;i<n-1;i++)  cin>>c[i];
    
    int sat = 0;
    
    for(int i=0;i<n;++i){
        
        if(i==0)
        { 
            sat = sat + b[a[i]-1];
            continue;
        }
        
        if( a[i] == (a[i-1]+1) ){
            sat = sat + b[a[i]-1] + c[a[i]-1-1];
        }
        else
            sat = sat + b[a[i]-1] ;
        
    }
    
    cout<<sat;
    
  return 0;      
}

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

// 基本テンプレート
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// 型
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// 定数
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion


int calc(int i, vi v) {
    int res = 0;
    repi(j,i) {
        res += v[j];
    }

    return res;
}

int main()
{
    ll n;
    cin >> n;
    vector<ll> A(n);
    rep(i,n) cin >> A[i];
    sort(A);

    ll ans = A.size();
    ll tmp = 0;
    ll cnt = 0;

    rep(i,A.size()-1) {
        tmp += A[i];
        cnt++;
        if(tmp*2<A[i+1]) {
            ans -= cnt;
            cnt = 0;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
bool used[2][100][100];
string memo[2][100][100];
bool used2[2][100][100];
string memo2[2][100][100];
string dfs(int,int,int);
string dfs2(int,int,int);

string nine(string s){
  for(int i=0;i<(int)s.size();i++)
    if(s[i]=='?') s[i]='9';
  return s;
}
bool check(string s){
  if(s=="!") return 0;
  if(s.size()==1) return 1;
  return s[0]!='0';
}
string comp(string a,string b){
  if(!check(a)&&!check(b)) return "!";
  if(!check(a)) return b;
  if(!check(b)) return a;
  if(a.size()>b.size()) return a;
  if(b.size()>a.size()) return b;
  return max(a,b);
}
string dfs(int l,int r,int f){
  if(used[f][l][r]) return memo[f][l][r];
  used[f][l][r]=1;
  string& res=memo[f][l][r];
  res="!";
  {
    //all digit
    bool ff=1;
    for(int i=l;i<r;i++)
      ff&=(isdigit(s[i])||s[i]=='?');
    if(ff)
      res=comp(res,nine(s.substr(l,r-l)));
  }
  if(l+1<r&&(s[l+1]=='?'||s[l+1]=='(')){
    if(s[r-1]=='?'||s[r-1]==')'){
      if(s[l]=='?'||s[l]=='L'){
	res=comp(res,dfs2(l+2,r-1,0));
      }
      if(s[l]=='?'||s[l]=='R'){
	res=comp(res,dfs2(l+2,r-1,1));
      }
    }
  }
  return res;
}
string dfs2(int l,int r,int f){
  if(used2[f][l][r]) return memo2[f][l][r];
  used2[f][l][r]=1;
  string& res=memo2[f][l][r];
  res="!";
  for(int i=l+1;i<r-1;i++){
    if(s[i]!='?'&&s[i]!=',') continue;
    string a=dfs(l,i,0);
    string b=dfs(i+1,r,0);
    if(check(a)==0||check(b)==0) continue;
    if(f) res=comp(res,b);
    else res=comp(res,a);
  }
  return res;
}
    
signed main(){
  cin>>s;
  string ans=dfs(0,s.length(),0);
  cout<<(ans!="!"?ans:"invalid")<<endl;
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <cmath>
#include <vector>
#include <array>
#include <algorithm>
#include <functional>

using namespace std;


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

	vector<bool> result(n);

	array<int, 3> triangle;
	for(int i = 0; i < n; i++){
		cin >> triangle[0] >> triangle[1] >> triangle[2];

		sort(begin(triangle), end(triangle), greater<int>());

		const auto square = bind(pow<int, int>, placeholders::_1, 2);
		result[i] = 
			square(triangle[0]) == square(triangle[1]) + square(triangle[2]);
	}

	for(const bool& b : result){
		cout << (b ? "YES" : "NO") << endl;;
	}

	return 0;
}

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

using namespace std;

int main() {
	int n,k;
	cin >> n >> k;
	int arr[n];
	vector<int> dp(n,INT_MAX);
	int c=0;
	for(int i=0;i<n;i++) {
		cin>>arr[i];
	}
	dp[0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<i+k+1;j++)
		{
			if(j<n)
			{
				dp[j]=min(abs(arr[i]-arr[j])+dp[i],dp[j]);
			}
		}
	}
	cout<<dp[n-1]<<endl;

return 0;
}

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

typedef long long ll;
#define mod 1000000007

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

void solve() {
    int a, b;
    cin>>a>>b;
    if(b%a == 0){
        cout<<a+b;
    }
    else{
        cout<<b-a;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    // pre();
    while (t--)
        solve();

    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define rvc(i,S) for(int i=0;i<(int)S.size();++i)
#define fore(i,x) for(int i = head[x] ; i ; i = e[i].next)
#define mp make_pair
#define pb push_back
#define maxn 200005
#define ll long long 
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
struct Dish
{ int A,B;
}dish[maxn];
bool cmp(Dish x,Dish y)
{return x.A+x.B>y.A+y.B;}
int n;
int main()
{  cin>>n;
   rep(i,1,n)  scanf("%d%d",&dish[i].A,&dish[i].B);
  sort(dish+1,dish+n+1,cmp);
  ll suma=0,sumb=0;
  rep(i,1,n)
  {if(i%2) suma+=dish[i].A;
   else    sumb+=dish[i].B;
  }
  cout<<suma-sumb;
return 0;	
}

Measured memory_bytes: 1024
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long a=0;
		boolean warikire = false;

		for(int i=2; i<=Math.sqrt(n); i++){
			if( n%i == 0 ){
				a = i;
				warikire = true;
			}
		}

		if(warikire){
			System.out.println( keta(n/a) );
		}else{
			System.out.println( keta(n) );
		}
		return;
	}

	public static int keta( long a ){
		int ans = 1;
		while( a/10 != 0 ){
			a /= 10;
			ans++;
		}
		return ans;
	}
}

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

int n, m, q;
long long ans = 0, tmp;
vector<int> a,b,c,d;

void dfs(vector<int> &A){
    if(A.size() == n){
        tmp = 0;
        for(int i = 0; i < q; i++){
            if(A.at(b.at(i)) - A.at(a.at(i)) == c.at(i)) tmp += d.at(i);
        }
        ans = max(ans, tmp);
        return;
    }
    int prev_A = (A.empty() ? 1: A.back());
    for(int j = prev_A; j <= m; j++){
        A.push_back(j);
        dfs(A);
        A.pop_back();
    }
}


int main(){
    cin >> n >> m >> q;
    a.resize(q); b.resize(q); c.resize(q); d.resize(q);
    for(int i = 0; i < q; i++){
        cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
        a.at(i)--; b.at(i)--;
    }
    vector<int> A;
    dfs(A);
    cout << ans << endl;
}

Measured memory_bytes: 3600
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>
#include <numeric>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
map<int, int> mp;
map<int, int>mm;
#define ll long long
#define ld long double
#define PI 3.14159265358979l

int gcd(int a, int b) {
	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}
	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}


int main() {
	string s;
	cin >> s;
	int c0 = 0, c1 = 0;
	rep(i, s.size()) {
		if (s[i] == '0')c0++;
		else c1++;
	}
	cout << 2 * min(c0, c1) << endl;
}

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

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	/*
	"iostream 遅い"などと検索すると、cin.tie(0); ios::sync_with_stdio(false);の2つの記述を加えると速くなる、という情報が見つかります。
	これはそれぞれ、cinとcoutの同期を切るもの、iostreamとstdioの同期を切るものです
	https://qiita.com/blackcurrant/items/312ea2471900132fbd6a
	*/

	// https://atcoder.jp/contests/abc122/tasks/abc122_a を解くわよ！
	//はい！
	// ちゃんとコメントにしなさい！

		//笑った
	// AtCoder 星には四種類の塩基 A, C, G, T が存在し、A と T、C と G がそれぞれ対になります。
	//文字 b が入力されます。これは A,  C, G, T のいずれかです。塩基 b と対になる塩基を表す文字を出力するプログラムを書いてください。

	// 問題をコピペしてあげたわよ！ありがたく思いなさい！

	// ここに入力をかく
	// cin.tie()
	char b;
	cin >> b;

	// ↑ 入力部分書いてくれますこと？
	// 入力部分書き終わりました！！



	// ここで答えをけいさんする
	char ans;

	// 問題はA と T、C と G が対ってことらしいね！
	// そうですことよ
	// はやく解いていただけます？

	// これってA->T, C->Gだけでいいのでしょうか?
	// T->A必要?
	// 対ってことは対ってことでしょう
	// つまり必要ってことですわ。
	//  ほんとだ！入力例2がG->Cになってますね。。
	
	//愚直にやるなら
	if (b == 'A') {
		ans = 'T';
	}
	else if (b == 'T') {
		ans = 'A';
	}
	else if (b == 'C') {
		ans = 'G';
	}
	else if (b == 'G') {
		ans = 'C';
	}
	// 醜いプログラムですこと
	// では、お嬢様はこの問題をどのように解くのですか

	// map!!!!!!!
	// ここでしゅつりょく

	//std::map<char, char> m = { {'A', 'T'}, {'T', 'A'}, {'C', 'G'}, {'G', 'C'} };
	//ans = m[b];
	// すまーと！！
	cout << ans << endl;
	// OK
	// OK!
	return 0;
}

Measured memory_bytes: 256
n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

x = sorted(x)
y = sorted(y)

if x[-1] < y[0] and X < x[-1] and y[0] <= Y:
    print("No War")
else:
    print("War")

Measured memory_bytes: 9128
a, b = gets.chomp.split(" ").map(&:to_i)

if a == b then
  puts a + b
end

if a - b == 1 || b - a == 1 then
  puts a + b
end

if a - b >= 2 then
  puts a + (a - 1)
elsif b - a >= 2 then
  puts b + (b - 1)
end

Measured memory_bytes: 1788
b, w = map(int, input().split())
MOD = 10 ** 9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

two_pow = [1]
for i in range(b+w+1):
	two_pow.append((two_pow[-1] * 500000004) % MOD)

ans = 500000004
print(ans)
for i in range(1, b+w):
	if i-1 >= b-1:
		ans -= comb(i-1, b-1) * two_pow[i+1]
	if i-w >= 0:
		ans += comb(i-1, i-w) * two_pow[i+1]
	ans %= MOD
	print(ans)

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

int main(){
    ll h,n;
    cin>>h>>n;
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        ll t;cin>>t;sum+=t;
    }
    if(sum>=h)cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 256
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a,b,c,k = MAP()

if(k<=a):
    print(k)
else:
    temp = k-a
    if(temp<=b):
        print(a)
    else:
        print(a-(k-a-b))

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll s = 0;
    sort(a.begin(), a.end());
    for (int i = 0; i < k; i++) s += a[i];
    cout << s << '\n';
    return 0;
}


Measured memory_bytes: 3652
using System;

class Program{
    public static void Main(){
        var n=int.Parse(Console.ReadLine());
        var r0=int.Parse(Console.ReadLine());
        var r1=int.Parse(Console.ReadLine());
        var min=Math.Min(r0, r1);
        var result=r1-r0;
        for(var i=2; i<n; i++){
            var r=int.Parse(Console.ReadLine());
            if(r-min>result){
                result=r-min;
            }
            if(r<min){
                min=r;
            }
        }
        Console.WriteLine(result);
    }
}

Measured memory_bytes: 9296
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define oo 1L<<60;
 
int N;
int happiness [100005][3];
ll memo [100005][3];
 
ll feliz(int n, int act){
	if(!n) return memo[n][act] = happiness[n][act];
	if(memo[n][act]) return memo[n][act];
	return memo[n][act] = happiness[n][act]+max(feliz(n-1, (act+1)%3),
	                                            feliz(n-1, (act+2)%3));
}
 
int main() {
	cin>>N;
	for(int i = 0; i<N;i++)
		cin>>happiness[i][0]>>happiness[i][1]>>happiness[i][2];
	ll resp = max(feliz(N-1, 0), max(feliz(N-1, 1), feliz(N-1,2)));
	cout<< resp<<endl;
	return 0;
}

Measured memory_bytes: 11836
#include <bits/stdc++.h>
#define IOS                                                                    \
  ios::sync_with_stdio(0);                                                     \
  cin.tie(0);                                                                  \
  cout.tie(0)
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
ll bpow(ll b, ll p, ll m = 1000000007LL) {
  ll rt = 1;
  for (; p; p >>= 1, b = b * b % m)
    if (p & 1)
      rt = rt * b % m;
  return rt;
}
int main() {
  IOS;
  int n;
  ll d;
  cin >> n >> d;
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    ll x, y;
    cin >> x >> y;
    if (x * x + y * y <= d * d)
      cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3640
#include <iostream>
#include<bits/stdc++.h>
#define INF 10000000000
using namespace std;
int a[200005];
int main()
{
    int n;
    scanf("%d",&n);

    long long sum=0;
    long long  x=0,y=0;
    long long ans=INF;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];

    }

    for(int i=1;i<n;i++){
        x+=a[i];
        y=sum-x;
      
        ans=min(ans,abs(x-y));
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 1024
def solve(n, m, grid):
    dp = [[0] * (m+1) for _ in range(n+1)]
    dp[1][1] = 1
    mod = int(1e9+7)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if grid[i-1][j-1] == '#' or i == 1 and j == 1:
                continue
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            dp[i][j] %= mod

    return dp[-1][-1]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    grid = [input() for _ in range(n)]
    print(solve(n, m, grid))


if __name__ == '__main__':
    main()


Measured memory_bytes: 51568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10,M=1e5+10,mod=998244353,G=3;
 
int n;
int a[N],b[N],fac[N],finv[N],two[N];
 
 
ll A[N],B[N],inv,tong[M];
int R[N];
int power(int x,int n)
{
	int res=1;
	for(;n;n>>=1,x=1ll*x*x%mod)
	if(n&1)res=1ll*res*x%mod;
	return res;
}
vector <int> colors[N<<1];
struct cmp{
	bool operator ()(int a,int b){
		return colors[a].size()>colors[b].size();
	}
};
priority_queue <int,vector<int>,cmp> heap;
void NTT(ll a[],int n,int re){
	for (int i=0;i<n;i++)
		if (i<R[i])
			swap(a[i],a[R[i]]);
    for(int i=2;i<=n;i<<=1)
    {
        ll mid=i>>1;
        ll wn=power(G,(mod-1)/i);
        if(re) wn=power(wn,(mod-2));
        for(int j=0;j<n;j+=i)
        {
            ll w=1;
            for(int k=0;k<mid;k++)
            {
                ll temp1=a[j+k];
                ll temp2=a[j+k+mid]*w%mod;
                a[j+k]=(temp1+temp2)%mod;
                a[j+k+mid]=(temp1-temp2);
				a[j+k+mid]=(a[j+k+mid]%mod+mod)%mod;
                w=w*wn%mod;
            }
        }
    }
    if(re){
		for(int i=0;i<n;i++)
       	 	a[i]=(a[i]*inv)%mod;
    }
}
void NTT_times(vector <int> &a,vector <int> &b,vector <int> &c){
	int n,d,as=a.size(),bs=b.size();
	for (int i=0;i<as;i++)
		A[i]=a[i];
	for (int i=0;i<bs;i++)
		B[i]=b[i];
	for (n=1,d=0;n<as+bs-1;n<<=1,d++);
	inv=power(n,mod-2);
	for (int i=0;i<n;i++){
		R[i]=(R[i>>1]>>1)|((i&1)<<(d-1));
	}
	for (int i=as;i<n;i++)
		A[i]=0;
	for (int i=bs;i<n;i++)
		B[i]=0;
	NTT(A,n,0),NTT(B,n,0);
	for (int i=0;i<n;i++)
		A[i]=A[i]*B[i]%mod;
	NTT(A,n,1);
	c.clear();
	for (int i=0;i<=as+bs-2;i++)
		c.push_back(A[i]%mod);
}
void init()
{
	fac[0]=fac[1]=finv[0]=1;
	two[0]=1;two[1]=(mod+1)/2;
	for(int i=2;i<N;++i)
	{
		fac[i]=1ll*fac[i-1]*i%mod;
		two[i]=1ll*two[i-1]*two[1]%mod;	
	}
	finv[N-1]=power(fac[N-1],mod-2);
	for(int i=N-2;i>=1;--i)
	finv[i]=1ll*finv[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
	if(m<0||n<m)return 0;
	return 1ll*fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int cal(int x){
	return 1ll*fac[2*x]*two[x]%mod*finv[x]%mod;
}
int main(){
	init();
	scanf("%d",&n);
	int mx=0;
	for(int i=1;i<=2*n;++i){
		int v;
		scanf("%d",&v);
		mx=max(mx,v);
		tong[v]++;
	}
	int sz=0;
	for(int i=1;i<=mx;i++){
		if(tong[i]<2)continue;
		colors[++sz].clear();
		int up=tong[i]/2;
		colors[sz].push_back(1);
		int now=1,left=tong[i],v;
		for(int j=1;j<=up;++j){
			now=1ll*now*C(left,2)%mod;
			v=1ll*now*finv[j]%mod;
			colors[sz].push_back(v);
			left-=2;
		}
		heap.push(sz);
	}
	while (heap.size()>=2){
		int x=heap.top();
		heap.pop();
		int y=heap.top();
		heap.pop();
		NTT_times(colors[x],colors[y],colors[++sz]);
		colors[x].clear(),colors[y].clear();
		heap.push(sz);
	}
	ll ans=cal(n);
	for(int i=1;i<colors[sz].size();++i){
		ll v=1ll*colors[sz][i]*cal(n-i)%mod;
		if(i&1){
			ans=(ans-v+mod)%mod;
		}
		else{
			ans=(ans+v)%mod;
		}
	}

	printf("%lld",ans);
	return 0;
}

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N;
	cin>>N;
	cout<<1LL*N*(N-1)/2<<'\n';
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] a = new int[N - 1];
    int[] b = new int[N - 1];
    for (int i = 0; i < N - 1; i++) {
      a[i] = sc.nextInt();
      b[i] = sc.nextInt();
    }
    sc.close();

    @SuppressWarnings("unchecked")
    List<int[]>[] g = new List[N + 1];
    g[0] = Collections.emptyList();
    for (int i = 0; i < N - 1; i++) {
      if (g[a[i]] == null) g[a[i]] = new ArrayList<>();
      if (g[b[i]] == null) g[b[i]] = new ArrayList<>();
      g[a[i]].add(new int[] {b[i], i});
      g[b[i]].add(new int[] {a[i], i});
    }
    int K = 0;
    for (List<int[]> e : g) K = Integer.max(K, e.size());

    int[] c = new int[N - 1];
    Deque<int[]> q = new ArrayDeque<>();
    q.addLast(new int[] {1, -1});
    while (!q.isEmpty()) {
      int[] n = q.pollFirst();
      int cno = n[0];
      int pid = n[1];

      int ec = 1;
      List<int[]> es = g[cno];
      for (int[] e : es) {
        int dno = e[0];
        int did = e[1];
        if (did == pid) continue;

        if (-1 < pid && ec == c[pid]) ec++;
        c[did] = ec++;
        q.addLast(new int[] {dno, did});
      }
    }
    StringBuffer buf = new StringBuffer();
    for (int i : c) buf.append(i).append(System.lineSeparator());

    System.out.println(K);
    System.out.println(buf);
  }
}

Measured memory_bytes: 101648