akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define INF (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f

ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }

return ans;
}






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

ll n;cin>>n;
vl a(n);

map<ll,ll>m;

rep(i,0,n)
{
cin>>a[i];
m[a[i]]++;
m[a[i]-1]++;
m[a[i]+1]++;

}
ll ans=0;

for(auto x:m)ans=max(ans,x.second);

  cout<<ans<<"\n";



return 0;

}

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

int const md = 200003;
int id[md], rv[md];
vector<int> fr(md - 1);

typedef complex<double> unr;
double const pi = acos(-1.0);
int ps = 2;
vector<unr> w { unr(0, 0), unr(1, 0) };

void fftpre(int n){
	if (ps >= n)return;
	w.resize(n);
	while (ps < n){
		double th = pi / ps;
		f(i, ps, ps << 1){
			double cth = th * (i - ps);
			w[i] = unr(cos(cth), sin(cth));
		}
		ps <<= 1;
	}
}

void fft(vector<unr> &v, bool inv = false){
	int n = v.size(), j = 0;
	fftpre(n);
	f(i, 1, n){
		int z = n >> 1;
		while (j & z)j ^= z, z >>= 1;
		j ^= z;
		if (i < j)swap(v[i], v[j]);
	}
	for (int m = 1; m < n; m <<= 1)for (int i = 0; i < n; i += m << 1)f(k, 0, m){
		unr a = v[i + k], b = (inv ? conj(w[m + k]) : w[m + k]) * v[i + k + m];
		v[i + k] = a + b;
		v[i + k + m] = a - b;
	}
	if (inv)f(i, 0, n)v[i] /= n;
}

vector<ll> ml(vector<int> const &a, vector<int> const &b){
	int m = a.size() + b.size() - 1, n = 1;
	while (n < m)n <<= 1;
	vector<unr> v1(n), v2(n);
	f(i, 0, a.size())v1[i].real(a[i]);
	f(i, 0, b.size())v1[i].imag(b[i]);
	fft(v1);
	f(i, 0, n){
		unr x = v1[i], y = conj(v1[i ? n - i : i]);
		v2[i] = (x + y) * (x - y) * unr(0, -0.25);
	}
	fft(v2, true);
	vector<ll> an(m);
	f(i, 0, m)an[i] = v2[i].real() + 0.5;
	return an;
}

int main(){
	int x = 1, c = 0;
	do{
		id[x] = c;
		rv[c] = x;
		++c;
		x = 2 * x % md;
	}while (x != 1);
	
	int n;
	scanf("%d", &n);
	f(i, 0, n){
		int t;
		scanf("%d", &t);
		if (t)++fr[id[t]];
	}
	
	vector<ll> z = ml(fr, fr);
	ll an = 0;
	f(i, 0, z.size()){
		int j = i >= md - 1 ? i - md + 1 : i;
		an += rv[j] * z[i];
	}
	f(i, 0, fr.size())an -= rv[i * 2 % (md - 1)] * (ll)fr[i];
	printf("%lld\n", an >> 1);
}

Measured memory_bytes: 33692
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int flag=0;
    string s;
    cin>>s;
    for(int i=0; i<s.size(); i=i+2)
    {
        if(s[i]!='h'||s[i+1]!='i')
        {
            flag=1;
            break;
        }
    }
    if(flag)
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        System.out.println(c + " " + a + " " + b);
        sc.close();
    }
}

Measured memory_bytes: 21972
#include <iostream>

using namespace std;

int		factorial(int N)
{
	int i = 1;
	int sum = 1;
	if (N < 0)
		return 0;
	while (i <= N)
		sum *= i++;
	return (sum);
}

int		main()
{
	int N;
	int P[9];
	int Q[9];
	int i,j;
	int p,q;
	int ans1 = 1,ans2 = 1;

	cin >> N;
	for (i = 1; i <= N; i++)
		cin >> P[i];
	for (i = 1; i <= N; i++)
		cin >> Q[i];
	i = 1;
	while (i < N)
	{
		j = 1;
		p = 0;
		q = 0;
		while (j < i)
		{
			if (P[j] < P[i])
				p++;
			if (Q[j] < Q[i])
				q++;
			j++;
		}
		ans1 += factorial(N - i) * (P[i] - p - 1);
		ans2 += factorial(N - i) * (Q[i] - q - 1);
		i++;
	}
	// printf("%d\n%d\n", ans1,ans2);
	printf("%d\n",abs(ans1 - ans2));
	return (0);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C;
  cin >> A >> B >> C;
  vector<int> vecT(3);
  vecT.at(0) = A;
  vecT.at(1) = B;
  vecT.at(2) = C;
  sort(vecT.begin(), vecT.end());
  cout << vecT.at(2)*10+vecT.at(1)+vecT.at(0) << endl;
}

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

