akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#define ALL(a) (a).begin(),(a).end()

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;
 
	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}
 
	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}
 
	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい]
	}
 
	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}
 
		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);
 
		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;
 
		return true;
	}
};




long long fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 510000; 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() {
  // 前処理
  COMinit();

  ll N,K;
  cin>>N>>K;



  cout<<N-K+1<<endl;

  return 0;
 
}


Measured memory_bytes: 12160
a, b, c, d = map(int,input().split())

timer = 0
both_push_time = 0
for t in range(101):
    if t < a or t < c:
        continue
    elif a <= t < b and c <= t < d: #b or d秒後にはスイッチを離す
        timer += 1
    else:
        break

print(timer)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<queue>
using namespace std;

typedef long long ll;

int main() {
  string t; cin >> t;
  int a[4];
  for ( int i = 0; i < 4; i++ ) a[i] = t[i] -'0';
  for ( int x = 0; x < (1<<3);  x++ ) {
    int sum = a[0];
    string s;
    s += (char)('0'+a[0]);
    for ( int i = 0; i < 3; i++ ) {
      if ( x & (1<<i) ) {
	sum += a[i+1];
	s += '+';
	s += (char)('0'+a[i+1]);
      } else {
	sum -= a[i+1];
	s += '-';
	s += (char)('0'+a[i+1]);
      }
    }
    if ( sum == 7 ) {
      cout << s << "=7" << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
X,K,D = map(int, input().split())
Ans = 0

if abs(X) >= K * D:
  if X >= 0:
    Ans = X - (K * D)
  else:
    Ans = abs(X + (K * D))
    
else:
  abX = abs(X)
#  if X >= 0:
  if (K - abX // D) % 2 == 0:
    Ans = abX - ((abX // D) * D)
  else:
    Ans = abs(abX - ((abX // D) * D) - D)
      
#  else:
#    print(abs(X // D))
#    if (K - abs(X // D)) % 2 == 0:
#      Ans = abs(X + (abs((X // D)) * D))
#    else:
#      Ans = abs(X + (abs((X // D)) * D) - D)
    
print(Ans)


Measured memory_bytes: 9220
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<random>
#include<numeric>
#include<string>
#include<cstring>
typedef long long ll;
typedef long double ld;
using namespace std;
ll dx[] = { 0,0,1,-1 };
ll dy[] = { 1,-1,0,0 };

ll gcd(ll a, ll b) {
	if (a<b) { return gcd(b, a); }
	else if (a%b) { return gcd(b, a%b); }
	else { return b; }
}
int main() {
	ll a, b;
	cin >> a >> b;
	if (a <= 8 && b <= 8)
		cout << "Yay!" << endl;
	else
		cout << ":(" << endl;

}


Measured memory_bytes: 256
#include <cstdio>
#define MAX 500000
#define SENTINEL 2e9

int L[MAX/2+2],R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left,int mid,int right){
	int n1=mid-left;
	int n2=right-mid;
	for(int i=0;i<n1;i++){
		L[i]=A[left+i];
	}
	for(int i=0;i<n2;i++){
		R[i]=A[mid+i];
	}
	L[n1]=R[n2]=SENTINEL;
	int i=0,j=0;
	for(int k=left;k<right;k++){
		cnt++;
		if(L[i]<=R[j]){
			A[k]=L[i++];
		}else{
			A[k]=R[j++];
		}
	}
}

void mergeSort(int A[],int n,int left,int right){
	if(left+1<right){
		int mid=(left+right)/2;
		mergeSort(A,n,left,mid);
		mergeSort(A,n,mid,right);
		merge(A,n,left,mid,right);
	}
}

int main(void){
	int A[MAX],n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&A[i]);
	}
	mergeSort(A,n,0,n);
	for(int i=0;i<n;i++){
		printf("%d%c",A[i],i==n-1?'\n':' ');
	}
	printf("%d\n",cnt);
	return 0;
}



Measured memory_bytes: 6480
NKQ = input().split(' ')
N = int(NKQ[0])
K = int(NKQ[1])
Q = int(NKQ[2])

Bn = [0] * N
for _ in range(Q):
    A = int(input()) 
    Bn[A-1] += 1

for i in range(N):
    if K - Q + Bn[i]  > 0:
        print('Yes')
    else:
        print('No')

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

int main() {
  long long int W, H, x, y;
  cin >> W >> H >> x >> y;
  double A;
  A = W * H * 0.5;
  int B = 0;
  if (W == 2 * x && H == 2 * y) B = 1;
  cout << fixed << setprecision(10) << A << " " << B << endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Taro's Obsession
 */
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int m = Integer.parseInt(line);
			int n = Integer.parseInt(br.readLine());

			//suspect
			Suspect[] suspects = new Suspect[m + 1];
			for (int i = 1; i < m + 1; i++) {
				suspects[i] = new Suspect(i);
			}

			//testimony
			for (int i = 0; i < n; i++) {
				line = br.readLine();
				int f = Integer.parseInt(line.substring(0, line.indexOf(' ')));
				int l = Integer.parseInt(line.substring(line.indexOf(' ') + 1));
				suspects[f].laters.offer(suspects[l]);
				suspects[l].formers.offer(suspects[f]);
			}

			//solve
			for (Suspect s : suspects) {
				if (s != null && !s.done && s.formers.size() == 0) {
					Deque<Suspect> queue = new ArrayDeque<Suspect>();
					queue.offer(s);
					while (queue.size() > 0) {
						Suspect f = queue.poll();
						for (Suspect l : f.laters) {
							l.formers.remove(f);
							if (l.formers.size() == 0) {
								queue.offer(l);
							}
						}
						//
						f.done = true;
						System.out.println(f.id);
					}
				}
			}
		} // end while

	} // end main
}

class Suspect {
	Deque<Suspect> formers = new ArrayDeque<Suspect>();
	Deque<Suspect> laters = new ArrayDeque<Suspect>();
	int id;
	boolean done = false;

	Suspect(int id) {
		this.id = id;
	}
}

Measured memory_bytes: 16880
N = int(input())

x = []
u = []
sum_m = []

for i in range(N):
    j, k = input().split(' ')
    if k == 'JPY':
        sum_m.append(int(j))
        x.append(int(j))
    elif k == 'BTC':
        sum_m.append(float(j) * 380000.0)
        x.append(float(j))
    u.append(k)

print(sum(sum_m))


Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl
ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}
int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  ll g = a[0];
  rep(i, n - 1) g = gcd(g, a[i + 1]);
  cout << g << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
constexpr double pi=3.14159265358979;

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;
}
using namespace std;

void solve(){
    int n;
    cin>>n;
    //nが奇数のとき、和がnとなる頂点対には辺を張らない(完全グラフから辺を外して考える)
    ///nが偶数のとき、和がn+1となる頂点対には辺を張らない(奇数の時と同じようにすると自分自身を引かねばならなくなる)
    int m=n*(n-1)/2-n/2;
    cout<<m<<"\n";
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            if(n%2==1&&i+j==n)continue;
            if(n%2==0&&i+j==n+1)continue;
            cout<<i<<" "<<j<<"\n";
        }
    }
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int main(void){
  char s[100];
  scanf("%s",s);
  int i,n=strlen(s);
  if(s[0]!='A'){
    puts("WA");
    return 0;
  }
  int cnt=0;
  for(i=1;i<n;i++){
    if(isupper(s[i])){
      if(i==1||i==n-1||s[i]!='C'){
        puts("WA");
        return 0;
      }
      cnt++;
    }
  }
  if(cnt!=1)puts("WA");
  else puts("AC");
  return 0;
}

Measured memory_bytes: 128
import heapq

N, M = map(int, input().split())
A = list(map(lambda x: -1 * int(x), input().split()))

heapq.heapify(A)
for _ in range(M):
    heapq.heappush(A, -1 * (-1 * heapq.heappop(A) // 2))

print(-1 * sum(A))

Measured memory_bytes: 14180
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();

        final LinkedList<Pair> pairs = new LinkedList<>();
        if (n % 2 == 1) {
            for (int i = 1; i <= n; i++) {
                for (int j = i + 1; j <= n; j++) {
                    if (i + j != n) {
                        pairs.add(new Pair(i, j));
                    }
                }
            }
        } else {
            for (int i = 1; i <= n; i++) {
                for (int j = i + 1; j <= n; j++) {
                    if (i + j != n + 1) {
                        pairs.add(new Pair(i, j));
                    }
                }
            }
        }

        System.out.println(pairs.size());
        final String answer = pairs.stream()
                .map(Pair::toString)
                .collect(Collectors.joining("\n"));
        System.out.println(answer);
    }

    private static class Pair {
        final int x;
        final int y;

        Pair(final int x, final int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return x + " " + y;
        }
    }
}


Measured memory_bytes: 27092
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
bool dp[100100];
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}
 
