akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int mn=1e6+10;
int nz[mn];
bool ch[mn];
int main(){
    nz[0]=0;
    for(int i=1;i<mn;i++)nz[i]=nz[i-1]+__builtin_ctz(i);
    int n;
    scanf("%d",&n);
    string s;
    cin>>s;
    for(char&c:s)c-='1';
    bool one=0;
    for(char c:s)if(c==1)one=1;
    if(!one)for(char&c:s)if(c==2)c=1;
    if(one)for(char&c:s)if(c==2)c=0;
    bool ans=0;
    for(int i=0;i<=n-1;i++)ch[i]=(nz[n-1]-nz[i]-nz[n-1-i]==0);
    for(int i=0;i<n;i++)if(s[i])ans^=ch[i];
    if(!ans)printf("0");
    else if(one)printf("1");
    else printf("2");
}

Measured memory_bytes: 6276
#include <iostream>
#include <climits>
#include <vector>

using namespace std;

typedef vector< int > VI;
typedef vector< VI > VVI;
typedef vector< VVI > VVVI;

const int INF = INT_MAX / 2;

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

	while ( true )
	{
		int n, m;
		cin >> n >> m;

		if ( !( n | m ) )
		{
			break;
		}

		VVVI G( m, VVI( m, VI( 2, INF ) ) );

		for ( int i = 0; i < m; i++ )
		{
			G[i][i][0] = G[i][i][1] = 0;
		}

		for ( int i = 0; i < n; i++ )
		{
			int a, b, cost, time;
			cin >> a >> b >> cost >> time;

			a--;
			b--;

			G[a][b][0] = G[b][a][0] = cost;
			G[a][b][1] = G[b][a][1] = time;
		}

		for ( int k = 0; k < m; k++ )
		{
			for ( int i = 0; i < m; i++ )
			{
				for ( int j = 0; j < m; j++ )
				{
					G[i][j][0] = min( G[i][j][0], G[i][k][0] + G[k][j][0] );
					G[i][j][1] = min( G[i][j][1], G[i][k][1] + G[k][j][1] );
				}
			}
		}

		int k;
		cin >> k;

		for ( int i = 0; i < k; i++ )
		{
			int p, q, r;
			cin >> p >> q >> r;

			p--;
			q--;

			cout << G[p][q][r] << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1780
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a[n+1];
  for(int i=1;i<=n;i++) cin >> a[i];
  a[0] = -1;
  int count = 0;
  for(int i=1;i<=n;i++){
    if(a[a[i]]==i){
      count++;
    }
  }
  cout << count/2 << endl;
  return 0;
}


Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <set>
using namespace std;
typedef long long ll;


int main(int argc, char *args[]) {
	string s, t;
	cin >> s >> t;
	int n;
	int u;
	n = s.length();
	for(int j = 0; j < n; j++){
		u = s[0];
		for (int i = 0; i < n; i++) {
			s[i] = s[i + 1];
		}
		s[n - 1] = u;
		if (s == t) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    int a[100010];
    for(int i = 0; i < N; i++) {
        cin >> a[i];
        a[i]--;
    }

    int x = 0;
    for(int i = 0; i < 100010; i++) {
        if(x == 1) {
            cout << i << endl;
            return 0;
        }
        x = a[x];
    }

    cout << -1;

    cout << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int T, card[9];

bool is_same_number(int a, int b, int c) {
  return (a==b && b==c) && c==a;
}

bool is_sequence (int a, int b, int c) {
  return (a+2==b+1 && b+1==c) && c==a+2;
}

bool is_good_set(int a, int b, int c) {
  return is_same_number(a, b, c) || is_sequence(a, b, c);
}

bool is_all_good_set() {
  return is_good_set(card[0],card[1],card[2]) &&
    is_good_set(card[3],card[4],card[5]) &&
    is_good_set(card[6],card[7],card[8]);
}

int win() {
  sort(card,card+9);
  do {
    if (is_all_good_set())
      return 1;
  } while (next_permutation (card, card+9));
  return 0;
}
  
int main() {
  cin >> T;
  for (int t=0; t<T; ++t) {
    for (int i=0; i<9; ++i) {
      cin >> card[i];
    }
    string color;
    for (int i=0; i<9; ++i) {
      cin >> color;
      if (color == "G") card[i] +=10;
      else if (color == "B") card[i] += 20;
    }
    cout << win() << endl;
  }
}

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

int main(void) {
	int x,y,data,cnt;
	while(1){
		scanf("%d %d",&x,&y);
		if (x == 0 && y == 0){
			break;
		}
		if (x < y){
			data = x,x = y,y = data;
		}
		cnt = 0;
		while(y != 0){
			x = x % y;
			data = x,x = y,y = data;
			cnt++;
		}
		printf("%d %d\n",x,cnt);
	}
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include <cstdio>
#include<cmath>

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

int main ()
{
    int n,i,cnt=0;
    cin>>n;
    string s;
    cin>>s;
    for (i=0;i<s.size();i++)
    {
        if (s[i]==s[i+1])cnt++;
    }
    cout<<s.size()-cnt<<endl;;

    return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
string s,t;
  cin >>s >>t;
  int a[26];
  for(int i=0;i<26;i++)a[i]=-1;
  bool out=false;
  for(int i=0;i<s.size();i++){
    if(a[s[i]-'a']==-1){
      for(int j=0;j<26;j++){
        if(a[j]==t[i]-'a'){
          out=true;
          break;
        }
      }
      if(!out)a[s[i]-'a']=t[i]-'a';
    }
    else{
      if(a[s[i]-'a']==t[i]-'a')continue;
      else{
        out=true;
        break;
      }
    }
  }
  if(out)cout <<"No"<<endl;
  else cout <<"Yes"<<endl;
}


Measured memory_bytes: 776
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define ll long long
#define endl "\n"
#define ar array
#define deb(x) cout << #x << " = " << x << endl
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll MOD = 998244353;
const ll N = 2e5 + 1;

template <class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
inline ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
inline ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
inline ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }
struct comp
{
    bool operator()(const pair<ll, ll> &x, const pair<ll, ll> &y) const
    {
        return x.first < y.first;
    }
};
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll pwr(ll x, ll n)
{
    if (n == 0)
        return 1;
    if (n & 1)
        return mul(x, pwr(mul(x, x), (n - 1) / 2));
    else
        return pwr(mul(x, x), n / 2);
}
ll modInv(ll n)
{
    return pwr(n, mod - 2);
}
ll modInverse(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}
int main()
{
    IOS;
    int t = 1;
    //  cin >> t;
    while (t--)
    {
        int x;
        cin >> x;
        x = !x;
        cout << x << endl;
    }
}

Measured memory_bytes: 3632
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl

int main() {
    string s; cin >> s;
    int cnt = 0;
    for(int i=0; i<s.size(); i++){
        if(s.at(i)=='+') cnt++;
        else cnt--;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;


int main(){
  int i,j;
  int n;
  cin>>n;
  int x[n],y[n];
  for(i=0;i<n;i++){
    cin>>x[i]>>y[i];
  }
  double ans=0;
  for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
      ans+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    }
  }
  
  cout<<fixed<<setprecision(15)<<2.0*ans/(double)n<<endl;

  
}


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

int main()
{
  int n;
  cin>>n;
  int x=n/1000;
  //int r=x%1000
  int p=n-1000*x;
  int ans=0;
  if(p>0)
    ans=1000-p;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pii pair<ll,ll>
#define tii tuple<ll,ll,ll>
#define all(v) (v).begin(),(v).end()
#define ll long long
#define deb(x) cout << #x << "=" << x << endl;
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define ld long double
#define mod 1000000007
#define PI 3.141592653589793238
#define phi 1.638
#define eps 1e-9
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;   

int rem[200005];
vector<set<int>> vec;
int tot = 0;

void dfs(int node) {
    if(rem[node]) return ;
    rem[node] = 1;
    tot++;
    for(auto& it : vec[node]) {
        dfs(it);
    }
}

int main() {
    fastio
    int n, m;
    cin>>n>>m;
    vec = vector<set<int>>(n);

    for(int i = 0; i<m; ++i) {
        int u, v;
        cin>>u>>v;
        u -= 1; v -= 1;
        vec[u].insert(v);
        vec[v].insert(u);
    }

    vector<ll> v;
    for(int i = 0; i<n; ++i) {
        tot = 0;
        if(rem[i]) continue;
        dfs(i);
        v.push_back(tot);
    }

    cout<<*(max_element(all(v)))<<endl;
}

Measured memory_bytes: 38312
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    set<int> st;
    int cnt=0;
    REP(i,N){
        int a; cin>>a;
        if(a<3200) st.insert(a/400);
        else cnt++;
    }
    if(st.size()==0){
        cout<<1<<' '<<cnt<<endl;
    }
    else{
        cout<<st.size()<<' '<<st.size()+cnt<<endl;
    }
}


Measured memory_bytes: 256
using System;

namespace Children_and_Candies_ABC_Edit
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());

            var sum = 0;
            for (int i = 0; i <= n; i++)
            {
                sum = sum + i;
            }

            Console.WriteLine(sum);
        }
    }
}


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

