akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
using pi = pair <ll, ll>;
int f[N];
int val[N * 4];
int pre[N];
int n, m;
string s;
inline int mn(int x, int y)
{
	if (x < 0)
		return y;
	if (y < 0)
		return x;
	return f[x] < f[y] || (f[x] == f[y] && x < y) ? x : y;
}
inline void Ckmin(int& x, int y)
{
	x = mn(x, y);
}
void amend(int x, int rt = 1, int L = 1, int R = n + 2)
{
	if (L == R - 1 && x == L)
	{
		Ckmin(val[rt], x);
		return ;
	}
	if (x < (L + R) / 2)
		amend(x, rt * 2, L, (L + R) / 2);
	else
		amend(x, rt * 2 + 1, (L + R) / 2, R);
	Ckmin(val[rt], mn(val[rt * 2], val[rt * 2 + 1]));
}
int query(int l, int r, int rt = 1, int L = 1, int R = n + 2)
{
	if (l <= L && R <= r)
		return val[rt];
	int res = -1;
	if (l < (L + R) / 2)
		Ckmin(res, query(l, r, rt * 2, L, (L + R) / 2));
	if ((L + R) / 2 < r)
		Ckmin(res, query(l, r, rt * 2 + 1, (L + R) / 2, R));
	return res;
}
inline void modify(int x, int v)
{
	if (v >= f[x])
		return ;
	f[x] = v;
	amend(x);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> s;
	memset(val, -1, sizeof(val));
	memset(f, 0x3f, sizeof(f));
	modify(1, 0);
	for (int i = 2; i <= n + 1; ++i)
	{
		if (s[i - 1] == '1')
			continue;
		int t = query(max(1, i - m), i);
		pre[i] = t;
		modify(i, f[t] + 1);
	}
	vector <int> ans;
	for (int i = n + 1; i > 1; i = pre[i])
	{
		if (i - pre[i] > m)
		{
			cout << -1;
			return 0;
		}
		ans.emplace_back(i - pre[i]);
	}
	for (auto i = ans.rbegin(); i != ans.rend(); ++i)
		cout << *i << ' ';
}


Measured memory_bytes: 3404
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

string s[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> s[i];

  int cnt[5] = {};
  REP(i, n) {
    if(s[i][0]=='M') cnt[0]++;
    else if(s[i][0]=='A') cnt[1]++;
    else if(s[i][0]=='R') cnt[2]++;
    else if(s[i][0]=='C') cnt[3]++;
    else if(s[i][0]=='H') cnt[4]++;
  }

  int ret = 0;
  REP(i, 5) FOR(j, i+1, 5) FOR(k, j+1, 5) {
    ret += cnt[i]*cnt[j]*cnt[k];
  }

  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 6144
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader vf = new BufferedReader(new InputStreamReader(System.in));

		String aou = vf.readLine();

		int f = aou.indexOf("A");

		StringBuffer sb = new StringBuffer(aou);
		StringBuffer eou = sb.reverse();

		int e = eou.indexOf("Z");

		int o = aou.length() - f - e;

		System.out.println(o);

	}

}


Measured memory_bytes: 27220
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<map>
#include<list>

using namespace std;

#define in(s) cin >> s
#define out(s) cout << s << endl
#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define MOD 1000000007
#define MAX 300001

#define IMIN INT_MIN;
#define IMAX INT_MAX;

int main(){
    ll N;
    in(N);
    vector<ll> a(N, 0);
    rep(i, N) in(a[i]);
    vector<ll> counter(N+1, 0), answer(N+1, 0);
    rep(i, N) {
        counter[a[i]]++;
    }
    ll sum = 0;
    rep(i, N+1) {
        if (counter[i] > 1)
            answer[i] = counter[i] * (counter[i]-1) / 2;
        else answer[i] = 0;
        sum += answer[i];
    }
    ll ans;
    rep(i, N) {
        ans = sum - counter[a[i]] * (counter[a[i]]-1) / 2 + (counter[a[i]] - 1) * (counter[a[i]] - 2) / 2;
        out(ans);
    }


	return 0;
}


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

using namespace std;

int main() {
  int n;
  cin >> n;
  double res = 0.0;
  for (int i = 0; i < n; i++) {
    double num;
    string d;
    cin >> num >> d;
    if (d == "BTC") {
      num *= 380000.0;
    }
    res += num;
  }
  cout << fixed << setprecision(10) << res << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<ll, ll> ump;
typedef pair<ll, ll> P;

ump mp;

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = ump();
#pragma clang diagnostic pop
#endif
        int a, b, k;
        cin >> a >> b >> k;
        int ans = 0;
        for (int i = min(a, b); i >= 1; --i) {
            if (a % i == 0 && b % i == 0 && k >= 1) {
                ans = i;
                k--;
            }
        }
        cout << ans << endl;

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
num_1 , num_2 , num_3, loops = input().split()
num_1 = int(num_1)
num_2 = int(num_2)
num_3 = int(num_3)
loops = int(loops)

if abs(num_1 - num_2) > (10**18):
    print('Unfair')

elif (loops % 2) == 0:
    print(num_1 - num_2)

elif (loops % 2) == 1:
    print(num_2 - num_1)


Measured memory_bytes: 3060
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i32; n],
    }

    let to = ((a.iter().sum::<i32>() as f64) / n as f64).round() as i32;
    let mut ans = 0;
    for i in &a {
        ans += (i - to).pow(2);
    }
    println!("{}", ans);
}