string nsin (long long n){
    string ans ; 
    
    while(n> 0){
        int num = n%26;
        n--;
        if (num ==0) num = 26;
        ans += ('a' + num-1 );
        n /= 26 ;
    }

    reverse(ans.begin(),ans.end());
    cout << ans << endl;
    return ans;
}
 
 
 
int main(){
    long long N;
    cin >> N;
 
    string inu = nsin(N);
    
}

Measured memory_bytes: 3632
#include<cstdio>
using namespace std;
typedef long long ll;

ll n, m, x, y, d[9][9], win[9], WIN;

ll dfs(ll x, ll y) {
  if (x == n) {
    //for (ll i = 0; i < n; i++) if (win[i] != WIN) return 0;
    //for (ll i = 0; i < n; i++) printf("%lld ", win[i]); printf("\n");
    return 1;
  }
  if (y == n) return dfs(x+1, x+2);
  if (d[x][y] != 0) return dfs(x, y+1);
  //printf("%lld,%lld\n", x, y);
  ll ans = 0;
  if (win[x] != WIN) win[x]++, ans += dfs(x, y+1), win[x]--;
  if (win[y] != WIN) win[y]++, ans += dfs(x, y+1), win[y]--;
  return ans;
}

int main() {
  while (scanf("%lld", &n), n) {
    scanf("%lld", &m);
    WIN = n/2;
    for (ll i = 0; i < n; i++) win[i] = 0;
    for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) d[i][j] = 0;
    for (ll i = 0; i < m; i++) scanf("%lld%lld", &x, &y), x--, y--, d[x][y] = 1, d[y][x] = -1, win[x]++;
    bool flag = false;
    for (ll i = 0; i < n; i++) if (win[i] > WIN) flag = true;
    if (flag) {
      printf("0\n");
      continue;
    }
    printf("%lld\n", dfs(0, 1));
  }
}



