akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define light ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i,a,b) for(ll i = a; i < b; i++)
#define REPE(i,a,b) for(ll i = a; i <= b; i++)
#define REPR(i,a,b) for(ll i = a; i >= b; i--)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define bins(v, x) binary_search(v.begin(), v.end(), x)
const double pi = 2*acos(0.0);
const int INF = 1e9+1;
const int MOD = 1e9+7;
const int MOD1 = 998244353;

using ll = long long;
using ld = long double;
using vi = vector<int>;

#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
 
ll modExp(ll base, ll exp, ll mod) {
   ll res = 1;
   while (exp > 0) {
    	if (exp % 2 == 1) {
        	res= (res * base) % mod;
		}
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}

ll inverse(ll base, ll exp, ll mod) {
   return modExp(base, exp - 2, mod);
}

bool compare(const pair<int,int> &i, const pair<int,int> &j) {
   return (i.S > j.S || (i.S == j.S && i.F > j.F));
}

void test() {
   ll N, W;
   cin >> N >> W;
   ll w[N+1], v[N+1];
   REP(i,1,N+1) cin >> w[i] >> v[i];
   
   ll dp[W+1][N+1];
   ll new_dp[W+1] = {-1};
   memset(dp, 0, sizeof(dp));

   for(int i = 1; i <= W; i++) {
      for(int j = 1; j <= N; j++) {
         if(w[j] <= i) {
            dp[i][j] = max(dp[i][j-1], dp[i-w[j]][j-1]+v[j]);
         } else {
            dp[i][j] = dp[i][j-1];
         }
         // cout << "dp" << i << j << ": " << dp[i][j] << " \n"[j == N];
      }

      for(int j = 1; j <= N; j++) {
         new_dp[i] = max(new_dp[i], dp[i][j]);
      }
      //cout << new_dp[i] << " ";
   }

   cout << new_dp[W];
}

int main() {
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   light;
   cout.precision(15);
   cout << fixed;

   int t = 1;
   //cin >> t;
   for(int i = 1; i <= t; i++) {
      //cout << "Case #" << i << ": ";
      test();
   }
   return 0;
}


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

n,w = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(n)]