Measured memory_bytes: 2600
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back 
#define mod 1e9+7
const ll INF = 1e18L + 5;
int main(){
      ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
       ll n,wt;
        cin>>n>>wt;
         
        
		  ll v[n],w[n],sum=0;
		  for(int i=0; i<n; i++)
		   {cin>>w[i]>>v[i]; sum+=v[i];
			   }
		   vector<ll >dp(sum+1,INF);
		     dp[0]=0;
		   for(int j=0; j<n ;j++){			   
		  for(ll  i=sum-v[j]; i>=0 ; i--){
		     dp[i+v[j]]=min(dp[i+v[j]],dp[i]+w[j]);
		  }
		 // for(int i=0; i<=sum; i++)
		   // cout<<dp[i]<<"  ";
		  //  cout<<endl;
	  }  
	   ll mn=0;
		  for(ll i=0; i<=sum; i++)
		   {  if(dp[i]<=wt)
			    mn=max(i,mn);
		      }
		      cout<<mn<<endl;
		
         
    }

// a  A  z  Z  q  Q  !  1 


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Text;

class Program
{
	static void Main(string[] args)
	{
		string[] input = Read();
		int n = int.Parse(input[0]);
		input = Read();
		int cnt = 0;
		for(int i=0; i<n; i++) 
		{
			int a = int.Parse(input[i]);
			if(i%2==0 && a%2!=0) cnt++;
		}
		Write(cnt);
	}

	static string[] Read()
	{
		return Console.ReadLine().Split(' ');
	}

	static void Write(object o)
	{
		Console.WriteLine(o.ToString());
	}
}


Measured memory_bytes: 27540
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#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>

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 pb(a) push_back
#define print(x) cout<<(x)<<endl
#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 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;
const int MOD = 1e9 + 7; const int MAX = 500050;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 2e18;


