akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
void vok()
{
    FAST
    FO
    FI
}
int main()
{
    vok();
    ll n,k;
    IN n>>k;
    vll a(n);
    bitset<50> b[n];
    loop(i,0,n)
    {
        IN a[i];
        bitset<50> temp(a[i]);
        b[i]=temp;
    }
    bitset<50> ans(0);
    rloop(i,49,0)
    {
        int countt=0;
        loop(j,0,n)
        {
            if(b[j][i])
            {
                countt++;
            }
          	//cout<<"";
        }
        ans[i]=1;
        if((countt*2)<n && ans.to_ullong()<=k)
        {
            //Do Nothing
        }
        else
        {
            ans[i]=0;
        }
    }
    ll fans=0LL;
    ll X=ans.to_ullong();
    loop(i,0,n)
    {
      	//cout<<"";
        fans+=(X^a[i]);
    }
    OUT fans<<endl
    return 0;
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
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 long long ll;

const long long INF = 1LL << 60;

struct UnionFind {
    vector<int> par, rank;

    UnionFind(int N) : par(N), rank(N) {
        rep(i, N) par[i] = i, rank[i] = 0;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) {
            par[rx] = ry;
        }
        else {
            par[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
    }

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

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

    vector<int> p(N);
    UnionFind tree(N);
    rep(i, N) cin >> p[i];
    rep(i, M) {
        int x, y;
        cin >> x >> y;
        tree.unite(x - 1, y - 1);
    }

    int ans = 0;
    rep(i, N) {
        if (i == p[i] - 1) ans++;
        else if (tree.same(i, p[i] - 1)) ans++;
    }

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

Measured memory_bytes: 1408
#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 V vector<int>
#define ll long long
using namespace std;

ll cnt;
int l;
int A[1000000];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g){
    for( int i = g; i < n; i++){
        int v = A[i];
        int j = i - g;
        while( j >= 0 && A[j] > v){
            A[j+g] = A[j];
            j -= g;
            cnt++;
        }
        A[j+g] = v;
    }
}

void shellSort(int A[], int n){
    for(int h = 1; ; ){
        if (h > n) break;
        G.push_back(h);
        h = h*3 + 1;
    }

    for ( int i = G.size()-1; i >= 0; i--){
        insertionSort(A, n, G[i]);
    }
}

int main() {
    cin >> n;
    rep(i, 0, n) scanf("%d", &A[i]);
    cnt = 0;

    shellSort(A, n);

    cout << G.size() << "\n";
    for (int i = G.size() - 1; i >= 0; i--){
        printf("%d", G[i]);
        if(i) printf(" ");
    }
    printf("\n");
    // printf("%d\n", cnt);
    cout << cnt << endl;
    rep(i, 0, n) printf("%d\n", A[i]);

    return 0;
}



Measured memory_bytes: 7212
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll A, B, C;
string s;
ll t;
ll ret = 0;

void input() {
  IN(A);
  IN(B);
  IN(C);
}

void solve() {
  cout << C << " " << A << " " << B << endl;
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define ll long long
#define pii pair<int,int>
#define y1 Emilia
#define N 500500
#define dracarys ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

ll a, b;
map<ll, int> u1, u2;
set<ll> st1, st2;
int main(){
    dracarys
    cin >> a >> b;
    for (ll i = 2; i * i <= a; ++i) {
        if (a % i == 0) {
            u1[i] = 1;
            while (a % i == 0) a /= i;
        }
    }
    if (a > 1) u1[a] = 1;
    
    for (ll i = 2; i * i <= b; ++i) {
        if (b % i == 0) {
            u2[i] = 1;
            while (b % i == 0) b /= i;
        }
    }
    if (b > 1) u2[b] = 1;
    int ans = 0;
    for (map<ll, int> :: iterator it = u1.begin(); it != u1.end(); ++it)
        if (u2[it->first]) ++ans;
    cout << ans + 1 << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int main (){

  string a;
  char b;
  int counter[26]={0},num;

  while(getline(cin,a)){

  for(int i=0; i < a.size() ; i++){
    a[i]=tolower(a[i]);

    if(islower(a[i])){
      num = a[i] - 'a';
      counter[num]++;
    }
  }
  }
  for(int j=0; j<26 ;j++){
    b=j+'a';
    cout << b <<" : "<<counter[j]<<endl;
  }

  return 0;
}

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

int main() {
  int N;
  cin >> N;
  while (true) {
    string tmp = to_string(N);
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    if (tmp.size() == 1) return cout << N << "\n", 0;
    N++;
  }
}

Measured memory_bytes: 256
S = input()
T = input()
LS = len(S)
LT = len(T)
L = []

if T in S:
  print(0)
else:
    for ls in range(LS - LT + 1):
        d = 0
        for lt in range(LT):
            if S[ls + lt] != T[lt]:
                d += 1
        L.append(d)
    print(min(L))


Measured memory_bytes: 73064
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb emplace_back
#define vi vector<int>
using namespace std;
struct brackets{
    int mnprefix, sum;
    brackets(const string &s){
        mnprefix=0;
        sum=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                sum++;
            }
            if(s[i]==')'){
                --sum;
            }
            mnprefix=min(mnprefix, sum);
        }
        mnprefix=-mnprefix;
    }
    bool operator<(const brackets &y){
        return max(mnprefix, y.mnprefix-sum) < max(y.mnprefix, mnprefix - y.sum);
    }
};
void solve(){
    int n;
    cin>>n;
    vector<brackets> seq;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        seq.pb(brackets(s));
    }
    sort(seq.begin(), seq.end());
    int currsum=0;
    for(int i=0;i<n;i++){
        if(currsum-seq[i].mnprefix<0){
            cout<<"No\n";
            return;
        }
        currsum+=seq[i].sum;
    }
    if(currsum!=0){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Measured memory_bytes: 11584
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);

    int n;
    cin >> n;
    if (n%1000==0)
    {
        cout << "0" << endl;
    }
    else
    {
        cout << 1000-(n%1000) << endl;
    }

    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int> p;
vector<vector<int>> adj;
vector<bool> in_cyc;
vector<bool> vis;
vector<int> ass;
int cyc_root;

int mex(vector<int>& v){
  if(v.empty())
    return 0;
  sort(v.begin(), v.end());
  if(v[0] != 0)
    return 0;
  for(int i = 1;i < v.size();i++){
    if(v[i] > v[i - 1] + 1)
      return v[i - 1] + 1;
  }
  return v.back() + 1;
}
int next_mex(vector<int>& v, int x){
  unordered_set<int> ss;
  for(auto el : v)
    ss.insert(el);
  x++;
  while(ss.find(x) != ss.end())
    x++;
  return x;
}
void detect_cycle(){
  vector<bool> v(n);
  int x = 0;
  v[0] = 1;
  while(!v[p[x]]){
    x = p[x];
    v[x] = 1;
  }

  cyc_root = x;
  in_cyc[x] = 1;
  x = p[x];
  while(x != cyc_root){
    in_cyc[x] = 1;
    x = p[x];
  }
//  cout << cyc_root << endl;
}

void dfs(int u){
  vis[u] = 1;
  vector<int> chs;
  for(auto el : adj[u]){
    assert(!in_cyc[el]);
    if(!vis[el])
      dfs(el);
    chs.push_back(ass[el]);
  }
  ass[u] = mex(chs);
}

vector<int> get_ch(int u,  bool ignore_cyc=false){
  vector<int> r;
  for(auto el : adj[u]){
    if(ignore_cyc || !in_cyc[el])
      r.push_back(ass[el]);
  }
  return r;
}
ostream& operator<<(ostream& out, vector<int>& v){
  for(auto el : v){
    out << el << ' ';
  }
  return out;
}
bool try_(int v){
  ass[cyc_root] = v;
  int x = p[cyc_root];
//  cout << "ASD " << x << endl;
  vector<int> tv;
  while(x != cyc_root){
    tv = get_ch(x, true);
//    cout << x << ' ' << tv << endl;
    ass[x] = mex(tv);
    x = p[x];
  }
  tv = get_ch(cyc_root, true);
  return ass[cyc_root] == mex(tv);
}

bool fix_cycle(){
  vector<int> root_chs = get_ch(cyc_root);
  int m1 = mex(root_chs);
  int m2 = next_mex(root_chs, m1);
//  cout << cyc_root << ' ' << m1 << ' ' << m2 << endl;


//  for(int i = 0;i < n;i++)
//    cout << ass[i] << endl;
  if(try_(m1))
    return true;

  if(try_(m2))
    return true;
  return false;
}

int main(){
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  cin >> n;

  p.resize(n);
  adj.resize(n);
  in_cyc.resize(n);
  ass.resize(n);
  vis.resize(n);
  cyc_root = -1;

  for(int i = 0;i < n;i++){
    cin >> p[i];
    p[i]--;
    adj[p[i]].push_back(i);
  }
  detect_cycle();
//  for(int i = 0;i < n;i++){
//    cout << in_cyc[i] << endl;
//  }
  for(int i = 0;i < n;i++){
    if(!in_cyc[i] && !vis[i]){
      dfs(i);
    }
  }


  cout << (fix_cycle() ? "POSSIBLE" : "IMPOSSIBLE");
}


Measured memory_bytes: 14836
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll n;
  cin>>n;
  ll keta=26,count=1;
  while(1){
    if(n<=keta){
      break;
    }
    n-=keta;
    keta*=26;
    count++;
  }
  n--;
  string ans="";
  while(count>0){
    count--;
    //cout<<n<<endl;
    ans.push_back('a'+n%26);
    n/=26;
  }
  reverse(ans.begin(),ans.end());
  cout<<ans<<endl;
  return 0;
}

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

int dp[100005];
int a[100005];

#undef int
int main()
{
#define int long long
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++)
          cin >> a[i];

    for(int i=1;i<n;i++)
          dp[i]=1e9;

    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i-j>=0)
                dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
        }
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
    char S[5];
    int ok=0;
    scanf("%s",S);
    for(int i=0;S[i]!='\0';i++){
        int c=0;
        for(int j=i;S[j]!='\0';j++){
            if(S[i]==S[j])
                c++;
        }
        if(c==1)
            ok++;
    }
    if(ok==2)
        printf("Yes\n");
    else
        printf("No\n");
    
    return 0;
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    ll N, K;
    cin >> N >> K;

    ll L = min(N-1, K);

    // 前処理
    COMinit();

    ll ans = 0;
    for(ll i=0; i<=L; i++){
        ans += (COM(N, i) * COM(N-1, N-1-i)) % MOD;
        ans = ans % MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12160
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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 long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    ll N, M;
    cin >> N >> M;

    ll ct = 1;
    rep(i, M) ct *= 2;

    ll ans = (N - M) * 100 * ct + M * 1900 * ct;

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

Measured memory_bytes: 256
h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 12
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for a, b in m:
    for i in range(h + 1):
        if i + a > h:
            dp[h] = min(dp[h], dp[i] + b)
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(dp[h])


Measured memory_bytes: 42988
n = int(input())
S = list(input())

ans = [0]*n
temp = 0
for i in range(1,n):
    if S[i-1] == "W":
        temp += 1
    ans[i] += temp
    
S.reverse()
ans.reverse()

temp = 0
for i in range(1,n):
    if S[i-1] == "E":
        temp += 1
    ans[i] += temp

ans.reverse()
print(min(ans))
     

Measured memory_bytes: 17528
mod = 10**9+7
def inv(n):
    x = pow(n,mod-2,mod)
    return x
k = int(input())
s = input()
l = len(s)
cmb = 1
ans = 1
for i in range(k):
    cmb =cmb*25*(k+l-i)*inv(i+1)
    cmb %= mod
    ans += cmb
    ans %= mod
print(ans)

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef string::const_iterator State;
VI arr1 = {0,1,2};
VI arr2 = {0,1,2};
VI arr3 = {0,1,2};
ll expression0(State&);
ll number(State &begin){
  ll ret = 0;
  while(isdigit(*begin)){
    ret *= 10;
    ret += *begin - '0';
    begin++;
  }
  return ret;
}

ll factor(State &begin){
  if(*begin == '('){
    begin++;
    ll ret = expression0(begin);
    begin++;
    return ret;
  }else{
    return number(begin);
  }
  cerr << "err" << endl;
  return -1;
}

ll expression2(State &begin){
  ll ret = factor(begin);
  while(true){
    if(*begin == '+' && arr1[0] == 2){
      begin++;
      ret += factor(begin);
    }
    else if(*begin == '-' && arr2[0] == 2){
      begin++;
      ret -= factor(begin);
    }
    else if(*begin == '*' && arr3[0] == 2){
      begin ++;
      ret *= factor(begin);
    } else {
      break;
    }
  }
  return ret;
}

ll expression1(State &begin){
  ll ret = expression2(begin);
  while(true){
    if(*begin == '+' && arr1[0] == 1){
      begin++;
      ret += expression2(begin);
    }
    else if(*begin == '-' && arr2[0] == 1){
      begin++;
      ret -= expression2(begin);
    }
    else if(*begin == '*' && arr3[0] == 1){
      begin ++;
      ret *= expression2(begin);
    } else {
      break;
    }
  }
  return ret;
}


ll expression0(State &begin){
  ll ret = expression1(begin);
  while(true){
    if(*begin == '+' && arr1[0] == 0){
      begin++;
      ret += expression1(begin);
    }
    else if(*begin == '-' && arr2[0] == 0){
      begin++;
      ret -= expression1(begin);
    }
    else if(*begin == '*' && arr3[0] == 0){
      begin ++;
      ret *= expression1(begin);
    } else {
      break;
    }
  }
  return ret;
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  ll mans = -LLONG_MAX;
  do {
    do {
      do {
        State begin = s.begin();
        ll ans = expression0(begin);
        mans = max(mans,ans);
      } while (next_permutation(all(arr3)));
      sort(all(arr3));
    } while (next_permutation(all(arr2)));
    sort(all(arr2));
  } while (next_permutation(all(arr1)));
  cout << mans << endl;
  return 0;
}



Measured memory_bytes: 3228
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define koto_memory(a) cout<<(sizeof(a)/1048576.0)<<" MB";
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=2e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
int h,w,k,ans,cnt;char a[10][10];set<pair<vi,vi>>s;vi R(10,0),C(10,0);
void f(int r=0,int c=0){
  if(r==h and c==w){
    cnt++;
    int an=0;if(s.count({R,C}))return;
    rep(i,0,h-1)rep(j,0,w-1)if(a[i][j]=='#')if(R[i]==0 or C[j]==0)an++;
    if(an==k){
    s.insert({R,C});}
    return;
  }
  if(r>=h+1 or c>=w+1){
    return;
  }
  int an=0;
  rep(i,0,h-1)rep(j,0,w-1)if(a[i][j]=='#')if(R[i]==0 or C[j]==0)an++;
  if(an<k)return;
  f(r+1,c);
  R[r]=1;
  f(r+1,c);
  R[r]=0;
  f(r,c+1);
  C[c]=1;
  f(r,c+1);
  C[c]=0;
}
void solve(){
  cin>>h>>w>>k;
  rep(i,0,h-1)rep(j,0,w-1)cin>>a[i][j];
  rep(m1,0,(1<<h)-1){
  	rep(m2,0,(1<<w)-1){
  		int x=0;
  		rep(i,0,h-1)if(((1<<i)&m1))
  			rep(j,0,w-1)if(((1<<j)&m2))
  				if(a[i][j]=='#')x++;
  		// if(x)cout<<x;
  		if(x==k)ans++;
  	}
  }
  cout<<ans;
}
int32_t main()
{
  ibs;cti;
  solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  // int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int H,N;
 cin >> H>>N;
 vector<int> Ai(N+1);
 for (int i = 0; i < N; i++)
   cin >> Ai.at(i);
 for (int i = 0; i < N; i++)
   H=H-Ai.at(i);
 if(H<=0)
   cout << "Yes" << endl;
 if(H>0)
   cout << "No" << endl;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    int xa = min(a, k);
    k -= xa;
    int xb = min(b, k);
    k -= xb;
    int xc = k;
    cout << xa - xc << endl;

    return 0;
}

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

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

    map<int, int> mp;
    for(int x=1; x<100; x++)
    for(int y=1; y<100; y++)
    for(int z=1; z<100; z++)
    {
        mp[x*x + y*y + z*z + x*y + y*z + z*x]++;
    }

    for(int i=1; i<=N; i++) cout << mp[i] << '\n';

    return 0;
}