int main(){
  int R, G, B, N;
  cin >> R >> G >> B >> N;
  int cnt=0;
  for(int i=0; i<=N/R; i++){
    for(int j=0; j<=N/G; j++){
      int dif=N-R*i-G*j;
      if(dif%B==0 && dif>=0) cnt++; 
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a,b,i,j,x,y,sum;
    while(scanf("%d",&n)==1)
    {
        m = 7;
        sum = 0;
        if(n%2==0||n%5==0)
        	printf("-1\n");
        else
        {
            while(m%n!=0)
            {
                sum++;
                m = m*10+7;
                m = m%n;
            }
            printf("%d\n",sum+1);
        }
    }
return 0;
}

Measured memory_bytes: 3812
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld long double
#define mod 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
ll p[200005],b[200005]={0};
vector<vector<ll> > a(200005);
void dfs(ll ver)
{
	for(ll i=0;i<a[ver].size();i++)
	{
		if(p[a[ver][i]]==-1)
		{
			p[a[ver][i]]=p[ver]+b[a[ver][i]];
			dfs(a[ver][i]);
		}
	}
}
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,q,i,j,x,y;
	cin>>n>>q;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
	}
	while(q--)
	{
		cin>>x>>y;
		b[x]+=y;
	}
	for(i=1;i<=n;i++)
	{
		p[i]=-1;
	}
	p[1]=b[1];
	dfs(1);
	for(i=1;i<=n;i++)
	{
		cout<<p[i]<<" ";
	}
	return 0;
}

