akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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 (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;
const ll MOD = 1e9+7;

// n^m%MOD を求める。O( log(m) )
ll modpow(ll n, int m){
	ll ret=1;
	for(int i=1; i<=m; i<<=1, (n*=n)%=MOD){
		if( m&i ) (ret *= n) %= MOD;
	}
	return ret;
}

// 逆元を求める
ll modinv(ll n){
	return modpow( n, MOD-2 );
}

// 階乗を求める。O(1)  準備O( n*log(n) )
// fact[n]     : nの階乗
// fact.inv[n] : nの階乗の逆元
class FACTORIAL{
public:
	vector<ll> fact, inv;
	FACTORIAL(int MAX_NUM): fact(MAX_NUM), inv(MAX_NUM) {
		fact[0] = inv[0] = 1;
		for(ll i=1; i<MAX_NUM; i++){
			fact[i] = (fact[i-1] * i) % MOD;
			inv[i] = modinv( fact[i] );
		}
	}
	const ll& operator [ ] ( const int i ) const {
		return fact[i];
	}
} fact(1000006); // nの最大値を指定


// 組み合わせ(Combinationを求める) O(1)
ll cmb(unsigned int n, unsigned int r){
	if( n < r ) return 0;
	return fact[n] * fact.inv[r] % MOD * fact.inv[n-r] % MOD;
}


map<pii,ll> memo;
ll fib(int n, int k){
	if( k < 0 || k > n || n <= 0 ) return 0;
	if( k == 0 ) return 1;
	if( n == 1 && k == 1 ) return 1;
	pii p = pii(n, k);
	if( memo.count(p) ) return memo[p];
	ll ret = 0;
	int nd = min({k, n/2, 10000});
	rep(i,nd+1){
		//if( memo.count(pii(n-nd-i, k-nd)) ){
		//	ret += cmb(nd, i) * memo[pii(n-nd-i, k-nd)];
		//}else{
			ret += cmb(nd, i) * fib(n-nd-i, k-nd);
		//}
		ret %= MOD;
	}
	return memo[p] = ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	ll N, K, ans=0;

	cin >> N;

	//cout << fib(N, K) << endl;
	ll sum = 0;
	rep(i,N) if( i-1 >= N-1-i ){
	//	ll tmp = fib(N,i);
		ll tmp = cmb(i-1, N-1-i);
		tmp = (tmp * fact[i]) % MOD;
		tmp = (tmp * fact[N-1-i]) % MOD;
		tmp = (tmp + MOD - sum) % MOD;
		sum = (sum + tmp) % MOD;
		tmp = (tmp * i) % MOD;
		ans = (ans + tmp) % MOD;
		//cout << ans << " " << cmb(i-1, N-1-i) << " " << fact[i] << endl;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};


int main() {
  int n, m;
  cin >> n >> m;

  UnionFind uf(n);
  int a, b;

  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    uf.unite(a, b);
  }
  int ans=0;

  for (int i = 0; i < n; i++) {
    ans = max(ans, uf.size(i));
  }

  cout << ans << endl;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace __gnu_pbds;
using namespace std;
/*
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
*/
#define ull unsigned long long int
#define ll long long int
#define MAX 1000000007
//1e9+7
#define pll pair<ll,ll>
#define pii pair<int,int>
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FO ifstream fin("a.in");ofstream fout("a.out");
#define TEST int testcase;cin>>testcase;while(testcase--)
#define all(x) (x).begin(),(x).end()
#define mset0(x) memset((x), 0, sizeof((x)));
#define mset1(x) memset((x), -1, sizeof((x)));
#define endl "\n"
typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
int fa[301],sizes[301];
int root(int node){
    while(node!=fa[node]){
        fa[node]=fa[fa[node]];
        node=fa[node];
    }
    return(node);
}
void link(int i,int j){
    i=root(i);j=root(j);
    if(i==j) return;
    if(sizes[i]>sizes[j]) swap(i,j);
    sizes[j]+=sizes[i];
    fa[i]=j;
    return;
}
void solve(){
    int n,cnt=0;
    cin>>n;
    ll arr[n];
    for(int i=0;i<n;i++) {
        cin>>arr[i];
        if(arr[i]<=0) cnt++;
        arr[i]=abs(arr[i]);
    }
    sort(arr,arr+n);
    ll sum=0;

    if(cnt%2) sum-=arr[0];
    else sum+=arr[0];
    for(int i=1;i<n;i++){
        sum+=arr[i];
    }
    cout<<sum;
    return;
}
int main(){
    IO
    //TEST
    solve();
    return(0);
}


Measured memory_bytes: 1024
"""
有向グラフ, シフト演算
"""

n = int(input())

g = [[0]*15 for i in range(15)]

for i in range(n):
    for j in range(n):
        g[i][j] = -1 # 何も証言されていない状態を-1。入力(1or0)があればその値を代入
for i in range(n):
    m = int(input())
    for j in range(m):
        a, x = map(int, input().split())
        a -= 1
        g[i][a] = x

ans = 0
for i in range(1<<n):
    d = [0]*n
    for j in range(n):
        if i>>j&1: # iのj桁目が1か
            d[j] = 1
    ok = True
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1: continue
                if g[j][k] != d[k]: ok = False
    if ok: ans = max(ans, bin(i).count('1'))

print(ans)

Measured memory_bytes: 44380
import bisect,collections,copy,heapq,itertools,math,string
import sys
import random
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
d = I()
c_l = LI()
s_l = [LI() for _ in range(d)]
for i in range(d):
    print(s_l[i].index(max(s_l[i]))+1)

Measured memory_bytes: 77932
def solve():

    K = int(input())
    A, B = map(int, input().split())

    i = 0

    while True:
        if A <= i <= B:
            print("OK")
            exit()
        elif B < i:
            print("NG")
            exit()

        i += K


if __name__ == "__main__":
    solve()


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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v),end()
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;

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

string str="yuiophjklnm";
int A[26];

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

    REP(i,str.size()) A[str[i]-'a']=1;

    while(true)
    {
        string s; cin>>s;
        if(s[0]=='#') break;

        int ans=0;
        REP(i,s.size()-1){
            if(A[s[i]-'a']!=A[s[i+1]-'a']) ans++;
        }
        cout<<ans<<endl;
    } 

}

Measured memory_bytes: 3244
#!/usr/bin/env python3
import numpy as np


DEBUG = True
dprint = print if DEBUG else lambda *x : x

N = int(input().strip())
P = [int(str) for str in input().strip().split()]

minnum = P[0]
ans = 0
for i in P:
    if i <= minnum:
        minnum = i
        ans += 1

print(ans)

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

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

const ll MRINF = 5000000000000000;

int main() {

  string N;
  cin >> N;
  int ans = 0;

  REP(i, N.length()){
    if(N[i]=='2')ans++;
  }

  cout << ans << endl;


}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

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

template <class T>
struct Primal_Dual {
  using Pa = pair<T, int>;
  long long infinity = (long long)(1e14);
  struct edge {
    int to;
    T cap, cost;
    int rev;
  };
  int v;
  vector<vector<edge>> edges;
  vector<T> h;
  vector<T> dist;
  vector<int> prevv, preve;
  Primal_Dual(int vsize = 1) {
    v = vsize;
    edges.resize(v);
    h.resize(v);
    dist.resize(v);
    prevv.resize(v);
    preve.resize(v);
  }
  bool add(int from, int to, T cap, T cost) {
    edges[from].push_back((edge){to, cap, cost, (int)edges[to].size()});
    edges[to].push_back((edge){from, 0, -cost, (int)edges[from].size() - 1});
    return 1;
  }
  T solve(int s, int t, T f) {
    T ans = 0;
    h.assign(v, 0);
    while (f > 0) {
      priority_queue<Pa, vector<Pa>, greater<Pa>> qu;
      dist.assign(v, infinity);
      dist[s] = 0;
      qu.push({0, s});
      while (!qu.empty()) {
        Pa now = qu.top();
        qu.pop();
        int nowv = now.second;
        if (dist[nowv] < now.first) continue;
        for (int i = 0; i < (int)edges[nowv].size(); ++i) {
          edge &e = edges[nowv][i];
          if (e.cap > 0 &&
              dist[e.to] > dist[nowv] + e.cost + h[nowv] - h[e.to]) {
            dist[e.to] = dist[nowv] + e.cost + h[nowv] - h[e.to];
            prevv[e.to] = nowv;
            preve[e.to] = i;
            qu.push({dist[e.to], e.to});
          }
        }
      }
      if (dist[t] == infinity) return -1;
      for (int i = 0; i < v; ++i) h[i] += dist[i];
      T d = f;
      for (int i = t; i != s; i = prevv[i])
        d = min(d, edges[prevv[i]][preve[i]].cap);
      f -= d;
      ans += d * h[t];
      for (int i = t; i != s; i = prevv[i]) {
        edge &e = edges[prevv[i]][preve[i]];
        e.cap -= d;
        edges[i][e.rev].cap += d;
      }
    }
    return ans;
  }
};

long long n, sum = 0;
vector<long long> a, b, v;
Primal_Dual<long long> pd;

int main() {
  cin >> n;
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
    v.push_back(a[i]);
    v.push_back(b[i]);
    sum += a[i] + b[i];
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  int len = v.size();
  pd = Primal_Dual<long long>(n + 2 + len);
  for (int i = 0; i < len; ++i) pd.add(n + i, n + len + 1, 1, 0);
  for (int i = 0; i < n; ++i) {
    pd.add(n + len, i, 1, 0);
    pd.add(i, n + len + 1, 1, a[i] + b[i]);
    pd.add(i, n + lower_bound(v.begin(), v.end(), a[i]) - v.begin(), 1, a[i]);
    pd.add(i, n + lower_bound(v.begin(), v.end(), b[i]) - v.begin(), 1, b[i]);
  }
  cout << sum - pd.solve(n + len, n + len + 1, n) << endl;
  return 0;
}



Measured memory_bytes: 3696
#include<iostream>
#include<algorithm>
using namespace std;
int N_MAX=100001;
int main()
{
  int n,m,k,i,j;
  int f[N_MAX];
  int c[N_MAX]; // 頂点iの属する集合番号
  int nc[N_MAX]; // 集合jの要素数
  int pc[N_MAX]; // 集合jの先頭の要素番号
  int pi[N_MAX]; // 頂点iと同じ集合の要素へのポインタ
  int res[N_MAX];
  int i1,i2,s1,s2,p,pt;
  int c1,c2;
  cin >> n >> m >> k;
  for(i=1;i<=n;i++){
    c[i]=i;
    nc[i]=1;
    pc[i]=i;
    pi[i]=0;
  }
  fill(f,f+n,0);
  for(i=0;i<m;i++){
    cin >> i1 >> i2;
    f[i1]++;
    f[i2]++;
    if(c[i1]!=c[i2]){
// 集合のマージここから
      s1=c[i1]; s2=c[i2];
      if(nc[s1]<nc[s2]){// 小さい方を潰す【重要】
        s1=c[i2]; s2=c[i1];
      }
      pt=pc[s1];
      p=pc[s2];
      pc[s1]=p;
      nc[s1]+=nc[s2];
      pc[s2]=0;
      nc[s2]=0;
      while(true){
        c[p]=s1;
        if(pi[p]==0) break;
        p=pi[p];
      }
      pi[p]=pt;
// 集合のマージここまで
    }
  }
  for(i=1;i<=n;i++)
    res[i]=nc[c[i]]-1-f[i];
  for(i=0;i<k;i++){
    cin >> i1 >> i2;
    if(c[i1]==c[i2]){
      res[i1]--;
      res[i2]--;
    }
  }
  for(i=1;i<=n;i++)
    cout << res[i] << " ";
  cout << endl;
  return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++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; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second
// 多倍長
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using boost::rational;
using boost::multiprecision::cpp_int;

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;


int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    rep(i, n) cin >> a[i] >> b[i];
    sort(all(a));
    sort(all(b));
    if(n % 2 != 0){
        ll ans = b[n / 2] - a[n / 2] + 1;
        print(ans);
    } else {
        ll ans = b[n / 2 - 1] + b[n / 2] - (a[n / 2 - 1] + a[n / 2]) + 1;
        print(ans);
    }

}




Measured memory_bytes: 6356
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

using ull = unsigned long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vull = vector<ull>;
using vpii = vector<pii>;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(b);i>=(a);i--)
#define SORT(a) sort((a).begin(),(a).end());
#define rSORT(a) sort((a).rbegin(),(a).rend());
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;