Measured memory_bytes: 5460
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


def dfs(set_list, n):
    global N
    for i, s in enumerate(set_list):
        new_set = s.copy()
        new_set.add(n)
        new_set_list = set_list.copy()
        new_set_list[i] = new_set
        if n == N - 1:
            min_string(new_set_list)
        else:
            dfs(new_set_list, n + 1)
    set_list.append(set([n]))
    if n == N - 1:
        min_string(set_list)
    else:
        dfs(set_list, n + 1)


def min_string(set_list):
    global N

    j = 0
    ret_list = [0 for _ in range(N)]
    for s in set_list:
        for i in s:
            ret_list[i] = j

        j += 1

    print(''.join([chr(j + ord("a")) for j in ret_list]))


def resolve():
    global N
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    dfs([], 0)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """1"""
        output = """a"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2"""
        output = """aa
ab"""
        self.assertIO(input, output)


Measured memory_bytes: 6928
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) int((a).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

#define _deb(x) cout<<x;
void _print() {cerr << "]\n";} template <typename T, typename... V>void _print(T t, V... v) {_deb(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
template <class T, class U> void print_m(const map<T,U> &m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}
template<class T, class U>void debp(const pair<T, U> &pr, bool end_line=1){cout<<"{"<<pr.first<<" "<<pr.second<<"}"; cout<<(end_line ? "\n" : ", ");}
template <class T> void print_vp(const T &vp, int sep_line=0){if(vp.empty()){cout<<"Empty"<<endl; return;}if(!sep_line) cout<<"{ ";for(auto x: vp) debp(x,sep_line);if(!sep_line) cout<<"}\n";cout<<endl;}
template <typename T>void print(const T &v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<sz(v); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<endl;}
template <typename T>void print_vv(const T &vv){if(sz(vv)==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<sz(*vv.begin()); j++)cout<<setw(w)<<j<<" ";cout<<endl;int i = 0;for(auto &v: vv){cout<<i++<<" {";for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<"},\n";}cout<<endl;}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s;
    while(cin>>s){
        int cnt = 0, ans = 0;
        for(auto x: s){
            if(x=='R') ++cnt;
            else cnt = 0;
            max_self(ans, cnt);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 3632
# あまりにもTLEになるから解説見ちゃった

from sys import stdin
import numpy as np

s = input()
a = [int(c) for c in s]

## 0から始まる数列
cnt_0 = 0
for i in range(len(a)):
  if a[i] == (i % 2):
    cnt_0 += 1
    
cnt_1 = 0
for i in range(len(a)):
  if a[i] == ((i+1) % 2):
    cnt_1 += 1
  
ans = min(cnt_0, cnt_1)  
print(ans)

Measured memory_bytes: 13668
#include <iostream>
#include <cstdio>
#include <iomanip>
using namespace std;
const int M = 100000;
const double pi = 3.141592653589;

int main(){
	int n, m;
	int a[1000][1000];
	int b[M];
	int o[M] = { 0 };

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < m; k++) {
			cin >> a[i][k];
		}
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < m; k++) {
			o[i] = o[i] + a[i][k] * b[k];
		}
		cout << o[i] << endl;
	}



	return 0;
}

Measured memory_bytes: 3784
#include<stdio.h>
long result[105];
long long qiu(int k,int n)
{
    for(int i=1;i<=n;i++)
    {
        result[i] = 1;
        for(int j=i-1;j>=1;j--)
        {
            result[j] = result[j-1]+result[j];
        }
        result[0] = 1;
    }
    return result[k];
}
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    int i;
    int ji=0,o=0;
    int temp;
    long long ans=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        if(temp%2==0)
            o++;
        else
        {
            ji++;
        }
    }
    if(p==0)
    {
        long long a=1;
        if(o==0)
        {
            a=1;
        }
        else
        {
        for(i=1;i<=o;i++)
        {
            a=a*2;
        }
        }
        long long b=0;
        if(ji==0)
        {
            b=1;
        }
        else
        {
        for(i=0;i<=ji;i=i+2)
        {
            b=b+qiu(i,ji);
        }
        }
        ans=a*b;
    }
    else if(p==1)
    {
        long long a=1;
        for(i=1;i<=o;i++)
        {
            a=a*2;
        }
        long long b=0;
        if(ji==0)
        {
            b=0;
        }
        else
        {
            for(i=1;i<=ji;i=i+2)
            {
                b=b+qiu(i,ji);
            }
        }
        ans=a*b;
    }
    printf("%lld",ans);
    return 0;
}

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