Measured memory_bytes: 22528
#include <iostream>
using namespace std;
int main() {
	int N;
	int i;
	int a;
	int ans = 0;
	int n[100000];
	cin >> N;
	for (i = 0; i < 100000; i++) {
		n[i] = 0;
	}
	for (i = 0; i < N; i++) {
		cin >> a;
		if (n[a] == 0) {
			n[a] = 1;
		}
		else {
			ans++;
		}
		
	}
	if (ans % 2 == 0)
		cout << N - ans << endl;
	else cout << N - ans - 1 << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep2(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i,n) rep2(i,0,n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using ll = long long;
template <typename T>
T sq(T x){
  return x * x;
}

signed main (){
  int A,B,C;
  cin >> A >> B >> C;
  if(A<=C&&C<=B){

cout << "Yes" << endl;
  }else{
cout << "No" << endl;
  }
    return 0;
}


Measured memory_bytes: 256
/*
     * Codeforces Contest
     * Au: Lost_Deviation
     */
    #ifndef open_dbg_func
    #define err(args...)
    #endif
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    static auto XxXOxO = []() {
        std::ios::sync_with_stdio(false); // turn off sync
        cin.tie(nullptr);                 // untie in/out streams
        return 0;
    }();
    struct T {
        int x, y;
    };
    int cmp(const T &a, const T &b) {
        if (a.x != b.x)
            return (a.x < b.x);
        else
            return (a.y < b.y);
    }
    int a[32] = {1, 1, 1, 2, 1, 2, 1, 5,  2, 2, 1, 5, 1, 2, 1, 14,
                 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int main(void) {
        ll h, w;
        cin >> h >> w;
        if (h>1&&w>1)
        cout << (h * w + 1) / 2;
      else cout << 1;
    }

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define vi vector<int>
#define vvll vector<ll>
#define vll(a) vector<ll> a(MAXN)
#define pb push_back
#define fo(a) for(auto&a1:(a))
#define fd(a,b) for(int i=(a);i>=(b);i--)
#define fk(a,b) for(int k=(a);k<(b);k++)
#define fj(a,b) for(int j=(a);j<(b);j++)
#define f(a,b) for(ll i=(a);i<(b);i++)
#define forni(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define fdk(a,b) for(int k=(a);k>=(b);k--)
#define fdj(a,b) for(int j=(a);j>=(b);j--)
#define ri(n) scanf("%d",&(n));
#define rll(n) scanf("%lld",&(n));
#define T(t) int t;scanf("%d",&(t));while((t)--)
#define MAXN 10000001
#define MAXN2 10000005
#define pll pair<ll,ll>
#define PI 3.14159265
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll mod=1000000007;
int main()
{
    ll n;
    cin>>n;
    ll a[n][3];
    f(0,n)
    cin>>a[i][0]>>a[i][1]>>a[i][2];
    f(1,n)
    {
        a[i][0]+=max(a[i-1][1],a[i-1][2]);
        a[i][1]+=max(a[i-1][0],a[i-1][2]);
        a[i][2]+=max(a[i-1][0],a[i-1][1]);
    }
    cout<<max({a[n-1][0],a[n-1][1],a[n-1][2]})<<"\n";
    return 0;
}


Measured memory_bytes: 5996
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPD(i,n) for(int i=(n)-1;i>=0;--i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define TLE() cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms.\n";
const ll MOD = 1E9+7;
const ll IINF = 1E18;
const int INF = 1e9;
const double EPS = 1E-9;
const double PI = atan(1.0) * 4.0;
template<class T> T getbit(T s, int i) {return s>>i&1;}
template<class T> void flipbit(T& s, int i) {s^=(1LL<<i);}
constexpr int cntbit(ll x) {return __builtin_popcountll(x);}
constexpr int lg2(ll x) {return __lg(x);} // return int(log2(x))
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
ll fpow(ll a,ll p){ll res=1LL;while(p){if(p&1LL) res=res*a%MOD;a=a*a%MOD;p>>=1LL;} return res;}

int q;
ll summax,summin,b;
priority_queue<ll> heapmax;
priority_queue<ll, vector<ll>, greater<ll>> heapmin;
 
void clearHeaps() {
    summax = summin = 0LL;
    while (!heapmax.empty()) heapmax.pop();
    while (!heapmin.empty()) heapmin.pop();
}
 
int getMedian(ll x) {
    if (heapmax.empty() && heapmin.empty()) {
        heapmax.push(x);
        summax += x;
        return x;
    }
    ll median = heapmax.size() >= heapmin.size() ? heapmax.top() : heapmin.top();
    if (x < median) heapmax.push(x), summax += x;
    else heapmin.push(x), summin += x;
    if (heapmax.size() > heapmin.size() + 1) {
        heapmin.push(heapmax.top());
        summin += heapmax.top();
        summax -= heapmax.top();
        heapmax.pop();
    } else if (heapmin.size() > heapmax.size() + 1) {
        heapmax.push(heapmin.top());
        summax += heapmin.top();
        summin -= heapmin.top();
        heapmin.pop();
    }
    return heapmax.size() >= heapmin.size() ? heapmax.top() : heapmin.top();
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>q;
	ll median,fx;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			ll a,yb;
			cin>>a>>yb;
			median=getMedian(a);
			b+=yb;
			fx=median*sz(heapmax)-summax+summin-median*sz(heapmin)+b;
		} else cout<<median<<' '<<fx<<'\n';
	}	

}



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

int main(){
  long long n, a[10000];
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  cout << *min_element( a, a + n) << " "
       << *max_element( a, a + n) << " "
       << accumulate( a, a + n, 0LL) << endl;
}




Measured memory_bytes: 3160
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Array as A
import Data.Bool (bool)

main :: IO ()
main = do
  (n : k : q : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  as <- sequence . replicate q $ unsafeSignedDecimal <$> T.getLine :: IO [Int]
  let
    cs = A.elems . A.accumArray (+) 0 (1, n) . map (flip (,) 1) $ as :: [Int]
    f :: Int -> Int
    f c = k - (q - c)
  mapM_ (putStrLn . bool "No" "Yes" . (0 <) . f) $ cs

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 34428
#include <iostream>
#include<set>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 100000000;

vector<int> divisor(int n) {
  vector< int > ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

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

    vector<int> v = divisor(M);
    sort(v.begin(), v.end(), greater<int>());

    for (int i = 0; i < v.size(); i++){
        int key = M / v[i];
        if((key - N) >= 0){
            cout << v[i] <<  endl;
            return 0;
        }
    }

    cout << 1 << endl;
/*
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << endl;
    }
*/
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
#include <vector>
#include <map>
#include <iterator>
#include <iterator>
#include <string>
#define pan(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define vi vector<int>
#define pb push_back
using namespace std;
 
 
 
int main() {
    int n;
    cin>>n;
    ll a[n];
    pan(i,n) cin>>a[i];
    sort(a,a+n);
    int flag=1;
    for(int i=0;i<n-1;i++){
        if(a[i]==a[i+1]){
            flag=0;
            break;
        }
    }
    if(flag==1) cout<<"YES";
    else cout<<"NO";
}

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

int main(){
	int n, h, w, ans = 0;
	scanf("%d %d %d", &n, &h, &w);
	for(int i=0; i<n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		ans += (a>=h and b>=w);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
INF = float('inf')
N, K = map(int, input().split())
h = list(map(int, input().split()))

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

for i in range(1, N):
    for j in range(min(i, K) + 1):
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[N - 1])


Measured memory_bytes: 85584
n = int(input())
lst = []
for _ in range(n):
    x,y = [x for x in input().split()]
    lst.append([float(x),y])

money = 0

for i in range(n):
    if lst[i][1] == "JPY":
        money += lst[i][0]
    else:
        money += lst[i][0] * 380000.0

print(money)

Measured memory_bytes: 3060
N=int(input())
A=list(map(int,input().split()))
ans=1
for i in range(N):
    if (A[i]==0):
        ans=0
if (ans!=0):
    for i in range(N):
        ans=ans*A[i]
        if ans>1e+18:
            ans=-1
            break
       
print(ans)

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

const int mod = 998244353;

ll dp[200010], cu[200010];
int l[10], r[10];

int main() {
    int n, k;
    cin >> n >> k;
    rep(i, k) {
        cin >> l[i] >> r[i];
    }
    dp[1] = 1;
    dp[2] = -1;
    for (int i = 1; i <= n; i++) {
        dp[i] += dp[i-1];
        dp[i] %= mod;
        rep(j, k) {
            if (i + l[j] <= n) {
                dp[i + l[j]] += dp[i];
                dp[i + l[j]] %= mod;
            }
            if (i + r[j] + 1 <= n) {
                dp[i + r[j] + 1] -= dp[i];
                dp[i + r[j] + 1] %= mod;
                if (dp[i + r[j] + 1] < 0) dp[i + r[j] + 1] += mod;
            }
        }
    }
    cout << dp[n] << endl;
}


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

signed main(){
	int a, b, x, ans = 0;
	
	cin>>a>>b>>x;
	
	if(a == 0)ans = b/x+1;
	else ans = b/x-(a-1)/x;
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

template <typename T1, typename T2>
inline void chmin(T1 &a, T2 b) {
    if (a > b) a = b;
}

ll n, a, b, c, d;
map<ll, __int128_t> dp;

__int128_t dfs(ll x) {
    if (dp.count(x)) return dp[x];
    if (x == 0) return 0;
    if (x == 1) return d;
    __int128_t res = (__int128_t)d * x;
    chmin(res, dfs(x / 2) + a + abs((x / 2) * 2 - x) * d);
    if (x % 2 != 0)
        chmin(res, dfs(x / 2 + 1) + a + abs((x / 2 + 1) * 2 - x) * d);
    chmin(res, dfs(x / 3) + b + abs((x / 3) * 3 - x) * d);
    if (x % 3 != 0)
        chmin(res, dfs(x / 3 + 1) + b + abs((x / 3 + 1) * 3 - x) * d);
    chmin(res, dfs(x / 5) + c + abs((x / 5) * 5 - x) * d);
    if (x % 5 != 0)
        chmin(res, dfs(x / 5 + 1) + c + abs((x / 5 + 1) * 5 - x) * d);
    return dp[x] = res;
}

signed main() {
    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> a >> b >> c >> d;
        cout << (ll)dfs(n) << endl;
        dp.clear();
    }
    return 0;
}

Measured memory_bytes: 4620
N = int(input())
x_pred = 0
y_pred = 0
t_pred = 0
ans = 'Yes'
for i in range(N):
    t,x,y = map(int,input().split())
    check = ((t-t_pred)-(abs(x-x_pred)+abs(y-y_pred)))
    if((check<0) or (check%2!=0)):
        ans = 'No'
    else:
        t_pred = t
        x_pred = x
        y_pred = y
print(ans) 


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

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

using namespace std;

int main() {
  int t;
  cin>>t;
  REP(dst,t){
    int n,k;
    cin>>n>>k;
    vector<int> x(n);
    REP(i,n)cin>>x[i];
    vector<int> d(n-1);
    REP(i,n-1)d[i]=x[i+1]-x[i];
    sort(begin(d),end(d));
    int sum = 0;
    REP(i,max(0,n-k)){
      sum += d[i];
    }
    cout<<sum<<endl;
  }
  return 0;
}

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

int main() {
  string S;
  cin >> S;
  int N = S.size();
  vector<int> ans(N);

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (S.at(i) == 'R') cnt++;
    else ans.at(i) += cnt / 2, ans.at(i - 1) += (cnt + 1) / 2, cnt = 0;
  }
  for (int i = N - 1; i >= 0; i--) {
    if (S.at(i) == 'L') cnt++;
    else ans.at(i) += cnt / 2, ans.at(i + 1) += (cnt + 1) / 2, cnt = 0;
  }

  for (int i = 0; i < N; i++) cout << ans.at(i) << "\n";
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

int main(){

  string s;
  cin >> s;
  for (int i = 0; i < 3; i++){
    if (s[i] == '9'){
      cout << '1';
    }
    else if (s[i] == '1'){
      cout << '9';
    }
    else {
      cout << s[i];
    }
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#define LL long long 
#define INF 0X7FFFFFFF
using namespace std;
int N;
LL f[100005];
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%lld",&f[i]);
	sort(f+1,f+N+1);
	LL sum=0;
	int pos=0;
	for(int i=1;i<N;i++)
	{
		sum+=f[i];
		if(sum*2<f[i+1])
			pos=i;
	}
	printf("%d\n",N-pos);
}

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

using namespace std;

const int INF = 1e9 + 5;

int ans = INF;
int n, m, x;
int c[13], a[13][13];

void solve(int i, vector <int> b)
{
    if (i == n)
    {
        int price = 0;
        int u[13];

        for (int j = 0; j < m; j++)
            u[j] = 0;

        for (int k = 0; k < b.size(); k++)
        {
            price = price + c[b[k]];

            for (int j = 0; j < m; j++)
                u[j] += a[b[k]][j];
        }

        for (int j = 0; j < m; j++)
        {
            if (u[j] < x)
                return;
        }

        ans = min(ans, price);

        return;
    }

    solve(i+1, b);
    b.push_back(i);
    solve(i+1, b);
    b.pop_back();
}

int main()
{

    cin >> n >> m >> x;

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

        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
        }
    }

    solve(0, vector <int>());

    if (ans == INF)
        ans = -1;
    
    cout << ans << "\n";

    return 0;
}

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

using namespace std;

#define ge getchar()
#define Re read()

inline long long read() {
	long long x = 0, ch;
	while(!isdigit(ch = ge)) ;
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	return x;
}

const int MAXN = 100100;

struct Edge {
	int u, v;

	Edge() {}
	Edge(int u, int v):u(u), v(v) {}
}E[MAXN + 1];

int ct, N;
int fa[MAXN + 1];
int sz[MAXN + 1];

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void Merge(int u, int v) {
	int fu = find(u), fv = find(v);
	if(fu == fv) return ;
	fa[fu] = fv; ++N;
	sz[fv] += sz[fu];
}

int main() {
	int n = Re; long long m = Re; int q = Re;
	for(int i = 1; i <= n; i++) fa[i] = i;
	for(int i = 1; i <= q; i++) {
		int u = Re + 1, v = Re + 1, k = Re;
		if(k) {
			E[++ct] = Edge(u, v);
		} else {
			Merge(u, v);
		}
	}
	for(int i = 1; i <= ct; i++) {
		if(find(E[i].u) == find(E[i].v)) {
			puts("No");
			return 0;
		}
	} int SZ = 0;
	for(int i = 1; i <= n; i++) SZ += find(i) == i;
	if(SZ == 2) {
		puts("No");
		return 0;
	}
	m -= n - SZ;
	if(m > 1LL * SZ * (SZ - 1) / 2) {
		puts("No");
		return 0;
	} int tN = 0;
	for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1; N = 0;
	for(int i = 1; i <= ct; i++) Merge(E[i].u, E[i].v);
	for(int i = 1; i <= n; i++) tN += find(i) == i && sz[i] > 1 ? max(3, sz[i]) : 0;
	if(m < tN) {
		puts("No");
		return 0;
	} puts("Yes");
	return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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;
}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    int A, B;
    cin >> A >> B;

    if (A >= 13) cout << B << endl;
    else if (A >= 6 and A < 13) cout << B/2 << endl;
    else cout << 0 << endl;

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  
  int i, p;
  vector<int> x(n);
  for(i = 0; i < n; i++){
    cin >> p;
    x.at(p - 1) = i;
  }
  
  int ans = 0, count = 1;
  for(i = 1; i < n; i++){
    if(x.at(i - 1) < x.at(i)) count++;
    else{
      ans = max(ans, count);
      count = 1;
    }
  }
  
  ans = max(ans, count);
  
  cout << n - ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define MAX 510000
#define Rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep(i, n) for(ll i = 1; i <= (ll)(n); i++)

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

//cout << fixed << setprecision(10);//
//最小公倍数//
ll gcd(ll x, ll y) {
	if (x == 0) return y;
	return gcd(y%x, x);
}
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

//べき//
ll squ(ll n, ll p, ll m){
	if(p==0) return 1;
	if(p%2==0){
		ll t=squ(n, p/2, m);
		return t*t%m;
	}
	return n*squ(n,p-1,m);
	
}


//逆元mod(mを法とするaの逆元)//
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//Cmonp//
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[k] * finv[n - k] % MOD) % MOD;
}

//nが大

ll com(ll n,ll m){
	if(n<=0 || m<=0 || n==m){
		return 1;
	}
	if(n<m){
		return 0;
	}
	ll k=1;
	for(ll i=1;i<=m;i++){
       k*=(n-i+1); 
	   k%=MOD;
	   k*=modinv(i,MOD);
	   k%=MOD;
	}

	return k;
}


//


////////////////////////////////////////////////////////////////////




int main() {

ll n,t;
cin>>n>>t;
ll w[n+1];
ll v[n+1];
rep(i, n){
    cin>>w[i]>>v[i];
}

ll dp[t+1][n+1];
Rep(i, t+1){
Rep(j, n+1){
dp[i][j]=0;
}
}

ll ans=0;
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
if(i>=w[j]){
dp[i][j]=max(dp[i][j],dp[i-w[j]][j-1]+v[j]);
ans=max(ans,dp[i][j]);
}
}
for(int l=2;l<=n;l++){
    dp[i][l]=max(dp[i][l],dp[i][l-1]);
}

}

cout<<ans<<endl;
return 0;

}



Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    string N;
    cin >> N;
    vector<vector<int>> dp(N.size()+1,vector<int>(2,0));
    dp[0][1] = 1;
    FOR(i,1,N.size()+1) {
        int Ni = N[i-1] - '0';
        dp[i][0] = min(dp[i-1][0]+Ni,dp[i-1][1]+10-Ni);
        dp[i][1] = min(dp[i-1][0]+Ni+1,dp[i-1][1]+10-Ni-1);
    }
    cout << dp[N.size()][0] << endl;
    return 0;
}