double dist(double x1, double x2, double y1, double y2) {
	return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
double dist(P &p1, P &p2) {
	double x1 = p1.first, x2 = p2.first, y1 = p1.second, y2 = p2.second;
	return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}


void solve() {
	int a, b; cin >> a >> b;
	if (a > b)swap(a, b);
	REP(i, b)cout << a;
	cout << endl;
}

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




Measured memory_bytes: 256
#include<bits/stdc++.h>
    using namespace std;
    int cnt[3];
    int main()
    {
      int N,A,B;
      cin>>N>>A>>B;
      for(int i=0;i<N;i++)
      {
        int x;
        cin>>x;
        if(x<=A) cnt[0]++;
        else if(x<=B) cnt[1]++;
        else cnt[2]++;
      }
      cout<<min(min(cnt[0],cnt[1]),cnt[2]);
      return 0;
    }

Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<end

int main(void) {
	string s;
	cin>>s;
	ll k;
	cin>>k;
	ll index = 0;
	rep(i,0,s.sz){
		if(s[index]!='1')break;
		index++;
	}
	if(index==s.sz){
		cout << 1 << endl;
	}
	else if(index<k){
		cout << s[index] << endl;
	}
	else{
		cout << 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=[k for k in p_dp]
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


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

using ll = long long int;
using P = std::pair<int, int>;

#define rep(i, n) for (int i = 1; i <= n; ++i)

int main()
{
    int n;
    ll k;
    std::cin >> n >> k;

    int m = 0;
    for (ll x = 1; x <= k; x *= 2)
    {
        ++m;
    }

    std::vector<std::vector<int>> vis(m, std::vector<int>(n + 1));

    rep(i, n)
    {
        std::cin >> vis[0][i];
    }

    rep(i, m - 1)
    {
        rep(j, n)
        {
            vis[i][j] = vis[i - 1][vis[i - 1][j]];
        }
    }

    ll x = 1;

    int ans = 1;

    rep(i, 60)
    {
        if (k & x)
            ans = vis[i - 1][ans];
        x *= 2;
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 51024
#include <stdio.h>
#include <stdlib.h>

#define MAX_P 100000 * 10000

typedef long long llong;

int isLoad(llong *ws, int n, int k, llong p)
{
    int i = 0, j, w_sum;

    for(j = 0; j < k; j++) {
        w_sum = 0;
        while(w_sum + ws[i] <= p) {
            w_sum += ws[i];
            i++;
            if(i == n) return n;
        }
    }
    return i;
}

llong getP(llong *ws, int n, int k)
{
    int v;
    llong left = 0;
    llong right = MAX_P;
    llong mid;
    while(right - left > 1) {
        mid = (left + right) / 2;
        v = isLoad(ws, n, k, mid);
        if(v >= n) right = mid;
        else left = mid;
    }

    return right;
}

int main(void)
{
    int i, n, k, w;
    llong ans, *ws;

    scanf("%d %d", &n, &k);
    ws = malloc(sizeof(llong) * n);
    for(i = 0; i < n; i++) {
        scanf("%d", &w);
        ws[i] = w;
    }
    ans = getP(ws, n, k);
    printf("%lld\n", ans);

    return 0;
}

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

using namespace std;

int main(){
    int a,b,c,d,e;
    cin >> a >> b >> c >> d >> e;
    if(a==0) cout << 1 << endl;
    else if(b==0) cout << 2 << endl;
    else if(c==0) cout << 3 << endl;
    else if(d==0) cout << 4 << endl;
    else cout << 5 << endl;  
}

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

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

  vector<int> a(1000001);

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

  for (int i = 1; i <= 1000000; i++) {
    if (a[i] != 0) {
      for (int j = (a[i] > 1 ? i : i + i); j <= 1000000; j += i) {
        a[j] = 0;
      }
    }
  }

  int ans = count_if(begin(a), end(a), [](auto a){return a != 0;});
  cout << ans << endl;
}


Measured memory_bytes: 7224
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <limits>
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1234567890123456;

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

#define in cin
#define out cout
#define pb push_back
using namespace std;

vector<ll>a;
int dp[1000000], oddp[1000000];

int main(){
	int n;

	REP(i,1000000) {
		dp[i] = i;
		oddp[i] = i;
	}
	int c=0;
	for (int a = 2;  c<1000000; ++a) {
		c = (a*(a + 1)*(a + 2)) / 6;
		if (c > 1000000)break;
		for (int i = 0; i <= 1000000; ++i) {
			if (i - c < 0)continue;

			dp[i] = min(dp[i], dp[i - c] + 1);
			if (c % 2 == 1) {
				oddp[i] = min(oddp[i], oddp[i - c] + 1);
			}
		}

	}
	while (in >> n) {
		if (!n) break;
		out << dp[n] << ' ' << oddp[n] << endl;
	}
	return 0;

}

Measured memory_bytes: 10808
#include <bits/stdc++.h>
using namespace std;
string x,y;
int main()
{
	cin>>x;
	y=x;
	reverse(y.begin(),y.end());
	for(int i=0;i<x.size();i++)
		switch(x[i])
		{
			case 'b':{x[i]='d';break;}
			case 'd':{x[i]='b';break;}
			case 'p':{x[i]='q';break;}
			default: x[i]='p';
		}
	if(x==y) cout<<"Yes";
	else cout<<"No";
    return 0;
}

Measured memory_bytes: 512
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int X[] = new int[N];
		int Y[] = new int[N];
		int i;
		for (i = 0; i < N; i++) {
			X[i] = sc.nextInt();
			Y[i] = X[i];
		}

		Arrays.sort(Y);
		for (i = 0; i < N; i++) {
			if (X[i] <= Y[(N / 2) - 1]) {
				System.out.println(Y[(N / 2)]);
			} else {
				System.out.println(Y[(N / 2) - 1]);
			}

		}
	}
}


Measured memory_bytes: 85792
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;



int main() {  
  double n; cin >> n;
  cout << (180-360/n)*n << endl;

  return 0;
}


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

std::vector< int > route;
int N, M;
std::string S;

bool routefind(int pos){
    if(pos < 0){
        return false;
    }else if(S[pos] == '1'){
        return false;
    }else if(pos == 0){
        return true;
    }else{
        for(int i=M; i>0; i--){
            int tmp = routefind(pos - i);
            if(tmp){
                route.push_back(i);
                return true;
            }
        }
    }
    return false;
}

int main(){
    std::cin >> N >> M >> S;
    
    int continuous = 0;
    for(int i=0; i<=S.size(); i++){
        if(S[i] == '1'){
            continuous++;
            if(continuous == M){
                std::cout << -1 << std::endl;
                return 0;
            }
        }else{
            continuous = 0;
        }
    }
    
    bool tmp = routefind(N);
    
    for(int i=0; i<route.size()-1; i++){
        std::cout << route[i] << " ";
    }
    std::cout << route[route.size()-1] << std::endl;
    
    
    return 0;
    
}


Measured memory_bytes: 8620
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define ull unsigned long long
#define FI(i,a,n) for(int i=a; i<=n; i++)
#define RFI(i,n,a) for(int i=n; i>=a; i--)
#define FLL(i,a,n) for(ll i=a; i<=n; i++)
#define RFLL(i,n,a) for(ll i=n; i>=a; i--)
#define vi vector<int>
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#define pll pair<ll,ll>
#define pi pair<int, int>
#define GCD(a,b) __gcd(a,b)
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define debug(x) cout << x << endl
#define MOD 1000000007
#define INF LLONG_MAX
#define PI 3.14159265359
using namespace std;


int main()
{
	fastio
  int k;
  string s;
  cin >> k >> s;
  if(s.length() <=k ) cout << s;
  else cout << s.substr(0, k) + "...";
	return 0;
}






Measured memory_bytes: 3640
from math import factorial
def nCk(n,k,mod=10**9+7):
    if n<k or k<0 or n<0:return 0
    return fact[n]*inv[n-k]*inv[k] % mod

mod = 10**9+7
n=int(raw_input())
a=map(int,raw_input().split())
cnt=[0]*(n+1)
for i in xrange(n+1):
    cnt[a[i]]+=1
dnum=0
for i in xrange(n+1):
    if cnt[i]==2:
        dnum=i
        break
idx=[]
fact=[0]*(n+5)
fact[0]=1
inv=[0]*(n+5)
inv[n+1]=pow(factorial(n+1), mod - 2, mod)
for i in xrange(n+1):
    fact[i+1] = (i+1)*fact[i]%mod
for i in xrange(n, -1, -1):
    inv[i] = inv[i+1]*(i+1)%mod
for i in xrange(n+1):
    if dnum==a[i]:
        idx.append(i)

y=n-idx[1]
x=idx[0]

for i in xrange(n+1):
    #print nCk(y,i)
    print (nCk(n+1, i+1) - nCk(x+y,i))%mod


Measured memory_bytes: 58092
#include <bits/stdc++.h>
using namespace std;
int main(){
	string a,b,c1;
	cin>>a>>b;
	int c2=0,i;
	c1=a+b;
	for(i=0;i<c1.length();i++) c2*=10,c2+=c1[i]-48;
	for(i=0;i*i<=c2;i++)
		if(i*i==c2){
			cout<<"Yes";
			return 0;
		}
	cout<<"No";
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
    int a,b,K;
    char op;
    while(1){
        cin>>a>>op>>b;
        if (op=='?') break;
        if (op=='+') cout<<a+b<<endl;
        else if(op=='-') cout<<a-b<<endl;
        else if(op=='*') cout<<a*b<<endl;
        else if(op=='/') cout<<a/b<<endl;
    }
    return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
  	cin.tie(0);
  	int n;cin>>n;
  	int ans =0, c=0;
  	for(int i=0; i<=1000000; i++){
    	c+=7;
      	c%=n;c*=10;
      	ans++;
      	if(c==0){
        	break;
        }
    }
  	if(c==0)cout<<ans<<"\n";
  	else cout<<-1<<"\n";
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 200005
#define MX 2100
using namespace std;
lo int n,x,y,A[li],B[li],fac[10005],inv[10005],f[MX*2+1005][MX*2+1005];
lo int ans;
lo int pw(lo int a,lo int b){
	if(b==0) return 1;
	if(b==1) return a%md;
	lo int t=pw(a,b/2);
	t=((t%md)*(t%md))%md;
	if(b%2==1) t=((t%md)*a)%md;
	return t;
}
lo int comb(lo int a,lo int b){
	return (((fac[a]%md)*(inv[b]%md)%md)*(inv[a-b]%md))%md;
}
int main(){
	fac[0]=1;
	for(int i=1;i<=8500;i++){
		fac[i]=fac[i-1]*i%md;
	}
	inv[0]=1;
	for(int i=1;i<=8500;i++){
		inv[i]=pw(fac[i],md-2);
	}
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld %lld",&A[i],&B[i]);
		f[MX-A[i]][MX-B[i]]++;
	}
	for(int i=1;i<=n;i++){
		ans=(ans%md-comb(2*A[i]+2*B[i],2*A[i])+md)%md;
	}
	for(int i=1;i<=2*MX;i++){
		for(int j=1;j<=2*MX;j++){
			f[i][j]=(f[i][j]%md+f[i-1][j]%md)%md;
			f[i][j]=(f[i][j]%md+f[i][j-1]%md)%md;
		}
	}
	for(int i=1;i<=n;i++){
		ans=(ans%md+f[A[i]+MX][B[i]+MX]%md)%md;
	}
	printf("%lld\n",(ans%md)*pw(2,md-2)%md);
	return 0;
}


Measured memory_bytes: 176000
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
static const ll mod=1000000007;
ll modpow(ll x,ll y){
if(y==0){
return 1;
}else if(y%2==0){
ll z=modpow(x,y/2);
  return (z*z)%mod;
}else{
ll z=modpow(x,y/2);
  return (x*((z*z)%mod))%mod;
}
}
ll N,A,B;
ll dp[2][5005][5005];
ll sum[5005];
int main(){
  cin>>N>>A>>B;
  if(A<B)swap(A,B);
  dp[1][0][0]=1;dp[0][0][0]=0;sum[0]=1;
  for(ll i=1;i<=N;i++){
    for(ll j=0;j<=min(i,A-1);j++){
    if(j!=0){
    dp[1][i][j]=(dp[1][i-1][j-1]+dp[0][i-1][j-1])%mod;
      if(B<j)
      dp[0][i][j]=dp[0][i-1][j-1];
      if(0<=j-B)
        dp[0][i][j]=(dp[0][i][j]+dp[1][i-B][j-B])%mod;
     
    }else{
   dp[0][i][0]=(sum[i-1]+dp[0][i-1][0])%mod;
      if(0<=i-B)
        dp[0][i][0]=(dp[0][i][0]-sum[i-B]+mod)%mod;
    
    }
    
    
    }ll a=0;
    for(ll j=0;j<=A-1;j++)
      a=(a+dp[1][i][j])%mod;
    sum[i]=a;
  }ll ans=0;
  for(ll j=0;j<=A-1;j++)
    ans=(ans+dp[1][N][j]+dp[0][N][j])%mod;
  ans=(mod-ans)%mod;
  ans+=modpow(2,N);ans%=mod;
  cout<<ans<<endl;
  return 0;
}

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

int main(){
  int i,j,n,m;
  cin >> n >> m;
  vector<int> a(m),b(10);
  b[1]=2;b[2]=5;b[3]=5;b[4]=4;
  b[5]=5;b[6]=6;b[7]=3;b[8]=7;b[9]=6;
  for(i=0;i<m;i++)cin >> a[i];
  long long int dp[n+1]={};
  for(i=1;i<=n;i++)dp[i]=-1000000;
  for(i=1;i<=n;i++){
    for(j=0;j<m;j++){
      if(i-b[a[j]]>=0)dp[i]=max(dp[i],dp[i-b[a[j]]]+1);
    }
  }
  //cout << dp[n] << endl;
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  while(n>0){
    for(i=0;i<m;i++){
      if(n==0)break;
      if(n-b[a[i]]>=0&&dp[n]-1==dp[n-b[a[i]]]){
        cout << a[i];
        n-=b[a[i]];
        i=-1;
      }
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 384
def solve(N, ABCs):
    ans = [ABCs[0]]
    for i in range(1, N):
        ans.append([
            max(ans[i - 1][1], ans[i - 1][2]) + ABCs[i][0],
            max(ans[i - 1][0], ans[i - 1][2]) + ABCs[i][1],
            max(ans[i - 1][0], ans[i - 1][1]) + ABCs[i][2],
        ])
    return max(ans[-1])

if __name__ == "__main__":
    N = int(input())
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABCs))


Measured memory_bytes: 40256
// Rotate 3*3
// * frank_c1
// * 2017 / 12 / 18
 
#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) ((x) & (-x))

const int maxn = (int)(1e5) + 5;
int a[maxn][3], C[2][maxn], f[2], c[2];
int n;

inline int sum(int p, int x) {
	int ret = 0;
	for (; x; x -= lowbit(x)) ret ^= C[p][x];
	return ret;
}

inline void add(int p, int x) {
	for (; x <= n; x += lowbit(x)) C[p][x] ^= 1;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%d", &a[j][i]);
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		if (a[i][0] + 1 == a[i][1] && a[i][1] + 1 == a[i][2] && a[i][2] % 3 == 0 && ((a[i][2] / 3 - i) & 1)) {
			c[i & 1] ^= sum(i & 1, a[i][2] / 3); add(i & 1, a[i][2] / 3);
		} else if (a[i][0] - 1 == a[i][1] && a[i][1] - 1 == a[i][2] && a[i][0] % 3 == 0 && ((a[i][0] / 3 - i) & 1)) {
			f[i & 1] ^= 1;
			c[i & 1] ^= sum(i & 1, a[i][0] / 3); add(i & 1, a[i][0] / 3);
		} else return printf("No\n"), 0;
 	}
	return f[0] == c[1] && f[1] == c[0] ? printf("Yes\n") : printf("No\n"), 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define llu unsigned long long 
#define pb push_back
#define loop(x) for(int i=0;i<x;i++)
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
#define dd fflush(stdout)
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mt make_tuple //use tie
#define eb emplace_back
typedef tuple<int,int,int> State;//use in dijkstra
ll mod=1e9+7;
// ll power(ll x,ll y,ll mod){
//  ll ans=1;
//  while(y>0){
//   if(y&1){
//     ans=ans*x;
//   }
//   x=x*x;
//   y=y/2;
//  }
//  return ans;
// }
ll INF = (1<<30LL);
int main(){
    IOS;  
      int n;
      ll ww;
      cin>>n>>ww;
      ll w[n+4];
      ll v[n+4];
      for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
      int sum=0;
    for(int i=1;i<=n;i++)
      sum+=v[i];
      ll dp[n+4][sum+4];
      for(int i=0;i<=n;i++){
        if(i==0)
        {
        for(int j=0;j<=sum;j++){
          if(j==0)
            dp[i][j]=0;
          else
            dp[i][j]=INF;
        }
       }
       else
       {
        for(int j=0;j<=sum;j++){
          if(j>=v[i]){
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
          }          
          else
             dp[i][j]=dp[i-1][j];
        }   
      }
     }
     ll ans=0;
     for(int i=0;i<=sum;i++){
      if(dp[n][i]<=ww)
        ans=i;
     }
     cout<<ans<<endl;
 }
 

Measured memory_bytes: 80896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,sum=0,i,i1,i2;
    cin>>n;
    for (i=1;i<=n;i++){
        for (i1=1;i1<=n;i1++){
            for (i2=1;i2<=n;i2++){
                sum+=__gcd(i,__gcd(i1,i2));
            }
        }
    }
    cout<<sum<<'\n';
}

Measured memory_bytes: 3652
import qualified Data.ByteString.Char8 as C
import Data.Maybe ( fromJust )
import Data.List ( sortBy )

getParm :: IO [Int]
getParm = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

main :: IO ()
main = do
  n <- readLn :: IO Int
  ass <- getParm
  print $ f n ass

sort' :: [Int] -> [Int]
sort' = sortBy (flip compare)

f :: Int -> [Int] -> Int
f n ass = g (sort' ass) n 0

g :: [Int] -> Int -> Int -> Int
g _        0 acc = acc
g (_:b:bs) n acc = g bs (n-1) (b+acc)

Measured memory_bytes: 51580
flag = False

def dfs(a, b, c, i):
  if i == 10:
    # print("OK")
    global flag
    flag = True
    return
  else:
    if a[i] > b:
     # print("b:",a[i], i)
      dfs(a, a[i], c, i + 1)
    else:
      pass
    
    if a[i] > c:
     # print("c:", a[i], i)
      dfs(a, b, a[i], i + 1)
    else:
      pass
    
    if a[i] < b and a[i] < c:
      return
    

n = int(input())
for i in range(n):
  a = list(map(int, input().split()))
  dfs(a, 0, 0, 0)
  if flag == True:
    print("YES")
  else:
    print("NO")
  flag = False


Measured memory_bytes: 5592
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,b) for (int i=a; i<=b; i++)
#define per(i,a,b) for (int i=a; i>=b; i--)
#define L(i,u) for (int i=head[u]; i!=0; i=edge[i].nxt)
#define abs(a) ((a)>0 ? (a) : -(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
typedef long long ll;
typedef long double ld;
const int N = 1002, M = 500000;


inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
	while (c>='0'&&c<='9') {x=10*x+c-'0'; c=getchar();} x*=f;
}
int n,m,d[N][N],sz,dy[N][N],s,t,C[N][N];
bool ok[N][N];
int tot,st1[M],st2[M],st3[M],a[N],b[N];
bool mrk[M];
int main() { //freopen("1.in","r",stdin);
	read(n); read(m); rep(i,1,n) rep(j,1,m) read(d[i][j]);
	s=203; t=s+1;
	if (n==1&&m==1) {
		puts("Possible");
		printf("2 1\n");
		printf("1 2 %d\n",d[1][1]);
		printf("1 2");
		return 0;
	}
	
	
	rep(A,0,100) rep(B,0,100) {
		int mx=0;
		rep(i,1,n) rep(j,1,m) mx=max(mx,d[i][j]-A*i-B*j);
		rep(i,1,n) rep(j,1,m) if (d[i][j]-A*i-B*j==mx) ok[i][j]=1;
		C[A][B]=mx;
	}
	rep(i,1,n) rep(j,1,m) if (!ok[i][j]) {puts("Impossible"); return 0;}
	
	
	rep(i,0,100) a[i]=++sz;
	rep(i,0,100) b[i]=++sz;
	st1[++tot]=s; st2[tot]=a[0]; st3[tot]=0;
	st1[++tot]=b[0]; st2[tot]=t; st3[tot]=0;
	rep(i,0,99) {st1[++tot]=a[i]; st2[tot]=a[i+1]; st3[tot]=1; mrk[tot]=1;}
	rep(i,0,99) {st1[++tot]=b[i+1]; st2[tot]=b[i]; st3[tot]=2; mrk[tot]=1;}	
	rep(i,0,100) rep(j,0,100) {st1[++tot]=a[i]; st2[tot]=b[j]; st3[tot]=C[i][j];}
	
	
	puts("Possible");
	printf("%d %d\n",t,tot);
	rep(i,1,tot) {
		printf("%d %d ",st1[i],st2[i]);
		if (!mrk[i]) printf("%d",st3[i]); else printf("%c",st3[i]==1?'X':'Y');
		puts("");
	}
	printf("%d %d",s,t);
	return 0;
}

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

int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>v;
    v.push_back(k);
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    vector<int>fr;
    for(int i=0;i<v.size()-1;i++)
    {
        int a=v[i+1]-v[i];
        fr.push_back(a);
    }
    int counter=fr[0];
    for(int i=1;i<fr.size();i++)
    {
        counter=__gcd(counter,fr[i]);
    }
    cout<<counter<<endl;
}


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