int main() 
{
    // min = INT_MAX; max = 0;
    int n, k, res=INT_MAX;
    cin >> n >> k;
    vector<int> x(n);
    for (int i=0; i<n; i++)
        cin >> x[i];
    sort(x.begin(), x.end());
    for (int i=k-1; i<n; i++)
        res = min(res, x[i]-x[i-k+1]);
    cout << res;
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#define MAX 500000

int size,A[MAX+1];

void swap( int  *a , int  *b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void buildmaxHeapify(int k)
{
  int left,right,big;
  left=2*k;
  right=2*k+1;

  if(left<=size && A[left]>A[k])big=left;
  else big=k;
  if(right<=size && A[right] > A[big])big=right;

  if(big!=k)
    {
      swap(&A[k],&A[big]);
      buildmaxHeapify(big);
    }
}

int main()
{
  int i;
  scanf("%d",&size);
  for(i=1;i<=size;i++)scanf("%d",&A[i]);
  for(i=size/2;i>=1;i--)buildmaxHeapify(i);
  for(i=1;i<=size;i++)printf(" %d",A[i]);
  printf("\n");

  return 0;
}

Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ll n, s1 = 0, s2 = 0, ans = INF;
  cin >> n;
  vector<ll> w(n);
  REP(i, n) { cin >> w[i]; }
  REP(t, n) {
    REP(i, n) {
      if (i <= t)
        s1 += w[i];
      else
        s2 += w[i];
    }
    ans = min(ans, abs(s1 - s2));
    s1 = 0;
    s2 = 0;
  }
  cout << ans << endl;
  return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;

int main(){
  int a,b; cin>>a>>b;
  cout<<max(a+b,max(a-b,a*b))<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
const int ddx[4] = {1,1,-1, -1};
const int ddy[4] = {1,-1,-1,1};
//////////////////////////////////

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


    return 0;
}

// EOF


Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define V vector<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
    int N;  cin >> N;
    while(N){
      if(N % 10 == 7){  cout << "Yes" << endl;  return 0;}
      N /= 10;
    }

    cout << "No" << endl;
  	return 0;
}


Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main(void){
    unsigned long long H,W;
    unsigned long long count = 0;
    cin >> H >> W;
    if(H == 1 || W == 1){
        cout << 1 << endl;
        return 0;
    }
    count = (W - (W / 2)) * (H - (H / 2)) + (W / 2) * (H / 2);
    cout << count << endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
ilst = [int(i) for i in input().split()]
tlst = [0]*n
total = 0
for i in range(m):
    List = [int(j) for j in input().split()]
    xlst = []
    for p in List:
        xlst.append(ilst[p-1])
    maxIndex = [i for i, x in enumerate(xlst) if x == max(xlst)]
    if len(maxIndex) >= 2:
        for k in List:
            tlst[k-1] +=1
    else:
        List.pop(maxIndex[0])
        for k in List:
            tlst[k-1] +=1
for x in tlst:
    if x == 0:
        total +=1
print(total)

Measured memory_bytes: 20140
A, B = map(int, input().split())

if A != 1 and B != 1:
    if A == B:
        winner = 'D'
    else:
        winner = 'A' if A > B else 'B'
else:
    if A == B:
        winner = 'D'
    else:
        winner = 'A' if A == 1 else 'B'

if winner == 'A':
    print('Alice')
elif winner == 'B':
    print('Bob')
else:
    print('Draw')


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

using namespace std;

typedef long long ll;

int main() {
    int w, h; cin >> w >> h;
    priority_queue<int, vector<int>, greater<int>> p, q;
    for (int i = 0; i < w; ++i) {
        int pi; cin >> pi;
        p.push(pi);
    }
    for (int i = 0; i < h; ++i) {
        int qi; cin >> qi;
        q.push(qi);
    }
    ll ans = 0;
    for (int c = 0; c < h + w; ++c) {
        if (q.empty() || (!p.empty() && p.top() < q.top())) {
            ans += (ll)p.top() * (ll)(q.size() + 1);
            p.pop();
        } else {
            ans += (ll)q.top() * (ll)(p.size() + 1);
            q.pop();
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#include<math.h>
#include<queue>
#include<cstdio>
#include<set>
#include<map>
using namespace std;
using ll = long long;

int main(){
    ll H,W,M;
    cin >> H >> W >> M;
    vector<ll> h(M),w(M);
    vector<pair<ll,ll>> row(H+1),col(W+1);
	vector<ll> r(H+1,0),c(W+1,0);
    for(ll i=0; i<M; i++){
        cin >> h.at(i) >> w.at(i);
        r.at(h.at(i))++;
        c.at(w.at(i))++;
    }
    for(ll i=1; i<=H; i++){
        row.at(i)=make_pair(r.at(i),i);
    }
    for(ll i=1; i<=W; i++){
        col.at(i)=make_pair(c.at(i),i);
    }
    sort(row.begin(),row.end());
    sort(col.begin(),col.end());
    ll maxrow=row.at(H).first;
    vector<ll> mr;
  	for(ll i=H; i>0; i--){
        if(row.at(i).first==maxrow) mr.push_back(row.at(i).second);
        else break;
    }
    ll maxcol=col.at(W).first;
  	vector<ll> mc;
    for(ll i=W; i>0; i--){
        if(col.at(i).first==maxcol) mc.push_back(col.at(i).second);
        else break;
    }
  	ll minus=1;
    ll plus=0;
  	ll a=mr.size();
  	ll b=mc.size();
    for(ll i=0; i<M; i++){
        if(r.at(h.at(i))==maxrow&&c.at(w.at(i))==maxcol){
            plus+=1;
        }
    }
    if(plus<a*b) minus=0;
    cout << maxrow+maxcol-minus << endl;
}

Measured memory_bytes: 30296
a,b,c = gets.chomp.split("/").map(&:to_i)

if a < 2019
    puts "Heisei"
elsif a > 2019
    puts "TBD"
else
    # a = 2019
    if b <= 4
        puts "Heisei"
    else
        puts "TBD"
    end
end

Measured memory_bytes: 3836
S = input()
dp = [[0] * 13 for _ in range(2)]

mod = 10**9 + 7
dp[0][0] = 1
pow10 = 1
for i, s in enumerate(S[::-1]):
    now_idx, next_idx = i & 1, (i + 1) & 1
    dp[next_idx] = [0] * 13
    if s == '?':
        for j in range(13):
            for k in range(10):
                next_mod = (j + k * pow10) % 13
                dp[next_idx][next_mod] += dp[now_idx][j]
                dp[next_idx][next_mod] %= mod
    else:
        k = int(s)
        for j in range(13):
            next_mod = (j + k * pow10) % 13
            dp[next_idx][next_mod] += dp[now_idx][j]
            dp[next_idx][next_mod] %= mod
    pow10 = (pow10 * 10) % 13
print(dp[len(S) & 1][5])


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

const long long infinity = 1e18;



int main(){
	int n,W;
	cin>>n>>W;
	int w[n];
    int v[n];

    
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	vector<vector<long long> > dp( n , vector<long long> (W + 1, 0));
	dp[0][0] = 0;
	dp[0][w[0]] = v[0];
	
	for(int id=1;id<n;id++){
		dp[id][0] = 0;
		for(int j=1;j<=W;j++){
			
			// Discard current object
			dp[id][j] = dp[id-1][j];
			
			// Pick current object
			if(j >= w[id])
				dp[id][j] = max(dp[id][j], v[id] + dp[id-1][j-w[id]]);
			
		}
	}
	
	long long answer = -infinity;
	
	for(int j = 0; j <= W;j++){
		answer = max(answer, dp[n-1][j]);
	}
	
	cout<<answer;
	
	return 0;
}


Measured memory_bytes: 82392
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;
const ll MOD = (ll)1e9 + 7;
ll mult(ll x, ll y)
{
	return (x * y) % MOD;
}

const int N = 500;
int n, m;
char s[N][N];
vector<int> g[N];
bool used[N];
ll f[5];

ll getCount(string p)
{
	sort(p.begin(), p.end());
	ll res = f[(int)p.size()];
	int l = 0;
	while(l < (int)p.size())
	{
		int r = l;
		while(r < (int)p.size() && p[l] == p[r]) r++;
		res /= f[r - l];
		l = r;
	}
	return res;
}

void dfs(int v)
{
	used[v] = 1;
	for (int u : g[v])
		if (!used[u])
			dfs(u);
	return;
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	f[0] = 1;
	for (int i = 1; i < 5; i++)
		f[i] = f[i - 1] * i;

	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf(" %s ", s[i]);
	ll ans = 1;
	for (int x = 0; x < n / 2; x++)
		for (int y = 0; y < m / 2; y++)
		{
			string p = "";
			p += s[x][y];
			p += s[n - 1 - x][y];
			p += s[x][m - 1 - y];
			p += s[n - 1 - x][m - 1 - y];
			ll z = getCount(p);
			if (z == 24)
			{
				z = 12;
				g[x].push_back(n + y);
				g[n + y].push_back(x);
			}
			ans = mult(ans, z);
		}
	if (n & 1)
	{
		bool ok = false;
		for (int y = 0; !ok && y < m / 2; y++)
			if (s[n / 2][y] != s[n / 2][m - 1 - y])
			{
				ok = true;
				ans = mult(ans, 2);
			}
	}
	if (m & 1)
	{
		bool ok = false;
		for (int x = 0; !ok && x < n / 2; x++)
			if (s[x][m / 2] != s[n - 1 - x][m / 2])
			{
				ok = true;
				ans = mult(ans, 2);
			}
	}
	int res = n + m;
	for (int i = 0; i < n + m; i++)
		if (!used[i])
		{
			res--;
			dfs(i);
		}
	for (int i = 0; i < res; i++)
		ans = mult(ans, 2);
	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 512
#define _USE_MATH_DEFINES    
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define quickIO()   {cin.tie(0);    cout.sync_with_stdio(false);}
#define rep(i,n)    for(ll i=0; i<(ll)n; i++)
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define fcout cout << fixed << setprecision(10) 
const ll inf = 1e18;
const ll mod = 1e9 +7;
     
ld sqrtld(ld x){
    ld left = 0, right = x;
    rep(i, 100){
        ld mid = (left + right)/2;
        if (mid*mid <= x)   left =mid;
        else    right = mid;
    }
    return left;
}



ll c[110];
int a[110];

int main (){
    int n;      cin >> n;
    int right, mid, left;
    int rp, mp;
    string ans;
    right =0;
    left = n;

    cout << 0 << endl;
    cin  >> ans;
    if(ans =="Vacant"){
        return 0;
    }else if(ans =="Male"){
        rp = 1;
    }else{
        rp = 0;
    }

    rep(i,18){
        mid = (right + left)/2;
        cout << mid << endl;
        cin >> ans;
        if(ans =="Vacant"){
            return 0; 
        }else{
            if(ans =="Male"){
                mp = 1;
            }else{
                mp = 0;
            }
        }
        if(abs(mp-rp) == (mid-right)%2 ){
            right = mid;
            rp = mp;
        }else{
            left = mid;
        }
    }
    cout << n-1 << endl;
}



Measured memory_bytes: 852
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[4],b[2];
	cin>>a[0]>>a[1]>>a[2]>>a[3]>>b[0]>>b[1];
	sort(a,a+4);
	sort(b,b+2);
	cout<<a[1]+a[2]+a[3]+b[1]<<endl;
	return 0;
}	


Measured memory_bytes: 3088
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
ll mod = 1e9 + 7;

int A,B;
int x[111];
ll coudp[111][111][5555];
string divide[4] = { "dream","dreamer","erase","eraser" };
int main()
{
	string N;
	map<int, int> mp;
	cin >> N;

	/*for (int i = 2; i <= N; i++)
	{
		int x = i;
		for (int j = 2; j <= x; j++)
		{
			while (x % j == 0)
			{
				x /= j;
				mp[j]++;
			}
		}
	}
	ll ans = 1;
	for (auto x : mp)
	{
		ans = ((ans % mod) * (x.second+1) % mod) % mod;
	}

	cout << ans << endl;*/
	int A = 0;
	int Z = 0;
	for (int i = 0; i < N.length(); i++)
	{
		if (N.at(i) == 'A')
		{
			A = i;
			break;
		}

	}
	for (int i = N.length()-1; i >0 ; i--)
	{
		if (N.at(i) == 'Z')
		{
			Z = i;
			break;
		}

	}

	cout << Z - A + 1 << endl;

	return 0;

		
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
using namespace std;
#define INF (1<<26)
#define P(a,b) make_pair(a,b)

int n,m;
int g[100][100]={};


int prim(int low){
	int used[100] = {} , cost[100] = {} , total = 0;
	for(int i = 0 ; i < 100 ; i++) cost[i] = INF;
	used[0] = true;
	for(int i = 0 ; i < n ; i++) if(g[i][0] >= low) cost[i] = min(g[i][0],cost[i]);
	while(1){
		int uV = -1, uC = INF;	
		for(int i = 0 ; i < n ; i++){
			if(!used[i] && cost[i] >= low && uC > cost[i]){
				uC = cost[i];
				uV = i;
			}
		}
		if(uV == -1){
			return count(used,used+n,1) == n ? total - low : INF;
		}
		total = max(uC,total);
		used[uV] = true;
		for(int i = 0 ; i < n ; i++) if(g[i][uV] >= low)cost[i] = min(g[i][uV],cost[i]);
	}
	
}
int main(){
	while(cin >> n >> m && n){
			for(int i = 0 ; i < n ; i++)
				for(int j = 0 ; j < n ; j++)
					g[i][j] = INF;
			
			for(int i = 0 ; i < m ; i++){
				int a,b,c;
				cin >> a >> b >> c;
				a--,b--;
				g[a][b] = g[b][a] = c;
			}
			int ans = INF;
			for(int i = 0 ; i < n ; i++){
				for(int j = i ; j < n ; j++){
					if(g[i][j] != INF)ans = min(ans,prim(g[i][j]));
				}
			}
			cout << (ans==INF?-1:ans) << endl;
	}
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;

int main(void){
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n), f(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> f[i];
    sort(all(a));
    sort(all(f), greater<ll>());
    ll ng = -1, ok = 1e12;
    while (ng + 1 < ok) {
        ll t = (ng + ok)/2;
        auto check = [&]() {
            ll sum = 0;
            rep(i,n) {
                ll x = ceil(a[i]-(double)t/f[i]);
                if (x > 0) sum += x;
            }
            return sum <= k; 
        };
        if (check()) {
            ok = t;
        } else {
            ng = t;
        }
    }
    cout << ok << endl;

    return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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 gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
#ifdef _MSC_VER
inline unsigned int __builtin_clz(unsigned int x){unsigned long r;_BitScanReverse(&r,x);return 31-r;}
#endif // _MSC_VER
template<class V> struct SparseTable { // [L,R)
    const V def = 0;
    inline V comp(V a, V b) { return gcd(a,b); }

    int n; vector<V> a, b[20]; inline int __lg(int x) { return 32 - 1 - __builtin_clz(x); }
    void init(vector<V> v) {
        int nn = v.size(); n = 1; while (n < nn) n *= 2; a.resize(n);
        rep(i, 0, 20) b[i].resize(n); rep(i, 0, nn) a[i] = v[i];

        int d = 1 << __lg(n - 1), e = d << 1;
        for (int h = 0, f; (f = 1 << h) <= d; ++h) {
            for (int i = f, r = f << 1; i < e; i += r) {
                b[h][i - 1] = a[i - 1];
                for (int j = i - 2; j >= i - f; --j) b[h][j] = comp(b[h][j + 1], a[j]);
                b[h][i] = a[i];
                for (int j = i + 1; j < i + f; ++j) b[h][j] = comp(b[h][j - 1], a[j]);
            }
        }
    }

    V get(int L,int R){assert(0<=L&&L<=R);if(L==R)return def;R--;if(L==R)return a[L];int h=__lg(L^R);
        return comp(b[h][L],b[h][R]);}};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int N, A[101010];
SparseTable<int> st;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];

	vector<int> v;
	rep(i, 0, N) v.push_back(A[i]);
	st.init(v);

	int ans = 0;
	rep(i, 0, N) {
		int g = 0;
		g = gcd(g, st.get(0, i));
		g = gcd(g, st.get(i + 1, N));
		chmax(ans, g);
	}
	cout << ans << endl;
}


Measured memory_bytes: 12408
#!/usr/bin/env python3


def main():
    s = input()
    t = input()

    ans = float("inf")

    add = 0
    for j in range(len(s) - len(t) + 1):
        tans = 0
        for i in range(len(t)):
            if s[i + add] == t[i]:
                pass
            else:
                tans += 1
        add += 1
        ans = min(ans, tans)

    print(ans)


main()


Measured memory_bytes: 9116
N = int(input())
wlist = list(map(int, input().split()))
mae = 0
ushiro = 0
sabun = sum(wlist)

for i in range(N):
    mae = sum(wlist[:i+1])
    ushiro = sum(wlist[i+1:])
    if abs(mae - ushiro)  < sabun :
        sabun = abs(mae- ushiro)
    else:
        break

print(sabun)

Measured memory_bytes: 3064