Measured memory_bytes: 55940
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define FOREACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIGN(x) (((x)>0)?1:(((x)<0)?-1:0))
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 (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
#define vv(t) vector< t > 
#define CHC(mp, x) if(mp.end() != mp.find(x))
#define CHCV(mp, x) if(mp.end() != find(ALL(mp), x))
template<typename T>
inline T lcm(T a, T b) {return a / __gcd(a, b) * b;}
#define fi first
#define se second
#define el endl
#pragma endregion


void Main();
void solve(long long A, long long P);

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    long long A;
    scanf("%lld",&A);
    long long P;
    scanf("%lld",&P);
    solve(A, P);
}

void solve(long long A, long long P){
    cout << (A*3+P)/2 <<el;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll n, k;
  cin >> n >> k;
  
  if (k == 1)
    cout << 0 << endl;
  else
    cout << n - k << endl;

  return 0;
}


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

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

    vector<int> buttons(num_buttons, 0);
    vector<bool> visited_buttons(num_buttons, false);
    int dest;
    bool exists_button2 = false;
    for(int i = 0; i < num_buttons; i++) {
        cin >> dest;
        buttons[i] = dest;
        if (dest == 2) {
            exists_button2 = true;
        }
    }
    if(!exists_button2) {
        cout << -1 << endl;
        exit(EXIT_SUCCESS);
    }

    int j = 0, count = 0, next;
    while (true) {
        if (j == 1 /* button 2 */) {
            cout << count << endl;
            exit(EXIT_SUCCESS);
        }
        else if (visited_buttons[j]) {
            cout << -1 << endl;
            exit(EXIT_SUCCESS);
        }
        visited_buttons[j] = true;
        j = buttons[j] - 1;
        count++;
    }
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		String a = scan.next();
		String b = a.substring(a.length() - 1);

		if(b.equals("3")) {
			System.out.println("bon");
		}else if(b.equals("0") || b.equals("1") || b.equals("6") || b.equals("8")) {
			System.out.println("pon");
		}else {
			System.out.println("hon");
		}

	}
}

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