dp = [[10**10] * (10**5 + 1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for j in range(10**5 + 1):
    for i in range(n):
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if j + wv[i][1] < 10**5 + 1:
            dp[i+1][j+wv[i][1]] = min(dp[i][j] + wv[i][0], dp[i][j+wv[i][1]])

for i in range(10**5,0,-1):
    if dp[-1][i] <= w:
        print(i)
        exit()


Measured memory_bytes: 121068
from collections import Counter

N = int(input())

Map = []
for i in range(N):
    x,y = list(map(int,input().split()))
    Map.append([x,y])

dif_list = []

for i in range(N):
    for j in range(N):
        if i!=j:
            dif_list.append(str(Map[i][0]-Map[j][0])+" "+str(Map[i][1]-Map[j][1]))


c = Counter(dif_list)

max_count = 0
#print(c)
for key in c.keys():
    max_count=max(c[key],max_count)

print(N-max_count)

Measured memory_bytes: 41328
// ref: https://img.atcoder.jp/abc096/editorial.pdf

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;
using namespace std;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

vector<int> prime_list(int size){
    vector<bool> v(size, true);
    v[0]=false;
    v[1]=false;
    
    for(int prime=2; prime<size;){
        for(int tmp=2*prime; tmp<size; tmp+=prime){ v[tmp]=false; }
        ++prime;
        while(prime<size && v[prime]==false){ ++prime; }
    }
    
    vector<int> vPrime;
    for(int i=0; i<size; ++i){
        if(v[i]){ vPrime.push_back(i); }
    }
    
    return vPrime;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N; cin >> N;
    vector<int> vPrime = prime_list(55555);
    
    for(int i=0, cnt=0; i<(int)vPrime.size() && cnt<N; ++i){
        if(vPrime[i] % 5 == 1){
            ++cnt;
            cout << vPrime[i] << ' ';
        }
    }
    cout << endl;
    
    return 0;
}

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

typedef long long ll;
typedef long double ld;

#define int long long 
#define rep(i, n) for(long long i = 0; i < (n); i++)
#define sqrt(d) pow((long double) (d), 0.50)

const ll INF = 2e9;
const ll large_P = 1e9 + 7;


signed main() {
	int N; cin >> N;
	string S, T;
	cin >> S >> T;

	rep(i, N) {
		cout << S.at(i) << T.at(i);
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

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

    vector<int> West(N+1,0); //左にWが何人いるか
    rep(n,1,N+1){
        if(S.at(n-1)=='W') West.at(n)=West.at(n-1)+1;
        else West.at(n)=West.at(n-1);
    }

    int ans=INT_MAX;
    rep(n,0,N){
        int _ans=0;
        if(n!=0) _ans+=West.at(n);
        if(n!=N-1) _ans+=(N-n-1)-(West.at(N)-West.at(n+1));
        ans=min(ans,_ans);
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 1796
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int sum = a + b + c;
    int max = a;
    if (max < b) max = b;
    if (max < c) max = c;
    int res = max * 3 - sum;
    if (res % 2 == 0) {
        cout << res / 2 << endl;
    } else {
        cout << (res + 3) / 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<cstring>

int main( ){
  char s[201],p[101],t[101];
  scanf("%s %s",s,p);
  strcpy(t,s);
  strcat(s,t);
  if(strstr(s,p)==NULL){
    printf("No\n");
  }else{
    printf("Yes\n");
  }
  return 0;
}

Measured memory_bytes: 2740
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 606
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

int n,m;
int ans[maxn][maxn];

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

int main(){
	n=read(); int pps=1;
	for (int x=1;x<n;x<<=1,++pps){
		for (int i=x+1;i<=(x<<1);i++)
			for (int j=i+1;j<=(x<<1);j++)
				ans[i][j]=ans[i-x][j-x];
		for (int i=1;i<=x;i++)
			for (int j=x+1;j<=(x<<1);j++)
				ans[i][j]=pps;
	}
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++)
			printf("%d ",ans[i][j]);
		puts("");
	}
    return 0;
}


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

//a >= b
long long gcd(long long a, long long b){
	if(b == 0) return a;
	else return gcd(b, a%b); 
}

long long lcm(long long a, long long b){
	long long g = gcd(a,b);
	return a / g * b;
}

long long lcms(vector<long long> t){
	int num = t.size();
	long long ans = t[0];
	for(int i = 1; i < num; i++)
	{
		ans = lcm(ans, t[i]);
	}
	return ans;
}

int main(){
	int n;
	cin >> n;
	vector<long long> t(n);
	for(int i = 0; i < n; i++)
	{
		cin >> t[i];
	}
	sort(t.begin(), t.end());
	
	cout << lcms(t) << endl;

	return 0;
}

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

using namespace std;

struct UnionFind {
    vector<int> par;
    int cnt;
    UnionFind(int size_) : par(size_, -1), cnt(size_) {}
    void unite(int x, int y) {
        if ((x = find(x)) != (y = find(y))) {
            if (par[y] < par[x]) swap(x, y);
            par[x] += par[y]; par[y] = x; cnt--;
        }
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
    int size(int x) { return -par[find(x)]; }
    int size() { return cnt; }
};

struct Edge {
    int src, dst, weight;
    Edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

int n, m;
Graph g;

bool check(int l, int r) {
    UnionFind uf(g.size());
    for (auto &es : g) {
        for (auto &e : es) {
            if (l <= e.weight && e.weight <= r) {
                uf.unite(e.src, e.dst);
            }
        }
    }
    return uf.size() == 1;
}

int solve() {
    int ans = 1e9;
    vector<int> ws;
    for (auto &es : g) {
        for (auto &e : es) {
            ws.emplace_back(e.weight);
        }
    }
    sort(ws.begin(), ws.end());
    ws.erase(unique(ws.begin(), ws.end()), ws.end());
    for (int i : ws) {
        int lb = i - 1;
        int ub = 10001;
        while (lb + 1 < ub) {
            int mid = (ub + lb) / 2;
            if (check(i, mid)) {
                ub = mid;
            } else {
                lb = mid;
            }
        }
        if (ub != 10001) {
            ans = min(ans, ub - i);
        }
    }
    return ans == 1e9 ? -1 : ans;
}

signed main() {
    while (cin >> n >> m && n) {
        g.assign(n, {});
        for (int i = 0; i < m; i++) {
            int a, b, w;
            cin >> a >> b >> w;
            --a, --b;
            g[a].emplace_back(a, b, w);
            g[b].emplace_back(b, a, w);
        }
        cout << solve() << endl;
    }
}

Measured memory_bytes: 3232
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
int sx, sy, gx, gy;

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> sx >> sy >> gx >> gy;
  gx -= sx;
  gy -= sy;
  FOR(i, 0, gy)cout << "U";
  FOR(i, 0, gx)cout << "R";
  FOR(i, 0, gy)cout << "D";
  FOR(i, 0, gx)cout << "L";
  cout << "L";
  FOR(i, 0, gy+1)cout << "U";
  FOR(i, 0, gx+1)cout << "R";
  cout << "D";
  cout << "R";
  FOR(i, 0, gy+1)cout << "D";
  FOR(i, 0, gx+1)cout << "L";
  cout << "U" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lol long long
using namespace std;
lol m[200005];
int main(){
  lol a,b,c,ans=0;
  string s;
  cin>>a>>b;
  for(int i=0;i<a;i++){
    cin>>m[i];
  }
  sort(m,m+a,greater<lol>());
  for(int i=b;i<a;i++){
    ans+=m[i];
  }
  cout<<ans<<"\n";
  return(0);
}


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

int main() {
	int a, n, i, m, k;
	cin >> n;
	m = n;
	while(n != 0) {
		k = 0;
		for(i = 1; i <= n; i++) {
			cin >> a;
			if (a <= 1) {
				m--;
			}
			if (a >= 1) {
				k++;
			}
		}
		if (m <= 0) {
			cout << "NA" << endl;
		}else{
			cout << k + 1 << endl;
		}
		cin >> n;
		m = n;
	}
}


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

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;


int d[201][201];
int n, m;
void warshall_floyd() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
}

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

	vector<int> root(r);
	for (int i = 0; i < r; i++) {
		int tmp;
		cin >> tmp;
		tmp--;
		root[i] = tmp;
	}
	sort(root.begin(), root.end());

	for (int i = 0; i < 201; i++) {
		for (int j = 0; j < 201; j++) {
			if (i==j) {
				d[i][j] = 0;
			}
			d[i][j] = INT_MAX/2;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		--a;
		--b;
		d[a][b]=d[b][a]=c;
	}
	warshall_floyd();

	int ans = INF;
	do
	{
		int tmp = 0;
		for (int i = 1; i < r; i++) {
//			cout << root[i-1] << " " << root[i]<< "-> " << d[root[i-1]][root[i]] << "\n";
			tmp += d[root[i-1]][root[i]];
		}
		ans = std::min(ans, tmp);
	} while (next_permutation(root.begin(), root.end()));

	cout << ans << "\n";
}


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

int main(){
int W, H, N;  cin >> W >> H >> N;
vector<int> a(N), x(N), y(N);
for (int i = 0; i < N; i++) {
    cin >> x[i] >> y[i] >> a[i];
}

int x_min = 0, x_max = W;
int y_min = 0, y_max = H;

for (int i = 0; i < N; i++) {
    if (a[i] == 1) {
        x_min = max(x_min, x[i]);
    } else if (a[i] == 2) {
        x_max = min(x_max, x[i]);
    } else if (a[i] == 3) {
        y_min = max(y_min, y[i]);
    } else if (a[i] == 4) {
        y_max = min(y_max, y[i]);
    }
}

cout << max(0, x_max - x_min)*max(0, y_max - y_min) << endl;
}


Measured memory_bytes: 256
n, m = list (map (int, input ().split ()))
d = [-1 for i in range (n + 1)]
flg = True

for i in range (m) :
    s, c = list (map (int, input ().split ()))
    if (flg) :
        if (d[s] != -1 and d[s] != c) :
            flg = False
            continue
        d[s] = c

if (d[1] == 0 and n > 1) :
    flg = False

if (flg and n > 1) :
    for i in range (1, n + 1) :
        if (d[i] == -1) :
            if (i == 1) :
                d[i] = 1
            else :
                d[i] = 0

if (n == 1 and d[1] == -1) :
    d[1] = 0

print (''.join (list (map (str, d[1:]))) if flg else "-1")

Measured memory_bytes: 3064
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
struct edge {
	int to;
	long long cost;
	int tp;
};
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
int W, H, N, x, y; long long dist[200009][2]; vector<pair<int, int> > xd[100009], yd[100009]; vector<edge> G[200009];
int main() {
	scanf("%d%d%d", &W, &H, &N);
	for (int i = 0; i < N; i++) {
		scanf("%d%d", &x, &y); x--, y--;
		xd[x].push_back(make_pair(y, i));
		yd[y].push_back(make_pair(x, i));
	}
	xd[0].push_back(make_pair(0, N));
	xd[W - 1].push_back(make_pair(H - 1, N + 1));
	yd[H - 1].push_back(make_pair(W - 1, N + 1));
	for (int i = 0; i < W; i++) {
		sort(xd[i].begin(), xd[i].end());
		for (int j = 1; j < xd[i].size(); j++) {
			int va = xd[i][j - 1].second, vb = xd[i][j].second, cost = xd[i][j].first - xd[i][j - 1].first;
			G[va].push_back(edge{ vb, cost, 0 });
			G[vb].push_back(edge{ va, cost, 0 });
		}
	}
	for (int i = 0; i < H; i++) {
		sort(yd[i].begin(), yd[i].end());
		for (int j = 1; j < yd[i].size(); j++) {
			int va = yd[i][j - 1].second, vb = yd[i][j].second, cost = yd[i][j].first - yd[i][j - 1].first;
			G[va].push_back(edge{ vb, cost, 1 });
			G[vb].push_back(edge{ va, cost, 1 });
		}
	}
	for (int i = 0; i < N + 2; i++) dist[i][0] = dist[i][1] = 1LL << 60; dist[N][0] = 0;
	priority_queue<edge> que; que.push(edge{ N, 0, 0 });
	while (!que.empty()) {
		edge u = que.top(); que.pop();
		for (edge e : G[u.to]) {
			long long cost = dist[u.to][u.tp] + e.cost + (u.tp != e.tp);
			if (dist[e.to][e.tp] > cost) {
				dist[e.to][e.tp] = cost;
				que.push(edge{ e.to, -cost, e.tp });
			}
		}
	}
	long long ret = min(dist[N + 1][0], dist[N + 1][1]);
	if (ret == 1LL << 60) ret = -1;
	printf("%lld\n", ret);
	return 0;
}

Measured memory_bytes: 46896
#include <iostream>

using namespace std;
using ll = long long;
using ld = long double;

#define ALL(x) begin(x), end(x)
#define REP(i, n) for (size_t i = 0, i##_len = (n); i < i##_len; ++i)

void solve(ll a, ll b, ll h) {
  cout << (a+b)*h/2 << endl;
}

int main() {
  ll a;
  cin >> a;
  ll b;
  cin >> b;
  ll h;
  cin >> h;
  solve(a, b, h);
  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  A - Sum of Two Integers
//
//  Created by Hashizo on 2019/11/09.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

int main(int argc, const char * argv[]) {
	ll ans = 0;

	ll n,m;
	cin >> n;

	m = n / 2;
	
	FOR(i, 1, (m+1)){
		if((n - i) > 0 && ((n-i) != i)) {
			ans++;
		}
	}
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define SIZE 200001

int main(){
    char s[SIZE],t[SIZE];
    scanf("%s",s);
    scanf("%s",t);
    int i=0;
    int ans=0;
    while(s[i]!='\0'){
        if(s[i]!=t[i]){
            ans++;
        }
        i++;
    }
    printf("%d\n",ans);
    return 0;
    
}

Measured memory_bytes: 2112
from bisect import bisect_right,bisect_left
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
an.sort()
ap.sort()
np,nn=len(ap),len(an)
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      cnt=0
      for i in range(nn):
        if mid%an[i]!=0:
          cnt+=np-bisect_left(ap,mid//an[i]+1)
        else:
          cnt+=np-bisect_left(ap,mid//an[i])
      #print(cnt)
      if cnt>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      cnt1,cnt2=0,0
      if np>=2:
        for i in range(np):
          cnt1+=bisect_right(ap,mid//ap[i])
          if ap[i]**2<=mid:
            cnt1-=1
      if nn>=2:
        for i in range(nn):
          cnt2+=bisect_right(an,mid//an[i])
          if an[i]**2<=mid:
            cnt2-=1
      if cnt1//2+cnt2//2>=k:
        ok=mid
      else:
        ng=mid
    print(ok)


Measured memory_bytes: 106196
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt() + 1;
		int [] t = new int [n];
		for(int i = 1; i < n; i++){t[i] = sc.nextInt();}
		int m = sc.nextInt() + 1;
		int [] p = new int [m];
		int [] x = new int [m];
		for(int i = 1; i < m; i++)
		{p[i] = sc.nextInt(); x[i] = sc.nextInt();}
		int goukei = 0;
		
		for(int i = 1; i < m; i++){
		for(int j = 1; j < n; j++){ goukei += t[j];}
		goukei = goukei + x[i] - t[p[i]];
		System.out.println(goukei);
		goukei = 0;
		}
		
	}
}

Measured memory_bytes: 10192
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,n) for(int i=a;i<n;i++)
#define M 1000000007
ll power(ll x, ll y, ll p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {   if (y & 1)
        res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
int main()
{
	IOS;
	int n;
	cin>>n;
	ll x=pow(n,3);
	cout<<x;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<sstream>
#include<cstring>
#include<vector>
using namespace std;

bool cmp1(const string& a,const string& b)
{
  int size_a,size_b;
  int start_a,start_b;
  start_a = start_b = 0;
  size_a = a.size(),size_b = b.size();
  if(a[0] == '0')
    for(int i=0;i<a.size() && a[i] == '0';i++)
      size_a--,start_a++;

  if(b[0] == '0')
    for(int i=0;i<b.size() && b[i] == '0';i++)
      size_b--,start_b++;

  if(size_a != size_b)
    return size_a < size_b;

  for(int i=0;i<size_a;i++)
    {
      if(a[start_a+i] != b[start_b+i])
	return a[start_a+i] < b[start_b+i];
    }
  return true;
}

bool cmp2(const string& a,const string& b)
{
  if(a.size() != b.size())
    return a.size() < b.size();
  for(int i=0;i<a.size();i++)
    {
      if(a[i] != b[i])
	return a[i] < b[i];
    }
  return true;
}

int main()
{

  int W,H;
  while(cin >> W >> H,W|H)
    {
     
      vector<vector<string> > G;
      G.resize(H);
      for(int i=0;i<H;i++)
	{
	  G[i].resize(W);
	  string line;
	  cin >> line;

	  for(int j=0;j<W;j++)
	    {
	      G[i][j] = line[j];
	    }
	}

      string G2[H][W];
      string ans = "";
      for(int i=0;i<H;i++)
	{
	  for(int j=0;j<W;j++)
	    {
	      if(isalpha(G[i][j][0]))
		continue;
	      //cout << i << " - " << j << endl;
	      G2[i][j] = max(G2[i][j],G[i][j],cmp1);
	      string A,B;
	      A = B = G2[i][j];
	      if(j-1 >= 0 && !isalpha(G[i][j-1][0]))
		A = max(G2[i][j],G2[i][j-1]+G2[i][j],cmp1);

	      if(i-1 >= 0 && !isalpha(G[i-1][j][0]))
		B = max(G2[i][j],G2[i-1][j]+G2[i][j],cmp1);
	      G2[i][j] = max(A,B,cmp1);
	      //cout << "G2[" << i << "][" << j << "] = " << G2[i][j] << endl;
	      ans = max(G2[i][j],ans,cmp1);
	      ans = max(A,ans,cmp1);
	      ans = max(B,ans,cmp1);
	    }
	}
    
      
      for(int i=0;i<ans.size()&&ans[i] == '0';i++)
	ans[i] = ' ';
      stringstream ss;
      ss << ans;
      ss >> ans;
      
     cout << ans << endl;

      }
    
  return 0;
}

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

int main() {
  int tmp,i;
  long int N,ans=0;
  cin>>N;
  string strN=to_string(N);
  for(tmp=0;tmp<(1<<(strN.size()-1));tmp++){
    bitset<9> s(tmp);
    long int L=0,w=1,copyN=N;
    for(i=0;i<strN.size()-1;i++){
      w*=10;
      if(s[i]){
        L+=copyN%w;
        copyN/=w;
        w=1;
      }
    if(i==strN.size()-2)L+=copyN;
   }
    //cout<<L<<endl;
    ans+=L;
  }
  if(ans==0)ans+=N;
  cout<<ans<<endl;
}


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

int main(){
	
	int n,m;
	scanf("%d %d",&n,&m);
	
	int arr[3];
	arr[0]=n+m;
	arr[1]=n-m;
	arr[2]=n*m;
	sort(arr,arr+3);
	printf("%d",arr[2]);
	return 0;
}




Measured memory_bytes: 256
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    d = i_input()
    c_list = i_list()
    s_list = i_row_list(d)

    for i in range(d):
        print(s_list[i].index(max(s_list[i]))+1)

if __name__ == '__main__':
    main()


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

int main() {
  int a1,a2,a3;
  cin >> a1;
  cin >> a2;
  cin >> a3;
  if (a1+a2+a3>=22){
    cout << "bust";
  }else{
    cout << "win";
  }
	return 0;
}


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

const int MAX = 510000;
const int MOD = 1000000007;

long long 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;
    }
}

// 二項係数計算
long long 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;
}

int main() {
    // 前処理
    COMinit();
  
  int N, K;
  cin >> N >> K;
  vector<int> a;
  
  for (int i = 0; i < N; i++) {
    int n;
    cin >> n;
    a.push_back(n);
  }
  sort(a.begin(), a.end());
  
  int ans = 0;
  
  for (int i = 0; i < N; i++) {
    ans = (ans + ((a[i] + MOD) % MOD * ((COM(i, K-1) - COM(N-i-1, K-1) + MOD) % MOD))) % MOD;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 12796
n = int(input())
L = []
A,B,C = [],[],[]
for _ in range(n):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    L.append([a,b,c])
if n ==1: print(max(L[0]));exit()

for i in range(1,n):
    A[i],B[i],C[i] = A[i]+max(B[i-1],C[i-1]),B[i]+max(A[i-1],C[i-1]),C[i] + max(A[i-1],B[i-1])

print(max(A[-1],B[-1],C[-1]))
    


Measured memory_bytes: 104812
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

fn main() {
    input! {
        n: usize,
        q: usize,
        s: chars,
        lrs: [(usize, usize); q],

    }
    let mut vals = vec![0; n];
    for i in (0..n).rev() {
        if i != n - 1 {
            vals[i] = vals[i + 1];
            if s[i] == 'A' {
                if s[i + 1] == 'C' {
                    vals[i] += 1;
                }
            }
        }
    }
    for (l, r) in lrs {
        println!("{}", vals[l - 1] - vals[r - 1]);
    }
}


Measured memory_bytes: 6908
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<iomanip>

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<int, int, lli> tiil;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

int main(){
	fast_io
	int n; cin>>n;
	cout<<n*n*n;
	
	return 0;
}

Measured memory_bytes: 256
x= {}
[*'a'..'z'].each{|s| x[s]=0}
while line = gets
    line.chomp.downcase.split('').each do |s|
        x[s] += 1 if x.has_key?(s)
    end
end
x.keys.sort.each do |key|
    puts "#{key} : #{x[key]}"
end




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

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

	int ans = 0;
	for (int i=1; i<=n; ++i) {
		string str = to_string(i);
		if (str.length() % 2 == 1) ans++;
	}
		
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) range(i,0,b)
#define rangei(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) rangei(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
    os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T>
ostream & operator << (ostream &os, tuple<T...> const &t){
    _ot<0>(os, t); return os;
}
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
                   << " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // #define endl '\n'
}
template<class T>
size_t uniq(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
    sort(l,l+n);
    return unique(l,l+n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/8;

const int MAX_D = 100010;
const int MAX_C = 30;

double dp[MAX_D][MAX_C]; // i日目にj回連続で得る確率
double ans[MAX_D];


int main(){
    memset(dp,0,sizeof(dp));
    memset(ans,0,sizeof(ans));
    dp[1][1] = 1;
    double cur = 0;
    for(int i = 1; i < MAX_D; i++){
        double p = 1;
        for(int j = 1; j < MAX_C; j++){
            cur += dp[i][j]*p;
            dp[i+1][j+1] += dp[i][j] * p;
            dp[i+1][1] += dp[i][j] * (1-p);
            p /= 2;
        }
        //rep(j,MAX_C) printf("%2.2lf ", dp[i][j]);
        //puts("");
        ans[i] = cur;
    }
    int n;
    while(scanf("%d", &n), n != 0){
        printf("%.10lf\n", ans[n]);
    }
}

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

typedef pair<int, int> P;
vector<P> x, y;
int n;
class Edge{
public:
        long long cost;
        int from, to;
        Edge(long long c, int f, int t){
                cost = c;
                from = f;
                to = t;
        }
};
vector<Edge> v;
bool operator < (const Edge &e, const Edge &f){
        return e.cost != f.cost ? e.cost < f.cost : e.from != f.from ? e.from < f.from : e.to < f.to;
}
class UnionFind{
public:
        vector<int> Parent;
        vector<int> Rank;
        UnionFind(int n){
                ++n;
                Parent.resize(n, 0);
                Rank.resize(n, 0);
                for(int i=0; i<n; ++i)
                        Parent[i] = i;
        }

        int find(int x){
                if(Parent[x] == x) return x;
                return Parent[x] = find(Parent[x]);
        }

        void unite(int x, int y){
                x = find(x);
                y = find(y);
                if(x == y) return;
                if(Rank[x] < Rank[y]) Parent[x] = y;
                else{
                        Parent[y] = x;
                        if(Rank[x] == Rank[y]) ++Rank[x];
                }
        }

        bool same(int x, int y){
                return find(x) == find(y);
        }
};

int main(){
//      cin.tie(0);
//      ios::sync_with_stdio(false);
        cin >> n;
        for(int i=0; i<n; ++i){
                int s, t;
                cin >> s >> t;
                x.push_back(P(s, i));
                y.push_back(P(t, i));
        }
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        for(int i=0; i<n-1; ++i){
                v.push_back(Edge(x[i+1].first - x[i].first, x[i].second, x[i+1].second));
                v.push_back(Edge(y[i+1].first - y[i].first, y[i].second, y[i+1].second));
        }
        sort(v.begin(), v.end());
//      for(auto e:v)
//              cout << e.cost << " " << e.from << " " << e.to << "\n";
        UnionFind uf(n);
        long long ans = 0;
        for(int i=0; i+1<v.size(); ++i){
                if(!uf.same(v[i].from, v[i].to)){
                        ans += v[i].cost;
                        uf.unite(v[i].from, v[i].to);
                }
        }
        cout << ans << "\n";
}

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

int main(void){
    int n;
    cin >> n;
    vector<char> s(n);
    for (int i=0; i<n; i++) cin >> s[i];
    int y = 0;
    for (auto x : s){
        if (x == 'Y') y++;
    }
    cout << (y == 0 ? "Three" : "Four") << endl;
    return 0;
}

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

def main():
    N = int(input())
    S = input()
    CNTR = 0
    CNTG = 0
    CNTB = 0
    for i in range(N):
        if S[i] == 'R':
            CNTR += 1
        if S[i] == 'G':
            CNTG += 1
        if S[i] == 'B':
            CNTB += 1
    CONB = CNTR * CNTG * CNTB
    CNT = 0
    for i in range(N):
        for j in range(i,N):
            if S[j] != S[i]:
                k = j + (j-i)
                if k > N-1:
                    continue
                if S[k] != S[i] and S[k] != S[j]:
                    CNT += 1
    print(CONB - CNT)


if __name__ == '__main__':
    main()

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

int main() {

	int a;
	int b;
	int c;
	int count =0;

	cin>>a>>b>>c;

	for(int i=a;i<=b;i++){


		if(c%i==0){
			count++;
		}




	}

	cout<<count<<endl;

	return 0;
}

Measured memory_bytes: 1164
import collections
import math
import operator as op
from functools import reduce
from collections import Counter
import numpy as np
import math
import bisect
import heapq

MOD = 1000000007


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def main():
    K = get_input(int)
    A, B = get_inputs(int)

    mul = K
    while mul <= B:
        if mul >= A and mul <= B:
            print("OK")
            return
        mul += K

    print("NG")


   

if __name__ == '__main__':
    main()


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

int main() {
    int n, m;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cin >> m;
    vector<int> b(m);
    for (int j = 0; j < m; ++j) cin >> b[j];
    if (n < m) {
        for (int i = 0; i < m - n; ++i) {
            a.emplace_back(0);
        }
    } else if (n > m) {
        for (int i = 0; i < n - m; ++i) {
            b.emplace_back(0);
        }
    }
    for (int k = 0; k < max(n, m); ++k) {
        if (a[k] < b[k]) {
            cout << 1 << endl;
            return 0;
        } else if (a[k] > b[k]) {
            cout << 0 << endl;
            return 0;
        }
    }
    if (n < m) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}



Measured memory_bytes: 3164
#include<bits/stdc++.h> 
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
const int mo=1e9+7,maxn=(1<<15)+5;
int n,m,i,j,k,s,num[maxn],cnt[maxn],g[maxn],p[16][maxn];
int f[maxn],two[400],ans;
int main(){
	scanf("%d%d",&n,&m);
	two[0]=1;
	fo(i,1,m){
		int a,b;
		scanf("%d%d",&a,&b);
		g[a]|=1<<b-1;
		two[i]=two[i-1]*2%mo;
	}ans=two[m];
	m=(1<<n)-1;
	fo(i,1,m) num[i]=num[i>>1]+(i&1);
	fo(j,1,n){
		s=g[j];
		fo(i,0,m) p[j][i]=num[i&s];
	}
	fo(i,0,m){
		int cn=0;
		fo(j,1,n) if (i&(1<<j-1)) cn+=p[j][i];
		cnt[i]=cn;
	}
	fo(i,0,m)if ((i&3)==3){
		int sum=1,an,t;
		for(j=i;j;j=(j-1)&i){
			s=i^j,an=1,t=0;
			if (!((s&3)==3||(j&3)==3)) continue;
			fo(k,0,n-1){
				if (j&(1<<k)) an=(ll)((1<<p[k+1][s])-1)*an%mo;	
				if (s&(1<<k)) t+=p[k+1][j];
			}
			an=(ll)an*two[t]%mo;
			if (j&3) (sum+=(ll)an*f[j]%mo)%=mo;else
			(sum+=(ll)an*two[cnt[j]]%mo)%=mo;
		}f[i]=sum;
	}
	printf("%d\n",(ans-f[m]+mo)%mo);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll a[114514];
int main() {
	ll n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=n-1;i>0;i--){
		if(a[i]<a[i-1]){
			if(a[i-1]-a[i]==1)a[i-1]--;
			else{
				cout<<"No"<<endl;
				return 0;
			}
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
struct obj{
	  int h,w;
	  obj(int hi, int wi){
			h = hi; w = wi;
	  }
	  bool operator < (const obj& tgt) const {
			if(h*h + w*w == tgt.h*tgt.h + tgt.w * tgt.w)
				  return h < tgt.h;
			return h*h + w*w < tgt.h*tgt.h + tgt.w * tgt.w;
	  }
	  bool operator > (const obj& tgt) const {
			if(h*h + w*w == tgt.h*tgt.h + tgt.w * tgt.w)
				  return h > tgt.h;
			return h*h + w*w > tgt.h*tgt.h + tgt.w * tgt.w;
	  }
};

int main(){

	  while(1){
			int h,w; cin >> h >> w;
			if(!h and !w) break;
			vector<obj> list;
			for(int i=1; i<=200; i++){
				  for(int j=1; j<=200; j++){
						if(j>i)
							  list.push_back( obj(i,j) );
				  }
			}
			sort(list.begin(),list.end());
			obj ans = *++lower_bound(list.begin(),list.end(), obj(h,w));
			cout << ans.h << " " <<  ans.w << endl;

	  }
	  
}

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

if __name__ == '__main__':
    cnt = 0
    for i in range(N):
        for j in range(N-1, i, -1):
            if j > 0 and A[j-1] > A[j]:
                A[j-1], A[j] = A[j], A[j-1]
                cnt += 1
    print(" ".join(map(str, A)))
    print(cnt)


Measured memory_bytes: 5600
import java.util.Scanner;

 
public class Main {
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long k = sc.nextLong();
		
		long rest = n % k;
		long num = k - rest;

		long ans = Math.min(rest, num); 
		System.out.println(ans);
		sc.close();
	}
	
}

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

#define REP(n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main()
{
  int N, K, Q;
  cin >> N >> K >> Q;
  int A[Q];
  int res[N];
  REP(N) res[i] = 0;
  REP (Q)
  {
    int a;
    cin >> a;
    res[a - 1]++;
  }
  REP (N) cout << (Q - res[i] < K ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3960
#include <stdio.h>

void BubbleSort(int A[],int N){
    int flag = 1,i,j,temp,count=0;
    while(flag){
        flag=0;
        for(j=N-1;0<j;j--){
            if(A[j]<A[j-1]){
                temp=A[j];
                A[j]=A[j-1];
                A[j-1]=temp;
                
                flag=1;
                count++;
            }
        }
    }
    for(i=0;i<N;i++){
        printf("%d",A[i]);
        if(i<N-1) printf(" ");
    }
    printf("\n%d\n",count);
}

int main(){
    int i,N;
    scanf("%d",&N);
    int A[N];
    for(i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    BubbleSort(A,N);
    return 0;
}

Measured memory_bytes: 1808
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
int main(void){
  int n,sn=0;
  scanf("%d",&n);
  int tmp=n;
  while(tmp!=0){
    sn+=tmp%10;
    tmp/=10;
  }
  if(n%sn==0) printf("Yes");
  else printf("No");
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;


namespace io{
    const int L = (1 << 20) + 1;
    
    char buf[L], *S , *T, c;
     
    char getchar() {
        if(S == T) {
            T = (S = buf) + fread(buf, 1, L, stdin);
            return (S == T ? EOF : *S++);
        }
        return *S++;
    }
    
    int inp() {
        int x = 0, f = 1; char ch;
        for(ch = getchar(); !isdigit(ch); ch = getchar())
            if(ch == '-') f = -1;
        for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
        return x * f;
    }
    
    ll inp_ll() {
        ll x = 0; int f = 1; char ch;
        for(ch = getchar(); !isdigit(ch); ch = getchar())
            if(ch == '-') f = -1;
        for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
        return x * f;
    }
    
    char B[25], *outs=B+20, *outr=B+20;
    template<class T>
    inline void print(register T a,register char x=0){
        if(x) *--outs = x, x = 0;
        
        if(!a)*--outs = '0';
        else 
            while(a)
                *--outs = (a % 10) + 48, a /= 10;
        
        if(x)
            *--outs = x;
        
        fwrite(outs, outr - outs , 1, stdout);
        outs = outr;
    }
};

using io :: print;
using io :: inp;
using io :: inp_ll;

const int maxN = 5010;
const int MOD = 1e9 + 7;
ll f[maxN][maxN];
ll val[maxN];
ll g[maxN];
vector<int> path[2*maxN];
int pre[maxN];
int size[maxN]; 
int n;
void dfsa(int x,int p)
{
	size[x] = 1;
	for(auto y: path[x])
	{
		if(y == p) continue;
		pre[y] = x;
		//size[y] ++;
		dfsa(y,x);
		size[x] += size[y];
	}
}

void dfsb(int x,int p)
{
	for(auto y:path[x])
	{
		if(pre[y] == x)
			dfsb(y,x);
	}
	f[x][1] = 1;
	int len = 1;
	for(auto y:path[x])
	{
		if(pre[y] != x) continue;
		for(int i=1;i<=len;i++)
		{
			g[i] = f[x][i];
			f[x][i] = 0;
		}
		for(int i=1;i<=len;i++)
		{
			for(int j=1;j<=size[y];j++)
			{
				f[x][i+j] = (f[x][i+j] + g[i] * f[y][j] %MOD)%MOD;
				if(j%2 == 0)
					f[x][i] = (f[x][i] + MOD - (g[i]*f[y][j]%MOD )*val[j/2]%MOD ) %MOD;
			}
		}
		len += size[y];
	}
}
int main()
{
	n = inp();
	for(int i=1;i<n;i++)
	{
		int u,v;
		u = inp();
		v = inp();
		path[u].push_back(v);
		path[v].push_back(u);
	}
	val[0] = 1;
	for(int i=1;i<=n;i++)
	{
		val[i] = val[i-1]*(2*i-1)%MOD;
	}
	dfsa(1,0);
	dfsb(1,0);
	ll ans = 0;
	for(int i=1;i<=n;i++)
	{
		if(i%2 == 0)
		{
			ans = (ans + f[1][i] * val[i/2] %MOD) %MOD;
		}
	}
	printf("%lld\n",ans);
    return 0;
}

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

int     FF(int N, vector<int> &W, int idW, int minC) {
        if (0==N) return 0;
        if (0>=minC) return minC;
        int C=0;
        if (0==idW) return min(minC, N);
        if (N>=W.at(idW)) {
                int C=1;
                C += FF(N-W.at(idW), W, idW, minC-C);
                minC=min(minC, C);
        }
        return FF(N, W, idW-1, minC);
}

int     main() {
        vector<int> W(0);
        W.push_back(1);
        int S=6;
        while (S<100000) {
                W.push_back(S);
                S *= 6;
        }
        S=9;
        while (S<100000) {
                W.push_back(S);
                S *= 9;
        }
        sort(W.begin(), W.end());
        int N;
        cin >>N;
        cout <<FF(N, W, W.size()-1, N) <<endl;
        return 0;
};

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=1e5+233;
int a[N];
int sum=0,sum1=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]%4==0)sum++;
		if(a[i]%2==0&&a[i]%4!=0)sum1++;
	}
	bool p=true;
	if(sum1>1)
	{
		n-=sum1;
		p=false;
	}
	if(n%2==1&&p==false)n++;
	if(sum>=n/2)printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 640