int main() {
  int N,L;
  cin >>N>>L;
  int sum =0;
  for(int i=1;i<=N;i++) sum += L+i-1;
  if(0 <L) cout << sum-L <<endl;
  else if(L <= 0 <=L+N-1) cout <<sum <<endl;
  else cout <<sum - (L+N-1) <<endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll ac(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int main()
{
	ll n, ans = 0, temp;
	cin >> n;
	ll k = (ll)sqrt(n);
	if (n == 2) {
		puts("1");
		return 0;
	}
	rep(i, 2ll, k + 1) {
		if ((n - 1) % i == 0)ans += n - 1 == i * i ? 1 : 2;
		else if (n % i == 0) {
			temp = n;
			while (temp % i == 0)temp /= i;
			if (temp % i == 1)ans++;
			if (n == i * i)continue;
			temp = n;
			while (temp % (n/i) == 0)temp /= (n / i);
			if (temp % (n / i) == 1)ans++;
		}
	}
	printf("%lld\n", ans + 2);
	return 0;
}

Measured memory_bytes: 3688
from sys import stdin
from collections import deque
d = deque()
N,H= list(map(int,stdin.readline().strip().split()))
damage=[list(map(int,input().split())) for x in range(N)]
a=[l[0] for l in damage]
b=[l[1] for l in damage]
b.sort(reverse=True)
a.sort(reverse=True)
max_a=a[0]
oppai=0
sum_=0
count=0
for num in b:
    if max_a<num:
        sum_ += num
        count += 1
        oppai+=num
        if sum_>=H:
            print(count)
            exit()
    else:break

H-=oppai
count+=H//max_a
if H%max_a==0:
    print(count)
    exit()
else:
    print(count+1)
    exit()



Measured memory_bytes: 29700
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+10;
ll a[MAXN],sum[MAXN];
int main()
{
    ll N,M;
    ll ans=0;
    ll cnt=0;
    ll flag=0;
    scanf("%lld%lld",&N,&M);
    for(ll i=1;i<=N;i++)
        scanf("%lld",&a[i]);
    memset(sum,0,sizeof(sum));
    sort(a+1,a+N+1);
    if(M<a[1])
    {
        printf("0");
        return 0;
    }
    for(ll i=1;i<=N;i++)
    {
        ans+=a[i];
        if(ans<=M)
            cnt++;
        else
        {
            flag=i;
            break;
        }
    }
    if(ans<M&&cnt!=0)
        printf("%d",cnt-1);
    else printf("%d",cnt);
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll a,b;
    cin>>a>>b;
    cout<<6-a-b;
}


Measured memory_bytes: 256
import numpy as np
import math as m

def main(**kwargs):
    r = "APPROVED"

    for a in A:
        if a % 2 == 0:
            if a % 3 == 0 or a % 5 == 0:
                continue

            else:
                r = "DENIED"

    return r

if __name__ == "__main__":
    cin = np.array(input().split(" ")).astype("int")
    n, *_ = cin
    
    cin = np.array(input().split(" ")).astype("int")
    A = np.array(cin)
    
    cout = main(n=n, A=A)
    print(cout)

Measured memory_bytes: 12668
import java.util.Random;
import java.util.Scanner;
 
public class Main 
{   
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
 
        int[] n = new int[6];
        for(int i=0; i<6; i++)
        {
            n[i] = scanner.nextInt();
        }
         
        int q = scanner.nextInt();
         
        for(int i=0; i<q; i++)
        {
            int[] in = new int[2];
            in[0] = scanner.nextInt();
            in[1] = scanner.nextInt();
             
            for(;;)
            {
                Random random = new Random();
                int d = random.nextInt(4);
                 
                int[] buf = new int[6];
                for(int j=0; j<6; j++)
                {
                    buf[j] = n[j];
                }
                     
                switch(d)
                {
                    case 0:
                        n[0] = buf[4];
                        n[1] = buf[0];
                        n[5] = buf[1];
                        n[4] = buf[5];
                        break;
                    case 1:
                        n[0] = buf[1];
                        n[1] = buf[5];
                        n[5] = buf[4];
                        n[4] = buf[0];
                        break;
                    case 2:
                        n[0] = buf[2];
                        n[2] = buf[5];
                        n[5] = buf[3];
                        n[3] = buf[0];
                        break;
                    case 3:
                        n[0] = buf[3];
                        n[3] = buf[5];
                        n[5] = buf[2];
                        n[2] = buf[0];
                        break;
                }
                if(in[0]==n[0] && in[1]==n[1])
                {
                    System.out.println(n[2]);
                    break;
                }
            }
        }
    }
}


Measured memory_bytes: 26276
#include<bits/stdc++.h>
#define MAX_N 1001
#define MAX_W 1001
using namespace std;


int dp[MAX_N][MAX_W];
int n,W;
int w[MAX_N];
int v[MAX_N];

void solve(int k){
  memset(dp,0,sizeof(dp));
  cout<<"Case "<<k<<":"<<endl;
  for(int i=0;i<n;i++){
    for(int j=0;j<=W;j++){
      if(j>=w[i]){
	dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      }else{
	dp[i+1][j]=dp[i][j];
      }
    }
  }
  int tmp=0;
  int weight;
  for(int i=0;i<=W;i++){
    if(dp[n][i]>tmp){
      tmp=dp[n][i];
      weight=i;
    }
  }
  cout << tmp << endl;
  cout << weight << endl;
}

int main(){
  int cnt=0;
  while(cin>>W,W){
    cnt++;
    cin>>n;
    for(int i=0;i<n;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
    solve(cnt);
  }

  return 0;
}

Measured memory_bytes: 5172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int w,a,b;cin >> w >> a >> b;
	cout << max(0,abs(a - b) - w) << endl;
}


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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int cnt[100002] = {};
    rep(i, N){
        int a; cin >> a;
        if(a > 0) cnt[a-1]++; cnt[a]++; cnt[a+1]++;
    }
    int mx = 0;
    rep(i, 100002){
        if(cnt[mx] < cnt[i]) mx = i;
    }
    cout << cnt[mx] << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,w=0,e=0,lw=0,le=0,sum=10e8,p;
  cin>>m>>n;
  string s[n];
  for(int i=0;i<n;i++){
    cin>>s[i];
    for(int j=0;j<m;j++)
      if(s[i][j]=='W')w++;
      else e++;
  }
  sum=w;p=-1;
  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++)
      if(s[j][i]=='W')w--,lw++;
      else e--,le++;
    if(le+w<sum)sum=le+w,p=i;
  }
  if(p==-1)cout<<0<<' '<<1<<endl;
  else cout<<p+1<<' '<<p+2<<endl;
}

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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  
  int n;
  cin >> n;
  vector<long long> d(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i];
  }

  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) { return d[i] > d[j]; });
  int rt = ord.back(); ord.pop_back();

  map<long long, int> mp;
  for (int i = 0; i < n; i++) {
    mp[d[i]] = i;
  }
  vector<int> sz(n, 1), par(n, -1);
  vector<vector<int>> g(n);

  for (auto i : ord) {
    long long par_d = d[i] + sz[i] - (n - sz[i]);
    if (mp.count(par_d) == 0 || mp[par_d] == i || par[mp[par_d]] != -1) {
      cout << -1 << '\n';
      return 0;
    }
    par[i] = mp[par_d];
    g[par[i]].push_back(i);
    sz[par[i]] += sz[i];
  }

  // check dist[rt]
  long long real_d = 0;
  queue<pair<int,int>> q;
  q.emplace(rt, 0);
  while (q.size()) {
    auto v = q.front(); q.pop();
    real_d += v.second;
    for (auto u : g[v.first]) {
      q.emplace(u, v.second + 1);
    }
  }
  if (d[rt] != real_d) {
    cout << -1 << '\n';
    return 0;
  }

  for (int i = 0; i < n; i++) {
    if (par[i] != -1) {
      cout << i + 1 << ' ' << par[i] + 1 << '\n';
    }
  }

  return 0;
}


