akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

vector<bool> sieve_of_eratosthenes(int n) {
  vector<bool> primes(n);
  for (int i = 2; i < n; ++i)
    primes[i] = true;
  for (int i = 2; i*i < n; ++i)
    if (primes[i])
      for (int j = i*i; j < n; j+=i)
        primes[j] = false;
  return primes;
}

int main(void){
	int n,m;
	while(cin >> n >> m,n+m != 0){
	vector<vector<bool>> grid(1100,vector<bool>(1100,false));
	vector<bool> primes = sieve_of_eratosthenes(n+1);
	vector<vector<int>> nums(1100,vector<int>(1100,-1));
	int mx,my;
	//??????????????????
	int x=505,y=505;
	int cnt = 1,d = 1,dir = 0;
	for(int i=1;i<=n;i++){
		nums[y][x] = i;
		if(primes[i])grid[y][x] = true;

		if(i == m){mx = x;my = y;}
		if(dir == 0){
			x++;
			d--;
			if(d == 0){d = cnt;dir++;}
		}else if(dir == 1){
			y--;
			d--;
			if(d == 0){cnt++;d = cnt;dir++;}
		}else if(dir == 2){
			x--;
			d--;
			if(d == 0){d = cnt;dir++;}
		}else{
			y++;
			d--;
			if(d == 0){cnt++;d = cnt;dir=0;}
		}

	}
	vector<vector<int>> dp(1100,vector<int>(1100,0));
	vector<vector<bool>> visited(1100,vector<bool>(1100,false));
	queue<int> qx,qy;
	qx.push(mx);
	qy.push(my);
	int dx[] = {-1,0,1};
	int ret = 0,rnum = 0;
	while(!qx.empty()){
		int xx = qx.front();qx.pop();
		int yy = qy.front();qy.pop();
		// cout << xx << " " << yy << endl;
		for(int i=0;i<3;i++){
			int nx = xx + dx[i],ny = yy + 1;
			if(nx < 0 || nx > 1080 || ny > 1080)continue;
			//if(nums[ny][nx] == -1)continue;
			if(grid[yy][xx]){
				if(ret < dp[yy][xx] + 1){
					ret = dp[yy][xx] + 1;
					rnum = nums[yy][xx];
				}else if(ret == dp[yy][xx] + 1 && rnum < nums[yy][xx]){
					rnum = nums[yy][xx];
				}
				dp[ny][nx] = max(dp[ny][nx],dp[yy][xx]+1);
			}else{
				dp[ny][nx] = max(dp[ny][nx],dp[yy][xx]);
			}

			if(visited[ny][nx] == false){
				qx.push(nx);
				qy.push(ny);
				visited[ny][nx] = true;
			}
		}
	}

	// for(int y=500;y<510;y++){
	// 	for(int x=500;x<510;x++){
	// 		printf("%2d ",nums[y][x]);
	// 	}cout << endl;
	// }
	// for(int y=500;y<510;y++){
	// 	for(int x=500;x<510;x++){
	// 		printf("%2d ",dp[y][x]);
	// 	}cout << endl;
	// }
	cout << ret << " " << rnum << endl;
}
	return 0;
}

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

typedef long long ll;

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

  int a, b;
  cin >> a >> b;

  if (a < 10 && b < 10){
    cout << a * b << endl;
  }else {
    cout << -1 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main (){

    int c[9];

    for (int i = 0; i < 3; i++){
        cin >> c[0+i*3] >> c[1+i*3] >> c[2+i*3];
    }

    int a[3],b[3];

    a[0] = 0;
    b[0] = c[0] - a[0];
    b[1] = c[1] - a[0];
    b[2] = c[2] - a[0];
    a[1] = c[3] - b[0];
    a[2] = c[6] - b[0];

    for (int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if ((a[i]+b[j])!=c[j+i*3]){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;    
    return 0;

}

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

using namespace std;

struct SegTree {
    vector<int> node;
    int n;
    SegTree(int sz) {
        n = 1;
        while (sz > n) n *= 2;
        node.resize(2 * n - 1, 0);
    }/*
    void add(int p, int x) {
        p += n-1;
        node[p] += x;
        do {
            p = (p-1) / 2;
            node[p] += x;
        } while (p);
    }*/
    void add(int k, int val) {
        k += (n - 1);
        node[k] += val;
 
        while(k > 0) {
            k = (k - 1) / 2;
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
    int get(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (b <= l || r <= a) return 0;
        if (a <= l && r <= b) {
            return node[k];
        }
        return get(a, b, k * 2 + 1, l, (l + r) / 2) + get(a, b, k * 2 + 2, (r + l) / 2, r);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;
    SegTree s(n);
    while (q--) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0) {
            s.add(x-1, y);
        } else {
            cout << s.get(x-1, y) << endl;
        }
    }
}


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

int n, f[26], from[26], nxt[210000];
char s[210000];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = n + 1; i <= n + 26; i++) {
        from[i - n - 1] = i, s[i] = 'a' + i - n - 1;
    }
    for (int i = n; i; i--) {
        for (int j = 0; j < 26; j++) {
            if (f[j] == *min_element(f, f + 26)) {
                f[s[i] - 'a'] = f[j] + 1;
                nxt[i] = from[j], from[s[i] - 'a'] = i; break;
            }
        }
    }
    int fir = from[min_element(f, f + 26) - f];
    string str;
    while (fir) {
        str.push_back(s[fir]), fir = nxt[fir];
    }
    cout << str << endl;
    return 0;
}

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

typedef long long int ll;
typedef long double ld;
const ll MAX=1e2+5;
const ll INF=1e15+2;
const ll MOD=1e9+7;

#define pb push_back
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define pi pair<ll,ll>
#define map1 unordered_map

ll a[MAX][MAX];
ll res[MAX][MAX];
ll n,k;

void mul(ll flg)
{
    ll tt[MAX][MAX];
    memset(tt,0,sizeof(tt));
    if(flg)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)
                    tt[i][j]=(tt[i][j] + (a[i][k]*res[k][j])%MOD)%MOD;
            }
        }
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            res[i][j]=tt[i][j];
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)
                    tt[i][j]=(tt[i][j] + (a[i][k]*a[k][j])%MOD)%MOD;
            }
        }
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            a[i][j]=tt[i][j];
    }
    
}