Measured memory_bytes: 2604
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main ()
{
	string s, a;
	cin>>s>>a;
	ll z = 0;
	for(size_t i = 0; i<s.size(); i++)
	{
		if(s[i]!=a[i])
		{
			z++;
		}
	}
	cout<<z<<endl;
	return 0;
}

Measured memory_bytes: 3912
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int bd[][][] = new int[4][3][10];
		int n = sc.nextInt();
		int i,j,k,b,f,r,v;
		for(i=0;i<n;i++){
			b = sc.nextInt();
			f = sc.nextInt();
			r = sc.nextInt();
			v = sc.nextInt();
			
			if((bd[(b-1)][(f-1)][(r-1)]+v) >= 0){
				bd[(b-1)][(f-1)][(r-1)] += v;
			}
		}
		for(i=0;i<4;i++){
			for(j=0;j<3;j++){
				for(k=0;k<10;k++){
					System.out.print(" "+bd[i][j][k]);
				}
				System.out.println();
			}
			if(i==3){
				break;
			}
			System.out.println("####################");
		}
		sc.close();
	}

}



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

void print(char c[][6], int H, int W){
  for (int h = 0; h < H; h++){
    for (int w = 0; w < W; w++){
      cout << c[h][w];
    }
    cout << endl;
  }
}

void copy(char S[][6], char D[][6], int H, int W){
  for (int h = 0; h < H; h++){
    for (int w = 0; w < W; w++){
      D[h][w] = S[h][w];
    }
  }
}  

int raw(char C[][6], int H, int W, int r){
  int ans = 0;
  for (int w =  0; w < W; w++){
    if (C[r][w] == '#'){
      ans++;
    }
    C[r][w] = 'R';
  }
  return ans;
}

int column(char C[][6], int H, int W, int c){
  int ans = 0;
  for (int h = 0; h < H; h++){
    if (C[h][c] == '#'){
      ans++;
    }
    C[h][c] = 'R';
  }
  return ans;
}

int main(){
  int H, W, K;
  cin >> H >> W >> K;
  int h, w;
  
  char Cij[6][6];
  int BCount = 0;		// Cij[][]の初期値に含まれる'#'の数
  
  for (h = 0; h < H; h++){
    for (w = 0; w < W; w++){
      cin >> Cij[h][w];
      if (Cij[h][w] == '#'){
	BCount++;
      }
    }
  }

  int Hc = 1;
  int Wc = 1;
  for (h = 0; h < H; h++){
    Hc *= 2;
  }
  for (w = 0; w < W; w++){
    Wc *= 2;
  }

  //cout << BCount << " " << Hc << " " << Wc << endl;
  
  char Ctmp[6][6];
  
  // 総当たりで見つける
  int ans = 0;

  // 行のみ操作した場合の判定
  int hmask;
  int wmask;
  for (h = 0; h < Hc; h++){
    for (w = 0; w < Wc; w++){
      //cout << "*** h=" << h << ", w=" << w << endl;
      int bc = BCount;
      copy(Cij, Ctmp, H, W);
      hmask = 1;
      for (int n = 0; n < H; n++){
	if (h & hmask){
	  bc -= raw(Ctmp, H, W, n);
	  //cout << "h" << n << " ";
	  if (bc < K){
	    goto skip;
	  }
	}
	hmask <<= 1;
      }
      
      wmask = 1;
      for (int n = 0; n < W; n++){
	//cout << "wmask:" << wmask << endl;
	if (w & wmask){
	  bc -= column(Ctmp, H, W, n);
	  //cout << "w" << n << " ";
	  if (bc < K){
	    goto skip;
	  }
	}
	wmask <<= 1;
      }
      //cout << "bc" << bc << endl;
      
      if (bc == K){
	//cout << h << "," << w << endl;
	ans++;
      }
    skip:
      ;
    }
  }
      
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main(){
   long long  int sum=0;
    long long int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k<a){
        sum = k;
    }
    if(k>=a && k<=(a+b)){
       sum = a;
    }
    if( k > (a+b) && k <= (a+b+c)){
       sum = a - (k-(a+b));
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF (1LL<<61 + 1<<29)
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
#define cint(...) ll __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__);

int main() {
	int i=0;
	string s;
	cin >> s;
	for (char c : s) i += c - '0';
	cout << i << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

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

int main(void) {
    int i,j;
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];
    int t = 0;
    rep(i,n){
        while(a[i]%2==0){
            t++;
            a[i]/=2;
        }
    }
    cout << t << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end());
    int res=0;
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                if(a[i]+a[j]>a[k] && a[i]!=a[j] && a[j]!=a[k])
                    res++;
            }
        }
    }
    cout<<res;