int main()
{
    int A, B;
    cin >> A >> B;
    int sum = 1;
    int i = 0;

    while (sum < B)
    {
        i++;
        sum = sum + A - 1;
    }

    cout << i << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int n, w, a = 0, b = 0, c = 0; cin >> n;
	int test[101] = { 0 };
	for (int h = 0; h < n; h++) {
		cin >> w;
		test[h] = w;
	}
	for (int t = 1; t <= n; t++) {
		for (int i = 0; i < t; i++) {
			a += test[i];
		}
		for (int i = t; i < n; i++) {
			b += test[i];
		}
		if (t == 1) {
			c = abs(a - b);
		}
		else {
			if (abs(a - b) < c) {
				c = abs(a - b);
			}
		}
		a = 0; b = 0;
	}
	cout << c << endl;
	cin >> n;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)

int n,f[5005][5005],len;
int clz=1E9+7;
char ch[5005];
long long pw(long long a,int b){
    long long nw=1;
    while(b){
        if(b&1){
            nw=nw*a%clz;
        }
        a=a*a%clz;
        b>>=1;
    }
    return nw;
}
void init(){
//    freopen("keyboard.in","r",stdin);
//    freopen("keyboard.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",ch);
    len=int(strlen(ch));
    f[0][0]=1;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=i;++j){
            f[i+1][j+1]=int(1LL*f[i][j]*2%clz+f[i+1][j+1]%clz)%clz;
            f[i+1][Max(j-1,0)]=int(1LL*(f[i][j]+f[i+1][Max(j-1,0)])%clz);
        }
    }
    int anss=(int(pw(pw(2,len),clz-2)*f[n][len]%clz));
    printf("%d",anss);
}
//int(pw(pw(2,len),clz-2))*
int main(){
    init();
    return 0;
}