int main()
{
    faster;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        res[i][i]=1;
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    }
    
    ll l=k;
    ll ans=0;
    
    while(l)
    {
        if(l&1)
            mul(1);
        mul(0);
        l>>=1;
    }
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            ans=(ans+res[i][j])%MOD;
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 384
#include <vector>
#include<stdio.h>
#include<string.h>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
#include<cstring>
#define ll long long
#define MODD 1000000007
#define  pii  pair<int,int>
#include<stdio.h>
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
struct node {
    ll num;
    ll cost;
    ll point;
};
node pp[1000000];
ll cmp(node a , node b){
    return a.cost<b.cost;
}
int arr[1000000];
int main(){
  int n;cin >>n;
  int sum =0 ;
  for(int i=0;i<n;i++){
    cin >>arr[i];
    sum+=arr[i]-1;
  }
    cout<<sum<<endl;
    return 0;
}
/*
                            *
                            *
        *                   *
        *                   *     *   *
        *                   *     *   *
*       *     *             *     *   *
*       *     * *     * *   *     * * *
*       *   * * *     * *   * *   * * * *
*     * * * * * *     * * * * *   * * * *     * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
*/


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int s;
    cin >> s;
    int kami2, shimo2;
    kami2 = s / 100;
    shimo2 = s % 100;
    if (kami2 > 0 && kami2 < 13) {
        if (shimo2 > 0 && shimo2 < 13) {
            cout << "AMBIGUOUS" << endl;
        } else {
            cout << "MMYY" << endl;
        }
    } else {
        if (shimo2 > 0 && shimo2 < 13) {
            cout << "YYMM" << endl;
        } else {
            cout << "NA" << endl;
        }
    }
}

Measured memory_bytes: 256
s=input()
t=input()
u=len(t)
for i in range(len(s)-u,-1,-1):
    for j in range(u):
        if s[i+j]!="?" and s[i+j]!=t[j]:
            break
    else:
        print((s[:i]+t+s[u+i:]).replace("?","a"))
        break