return 0;
}

Measured memory_bytes: 3604
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


N = a_int()
S = []
for _ in range(N):
    S.append(read()[:-1])
cnt = Counter(S)
print('AC x', cnt['AC'])
print('WA x', cnt['WA'])
print('TLE x', cnt['TLE'])
print('RE x', cnt['RE'])


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

int main(){
  ll N,ans=0;
  cin>>N;
  
  map<string,ll> L;
  
  REP(i,N){
    string S;
    cin>>S;
    L[S]=0;
  }
  
  cout<<L.size()<<endl;
  return 0;
}

Measured memory_bytes: 19224
#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define rs (x<<1|1)
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) (int((x).size()))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
const int maxn=2e6+5;
int n,ans,h,t;
int last[maxn][26],L[maxn],q[maxn];
char S[maxn],T[maxn];
pa now[maxn];
int main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	scanf("%d%s%s",&n,S+1,T+1);
	rep(i,1,n){
		memcpy(last[i],last[i-1],sizeof last[i]);
		last[i][S[i]-'a']=i;
	}
	int C=0;
	rep(i,1,n)if(S[i]!=T[i])C=1;
	if(!C)return puts("0"),0;
	int tmp=n,tot=0;
	per(i,n,1){
		if(i>=tmp&&T[i]==T[i+1])continue;
		if(i<tmp)tmp=i;
		int x=T[i]-'a';
		tmp=last[tmp][x];
		if(!tmp)return puts("-1"),0;
		L[i]=tmp;
		if(L[i]!=i)now[++tot]=mp(L[i],i);
	}
	reverse(now+1,now+tot+1);
	ans=1;
	per(i,tot,1){
		while(h!=t&&q[h]-(t-h)>=now[i].w2)h++;
		ans=max(ans,t-h+1);
		q[t++]=now[i].w1;
	}
	printf("%d\n",ans);
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  const long long M = 1000000007;
  vector<long long> A(N);
  vector<long long> S(N+1);
  for(int i = 0; i < N; i++){
    cin >> A[i];
    A[i] %= M;
    S[i+1] = (S[i]+A[i])%M;
  }
  long long sum = 0;
  for(int i = 0; i < N-1; i++){
    if(S[N] < S[i+1]){
      sum = sum+(A[i]*(M+S[N]-S[i+1]))%M;
    }else{
      sum = sum+(A[i]*(S[N]-S[i+1]))%M;
    }
  }
  cout << sum%M << endl;
}


Measured memory_bytes: 6356
n=int(input())
a=[int(x) for x in input().split()]
s=sum(a)
q=int(input())
b=[]
c=[]
for i in range(q):
    xb,xc=map(int,input().split())
    b.append(xb)
    c.append(xc)
r=[0]*1000001
for i in a:
    r[i]+=1
for i in range(q):
    y=r[b[i]]
    r[b[i]]=0
    r[c[i]]+=y
    s+=y*(c[i]-b[i])
    print(s)

Measured memory_bytes: 30448
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  double money;
  cin >> N; 
  vector<double> num(N);
  vector<string> str(N);

  for(int i =0; i< N; i++){
    cin >> num.at(i) >> str.at(i);
    if (str.at(i) == "JPY"){
      money += num.at(i);
    }
    else{
      money += num.at(i) * 380000.0;
    }
  }
  cout << money << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996)

#define MAX_N 100000

int W[MAX_N + 1];
long long WS[MAX_N + 1];