Measured memory_bytes: 96640
N, K = map(int, input().split())
a = []

for i in range(N):
    a.append(False)

for i in range(K):
    dam = int(input())
    d = [int(x) for x in input().split()]
    for j in d:
        a[j-1] = True

c=0
for i in a:
  if i==False:
    c = c + 1
print(c)

Measured memory_bytes: 9124
#include<bits/stdc++.h>
using namespace std;
 
int n, x, y, res, fir=1, rt, f[101000];
vector<int>G[101000];
 
void dfs(int x,int fff){
  int isrt=0;
  if (G[x].size()>2&&fir) fir=0, isrt=1;
  for (auto y:G[x]) if (y!=fff) dfs(y,x);
  int t=max(0,(int)G[x].size()+isrt-2-f[x]);
  f[fff]+=!!f[x]|!!t;
  res+=t;
}
 
int main(){
  cin>>n;
  for (int i=n-1;i--;){
    scanf("%d%d",&x,&y); ++x; ++y;
    G[x].push_back(y); G[y].push_back(x);
  }
  for (rt=1;G[rt].size()!=1;++rt); dfs(rt,0);
  cout<<max(res,1);
}

Measured memory_bytes: 12416
#include<stdio.h>

int A=0,B=0,n,i;

void Battle(int kaisuu);
main()
{
	while(scanf("%d",&n)){
		if(n==0)break;
		A=0,B=0;
		Battle(n);
		
		printf("%d %d\n",A,B);
	}
	
	return 0;
}

void Battle(int kaisuu){
	int a,b;
	for(i=0;i<n;i++){
		scanf("%d %d",&a,&b);
		if(a>b) {A+=a+b;}
		else if(a<b) {B+=a+b;}
		else {A+=a;B+=b;}
	}
}

Measured memory_bytes: 600
import re
s, t = input().replace(*"?."), input()
l, m = len(s), len(t)

can = []
for i in range(l - m + 1):
    if re.match(s[i:i+m], t):
        can += (s[:i] + t + s[i+m:]).replace(*".a"),
print(min(can) if can else "UNRESTORABLE")

Measured memory_bytes: 9808
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
using namespace std;
using ll=long long;
using ld=long double;
#define ssort(n) sort((n).begin(),(n).end())
typedef pair<int,int> P;

int main()
{
    int N;
    vector<ll> a;
    cin >> N;
    a.resize(N);
    vector<ll> list(3);

    rep(i,N)cin >> a[i];
    rep(i,3)list[i]=0;
    rep(i,N){
        if(a[i]%4==0){
            list[0]++;
        }else if(a[i]%2==0&&a[i]%4==2){
            list[1]++;
        }else{
            list[2]++;
        }
    }
    ll n_4=0;
    if(list[1]>0){
        n_4=1;
    }
    n_4+=list[2];
    if(n_4<=list[0]+1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }




}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int ans=1000000009;
    int vmax=0;
    cin>>n;
    int x[110]={};
    for(int i=0;i<n;i++){
        cin>>x[i];
        vmax=max(vmax,x[i]);
    }
    for(int p=1;p<=vmax;p++){
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=pow(x[i]-p,2);
        }
        ans=min(ans,sum);
    }
    cout<<ans<<"\n";
    return(0);
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define double long double
double v[100005];
double w[100005];
double solve(int l,int r,double W){
	if(l>r)return 0;
	int k=l;
	for(int i=l;i<r;i++){
		if(v[i]/w[i]<v[r]/w[r]){
			swap(v[i],v[k]);swap(w[i],w[k]);
			k++;
		}
	}
	swap(w[k],w[r]);swap(v[k],v[r]);
	double Wr=0,Wl=0,Vr=0,Vl=0;
	for(int i=r;i>k;i--)Wr+=w[i],Vr+=v[i];
	for(int i=l;i<k;i++)Wl+=w[i],Vl+=v[i];
	if(W<Wr){
		return solve(k+1,r,W);
	}else if(Wr<=W&&W<=Wr+w[k]){
		return Vr+v[k]/w[k]*(W-Wr);
	}else if(Wr+w[k]<W&&W<Wr+w[k]+Wl){
		return Vr+v[k]+solve(l,k-1,W-Wr-w[k]);
	}else{
		return Vr+v[k]+Vl;
	}
}
int main(){
//	freopen("a.txt","r",stdin);
//	freopen("b1.txt","w",stdout);
	int n;double W;
	cin>>n>>W;
	for(int i=0;i<n;i++)cin>>v[i]>>w[i];
//	printf("%.6f\n",solve(0,n-1,W));
	printf("%.6Lf\n",solve(0,n-1,W));
	return 0;
}