//sankou
//vvi = vector<vector<int>>(20, vector<int>(10, 0));

int isP(int n) {
    if(n<=1) return 0;
    FOR(i,2,(int)sqrt(n)) {
        if(n%i==0) return 0;
    }
    return 1;
}

int main() {
    
    int A,B;
    cin >>A>>B;
    A=(A+11)%13;
    B=(B+11)%13;
    
    if(A>B) cout <<"Alice";
    if(A==B) cout <<"Draw";
    if(A<B) cout <<"Bob";

    return 0;
}

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

string S, T;
int Q, sumS[100005], sumT[100005];

int main() {
	
	cin >> S >> T;
	scanf("%d", &Q);
	int cur = 0;
	for (int i = 0; i < S.length(); i++) {
		cur += (S[i] == 'A');
		sumS[i] = cur;
	}
	cur = 0;
	for (int i = 0; i < T.length(); i++) {
		cur += (T[i] == 'A');
		sumT[i] = cur;
	}
	while (Q--) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;
		b--;
		c--;
		d--;
		int A1 = sumS[b] - ((a == 0) ? 0 : sumS[a - 1]);
		int B1 = b - a + 1 - A1;
		int A2 = sumT[d] - ((c == 0) ? 0 : sumT[c - 1]);
		int B2 = d - c + 1 - A2;
		if ((A1 * 2 + B1) % 3 == (A2 * 2 + B2) % 3 || (A1 + B1 * 2) % 3 == (A2 + B2 * 2) % 3) printf("YES\n");
		else printf("NO\n");
	}
}


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