int main(void) {
	int n, k;
	scanf("%d %d", &n, &k);

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

	long long sum = 0;
	int max = 0;
	for (int i = 0; i < n; ++i) {
		if (max < W[i]) {
			max = W[i];
		}
		sum += W[i];
		WS[i] = sum;
	}
	int p = int(sum / k);
	if (p < max) {
		p = max;
	}
	while (true) {
		int num = 0;
		long long s = 0;
		int offset = 0;
		while (true) {
			long long targetW = s + p;
			long long *pos = std::upper_bound(WS + offset, WS + n, targetW);
			offset = std::distance(WS, pos);
			s = WS[offset - 1];
			if ((++num > k) || (offset == n)) {
				break;
			}
		}
		if (num <= k) {
			break;
		}
		++p;
	}

	printf("%d\n", p);


	return 0;
}


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

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

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

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

template<typename T, size_t size> void fill(T (&ary)[size], const T& val){
    fill_n((T*)ary, size, val);
}

void solve() {
    //const i64 mod = 1'000'000'007;
    i64 N,M;
    cin >> N >> M;

    priority_queue<i64,vector<i64>,greater<i64>> que;

    vector<i64> A(N);
    rep(i,0,N){
        cin >> A[i];
        que.push(A[i]);
    }

    vector<pair<i64,i64>> cb(M);
    rep(i,0,M){
        cin >> cb[i].second >> cb[i].first;
    }
    sort(rbegin(cb),rend(cb));

    rep(i,0,M){
        if(que.size() == N and que.top()>=cb[i].first) continue;
        i64 use=0;
        while(use<cb[i].second and que.top()<cb[i].first){
            ++use;
            que.pop();
            que.push(cb[i].first);
        }
    }

    i64 ans=0;
    while(!que.empty()){
        ans+=que.top();
        que.pop();
    }

    cout << ans << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


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

struct node{
  string exp;
  int left=-1;
  int right=-1;
};

int num;

int prior(char c){
  if(c=='+') return 0;
  else if(c=='*') return 1;
  else if(c=='-') return 2;
  else return 3;
}

void divide(int self,string exp,node nodes[]){
  int cnt=0,min=3,min_index=-1;
  bool inter=false;
  for(int i=0;i<exp.size();i++){
    if(exp[i]=='('){
      cnt++;
      if(i==0) inter=true;
    } else if(exp[i]==')'){
      cnt--;
      if(cnt==0&&i!=exp.size()-1) inter=false;
    } else if(cnt==0){
      int p=prior(exp[i]);
      if(p<min){
	min=p; min_index=i;
      }
    }
  }
  if(inter){
    divide(self,exp.substr(1,exp.size()-2),nodes); return;
  }
  if(min_index>=0){
    if(min<2) divide(nodes[self].left=++num,exp.substr(0,min_index),nodes);
    divide(nodes[self].right=++num,exp.substr(min_index+1),nodes);
    nodes[self].exp=exp[min_index];
  } else nodes[self].exp=exp;
}

int AND[3][3]={{0,0,0},{0,1,1},{0,1,2}};
int OR[3][3]={{0,1,2},{1,1,2},{2,2,2}};
int NOT[3]={2,1,0};

int solve(int n,node nodes[],int p,int q,int r){
  if(nodes[n].exp=="0") return 0;
  else if(nodes[n].exp=="1") return 1;
  else if(nodes[n].exp=="2") return 2;
  else if(nodes[n].exp=="P") return p;
  else if(nodes[n].exp=="Q") return q;
  else if(nodes[n].exp=="R") return r;
  else{
    if(nodes[n].exp=="+")
      return OR[solve(nodes[n].left,nodes,p,q,r)][solve(nodes[n].right,nodes,p,q,r)];
    else if(nodes[n].exp=="*")
      return AND[solve(nodes[n].left,nodes,p,q,r)][solve(nodes[n].right,nodes,p,q,r)];
    else
      return NOT[solve(nodes[n].right,nodes,p,q,r)];
  }
  //cout<<nodes[n].exp<<endl;
}

int main(){
  string exp;

  for(;;){
    cin>>exp;
    if(exp==".") break;
    num=0;
    struct node nodes[100];
    divide(0,exp,nodes);
    int sum=0;
    for(int i=0;i<3;i++)
      for(int j=0;j<3;j++)
	for(int k=0;k<3;k++)
	  if(solve(0,nodes,i,j,k)==2) sum++;
    cout<<sum<<endl;
  }
}


Measured memory_bytes: 3152
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
using namespace std;

const int LIMIT = 45000;

int main() {
	int x;
	cin >> x;
	int sum[LIMIT];
	int pos = 0;
	int ans = 0;

	for(int i = 0; i < LIMIT; i++){
		sum[i] = i*(i+1)/2;
	}
	for(int i = 0; i < LIMIT; i++){
		if(sum[i] >= x){
			pos = i;
			break;
		}
	}
	cout << pos << endl;

	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define rep(i, a) for (int i=0; i<(a); i++) 
#define ub        upper_bound            // first element >  val(itr)
#define lb        lower_bound            // first element >= val(itr)

#define mp make_pair
#define pb push_back
#define pi 3.141592653589793
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define bitcount(a) __builtin_popcount(a) // count set bits
#define all(x) (x).begin(),(x).end()

const ll MOD = 1e9 + 7;
const int inf = 1e9+9;
const long long INF = 1e18+3;

//to debug 
#define dbg(x) cout << "Line " << __LINE__ << " | " #x ": " << (x) << endl

template<typename T> T gcd(T a,T b){ if(b>a) return gcd(b,a);return b==0?a:gcd(b,a%b); }
template<typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template<typename T> T fast_power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

inline ll mod(ll x,ll n) {if (x < n) return x; if (x >= n) return x - n;}
string IntToString(ll a){ ostringstream temp; temp << a; return temp.str();}
ll findMMI_fermat(ll n,ll M) {ll ans= fast_power(n,M-2,M);return ans;}//i.e In (a/b)%M..it calculates MMI of b wrt M
ll add(ll a,ll b,ll M)  { return ( mod(a,M ) + mod(b,M ))%M;     }
ll sub(ll a, ll b,ll M) { return (mod(a,M ) + M - mod(b,M ))%M;   }
ll mult(ll a,ll b,ll M) { return  ( mod(a,M)*mod(b,M) ) %M ; }
bool isprime(ll a){ if(a==2) {return 1;}if(!(a&1) ) {return 0;}for(ll i=3;i*i<=a;i+=2){if(a%i==0) {return 0;} } return 1;} 

                /* -------------------------------Main Code------------------------------- */

const int N=1e5+5;

int main() 
{
    FAST;
    int x,y;cin>>x>>y;
	int t = x*y;
	int mx = max(t,x+y);
	cout<<max(x-y,mx)<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

// ax + by = gcd(a, b) となるような (x, y) を求める
// 多くの場合 a と b は互いに素として ax + by = 1 となる (x, y) を求める
ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x); // 再帰的に解く
    y -= a / b * x;
    return d;
}

// 負の数にも対応した mod (a = -11 とかでも OK) 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}

// 逆元計算 (ここでは a と m が互いに素であることが必要)
ll modinv(ll a, ll m) {
    ll x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}

// a^n mod を計算する
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    int N; cin >> N;
    string S; cin >> S;
    int bc = 0; // Bit Count

    vector f(N+1, 0);
    for (int i = 1; i <= N; i++) {
        int bits = __builtin_popcount(i);
        f[i] = f[i % bits] + 1;
        bc += S[i-1] - '0';
    }
    ll bcp = bc + 1;
    ll bcm = bc - 1;

    ll T1 = 0, T2 = 0;
    rep(i, N) {
        int d = S[i] - '0';
        if (bc < N) {
            T1 <<=1;
            T1 += d;
            T1 %= bcp;
        }
        if (bcm > 0) {
            T2 <<=1;
            T2 += d;
            T2 %= bcm;
        }
    }

    rep(i, N) {
        if (S[i] - '0') {
            int res = (bcm == 0) ? 0 : f[mod(T2 - modpow(2, N-1-i, bcm), bcm)] + 1;
            cout << res << endl;
        } else {
            cout << f[mod(T1 + modpow(2, N-1-i, bcp), bcp)] + 1<< endl;
        }
    }
}


