akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
main()
{
	int N;
	while(cin>>N,N)
	{
		vector<pair<string,pair<int,int> > >A;
		for(int i=0;i<N;i++)
		{
			string f;int w,s;cin>>f>>w>>s;
			A.push_back(make_pair(f,make_pair(w,s)));
		}
		sort(A.begin(),A.end());
		vector<string>ans;
		double mG=1e150;
		do{
			bool flag=true;
			int T=0;
			for(int i=0;i<N;i++)
			{
				if(T>A[i].second.second)
				{
					flag=false;
					break;
				}
				T+=A[i].second.first;
			}
			if(flag)
			{
				double G=0;
				for(int i=0;i<N;i++)G+=A[i].second.first*(N-i);
				G/=T;
				if(mG>G)
				{
					mG=G;
					ans.clear();
					for(int i=N;i--;)ans.push_back(A[i].first);
				}
			}
		}while(next_permutation(A.begin(),A.end()));
		for(int i=0;i<N;i++)cout<<ans[i]<<endl;
	}
}



Measured memory_bytes: 3180
S = list(input())
ans = 0
tmp = S[0]
for i in range(0,len(S)-1,2):
    if tmp != S[i]:
        ans += 1
        S[i] = tmp
    if S[i] == S[i+1]:
        ans += 1
if len(S)%2 == 1:
    if S[-1] != tmp:
        ans += 1
print(ans)

Measured memory_bytes: 4008
#include<stdio.h>
#define N 101
#define WHITE 0
#define BLACK 1
#define GRAY 2
typedef struct{
  int k;
  int d;
  int color;
  int v[N];
} Graph;
Graph g[N];
int n,head=0,tail=0,q[N];

void enqueue(int x)
{
  q[tail] = x;
  if(tail+1 == N-1) tail = 0;
  else tail++;
}

int dequeue()
{
  int x;
  x = q[head];
  if(head+1 == N-1) head=0;
  else head++;
  return x;
}

void bfs()
{
  int i,u,v;
  for(i=2; i<=n; i++) {
    g[i].color = WHITE;
    g[i].d = N+1;
  }
  g[1].color = GRAY;
  g[1].d = 0;
  enqueue(1);
  while(head!=tail) {
    u = dequeue();
    for(i=0; i<g[u].k; i++){
      v=g[u].v[i];
      if(g[v].color == WHITE){
        g[v].color = GRAY;
        g[v].d = g[u].d +1;
        enqueue(v);
      }
    }
    g[u].color = BLACK;
  }
}

int main()
{
  int u,i,j,k;
  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%d%d",&u,&k);
    g[u].k = k;
    for(j=0; j<g[u].k; j++) {
      scanf("%d",&g[u].v[j]);
    }
  }
  bfs();
  for(i=1; i<=n; i++) {
    if(g[i].d == N+1) g[i].d = -1;
  }
  for(i=1; i<=n; i++){
    printf("%d %d\n",i,g[i].d);
  }
  return 0;
}

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

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	string s;
	cin >> s;
	int n = s.size(), ss = -1;
	vector<int> ans (n + 1, 0);
	for (int i = 0; i < n; ++i){
		if (s[i] == 'R'){
			int left = i;
			while (left < n && s[left] == 'R'){
				left++;
			}
			int right = left;
			left--;
			while (right < n && s[right] == 'L'){
				right++;
			}
			right--;
			int t1 = left - i + 1, t2 = right - left;
			i = right;
			right = left + 1;
			if (t2 % 2 == 1){
				swap(left, right);
			}
			ans[left] += (t1 + t2) / 2 + (t1 + t2) % 2;
			ans[right] += (t1 + t2) / 2;
		}	
		else{
			int left = i;
			while (left < n && s[left] == 'L'){
				left++;
			}
			ans[i] += left;
			i = left - 1;
		}
	}
	for (int i = 0; i < n; ++i){
		cout << ans[i] << " ";
	}
	return 0;
}



Measured memory_bytes: 1104
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,b;
  int sum=0;
  cin>>n>>a>>b;
  for(int i=1;i<=n;i++){
    int temp=i;
    int p=0;
    while(temp){
      p+=temp%10;
      temp/=10;
    }
    if(a<=p&&p<=b)sum+=i;
  }
  cout<<sum<<endl;
  return(0);
}


Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
using ll = long long;

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

int main() {
  int N;
  cin >> N;
  map<ll, int> ns;
  ll a;
  for(int i = 0; i < N; ++i) {
    cin >> a;
    ns[a]++;
  }
  vector<ll> as;
  for(auto n : ns) {
    for(int i = 0; i < n.second / 2; ++i) {
      as.push_back(n.first);
    }
  }
  if(as.size() < 2) {
    cout << 0 << endl;
    return 0;
  }
  sort(as.begin(), as.end(), greater<ll>());
  cout << as[0] * as[1] << endl;
  /*
  ll ans = 0;
  for(int i = 0; i < as.size() - 1; ++i) {
    for(int j = i + 1; j < as.size(); ++j) {
      chmax(ans, as[i] * as[j]);
    }
  }
  cout << ans << endl;
  */
  return 0;
}

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

int main() {
  int n;
  cin >> n;
  long long a[n+1];
  long long b[n];
  for ( int i = 0; i < n+1; i++ ) { cin >> a[i]; }
  for ( int i = 0; i < n; i++ ) { cin >> b[i]; }

  long long ans = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( a[i] >= b[i] ) {
      ans += b[i];
    } else {
      ans += a[i];
      b[i] -= a[i];
      if ( a[i+1] >= b[i] ) {
        ans += b[i];
        a[i+1] -= b[i];
      } else {
        ans += a[i+1];
        a[i+1] = 0;
      }
    }
  }

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


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