int main() {
  int k,a;
  cin>>k;
  a=0;
for(int i=1;i<k+1;i++){
for(int j=1;j<k+1;j++){
for(int l=1;l<k+1;l++){
a+=gcd(gcd(i,j),l);
}}}  
  cout<<a<<endl;
}

Measured memory_bytes: 3636
H,W=map(int,input().split())
Map=[input() for i in range(H)]
Base1,Base2=[],[]
for i in range(H):
  if i%2==0:
    Base1.append(["#"]*(W-1)+["."])
    Base2.append(["."]*(W-1)+["#"])
  elif i%2==1:
    Base1.append(["#"]+["."]*(W-1))
    Base2.append(["."]+["#"]*(W-1))
for i in range(H):
  for j in range(W):
    if Map[i][j]=="#":
      Base1[i][j],Base2[i][j]="#","#"
for i in range(H):
  print("".join(Base1[i]))
print()
for i in range(H):
  print("".join(Base2[i]))

          
                       

Measured memory_bytes: 46320
#include <iostream>

using namespace std;

int Q;
long long int x[100005], d[100005], n[100005];
long long int MOD = 1000003;

long long int C[1000006];

long long int POW(long long int K, long long int p) {
	if (p == 0) { return K; }

	if (p == 1) { return K; }

	if ((p % 2) == 1) { return (POW(K, p - 1)*K) % MOD; }

	long long int tmp = POW(K, p / 2);

	return (tmp*tmp) % MOD;
}