else:
    print("UNRESTORABLE")

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<ll> prev(1e6 + 5, -1);
    rep2(i, 2, 1e6) {
        if (prev[i] == -1) {
            for (int j = i; j <= 1e6; j += i) {
                prev[j] = i;
            }
        }
    }
    bool ok = true;
    set<ll> used;
    rrep(i, N - 1, 0) {
        ll a = A[i];
        if (a == 1) continue;
        vector<ll> x;
        while (prev[a] != a && a != 1) {
            x.push_back(prev[a]);
            ll v = prev[a];
            while (a % v == 0) {
                a /= v;
            }
        }
        if (a >= 2) x.push_back(a);
        for (ll v : x) {
            if (used.count(v)) {
                ok = false;
                break;
            }
        }
        for (ll v : x) {
            used.insert(v);
        }
    }
    if (ok) {
        cout << "pairwise coprime" << '\n';
    } else {
        ll g = 0;
        rep(i, N) {
            g = gcd(g, A[i]);
        }
        if (g == 1) {
            cout << "setwise coprime" << '\n';
        } else {
            cout << "not coprime" << '\n';
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 22412
#include <bits/stdc++.h> 
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
#define vbi vector<bool> 
#define mod 1000000007
#define INF 1000000000
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define sd second
#define ft first
#define ms(x,v) memset(x,v,sizeof x)
#define endl '\n'
#define cnl cout<<endl;
#define frr(i,b) for(ll i=0; i<b;i++)
#define fb(i,b) for(ll i=b-1; i>=0; i--)
#define pi  3.141592653589793238
ll i,j,k;
long long dp[100+5][100000+5];
void solve(){
       ll n; cin>>n; 
       ll w; cin>>w;
       ll z=0;
        vector<pair<long long ,long long>> v; 
        for(i=0;i<n;i++){
            ll x,y; cin>>x>>y;
            v.pb(mp(x,y));
        }
        sort(all(v));
       for(i=0;i<n;i++){
        for(j=1;j<=w;j++){
            if(j<v[i].ft) dp[i+1][j]=dp[max(z,i)][j];
            else{
                ll v1=v[i].sd;
                ll w1=v[i].ft;
                dp[i+1][j]=max((v1+dp[max(z,i)][max(z,j-w1)]),dp[i][j]);
            }
        }
       }
       cout<<dp[n][w];
}
 signed main(){
    solve();
    return 0;
  }

Measured memory_bytes: 79488
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define DEBUG(val) cout << #val << " : " << val << endl
#define MOD 1000000007

int main() {
  int n;
  vector<ll> data;
  cin >> n;
  ll ans = 0;
  REP(i, n) {
    ll a, b;
    cin >> a >> b;
    data.push_back(a + b);
    ans -= b;
  }
  sort(ALL(data));
  reverse(ALL(data));
  REP(i, n) {
    if (i % 2 == 0) ans += data[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 4320
/*
  Vivek Rathi
  CSE 2nd Year
  MNNIT
*/
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long int
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define present(c,x) ((c).find(x) != (c).end())
#define null NULL
#define mp make_pair
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inf 1e18
#define flush fflush(stdout);
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
ll modpower(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return res;
}
//-------------------------------Template--Above------------------------------------------------
ll n;
pair<ll,ll> xy[51];
map<pair<ll,ll>,ll> m;
ll solve(ll p,ll q)
{
	ll co=0;
	ll vis[51]={0};
	if(p>0)
	{
		for(ll i=0;i<n;i++)
		{
			if(m.find(mp(xy[i].fi+p,xy[i].se+q))!=m.end())
			{
				if(vis[m[mp(xy[i].fi+p,xy[i].se+q)]-1]==0)
				{
					vis[m[mp(xy[i].fi+p,xy[i].se+q)]-1]++;
					vis[i]++;
				}
			}
			else
				co++;
		}
	}
	else
	{
		for(ll i=n-1;i>=0;i--)
		{
			if(m.find(mp(xy[i].fi+p,xy[i].se+q))!=m.end())
			{
				if(vis[m[mp(xy[i].fi+p,xy[i].se+q)]-1]==0)
				{
					vis[m[mp(xy[i].fi+p,xy[i].se+q)]-1]++;
					vis[i]++;
				}
			}
			else
				co++;
		}
	}
	return co;
}
int main()
{
	boost
	
	cin>>n;
	for(ll i=0;i<n;i++)
	{
		ll a,b;
		cin>>a>>b;
		xy[i]=mp(a,b);
		m[xy[i]]=i+1;
	}
	sort(xy,xy+n);
	set<pair<ll,ll> > s;
	for(ll i=0;i<n;i++)
	{
		for(ll j=i+1;j<n;j++)
		{
			if(xy[j].fi-xy[i].fi!=0||xy[j].se-xy[i].se!=0)
			{
				s.insert(mp(xy[j].fi-xy[i].fi,xy[j].se-xy[i].se));
			}
		}
	}
	ll mini=inf;
	for(auto it:s)
	{
		mini=min(mini,solve(it.fi,it.se));
		//debug3(it.fi,it.se,mini);
	}
	if(n==1)
		mini=1;
	cout<<mini<<endl;
	return 0;
}


Measured memory_bytes: 384
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

int main(){
  string s,t;
  cin>>s>>t;
  int dep=1;
  string targ=t;
  while(1){
    int pos=0;
    rep(i,s.length()){
      if(pos>=(int)targ.length())break;
      if(s[i]==targ[pos]){
	pos++;
      }
    }
    if(pos<(int)targ.length())break;
    dep++;
    lint nxtlen=(t.length()+1)*(lint)targ.size()+t.length();
    if(s.length()<nxtlen)break;
    string nxt=targ;
    rep(i,t.length())
      nxt+=t[i]+targ;
    targ=nxt;
  }
  cout<<dep-1<<endl;
}



Measured memory_bytes: 3340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int n, k;
vector<vector<int>> e(100010);
ll ans;

void dfs(int now, int parent, int depth) {
    depth++;
    int color_num;
    if (depth == 1) color_num = k - 1;
    if (depth >= 2) color_num = k - 2;
    rep(i, 0, (int)e[now].size()) {
        int next = e[now][i];
        if (next == parent) continue;
        dfs(next, now, depth);
        ans *= color_num;
        ans %= MOD;
        color_num--;
    }
}

int main() {
    cin >> n >> k;
    rep(i, 0, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    ans = k;
    dfs(0, -1, 0);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>
#include <queue>
#include <iomanip>
#include <map>
using namespace std;

#define rip(i,n,s) (int i=(s);i<(int)(n);i++)
#define all(a) (a).begin(),(a).end()
long long mod=1000000007;

long long pow(long long n, long long p,long long k) {//n^k(mod p)
	if (k != 0) {
		if (p % 2==0) {
			long long x = pow(n, p, k / 2);
			return (long long)x*x%p;
		}
		else {
			long long x = pow(n, p, k - 1);
			return (long long)x*n%p;
		}
	}
	return 1;
}

long long rev(long long n, long long p) {//nの逆元
	return pow(n, p ,p - 2);
}

long long bino(long long n, long long m, long long p) {//nCm(mod p)
	long long me = 1;
	long long ans = 1;
	for (int i = 0;i < n + m;i++) {
		me = (long long)(i + 1) * ans % p;
		if (i == m - 1) {
			ans =(long long) rev(me,p) * ans%p;
		}
		if (i == m - n - 1) {
			ans = (long long)(rev(me, p))*ans%p;
		}
	}
	ans = (long long)(ans*me%p);
	return ans;
}

struct modint{
    long long num;
    long long p;
    modint () {
        num=0;
        p=1000000007;
    }
    modint(int x){
        num=(long long) x%p;
        p=1000000007;
    }
    modint operator+(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num+other.num)%p;
        return ret;
    }
	modint operator+(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num+(other%p))%p;
        return ret;
    }
    modint operator-(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num-other.num+p)%p;
        return ret;
    }
    modint operator-(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num-(other%p)+p)%p;
        return ret;
    }
    modint operator*(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num*other.num)%p;
        return ret; 
    }
    modint operator*(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num*(other%p))%p;
        return ret; 
    }
    modint operator/(const modint &other){
        modint ret;
        ret.p=p;
        ret.num=(num*rev(other.num,p))%p;
		return ret;
    }
    modint operator/(const long long &other){
        modint ret;
        ret.p=p;
        ret.num=(num*rev(other%p,p))%p;
		return ret;
    }
};


int main(){
	long long n,k;
	cin >> n >> k;
	vector<int> da(n);
	for(int i=0;i<n;i++){
		cin >> da[i];
	}
	modint co;
	for rip(i,n,0){
		for rip(j,i,0){
			if(da[i]<da[j]){
				co=co+1;
			}
		}
	}
	sort(all(da));
	modint coo=0;
	int fl=0;
	for rip(i,n,1){
		if(da[i]==da[i-1]){
			fl++;
		}
		else{
			fl=0;
		}
		coo=coo+i-fl;
	}
	modint ans=co*k;
	//printf("%d %d\n",co.num,k);
	ans=(ans+coo*(k*(k-1)/2));
	cout << ans.num << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;++i)
struct Dice{
  int a[6];
  void D(char c){
    int b;
    if(c=='E')
      b=a[0], a[0]=a[3], a[3]=a[5], a[5]=a[2], a[2]=b;
    else if(c=='W')
      b=a[0], a[0]=a[2], a[2]=a[5], a[5]=a[3], a[3]=b;
    else if(c=='S')
      b=a[0], a[0]=a[4], a[4]=a[5], a[5]=a[1], a[1]=b;
    else if(c=='N')
      b=a[0], a[0]=a[1], a[1]=a[5], a[5]=a[4], a[4]=b;
    else
      b=a[1], a[1]=a[2], a[2]=a[4], a[4]=a[3], a[3]=b;
  }
};
bool f(Dice d,Dice e){
  REP(i,6)
    if(d.a[i]!=e.a[i]) return false;
  return true;
}
int main(){
  Dice d,e;
  REP(i,6) cin>>d.a[i];
  REP(i,6) cin>>e.a[i];
  REP(i,4){
    e.D('E');
    REP(j,4){
      e.D('S');
      REP(k,4){
        e.D('X');
        if(f(d,e)){
          cout<<"Yes\n";
          return 0;
        }
      }
    }
  }
  cout<<"No\n";
  return 0;
}

Measured memory_bytes: 3096
#include <iostream>
#include <climits>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#define MAX 1000000007


using namespace std;
#define ll long long
#define dbg if(0)
#define ISRANGE(val,lo,hi) ((lo<=val)&&(val<hi))

int UF[100002];

void init(int n){
    for(int i=0;i<100002;i++){
        UF[i]=i;
        if(i==0 ||i>n)UF[i]=-1;
    }
}
int root(int x){
    if(UF[x]==x)return x;
    return UF[x]=root(UF[x]);
}
void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)return;
    UF[rx]=UF[ry];
}

