akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long
#define INF             __LONG_LONG_MAX__

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

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

void solve() {
  ll n, k; cin >> n >> k;
  ll m = 0, g = -1;
  rep(i, n) {
    ll ai; cin >> ai;
    m = max(m, ai);
    g = g == -1 ? ai : gcd(g, ai);
  }
  if (k <= m && k % g == 0) outl("POSSIBLE");
  else outl("IMPOSSIBLE");
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		decimal A = decimal.Parse(str[0]);
		decimal B = decimal.Parse(str[1]);
		decimal C = decimal.Parse(str[2]);
		string ans = "No";
		if(Sqrt(A)+Sqrt(B)+0.000000000000000001m<Sqrt(C)){
			ans = "Yes";
		}
		Console.WriteLine(ans);
	}
public static decimal Sqrt(decimal x, decimal epsilon = 0.0M)
{
    if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");

    decimal current = (decimal)Math.Sqrt((double)x), previous;
    do
    {
        previous = current;
        if (previous == 0.0M) return 0;
        current = (previous + x / previous) / 2;
    }
    while (Math.Abs(previous - current) > epsilon);
    return current;
}
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define ull unsigned long long int
#define ll long long int
#define LL_MAX 9223372036854775807
#define pb push_back
#define pf push_front
#define mp make_pair
#define popb pop_back
#define vl vector<ll>
#define bs(v, x) binary_search(v.begin(), v.end(), x)
#define popf pop_front
#define p() cout << '\n'
#define p0(x) cout << x << " "
#define p1(x) cout << x << '\n'
#define p2(x, y) cout << x << " " << y << '\n'
#define p3(x, y, z) cout << x << " " << y << " " << z << '\n'
#define printv(v)                   \
  for (ll i = 0; i < v.size(); ++i) \
    cout << v[i] << " ";            \
  cout << '\n'
#define pr1(x) cout << fixed << setprecision(15) << x << '\n'
#define mod 1000000007
#define mod1 998244353
#define fio                         \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL)
#define get(n) \
  ll n;        \
  cin >> n
#define getvec(v, n)         \
  vector<ll> v(n);           \
  for (ll i = 0; i < n; i++) \
    cin >> v[i];
#define getstr(s) \
  string s;       \
  cin >> s
#define all(x) x.begin(), x.end()
#define countBits(x) __builtin_popcount(x)
using namespace std;

void mainSolve()
{
  get(x);
  ll k = 0;
  while (++k)
  {
    if ((x * k) % 360 == 0)
    {
      p1(k);
      return;
    }
  }
}

int main()
{
  fio;
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  //get(t);
  ll t = 1;
  while (t--)
  {
    mainSolve();
  }
  return 0;
}


Measured memory_bytes: 3608
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,used[200005],dp[200005],mx;
vector<int> g[200005];

void dfs(int v,int d)
{
	used[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (used[to])
			continue;
		dfs(to,d+1);
		mx = max(mx, dp[v] + 1 + dp[to]);
		dp[v] = max(dp[v], dp[to] + 1);
	}
	mx = max(mx, dp[v] + d);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n - 1; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].PB(b);
		g[b].PB(a);
	}
	for (int i = 1; i <= n; i++)
		if (g[i].size() == 1)
		{
			dfs(i,0);
			break;
		}
	mx %= 3;
	if (mx == 1)
		cout << "Second" << endl;
	else
		cout << "First" << endl;
	return 0;
}

/*

*/

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

using namespace std;
using LL = long long;
using P = pair<int, int>;
using Tapris = tuple<int, int, int>;

#define REP(i, n) for(LL i = 0; i < n; ++i)
#define FOR(i, a, n) for(LL i = a; i < n; ++i)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e15;
const int MOD = 1e9 + 7;

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

//#define int long long

/*************** using variables ***************/
int n, a;
vector<int> x;
LL dp[55][55][2505];
// dp[i][j][k]: i-1番目まででj個使ってkになる組み合わせの数
/**********************************************/

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

    cin >> n >> a;
    x.resize(n+1);
    REP(i, n){
        cin >> x[i+1];
    }
    
    dp[0][0][0] = 1;

    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= a*n; k++){
                if(i >= 1 && k < x[i]){
                    dp[i][j][k] = dp[i-1][j][k];
                }else if(i >= 1 && j >= 1 && k >= x[i]){
                    dp[i][j][k] = dp[i-1][j-1][k-x[i]] + dp[i-1][j][k];
                }
            }
        }
    }
    LL ans = 0;
    FOR(j, 1, n+1){
        ans += dp[n][j][a*j];
    }

    cout << ans << endl;
}



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

using namespace std; 
int main()
{
string s;
getline(cin,s);
if(isupper(s[0])){
	cout<<s[0];
}
 for(int i=1;i<s.length();i++){
 	if(isupper(s[i])&&s[i-1]==' '){
 		cout<<s[i];
	 }
 }
}

	

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val m = sc.nextInt()
    val ps = (0 until m).map { sc.next().toInt() to sc.next() }
    println(problem151c(n, m, ps))
}

