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

ll n,k;
const int MAXN = 2000*2000+1;
long long kai[MAXN];
long long inv[MAXN];
long long mod = 1e9+7;
long long mp(long long a, long long b) {
    long long res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}
void init() {
    kai[0] = 1;
    for (long long i = 1; i <= n*k; i++) kai[i] = kai[i - 1] * i % mod;
    for (long long i = 0; i <= n*k; i++) inv[i] = mp(kai[i], mod-2);
}
long long calc(long long n, long long k) {
    if (n < k) return 0;
    return (kai[n] * inv[k]) % mod * inv[n - k] % mod;
}

ll dp[2010][2010];
bool ok[2010][2010];

ll dfs(int a, int b) {
    if (ok[a][b]) return dp[a][b];
    ll ret = 0;
    if (a - 1 >= 0) ret += dfs(a-1,b);
    if (b - 1 >= a) ret += dfs(a, b-1) * calc(a + b * (k - 1) - 1, k - 2) % mod;
    ok[a][b] = 1;
    return dp[a][b] = ret % mod;
}

int main() {
    cin >> n >> k;
    init();
    if (k == 1) {
        cout << 1 << endl;
        return 0;
    }
    dp[0][0] = 1;
    ok[0][0] = 1;
    ll ret = dfs(n,n);
    for (ll i = 1; i <= n; i++) ret = ret * i % mod;
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 92788
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 10000000007; //10^9+7

int main(){
  int n; 
  cin>>n;
  ll ans=1;
  REP(i,10000005){
    if(i*i>n)break;
    ans=i*i;
  }
  print(ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int const MAXN = 100;
bool k[MAXN];

int main() {
  int N, K; std::cin >> N >> K;
  std::fill_n(k, N, true);
  for(int i = 0; i < K; ++i) {
    int d; std::cin >> d;
    for(int j = 0; j < d; ++j) {
      int A; std::cin >> A; --A;
      k[A] = false;
    }
  }
  int ans = 0;
  for(int i = 0; i < N; ++i) if(k[i]) ++ans;
  fin(ans);
  return 0;
}


Measured memory_bytes: 3588
/* Coached by Dukkha */
#include <stdio.h>

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int main() {
	int n, ans;

	scanf("%d", &n);
	ans = 0;
	while (n--) {
		int a;

		scanf("%d", &a);
		ans = gcd(ans, a);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    if(a>=10){ System.out.println( b );}
    else { System.out.println( (b+1000-100*a));};
  }
}

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

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

typedef long long int lli;

int main()
{
	fio;
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++) ans=max(ans,abs(a[i]-a[j]));
	}
	cout<<ans<<endl;
	cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n";
	return 0;
}

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


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

    int ans = 0;
    if (N%2==0) N--;

    cout << (N/2) << endl;
    return 0;
}


Measured memory_bytes: 256
/*
 * ARC084C.cpp
 *
 *  Created on: Jun 1, 2018
 *      Author: 13743
 */
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}

int a[100000];
int b[100000];
int c[100000];

lng bb[100001];

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

	int N;
	cin >> N;
	REP(i, N) cin >> a[i];
	REP(i, N) cin >> b[i];
	REP(i, N) cin >> c[i];

	sort(b, b+N);
	sort(c, c+N);
	REP(i, N) {
		bb[i] = N - (upper_bound(c, c+N, b[i]) - c);
	}
	bb[N] = 0;
	FORD(i, N-1, 0) {
		bb[i] += bb[i+1];
	}

	lng ans = 0;
	REP(i, N) {
		ans += bb[upper_bound(b, b+N, a[i]) - b];
	}

	cout << ans << endl;
}






Measured memory_bytes: 2176
fun main(args: Array<String>) {
    val s = readLine()!!.split(" ").map { it.toLong() }
    val anb = s[1] + s[2]
    val amari = s[0] % anb
    val syou = s[0] / anb
    var blue = syou * s[1]
    var x:Long = 0
    if (amari > s[1]){
        x = s[1]
    } else {
        x = amari
    }
    blue = blue + x
    println(blue)
}



Measured memory_bytes: 37936
#include<stdio.h>
int main()

{
    int n,x,i,j,k;


    while(1)
    {
        int count=0 ;
        scanf("%d %d",&n,&x);

        if(x==0 && n==0)
            break;
        else
        {
            for(i=1; i<=n; i++)
            {
                for(j=i+1; j<=n; j++)
                {
                    for(k=j+1; k<=n; k++)
                    {
                        if(i+j+k==x)
                            count++;
                    }

                }
            }
            printf("%d\n",count);
        }
    }
    return 0;
}