Measured memory_bytes: 4456
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <math.h>
using namespace std;

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

typedef long long ll;


ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

int main() {
  ll a, b;
  cin >> a >> b;
  ll diff = b - a;

  ll ans = 0;
  rep(i, diff) 
  {
      ans += i;
  }
  ans -= b;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<queue>
#include<iostream>
using namespace std;
priority_queue< int >q;

int main()
{
    int n;
    int sum1=0;
    int sum2=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int temp;
        cin>>temp;
        q.push(temp);
    }
    for(int i=1;i<=n;i++){
        if(i%2) sum1+=q.top();
        else sum2+=q.top();
        q.pop();
    }
    cout<<sum1-sum2;
    return 0;
}

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

int main() {
  long long  n;
  cin >> n;
  long long k=2;
  int s=0;
  while(k*k <= n){
    if(n%k == 0){
      int x=0;
      while(n%k == 0){
        x += 1;
        n = n/k;
      }
      int i=1;
      while(x>=(i+2)*(i+1)/2) i += 1;
      //cout << k << " " << i << endl;
      s += i;
    }
    k += 1;
  }
  if (n>1) s+= 1;
  cout << s;
 
}


Measured memory_bytes: 3632
N=int(input())
L=[3,5,7]
def num753(x):
    tmp=0
    for i in L:
        p=x*10+i
        if p<=N:
            if set([int(j) for j in str(p)])==set(L):
                tmp+=num753(p)+1
            else:
                tmp+=num753(p)
    return tmp
print(num753(0))