bool same(int x,int y){
    int rx=root(x);
    int ry=root(y);
    return rx==ry;
}


int main(){
    ll ans=0,n,m;
    cin >>n>>m;

    init(n);

    ll cnt[n+1];
    for(int i=1;i<=n;i++){
        cnt[i]=0;
    }

    for(int i=0;i<m;i++){
        ll x,y,z;
        cin >>x>>y>>z;
        unite(x,y);
    }

    for(int i=1;i<=n;i++){
        if(i==root(i)){
            ans++;
        }
    }


    cout <<ans<<endl;

    return 0;

}

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

int N;
int A[20];
int x[20][20];
int y[20][20];

int counter(int x) { // counts all the honest people in that combo
    if(x==0) return 0;
    return counter(x>>1) + (x&1);
}

void solve() {
    cin >> N;
    for(int i=1;i<=N;i++) {
        cin >> A[i];
        for(int j=1;j<=A[i];j++) {
            cin >> x[i][j] >> y[i][j];
        }
    }
    int ans = 0;
    for(int mask=1;mask<(1<<N);mask++) { // mask generates all possible combos
        bool ok = true;
        for(int i=1;i<=N;i++) {
            if((mask&(1<<(i-1)))) { // checks for set in mask
                for(int j=1;j<=A[i];j++) { // iterates over testimonies of that person
                    if(((mask >> (x[i][j]-1)) & 1) ^ y[i][j]) ok = false; // first part checks if in this combo that person is honest, second part checks if testimony says that person is honest
                }
            }
        }
        if(ok) ans = max(ans,counter(mask));
    }
    cout << ans << endl;
    return;
}

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

Measured memory_bytes: 256
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()

    kyu = 9

    N -= 400

    while N >= 0:
        N -= 200
        kyu -= 1

    print(kyu)


main()


Measured memory_bytes: 64908
#include "bits/stdc++.h"
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <random>
#include <stdio.h>
#include <bitset>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef string ST;


#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) {LL i=0; for(auto (a): v ){   cerr <<i << " : "<<  a << endl; i++;}}
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl

void func() {
  LL H;
  cin >> H;
  LL W;
  cin >> W;
  
  vector<vector<LL>> M(H, vector<LL>(W, 0));
  REP(i, H) {
    REP(j, W) {
      cin >> M[i][j];
    }
  }
  
  vector<vector<LL>> A;
  REP(i, H) {
    REP(j, W) {
      if (M[i][j] % 2 == 1) {
        if (j + 1 < W) {
          M[i][j]--;
          M[i][j+1]++;
          //cout << i << " " << j << " " << i << " " << j + 1 << endl;
          A.push_back(vector<LL>{i, j, i, j + 1});
        }
        else if (i + 1 < H) {
          M[i][j]--;
          M[i+1][j]++;
          //cout << i << " " << j << " " << i+1 << " " << j << endl;
          A.push_back(vector<LL>{i, j, i+1, j});
        }
      }
    }
  }
  REP(i, H) {
    //PRINTSP(M[i]);
  }

  cout << A.size() << endl;
  for (auto a : A) {
    cout << a[0]+1 << " " << a[1]+1 << " " << a[2]+1 << " " << a[3]+1   << endl;
  }
  

}