Measured memory_bytes: 6312
package main

import (
	"fmt"
)

type Operation struct {
	y1, x1, y2, x2 int
}

func main() {
	var h, w int
	fmt.Scan(&h, &w)

	ops := make([]Operation, 500 * 500)
	opsInd := 0
	a := make([][]int, h)
	for i := 0; i < h; i++ {
		a[i] = make([]int, w)
		for j := 0; j < w; j++ {
			fmt.Scan(&a[i][j])
			if j > 0 && a[i][j-1] % 2 == 1 {
				a[i][j-1]--
				a[i][j]++
				ops[opsInd] = Operation{i + 1, j, i + 1, j + 1}
				opsInd++
			}
		}
		if i > 0 && a[i-1][w-1] % 2 == 1 {
			a[i-1][w-1]--
			a[i][w-1]++
			ops[opsInd] = Operation{i, w, i + 1, w}
			opsInd++
		}
	}

	ops = ops[:opsInd]
	fmt.Println(opsInd)
	for _, op := range ops {
		fmt.Println(op.y1, op.x1, op.y2, op.x2)
	}
}

Measured memory_bytes: 21840
import sys
sys.setrecursionlimit(10**8)
n=int(input())
l=list(map(int,input().split()))
dp=[-1 for i in range(n)]
dp[0]=0
dp[1]=abs(l[0]-l[1])
def dp1(n1):
  if dp[n1]!=-1:
    return dp[n1]
  else:
    ans=min(dp1(n1-1)+abs(l[n1-1]-l[n1]),dp1(n1-2)+abs(l[n1-2]-l[n1]))
    dp[n1]=ans
    return ans
print(dp1(n-1))


Measured memory_bytes: 93588
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin >> a;
  int key = 0;
  for(int i = 0;i<a;i++){
    int b;
    cin >> b;
    if(b%2 == 0){
      if(b%3 != 0 && b%5 != 0){
        cout << "DENIED" << endl;
        key = 1;
        break;
      }
    }
  }
  if(key == 0)
    cout << "APPROVED" << endl;
}

Measured memory_bytes: 256
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
 
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

fn pow(i: i64) -> i64 {
    i*i*i*i*i
}

fn f(x: i64, a: i64, b: i64) -> i64 {
    pow(a) - pow(b)
}

fn try_b(x: i64, a: i64) -> Option<i64> {
    let mut b = 0;

//    dbg!(x);
//    dbg!(a);
//    dbg!(b);

    while f(x, a, b) > x {
        b += 1;
    //    dbg!(b);
    }

    while f(x, a, b) < x {
        b -= 1;
   //     dbg!(b);
    }

    if f(x, a, b) == x {
  //      dbg!(b);
        return Some(b);
    };

    return None;
}

fn solve(x: i64) -> (i64, i64) {
    let mut a = 0;
    loop {
        if let Some(b) = try_b(x, a) {
            return (a, b);
        }
        if let Some(b) = try_b(x, -a) {
            return (-a, b);
        }
        a += 1;
    }
}

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let x = sc.read();

    let (a, b) = solve(x);
    println!("{} {}", a, b);
}
 


Measured memory_bytes: 2184
from heapq import heappush, heappop
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

# グラフにコストを格納
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

q, k = map(int, input().split())


# コストの初期化
INF = 1 << 60
dist = [INF] * (n + 1)
dist[k] = 0

#　スタート地点
que = [(0, k)]

# ３からの距離
while que:
    cost, curr = heappop(que)
    if cost > dist[curr]:
        continue
    for after, nc in graph[curr]:
        if cost + nc < dist[after]:
            dist[after] = cost + nc
            heappush(que, (cost + nc, after))
            
print(*([dist[x] + dist[y] for x, y in (map(int, input().split()) for _ in range(q))]), sep="\n")

Measured memory_bytes: 60704
import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""





co = 0



n,k = m()

dp = [[0 for i in range(n)] for j in range(n)]

for i in range(k):
    a,b = m()
    a -= 1
    b -= 1
    dp[a][b] = 1
    dp[b][a] = 1

def dfs(now,li,dp):
    global co

    for i in range(n):
        if dp[now][i] == 1 and li[i] == 0:
            po = copy.deepcopy(li)
            po[i] = 1
            dfs(i,po,dp)
    if sum(li) == n:
        co += 1
nnn = [0 for i in range(n)]
nnn[0] = 1
dfs(0,nnn,dp)
print(co)


Measured memory_bytes: 50648
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
char ch[110000];
int A[3],n;
int check(int k1,int k2,int k3){
	if (k3==0) return 1;
	int ne=3-k1-k2;
	if (A[ne]==0) return 0;
	A[ne]--;
	int ans=check(k2,ne,k3-1);
	A[ne]++; return ans;
}
int main(){
	scanf("%s",ch+1); n=strlen(ch+1);
	for (int i=1;i<=n;i++) A[ch[i]-'a']++;
	if (n==1){
		cout<<"YES"<<endl; return 0;
	}
	for (int i=0;i<3;i++)
		if (A[i]){
			A[i]--;
			for (int j=0;j<3;j++)
				if (A[j]&&i!=j){
					A[j]--;
					if (check(i,j,n-2)){
						cout<<"YES"<<endl; return 0;
					}
					A[j]++;
				}
			A[i]++;
		}
	cout<<"NO"<<endl; return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	int X;
	cin >> X;
	int res = (X / 500) * 1000 + ((X % 500) / 5) * 5;
	cout << res << endl;

	return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())