fun problem151c(n: Int, m: Int, ps: List<Pair<Int, String>>): String {
    if (m == 0) return "0 0"
    val ps = ps.sortedBy { it.first }
    var waCount = 0
    var waCount2 = 0
    var acCount = 0
    var currentP = ps[0].first
    var isAc = false
    for (i in 0 until m) {
        val psi = ps[i]
        if (currentP != psi.first) {
            currentP = psi.first
            isAc = false
            waCount = 0
        }
        if (isAc) continue
        if (psi.second == "WA") waCount++
        if (psi.second == "AC") {
            acCount++
            waCount2 += waCount
            waCount = 0
            isAc = true
        }
    }
    return "$acCount $waCount2"
}

Measured memory_bytes: 85448
#include <iostream>
#include <vector>
#define NtoM(N, M) for(int i=N;i<M;i++)
#define Nfor(N) for(int j=0;j<N;j++)

using namespace std;

int main(){
  	int W, H, N;
  	cin >> W >> H >> N;
  	vector<vector<int>> board(W, vector<int>(H));
  	for(int k=0;k<N;k++){
      	int x, y, a;
      	cin >> x >> y >> a;
      	switch(a){
          case 1:
            	NtoM(0, x){
                  	Nfor(H) board[i][j] = 1;
                }
            	break;
          case 2:
            	NtoM(x, W){
                  	Nfor(H) board[i][j] = 1;
                }
            	break;
          case 3:
            	NtoM(0, y){
                  	Nfor(W) board[j][i] = 1;
                }
            	break;
          case 4:
            	NtoM(y, H){
					Nfor(W) board[j][i] = 1;
                }
            	break;
        }
    }
  	int sum = 0;
  	NtoM(0, W){
      	Nfor(H){
          	if(board[i][j] == 0) sum++;
        }
    }
  	cout << sum << endl;
}


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

def main():
    N = int(input())
    a = [int(input()) for i in range(N)]

    ans = a[0] // 2
    a[0] %= 2
    for i in range(1, N):
        if a[i] > 0:
            a[i] += a[i-1]
            ans += a[i] // 2
            a[i] %= 2
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 7072
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<set<int> > g(n);
  rep (i, m) {
    int a, b;
    scanf("%d%d", &a, &b);
    a -= 1; b -= 1;
    g[a].insert(b);
    g[b].insert(a);
  }
  bool ans = false;
  for (int u : g[0]) {
    if (g[u].find(n-1) != end(g[u])) {
      ans = true;
      break;
    }
  }
  if (ans) {
    printf("POSSIBLE\n");
  } else {
    printf("IMPOSSIBLE\n");
  }
  return 0;
}


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

int main()
{
  int64_t a, b;
  cin >> a >> b;
  if (a * b <= 0)
    cout << "Zero" << endl;
  else if (a > 0 || (b - a) % 2)
    cout << "Positive" << endl;
  else
    cout << "Negative" << endl;
}

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

int main() {
	string s;cin>>s;
  
  	for(int i=0;i<(1<<3);i++){
      int sum=stoi(s.substr(0,1));
  	  	for(int j=0;j<3;j++){
        	if(i&(1<<j)){        
              sum+=stoi(s.substr(j+1,1));
            }else{
              sum-=stoi(s.substr(j+1,1));
            }
        }
  		if(sum==7){
        	cout<<s[0]<<((i&(1<<0))?"+":"-");
            cout<<s[1]<<((i&(1<<1))?"+":"-");
          	cout<<s[2]<<((i&(1<<2))?"+":"-");
          	cout<<s[3]<<"=7";
          	return 0;
        }
        
	}    
}


Measured memory_bytes: 256
n = int(input())
A = []
B = []
for _ in range(n):
    a,b = map(int,input().split())
    A += [a]
    B += [b]