Measured memory_bytes: 3064
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
def f(b,n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n%b


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
S = int(input())

ans = -1
if S==N:
    ans = N+1
else:
    # bをN^(1/2)まで全探索
    for b in range(2, int(N**.5)+1):
        if f(b,N)==S:
            ans = b
            break

# まだ答えが見つからなければ
if ans == -1:
    # bがN^(1/2)より大きい可能性が残っており、b進数で表すと2桁
    # 1 <= p < b, N = pb+q <= pb < p^2, p > N^(1/2) なので pで全探索
    # p+q = S より b = (N-S)/p+1
    for p in range(int(N**.5)+1,0,-1):
        b = (N-S)//p + 1
        # bが1のときは対象外にしないと無限ループ！
        if b >= 2 and f(b,N)==S:
            ans = b
            break

print(ans)


Measured memory_bytes: 3064
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<cstring>
#include<sstream>
#include<cassert>
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()


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


const int MAX_N = 100000;

int main(int argc, char const* argv[])
{
    int N;
    int ans = 0;
    cin >> N;
    

    static ll nums[MAX_N];

    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }

    sort(nums, nums+N);


    for (int i = 0; i < N; i++) {
        ll k = nums[i];
        for (int n = i; n < N; n++) {
            if (k != nums[n+1]) {
                if ((n-i+1) % 2 == 1) {
                    ++ans;
                }
                i = n;
                break;
            } 
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <cstring>

using namespace std;

int main(int argc, char* argv[])
{
    int n, m, c = 0;

    cin >> n >> m;

    int A[n][m], b[m];

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> A[i][j];
        }
    }

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

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            c += A[i][j] * b[j];
        }
        cout << c << endl;
        c = 0;
    }
    return 0;
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=1010;
const ll mod=1e9+7;

int n;
int a[mx];
vector<int> v[mx];

P dfs(int x){
  if(v[x].empty()){ return {0,a[x]}; }
  bitset<5050> bit;
  bit.set(0);
  int sum=0;
  for(auto to : v[x]){
    P p=dfs(to);
    if(p.F==-1){return {-1,-1};}
    bit = (bit<<p.first | bit<<p.second);
    sum += p.first+p.second;
  }
  
  for(int i=a[x]; i>=0; i--){ if(bit[i]){ return {a[x],sum-i}; }}
  return {-1,-1};
}

int main() {
  cin >> n;
  rep(i,n-1){
    int x;  cin >> x;
    v[x-1].push_back(i+1);
  }
  rep(i,n){ cin >> a[i]; }
  
  cout << (dfs(0).first!=-1?"POSSIBLE":"IMPOSSIBLE") << endl; 
  return 0;
}  


Measured memory_bytes: 1664
N , K = map(int,input().split(" "))
a = list(map(int,input().split(" ")))

mod = 10 ** 9 + 7

dp = [ [0]*(K+1) for _ in range(N) ]
acc = [ [0]*(K+1) for _ in range(N) ]
mn = min(K,a[0])

for i in range(K+1):
    if i <= mn:
        dp[0][i] = 1
    acc[0][i] = (acc[0][i-1] + dp[0][i])%mod if i > 0 else dp[0][i]%mod

for i in range(1,N):
    dp[i][0] = dp[i-1][0]
    acc[i][0] = dp[i][0]
    for k in range(1,K+1):
        if k - a[i] <= 0:
            dp[i][k] = acc[i-1][k]  % mod 
        else:
            dp[i][k] = (acc[i-1][k] - acc[i-1][k-a[i]-1]) % mod
        acc[i][k] = (acc[i][k-1] + dp[i][k])%mod

print(dp[N-1][K]%mod)

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

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  const int inf = 1e9;
  vector<int> f(n + 1, inf);
  f[0] = 0;
  for (int b : {6, 9}) {
    for (int w = 1; w <= n; w *= b) {
      for (int j = 0; j <= n - w; j++) {
        f[j + w] = min(f[j + w], f[j] + 1);
      }
    }
  }
  printf("%d\n", f[n]);
  return 0;
}