#ifdef CALC_TIME 
#include <windows.h>
int main()
{
  LARGE_INTEGER freq;
  QueryPerformanceFrequency(&freq);
  LARGE_INTEGER start, end;
  QueryPerformanceCounter(&start);
  // 何かの処理
  func();
  QueryPerformanceCounter(&end);
  double time = static_cast<double>(end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
  fprintf(stderr, "\n%lf[ms]\n", time);
  return 0;
}
#else 
int main()
{
  func();
  return 0;
}
#endif





Measured memory_bytes: 12848
def factorize(n):
    nn = n
    lst = []
    for i in range(2, int(1 + n ** 0.5)):
        k = 0
        while nn % i == 0:
            k += 1
            nn = nn // i
        if k > 0:
            lst.append([i, k])
    if nn != 1:
        lst.append([nn, 1])
    return lst

def gen_divisor(m):
    # not sorted!
    yield 1
    factorized = factorize(m)
    length = len(factorized)
    if length == 0:
        return
    factor_nexps = [0] * length
    while True:
        # increment
        factor_nexps[0] += 1
        for idx in range(length - 1):
            if factor_nexps[idx] > factorized[idx][1]:
                factor_nexps[idx] = 0
                factor_nexps[idx+1] += 1
        if factor_nexps[-1] > factorized[-1][1]:
            return
        divisor = 1
        for i, tup in enumerate(factorized):
            divisor *= tup[0] ** factor_nexps[i]
        yield divisor

N, M = map(int, input().split())

def solve():
    divisors = sorted([di for di in gen_divisor(M) if di >= N])
    ans = M // divisors[0]
    return ans

print(solve())



Measured memory_bytes: 3188
N = int(input())
A = list(map(int,input().split()))
A.append(0)
sm = abs(A[0])
j = 0
while j < N:
        sm += abs(A[j]-A[j+1])
        j += 1

for i in range(N):
    if i == 0:
        print(sm-abs(A[0]-0)
                -abs(A[1]-A[0])
                +abs(A[1]-0))
        continue
    print(sm-abs(A[i]-A[i-1])
            -abs(A[i+1]-A[i])
            +abs(A[i+1]-A[i-1]))

Measured memory_bytes: 14048
#include<stdio.h>
#include<stdlib.h>
struct node {
	int key;
	struct node *right;
	struct node *left;
	struct node *parent;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node find(Node u, int k) {
	while(u!=NIL&&k!=u->key){
		if (k < (u->key)) {
			u = u->left;
		}
		else {
			u = u->right;
		}
	}
	return u;
}

void insert(int k) {
	Node y = NIL;
	Node x = root;
	Node z;

	z = malloc(sizeof(struct node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL) {
		y = x;
		if ((z->key) < (x->key)) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NIL) {
		root = z;
	}
	else {
		if ((z->key) < (y->key)) {
			y->left = z;
		}
		else {
			y->right = z;
		}
	}
}

void inorder(Node u) {
	if (u == NIL) {
		return;
	}
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
}

void preorder(Node u) {
	if (u == NIL) {
		return;
	}
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
}


int main() {
	int n, i, x;
	char com[20];
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%s", com);
		if (com[0] == 'f') {
			scanf("%d", &x);
			Node t = find(root,x);
			if (t != NIL) { printf("yes\n"); 
			}
			else {
				printf("no\n"); 
			}
		}else if (com[0] == 'i') {
			scanf("%d", &x);
			insert(x);
		}
		else if (com[0] == 'p') {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}

	return 0;
}


Measured memory_bytes: 20440
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<cstdio>
#include<cstring>

using namespace std;

/*
typedef pair<double,pair<unsigned char,char> > pi;

#define P(a,b,c) make_pair(a,make_pair(b,c))
#define COST(p) ((p).first)
#define POS(p) ((p).second.first)
#define TIC(p) ((p).second.second)
*/
#define P(a,b,c) pi(a,b,c)
#define COST(p) ((p).cost)
#define POS(p) ((p).pos)
#define TIC(p) ((p).tic)

class pi{
public:
  int pos;
  unsigned char tic;
  double cost;
  pi(double c, int p, unsigned char t){
    pos=p; tic=t; cost=c;
  }
  bool operator < (const pi& b) const{
    return cost > b.cost;
  }
};

/*
class test{
public:
  inline bool operator () (const pi& a, const pi& b) const{
    return COST(a)>COST(b);
  }
};
*/

int main(){
  int n,m,p,a,b;
  int table[129];
  int ticket[8];
  pair<int,int> load[40][40];
  table[1]=0; table[2]=1;
  table[4]=2; table[8]=3;
  table[16]=4;table[32]=5;
  table[64]=6;table[128]=7;
  while(scanf("%d%d%d%d%d",&n,&m,&p,&a,&b),n+m+p+a+b){
    int size[40] = {0};
    bool memo[40][300] = {{false}};
    int step[40];
    --a; --b;
    memset(step,-1,sizeof(step));
    for(int i=0; i<n; i++)
      scanf("%d",ticket+i);
    for(int i=0; i<p; i++){
      int s,t,d;
      scanf("%d%d%d",&s,&t,&d);
      load[s-1][size[s-1]].second=d;
      load[t-1][size[t-1]].second=d;
      load[s-1][size[s-1]++].first=t-1;
      load[t-1][size[t-1]++].first=s-1;
    }

    {
      queue<int> q;
      q.push(b);
      step[b]=0;
      while(q.size()){
        int pos = q.front(); q.pop();
	for(int k=0; k<size[pos]; k++){
	  int i = load[pos][k].first;
          if(step[i]==-1){
	    step[i]=step[pos]+1;
            q.push(i);
	  }
        }
      }
    }

    if(step[a] > n || step[a]==-1){
      printf("Impossible\n");
      continue;
    }

    priority_queue<pi> q;
    q.push(P(0.0,a,(1<<n)-1));
    while(true){
      pi pp = q.top(); q.pop();
      char pos = POS(pp);
      double cost = COST(pp);
      unsigned char tic = TIC(pp);
      if(memo[pos][tic])
        continue;

      if(pos == b){
        printf("%.4lf\n",cost);
        break;
      }

      memo[pos][tic]=true;

      unsigned int cnt = tic;
      cnt = (cnt&0x55) + ((cnt>>1)&0x55);
      cnt = (cnt&0x33) + ((cnt>>2)&0x33);
      cnt = (cnt&0x0F) + ((cnt>>4)&0x0f);

      for(int k=0; k<size[pos]; k++){
        int i = load[pos][k].first;
        int d = load[pos][k].second;
        unsigned char tmp = tic;
        while(tmp!=0){
          unsigned char t = tmp&(-tmp);
	  unsigned char nt = tic^t;
          if((!memo[i][nt]) & (step[i]<cnt) & (step[i]!=-1) ){
            q.push(P(cost+(double)d/ticket[table[t]],i,nt));
          }
          tmp^=t;
        }
      }
    }
  }
  return 0;
}

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

int main(){
    int n,l;
    cin>>n>>l;
    int s=n*l+n*(n-1)/2,min;
    if(l>0) min=s-l;
    else if(n+l<=0) min=s-l-n+1;
    else min=s;
    cout<<min<<endl;
    return 0;
}

Measured memory_bytes: 256
/* １個ずつ紐を張っていく感じ */

#include <stdio.h>
#include <math.h>
#define N_MAX 100
#define INF 100

/* vector */

typedef struct vector { double x, y; } vector;

double norm(vector a){ return hypot(a.x, a.y); }
vector div(vector a, double b){ vector c={ .x = a.x/b, .y = a.y/b}; return c; }
vector normalize(vector a) { return div(a, norm(a)); }
double product(vector a, vector b){ return a.x * b.y - a.y * b.x; }
vector sub(vector a, vector b){ vector x={ .x = a.x-b.x, .y = a.y-b.y }; return x; }
vector zero={ .x = 0, .y = 0 };

/**********/

double cosV(vector a, vector b){ a=normalize(a), b=normalize(b); return a.x*b.x + a.y*b.y; }
double sinV(vector a, vector b){ a=normalize(a), b=normalize(b); return a.x*b.y - a.y*b.x; }

int main(void)
{
     int n; vector pin[N_MAX]; int used[N_MAX];
     
     while(scanf("%d",&n), n!=0){
	  int i, k, maxN; double max, t; vector prev;

	  /* input */
	  max = 0, maxN = -1;
	  for(i=0; i<n; i++) used[i]=0;
	  for(i=0; i<n; i++){
	       scanf("%lf,%lf",&(pin[i].x),&(pin[i].y));
	       if((t=norm(pin[i])) > max) max = t, maxN = i;
	  }

	  /* first "k" is the point that has the largest norm */
	  /* zero is zero-vector */
	  k = maxN, prev = zero;
	  while(!used[k]){

	       used[k] = 1;
	       
	       max = -INF, maxN = -1;
	       for(i=0; i<n; i++)
		    if(i!=k){
			 if(sinV(sub(pin[k],prev), sub(pin[i],pin[k])) < 0) continue;
			 
			 t = cosV(sub(pin[k],prev), sub(pin[i],pin[k]));
			 if(t > max) max = t, maxN = i;
		    }

	       prev = pin[k], k = maxN;
	  }

	  k = 0;
	  for(i=0; i<n; i++)
	       if(!used[i]) k++;

	  printf("%d\n",k);
     }

     return 0;
}

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

using namespace std ;

#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0)
#define ll long long int 

#define fr first
#define se second

#define all(v) v.begin(),v.end() 
#define rall(v) v.rbegin(),v.rend()
#define sz(v) v.size() 

#define pb push_back
#define mp make_pair 

#define PI 3.141592653589793238



ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a*b / gcd(a,b) ;}


//bool valid(int x, int y){return x > 0 && x < n && y > 0 && y < m;}


int n;
int main(){
  cin >> n;
  vector<int>v(n);
  for(int i = 0 ; i < n ; i++)
    cin >> v[i];
  sort(all(v));
  int c = accumulate(v.begin(), v.end()-1, 0) + v[n-1]/2;
  cout << c;
  return 0;
}


Measured memory_bytes: 256
import sys
import math
n = int(input())
li = [n]
li[0] = input()
isGood=True
for i in range(n-1):
    tmp = input()
    if (not isGood):
        continue
    if (tmp not in li):
        if (li[i][-1] != tmp[0]):
            isGood = False
        else:
            li.append(tmp)
    else:
        isGood = False

if (isGood):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 何回で１周するのか
N, K = lr()
A = [0] + lr()
if A[1] == 1:
    print(1); exit()
lap = 1
cur = A[1]
nex = [1, A[1]]
been = set([A[1]])
while cur != 1:
    if lap == K:
        print(cur); exit()
    cur = A[cur]
    lap += 1
    nex.append(cur)
    if cur in been:
        lap2 = 1
        cur2 = A[cur]
        while cur2 != cur:
            if lap + lap2 == K:
                print(cur2)
            cur2 = A[cur2]
            lap2 += 1
        K -= lap
        K %= lap2
        for _ in range(K):
            cur2 = A[cur2]
        print(cur2); exit()
    been.add(cur)

# lap回で１周
K %= lap
answer = nex[K]
print(answer)




Measured memory_bytes: 32460
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
 
int main(){
  int n,x;
  ll int l[10000];
  cin >> n >> x;
  REP(i, n) cin >> l[i];
  ll int tmp = 0;
  int cnt = 0;
  if(tmp <= x) cnt++;
  REP(i, n){
    tmp += l[i];
    if(tmp <= x) cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int, int>;
using vpii=vector<pii>;

template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>p){os<<"("<<p.fst<<", "<<p.scd<<")";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<T>v){rep(i,v.size()){if(i)os<<", ";os<<v[i];}return os;}
template<typename T>T&max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T&min(T&a,T&b){if(a < b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a < b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a > b){a=b;return true;}return false;}
int in(){int a;scanf("%d",&a);return a;}
ll lin(){ll a;scanf("%lld",&a);return a;}

constexpr int inf = 1e9;
constexpr ll linf = 3e18;
constexpr double eps = 1e-9;

int main()
{
    string s; cin >> s;
    int n = s.size();

    int cnt = 1; // 区間の数

    for (int i = 1; i < n; ++i) {
        if (s[i] != s[i - 1]) cnt++;
    }

    printf("%d\n",cnt-1);
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int p[200005];
int u_find(int a){
	if(p[a]<0) return a;
	return p[a] = u_find(p[a]);
}
void merge(int a,int b){
	a = u_find(a);
	b = u_find(b);
	if(a==b) return;
	p[a]+=p[b];
	p[b] = a;
}
int main(){
	memset(p,-1,sizeof(p));
	int n,m;
	cin>>n>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		merge(a,b);
	}
	int maxsize = 0;
	for(int i=1; i<=n; i++){
		maxsize = max(maxsize,-1*p[u_find(i)]);
	}
	cout<<maxsize;
}

Measured memory_bytes: 5172
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		List<Integer> list = new ArrayList<>();
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();


		System.out.print(Math.min(a,b));
		System.out.print(" ");
		System.out.print(-Math.min(0,n-a-b));

	}

}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971693993751058
#define maxn 100005

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
#define ceil(a,b) (a+b-1)/b
 
using namespace std;

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

//START OF CODE ->->->->->->->

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int> a(m);
    // bool ok = true;
    int dp[n+1] = {0};
    dp[0] = 1;
    rep(i,0,a.size()){
        cin>>a[i];
        dp[a[i]] = -1;
    }
    rep(i,1,n+1){
        if ( dp[i] == -1 ){
            continue;
        }
        else{
            if ( (i-1 >= 0) ){
                if ( dp[i-1] != -1 ){
                    dp[i] += dp[i-1];
                    dp[i] %= mod;
                }
            }
            if ( (i-2 >= 0) ){
                if ( dp[i-2] != -1 ){
                    dp[i] += dp[i-2];
                    dp[i] %= mod;
                }
            }
        }  
    }
    // rep(i,0,n+1){
    //     out1(dp[i]);
    // }
    cout<<dp[n]%mod<<endl;
}