#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define rep(i,N) repr(i,0,N)
#define all(vec) vec.begin(), vec.end()
#define per(i,N) for (int i=(int)N-1; i>=0; i--)
//#define int long long
#define endl "\n"

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

  int N, K;
  cin >> N >> K;

  int ans = K * pow(K-1, N-1);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

S = gets.chomp
T = gets.chomp

ans = false
sx = S.split('')

i = 1
while i <= sx.length
  str = S[(-i)..] + S[0..(-i-1)]
  ans = true if str == T
  i += 1
end

puts ans ? 'Yes' : 'No'


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

int main()
{
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int min = 0;
    if (d < b)
    {
        min += 60 - b + d;
        min += (c - a - 1) * 60;
    }
    else
    {
        min += d - b;
        min += (c - a) * 60;
    }
    int diff = min - e;

    if (diff <= 0)
        cout << 0 << endl;
    else
        cout << diff << endl;
}

Measured memory_bytes: 3624
import sys

class Solution(object):
    def __init__(self):
        self.n = int(sys.stdin.readline())
        self.colors = sys.stdin.readline()

    def get_combined_slimes(self):
        count = 1
        curr_color = self.colors[0]
        for i in range(1, len(self.colors)-1):
            if curr_color != self.colors[i]:
                #print("curr color ", curr_color)
                #print("new color ", self.colors[i])
                curr_color = self.colors[i]
                count += 1
        return count