Measured memory_bytes: 16992
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, a, b, c, t[100000];
ll s[100000];
priority_queue<pair<int, pair<int, int>>>q;

int par(int x) {
	if (t[x] < 0)return x;
	return par(t[x]);
}

void func(int x, int y, ll c) {
	x = par(x);
	y = par(y);
	if (t[x] < t[y]) {
		s[x] += -t[y] * c;
		s[y] += -t[x] * c - s[x];
		t[x] += t[y];
		t[y] = x;
	}
	else {
		s[y] += -t[x] * c;
		s[x] += -t[y] * c - s[y];
		t[y] += t[x];
		t[x] = y;
	}
}

ll calc(int i) {
	ll a = 0;
	while (i >= 0) {
		a += s[i];
		i = t[i];
	}
	return a;
}

int main() {
	cin >> N;
	memset(t, -1, sizeof t);
	for (int i = 1; i < N; ++i) {
		cin >> a >> b >> c;
		--a;
		--b;
		q.push(mkp(c, mkp(a, b)));
	}
	for (int i = 1; i < N; ++i) {
		func(q.top().second.first, q.top().second.second, q.top().first);
		q.pop();
	}
	for (int i = 0; i < N; ++i) {
		cout << calc(i) << endl;
	}
}

Measured memory_bytes: 4212
from collections import Counter

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