long long int INV(long long int K) {
	return POW(K, MOD - 2);
}


int main(void) {

	cin >> Q;

	for (int i = 1; i <= Q; i++) {
		cin >> x[i] >> d[i] >> n[i];
	}

	C[1] = 1;
	for (int i = 2; i <= MOD; i++) {
		C[i] = (C[i - 1] * ((long long int)i)) % MOD;
	}

	for (int i = 1; i <= Q; i++) {

		if (d[i] == 0) { 
			cout << POW(x[i], n[i]) % MOD << endl; continue;
		}

		int H = (int) ((x[i] * INV(d[i]))%MOD);
		//cout << "H= " << H << "  " << (H*d[i]) %MOD<<endl;

		if ((n[i]>=MOD) || (n[i]+H - 1 >= MOD)) { cout << 0 << endl; }
		else {
			long long int val = C[(int) (n[i] - 1)+H] * INV(C[H - 1]);
			val %= MOD;
			val *= POW(d[i], n[i]);
			val %= MOD;
			cout << val << endl;
		}
	}

	
	return 0;
}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	int size=s.size();
	int ans=0;
	for(int i=1;i<size;i++){
		if(s[i]!=s[i-1]){
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
L = [[int(x) for x in input().split()] for _ in range(M)]

reg = min(a) + min(b)
for x, y, c in L:
    tmp = a[x-1] + b[y-1] - c
    reg = min(reg, tmp)
print(reg)

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

int main(){
  int H, W, M;
  cin >> H >> W >> M;
  vector<pair<int, int>>hcnt(H), wcnt(W);
  for(int i=0; i<H; i++)hcnt[i]=make_pair(0, i);
  for(int i=0; i<W; i++)wcnt[i]=make_pair(0, i);
  vector<pair<int, int>>hw(M);
  for(int i=0; i<M; i++){
    cin >> hw[i].first >> hw[i].second;
    hw[i].first--;
    hw[i].second--;
    hcnt[hw[i].first].first++;
    wcnt[hw[i].second].first++;
  }
  sort(hcnt.rbegin(), hcnt.rend());
  sort(wcnt.rbegin(), wcnt.rend());
  vector<bool>h_ismax(H, false), w_ismax(W, false);
  
  int hmaxc=0, wmaxc=0;
  for(int i=0; i<H; i++){
    if(hcnt[i].first < hcnt[0].first)break;
    h_ismax[hcnt[i].second]=true;
    hmaxc++;
  }
  for(int i=0; i<W; i++){
    if(wcnt[i].first < wcnt[0].first)break;
    w_ismax[wcnt[i].second]=true;
    wmaxc++;
  }
  
  long maxmcnt = 0; // maxの交点にある爆破対象の数
  for(int i=0; i<M; i++){
    if(h_ismax[hw[i].first] && w_ismax[hw[i].second])maxmcnt++;
  }
  int ret = hcnt[0].first+wcnt[0].first;
  if(maxmcnt<long(hmaxc)*long(wmaxc))cout << ret << endl;
  else cout << ret-1 << endl;
  return 0;
}

Measured memory_bytes: 10020
h, w, k = list(map(int, input().split()))

grid = []
for _ in range(h):
  row = input()
  grid.append(row)
  
res = 0  
for maskR in range(1 << h):
  for maskC in range(1 << w):
    black = 0
    for i in range(h):
      for j in range(w):
        if ((maskR >> i) & 1) == 0 and ((maskC >> j) & 1) == 0 and grid[i][j] == '#':
          black += 1
    if black == k:
      res += 1
      
print(res)

Measured memory_bytes: 9112
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int a,b; char op; cin >> a >> op >> b;
    if (op == '+') cout << a+b << endl;
    else cout << a-b << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N = int(input())
    C, S, F = [], [], []
    for _ in range(N - 1):
        c, s, f = map(int, input().split())
        C.append(c)
        S.append(s)
        F.append(f)

    for i in range(N):
        now = 0
        for j in range(i, N - 1):
            if S[j] > now:
                now += S[j] - now

            t = ceil(now / F[j])
            now += (F[j] * t) - now
            now += C[j]
        print(now)


if __name__ == '__main__':
    main()


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


int main(){
//    cout << fixed << setprecision(10);
    
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> S = vector<string>(H, "");
    vector< vector<int> > isWhite;

    for (int i = 0; i < H; i++) {
        cin >> S[i];
        vector<int> row;
        for (int j = 0; j < W; j++) {
            row.push_back(S[i][j] == '1' ? 1 : 0);
        }
        isWhite.push_back(row);
    }
    
    int minmin = 999999;
    for (int z = 0; z < (1 << (H-1)); z++) {
        int minOk = 0;
        vector<int> m = vector<int>(H, 0);
        int index = 0;
        for (int zz = 0; zz < (H-1); zz++) {
            if ((z & (1 << zz)) > 0) {
                index++;
                minOk++;
            }
            m[zz+1] = index;
        }
    
        vector<int> current = vector<int>(H, 0);
        for (int i = 0; i < H; i++) {
            current[m[i]] += isWhite[i][0];
        }
        
        vector<int> row = vector<int>(H, 0);
        for (int i = 1; i < W; i++) {
            for (int j = 0; j < H; j++) {
                row[j] = 0;
            }
            for (int j = 0; j < H; j++) {
                row[m[j]] += isWhite[j][i];
            }
            
            for (int j = 0; j < H; j++) {
                if (row[j] > K) {
                    minOk = 999999;
                    break;
                }
                current[j] += row[j];
            }
            bool isOk = true;
            for (int j = 0; j < H; j++) {
                if (current[j] > K) {
                    isOk = false;
                }
            }
            if (!isOk) {
                current = row;
                minOk++;
            }
        }
        
        if (minmin > minOk) {
            minmin = minOk;
        }
    }
    
    cout << minmin;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int k[10];
int s[10][10];
int p[10];

bool state[10];
int N, M;

int search(int cur)
{
    if (cur == N) {
        REP(i, M) {
            int nOn = 0;
            REP(j, k[i]) if (state[s[i][j] - 1]) nOn++;
            if (nOn % 2 != p[i]) return 0;
        }
        return 1;
    }
    else {
        // on
        state[cur] = true;
        int c1 = search(cur + 1);
        // off
        state[cur] = false;
        int c2 = search(cur + 1);
        return c1 + c2;
    }
}


int main(int argc, char **argv)
{
    cin >> N >> M;
    REP(i, M) {
        cin >> k[i];
        REP(j, k[i]) cin >> s[i][j];
    }
    REP(i, M) cin >> p[i];

    REP(i, 10) state[i] = false;
    cout << search(0) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <climits>
#include <functional>
#include <queue>
#include <cmath>
#include <utility>
 
using namespace std;
 
#define int long long
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rep1(i,n) for(int i=1;i<=(int)n;++i)
 
int N;
int a[300010];
int scoreL[100010], scoreR[100010];
 
signed main()
{
	cin >> N;
 
	rep(i, N*3) cin >> a[i];
 
	priority_queue<int, vector<int>, greater<int>> L;
	priority_queue<int> R;
 
	int sumL = 0, sumR = 0;
	for (int i = 0; i < N; ++i) {
		L.push(a[i]);
		sumL += a[i];
	}
	for (int i = N * 2; i < N * 3; ++i) {
		R.push(a[i]);
		sumR += a[i];
	}
 
	scoreL[0] = sumL;
	scoreR[0] = sumR;
	int l = N, r = N * 2 - 1;
	for (int i = 1; i <= N; ++i) {
      	sumL += a[l];
		L.push(a[l]);
		sumL -= L.top(); L.pop();
		scoreL[i] = sumL;
 		sumR += a[r];
		R.push(a[r]);
		sumR -= R.top(); R.pop();
		scoreR[i] = sumR;
 
		l++, r--;
	}
 
	int ans = -(LLONG_MAX/2);
 
	for (int i = 0; i <= N; ++i) {
		ans = max(ans, scoreL[i] - scoreR[N-i]);
	}
 
	cout << ans << endl;
}


Measured memory_bytes: 5876
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int N=26;
int D;
vector<int> c(N);
vector<vector<int>> s;

lint calc_score(vector<int> &t){
  lint ans=0;
  int last[N];
  REP(n,N)last[n]=-1;
  REP(d,D){
    ans+=s[d][t[d]];
    last[t[d]]=d;
    REP(n,N)ans-=c[n]*(d-last[n]);
  }
  return ans;
}

int main(){
  cin>>D;
  REP(i,N)cin>>c[i];
  REP(d,D){
    vector<int> v(N);
    REP(n,N)cin>>v[n];
    s.push_back(v);
  }
  int last[N];
  REP(n,N)last[n]=-1;
  vector<int> ans;
  lint score=0;
  REP(d,D){
    int arg_max=0;
    lint max_score=-1e9;
    lint S=0;
    REP(i,N){
      S-=c[i]*(d-last[i]);
    }
    REP(i,N){
      lint temp=c[i]*(d-last[i])+s[d][i];
      if(temp>max_score){
        max_score=temp;
        arg_max=i;
      }
    }
    score+=S+max_score;
    last[arg_max]=d;
    ans.push_back(arg_max);
  }
  for(auto e:ans)cout<<e+1<<endl;
  // cerr<<score<<" "<<calc_score(ans)<<endl;
  return 0;
}


Measured memory_bytes: 3664
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, c = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(n)]
    R1, R2 = [0], [0]
    max1, max2 = [0], [0]
    ma = 0
    prev = 0
    for x, y in XY:
        R1.append(R1[-1] + y - (x - prev))
        prev = x
        if ma < R1[-1]:
            ma = R1[-1]
        max1.append(ma)

    ma = 0
    prev = 0
    for x, y in XY[::-1]:
        R2.append(R2[-1] + y - ((c - x) - prev))
        prev = (c - x)
        if ma < R2[-1]:
            ma = R2[-1]
        max2.append(ma)

    res = max(max(R1), max(R2))
    for i in range(1, n + 1):
        point1 = R1[i] - XY[i - 1][0] + max2[n - i]
        point2 = R2[i] - (c - XY[-i][0]) + max1[n - i]
        res = max(res, point1, point2)
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 39672
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;

int cnt;
vector<int> G;

void insertionSort(vector<int> &A, int n, int g) {
  for (int i = g; i < n; i++) {
    int v = A.at(i);
    int j = i - g;

    while (j >= 0 && A.at(j) > v) {
      A.at(j + g) = A.at(j);
      j -= g;
      cnt++;
    }
    A.at(j + g) = v;
  }
}

void shellSort(vector<int> &A, int n) {
  cnt = 0;
  
  // 数列G = {1, 4, 12, 40, 121, 364, 1093, ...} を生成
  int h = 1;
  while (h <= n) {
    G.push_back(h);
    h = 3 * h + 1;
  }
  int m = G.size();
  for (int i = m - 1; i >= 0; i--) {
    insertionSort(A, n, G.at(i));
  }
}

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

  vector<int> A(n);
  rep (i, n) cin >> A.at(i);

  shellSort(A, n);

  cout << G.size() << endl;
  for (int i = G.size() - 1; i >= 0; i--) {
    cout << G.at(i);
    if (i > 0) cout << " ";
  }
  cout << endl;
  cout << cnt << endl;
  rep (i, n) cout << A.at(i) << endl;

  return 0;
}


Measured memory_bytes: 6732
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_temp>
using smaller_queue = priority_queue<Q_temp, vector<Q_temp>, greater<Q_temp>>;

const ll MOD = (ll)(1e9 + 7);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << setiosflags(ios::fixed);
  int n;
  cin >> n;
  string s[50];
  int t[50];
  rep(i, n)
  {
    cin >> s[i] >> t[i];
  }
  string x;
  cin >> x;
  bool conti = true;
  int sum = 0;
  rep(i, n)
  {
    if (conti)
    {
      if (s[i] == x)
        conti = false;
      continue;
    }
    sum += t[i];
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

        int appleNum = sc.nextInt();
        int sight = sc.nextInt() * 2 + 1;

        int ans = (int)Math.ceil((double)appleNum / (double)sight);

        System.out.println(ans);
    }
}

Measured memory_bytes: 24020
#include<bits/stdc++.h>
#define INF 2000000000
#define int long long int
#define MOD 1000000007
#define pb push_back
#define cin1(n) (cin >> n)
#define cin2(a,b) (cin >> a >> b)
#define cin3(a,b,c) (cin >> a >> b >> c)
#define cout(n) (cout << n << endl)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define fr first 
#define sc second 
#define EPS (1e-10)

using namespace std;

typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector<pair<int,int>> vpii;
typedef vector<string> vs;
typedef vector<vector<string>> vss;
typedef pair<int,int> pii;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n,m;
int a,b;
int p,q;


signed main() {
	
	while(1) {
		cin2(n,m);
		if (n + m == 0) break;

		vi p(n,0);
		rep(i,0,n) {
			cin1(p[i]);
		}
		p.pb(0);

		rep(i,0,n) {
			rep(j,0,n) {
				if (p[i] + p[j] <= m) { 
					p.pb(p[i] + p[j]);	
				}
			}
		}
		sort(p.begin(),p.end());

		int size = p.size();

		int ans = 0;
		rep(i,0,size) {
			int c_d = p[i];
			int a_b = *(upper_bound(p.begin(),p.end(),m - c_d) - 1);
			ans = max(ans,a_b + c_d);
		}
		cout(ans);
	}



	return 0;
}

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

using namespace std;

const int P = 1000000007;

long long power(long long x, long long t) {
	long long ret = 1;
	for(; t; t >>= 1, x = x * x % P) {
		if(t & 1) {
			ret = ret * x % P;
		}
	}
	return ret;
}

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

	int n;
	cin >> n;

	vector<long long> a(n);
	vector<long long> b(n);

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

	map<pair<long long, long long>, int> mp;

	int cnt = 0;

	for(int i = 0; i < n; ++i) {
		long long A, B;
		A = a[i];
		B = b[i];
		long long d = __gcd(A, B);
		if(d == 0) {
			++cnt;
			continue;
		}
		A /= d;
		B /= d;
		if(A < 0) {
			A = -A;
			B = -B;
		}
		++mp[{ A, B }];
	}	

	map<pair<long long, long long>, bool> vis;

	long long ans = 1;

	for(auto it : mp) {
		auto o = it.first;
		long long A = o.first;
		long long B = o.second;
		if(vis.count({ A, B })) {
			continue;
		}
		long long d = power(2, mp[{ A, B }]);
		B = -B;
		if(B < 0) {
			B = -B;
			A = -A;
		}
		pair<long long, long long> v = { B, A }; 
		if(mp.count(v)) {
			d = (d + power(2, mp[v]) - 1) % P;
			vis[v] = true;
		}

		ans = ans * d % P;
	}

	cout << (ans - 1 + cnt + P) % P << '\n';

	return 0;
}