if __name__ == "__main__":
    s = Solution()
    print(s.get_combined_slimes())

Measured memory_bytes: 3188
S=input()
w=int(input())
Sdash=[]
a=''
for i in range(0,len(S)//w):
    Sdash.append(S[w*i:w*(i+1)])
if len(S)%w!=0:
    Sdash.append(S[((len(S)//w)*w):])
for i in range(len(Sdash)):
    a+=Sdash[i][0]
print(a)

Measured memory_bytes: 9132
/*
=============================================================

------------------Welcome To My Code-------------------------

---------Ankit Kumar || IIITBH || CSE || 2018-2022-----------

=============================================================
*/

#include <bits/stdc++.h>
using namespace std;

#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vl(p) vector<p>
#define w while
#define For(i,s,x) for(i=s;i<x;i++)
#define Fore(i,s,x) for(i=s;i<=x;i++)
#define FOR(i,x) for(i=0;i<x;i++)
#define Rof(i,s,x) for(i=s;i>=x;i--)
#define all(v) v.begin(),v.end()
#define it(r,v) for(auto r=v.begin();r!=v.end();r++)
#define pb push_back
#define in insert
#define sz size()
#define F first
#define S second
#define nl cout<<"\n"
#define pr(a) cout<<a<<" "
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define pr3(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n"
#define mod 1000000007
map<ll, ll>::iterator itr;
vector<ll>::iterator it, it1;
const double PI = 3.141592653589793238;

int main()
{
	FASTIO;
	ll t;

        ll i,j,k,x,y,z,m,n,a,b,c,c1=0,c2=0,flag=0,sum=0;
	string s,s1,str;

	cin>>n>>x;
	x=x*x;
	FOR(i,n)
	{
	    cin>>y>>z;
	    y=y*y;
	    z=z*z;
	    a=y+z;

	    if(a<=x)
            c1++;
	}
	cout<<c1;
	nl;

}


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

inline int read()
{
	int x=0,f=1,c=getchar();
	while(c<48) c=='-'&&(f=-1),c=getchar();
	while(c>47) x=x*10+c-'0',c=getchar();
	return x*f;
}

const int MAXN = 400005;
struct Edge {int u,v,w;} e[MAXN];
int fa[MAXN],f[MAXN];
int n,m,q;

inline int find(int x)
{return x^fa[x]?fa[x]=find(fa[x]):x;}

inline void merge(int x,int y)
{((x=find(x))^(y=find(y)))&&(fa[x]=y);}

int main(int argc,char const *argv[])
{
	n=read(); q=read();
	memset(f,0x3f,sizeof(f));
	for(int i=1,a,b,c; i<=q; ++i)
	{
		a=read()+1,b=read()+1,c=read();
		f[a%n+1]=min(f[a%n+1],c+1);
		f[b%n+1]=min(f[b%n+1],c+2);
		e[++m]=Edge{a,b,c};
	}
	int pos=1;
	for(int i=2; i<=n; ++i) if(f[i]<f[pos]) pos=i;
	for(int i=pos%n+1,j=pos; i!=pos; j=i,i=i%n+1)
		f[i]=min(f[i],f[j]+2);
	for(int i=1; i<n; ++i)
		e[++m]=Edge{i,i+1,f[i+1]};
	e[++m]=Edge{n,1,f[1]};
	sort(e+1,e+m+1,[](Edge a,Edge b) {return a.w<b.w;});
	for(int i=1; i<=n; ++i) fa[i]=i;
	long long tot=0,ans=0;
	for(int i=1; i<=m; ++i)
	{
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)==find(v)) continue;
		++tot,ans+=w,merge(u,v);
		if(tot==n-1) break;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 12948
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

struct State{
    int v, l, c;
    State(int v, int l, int c): v(v), l(l), c(c) {}
    bool operator<(const State& right ) const {
        return c > right.c;
    }
};

struct edge{
    int to, l, c;
    edge(int to, int l, int c): to(to), l(l), c(c) {}
};

int dp[102][102];

int main(){
    while(true){
        int N, M, L;
        cin >> N >> M >> L;
        if(N == 0) break;

        vector<vector<edge>> G(N);
        for(int i=0;i<M;i++){
            int A, B, D, E;
            cin >> A >> B >> D >> E;
            A--; B--;
            G[A].emplace_back(B, D, E);
            G[B].emplace_back(A, D, E);
        }

        int ans = -1;
        priority_queue<State> que;
        que.emplace(0, L, 0);

        memset(dp, -1, sizeof(dp));
        dp[0][L] = 0;

        while(que.size()){
            State s = que.top(); que.pop();
            if(dp[s.v][s.l] != -1 && dp[s.v][s.l] < s.c) continue;
            if(s.v == N-1){
                ans = s.c;
                break;
            }
            for(edge e : G[s.v]){
                int nv = e.to, nl = s.l, nc = s.c + e.c;
                if(dp[nv][nl] == -1 || dp[nv][nl] > nc){
                    dp[nv][nl] = nc;
                    que.emplace(nv, nl, nc);
                }
            }
            for(edge e : G[s.v]){
                if(s.l >= e.l){
                    int nv = e.to, nl = s.l - e.l, nc = s.c;
                    if(dp[nv][nl] == -1 || dp[nv][nl] > nc){
                        dp[nv][nl] = nc;
                        que.emplace(nv, nl, nc);
                    }
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3240
#include <cstdio>
#include <queue>
const int N=1e5+5;
const int M=4e5+5;
const long long inf=1LL<<60;
int n,m,tot,hd[N],ter[M],nxt[M],val[M];
long long dis[N];
bool vis[N],inq[N];
std::queue<int> q;

void add(int u,int v,int w) {
	ter[++tot]=v;
	val[tot]=w;
	nxt[tot]=hd[u];
	hd[u]=tot;
}
bool spfa(int s) {
	q.push(s),vis[s]=inq[s]=1,dis[s]=0;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=hd[u];i;i=nxt[i]) {
			int v=ter[i];
			if(dis[v]==inf) {
				dis[v]=dis[u]+val[i];
				vis[v]=1;
				if(!inq[v]) q.push(v),inq[v]=1;
			} else {
				if(dis[v]!=dis[u]+val[i]) return 0;
			}
		}
		inq[u]=0;
	}
	return 1;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int u,v,w;m;--m) {
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,-w);
	}
	for(int i=1;i<=n;++i) dis[i]=inf;
	for(int i=1;i<=n;++i) if(!vis[i]&&!spfa(i)) return puts("No"),0;
	puts("Yes");
	return 0;
}

Measured memory_bytes: 6656
import std.stdio, std.string, std.conv;

void main() {
    int n = readln.chomp.to!int;
    bool ok;
    foreach (i; 1 .. 10) {
        foreach (j; 1 .. 10) {
            if (i * j == n) ok = true;
        }
    }
    writeln(ok ? "Yes" : "No");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX =2000007;
const int MOD = 998244353;
//
int modpow(int a, int n, int mod) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
     signed main(){
  int n;
  cin>>n;
  int x[n],y[n];for(int i=0;i<n;i++)cin>>x[i]>>y[i];
  bool used[n][n];for(int i=0;i<n;i++)fill(used[i],used[i]+n,false);
  int ans=(modpow(2,n,MOD)+MOD-n-1)%MOD;
  for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
      if(used[i][j])continue;
      vector<int> v;
      v.push_back(i);v.push_back(j);
      for(int k=j+1;k<n;k++)if((x[i]-x[k])*(y[i]-y[j])==(y[i]-y[k])*(x[i]-x[j]))v.push_back(k);
      ans=(ans+MOD-modpow(2,v.size(),MOD)+v.size()+1)%MOD;
    for(int p=0;p<v.size();p++)for(int q=p+1;q<v.size();q++)used[v[p]][v[q]]=true;
  }
  cout<<ans<<endl;

     }


 


 






    





      

        


Measured memory_bytes: 3672
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);
#if __cplusplus>=201700L
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
#endif

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}


void solve(long long N, std::vector<long long> x, std::vector<long long> y){
  long double sum=0.0;
  REP(N){
    FOR(j,i+1,N){
      ll dx=x[i]-x[j],dy=y[i]-y[j];
      sum+=sqrtl(dx*dx+dy*dy);
    }
  }
  sum*=2;
  sum/=N;
  cout<<setprecision(100)<<sum<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> x(N);
    std::vector<long long> y(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&x[i]);
        scanf("%lld",&y[i]);
    }
    solve(N, std::move(x), std::move(y));
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

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


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


int64_t solve(int64_t n){
  if(n==0 || n==1){return 0;}
  return n * (n-1) / 2;
}


int main(void){
  int N;
  cin >> N;
  vector<int> A;
  map<int,int> Am;
  for(int i=0;i<N;i++){
    int tmp;
    cin >> tmp;
    Am[tmp] = Am[tmp] + 1;
    A.push_back(tmp);
  }
  
  int64_t total = 0;
  for(auto it=Am.begin();it != Am.end() ; ++it) {
    int64_t count = solve(it->second);
    total += count;
  }
  
  for(int i=0;i<N;i++){
    int64_t target = Am[A[i]];
    cout << total - (target -1) << endl;
  }
}


Measured memory_bytes: 8308
n, m = map(int, raw_input().split())
a = [map(int, raw_input().split())[::-1] for _ in xrange(n)]
ans = n
d = [0] * (m + 1)
for i in xrange(m):
    s = [0] * (m + 1)
    for j in xrange(n):
        while d[a[j][-1]]:
            a[j].pop()
            continue
        s[a[j][-1]] += 1
    l = 1
    for i in xrange(m + 1):
        if s[l] < s[i]:
            l = i
    d[l] = 1
    ans = min(ans, s[l])
print ans


Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for( int i = 0 ; i < n ; i++ )
typedef long long ll ;
int main() {
  int A , B ;
  cin >> A >> B ;
  rep(i,1e8){
    int A1 = i * 0.08 ;
    int B1 = i * 0.1 ;
    if( A1 == A && B1 == B ){
      cout << i << endl;
      return 0 ;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>

#define x first
#define y second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define bit __builtin_popcount
#define all(x) x.begin(),x.end()

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const ll INF=1e18+123;
const ld EPS=1e-9;
const int inf=1e9+123;
const int MOD=1e9+7;
const int N=1e5+123;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin>>s;
    int n;
    cin>>n;
    for(int i=0;i<s.size();i+=n){
        cout<<s[i];
    }
    return 0;
}


Measured memory_bytes: 256
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　RedcoderになるためAtCoderを巡る旅をしてます。

　　　 　＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　   ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣￣/ヽ
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl

#define rep(i, n) REP(i, 0, n)                  // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++) // x, x + 1, ..., n-1
#define FOREACH(x, a) for(auto &(x) : (a))

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}

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

    int a; string s; cin >> a >> s;
    if(a >= 3200) COUT(s);
    else COUT("red");
}


Measured memory_bytes: 3620
n=int(input())
h=input().split()
for i in range(n):
    h[i]=int(h[i])
ans=1
x=[]
x.append(h[0])
for j in range(1,n):
    if h[j]>=max(x):
        ans+=1
    x.append(h[j])
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f(a, b) for (ll i = a; i <= b; i++)
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
#define N 100005
const ll INF = 1000000001;
const ll MOD = 998244353 ; //1e9+7;

vector< vector<ll> > g(N);
//vector< pair<ll, pair< ll, ll > > > g(N);
ll vis[N] = {0}, par[N] = {0}, child[N] = {0}, dp[N] = {0};

void dfs(ll v){
    vis[v] = 1;
    for(auto u: g[v]){
        if(!vis[u]){
            dfs(u);
        }
        dp[v] = max(dp[v], 1 + dp[u]);
    }
}

void solve(){
    ll n, m; cin >> n >> m;
    f(0, m-1){
        ll x, y;cin >> x >> y;
        g[x].pb(y);
    }
    ll ans = -INF;
    f(1, n){
        if(!vis[i]) dfs(i);
    }
    f(1, n) ans = max(ans, dp[i]);
    cout << ans << '\n';
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    //ll t;cin >> t;for(ll index=1; index<=t; index++){
        //cout << "Case #" << index << ": " ;
        solve();
    //}
    return 0;
}


Measured memory_bytes: 12992
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[]) {
  int n, k;
  cin >> n >> k;
  int ans = n - k + 1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int prime(int x){
	if(x==2||x==3)
		return 1;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
			return 0;
	return 1;
}
int main(){
	int n;
	while(cin>>n){
		int ans=0;
		int x;
		for(int i=0;i<n;i++){
			cin>>x;
			if(prime(x))
				ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
const ll MAX=200005;
vector<ll>G[MAX];
vector<ll>ans(MAX);
vector<ll> siz(MAX);
ll rui(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void preDFS(ll u,ll p){
    for(int to:G[u]){
        if(to==p)continue;
        preDFS(to,u);
        siz[u]+=siz[to];
    }
    siz[u]++;
}
ll sum=1;
void DFS(ll u,ll p){
    ans[u]=sum;
    for(int to:G[u]){
        if(to==p)continue;
        ll a=siz[u],b=siz[to],c=sum;
        sum*=siz[to];
        sum%=mod;
        siz[u]-=siz[to];
        sum*=rui(siz[u],mod-2);
        sum%=mod;
        siz[to]=a;
        DFS(to,u);
        siz[u]=a;
        siz[to]=b;
        sum=c;
    }
}
int main(){
    ll n;cin>>n;
    rep(i,n-1){
        ll a,b;cin>>a>>b;
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    preDFS(0,-1);
    REP(i,1,n){
        sum*=i;
        sum%=mod;
    }
    REP(i,1,n){
        sum*=rui(siz[i],mod-2);
        sum%=mod;
    }
    DFS(0,-1);
    rep(i,n){
        cout<<ans[i]<<"\n";
    }
}

Measured memory_bytes: 17776
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <queue>

using namespace std;
const int maxn = 800005;

struct node {int l,r;}p[maxn];
int n,m,ans;
bool comp(node a,node b) {
	return a.l<b.l;
}
namespace ST {
	#define ls rt<<1
	#define rs rt<<1|1
	int tag[maxn],maxv[maxn];
	void update(int rt) {maxv[rt]=max(maxv[ls],maxv[rs]);}
	void add(int rt,int v) {maxv[rt]+=v;tag[rt]+=v;}
	void pushdown(int rt) {
		if (int v=tag[rt]) {
			add(ls,v);add(rs,v);tag[rt]=0;
		}
	}
	void build(int rt,int L,int R)
	{
		maxv[rt]=R-m-1;
		if (L>=R) return ;
		int mid=L+R>>1;
		build(ls,L,mid);build(rs,mid+1,R);
		update(rt);
	}
	void modify(int rt,int L,int R,int l,int r)
	{
		if (L>=l&&R<=r) {add(rt,1);return ;}
		int mid=L+R>>1;pushdown(rt);
		if (l<=mid) modify(ls,L,mid,l,r);
		if (r>mid) modify(rs,mid+1,R,l,r);
		update(rt);
	}
}
using namespace ST ;

int main()
{
	#ifdef LOCAL_JUDGE
		freopen("exhausted.in","r",stdin);
		freopen("exhausted.out","w",stdout);
	#endif
	scanf("%d %d",&n,&m);ans=max(0,n-m);
	for (int i=1;i<=n;i++)
		scanf("%d %d",&p[i].l,&p[i].r);
	sort(p+1,p+n+1,comp);build(1,0,m+1);
	for (int j=1,i=0;i<=m;i++)
	{
		while (j<=n&&p[j].l<=i) {
			modify(1,0,m+1,0,p[j].r);++j;
		}
		ans=max(ans,maxv[1]-i);
	}
	printf("%d",ans);
	return 0;
}

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

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = m - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  //cout<<fixed<<setprecision(10);
  ll res=0,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<pair<ll,P>>a(n);
  rep(i,0,n){
    cin>>a[i].se.fi>>a[i].fi>>a[i].se.se;
    a[i].fi+=a[i].se.fi;
  }
  sort(ALL(a));
  auto dp=vec(n+1,20001,0LL);
  rep(i,0,n){
    ll w=a[i].se.fi,s=a[i].fi-a[i].se.fi,v=a[i].se.se;
    rep(j,0,s+1){
      chmax(dp[i+1][j+w],dp[i][j]+v);
    }
    rep(j,0,20001){
      chmax(dp[i+1][j],dp[i][j]);
    }
  }
  cout<<*max_element(ALL(dp[n]))<<endl;
  return 0;
}

Measured memory_bytes: 160640
#include <bits/stdc++.h>
using namespace std;
int main(){
int H, W,i;
cin >> H >>W;
vector <string>vec(H);
for(i=0;i<H;i++){
cin >>vec.at(i);
}
string s = "#";
for(i=0;i<W+2;i++){
cout << s;
}
cout<<endl;
for(i=0;i<H;i++){
cout << s << vec.at(i)<<s<<endl;
}

for(i=0;i<W+2;i++){
cout << s;
}
cout<<endl;
}


Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main() {
    int n,l;
    cin>>n>>l;
    int min_legs = 2*n;
    int max_legs = 4*n;
    if(l>=min_legs&&l<=max_legs)
    {
        if(l==min_legs)
        cout<<"Yes\n";
        else if(l==max_legs)
        cout<<"Yes\n";
        else
        {
        int flag = 0;
        for(int i = 1;i<n;i++)
        {
            int res = i*2 + (n-i)*4;
            if(res==l)
            {
                cout<<"Yes\n";
                flag = 1;
                break;
            }
        }
        if(flag==0)
        cout<<"No\n";
        }
    }
    else
    {
        cout<<"No";
    }

}


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

constexpr int64_t INF = 1'010'000'000'000'000'017LL;
constexpr int64_t MOD = 1'000'000'007LL;
constexpr double EPS = 1e-12;
constexpr double PI = 3.14159265358979323846;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

void primeFactorization2(uint64_t number, list<uint64_t> &factors){
  uint64_t val = sqrt(number);
  for (uint64_t i = 2; i <= val; i++){
    while (number % i == 0){
      number /= i;
      factors.push_back(i);
	}
  }
  if(number != 1){
    factors.push_back(number);
  }
}

signed main() {
  uint64_t x;
  for(int i = 1; i<=5; i++){
  	cin >> x;
    if(x==0){
      cout << i << endl;
      return 0;
    }
  }
  
  return 0;
}

Measured memory_bytes: 3652
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        String s = scanner.next();
        for (char ch = 'a'; ch <= 'z'; ch++) {
            if (s.indexOf(ch) == -1) {
                System.out.println(ch);
                return;
            }
        }
        System.out.println("None");
    }
}

Measured memory_bytes: 26068
N = int(input())
dp = dict()

dp[0] = 0
# 貰う DP --- dp[n] に遷移を集める
for n in range(1, N+1):
  dp[n] = dp[n-1] + 1
  
  # メモ化
  x = 6
  while x <= n:
    dp[n] = min(dp[n], dp[n-x]+1)
    x *= 6
  
  x = 9
  while x <= n:
    dp[n] = min(dp[n], dp[n-x]+1)
    x *= 9
    
  # dp[n] = ans
  
print(dp[N])

Measured memory_bytes: 15072
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;

// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;
long long stuff[401][401];
long long sums[401][401];
int main ()
{
  prep();
  int n, c;
  cin >> n >> c;
  int a[n];
  int b[n];
  for (int i=0; i<n; i++){
      cin >> a[i];
  }
  for (int i=0; i<n; i++){
      cin >> b[i];
  }
 
  for (int i=1; i<=400; i++){
      sums[i][0] = 1;
      for (int j=1; j<=400; j++){
          sums[i][j] = (sums[i][j-1]*i)%mod;
      }
  }
  for (int i=1; i<=400; i++){
      for (int j=0; j<=400; j++){
          sums[i][j] = (sums[i][j]+sums[i-1][j])%mod;
      }
  }
  stuff[n][0] = 1;
  for (int i=n-1; i>=0; i--){
      for (int j=0; j<=c; j++){
          // make the jth one
          for (int k=0; k<=j; k++){
              stuff[i][j] = (stuff[i][j]+(mymod(sums[b[i]][k]-sums[a[i]-1][k])*stuff[i+1][j-k])%mod)%mod;
          }
      }
  }
 
  cout << stuff[0][c];
  return 0; 
}

Measured memory_bytes: 2816
encode = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + " .,-\'?"
decode = {"101":" ","000000":"\'","000011":",","10010001":"-","010001":".","000001":"?",
          "100101":"A","10011010":"B","0101":"C","0001":"D","110":"E","01001":"F",
          "10011011":"G","010000":"H","0111":"I","10011000":"J","0110":"K","00100":"L",
          "10011001":"M","10011110":"N","00101":"O","111":"P","10011111":"Q","1000":"R",
          "00110":"S","00111":"T","10011100":"U","10011101":"V","000010":"W","10010010":"X",
          "10010011":"Y","10010000":"Z"}
while True:
    try:
        s = input()
        code = ""
        for inp in s:
            code += format(encode.find(inp), "05b")
        ans = ""
        tmp = ""
        for inp in code:
            tmp += inp
            if tmp in decode:
                ans += decode[tmp]
                tmp = ""
        print(ans)
    except:
        break



Measured memory_bytes: 5596
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

/*
自分の周囲にBがあるならB
自分の周囲にWがあるならW
自分の周囲に両方があるならG
*/

char map[52][52];
bool flag[52][52];
int xv[]={0,1,0,-1};
int yv[]={1,0,-1,0};
int Bf,Wf,cnt;


void dfs(int X,int Y){
	flag[X][Y]=1;
	cnt++;
	
	for(int i=0;i<4;i++){
		if(map[X+xv[i]][Y+yv[i]]=='B')Bf=1;
		else if(map[X+xv[i]][Y+yv[i]]=='W')Wf=1;
		else if(map[X+xv[i]][Y+yv[i]]=='.'&&flag[X+xv[i]][Y+yv[i]]==0){
			dfs(X+xv[i],Y+yv[i]);
		}
	}
	
}

int main(){
	int W,H;
	while(cin>>W>>H,W){
		
		int BB=0,WW=0;
		for(int i=0;i<=W+1;i++)map[i][0]=map[i][H+1]='#';
		for(int i=0;i<=H+1;i++)map[0][i]=map[W+1][i]='#';
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				cin>>map[j][i];
			}
		}
		memset(flag,0,sizeof(flag));
		
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				if(!flag[j][i]&&map[j][i]=='.'){
					Bf=Wf=cnt=0;
					dfs(j,i);
					if(Bf&&!Wf)BB+=cnt;
					if(!Bf&&Wf)WW+=cnt;
				}
			}
		}
		cout<<BB<<" "<<WW<<endl;
	}
	
	
	
	return 0;
}


Measured memory_bytes: 1236
#include "bits/stdc++.h"

#define REP(i,num) for(ll i=0;i<(num);++i)
#define FOR(i,c,num) for(ll (i)=(c);(i)<(num);++(i))
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){T x; cin >> x; return (x);}
template<typename T=ll,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

ll safemod(ll a,ll m){
	return (a%m+m)%m;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	auto N=in(),M=in();
	vll X=vecin(N),Y=vecin(M);
	vll W(N-1),H(M-1);
	REP(i,N-1){
		W[i] = X[i+1]-X[i];
		ll L=i+1ll,R=N-i-1;
		W[i] = ((((L*R)%atcoder_mod)*W[i])%atcoder_mod);
	}

	ll HS=0;
	REP(i,M-1){
		H[i] = Y[i+1]-Y[i];
		ll L=i+1ll,R=M-i-1;
		H[i] = ((((L*R)%atcoder_mod)*H[i])%atcoder_mod);
		HS += H[i];
		HS %= atcoder_mod;
	}
	
	ll S=0;
	REP(i,N-1){
		S += (W[i]*HS)%atcoder_mod;
		S %= atcoder_mod;
	}
	out(S);
	return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
	int n, xr = 0;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
		xr ^= a[i];
	}
	for (int i = 0; i < n; ++i)
	{
		cout << (xr ^ a[i]) << ' ';
	}
	return 0;
}

Measured memory_bytes: 4012
#include<iostream>
#include<cstdint>
using namespace std; // 575

const int MAX = 200001;

int main() {
	int L;
	static int64_t A[MAX];
	cin >> L;
	for (int i = 0;i < L;++ i) cin >> A[i];
	static int64_t sum[MAX], sumL[MAX], sumR[MAX], sumL2[MAX], sumR2[MAX];
	sum[0] = sumL[0] = sumR[L] = sumL2[0] = 0;
	for (int i = 0;i < L;++ i) sum[i + 1] = sum[i] + A[i]; // いつもの累積和
	for (int i = 0;i < L;++ i) {
		sumL[i + 1] = min(sum[i + 1], sumL[i] + (A[i] == 0 ? 2 : A[i] & 1));
		sumR[L - i - 1] = min(sum[L] - sum[L - i - 1], sumR[L - i] + (A[L - i - 1] == 0 ? 2 : A[L - i - 1] & 1)); // 逆側から見た累積和
		sumL2[i + 1] = sumL2[i] + (A[i] & 1 ? 0 : -1);
	}
	sumR[L] -= sumL2[L];
	for (int i = 0;i < L;++ i) {
		sumL[i + 1] += sumL2[i + 1];
		sumR[L - i - 1] -= sumL2[L - i - 1];
		sumR[L - i - 1] = min(sumR[L - i - 1], sumR[L - i]);
	}
	static int64_t ans = sumL[0] + sumR[0];
	for (int i = 0;i < L;++ i) { // iが左端
		ans = min(ans, sumL[i + 1] + sumR[i + 1]);
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

まず、移動開始位置が決まっていたとする
その時、次の点に注意
・その数列中における奇数マスは通過しつつ全消し、偶数マスは丁度止まりつつ全消しできる
ということは、すぬけが動く範囲における大きい数字はすべて2まで2ずつ引いても問題ない(これはO(1)操作)
すると入力例2は2-0-0-2-1-1-2-1になるが
ここで、端は2、それ以外は1に関しては0にできて、そうでないところは1になる性質を持つ
つまり、端さえ分かっていれば答えを出すのは簡単よ
今、累積和として0の個数、1の個数、2の個数を出していたとする
0-0-1-2-2-2-2-2-2 0の個数
0-0-0-0-0-1-2-2-3 1の個数
0-1-1-1-2-2-2-3-3 2の個数
で、今区間を指定したとき、その操作回数は(範囲外の値合計)+(範囲内で、端の連続した2以外にある2の合計)で求められる
ただ両端を指定してしまうとこれはO(L^2)だ、もっといい性質はないかな？
まず操作は順番変えても良いので、左端スタートにしておくよね
そうしたときに右側を一意に定められるのかは大事そう
ここで、今0で区切られているところはいったん別に考えるとする
この時、操作区間に関してはまず左端は

…省略
*/

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>
 
using namespace std;
 
const double eps=1e-10;

int main()
{

	int b[]={48,51,54,57,60,64,69,75,81,91};
	string g[]={
		"light fly",
		"fly",
		"bantam",
		"feather",
		"light",
		"light welter",
		"welter",
		"light middle",
		"middle",
		"light heavy",
	};

	double w;
	while(cin>>w){
		bool h=true;
		for(int i=0;i<10 && h ;i++){
			if(w<=b[i]){cout<<g[i]<<endl; h=false;}
		}
		if(h) cout<<"heavy"<<endl;
	}

	return 0;
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define sort(vec) sort(vec.begin(),vec.end())
#define reverse(vec) reverse(vec.begin(),vec.end())
int gcd(int x,int y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
int n,ans=0;
vector<int>a(600000);
signed main(){
    cin>>n;
    rep(i,3*n)cin>>a[i];
    sort(a);
    reverse(a);
    rep(i,2*n){
        if(i%2)ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}

    

Measured memory_bytes: 4992
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a%2==1 && b%2==1)    System.out.println("Odd");
        else    System.out.println("Even");
    }
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#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()
 
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<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

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<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

vector<ll> g[205];
ll col[205];
bool dfs(int v, int c) {
    col[v] = c;
    for(auto to: g[v]) {
        if(col[to] == c) return false;
        if(col[to] == 0 && !dfs(to, -c)) return false;
    }
    return true;
}

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

    ll n;
    cin >> n;
    vector<string> s(n);
    REP(i, n) cin >> s[i];

    REP(i, n) FOR(j, i+1, n) {
        if(s[i][j] == '1') {
            g[i].push_back(j);
            g[j].push_back(i);
        }
    }
    REP(i, n) {
        if(col[i] == 0) {
            bool ret = dfs(i, 1);
            if(!ret) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    vector<vector<ll>> dist(n, vector<ll>(n, LLINF));
    REP(i, n) dist[i][i] = 0;
    REP(i, n) REP(j, n) if(s[i][j]=='1') dist[i][j] = 1;
    REP(k, n) REP(i, n) REP(j, n) chmin(dist[i][j], dist[i][k]+dist[k][j]);
    
    ll ret = 2;
    REP(i, n) REP(j, n) chmax(ret, dist[i][j]+1);
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 896