Measured memory_bytes: 2100
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define P 1000000007
using namespace std;
int add(int a,int b){a+=b;return (a>=P)?a-P:a;}
int mul(int a,int b){return 1ll*a*b%P;}
int N,M;
int X[100005];
struct Mat{
	int mat[3][3];
	void clear(){memset(mat,0,sizeof(mat));}
	friend Mat operator *(Mat a,Mat b){
		Mat c;
		c.clear();
		for(int i=0;i<3;++i){
			for(int j=0;j<3;++j){
				for(int k=0;k<3;++k)c.mat[i][j]=add(c.mat[i][j],mul(a.mat[i][k],b.mat[k][j]));
			}
		}
		return c;
	}
}ret,a,b;
void init(){
	ret.mat[0][0]=1,ret.mat[0][1]=2,ret.mat[0][2]=1;
	a.mat[0][0]=1,a.mat[0][1]=2,a.mat[0][2]=1;
	a.mat[1][0]=0,a.mat[1][1]=1,a.mat[1][2]=1;
	a.mat[2][0]=1,a.mat[2][1]=2,a.mat[2][2]=2;
	b.mat[0][0]=1,b.mat[0][1]=2,b.mat[0][2]=1;
	b.mat[1][0]=0,b.mat[1][1]=1,b.mat[1][2]=1;
	b.mat[2][0]=0,b.mat[2][1]=0,b.mat[2][2]=1;
}
void solve(int ty,int times){
	Mat o,x;
	o.clear();
	if(ty==1)x=a;
	else x=b;
	for(int i=0;i<3;++i)o.mat[i][i]=1;
	while(times){
		if(times&1)o=o*x;
		x=x*x,times>>=1;
	}
	ret=ret*o;
}
int main(){
	init();
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;++i)scanf("%d",&X[i]);
	X[++M]=N;
	int now=1;
	for(int i=1;i<=M;++i){
		solve(1,X[i]-now);
		if(i==M)break;
		solve(2,1);
		now=X[i]+1;
	}
	printf("%d",ret.mat[0][2]);
	return 0;
}

Measured memory_bytes: 640
// ABC123_C
#include <iostream>
#include <string>
#include <vector>
#include <iterator>  // std::prev(iter, n) n 個分デクリメントしたイテレータ
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <functional>  // std::greater<T>()
#include <utility>  // std::swap()
#include <numeric>  // accumulate(ALL(vec), 0)  0 は初期値
#include <bitset>  // static_cast<std::bitset<8>>
#include <sstream>  // std::stringstream
#include <cmath>
#include <climits>  // INT_MIN
#include <cctype>  // std::isdigit()
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define MIN(vec) min_element(vec.begin(), vec.end())  // イテレータのため、値を取り出すときは * を先頭につける
#define MAX(vec) max_element(vec.begin(), vec.end())
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define SUM(vec) accumulate(vec.begin(), vec.end(), 0LL)  // 0 は初期値
#define pll pair<ll, ll>
#define F first
#define S second
const ll INF = 1LL<<60;  // 10^18（const int inf   = 1<<29;）

int main() {
    // input(sunippets: inpv, inpn, inps)
    ll N, A, B, C, D, E;
    cin >> N >> A >> B >> C >> D >> E;
    ll m = min({A, B, C, D, E});
    ll group = (N+m-1)/m;
    
    // calculation
    cout << 5 + (group-1) << "\n";
    
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD (1000000007)
#define INF (2e9)
#define INFL (2e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using vint=vector<int>;
using vll=vector<ll>;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    int n, h; cin >> n >> h;
    priority_queue<int> a, b;
    rep(i, n){
        int x, y; cin >> x >> y;
        a.push(x);
        b.push(y);
    }

    int ans = 0;
    while(h > 0 && !b.empty() && b.top() > a.top()){
        int c = b.top(); b.pop();
        h -= c;
        ans++;
    }

    if(h > 0){
        int c = a.top();
        ans += h / c;
        if(h%c>0) ans++;
    }

    pr(ans);
    return 0;}

Measured memory_bytes: 4308
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int main() {
    int n; cin >> n;
    int a[n];
    int ans;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i == 0) ans = a[0];
        else ans = gcd(ans, a[i]);
    }
    cout << ans << endl;
}




Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int main(){
	int n;
	while(cin>>n,n){
		int sum=0,a[5001];
		vector<int>anss(0);
		for(int i=0;i<n;i++)cin>>a[i];
		for(int i=0;i<n;i++){
			sum=0;
			for(int j=i;j<n;j++){
				sum+=a[j];
				anss.push_back(sum);
			}
		}
		sort(anss.begin(),anss.end(),greater<int>());
		cout<<anss[0]<<endl;
	}
	return 0;
}

Measured memory_bytes: 35852
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint f(int n){
  if(n < 1) return 1;
  mint x = f(n / 2);
  x *= x;
  if(n % 2) x *= 2;
  return x;
}
mint choose(int n, int r){
  mint x = 1, y = 1;
  rep(i, r){
    y *= i + 1;
    x *= n - i;
  }
  return x / y;
}