const int MAX_N = 110000;

int memo[MAX_N]; // memo[i] が i についての答え
int rec(int n) {
    if (n == 0) return 0; // 終端条件
    if (memo[n] != -1) return memo[n]; // すでに探索済みならリターン

    int res = n; // INF の気持ち

    // 1, 6, 6^2, ..., を試す (n を超えない範囲で)
    for (int pow6 = 1; pow6 <= n; pow6 *= 6) res = min(res, rec(n - pow6) + 1);

    // 1, 9, 9^2, ..., を試す (n を超えない範囲で)
    for (int pow9 = 1; pow9 <= n; pow9 *= 9) res = min(res, rec(n - pow9) + 1);

    // メモしながらリターン
    return memo[n] = res;
}

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

    // テーブルを -1 で初期化
    for (int i = 0; i < MAX_N; ++i) memo[i] = -1;
    cout << rec(N) << endl;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
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;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void anss(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=0,res2=INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0,sum=0;
  ll l,r;
  bool judge = true;
  ll a,b;cin>>a>>b;
  cout<<(a+b)%24<<endl;

  return 0;
}

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

int main() {
    string s;
    cin >> s;
    string ans = "Yes";
    for (size_t i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - 1]) ans = "No";
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(a) ((a).begin(), (a).end())
typedef long long ll;
// const long long INF = 1LL << 60;
const int INF = 1010101010;
// using Graph = vector<vector<int>>;
const int MOD = 1000000007;