def main(N, lst_A):

    dct_cntA = Counter(lst_A)
    sum_comb = 0

    for cntA in dct_cntA.values():
        comb = (cntA * (cntA - 1)) // 2
        sum_comb += comb

    for A in lst_A:
        print(sum_comb - (dct_cntA[A] - 1))

    return 0

if __name__ == "__main__":

    main(N, lst_A)
    

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

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


Measured memory_bytes: 3096
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main(){
	double r,s,c;
	cin >> r;
        s = r*r*M_PI;
        c = r*2*M_PI;
	printf("%lf %lf\n",s,c);
	return 0;
}

Measured memory_bytes: 3288
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>

//マクロ
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define REPS(i,n) for(int i=1; i<=(int)(n); ++i)
#define RREP(i,n) for(int i=(int)(n)-1; i>=0; --i)
#define RREPS(i,n) for(int i=(int)(n); i>0; --i)
#define FOR(i,s,e) for(int i=(int)(s); i<(int)(e); ++i)
#define RFOR(i,s,e) for(int i=(int)(e)-1; i>=(int)(s); --i)

#define All(a) (a).begin(),(a).end()

//定数
#define INF 1e9
#define MOD (int)(1e9+7)

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

//とりあえず書いておく変数
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//今回の変数

//使用する関数