Measured memory_bytes: 18752
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n);i++)
using namespace std;
int main(void){
   int n;
   cin >> n;
   string s;
   map<string,int> mp;
   rep(i,n) {
       cin >> s;
       mp[s]++;
   }
   int mx = 0;
   for(auto p:mp) mx = max(mx,p.second);
   for(auto p:mp) {
       if(p.second != mx) continue;
       cout << p.first << endl;
   }
   
}


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

#define int long long
#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define endl "\n"
#define ends " "
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
#define debugV(v) cerr << #v << ": [ "; for(int __ = 0; __ < v.size(); __++) cerr << v[__] << ((__ != v.size() - 1) ? ", " : ends); cerr << ']' << endl
#define debugVP(v) cerr << #v << ": [ "; for(int ___ = 0; ___ < v.size(); ___++) cerr << '{' << v[___].first << ", " << v[___].second << '}' << ((___ != v.size() - 1) ? ", " : ends); cerr << ']' << endl
#define debugA(a, n) cerr << #a << ": [ "; for(int ____ = 0; ____ < n; ____++) cerr << a[____] << ((____ != n - 1) ? ", " : ends); cerr << ']' << endl
#define print(args...) fprintf (stderr, args)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int INF = 1e9, MOD = INF + 7;

/////////////////////////////////////////////////////////////////////