//END OF CODE ->->->->->->->->

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}



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

constexpr ll MOD = 1000000007;
ll f2(vector<ll> v, int K) {
  if (K & 1) sort(v.rbegin(), v.rend());
  else sort(v.begin(), v.end());
  ll res = 1;
  for (int i = 0; i < K; i++) {
    res *= v[i];
    res %= MOD;
  }
  if (res < 0) res += MOD;
  return res;
}

ll f1(vector<ll> v, int K) {
  const int n = v.size();
  vector<ll> p, m;
  for (int i = 0; i < n; i++) {
    if (v[i] >= 0) p.push_back(v[i]);
    else m.push_back(-v[i]);
  }
  sort(p.rbegin(), p.rend());
  sort(m.rbegin(), m.rend());
  int mcnt = 0;
  while (p.size() < K - mcnt) mcnt += 2;
  for (; mcnt + 2 <= m.size() && K - mcnt - 2 >= 0; mcnt += 2) {
    int pcnt = K - mcnt;
    if (p[pcnt-1] * p[pcnt-2] < m[mcnt] * m[mcnt+1]) continue;
    else break;
  }
  ll res = 1;
  for (int i = 0; i < mcnt; i++) {
    res *= m[i];
    res %= MOD;
  }
  for (int i = 0; i < K - mcnt; i++) {
    res *= p[i];
    res %= MOD;
  }
  return res;
}