int main(){
  int n, a, b;
  cin >> n >> a >> b;
  mint ans = f(n) - choose(n, a) - choose(n, b) - 1;
  cout << ans. x << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;

array<long long, 100000> ai;
int main(){
    long long n;
    cin >> n;
    for(long long i=0;i<n;i++){
        cin >> ai[i];
    }
    sort(ai.begin(),(ai.begin()+n));
    long long dup0=0;
    long long tmp;
    long long evencnt=0;
    int flag=0;
    long long res=n;
    for(long long i=0;i<n;i++){
        if(flag==0){
            tmp=ai[i];
            dup0=1;
            flag=1;
        }
        else if(flag==1 && ai[i]==tmp){
            dup0++;
        }
        else if(flag==1 && ai[i]!=tmp){
            if(dup0%2==1){
                res = res-(dup0-1);
            }
            else{
                res = res-(dup0-1);
                evencnt++;
            }
            flag=1;
            tmp=ai[i];
            dup0=1;
          //  cout << res <<endl;
        }
    }
    if(dup0%2==1){
        res = res-(dup0-1);
    }
    else{
        res = res-(dup0-1);
        evencnt++;
    }
    if(evencnt%2==0){
        cout << res;
        return 0;
    }
    else{
        cout << res-1;
        return 0;
    }

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200200;
int u[maxn], sz[maxn];
void init(){
	iota(u, u + maxn, 0);
	for(int i = 0; i < maxn; i++) sz[i] = 1;
}
int find(int x){
	if(x == u[x]) return x;
	return u[x] = find(u[x]);
}
void join(int x, int y){
	x = find(x);
	y = find(y);
	if(x ^ y){
		u[x] = y;
		sz[y] += sz[x];
		sz[x] = 0;
	}
}
vector<int> e[maxn];
int seen[maxn], cmp[maxn];
int main(){
	int n, k, l; cin >> n >> k >> l;
	init();
	for(int i = 0; i < k; i++){
		int x, y; cin >> x >> y;
		join(x, y);
	}
	for(int i = 1; i <= n; i++) cmp[i] = find(i);
	init();
	for(int i = 0; i < l; i++){
		int x, y; cin >> x >> y;
		join(x, y);
	}
	map<pair<int,int>, int> ans;
	for(int i = 1; i <= n; i++) ans[{cmp[i], find(i)}]++;
	for(int i = 1; i <= n; i++) cout << ans[{cmp[i], find(i)}] << " "; cout << endl;
	return 0;
}






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

using namespace std;
using ll = long long;
using edge = struct
{
    int to;
    ll cost;
};

#define mod 1000000007
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(a) (a).begin(), (a).end()
#define INF (1 << 29)

//long C(long n, long r);
long long gcd(long long a, long long b);
long long lcm(long long a, long long b);

int how2div(ll a)
{
    int ans = 0;
    while (a % 2ll == 0)
    {
        ans++;
        a /= 2ll;
    }
    return ans;
}

void solve()
{
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n);
    REP(i, n)
    {
        cin >> a[i];
    }
    int tow0 = how2div(a[0]);
    REP(i, n)
    {
        if (tow0 != how2div(a[i]))
        {
            cout << 0 << "\n";
            return;
        }
    }
    ll T = 1ll;
    REP(i, n)
    {
        T = lcm(T, a[i] / 2ll);
    }
    //cout << T << "\n";
    ll ans = (ll)((m / T + 1) / 2ll);
    cout << ans << "\n";
}

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

long C(long n, long r)
{
    if (n < r)
        return 0;
    long p[n + 1][n + 1];
    p[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p[i][0] = 1;
        p[i][i] = 1;
        for (int j = 1; j <= i - 1; j++)
        {
            p[i][j] = p[i - 1][j] + p[i - 1][j - 1];
        }
    }
    return p[n][r];
}

long long gcd(long long a, long long b)
{
    if (a < b) swap(a, b);
    while(true) {
        if(a % b == 0ll) break;
        ll _a = a;
        a = b;
        b = _a % b;
    }
    return b;
}

long long lcm(long long a, long long b)
{
    return (max(a, b) / gcd(a, b)) * min(a, b);
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll gcd(ll a, ll b);
int main(){
cin.tie(0);
ll d,t,s;
 cin>>d>>t>>s;
 if(d>t*s)cout<<"No";
 else cout<<"Yes";

return 0;
}






ll gcd(ll a, ll b){

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

}

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

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; }
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
using Graph = vector<vector<int>>;
queue<int> quex,quey;
const int MOD = 1000000007;




int main(){
    int a,b;
    string s,t;

    char u[3];
    for(int i=0;i<3;i++){
        cin >> u[i];
    }
    if(u[0]==u[1] && u[1]==u[2]) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

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

struct Edge {
  int t, w;
  Edge() {}
  Edge(int t, int w): t(t), w(w) {}
};

using ve = vector<Edge>;
using vve = vector<ve>;
int n;
vve tree;

void bfs(vi &d, int s) {
  queue<int> q;
  q.push(s);
  
  vector<bool> visited(n);
  while (!q.empty()) {
    int c = q.front(); q.pop();
    visited[c] = true;

    for (auto nt: tree[c]) {
      int t = nt.t, w = nt.w;
      
      if (visited[t]) continue;

      d[t] = w + d[c];

      q.push(t);
    }
  }
}

int solve() {
  vi d1(n);
  bfs(d1, 0);

  int max_e = 0;
  rep(i, n)
    if (d1[max_e] < d1[i]) max_e = i;
  
  vi d2(n);
  bfs(d2, max_e);
  rep(i, n)
    if (d2[max_e] < d2[i]) max_e = i;
  
  return d2[max_e];
}

int main() {
  cin >> n;
  
  int s, t, w;
  tree.resize(n);
  rep(i, n - 1) {
    cin >> s >> t >> w;
    tree[s].push_back(Edge(t, w));
    tree[t].push_back(Edge(s, w));
  }
  
  int max_d = solve();
  cout << max_d << endl;
}



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

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

int main()
{
    using vi = vector<int>;
    using vvi = vector<vi>;
    using vvvi = vector<vvi>;

    int N;
    cin >> N;
    vi B(N - 1);
    rep(i, N - 1) cin >> B[i];

    int sum = B[0];
    for(int i = 1; i < N - 1; i++)
        sum += min(B[i - 1], B[i]);
    sum += B[N - 2];
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define INF 1000000000000
#define MOD 10000007
typedef long long ll;
//
int main(){
   int h,w,k;cin>>h>>w>>k;
   vector<vector<char>> v(h,vector<char>(w,0));
   ll ans=0;
   rep(i,h){
      rep(j,w){
         char s;
         cin>>s;
         v[i][j]=s;
      }
   }
   rep(bits1,(1<<h)){
      rep(bits2,(1<<w)){
         int black=0;
         rep(i,h){
            rep(j,w){
               if((bits1 &1<<i)==0&&(bits2 &1<<j)==0&&v[i][j]=='#' )black++;
            }
         }
         if(black == k)ans++;
      }
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 3580
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) ((V).begin(),(V).end())
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LaL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
using namespace std;

int main(){
  string S,T;
  cin>>S>>T;
  
  bool CAN=true;
  
  REP(i,S.size()){
    if(S.at(i)!=T.at(i)) CAN=false;
  }
  
  if(CAN) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 3600
using System;
class Program
{
static void Main(string[] args)
{

string[] input = Console.ReadLine().Split(' ');

int a = int.Parse(input[0]);
int b = int.Parse(input[1]);
int c = int.Parse(input[2]);

if( a == b+c || b == c+a || c == a+b ) Console.WriteLine("Yes");
else Console.WriteLine("No");
}
}

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

#define int long long
using namespace std;
const int MAXN = 2e5 + 10;
int vis[MAXN];

signed main(){
//    freopen("in", "r", stdin);
    ios::sync_with_stdio(false);
    int n, m, t; cin >> n;
    for (int i = 0; i < n - 1; i++){
        cin >> t;
        vis[t]++;
    }
    for (int i = 1;i <= n; i++)
        cout << vis[i] << endl;
    return 0;
}

Measured memory_bytes: 5104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		boolean[] sieve = new boolean[101];
		
		sieve[0] = true;
		sieve[1] = true;
		for(int i = 2; i < 101; i++)
		{
			if(!sieve[i])
				for(int j = i*i; j < 101; j+= i)
				{
					sieve[j] = true;
				}
		}
		int ps = 0;
		int[][] inv = new int[n+1][26];
		int[] iden = new int[26];
		
		int[] tot = new int[26];
		
		//dont forget 1 as a divisor!!
		for(int i = 0; i <= n; i++)
		{
			if(!sieve[i])
			{
				int powres = i;
				while(powres <= n)
				{
					for(int j = powres; j <= n; j+=powres)
					{
						inv[j][ps]++;
						tot[ps]++;
					}
					powres *= i;
				}
				iden[ps] = i;
				ps++;
			}
		}
		
		for(int i = 0; i <= n; i++)
		{
			for(int p = 0; p < 26; p++)
			{
//				if(inv[i][p] > 0)
//					System.out.println(i + "'s " + iden[p] + ": " + inv[i][p]);
			}
		}
		for(int p = 0; p < 26; p++)
		{
//			System.out.println("Total " + iden[p] + ": " + tot[p]);
		}
		
		int score = 0;
		for(int i = 0; i < 26; i++)
		{
			//only 1 case
			if(tot[i] >= 74) {score++;}
			if(tot[i] == 0)continue;
			for(int j = i+1; j < 26; j++)
			{
				if(tot[j] == 0)continue;
				//25 * 3, 3 * 25, 15 * 5, 5 * 15
				if((tot[i]+1) >= 25 && tot[j]+1 >= 3)score++;
				if((tot[i]+1) >= 3 && tot[j]+1 >= 25)score++;
				if((tot[i]+1) >= 5 && tot[j]+1 >= 15)score++;
				if((tot[i]+1) >= 15 && tot[j]+1 >= 5)score++;
				
				for(int k = j+1; k < 26; k++)
				{
					if(tot[k] == 0)continue;
					if((tot[i]+1) >= 3 && tot[j]+1 >= 5 && tot[k]+1 >= 5)score++;
					if((tot[i]+1) >= 5 && tot[j]+1 >= 3 && tot[k]+1 >= 5)score++;
					if((tot[i]+1) >= 5 && tot[j]+1 >= 5 && tot[k]+1 >= 3)score++;
				}
			}
		}
//		System.out.println("Score: ");
		System.out.println(score);

	}

}


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

#define int long long

#define rep(i, n) for (int i = 0; i < (n); i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second

using vint = vector<int>;
using pint = pair<int, int>;
using vpint = vector<pint>;

template <typename A, typename B>
inline void chmin(A& a, B b) {
    if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
    if (a < b) a = b;
}

template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
    ost << "{" << p.first << "," << p.second << "}";
    return ost;
}

template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
    ost << "{";
    for (int i = 0; i < v.size(); i++) {
        if (i) ost << ",";
        ost << v[i];
    }
    ost << "}";
    return ost;
}

inline int topbit(unsigned long long x) {
    return x ? 63 - __builtin_clzll(x) : -1;
}

inline int popcount(unsigned long long x) {
    return __builtin_popcountll(x);
}

inline int parity(unsigned long long x) {
    return __builtin_parity(x);
}

template <uint32_t mod>
struct ModInt {
    uint32_t a;
    ModInt& s(uint32_t vv) {
        a = vv < mod ? vv : vv - mod;
        return *this;
    }

    ModInt(int64_t x = 0) { s(x % mod + mod); }

    ModInt& operator+=(const ModInt& x) { return s(a + x.a); }
    ModInt& operator-=(const ModInt& x) { return s(a + mod - x.a); }
    ModInt& operator*=(const ModInt& x) {
        a = uint64_t(a) * x.a % mod;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) {
        *this *= x.inv();
        return *this;
    }

    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    bool operator==(const ModInt& x) const { return a == x.a; }
    bool operator!=(const ModInt& x) const { return a != x.a; }
    bool operator<(const ModInt& x) const { return a < x.a; }

    ModInt operator-() const { return ModInt() - *this; }
    ModInt pow(int64_t n) const {
        ModInt res(1), x(*this);
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }

    ModInt inv() const { return pow(mod - 2); }
};

template <uint32_t mod>
istream& operator>>(istream& in, ModInt<mod>& a) {
    return (in >> a.a);
}
template <uint32_t mod>
ostream& operator<<(ostream& out, const ModInt<mod>& a) {
    return (out << a.a);
}
using mint = ModInt<1000000007>;

signed main() {
    int N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    mint ans = 0;
    rep(i, N) ans += A[i];
    ans *= ans;
    rep(i, N) ans -= A[i] * A[i];
    ans /= 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4828
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1e9+7;
//const ll MOD=998244353;

int cnt[3];
int num2[1010101];

void prepare(){
  for(int i=1;i<=1010100;i++){
    int tmp=0,x=i;
    while(x%2==0) x/=2,tmp++;
    num2[i]=num2[i-1]+tmp;
  }
}

int main(){
  prepare();
  
  int N; cin>>N;
  string S; cin>>S;
  int A[N];
  rep(i,N){
    A[i]=(S[i]-'0');
    A[i]--;
    cnt[A[i]]++;
  }
  
  if(cnt[1]){
    int ans=0;
    rep(i,N){
      if(A[i]%2){
        int x=num2[N-1]-num2[N-1-i]-num2[i];
        if(x==0) ans++;
      }
    }
    if(ans%2) cout<<"1\n";
    else cout<<"0\n";
  }else{
    int ans=0;
    rep(i,N){
      if(A[i]==2){
        int x=num2[N-1]-num2[N-1-i]-num2[i];
        if(x==0) ans++;
      }
    }
    if(ans%2) cout<<"2\n";
    else cout<<"0\n";
  }
  return 0;
}

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

typedef long long ll;

ll mod = 1e9 + 7;

int main() {
	int n; cin >> n;
	ll ans = 1;
	for (int i = 1; i <= n; i++) {
		ans = ans * i % mod;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3544
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please


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

	int A, B, C;
	cin >> A >> B >> C;

	if (A <= C && C <= B) co("Yes");
	else co("No");

	Would you please return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void solve(){
    ll a;cin>>a;
    ll arr[a][2];
    for(int i=0;i<a;i++){
        cin>>arr[i][0]>>arr[i][1];
    }
    for(int i=0;i<a-2;i++){
        if(arr[i][0]==arr[i][1] && arr[i+1][0]==arr[i+1][1] && arr[i+2][0]==arr[i+2][1]) {
            cout<<"Yes";
            return;
        }
    }
    cout<<"No";
}
int main(){
    ll t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
}

Measured memory_bytes: 3628
/*input

*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

#pragma GCC optimize("O3")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")

#define F first
#define S second
#define mp make_pair
#define append push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long int
#define pb push_back
#define print(a) cout<<a<<endl
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define all(x) x.begin(), x.end()
#define loop(i,n) for(int i = 0; i < n; i++)
#define int long long int
 
const int MOD = 1e9 + 7;

int fastexpo(int x, int y) 
{ 
    int res = 1;
    x = x % MOD;
    while (y) 
    { 
        if (y & 1) res = (res*x) % MOD; 
        y = y>>1;
        x = (x*x) % MOD;   
    } 
    return res; 
}

int mod(int x, int y){
    return (x%y + y)%y;
}

void solve();

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

    int t = 1;
    //cin>> t;
    while(t--){
        solve();
    }

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

const int MAXN = 1e5 + 10;

vector<pair<int, int> > graph[MAXN];
int color[MAXN];

void dfs(int node, int par, int dist){
    color[node] = dist&1;
    for(auto u :  graph[node]){
        if(u.F == par)
            continue;
        dfs(u.F, node, (dist + u.S)&1);
    }
}

void solve(){
    int n;
    cin>> n;
    for(int i = 0; i < n - 1; i++){
        int u, v, w;
        cin>> u >> v >> w;
        graph[u].append(mp(v, w&1));
        graph[v].append(mp(u, w&1));
    }
    dfs(1, 0, 0);
    for(int i = 1; i <= n; i++)
        print(color[i]);
}

Measured memory_bytes: 9728
#include <iostream>

using namespace std;

int main()
{
	long long n, m;
	long res;

	cin >> n;

	m = n;
	res = 0;
	while (m)
	{
		res += m % 10;
		m /= 10;
	}

	if (n % res == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int len = s.length();
  cout << s[0] << len - 2 << s[len - 1] << endl;
  return 0;
}

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

using namespace std;

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

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

	cout << max(a + b, max(a - b, a * b)) << endl;

}

Measured memory_bytes: 384
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList

  val N = inputs(0).toInt
  val K = inputs(1).toInt
  val X = inputs(2).toInt
  val Y = inputs(3).toInt

  println(solve(N, K, X, Y))

  def solve(n: Int, k: Int, x: Int, y: Int): Int = {
    val a = (n - k)
    if (a <= 0) {
      n * x
    } else {
      (k * x) + (n - k) * y
    }
  }
}

Measured memory_bytes: 27300
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

int n;

int main()
{
	usecppio
	cin >> n;
	vector <int> arr(2*n, 0), box(2*n, 0);
	for (int i = 1; i<=n; i++)
		cin >> arr[i];
	int half = n/2+1;
	for(int i=half; i<=n; i++)
		box[i] = arr[i];
	for (int k = half-1; k>=1; k--)
	{
		int cur = 0;
		for (int check = 2*k; check <= n; check+=k)
		{
			cur += box[check];
		}
		box[k] = ((cur%2)!=arr[k]); 
	}
	int m = 0;
	for (int i = 1; i<=n; i++)
	{
		m += box[i];
	}
	cout << m << '\n';
	for (int i = 1; i<=n; i++)
	{
		if (box[i])
			cout << i << ' ';
	}
}

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

#define MOD 1000000007

typedef long long ll;

ll fact[2002], ifact[2002];
ll ans[2002];

ll pow (ll a, ll n) {
	if (n==0)
		return 1;
	if (n==1)
		return a;

	ll tmp = pow (a, n/2) % MOD;
	ll tmp2 = tmp*tmp % MOD;
	if (n%2==0)
		return tmp2;
	return tmp2*a % MOD;
}

ll comb (ll a, ll b) {
	if (a==0 && b==0)
		return 1;
	if (a<b || a<0)
		return 0;
	ll tmp = ifact[a-b] * ifact[b] % MOD;
	return tmp * fact[a] % MOD;
}

ll ccomb (ll a, ll b) {
	return comb (a+b-1, b);
}



int main () {
	fact[0] = fact[1] = 1;
	ifact[0] = ifact[1] = 1;
	for (int i=2; i<2002; i++) {
		fact[i] = fact[i-1]*i % MOD;
		ifact[i] = ifact[i-1]*pow(i, MOD-2) % MOD;
		ans[i] = -1;
	}
	ans[0] = ans[1] = ans[2] = 0;
	ans[3] = ans[4] = ans[5] = 1;

	ll S;
	cin >> S;

	if (S < 3) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = 1;
	ll mb = S/3 - 1;
	for (int k=1; k<=mb; k++) {
		ll tmp = ccomb (k+1, S-3*(k+1)) % MOD;
		ans += tmp;
		ans %= MOD;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>

#define NUM 100

int main(void)
{
	int n,m;
	int i,j;
	int a[NUM][NUM];
	int b[NUM];
	int c[NUM] = { 0 };

	scanf("%d %d",&n,&m);
	for (i = 0; i < n; i++){
		for (j = 0; j < m; j++){
			scanf("%d", &a[i][j]);
		}
	}
	for (i = 0; i < m; i++)scanf("%d", &b[i]);
	
	for (i = 0; i < n; i++){
		for (j = 0; j < m; j++){
			c[i] += a[i][j] * b[j];
		}
	}
	for (i = 0; i < n; i++){
		printf("%d\n", c[i]);
	}
	return 0;
}

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

typedef long long ll;
ll n, x;

ll fast_pow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if ((b & 0x1))
            ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

ll get_num(ll total, ll x) {
    if (x == total) {
        return (total + 1ll) / 2ll;
    }
    if (x == 1) {
        return 0;
    }
    x--;
    ll tt = (total - 3ll) / 2ll;
    if (x < tt) return get_num(tt, x);
    else if (x == tt) return get_num(tt, x);
    else if (x == tt + 1) return 1 + get_num(tt, x - 1);
    else {
        ll ans1 = (tt + 1ll) / 2ll;
        x -= tt;
        return ans1 + 1 + get_num(tt, x - 1);
    }
    return 0;
}
int main() {
    cin >> n >> x;
    ll total = 4ll * fast_pow(2, n) - 3;
    ll ans = get_num(total , x);
    cout << ans << endl;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]
    
ans=10**20

sp=S[1]
sq=0
sr=S[3]-S[1]
ss=S[-1]-S[3]

th_pq=1
th_rs=3

for i in range(2,N-1):#全体をi番目で二分割
    sq+=A[i-1]
    sr-=A[i-1]
    while th_pq!=i-1:#pqの境界を移動させる
        diff_pq=abs(sp-sq)
        sp2=sp+A[th_pq]
        sq2=sq-A[th_pq]
        diff_pq2=abs(sp2-sq2)
        if diff_pq2 <= diff_pq:
            sp=sp2
            sq=sq2
            th_pq+=1
        else:
            break
        
    while th_rs!=N-1:
        diff_rs=abs(sr-ss)
        sr2=sr+A[th_rs]
        ss2=ss-A[th_rs]
        diff_rs2=abs(sr2-ss2)
        if diff_rs2 <= diff_rs:
            sr=sr2
            ss=ss2
            th_rs+=1
        else:
            break
    temp=max(sp,sr,sq,ss) - min(sp,sq,sr,ss)
    ans=min(ans,temp)
    
print(ans)





Measured memory_bytes: 106744
import math

a, b, h, m = map(int, input().split())

c1 = 6 * m
c2 = 30 * h + m / 2

c0 = abs(c1-c2)
c0 = min(c0, 360-c0)

ans = (a*a + b*b - 2*math.cos(math.radians(c0))*a*b) ** 0.5

print(ans)

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

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

string S;
string T;
int place;

bool dfs(int depth){
	if(depth <= 0)return true;
	if(!dfs(depth-1))return false;
	REP(i,T.size()){
		while(S[place] != T[i])
		{
			//cout << S[place];
			place++;
			if(place >= S.size())return false;
		}
		//cout << depth;
		place++;
		if(depth>1 && place >= S.size())return false;
		if(!dfs(depth-1))return false;
	}	
	
	return true;
}

int main()
{
	cin >> S >> T;
	//cout << S.size() << endl;
	//cout << T.size() << endl;
	int ans = 0;
	while(1){
		//cout << endl;
		place = 0;
		if(dfs(ans))ans++;
		else break;
	}
	//cout << endl;
	cout << ans-1 << endl;
	
	return 0;
}


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

// 連結成分
int color[110000], mi[110000];
ll n;
vector<int> Fri[110000], Blo[110000];
    int cnt[110000];

void dfs(int r, int c){
    stack<int> S;
    S.push(r);
    color[r] = c;
    while(!S.empty()){
        int u = S.top(); S.pop();
        rep(i, 0, Fri[u].size()){
            int v = Fri[u][i];
            if(color[v] == -1){
                color[v] = c;
                S.push(v);
            }
        }
    }
}

void assignColor(){
    int id = 0;
    Rep(i, 1, n) color[i] = -1;
    Rep(u, 1, n){
        if(color[u] == -1) dfs(u, id++);
    }
}

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

    ll m, k;
    cin >> n >> m >> k;
    int a[m], b[m], c[k], d[k];
    rep(i, 0, m){
        cin >> a[i] >> b[i];
        Fri[a[i]].push_back(b[i]);
        Fri[b[i]].push_back(a[i]);
    }
    rep(i, 0, k){
        cin >> c[i] >> d[i];
        Blo[c[i]].push_back(d[i]);
        Blo[d[i]].push_back(c[i]);
    }

    assignColor();

    Rep(i, 1, n){
        cnt[color[i]]++;
    }
    rep(i, 0, m){
        mi[a[i]]++;
        mi[b[i]]++;
    }
    rep(i, 0, k){
        if(color[c[i]] == color[d[i]]){
            mi[c[i]]++;
            mi[d[i]]++;
        }
    }
    

    Rep(i, 1, n){
        ll ans = cnt[color[i]]-mi[i]-1;
        if(i != 1) cout << " ";
        cout << ans;
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 15096
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] sp = line.split("");
        for(int i = 0; i < sp.length; i++) {
            System.out.print("x");
        }
        System.out.println("");
    }
}


Measured memory_bytes: 23124
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] x = new int[5];

        x[sc.nextInt()]++;
        x[sc.nextInt()]++;
        x[sc.nextInt()]++;
        x[sc.nextInt()]++;
        x[sc.nextInt()]++;
        x[sc.nextInt()]++;

        int[] r = new int[2];

        for (int i = 1; i < 5; ++i) {
            if (x[i] == 1) {
                r[0]++;
            } else if (x[i] == 2) {
                r[1]++;
            }
        }

        System.out.println(r[0] == r[1] ? "YES" : "NO");
    }
}

Measured memory_bytes: 23636
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
q = int(input())
query = list(map(int,input().split()))
for k in query:
  ans = 0
  dp0,dp1,dp2 = 0,0,0
  for i in range(n):
    if s[i] == "D":
      dp0 += 1
    elif s[i] == "M":
      dp1 += 1
      dp2 += dp0
    elif s[i] == "C":
      ans += dp2
    if i >= k-1:
      if s[i-k+1] == "D":
        dp0 -= 1
        dp2 -= dp1
      elif s[i-k+1] == "M":
        dp1 -= 1
  print(ans)

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a, b) accumulate(all(a), b)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
ll const INF = 1e18;

template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << min({a+b, b+c, c+a}) << endl;
    return 0;
}


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

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

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

struct Edge {
    int to,cost;
    Edge (int t,int c) {
        to = t; cost = c;
    }
    bool operator>(const Edge& e)const {
        return cost > e.cost;
    } 
    bool operator<(const Edge& e)const {
        return cost < e.cost;
    }
};

int main (void) {
    int H,W;
    cin>>H>>W;
    vector<vector<Edge>> G(10);
    REP(i,10) {
        REP(j,10) {
            int c;
            cin>>c;
            G[j].pb(Edge(i,c)); //辺を逆向きに追加
        }
    }

    //Dijkstraで1をnに変えるのに必要なコストを求める。
    //-> グラフの辺は逆向きなので、
    //   nから1に変えるのに必要なコストを求めることになる（はず）
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    // start��ǉ�
    pq.push(Edge(1, 0));
    vector<int> Cost(10, inf);
    vector<bool> used(10, false);
    Cost[1] = 0;
    while (pq.size()) {
        Edge e = pq.top();
        pq.pop();
        int to, cost;
        to = e.to;
        cost = e.cost;
        if (used[to] == true) {
            continue;
        }
        used[to] = true;
        for (int i = 0; i < G[to].size(); i++) {
            Edge toe = G[to][i];
            if (Cost[toe.to] > Cost[to] + toe.cost) {
            Cost[toe.to] = Cost[to] + toe.cost;
            pq.push(Edge(toe.to, Cost[toe.to]));
            }
        }
    }




    ll ans = 0;
    REP(i,H) {
        REP(j,W) {
            int n;
            cin>>n;
            if (abs(n) != 1) {
                ans += Cost[n];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/*
дружочек, ты видимо не понял с кем общаешься.
вот эта манера речи "клоунская" меня не впечатляет.
давай встретимся и я объясню на понятном тебе языке - языке боли.
*/
int main(){
int n;
cin >> n;
if(n%2==0){
    vector<pair<int,int> > g;
    for(int i = 1;i<=n/2;i++){
        for(int j = i+1;j<=n/2;j++){
            g.push_back({i,j});
            g.push_back({i,n+1-j});
            g.push_back({n+1-i,j});
            g.push_back({n+1-i,n+1-j});
        }
    }
    cout << g.size() << endl;
    for(auto x : g) cout << x.first << ' ' << x.second << endl;
}else{
    vector<pair<int,int> > g;
    for(int i = 0;i<=n/2;i++){
        for(int j = i+1;j<=n/2;j++){
            if(i!=0)g.push_back({i,j});
            if(i!=0)g.push_back({i,n-j});
            g.push_back({n-i,j});
            g.push_back({n-i,n-j});
        }
    }
    cout << g.size() << endl;
    for(auto x : g) cout << x.first << ' ' << x.second << endl;
}
}


Measured memory_bytes: 384
type tree = Nil | Node of int * tree * tree

let create () = Nil

let insert x t =
  let rec doit t id = match t with
    | Nil -> id (Node (x, Nil, Nil))
    | Node (y, l, r) ->
      if x < y then doit l (fun a -> id (Node (y, a, r)))
      else doit r (fun b -> id (Node (y, l, b))) in
  doit t (fun i -> i)

let preorder f t =
  let rec doit = function
    | Nil -> ()
    | Node (x, l, r) -> f x; doit l; doit r in
  doit t

let inorder f t =
  let rec doit = function
    | Nil -> ()
    | Node (x, l, r) -> doit l; f x; doit r in
  doit t

let print t =
  inorder (fun e -> print_string " "; print_int e) t;
  print_newline ();
  preorder (fun e -> print_string " "; print_int e) t;
  print_newline ()

let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let m = read_int () in
  let t = ref (create ()) in
  for _ = 0 to m - 1 do
    let op = Scanf.scanf "%s " (fun i -> i) in
    if op = "print" then print !t
    else t := insert (Scanf.scanf "%d " (fun i -> i)) !t
  done

Measured memory_bytes: 33224
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
#include <cassert>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

void solve()
{
    int n;
    scanf("%d", &n);
    int cnt = 1;
    while (cnt*2<=n) {
        cnt *= 2;
    }
    printf("%d\n", cnt);
    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 128
n, x, m = map(int, input().split())
d = [0]*(m+1)
check = [x]
tmp = x
for i in range(1, n):
    tmp = (tmp**2)%m
    if d[tmp]: break
    d[tmp] = 1
    check.append(tmp)

for i in range(len(check)):
    if tmp == check[i]:
        index = i
        break
sum_c = sum(check[index:])
ans = sum(check)
nokori = n - len(check)
kuri = nokori//len(check[index:])
ans += kuri*sum_c
nokori -= kuri*len(check[index:])
ans += sum(check[index:index+nokori])
print(ans)

Measured memory_bytes: 70220