const int N = 4e2 + 20;

int a[N];
int dp[N][N];
int ps[N];

int sum(int l, int r) { return ps[r] - ps[l - 1]; }

int32_t main(){

    sync;

    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];
    for(int l = n; l >= 1; l--) for(int r = l + 1; r <= n; r++) {
    	dp[l][r] = INF * INF;
    	for(int i = l; i < r; i++) dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r] + sum(l, i) + sum(i + 1, r));
    }
	cout << dp[1][n] << endl;

    return 0;
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int N; cin >> N;
    string S; cin >> S;
    VI west(N), east(N);
    west[0] = 0; east[N-1] = 0;
    REP(i,N-1){
        west[i+1] = S[i]=='W' ? west[i]+1 : west[i];
        east[N-2-i] = S[N-1-i]=='E' ? east[N-1-i]+1 : east[N-1-i];
    }
    int ans = INT_INF;
    REP(i,N) chmin(ans, east[i]+west[i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3076
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

s = ins()
t = ins()
ls = len(s)
lt = len(t)
mn = BIG
for i in range(ls-lt+1):
    x = 0
    for j in range(lt):
        if s[i+j]!=t[j]:
            x += 1
    mn = min(mn,x)
print(mn)


Measured memory_bytes: 9048
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <tuple>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repd(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repdm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)
const ll INF = 1LL << 60;
const ll ZERO = 0;

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

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

int N;
ll dp[100010][3];
ll a[100010][3];
ll ans = 0;

int main()
{
  int N;
  cin >> N;
  rep(i, N)
  {
    rep(j, 3)
    {
      cin >> a[i][j];
    }
  }

  rep(i, N)
  {
    rep(j, 3)
    {
      rep(k, 3)
      {
        if (j == k)
          continue;
        chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
      }
    }
  }

  ll res = 0;
  rep(j, 3) chmax(res, dp[N][j]);
  cout << res << endl;
}

Measured memory_bytes: 4992
# coding: utf-8
# Your code here!
num = int(raw_input())
li = list(map(int,raw_input().split()))
count = 0
while True:
    li = list(filter(lambda x:x%2 ==0,li))
    count += len(li)
    if len(li) == 0:
        break
    li = list(map(lambda x: x/2,li))
print count

Measured memory_bytes: 3460
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;


ll n, k;
ll a[500];

bool f(ll div) {
    ll b[n];
    for (int i = 0; i < n; i++) {
        b[i] = a[i] % div;
    }

    sort(b, b + n);
    for (int i = 1; i < n; i++) {
        b[i] += b[i - 1];
    }

    for (int i = 0; i < n; i++) {
        if (b[i] == (n - 1 - i) * div - (b[n - 1] - b[i]) && b[i] <= k) {
            return true;
        }
    }

    return false;
}



int main() {
//    cout << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll ans = 0;
    ll sum = accumulate(a, a + n, (ll) 0);

    for (ll div = 1; div * div <= sum; div++) {
        if (f(div)) {
            ans = max(ans, div);
        }

        if (f(sum / div)) {
            ans = max(ans, sum / div);
        }
    }

    cout << ans;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 2000000001;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

int main() {
    int N,M;
    cin >> N >> M;
    vector<bool> broke(N + 1);
    for(int i = 0;i < M;i++) {
        int A;
        cin >> A;
        broke.at(A) = true;
    }
    vector<ll> vec(N + 1);
    vec.at(0) = 1;
    if(broke.at(1) == false) {
        vec.at(1) = 1;
    }
    for(int i = 2;i < N + 1;i++) {
        if(broke.at(i) == true) {
            continue;
        }
        else {
            if(i == 1) {
                vec.at(i) += vec.at(i - 1);
            }
            else {
                vec.at(i) += vec.at(i - 1);
                vec.at(i) += vec.at(i - 2);
            }
            vec.at(i) %= MOD;
        }
    }
    cout << vec.at(N) << endl;
}

Measured memory_bytes: 1024
t_h,t_a,a_h,a_a=[int(i) for i in input().split()]

if t_a >= a_h:
  print('Yes')
  exit()
if t_h <= a_a:
  print('No')
  exit()

if a_h%t_a == 0:
  t_t = int(a_h/t_a)
else:
  t_t = int(a_h/t_a) + 1
  
if t_h%a_a == 0:
  a_t = int(t_h/a_a)
else:
  a_t = int(t_h/a_a) + 1

if t_t <= a_t:
  print('Yes')
else:
  print('No')

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

using namespace std;

int n;

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

    cin >> n;
    int mx = -1e9, sum = 0;
    for(int i = 0; i < n; i++)
    {
        int l;
        cin >> l;
        mx = max(mx, l);
        sum += l;
    }

    if(mx < sum - mx)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}


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

using namespace std;

int d[10][10];
int n;
string ms;
int ml;
string s[10];

void dfs(int l,int sz,int u,vector<int> v){
  if(u==(1<<n)-1){
    string t;
    if(sz<=ml){
      t=s[v[0]];
      for(int i=1;i<v.size();i++){
	t+=s[v[i]].substr(s[v[i]].size()-d[v[i-1]][v[i]]);
      }
    }
    if(sz<ml||sz==ml&&t<ms){
      ml=sz;
      ms=t;
    }
  }else{
    v.push_back(0);
    for(int i=0;i<n;i++){
      if(!(u>>i&1)){
	v.back()=i;
	dfs(i,sz+d[l][i],u|1<<i,v);
      }
    }
  }
}

int main(){
  while(cin>>n,n){
    for(int i=0;i<n;i++){
      cin>>s[i];
    }
    int u=0;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(i!=j){
	  if(!(u>>i&1)&&s[i].find(s[j])!=string::npos){
	    u|=1<<j;
	  }else{
	    int k;
	    for(k=min(s[i].size(),s[j].size());;k--){
	      if(s[i].compare(s[i].size()-k,k,s[j],0,k)==0)break;
	    }
	    d[i][j]=s[j].size()-k;
	  }
	}
      }
    }
    ml=1<<30;
    for(int i=0;i<n;i++){
      dfs(i,s[i].size(),u|1<<i,vector<int>(1,i));
    }
    cout<<ms<<endl;
  }
  return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long n,h,w;
    cin>>n>>h;
    w=n+h;
    if(w%3!=0 && n%3!=0 && h%3!=0) cout<<"Impossible"<<endl;
    else  cout<<"Possible"<<endl;


  return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  int n,d,x;
  cin >> n >> d >> x;
  rep(i,n){
    int a;
    cin >> a;
 	x += 1 +(d-1)/a;    
  }
  cout << x << endl;


  
  
  return 0;
    

}


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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < (Int)n; i++) {
        cin >> a[i];
    }
    Int res = 0;
    for (Int i = 0; i < (Int)a.size(); i++) {
        if (i % 2 == 0 and a[i] % 2 == 1) res++;
    }
    print(res);
    return 0;
}