int main() {
  int N, K; cin >> N >> K;
  vector<ll> v(N);
  for (int i = 0; i < N; i++) cin >> v[i];
  if (*max_element(v.begin(), v.end()) <= 0 || N == K) {
    cout << f2(v, K) << endl;
  } else {
    cout << f1(v, K) << endl;
  }
}


Measured memory_bytes: 8416
#include<cstdio>
#include<algorithm>
#include <math.h>

using namespace std;

int main(void){
  int n,ans=0;
  long long int a[100001],max;
  double half,diff;
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    scanf("%lld",&a[i]);
  }
  sort(a,a+n);
  max = a[n-1];
  half = (double)a[n-1]/2;

  diff = (double)(half-a[0]);
  diff = fabs(diff);
  //printf("%lf\n",diff);
  for(int i=1;i<n;++i){
    if(fabs(half-a[i])<diff){
      diff = fabs(half-a[i]);
      ans=i;
    }
  }
  printf("%lld %lld\n",max,a[ans]);
  return 0;
}


Measured memory_bytes: 896
#if _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#ifndef ONLINE_JUDGE 
const bool DEBUG = true;
#else
const bool DEBUG = false;
#endif

// Reads a 1D vector
template <class T>
void read1d(vector<T> & arg) {
	const int l = arg.size();
	for (int i = 0; i < l; ++i) cin >> arg[i];
}

void read() {}
// Reads arbitrary values
template <class T1, class... T2>
void read(T1& var1, T2&... var2) { cin >> var1; read(var2...); }



void pln() { cout << (DEBUG ? "]\n" : "\n"); }
template <class T1, class... T2>
void pln(const T1& var1, const T2& ... var2) { cout << var1 << " "; pln(var2...); }

// Prints arbitrary values and goes to next line
template <class T1, class... T2>
constexpr void print(const T1& var1, const T2& ... var2) { cout << (DEBUG ? " [ " : ""); pln(var1, var2...); }

// Prints arbitrary values and goes to next line ONLY IF IN DEBUG MODE
template <class T1, class... T2>
constexpr void debug(const T1& var1, const T2& ... var2) { if (!DEBUG) return;  cout << " debug : [ "; pln(var1, var2...); }





using ll = long long;
using ull = unsigned long long;


#define all(x) begin(x), end(x)

const bool MULTIPLE_TEST_CASES = 0;
const ll mod = 1e9 + 7;


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

	ll sum = 0;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i) cin >> arr[i];
	for (int i : arr) {
		sum += ll(i);
		sum %= mod;
	}

	ll ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		sum -= arr[i];
		sum = (sum + mod) % mod;

		ans += (arr[i] * sum) % mod;
		ans %= mod;
	}

	print(ans);
}

















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

	if (!MULTIPLE_TEST_CASES)
		exec();
	else {
		int n;
		cin >> n;

		while (n--)
			exec();
	}

    return 0;
}