Measured memory_bytes: 640
import sys
from itertools import combinations
from collections import Counter


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    S = inputs[0]
    N = len(S)
    trees = {}

    trees[S[0]] = {S[1]: set(S[2])}

    prev = S[2]
    prevprev = S[1]
    for i, c in enumerate(S):
        if i <= 2:
            continue

        for first in trees.keys():
            for second in trees[first].keys():
                trees[first][second].add(c)
            if prev not in trees[first]:
                trees[first][prev] = set(c)
        if prevprev not in trees:
            trees[prevprev] = {prev: set(c)}
        prevprev = prev
        prev = c

    count = 0
    for first in trees:
        for second in trees[first]:
            count += len(trees[first][second])
    return count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    input()
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 44780
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
signed main(){
  int N;
  cin>>N;
  vector<pair<bitset<16>,bitset<16>>> A(N);
  rep(i,0,N){
    int Z;
    cin>>Z;
    rep(j,0,Z){
    int X;
    bool Y;
    cin>>X>>Y;
      if(Y) A.at(i).first.set(X-1);
      else A.at(i).second.set(X-1);
    }
  }
  int ans=0;
  rep(i,0,(1<<N)){
    bitset<16> B(i);
    bool flag=1;
    rep(j,0,N){
      if(!B.test(j)){
        rep(k,0,N){
          if(A.at(j).first.test(k)){
            if(B.test(k)){
              flag=0;
              //cout<<i<<" "<<j<<" "<<k<<" "<<B<<endl;
              goto XYZ;
            }
          }
          if(A.at(j).second.test(k)){
            if(!B.test(k)){
              flag=0;
              //cout<<i<<" "<<j<<" "<<k<<" "<<B<<endl;
              goto XYZ;
            }
          }
        }
      }
    }
    XYZ:
    if(flag){
      ans=max(ans,N-(int)B.count());
    }
  }
  cout<<ans<<endl;
  }

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
typedef long long ll;

using namespace std;

int main()
{
	int n;
	int a[100];
	int alice=0;
	int bob=0;
	int ans=0;
	
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	reverse(a,a+n);
	for(int i=0;i<n;i+=2)
	{
		alice+=a[i];
	}
	for(int i=1;i<n;i+=2)
	{
		bob+=a[i];
	}
	ans=alice-bob;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define FOR(i, a, b) for(ll i=(a); i < (ll)(b); ++i)
template<class T> inline bool chmax(T& a, T b) { if(a < b){ a=b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if(a > b){ a=b; return 1; } return 0;}

int main(){
	string s;
	cin >> s;
	int n = s.size();
	
	vector<int> sp(n+1);
	
	int num = 0;
	int ten = 10;
	sp[n] = 0;
	for(int i=n-1; i>=0; i--){
		num += ten*(s[i]-'0')%2019;
		num %= 2019;
		sp[i] = num;
		ten = (ten*10)%2019;
	}
	
	int a[2019]={};
	REP(i,n+1){
		a[sp[i]]++;
	}
	
	ll ans = 0;
	REP(i,2019){
		ll b = ((ll)a[i]*(a[i]-1))/2;
		ans += b;
	}
	
	cout << ans << endl;
	
	
	return 0;
}

Measured memory_bytes: 4456
#include<bits/stdc++.h>
#include<math.h>
#include <stdio.h>
#include<vector>
#include<deque>
#include<stdlib.h>
//#include <algorithm>
#include<set>
#include <limits>
#include<string>
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define ll long long
#define d_5 100000
#define d9_7 1000000007int N;

int main(void){
  ll n;
  cin>>n;
  vector<ll> p;
  rep(i,n){
    ll tp;
    cin >> tp;
    p.push_back(tp);
  }
  int sc=0;
  rep(i,n){
    if(p[i]==i+1){
      if(p[i+1]==i+2){
        swap(p[i],p[i+1]);
        sc++;
      }else{
        if(i==0){
          swap(p[i],p[i+1]);
          sc++;
        }else if(i==n-1){
          swap(p[i-1],p[i]);
          sc++;
        }else{
          if(p[i+1]<i+2){
            swap(p[i+1],p[i]);
            sc++;
          }else{
            swap(p[i],p[i-1]);
            sc++;
          }
        }
      }
    }
  }
  cout << sc;
	return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define era first
#define end second.first
#define str second.second
using namespace std;
typedef pair <int,pair <int,string> > P;

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

    P ls[1002];

    for(int i=0;i<n;i++){
      cin >> ls[i].str >> ls[i].end >> ls[i].era;
      ls[i].era = ls[i].era-ls[i].end+1;
    }
    ls[n].era = 1000000000;
    sort(ls,ls+n);

    for(int i=0;i<m;i++){
      int a,flg = 0;
      cin >> a;
      for(int j=0;j<n;j++)
	if(ls[j].era <= a && a < ls[j+1].era){
	  if(ls[j].end >= a-ls[j].era+1) cout << ls[j].str <<" "<< a-ls[j].era+1<<endl,flg = 1;
	  break;
	}
      if(flg == 0) cout << "Unknown"<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1296
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1LL<<60;
long double pi=3.14159265358979323846L;
double eps=1e-12;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll popcount(ll n){
    ll ret=0;
    while(n>0){
        ret+=n%2;
        n/=2;
    }
    return ret;
}
ll gya[1000010];
ll kai[1000010];
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n,m;cin>>n>>m;
    if(n<m)swap(n,m);
    if(n-m>=2){
        cout<<0<<endl;
        return 0;
    }
    ll ans=1;
    rep(i,1,n+1)(ans*=i)%=mod;
    rep(i,1,m+1)(ans*=i)%=mod;
    if(n==m)ans*=2;
    cout<<ans%mod<<endl;
}




Measured memory_bytes: 256