Measured memory_bytes: 3600
#include<stdio.h>
#include<stdlib.h>
#define gc() getchar()
typedef unsigned long long ull;
int in() {   // 非負整数の入力
	int n = 0; int c;
	c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}
int comp(const void* a, const void* b)//用来做比较的函数。
{
	return *(int*)a - *(int*)b;
}
int main()
{
	int a, b, c;
	a = in(), b = in(), c = in();
	printf("%d %d %d", c, a, b);
}

Measured memory_bytes: 128
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << x << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

int main() {
    int t, n;

    while (~scanf("%d", &t)) {
        if (t == 0) break;
        scanf("%d", &n);
        int cnt = 0;
        int s, f;

        REP (i, n) {
            scanf("%d%d", &s, &f);
            cnt += f - s;
        }

        if (cnt >= t) OUT("OK");
        else OUT(t - cnt);
    }

    return 0;
}



Measured memory_bytes: 3132
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll N,M,Q;
vector<ll>a,b,c,d;
ll score(const vector<ll>&A){
  ll res=0;
  for(ll i=0;i<Q;i++){
    if(A[b[i]]-A[a[i]]==c[i])res+=d[i];
  }
  return res;
}
ll dfs(vector<ll>&A){
  if(A.size()==N){
    return score(A);
  }
  ll res=0;
  ll prev_back=(A.empty()?0:A.back());
  for(ll i=prev_back;i<M;i++){
    A.push_back(i);
    res=max(res,dfs(A));
    A.pop_back();
  }
  return res;
}
int main(){
  cin>>N>>M>>Q;
  a.resize(Q),b.resize(Q),c.resize(Q),d.resize(Q);
  for(ll i=0;i<Q;i++){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
    a[i]--,b[i]--;
  }
  vector<ll>A;
  cout<<dfs(A)<<endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,a,b,c,d ;
  cin >> N ;

  a = N / 1000;
  b = (N / 100 ) % 10;
  c = (N / 10) % 10;
  d = N % 10;
     
  if (a == b && a == c) {
    cout << "Yes" << endl;
  } else if (d == b && d == c) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define ALL(v) v.begin(), v.end()
#define N 100007
#define INF 1000000007
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll fceil(ll a, ll b) { return (a % b == 0 ? a / b : a / b + 1); }
int main()
{
   int n, ans = 0;
   cin >> n;
   vector<int> a(n, 0);
   for (int i = 0; i < n; i++)
   {
      cin >> a[i];
      int tmp = a[i];
      while (tmp % 2 == 0)
      {
         ans++;
         tmp = tmp >> 1;
      }
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256