Measured memory_bytes: 3980
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
const ll inf=0x3f3f3f3f3f3f3f3fll;
struct node
{
	ll a,b;
	friend bool operator < (node x,node y)
	{
		return (x.a==y.a)?x.b<y.b:x.a<y.a;
	}
};
struct Edge
{
	int next;
	int to;
	ll val;
}edge[300005];
vector <node> v[150005];
int head[150005];
int siz[150005];
ll pre[150005];
int cnt=1;
int n;
ll sum;
void init()
{
	memset(head,-1,sizeof(head));
	cnt=1;
}
void add(int l,int r,ll w)
{
	edge[cnt].next=head[l];
	edge[cnt].to=r;
	edge[cnt].val=w;
	head[l]=cnt++;
}
int findf(int s1,int s2,ll a1,ll b1,ll w)
{
	if(!v[s2].size())return 0;
	int l=0,r=v[s2].size()-1,ans=v[s2].size();
	while(l<=r)
	{
		int mid=(l+r)>>1;
		ll a2=v[s2][mid].a,b2=v[s2][mid].b;
		if(b1+a2+pre[s1]+pre[s2]<=w)ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
void update(int x,ll w)
{
	int s1=0,s2=0;
	for(int i=head[x];i!=-1;i=edge[i].next)
	{
		int to=edge[i].to;
		if(!s1)s1=to;
		else s2=to;
	}
	if(siz[s1]>siz[s2])swap(s1,s2);
	vector <node> temp;
	temp.clear();
	for(int i=0;i<v[s1].size();i++)
	{
		int t=findf(s1,s2,v[s1][i].a,v[s1][i].b,w);
		if(t>=v[s2].size())continue;
		temp.push_back((node){v[s1][i].a+pre[s1],v[s2][t].b+pre[s2]});
		temp.push_back((node){v[s2][t].b+pre[s2],v[s1][i].a+pre[s1]});
	}
	sort(temp.begin(),temp.end());
	ll minv=inf;
	for(int i=0;i<temp.size();i++)
	{
		if(temp[i].b<minv)v[x].push_back(temp[i]),minv=temp[i].b;
	}
}
void dfs(int x,ll w)
{
	siz[x]=1;
	int num=0;
	for(int i=head[x];i!=-1;i=edge[i].next)
	{
		int to=edge[i].to;
		pre[to]=edge[i].val;
		dfs(to,w);
		siz[x]+=siz[to],num++;
		if(num==2)update(x,w);
	} 
	if(!num)v[x].push_back((node){0,0});
}
bool check(ll w)
{
	for(int i=1;i<=n;i++)v[i].clear();
	dfs(1,w);
	return (v[1].size()!=0);
}
ll divi()
{
	ll l=0,r=sum,ans=sum;
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int main()
{
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
	scanf("%d",&n);
	init();
	for(int i=2;i<=n;i++)
	{
		int x;
		ll z;
		scanf("%d%lld",&x,&z);
		add(x,i,z),sum+=z;
	}
	printf("%lld\n",divi());
	return 0;
}

Measured memory_bytes: 35060
def insertion_sort(a, n, g, cnt):
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j -g
            cnt += 1
        a[j+g] = v
    return cnt

def shell_sort(a, n):
    cnt = 0
    h = 1
    g = []
    while h <= n:
        g.insert(0, h)
        h = 3 * h + 1

    for i in range(len(g)):
        if g[i] <= len(a):
            cnt = insertion_sort(a, n, g[i], cnt)

    print(len(g))
    print(' '.join(map(str, g)))
    print(cnt)


n = int(input())
a = [int(input()) for _ in range(n)]

shell_sort(a, n)
for num in a:
    print(num)



Measured memory_bytes: 45520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll x;
    cin >> x;
    ll cnt = x / 11;
    x -= cnt * 11;
    cnt *= 2;
    if (x > 6) cnt += 2;
    else if (x > 0) cnt += 1;
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
def foo
  i = gets.to_i
  i.times do
    max = 0
    min = 0
    list = gets.split.map(&:to_i)
    while true
      break if list.empty?
      j = list[0]
      if max < j
        max = j
      elsif min < j
        min = j
      else
        break
      end
      list.delete(j)
    end

    res = list.empty? ? 'YES' : 'NO'
    puts res
  end
end

foo

Measured memory_bytes: 8692
N, Q = map(int, input().split())
A = list(map(int, input().split()))
X = [int(input()) for i in range(Q)]
B = [0, sum(A[::-1][::2])]
W = [0, sum(A[::-1][::2])]

for i in range(1, (N+1)//2):
    d = (A[-i-1] - A[-i*2-1])
    B.append(B[-1] + d)
    W.append(W[-1] - d)
#print(B, W)
for q in X:
    l, r = 1, (N+1)//2

    while r-l>0:
        a = (r+l)//2+1
        b = A[-a]
        db = b-q
        w = A[-a*2+1]
        dw = q-w
        if dw <= db:
            l = a
        else:
            r = a-1

    print(B[r])


Measured memory_bytes: 18344
#include<bits/stdc++.h>
#define ll long long
#define no cout<<"NO"<<endl;
#define pb push_back
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define mod 1000000007
#define gcd(x,y) __gcd(x, y)
using namespace std;
int main()
{
	ll n,k;
	cin>>n>>k;
	ll a[n];
	for0(i,n)
	cin>>a[i];
	sort(a,a+n);
	ll x=0;
	for0(i,k)
	x+=a[i];
	cout<<x<<endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

void printFormatDate(int t){
	string str;
	int h, m, s;
	h = t/3600;
	m = t%3600/60;
	s = t%60;
	printf("%02d:%02d:%02d\n", h, m, s);
}

int main(){
	int h, m, s;
	int time;
	while (cin >> h >> m >> s) {
		if (h == -1 && m == -1 && s == -1) {
			break;
		}
		time = 120*60 - (h*60*60 + m*60 + s);
		printFormatDate(time);
		printFormatDate(time*3);
	}
	return 0;
}

Measured memory_bytes: 0