int main() {
  string s;
  cin >> s;
  bool ans = true;
  for (int i = 0; i < s.length() / 2; i++) {
    if (s[i] != s[s.length() - i - 1]) ans = false;
  }
  string k = s.substr(0, (s.length() - 1) / 2);
  for (int i = 0; i < k.length() / 2; i++) {
    if (k[i] != k[k.length() - i - 1]) ans = false;
  }
  string t = s.substr((s.length() + 3) / 2 - 1);
  for (int i = 0; i < t.length() / 2; i++) {
    if (t[i] != t[t.length() - i - 1]) ans = false;
  }
  if (ans)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


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


#define ll long long int
#define vll vector<ll>
#define vllv vector<vector<ll>> 
#define sz size()
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

ll ceil1(ll n,ll m){if(n%m==0){return n/m;}return n/m +1;}
vll factor(ll n){
    vll ans;
    if(n>0)ans.pb(1);if(n==2)ans.pb(2);
    for(ll i=2;i*i<=n;i++){if(n%i==0){ans.pb(i);if(n/i!=i)ans.pb(n/i);}}if(n>2)ans.pb(n);
    return ans;
}
ll fact(ll n){
	
    ll res = 1; 
    for (ll i = 2; i <= n; i++) 
        res = res * i; 
    return res; 
} 
  
int nCr(ll n, ll r) 
{ 
    return fact(n) / (fact(r) * fact(n - r)); 
} 
  
void dfs(vllv &v,ll k,vll &par,vll &dis,ll p)
{
 
    par[k]=p;
    dis[k]=dis[p]+1;
    for(ll i=0;i<v[k].sz;i++){
        if(v[k][i]!=p){
            dfs(v,v[k][i],par,dis,k);
        }
    }
}
bool sortbysec(const pair<string,int> &a,const pair<string,int> &b){return (a.second<b.second);} 


ll ston(string s) 
{ 
    stringstream geek(s); 
    ll x = 0; 
    geek >> x; 
    
  
    return x; 
}
ll pow2(ll n,ll k){ll ans=1;
    while(k>0){
        if(k%2==1)ans=ans*n;n=n*n;k/=2;
    }return ans;}
bool prime(int n){
    int i,j;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
bool bserch(vector<string> a, string s){
	
	ll l=0,r=a.sz-1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(a[mid]==s)return true;
		if(a[mid]<s){
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	return false;
}

bool sortcol( const vector<int>& v1, 
               const vector<int>& v2 ) { 
 return v1[0] < v2[0]; 
} 

 ll degit(ll n)
 {
 	ll t=0;
 	while(n>0)
 	{
 		t++;
 		n/=10; 	}
 		return t;
 }
 

void solve()
{
	string s,t;
	cin>>s>>t;
	ll n=s.sz+t.sz;
	ll x=0,y=0;
	for(ll i=0;i<n;i++)
	{
		if(i%2==0)
			cout<<s[x],x++;
		else
			cout<<t[y],y++;
	}
	
}
	

int main()
{
	fast;
    ll q;
    q=1;
    // cin>>q;
    while(q--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
def main():

    S = input()
    d = dict()
    d[0] = 1
    v = 0
    p = 1
    for i in range(len(S)):
        v = v + int(S[len(S)-i-1]) * p
        v %= 2019
        d[v] = d.get(v, 0) + 1
        p *= 10
        p %= 2019

    ans = 0
    for v in d:
        ans += d[v] * (d[v] - 1) // 2
    return ans


if __name__ == '__main__':
    print(main())

Measured memory_bytes: 68576
def main():

    N = int(input())
    A = []
    B = []
    C = []

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    # print(C)
    tot = sum(B)
    # print(tot)
    for i in range(N-1):
        if A[i] + 1 == A[i+1]:
            tot += C[A[i]-1]
            # print(i, C[A[i]])

    return tot



if __name__ == '__main__':
    print(main())

Measured memory_bytes: 38256
L, R = list(map(int, input().split()))
a = (L * (L + 1)) % 2019
for i in range(L, min(R + 1, L + 2019)):
    for j in range(i + 1, min(i + 2020, R + 1)):
        if (i * j) % 2019 < a:
            a = (i * j) % 2019
print(a)


Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
     
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,n) for(int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for(int i=(a)-1;i>=b;--i)
#define range(i,a,b,c) for(int i=a;				\
								 c>0?i<b:							\
								 i>b;								\
								 i+=c)
#define chmax(a, b) (a = (a) < (b) ? (b) : (a))
#define chmin(a, b) (a = (a) > (b) ? (b) : (a))
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
#define int long long
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif
     
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int INF = 1 << 28;
const ll INFL = (ll)1 << 58;
ll mod_n = (int)1e9 + 7;
const double eps = 1e-10;
typedef long double Real;
// return -1, 0, 1
int sgn(const Real& r) { return (r > eps) - (r < -eps); }
int sgn(const Real& a, const Real &b) { return sgn(a - b); }
     
//.....................
const int MAX = (int)2e5 + 5;
     
vector<string> split(const string &str, char sep) {
	vector<string> v;
	stringstream ss(str);
	string buffer;
	while (getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}
     
template<class InputIterator>
int sum(InputIterator begin, InputIterator end) {
	return accumulate(begin, end, 0ll);
}

void solve();

signed main() {
	cout << fixed << setprecision(20);
	solve();
	while(true) {
		char s[MAX];
		if (scanf("%s", s) == EOF) break;
		int n = strlen(s);
		for (int i = n - 1; i > -1; i--) {
			ungetc(s[i], stdin);
		}
		solve();
	}
	return 0;
}

class Mycin {
	bool flag = true;
public:
	Mycin& operator >> (int& a) {flag = scanf("%lld", &a) != EOF; return *this;}
	Mycin& operator >> (char& a) {flag = scanf("%c", &a) != EOF; return *this;}
	Mycin& operator >> (string& s) {flag = (bool)(cin >> s); return *this;}
	operator bool() {return flag;}
} mycin;

class Mycout {
public:
	Mycout& operator << (const int& a) {printf("%lld", a); return *this;}
	Mycout& operator << (const char c) {printf("%c", c); return *this;}
	Mycout& operator << (const string& s) {printf("%s", s.c_str()); return *this;}
} mycout;

#define cin mycin
#define cout mycout
#define endl '\n'


int H, W;
string a[105];

void solve() {
	cin >> H >> W;
	rep2(i, 1, H + 1) cin >> a[i];
	rep(j, W + 2) {
		a[0] += '#';
		a[H + 1] += '#';
	}
	rep2(i, 1, H + 1) {
		a[i] = '#' + a[i] + '#';
	}
	rep(i, H + 2) cout << a[i] << endl;
} 


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

long long int a[1000000] = {0},n;

int main(){

  for(int i=2;i*i<=1000000;i++){
    if(a[i] == 0){
      for(int j=i+i;j<=1000000;j+=i) a[j] = 1;
    }
  }

  while(cin >> n, n){

    int ans = 0;

    for(int i=2;i<=n/2;i++){
      if(a[i] == 0 && a[n - i] == 0) ans++;
    }

    cout << ans << endl;

  }
}

Measured memory_bytes: 8972
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define pi 3.14159265358979323846
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

int main()
{

  vector<int> num(3);
  rep(i,3){cin >> num[i];}

  sort(num.begin(),num.end());

  cout << num[2]*10 + num[1] + num[0] << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(){
    int N, K;
    cin >> N >> K;
    vector<ll> V(N);
    for(int  i = 0; i < N; i++){
        cin >> V[i];
    }
    ll maxt = 0, sum = 0;
    if(N >= K){
    for(int i = 0; i < K; i++){//捨てる数
        for(int j = 0; j <= K - i; j++){ //左から何個取るか
            vector<ll> tmpv;
            for(int k = 0; k < j; k++){
                sum += V[k];
                tmpv.push_back(V[k]);
            }
            for(int k = N-1; k >= N - K + i + j; k--){
                sum += V[k];
                tmpv.push_back(V[k]);
            }
            sort(tmpv.begin(), tmpv.end());
            for(int k = 0; k < i; k++){
                if(tmpv[k] < 0 && k < tmpv.size()){
                    sum -= tmpv[k];
                }else{
                    break;
                }
            }
            if(sum > maxt) maxt = sum;
           // cout << sum <<endl;
            sum = 0;
        }
    }
    }else{
        for(int i = 0; i < N; i++){
            for(int j = 0; j <= N; j++){
                vector<ll> tmpv;
                for(int k = 0; k < j; k++){
                    sum += V[k];
                    tmpv.push_back(V[k]);
                }
                for(int k = N-1; k >= max(N - K + i + j,j); k--){
                    sum += V[k];
                    tmpv.push_back(V[k]);
                }
                sort(tmpv.begin(), tmpv.end());
                for(int k = 0; k < i; k++){
                    if(tmpv[k] < 0 && k < tmpv.size()){
                        sum -= tmpv[k];
                    }else{
                        break;
                    }
                }
                if(sum > maxt) maxt = sum;
            // cout << sum <<endl;
                sum = 0;
            }
        }
    }
    cout << maxt << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int N;

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N;
	long long J = 0, B = 0;
	for(int i=0; i<N; i++){
		string x, u;
		cin >> x >> u;
		if(u == "JPY"){
			J += atoll(x.c_str());
		}
		else{
			string t;
			for(int j=0; j<x.size(); j++){
				if(x[j] != '.'){
					t.push_back(x[j]);
				}
			}
			B += atoll(t.c_str());
		}
	}
	long double ans = 0.0;
	ans += J;
	ans += (B/(10000.0))*38.0 ;
	printf("%.12Lf\n", ans);
	return 0;
}

Measured memory_bytes: 3724
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using System.Threading.Tasks;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }
    

    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int A = cin.nextInt();
        int B = cin.nextInt();

        int ans = 0;
        for (int i = A; i <= B; i++)
        {
            if (i == int.Parse(new string(i.ToString().Reverse().ToArray()))) ans++;
        }
        Console.WriteLine(ans);
    }

}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}



Measured memory_bytes: 15416
order = []
str = input()
#print(str)
q = int(input())
for i in range(q):
    s = input().split()
    order.append(s)
#print(order)

for i in range(q):
    a = int(order[i][1])
    b = int(order[i][2])
    #print('a,b=',a,b)
    if order[i][0] == 'print':
            print(str[a:(b+1)])
    elif order[i][0] == 'replace':
        str = str[:a] + order[i][3] + str[(b+1):]
        #print('replace',str)
    elif order[i][0] == 'reverse':
        new_str = list(str[a:(b+1)])
        new_str.reverse()
        new_str = ''.join(new_str)
        str = str[:a] + new_str + str[(b+1):]
        #print('reverse',str)


Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
vector<int>color;
vector<vector<pii>>v;
vector<bool>visited;
void c(int node, int distance){
	if(distance%2==0)color[node] = 1;
	for(pii a: v[node]){
		int n = a.first;
		int w = a.second;
		if(!visited[n]){
			visited[n] = true;
			c(n, distance+w);
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	color = vector<int>(n);
	v = vector<vector<pii>>(n,vector<pii>());
	visited = vector<bool>(n);
	int v1,v2,w;
	for(int i =0; i <n-1; i++){
		cin>>v1>>v2>>w;
		v1--;
		v2--;
		v[v1].pb(make_pair(v2,w));
		v[v2].pb(make_pair(v1,w));
	}
	c(0, 0);
	for(int i =0 ;i < color.size(); i++){
		cout<<color[i]<<"\n";
	}
	return 0;
}

Measured memory_bytes: 11052
def main():
    length, snuke_start, hnuke_start, snuke_goal, hnuke_goal = map(lambda x: int(x) - 1, input().split())
    grid = input()
    is_rock_continuing = False
    is_space_continuing = False
    if "##" in grid[min(snuke_start, hnuke_goal):max(snuke_goal, hnuke_goal) + 1]:
        is_rock_continuing = True
    if "..." in grid[hnuke_start - 1:hnuke_goal + 2]:
        is_space_continuing = True
    if snuke_goal < hnuke_goal and not is_rock_continuing:
        print("Yes")
    elif hnuke_goal < snuke_goal and not is_rock_continuing and is_space_continuing:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()



Measured memory_bytes: 3572
#include <iostream>

using namespace std;

#define MAX_N 100

int n;
int a[MAX_N];

void sort()
{
    for (int i = 0; i < n; i++) {
        int max = i;
        for (int j = i+1; j < n; j++) {
            if (a[j] > a[max]) max = j;
        }

        int swap = a[i];
        a[i] = a[max];
        a[max] = swap;
    }
}

void solve()
{
    sort();

    int alice, bob;
    alice = bob = 0;
    for (int i = 0; i < n; i += 2) alice += a[i];
    for (int i = 1; i < n; i += 2) bob += a[i];

    cout << alice - bob << endl;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int b;
        scanf("%d", &b);
        a[i] = b;
    }

    solve();

    return 0;
}

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

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30

using namespace std;
typedef pair<int,int> P;

struct edge
{
	int to;
	int cost;
   	int free;

	edge(int t,int c,int f)
	{
		to = t;
		cost = c;
		free = f;
	}

	bool operator>(const edge &e) const
	{
		return cost > e.cost;
	}
};


vector<edge> G[101];
int d[101][2];
bool used[101][2];

void dijkstra(int s,int n)
{
	priority_queue<edge,vector<edge>,greater<edge> > que;
	rep(i,101) rep(j,2) d[i][j] = INF;

	rep(i,101) rep(j,2) used[i][j] = false;

	d[s][1] = 0;
	que.push(edge(0,s,1));

	while(que.size())
	{
	   	edge p = que.top();
		que.pop();


		int v = p.to;

		if(used[v][p.free]) continue;
		used[v][p.free] = true;

		if(d[p.to][p.free] < p.cost) continue;

		rep(i,G[v].size())
		{
			edge e = G[v][i];

			if(p.free - e.free >= 0)
			{
				if(d[e.to][p.free-e.free] > p.cost + e.cost)
				{
					d[e.to][p.free-e.free] = p.cost + e.cost;
					que.push(edge(e.to,p.cost + e.cost,p.free-e.free));
				}
			}
		}
	}
}

int main()
{
	int n,m;
	while(cin >> n >> m)
	{
		if(n == 0 && m == 0) break;

			
		rep(i,100) G[i].clear();

		rep(i,m)
		{
			int a,b,c;
			cin >> a >> b >> c;

			a--;
			b--;

			G[a].push_back(edge(b,c,0));
			G[b].push_back(edge(a,c,0));
		}

		vector<P> v;
		rep(i,n)
		{
			rep(j,G[i].size())
			{
				rep(k,G[G[i][j].to].size()) 
				{
					if(i != G[G[i][j].to][k].to) v.push_back(P(i,G[G[i][j].to][k].to));
				}
			}
		}

		rep(i,v.size()) if(v[i].first > v[i].second) swap(v[i].first,v[i].second);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());

		rep(i,v.size())
		{
			G[v[i].first].push_back(edge(v[i].second,0,1));
			G[v[i].second].push_back(edge(v[i].first,0,1));
		}

		dijkstra(0,n);

		cout << min(d[n-1][1],d[n-1][0]) << endl;
	}
}

Measured memory_bytes: 1308
import numpy as np

def solve(A, B):
  diff = np.array(A) - np.array(B)
  shortage = list(filter(lambda d: d < 0, diff))
  remainder = sorted(list(filter(lambda d: d > 0, diff)), reverse=True)
  short_sum = sum(shortage)
  if short_sum == 0: return 0
  counter = 0
  for r in remainder:
    short_sum += r
    counter += 1
    if short_sum >= 0: return len(shortage) + counter
  return -1

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

print(solve(A, B))

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

const double PI = 3.14159265358979323846;

int main()
{
    int N;
    cin >> N;
    int *x = new int[N];
    int *y = new int[N];
    double **d = new double*[N];
    for(int i=0;i<N;i++){
        cin >> x[i] >> y[i];
        d[i] = new double[N];
        for(int j=0;j<N;j++){
            d[i][j] = 0;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(x[i]==x[j]){
                if(y[i]>y[j]) d[i][j] = 0.25;
                else d[i][j] = 0.75;
            }
            else{
                double theta = atan((double)(y[i]-y[j])/(double)(x[i]-x[j]))/(2.0 * PI); // in [-0.25, 0.25]
                if(x[i]>x[j]){
                    if(y[i]>y[j]) d[i][j] = theta;
                    else d[i][j] = theta + 1.0;
                }
                else d[i][j] = theta + 0.5;
            }
            if(d[i][j]<0.5) d[j][i] = d[i][j] + 0.5;
            else d[j][i] = d[i][j] - 0.5;
        }
    }
    for(int i=0;i<N;i++){
        double probability = 0.0;
        for(int j=0;j<N;j++){
            if(i==j) continue;
            double nearest_clock = 1.0;
            double nearest_counter = 1.0;
            for(int k=0;k<N;k++){
                if(i==k) continue;
                if(j==k) continue;
                double dist_clock = d[i][j] - d[i][k];
                if(dist_clock<0.0) dist_clock += 1.0;
                double dist_counter = 1.0 - dist_clock;
                nearest_clock = min(nearest_clock, dist_clock);
                nearest_counter = min(nearest_counter, dist_counter);
            }
            if(nearest_clock>0.5 || nearest_counter>0.5){
                probability = max(nearest_clock, nearest_counter) - 0.5;
                break;
            }
        }
        cout << probability << endl;
    }
    delete [] x;
    delete [] y;
    for(int i=0;i<N;i++) delete [] d[i];
    return 0;
}


Measured memory_bytes: 384
def sumOfDigit(num):
    sum=0
    while num>0:
        sum += num%10
        num   = num//10
    return sum

N,A,B=map(int,input().split())
ans=0
for i in range(1,N+1):
    if sumOfDigit(i)>=A and sumOfDigit(i)<=B:
        ans += i
print(ans)

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

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long                           //del this if TLE or MLE
#define ll long long
#define ld long double
#define pr pair<int,int>
#define prr pair<pr,int>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fow(i,a,b,c) for(int i=a;i<=b;i+=c)
#define bck(i,a,b,c) for(int i=a;i>=b;i-=c)
#define fi first
#define se second
#define loop int tests;cin>>tests;while(tests--)

signed main()
{
	fastio;
//	freopen("SMTH.inp","r",stdin);
//	freopen("SMTH.out","w",stdout);
	double n,m,d,ans;
	cin>>n>>m>>d;
	if(d==0)
		ans=(m-1)/n;
	else
		ans=2*(n-d)*(m-1)/(n*n);
	cout<<fixed<<setprecision(7)<<ans<<"\n";
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

 
int main() {
  int K=0,S=0,count=0;
  cin >> K >> S;
  for(int x=0;x<=K;x++){
    for(int y=0;y<=K;y++){
      if(S-x-y<=K&&S-x-y>=0){
        count++;
      }
  }
  }
  
  cout << count << endl;
}

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

int main(){
	int n,m;
	cin >> n >> m;
	int num_n = 0, num_m = 0;
	if(n > 1)
		num_n = n *(n-1) /2;
	if(m > 1)
		num_m = m * (m-1) / 2;
	cout << num_n + num_m << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
  int main(){
  int student[30];
   int i;
    for(i=0;i<30;i++){
      student[i] = 0;
       }
        for(i=0;i<28;i++){
        int x;
          scanf("%d",&x);
            student[x-1] = 1;
               }
for(i=0;i<30;i++){
    if(student[i] == 0){
        printf("%d\n",i+1);
         }
}
return 0;
}

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

int main(){
  int D; cin >> D;
  vector<int> c(26);
  for(int i=0; i<26; i++) cin >> c[i];
  vector<vector<int>> s(D,vector<int>(26));
  for(int i=0; i<D; i++){
    for(int j=0; j<26; j++){
      cin >> s[i][j];
    }
  }
  vector<vector<int>> lastc(D+1,vector<int>(26,0));
  vector<int> t(D);
  
    srand(std::time(nullptr));
  
  for(int i=1; i<=D; i++){
    
    int cont; /*cin >> cont;
    cont--;*/ cont=rand()%26;
    t[i-1]=cont;
    
    //lastcの更新
    for(int j=0; j<26; j++){
      if(j==cont) lastc[i][j]=i;
      else lastc[i][j]=lastc[i-1][j];
    }
  }
  
  int M=10;//調整
  for(int i=0; i<M; i++){
    int d,q; /*cin >> d >> q; q--;
    */
    d=rand()%D+1; 
    q=rand()%26;
    int qold=t[d-1];
    
    int sat=0;
    
    sat = sat - s[d-1][qold];
    sat = sat + s[d-1][q];
    
    int lastcold = lastc[d-1][qold];
    for(int j=d; j<=D; j++){
      if(j==d){
        sat-=c[qold]*(j-lastcold);
      }
      else if(lastc[j][qold]==j){
        break;
      }
      else{
        sat-=c[qold]*(lastc[j][qold]-lastcold);
      }
    }
    
    for(int j=d; j<=D; j++){
      if(lastc[j][q]==j){
        break;
      }
      else{
        sat+=c[q]*(d-lastc[j][q]);
      }
    }
    
    if(sat>0){
      for(int j=d; j<=D; j++){
        if(j==d){
          lastc[j][qold]=lastc[j-1][qold];
        }
        else if(lastc[j][qold]==j){
          break;
        }
        else{
          lastc[j][qold]=lastc[j-1][qold];
        }
      }
      
      for(int j=d; j<=D; j++){
        if(j==d){
          lastc[j][q]=d;
        }
        else if(lastc[j][q]==j){
          break;
        }
        else{
          lastc[j][q]=lastc[j-1][q];
        }
      }
      
      t[d-1]=q;
    }
  }
  
  for(int i=0; i<D; i++){
    cout << t[i]+1 << endl;
  }
}

Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

int main(){
    ll N;
    cin >> N;
    vector<ll> P(N),Q(N);
    rep(i,N){
        cin >> P[i];
        Q[P[i]-1] = i;
    }
    ll cnt = -1;
    ll prev = -1;
    ll M = 1;
    rep(i,N){
        //cout << Q[i] << " ";
        if(prev < Q[i]){
            cnt++;
        }else{
            cmax(M,cnt+1);
            cnt = 0;
        }
        prev = Q[i];
    }
    //cout << endl;
    cmax(M,cnt+1);
    cout << N-M << endl;    
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;


const double INF = 1001001001;

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    sort(ALL(a));
    int ai = a.back();
    int kyori = INF;
    int aj = 0;
    rep(i,n){
        double diff = abs(ai - a[i] * 2);
        if(diff < kyori) {
            aj = a[i];
            kyori = diff;
        }
    }
    //cout << half << endl;
    cout << ai << " " << aj << endl;
}

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

typedef long long ll;

int const N = 200 * 1000 + 16;
int const M = 1000 * 1000 * 1000 + 7;
int const inf = 1000 * 1000 * 1000;

typedef pair<int,int> type;

int X;


int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  cin >> X;
  ll l = 1;
  ll r = 1e9;
  ll ans = 0;
  while(l <= r) {
    ll m = l + r >> 1;
    if(X <= m*(m+1)/2)
      r = m - 1, ans = m;
    else
      l = m + 1;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#include<cstring>
using namespace std;
 
int main()
{
	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int k,a,b;
    cin>>k>>a>>b;
    int i=0;
    for(i=a;i<=b;i++)
    {
    	
    	if(i%k==0)
    	{
    		
    		cout<<"OK"<<endl;
    		return 0;
    		
		}
    	
    	
    	
	}
	
	
	if(i>=b)
	{
		
		cout<<"NG"<<endl;
		
	}
	
    
    
    
    
    return 0;
    
}
    

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;
template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T& val) {
    std::fill((T*)array, (T*)(array + N), val);
}
// long long mod = 998244353;
#define REP(i, n) for (long long i = 0; i < (n); i++)
#define rep(i, a, n) for (long long i = a; i < (n); i++)
typedef long long ll;
typedef pair<ll, ll> P;
long long mod = 1000000007;
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t % mod;
    } else {
        return modpow(m, n - 1) * m % mod;
    }
}
long long power(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}

long long moddiv(long long a, long long b) { return (a * modpow(b, mod - 2)) % mod; }

const ll INF = 1LL << 60;

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}

ll nCkmod(ll n, ll k) {
    ll denomi = 1;
    for (int i = n; i > n - k; i--) {
        denomi *= i;
        denomi %= mod;
    }
    ll numera = 1;
    REP(i, k) {
        numera *= (i + 1);
        numera %= mod;
    }
    return moddiv(denomi, numera);
}
vector<vector<ll>> graph;
vector<ll> as;
map<P, ll> number;
ll rmemo[101][300001];
ll memo[101][300001];
int main() {
    ll a, b, d;
    cin >> a >> b >> d;
    ll ans = 0;
    for (int i = a; i <= b; i++) {
        if (i % d == 0) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
//const int MAX=;
const ll MOD=1e9+7;

int extgcd(int a,int b,int& x, int& y){
	int d=a;
	if(b!=0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}
	else{
		x = 1; y = 0;
	}
	return d;
}
int mod_inv(int a,int m){
	int x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

int main(){
	ll N,A,B,C,D;
	cin>>N>>A>>B>>C>>D;
	
	//階乗を持っておく
	ll fa[1002];
	fa[0]=1;
	rep1(i,N)fa[i]=(fa[i-1]*i)%MOD;
	
	//階乗のべきも持っておく(i!のj乗)
	ll fap[1002][1002];
	rep(i,N+1){
		fap[i][0]=1;
		rep1(j,N){
			fap[i][j]=(fap[i][j-1]*fa[i])%MOD;
		}
	}
	
	ll dp[1002][1002];
  	dp[A-1][0]=1;
	rep1(j,N)dp[A-1][j]=0;
	for(int i=A;i<=B;i++)rep(j,N+1){
		dp[i][j]=dp[i-1][j];
		rep1(k,j/i){
			if(!(C<=k && k<=D))continue;
			ll c=dp[i-1][j-i*k];
			c=(c*fa[N-j+i*k])%MOD;
			c=(c*mod_inv(fa[N-j],MOD))%MOD;
			c=(c*mod_inv(fa[k],MOD))%MOD;
			c=(c*mod_inv(fap[i][k],MOD))%MOD;
			dp[i][j]=(dp[i][j]+c)%MOD;
		}
	}
	cout<<dp[B][N];
}


Measured memory_bytes: 15872
# include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;
 
# define S second
# define F first
# define kill(x) return(cout << x << endl, 0)
# define debug(x) cerr<< #x << " : " << x << endl
# define ddebug(x, y) cerr<< #x << " : " << x  << ", " << #y << " : " << y << endl
# define sz(s) (int)s.size()
# define sq(x) (x) * (x)
# define PB(x) push_back(x)
# define smax(x, y) (x) = max((x), (y))
# define smin(x, y) (x) = min((x), (y))
# define all(x) x.begin(), x.end()
# define SP fixed << setprecision(10)
# define UB upper_bound 

const int MAXN = 100 * 1000 + 10;
int a[MAXN];
map <int, int> ind;

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i ++)
	{
		cin >> a[i];
		ind[a[i]] = i;
	}
	sort(a, a + n);
	int ans = 0;
	for (int i = 0; i < n; i += 2)
		if (ind[a[i]] & 1)
			ans ++;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 7296
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));

int N;
vector<int>arr;
vector<int>A;

void Eratosthenes() {
	for (int i = 0; i <= 1000000; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i * i < N; i++) {
		if (arr[A[i]]) {
			for (int j = 0; A[i] * (j + 2) < N; j++) {
				arr[A[i] * (j + 2)] = 0;
			}
		}
	}

	for (int i = 2; i < N; i++) {
		if (arr[i]) {
			//cout << i << endl;
		}
	}
}

signed main() {
	cin >> N;
	arr.resize(N + 1);
	A.resize(N);
	rep(i, N)cin >> A[i];
	int setwise = A[0];
	rep(i, N) {
		setwise = gcd(setwise, A[i]);
	}
	if (setwise != 1) {
		cout << "not coprime";
		return 0;
	}
	map<int, int>m;
	rep(i, N) {
		int a = 2;
		int n = A[i];
		int cnt = 0;
		while (n >= a * a) {
			if (n % a == 0) {
				if (m[a] != 0) {
					if (m[a] != cnt) {
						cout << "setwise coprime";
						return 0;
					}
				}
				m[a]++;
				n /= a;
				cnt++;
			}
			else {
				a++;
				cnt = 0;
			}
		}
		if (n == 1)continue;
		if (m[n] != 0 && m[n] != cnt) {
			cout << "setwise coprime";
			return 0;
		}
		m[n]++;
	}
	cout << "pairwise coprime";
}


Measured memory_bytes: 18776
#include<bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define endl "\n"
#define loop(i,s,e) for(int i=s;i<e;i++)
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define mset(a,f)  memset(a , f , sizeof(a))
#define pb push_back
const int N = 2e5 + 6;
const int M = 1e9 + 7;
int A[N];
int mat[22][22];
int dp[22][(1<<22)];
int n;

// bool J27 = 1;
#define bug(...)                                  __f (#__VA_ARGS__, __VA_ARGS__)
#define rtn                                       if(0)return;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { rtn cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{     rtn 
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

int alpha(int i , int mask)
{
	if(i == n && mask == 0)return 1;
	if(i == n)return 0;
	
	int &solotov = dp[i][mask];

	if(solotov != -1)return solotov;

	int ans = 0;

	loop(j,0,n)
	{
		if(mat[i][j] == 1 && (mask&(1<<j)))
		{
			int k1 = (mask^(1<<j));
			ans += alpha(i+1,k1);
		}
	}
	return solotov = ans%M;
}

void solve()
{
	cin >> n;

	loop(i,0,n)loop(j,0,n)cin >> mat[i][j];

	int k = (1<<n)-1;

	mset(dp,-1);

	cout << alpha(0,k);
}
 
int32_t main()
{
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
 	
 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}


Measured memory_bytes: 721280
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
int lcm(int a, int b){
  return a / gcd(a,b) * b;
}
const int INF = 1<<30;
const int MOD = 1000000007;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int main(){
  int n,m; cin >> n >> m;
  vector<int> dp(1<<n,INF);
  vector<int> a(m),key(m);
  dp[0] = 0;
  
  rep(i,m){
    int b;
    cin >> a[i] >> b;
    int tmp = 0;
    rep(j,b){
      int c; cin >> c;
      c--;
      int tmp2 = 1 << c;
      tmp |= tmp2;
    }
    key[i] = tmp;
  }

  rep(i,m){
    rep(j,1<<n){
      if(dp[j] != INF){
        chmin(dp[j|key[i]],dp[j]+a[i]);
      }
    }
  }
  
  int ans = dp[(1<<n)-1];
  if(ans == INF) cout << -1 << endl;
  else cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 29;
 
int main() {
	int n, m;
	vector<int> like(30, 0);
	cin >> n >> m;
	rep(i, n) {
		int k; cin >> k;
		rep(j, k) {
			int a; cin >> a;
			a--;
			like[a]++;
		}
	}
	int cnt = 0;
	rep(i, m) {
		if (like[i] == n) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

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

int main()
{
    int a, b, c;
    int tmp = 0;
    
    cin >> a >> b >> c;
    for (int i = 0; i < 2; i++)
    {
        if (a > b)
        {
            tmp = a;
            a = b;
            b = tmp;
        }
        if (b > c)
        {
            tmp = b;
            b = c;
            c = tmp;
        }
    }
    cout << a << " " << b << " " << c << endl;
}


Measured memory_bytes: 3116
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define MOD 998244353
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}


//nCr,nPr,modの逆元
class Combination {
public:
	Array fact;//n！
	Array inv;//n!の逆元
	ll mod;
	Combination(ll n, ll _mod) {
		mod = _mod;
		fact.resize(n + 1);
		fact[0] = 1;
		REP(i, n) {
			fact[i + 1] = (fact[i] * (i + 1LL)) % mod;
		}
		inv.resize(n + 1);
		inv[n] = mod_inv(fact[n]);
		for (int i = n; i > 0; i--) {
			inv[i - 1] = inv[i] * i % mod;
		}
	}
	//modの逆元
	ll mod_inv(ll x) {
		ll n = mod - 2;
		ll res = 1LL;
		while (n > 0) {
			if (n & 1) res = res * x % mod;
			x = x * x % mod;
			n >>= 1;
		}
		return res;
	}
	ll nCr(ll n, ll r) {
		return ((fact[n] * inv[r] % mod) * inv[n - r]) % mod;
	}
	ll nPr(ll n, ll r) {
		return (fact[n] * inv[n - r]) % mod;
	}
	ll nHr(ll n, ll r) {
		//重複組み合わせ：n種類のものからr個取り出す組み合わせ
		return nCr(r + n - 1, r);
	}
};


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

	ll n,a,b,k;
	cin >> n >> a >> b >> k;

	Combination com(n, MOD);

	ll ans = 0;
	for (int i = 0; i <= n && a * i <= k;i++) {
		ll j = (k - (a * i)) / b;
		if ((k - a * i) % b == 0&&j<=n) {
			//cout << i << " " << j << endl;
			ans += (com.nCr(n, i) * com.nCr(n, j))%MOD;
			ans %= MOD;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
//#define DEBUG//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
	x=0; int ch=getchar(),f=0;
	while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	if(f)x=-x;
	read(oth...);
}
int a[maxn],tar;
ll dist[maxn]={-1};
map<ll,int>mp;
bool vis[maxn];
vector<int>rec,cir;
void dfs(int x,int fa)
{
//	printf("%d\n",x);
	if(!vis[x])
		cir.push_back(x);
	if(vis[x])
	{
		tar=x;
		bool flag=0;
		for(int i=0;i<cir.size();i++)
		{
			if(cir[i]==x)
				flag=1;
			if(flag)
			{
				rec.push_back(cir[i]);
//				printf("%d,",cir[i]);
			}
		}
//		printf("\n");//
//		rec.erase(rec.find(rec.begin(),rec.end(),x),rec.end());
		return;
	}
	vis[x]=1;
	dist[x]=dist[fa]+1;
	mp[dist[x]]=x;
	dfs(a[x],x);
}
signed main()
{
	std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	#ifdef DEBUG
		freopen("input.in", "r", stdin);
	//	freopen("output.out", "w", stdout);
	#endif
	ll n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dfs(1,0);
	if(k<=dist[tar])
		cout<<mp[k]<<endl;
	else{
		k-=dist[tar];
		ll len=rec.size();
		cout<<rec[k%len]<<endl;
	}
	return 0;
}




Measured memory_bytes: 37360
#include<bits/stdc++.h>
#define int long long
#define rep(i,m,n) for(int i=m;i<n;i++)
#define repr(i,n,m) for(int i=n;i>=m ;i--)
#define mod 1000000007
#define float long double
#define pb push_back
#define mp make_pair
using namespace std;

bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
}
bool sortinrev(const pair<int,int> &a,  
               const pair<int,int> &b) 
{ 
       return (a.first > b.first); 
} 
void isPalindrome(string s) 
{ 
    // Start from leftmost and rightmost corners of str 
   int x=s.length();
   rep(i,0,x)
   {
   	if(s[i]!=s[x-1-i])
   	{
   		cout<<"No";
   		return;
   	}
   }
   rep(i,0,(x-1)/2)
   {
   	if(s[i]!=s[(x-1)/2-i-1])
   	{
   		cout<<"No";
   		return;
   	}
   }
  for(int i=x/2+1,j=x-1;i<x,j>=x/2+1;i++,j--)
  {
  	if(s[i]!=s[j])
  	{
  		cout<<"No";
  		return;
  	}
  }
  	cout<<"Yes";
}
void solve()
{
	string s;
	cin>>s;
	isPalindrome(s);
}
signed main()
{
   int t=1; 	
   //cin>>t;
   while(t--)
   {
      solve();
   }
   cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
  return 0;
 }


Measured memory_bytes: 256