A.sort()
B.sort()
if n % 2 == 1:
    print(B[n//2]-A[n//2]+1)
else:
    a1 = A[n//2-1]
    a2 = A[n//2]
    b1 = B[n//2-1]
    b2 = B[n//2]
    print(b2+b1-a2-a1+1)

Measured memory_bytes: 25560
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

dic = Counter(A)

ans = sum(A)
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    ans += (C-B)*dic[B]
    dic[C] += dic[B]
    del dic[B]
    print(ans)

Measured memory_bytes: 24344
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

int main(int argc, char const *argv[])
{
    int ans = (1 << 30);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, -100, 100 + 1)
    {
        int tmp = 0;
        rep(j, n)
        {
            tmp += (a[j] - i) * (a[j] - i);
        }
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main
{
  public static void main(String[] agh)
  {
    Scanner sc=new Scanner(System.in);
    int n,m;
    n=sc.nextInt();
    m=sc.nextInt();
    int[] w=new int[n+1];
    int cor=0,inc=0;
    int[] x=new int[n+1];
   // for(int i=0;i<n;i++)
     // System.out.println(x[i]);
    for(int i=0;i<m;i++)
    {
      int que=sc.nextInt();
      String sta=sc.nextLine();
      if(x[que]==1)
        continue;
      if(sta.equals(" AC"))
      {
        x[que]=1;
        cor++;
        inc+=w[que];
      }
      else 
      {
        if(x[que]==0 && sta.equals( " WA"))
        {
          w[que]++;
        }
      }
    }
      System.out.println(cor+" "+inc);
 
  }
}

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

int main(){
    int n;
    double keeper = 0;
    cin >> n;
    vector<pair<double, double>> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i].first;
        keeper += v[i].first;
        v[i].second = i;
    }
    keeper /= n;
    int numKeeper;
    for(int i = 0; i < n; i++){
        numKeeper = v[i].second;
        v[i].second = v[i].first;
        v[i].first = numKeeper;
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++){
        numKeeper = v[i].first;
        v[i].first = v[i].second;
        v[i].second = numKeeper;
    }
    for(int i = 0; i < n; i++){
        v[i].first = abs(v[i].first - keeper);
    }
    sort(v.begin(), v.end());
    cout << v[0].second << endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<map> 
using namespace std;

typedef long long ll;

const int MAXN = 100010;

int a[MAXN];

map<int, bool> mp;

int main(){
	int N, ans = 0;
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &a[i]);
	for (int i = 1; i <= N; i += 2)
		mp[a[i]] = 1;
	for (int i = 2; i <= N; i += 2)
		mp[a[i]] = 0;
	sort(a + 1, a + 1 + N);
	for (int i = 1; i <= N; ++i)
		if ((i & 1) != mp[a[i]])
			++ans;
	printf("%d", ans >> 1);
	return 0;
}


Measured memory_bytes: 5376
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int ans = 0;
		String S = sc.nextLine();
		String T = sc.nextLine();
		
		for(int i = 0; i < 3; i++) {
			if(S.charAt(i) == T.charAt(i)) {
				ans++;
			}
			
		}
		
		System.out.println(ans);
	}
}


Measured memory_bytes: 21844
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int []pen = new int[3];
		for(int i = 0; i < 3; i++) {
			pen[i] = stdIn.nextInt();
		}
		int cnt = 3;
		if(pen[0]==pen[1]) {
			cnt--;
		}
		if(pen[1]==pen[2]) {
			cnt--;
		}
		if(pen[0]==pen[2]) {
			cnt--;
		}
		if(pen[0]==pen[1] && pen[1] ==pen[2]) {
			System.out.println(1);
			System.exit(0);
		}
		System.out.println(cnt);
	}

}


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

int dfs(int a,int b){
if(b==0)return a;
return dfs(b,a%b);
}

int main(void){
//cout<<dfs(12,6)<<endl;
int n,k;
cin>>n>>k;
vector<int> a(n);
cin>>a[0];

for(int i=1;i<n;i++){cin>>a[i];}
int ma=a[0],d=a[0];
//cout<<d<<endl;
for(int i=1;i<n;i++){
d=dfs(d,a[i]);
//cout<<d<<endl;
ma=max(ma,a[i]);
}
//cout<<d<<endl;
if(ma<k||(k%d)!=0){
cout<<"IMPOSSIBLE"<<endl;
}else{
	cout<<"POSSIBLE"<<endl;
}
return 0;
}


Measured memory_bytes: 768
n = int(input())
p = list(map(int,input().split()))

ans = 0
for i in range(1, n-1):
    if p[i] != max(p[i-1],p[i],p[i+1]) and p[i] != min(p[i-1],p[i],p[i+1]):
        ans += 1
print(ans)

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;



void solve() {
	int N, K; cin >> N >> K;
	vector<int>v(N);
	vector<int>pl, mi;
	REP(i, N) {
		cin >> v[i];
		if (v[i] >= 0)pl.push_back(v[i]);
		else mi.push_back(-v[i]);
	}
	VSORT(mi);
	vector<int>cum1(N + 1), cum2(N + 1);
	REP(i, (int)pl.size()) {
		cum1[i + 1] = pl[i];
	}
	REP(i, (int)mi.size()) {
		cum2[i + 1] = mi[i];
	}
	ll ans = 1e18;
	REP(k, min(K, (ll)pl.size())+1) {
		if (K - k > (int)mi.size())continue;
		int l1 = cum1[k];
		int l2 = cum2[K - k];
		//pe(l1); print(l2);
		ll tmp = l1 + l2 + min(l1, l2);
		ans = min(ans, tmp);
	}
	print(ans);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



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

class MyClass
{
    public static void Main(string[] args)
    {
        var str = Console.ReadLine();
        var down = new Stack<int>();
        var water = new Stack<int>();
        var top = new Stack<int>();
        var h = 0;
        for (int i = 0; i < str.Length; i++)
        {
            var c = str[i];
            if (c == '\\')
            {
                h--;
                down.Push(i);
            }
            else if (c == '/')
            {
                h++;
                if (down.Count > 0)
                {
                    var l = i - down.Pop();
                    while (water.Count > 0 && top.Peek() < h)
                    {
                        top.Pop();
                        l += water.Pop();
                    }
                    water.Push(l);
                    top.Push(h);
                }
                else if (top.Count > 0)
                {
                    top.Push(top.Pop() + 1);
                }
            }
        }
        Console.WriteLine(water.Sum());
        if (water.Count == 0)
        {
            Console.WriteLine(0);
        }
        else
        {
            Console.WriteLine("{0} {1}", water.Count, string.Join(" ", water.Reverse()));
        }
    }
}


Measured memory_bytes: 18720
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>

using namespace std;
using boost::sort;
using boost::adaptors::reversed;

auto factorize(int n) {
    vector<int> ans;

    for (int i = 2; i * i <= n; i++) {
        if (n % i != 0) continue;
        while (n % i == 0) n /= i;
        ans.push_back(i);
    }

    if (n != 1) ans.push_back(n);

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a);

    vector<vector<int>> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = factorize(a[i]);
    }
    bool pc = true;
    bool sc = true;
    unordered_map<int, int> p;
    for (int i = 0; i < n; i++) {
        for (int j : ans[i]) {
            if (p[j]) pc = false;
            p[j] += 1;
        }
    }
    for (auto [k, v] : p) {
        if (v == n) {
            sc = false;
            break;
        }
    }
    if (pc) {
        cout << "pairwise coprime" << endl;
    } else if (sc) {
        cout << "setwise coprime" << endl;
    } else {
        cout << "not coprime" << endl;
    }
}