s = input()

ans = []
p = n

flag = 1
while flag:
    for j in range(m,0,-1):
        if p-j<=0:
            ans.append(p)
            flag = 0
            break
        elif s[p-j]=='0':
            ans.append(j)
            p-=j
            break
        elif j == 1:
            ans.append(-1)
            flag = 0
            break

print(' '.join(map(str,reversed(ans))) if ans[-1]!=-1 else -1)


Measured memory_bytes: 49840
from collections import deque
n = int(input())
ki = [[] for i in range(n)]
lis = []
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)
    lis.append([a,b,i])
mx = 0
for i in range(n):
    ki[i].sort()
    mx = max(mx,len(ki[i]))
lis = sorted(lis, key=lambda x:x[0])
lis = sorted(lis, key=lambda x:x[1])
lis2 = [[] for i in range(n)]
cnt = 0
for i in range(n-1):
    lis2[lis[i][0]].append(lis[i])
#print(lis2)

#print(ki)
def bfs(ki,lis2):
    d = [True] * n
    que = deque([(0,-1)])
    d[0] = False
    while len(que) != 0:
        val = que.popleft()
        cnt = 1
        cnt2 = 0
        for i in range(len(ki[val[0]])):
            if d[ki[val[0]][i]] == True:
                d[ki[val[0]][i]] = False

                #print(cnt,cnt2,val,i)
                if val[1] == cnt:
                    cnt += 1
                lis2[val[0]][cnt2].append(cnt)
                que.append([ki[val[0]][i],cnt])
                cnt += 1
                cnt2 += 1

    return lis2
lis2 = bfs(ki,lis2)
#print(lis2)
val = 0
for i in range(n):
    val = max(len(ki[i]),val)
print(val)
lis = []
for i in range(n):
    for j in range(len(lis2[i])):
        lis.append(lis2[i][j])
lis = sorted(lis,key=lambda x:x[2])
for i in range(n-1):
    print(lis[i][3])


Measured memory_bytes: 54548
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//ll a[Max];
ll n,d;
void solve(){
	cin>>n;
	int j=0;
	int mx1=0,mx2=0;
	rep(i,0,n){
		ll t;
		cin>>t;
		if(t>mx1){
			mx1 = t;
			j = i;
		}else if(t>mx2){
			mx2 = t;
		}
	}
	rep(i,0,n)if(i==j)cout<<mx2<<"\n";else cout<<mx1<<"\n";
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





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

using namespace std;

char s[105];
int frecv[30];

int main(){
    int i,ok=1;

    cin>>s;

    for(i=0;i<strlen(s);i++)
        frecv[s[i]-'a']++;

    for(i=0;i<=26;i++)
        if(frecv[i]%2!=0)
            ok=0;

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

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	char a[60][60],c;
	int h,w,i,j,k,l,u;
	scanf("%d%d",&h,&w);
	scanf("%c",&c);
	
	for(i=0;i<h;i++){scanf("%s",a[i]);scanf("%c",&c);}
	for(i=0;i<h;i++){
	for(j=0;j<w;j++){
	if (a[i][j]=='.'){
		u=0;
	 if(i-1>=0){
	 	if (a[i-1][j]!='.')u++;
	 	 if(j-1>=0){
	 	if (a[i-1][j-1]!='.')u++;
	 	
	 }
	 if(j+1<w){
	 	if (a[i-1][j+1]!='.')u++;
	 	
	 }
	 	
	 }
	  if(j-1>=0){
	 	if (a[i][j-1]!='.')u++;
	 	
	 }
	if(i+1<h){
	 		if (a[i+1][j]!='.')u++;
	 	 if(j-1>=0){
	 	if (a[i+1][j-1]!='.')u++;
	 	
	 }
	 if(j+1<w){
	 	if (a[i+1][j+1]!='.')u++;
	 	
	 }
	 	
	 }
	  if(j+1<w){
	 	if (a[i][j+1]!='.')u++;
	 	
	 }
	 printf("%d",u);
	 
} 
else printf("%c",a[i][j]);
}
printf("\n");
}
return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
using namespace std;

signed main(){
    int n,m,xx=0,yy=0; cin>>n>>m;
    vector<int> x(n),y(m);
    rep(i,n) cin>>x.at(i);
    rep(i,m) cin>>y.at(i);
    rep(i,n-1){
        xx+=(x.at(i+1)-x.at(i))*(i+1)*(n-i-1);
    }
    rep(i,m-1){
        yy+=(y.at(i+1)-y.at(i))*(i+1)*(m-i-1);
    }
    cout<<((xx%mod)*(yy%mod))%mod<<endl;
}

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

using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  double a, b, x;
  cin >> a >> b >> x;
  double y = x / a;
  cout << fixed;
  if (y > a * b / 2) {
    y = a * b - y;
    double z = y * 2 / a;
    cout << setprecision(10) << atan(z / a) / M_PI * 180 << endl;
  } else {
    double z = y * 2 / b;
    cout << setprecision(10) << atan(b / z) / M_PI * 180 << endl;
  }
}

Measured memory_bytes: 256