int main()
{
	int a, b;
	cin >> a >> b;

	int cnt = 1;
	int ans = 0;
	while (cnt < b) {
		ans++;
		cnt += a - 1;
	}
	cout << ans;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        
        int count = h[0];
        for (int i = 1; i < n; i++) {
            count += Math.max(h[i] - h[i-1], 0);
        }
        System.out.println(count);
    }
}



Measured memory_bytes: 21844
import sys
input = sys.stdin.readline
INF = 100100100100100100100100


def main():
    V, E = map(int, input().split())
    graph = [[INF]*V for _ in range(V)]
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph[s][t] = d
    for i in range(V):
        graph[i][i] = 0
    for k in range(V):
        for i in range(V):
            if graph[i][k] == INF:
                continue
            for j in range(V):
                if graph[k][j] == INF:
                    continue
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    flag = False
    for i in range(V):
        if graph[i][i] < 0:
            flag = True
            break
    if flag:
        print('NEGATIVE CYCLE')
    else:
        for A in graph:
            if A[0] == INF:
                print('INF', end='')
            else:
                print(A[0], end='')
            for i in range(1, V):
                if A[i] == INF:
                    print(' INF', end='')
                else:
                    print(' {}'.format(A[i]), end='')
            print()


if __name__ == '__main__': main()


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