Measured memory_bytes: 75756
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
typedef vector<int,vector<int>> vec;
typedef pair<string,int> P;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n,j) for (int i = n; j<i;i--)
#define print(out) cout<< out  << "\n";
#define all(vec) vec.begin(),vec.end()
#define mod 1000000007
const int INF = 1e9;

int main(){
  string S;int K;cin>>S>>K;
  set<string> st;
  REP(i,0,S.size()){
    REP(j,1,min(6,(int)S.size()+1)){
      string substr=S.substr(i,j);
      st.insert(substr);
    }
  }
  vector<string> vec(st.begin(),st.end());
  print(vec[K-1])
}


Measured memory_bytes: 1792
N = int(input())
T = list(map(int, input().split()))
A = list(map(int, input().split()))

M = [[-1, 10**9] for i in range(N)]

for i in range(N):
    if i == 0:
        M[i][0] = T[i]
    else:
        if T[i] != T[i-1]:
            M[i][0] = T[i]
        else:
            M[i][1] = T[i]

for i in range(N-1, -1, -1):
    if i == N-1:
        if M[i][0] != -1 and M[i][0] != A[i]:
            print(0)
            exit(0)
        else:
            if M[i][1] >= A[i]:
                M[i][0] = A[i]
            else:
                print(0)
                exit(0)

    else:
        if A[i] != A[i+1]:
            if M[i][0] != -1 and M[i][0] != A[i]:
                print(0)
                exit(0)
            else:
                if A[i] <= M[i][1]:
                    M[i][0] = A[i]
                else:
                    print(0)
                    exit(0)
        else:
            M[i][1] = min(M[i][1], A[i])
ans = 1
mod = (10 ** 9) + 7
for x, y in M:
    if x == -1:
        ans *= y
        ans %= mod

print(ans)


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

const ll N_MAX = 100005;

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

ll Combination(ll C, ll D){
    if(C<D||C<1) return 0;
    return fac[C]*(finv[D]*finv[C-D]%mod)%mod;
}

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

    ll N, K;
    cin >> N >> K;
    if(N == 1){
    	cout << 1 << endl;
    	return 0;
    }
    make();

    for(int i=1;i<=K;i++){
    	ll res = Combination(K-1, i-1);
    	ll T = (N-K) - (i-1);
    	ll cho = Combination(T+i+1-1, i+1-1);
    	res *= cho;
    	res %= mod;
    	cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>
#include <string.h>

int main(void) {
	int N;
	char X[1024];
	int D;
	char YakusimaruHiroko[1024];
	int YosinagaSayuri;
	int MinaseInori;
	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%s", X) != 1) return 1;
	if (scanf("%d", &D) != 1) return 1;
	YosinagaSayuri = D;
	for (MinaseInori = 0; MinaseInori < N; MinaseInori++) {
		if (X[MinaseInori] == '0') {
			if (YosinagaSayuri > 0) {
				YakusimaruHiroko[MinaseInori] = '1';
				YosinagaSayuri--;
			} else {
				YakusimaruHiroko[MinaseInori] = '0';
			}
		} else {
			YakusimaruHiroko[MinaseInori] = '1';
		}
	}
	YakusimaruHiroko[N] = '\0';
	for (MinaseInori = N - 1; YosinagaSayuri > 0 && MinaseInori >= 0; MinaseInori--) {
		if (YakusimaruHiroko[MinaseInori] == '1' && X[MinaseInori] == '1') {
			YakusimaruHiroko[MinaseInori] = '0';
			YosinagaSayuri--;
		}
	}
	puts(YakusimaruHiroko);
	return 0;
}

Measured memory_bytes: 588
import math
import copy
import fractions
import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

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

ans = 0
for i in range(n):
    tmp = math.ceil(np.log2(k/(i+1)))
    tmp = max(0, tmp)
    ans += 1/pow(2, tmp)

ans = ans/n
print(ans)


Measured memory_bytes: 13748
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)

#include <iostream>
#include <vector>
using namespace std;

//重複順列
vector<ll> buf;
void permutation(ll i, const ll size, const ll range_start, const ll range_end)
{
    if (i == size) {
      // ここで所望の作業を行う
      for(ll itr:buf){
        cout << itr;
      }
    }
    else{
        for(ll j = range_start; j <= range_end; ++j){
            buf[i] = j;
            permutation(i + 1, size, range_start, range_end);
        }
    }
}

int main(void)
{
  ll n, x, t, ans;
  cin >> n >> x >> t;
  ans = n/x;
  if(n%x!=0){
    ans++;
  }
  ans = ans * t;
  cout << ans << endl;
  return 0;
}


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

typedef long long ll;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    string s,t;
    cin >> s >> t;
    int n = s.size(),m = t.size();
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < m;++j) 
        if (s[i] == t[j]) {
            dp[i+1][j+1] = max(dp[i][j]+1,max(dp[i+1][j],dp[i][j+1]));
        } else {
            dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
        }
    }
    //for (int i = 0;i <= n;++i) p_ary(dp[i],0,m+1,j);
    string ans = "";
    int i = n,j = m;
    while (i > 0 && j > 0) {
        if (dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1] && dp[i][j] > dp[i-1][j-1]) {
            ans = s[i-1]+ans;
            i--;j--;
        } else if (dp[i][j] == dp[i-1][j]) i--;
        else j--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 37120
#include <bits/stdc++.h>
using namespace std ; 
long long a[500005] , q ;
int n ;
void merge(int l , int mid , int r) {
	vector<int> L , R ;
	int nl = mid-l+1;
	int nr=r-mid;
	for(int i=0 ; i < nl ; i++) {
		L.push_back(a[l+i]) ; 
	}
	for(int i=0 ; i < nr ; i++) {
		R.push_back(a[mid+1+i]) ; 
	}	
	
//	cout << l << ' ' << mid << ' ' << r << endl;
//	for(int i = 0 ; i < L.size() ; i++) cout << L[i] << ' '; cout << endl;
//	for(int i = 0 ; i < R.size() ; i++) cout << R[i] << ' '; cout << endl;
	
	R.push_back(1e9+7) ;
	L.push_back(1e9+7) ;
	int i=0 , j=0; 
	for(int k=l ; k<=r ; k++) {
		if(L[i] < R[j]) {
			a[k]=L[i];
			i++;
		}
		else {
			a[k]=R[j];
			j++;
		}
		q++;
	}
}
void merge_sort(int l, int r){
	if( l < r ){
		int mid=( l+r ) / 2 ;
		merge_sort(l , mid);
		merge_sort(mid+1, r);
		merge(l , mid , r ) ;
	}	
}
int main() {
	 cin >> n ; 
	 for(int i=0 ; i<n ; i++) {
	 	cin >> a[i]  ; 
	 }
	 merge_sort(0 , n-1) ;
	  
	 for(int i=0; i<n ;i++) {
	 	cout << a[i];
	 	if(i != n-1) cout << " ";
	 }
	 cout << endl ;
	 cout << q << endl ;
}


Measured memory_bytes: 9212
from fractions import gcd
a,b,c,d = map(int, input().split())
 
lcm = (c*d)//gcd(c,d)
 