int main(){	
	string s;
	cin >> s;
	char c = '0';
	int res = 0, now = 0;
	for (int i=0; i<s.length(); i++) {
		if (c == s[i]) now++;
		if (c == '0') c='1'; else c='0';
	}
	res = now;
	c = '1';
	now = 0;
	for (int i=0; i<s.length(); i++) {
		if (c == s[i]) now++;
		if (c == '0') c='1'; else c='0';
	}
	res = min(res, now);
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef vector<int> vi;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define read(x) scanf("%d",&x)

const ll P=1e9+7;
const int MAXN=200005;
inline ll inv(ll x){
	ll exp=P-2,a=1,tmp=x;
	while(exp){
		if (exp&1) a=a*tmp%P;
		tmp=tmp*tmp%P;
		exp>>=1;
	}
	return a;
}

int n;
ll fact[MAXN];
vector<int> G[MAXN];
int fa[MAXN],sz[MAXN];
ll dp[MAXN];
inline void dfs(int u,int pa){
	dp[u]=sz[u]=1;
	for (int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if (v!=pa){
			dfs(v,u);sz[u]+=sz[v];dp[u]=dp[u]*dp[v]%P*inv(fact[sz[v]])%P;
		}
	}
	dp[u]=dp[u]*fact[sz[u]-1]%P;
	return;
}
inline void reroot(int u,int pa){
	for (int i=0;i<G[u].size();++i){
		int v=G[u][i];
		if (v!=pa){
			dp[v]=dp[u]*sz[v]%P*inv(n-sz[v])%P;reroot(v,u);
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	fact[0]=1;
	REP(i,n) fact[i]=fact[i-1]*i%P;
	REP(i,n-1){
		int u,v;cin>>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	dfs(1,0);
	reroot(1,0);
	REP(i,n) cout<<dp[i]%P<<endl;
	return 0; 
}

Measured memory_bytes: 18676
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	string s;
	cin >> s;
	cout << s[0] + s[1] + s[2] - '0' * 3 << endl;
	//printf((a==b) ? "H\n" : "D\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lint long long
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
using namespace std;

// cout << fixed << setprecision(12)

int main(){
 string T;
  cin >> T;
  for(int i=0; i<T.size(); i++){
    if(T[i]=='?') T[i]='D';
  }
  cout << T << endl;
}
  
  

Measured memory_bytes: 3724
n, m =map(int,input().split())
flg=0
for i in range(n+1):
    for j in range(n-i+1):
        if 10000*i+5000*j+1000*(n-i-j)==m:
            flg = 1
            print(i,j,n-i-j)
            break
    else:
        continue
    break
            
if flg==0:
    print(-1,-1,-1)

Measured memory_bytes: 3060