x = ((a-1)//c)+((a-1)//d)-((a-1)//lcm)
y = (b//c)+(b//d)-(b//lcm)
 
print((b-(a-1))-(y-x))

Measured memory_bytes: 5048
#include "bits/stdc++.h"
using namespace std;

#define all(container) container.begin(), container.end()
#define sortall(container) (sort(container.begin(), container.end()))
#define yn(cond) ((cond) ? (cout << "yes" << endl) : (cout << "no" << endl))
#define Yn(cond) ((cond) ? (cout << "Yes" << endl) : (cout << "No" << endl))
#define YN(cond) ((cond) ? (cout << "YES" << endl) : (cout << "NO" << endl))

typedef long long       ll;

typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<char>    vc;
typedef vector<string>  vs;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<vi>		vvi;
typedef vector<vll>		vvll;
typedef vector<vd>		vvd;
typedef vector<vb>		vvb;
typedef vector<vc>		vvc;
typedef vector<vs>		vvs;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;

typedef struct edge_ {
	ll to;
	ll cost;
} edge;

typedef struct point_ {
	ll x, y;
	point_(ll x = 0, ll y = 0) : x(x), y(y) {}
} point;

template <typename T>
using mat2d = vector<vector<T>>;

constexpr double	PI = 3.14159265358979323846;
constexpr ll		INF = 1 << 15;
constexpr ll		MOD = (ll)1e9 + 7;
constexpr double	EPS = 1e-7;
constexpr int		dy4[4] = { 0, 1, 0, -1 };
constexpr int		dx4[4] = { 1, 0, -1, 0 };
constexpr int		dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
constexpr int		dx8[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
	for (const T& x : vec) os << x << " ";
	return os;
}

template<typename S, typename T>
istream& operator >> (istream& is, pair<S, T>& p) {
	is >> p.first >> p.second;
	return is;
}

istream& operator >> (istream& is, point& p) {
	is >> p.x >> p.y;
	return is;
}

template<typename S, typename T>
ostream& operator << (ostream& os, const pair<S, T>& p) {
	os << "{" << p.first << " : " << p.second << "}";
	return os;
}

template<typename T>
ostream& operator << (ostream& os, const set<T>& s) {
	for (const T& x : s) os << x << " ";
	return os;
}

ostream& operator << (ostream& os, const edge e) {
	os << "{to: " << e.to << ", cost: " << e.cost << "}";
	return os;
}

ostream& operator << (ostream& os, const point& p) {
	os << "(" << p.x << " " << p.y << ")";
	return os;
}

/******************************************************************************/
/**********************         Don't make WA !!         **********************/
/******************************************************************************/

int main()
{
	int N, H, W;
	cin >> N >> H >> W;
	vpii AB(N);
	cin >> AB;

	int ans = 0;
	for (auto ab : AB) {
		if (ab.first >= H && ab.second >= W)
			ans++;
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n; ll a[55];
int main(){
	cin>>n;
	rep(i,n) cin>>a[i];
	sort(a,a+n);
	ll ret = 0LL;
	for(int i=n-1;i>=0&&a[n-1];i--){
		//[i,n-1]
		ll prev = (i==0?0LL:a[i-1]);
		ll dif = a[i]-prev;
		ll num = dif/(n*1LL+1LL);
		ret += num*1LL*(n-i); //cout << ret << endl;
		for(int j=0;j<i;j++) a[j]+=num*(n-i);
		for(int j=i;j<n;j++) a[j]+=(-1-i)*1LL*num;
		rep(q,n){
			if(a[n-1]<n)break;
			a[n-1]-=n;
			for(int i=0;i<n-1;i++) a[i]++;
			ret++;
			sort(a,a+n);
		}
	}
	ll add = 5e18;
	for(int i=0;i<n;i++){
		add = min(add,max(0LL,a[n-1]-n*1LL+1LL)*n+1LL*i);
		a[n-1]-=n;
		for(int i=0;i<n-1;i++) a[i]++;
		sort(a,a+n);
	}
	cout << ret+add << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

/*
テストケース全てに目を通す
テストケースが2個以下だったらなんかある
N最小のコーナーケースがないか調べる
制約をしっかりと確認する（1からNまでの順列、全て異なる値などの制約も含め）
操作の逆順を考える
Codeforcesではscanfを使う
modの引き算には+modをする
エラー出力は消す
エラー出力を消せ！！！！！
 */

int main() {
    int a,b;
    cin >> a >> b;
    if(a>9 || b>9)cout << -1;
    else cout << a*b;
    


}

/*
cout << fixed;
cout << setprecision(n) << ans;
*/


Measured memory_bytes: 256
import java.util.*;
 
class Main{
	
	public static void main(String args[]){
 
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int x[] = new int[N];
 
		for(int n=0;n<N;n++){
			x[n] = sc.nextInt();
		}
 
		Arrays.sort(x);
 
		int max = x[N-1];
		int dist = -1;
		int t=-1;
		for(int n=0;n<N;n++){
			
			if(dist == -1 ||dist > Math.abs((max+1)/2-x[n])){
				dist = Math.abs((max+1)/2-x[n]);
				t = x[n];
			}
		}
		System.out.println(max+" "+t);
	}
}

Measured memory_bytes: 50384
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;
ll dp[101][10001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int N, K;
    cin >> N >> K;
    if(N == K) {
        dp[N][0] = N;
        dp[N][1] = 1;
    }else{
        dp[N][0] = K+1;
    }
    for(int i = N-1; i >= 1; i--){
        for(int j = N*K; j >= 0; j--){
            if(dp[i+1][j] > 0){
                for(int k = 0; k <= K; k++){
                    if(k < i){
                        dp[i][j+(k+j)/i] += dp[i+1][j];
                        dp[i][j+(k+j)/i] %= MOD;
                    }
                    if(k == i){
                        dp[i][1+j/i+j] += dp[i+1][j];
                        dp[i][1+j/i+j] %= MOD;
                    }
                    if(k > i){
                        dp[i][j] += dp[i+1][j];
                        dp[i][j] %= MOD;
                    }
                }
            }
        }
    }
    ll pow = 1;
    for(int i = 0; i < N-1; i++){
        pow *= (K+1);
        pow %= MOD;
    }
    ll sum = ((K*(K+1))/2)*N*pow;
    sum %= MOD;
    for(int j = N*K; j >= 0; j--){
        sum -= (ll)dp[1][j]*j;
        sum %= MOD;
        sum += MOD;
        sum %= MOD;
    }
    cout << sum << endl;
}

Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
using P = pair <int, int>;
 
 
int main() {
    ll n ,k;
    cin >> n >> k;
    ll ans = k;
    rep(i,n-1){
        ans *=(k-1);
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
n,m,x,y = map(int, input().split())
xs = [int(i) for i in input().split()]
ys = [int(i) for i in input().split()]

flag =False
d = x+1
while d <= y:
    if max(xs) < d and d <= min(ys):
        flag = True
        break
    d = d + 1

if flag:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3064
#!/usr/bin/python3
# -*- coding: utf-8 -*-



def main():
  N = int(input())
  ret = N-1
  for i in range(1,int(N**0.5)+1):
    if N%i != 0:
      continue
    else:
      ret = min(ret,i+N//i-2)
  return ret

print(main())

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

using namespace std;

#define allof(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define exists(s, e) (s.find(e)!=s.end())
#define INF 0x3f3f3f3f
#define endl '\n'
#define mp make_pair
#define watch(x) cout << (#x) << " is " << (x) << endl;

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

ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

vector<int> not_want;

bool does_not_want(char ch) {
    int lo = 0, hi = sz(not_want)-1;
    int num = ch - '0';
    int mid = 0;
    while(lo<=hi) {
        mid = (lo+hi)>>1;
        if(num < not_want[mid]) hi = mid - 1;
        else if(num > not_want[mid]) lo = mid + 1;
        else return true;
    }
    return false;
}

bool check(string s) {
    for(char ch : s) {
        if(does_not_want(ch)) return false;
    }
    return true;
}

void solve() {
    int n, k;
    cin >> n >> k;
    not_want.resize(k);
    for(int i=0; i<k; i++) cin >> not_want[i];
    
    while(true) {
        if(check(to_string(n))) {
            cout << n << endl;
            return;
        }
        n++;
    }
}

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



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
  int n,i;
  long a[200010],ans=1e18;
  cin >> n;
  for (i=0;i<n;i++) cin >> a[i];
  for (i=1;i<n;i++) a[i]+=a[i-1];
  for (i=1;i<n-2;i++){
    long min1,max1,min2,max2;
    long *p1,*p2;
    p1=lower_bound(a,a+i+1,a[i]/2);
    p2=lower_bound(a+i+1,a+n,a[i]+(a[n-1]-a[i])/2);
    if (abs(a[i]-*(p1-1)*2) < abs(a[i]-*p1*2)) p1--;
    min1=min(*p1,a[i]-*p1);
    max1=max(*p1,a[i]-*p1);
    if (abs(a[n-1]+a[i]-*(p2-1)*2) < abs(a[n-1]+a[i]-*p2*2)) p2--;
    min2=min(*p2-a[i],a[n-1]-*p2);
    max2=max(*p2-a[i],a[n-1]-*p2);
    ans=min(ans,max(max1,max2)-min(min1,min2));
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

using ll = long long;
using p  = pair<ll, ll>;

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (auto&& a : A) {
        cin >> a;
    }
    
    sort(A.begin(), A.end());
    
    size_t survivor = N - 1;
    size_t least = 0;
    
    while (survivor != least) {
        auto ptr = lower_bound(A.begin(), A.end(), (A[survivor] + 1) / 2);
        least = survivor;
        survivor = ptr - A.begin();
    }
    
    vector<ll> B = A;
    for (ll i = 1; i < N; i++) {
        B[i] += B[i - 1];
    }
    
    least = 0;
    while (survivor != least) {
        auto ptr = lower_bound(B.begin(), B.end(), (A[survivor] + 1) / 2);
        least = survivor;
        survivor = ptr - B.begin();
    }
    
    cout << N - survivor << endl;
    
    return 0;
}


Measured memory_bytes: 1792
package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
  "strings"
)

func main() {
  input := Input{bufio.NewReaderSize(os.Stdin,100)}
  n,m := input.NextInts()
  g := make([][]int,n)
  for i:=0;i<m;i++ {
    u,v := input.NextInts()
    g[u-1] = append(g[u-1],v-1)
    g[v-1] = append(g[v-1],u-1)
  }
  fmt.Println(multiply(g,g))
}

func multiply(ga,gb [][]int) int64 {
  na,ia,pa,qa := decompose(ga)
  nb,ib,pb,qb := decompose(gb)
  return int64(ia)*int64(ib)+int64(ia)*int64(nb-ib)+int64(ib)*int64(na-ia)+
  int64(pa)*int64(pb)+int64(pa)*int64(qb)+int64(qa)*int64(pb)+
  2*int64(qa)*int64(qb)
}

func decompose(g [][]int) (int,int,int,int) {
  n,i,p,q := len(g),0,0,0
  used := make([]bool,n)
  color := make([]int,n)
  var isBipartite func(int) bool
  isBipartite = func(u int) bool {
    if color[u] == 0 {
      color[u] = 1
      return isBipartite(u)
    }
    used[u] = true
    ret := true
    for _,v := range g[u] {
      if color[v] == color[u] { ret = false }
      if color[v] == 0 {
        color[v] = -color[u]
        ret = isBipartite(v) && ret
      }
    }
    return ret
  }
  for u:=0;u<n;u++ {
    if used[u] { continue }
    used[u] = true
    if len(g[u]) == 0 { i++;continue }
    if isBipartite(u) { q++;continue }
    p++
  }
  return n,i,p,q
}

type Input struct { reader *bufio.Reader }
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInts() (int,int) {
  s := strings.Fields(i.NextLine())
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  return x,y
}

Measured memory_bytes: 44928
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define debug2(x, y)                       \
  cerr << "(" << #x << "," << #y << ") = " \
       << "(" << x << "," << y << ")\n"
#define all(x) x.begin(), x.end()
#define each(a, x) for (auto &a : (x))
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5LL << 57, MOD = 1e9 + 7;

int N, H;
vector<pii> Katana;
void input() {
  cin >> N >> H;
  rep(i, 0, N - 1) {
    int a, b;
    cin >> a >> b;
    Katana.push_back(pii(a, 1));
    Katana.push_back(pii(b, 0));
  };
  ;
}
void solve() {
  sort(all(Katana),
       [](const auto &a, const auto &b) { return a.first > b.first; });

  int cnt = 0;
  for (auto x : Katana) {
    if (H <= 0) break;
    // debug(H);
    if (x.second == 0) {
      H -= x.first;
      cnt++;
    } else {
      cnt += H / x.first + (H % x.first > 0);
      H = 0;
      break;
    }
  }
  cout << cnt << endl;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 6384
from operator import itemgetter

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(n)]
ans = 0
dp_ab = [False] * n
dp_cd = [False] * n

ab.sort(key = itemgetter(1), reverse = True)
cd.sort()

for i in range(n):
    for j in range(n):
        if cd[i][0] > ab[j][0] and cd[i][1] > ab[j][1] and dp_cd[i] == False and dp_ab[j] == False:
            dp_cd[i] = True
            dp_ab[j] = True
            ans += 1

print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
int main(void){
  int a[100][100]={0},b[100]={0},c[100]={0},m,n,i,j;
  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++){
    for(j=0;j<m;j++)
      scanf("%d",&a[i][j]);
  }
  for(i=0;i<m;i++)
    scanf("%d",&b[i]);
  for(i=0;i<n;i++){
    for(j=0;j<m;j++)
      c[i]+=a[i][j]*b[j];
  }
  for(i=0;i<n;i++)
    printf("%d\n",c[i]);
  return 0;
}


Measured memory_bytes: 2772
using System;
using System.Collections;
using System.Linq;


public class Test
{	
	public static int min = 999999999;
	public static int target = 0;
	public static int n =0;
	public static int[] questions = new int[10];
	public static int[]  bonus = new int[10];
	public static void Main()
	{
		string[] str = Console.ReadLine().Split(' ');
		n = int.Parse(str[0]);
		target = int.Parse(str[1]);

		for(int i = 0 ; i < n ; i++)
		{
			str = Console.ReadLine().Split(' ');
			questions[i] = int.Parse(str[0]);
			bonus[i] = int.Parse(str[1]);
		}
		string s = "";
		tansaku(s);
		Console.WriteLine(min);
	}

	public static void tansaku(string s)
	{
		if(s.Length == n)
		{
			keisan(s);
		}
		else
		{
			tansaku(s+"1");
			tansaku(s+"0");
		}
	}

	public static void keisan(string s)
	{
		char[] c = s.ToCharArray();
		int cnt = 0;
		int a = 0;
		for(int i = 0 ; i < n ; i++ )
		{
		   
			if(c[i] == '1')
			{
				a += (questions[i]*(i+1)*100)+bonus[i];
	
				cnt += questions[i];
			}
		
		}
        
		for(int i = n-1 ; i >= 0 ; i--)
		{
		    if(c[i]=='0')
				{
				    int aa = 0;
				    while(target > a && aa< questions[i]){
    					a += ((i+1)*100);
    					aa ++;
    					cnt ++;
				    }
			        break;
				}
			
		}

         if(min > cnt && target <= a)
                  {
                   // Console.WriteLine(a);
            
                    min = cnt;
            
                  }
        
	}
}

Measured memory_bytes: 13140
masu = int(input())
height = list(map(int,input().split()))

count = 0
n = 0
for i in range(1,masu):
    if height[i-1] - height[i] >=0:
        n +=1
        if n >= count:
            count = n
    
    elif height[i-1] - height[i] < 0:
        if n >= count:
            count = n
        
        n = 0

print(count)

Measured memory_bytes: 15020
n=gets.to_i
s=gets.chomp.split('')
ma=0
for i in 1..n-1
  x=s[0..i-1].uniq
  y=s[i..n-1].uniq
  c=0
  for x in x
    if y.index(x)
      c+=1
    end
  end
  ma=[ma,c].max
end
puts ma
  

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

ll np(int a){
    ll ans=1;
    while(a>0){
        ans *= a;
        ans %= r;
        a--;
    }
    return ans;
}


int main(){
    int n,m;
    cin >> n >> m;
    if(abs(n-m) > 1){
        cout << 0 << endl;
    }
    else if(abs(n-m) == 1){
       cout <<(np(n)*np(m))%r << endl;
    }
    else{
        cout << (2*np(n)*np(m))%r << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using pchar = pair<char,char>;

int simulate(const string &s, const vector<pchar> &td, int pos) {
    for (auto c : td) {
        if (s[pos] != c.first) continue;
        if (c.second == 'L') --pos;
        else ++pos;
        if (pos < 0) return -1;
        if (pos >= (int)s.size()) return 1;
    }
    return 0;
}

int solve(const string &s, const vector<pchar> &td) {
    int N = (int)s.size();
    
    // 左側の境目
    int low = -1, high = N;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (simulate(s, td, mid) == 0) high = mid;
        else low = mid;
    }
    int left_fall = high;
    //cout << left_fall << endl;

    // 右側の境目
    low = -1, high = N;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (simulate(s, td, mid) == 0) low = mid;
        else high = mid;
    }
    int right_fall = N-1-low;
    //cout << right_fall << endl;
    
    return N - min(N, left_fall + right_fall);
}

int main() {
    int N, Q;
    string s;
    cin >> N >> Q >> s;
    vector<pchar> td(Q);
    for (int i = 0; i < Q; ++i) cin >> td[i].first >> td[i].second;
    cout << solve(s, td) << endl;
}


Measured memory_bytes: 900