akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
    static long[] V;
    static long[][] dp;
    static final long MOD = (int)Math.pow(10,9) + 7;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt(),W = sc.nextInt();
        sc.nextLine();
        dp = new long[H+1][W+1];
        String[] map = new String[H + 1];
        for (int i = 1; i <= H; i++) {
            map[i] = sc.nextLine();
        }
        dp[1][1] = 1;
        System.out.println(solve(H,W,map));
    }

    private static long solve(int H,int W,String[] map) {
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if(map[i].charAt(j-1) == '.' && !(i==1 && j==1))
                    dp[i][j] = ((j-1==0?0:dp[i][j-1])+(i-1==0?0:dp[i-1][j]))%MOD;
            }
        }
        return dp[H][W];
    }
}


Measured memory_bytes: 51688
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;
 
int main(){

	int n;
	stack<int> st;
	while(cin >> n){
		if(n != 0){
			st.push(n);
		}
		else{
			cout << st.top() << endl;
			st.pop();
		}
	}
	
	return 0;
}

Measured memory_bytes: 3096
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

const int N = 205;

int dis[N][N];
char s[N];

int main()
{
	int n = read();
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s + 1);
		for (int j = 1; j <= n; ++j) 
			if (s[j] == '1') dis[i][j] = 1;
	}
	
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j) 
				dis[i][j] = min(dis[i][j],
					dis[i][k] + dis[k][j]);
	
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				if (abs(dis[i][j] - dis[i][k] - dis[k][j]) & 1)
					return puts("-1"), 0;
	
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = i + 1; j <= n; ++j)
			ans = max(ans, dis[i][j]);
	printf("%d\n", ans + 1);
	return 0;
}

Measured memory_bytes: 384
#define _USE_MATH_DEFINES
 
#include <cmath>

#include <iostream>
# include <bits/stdc++.h>
using namespace std;

long long powerexp(long long base, long long exp, int mod) {
   long long res = 1;
   while (exp > 0) {
      if (exp % 2 == 1)
         res= (res * base) % mod;
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}
int gcd(int a, int b)
{
    int c = a % b;
    while(c != 0)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}
void PrintVector(vector<long long int> v,long long int n)
{
 
    for(int i=v.size()-1;i>=0;i--)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
void Takevector(vector<long long int> &v,long long int n)
{
  for(long long int i=0;i <n;i++)
  { long long int number;
    cin>>number;
    v.push_back(number);
  }
}
typedef long long int ll;
typedef vector<long long int> vi;

#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define scl(x)         ll x;       scanf("%lld", &x);
#define scll(x, y)     ll x, y;    scanf("%lld %lld", &x, &y);
#define sclll(x, y, z) ll x, y, z; scanf("%lld %lld %lld", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define rep(i, x, y)   for (__typeof(x) i = x; i <= y; i ++)
#define repi(i, x, y)  for (__typeof(x) i = x; i >= y; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
#define nl cout<<"\n";
ll min(ll x, ll y)  
{  
    return (x < y)? x: y;  
      
}  
  ll fn(ll a,ll b,ll n)
  {
    ll f=floor(a*min(b-1,n)/b);
    return f;
  }
int main()
 {
//   int flag=0;
//   ll sum=0;
//   int flag1=1;
//   ll tot=0;
//   int ans=0;
//   map<int,int>m;
//   vi v;
//   set<ll>st;
//   string s;
  sclll(a,b,n);
  
  cout<<fn(a,b,n);
    return 0;
}

Measured memory_bytes: 3692
#include <iostream>
#include <math.h>
using namespace std;
int main(void){
	double a, b, x;
	cin >> a >> b >> x;
	double r = x<= (b*a*a)/2.0? atan(2.0*x/(a*b*b)) : atan(a*a/(2.0*(a*b-x/a)));
	cout.precision(11);
	cout << 90.0-r*180.0/acos(-1.0) << endl;
}

Measured memory_bytes: 4060
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;



int main() {
    int n, m;
    cin >> n >> m;
    vector<P> you(m);
    rep(i, m) {
        cin >> you[i].second >> you[i].first;
    }

    sort(all(you));
    int ans = 0;
    int j = 0;
    rep(i, m) {
        if(you[i].second >= j) {
            ans++;
            j = you[i].first;
        }
    }

    cout << ans << endl;
}

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

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

  ll a[n];
  priority_queue <ll> q;

  rep(i,n) {
      int j;
      cin >> j;
      a[i]=j;
      q.push(j);
  }
  
  sort(a,a+n);
  ll ans=0;

   ans+=q.top();
   q.pop();

   int count=0;


for(int i=1;i<n-1;i++){
    count++;
     ll mm=q.top();
       ans+= mm;
    if(count==2){
       count=0;
       q.pop();
    }
   
}
   

   cout << ans << endl;



}

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

using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

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

int main(){
    long long int summ=0;
    long long int N;
    cin >> N;
    vector<long long int> A(N),sum(N+1,0);

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

    for(int i=0;i<=N;i++){
        summ += sum[i]*(sum[i]-1)/2;
    }

    for(int i=0;i<N;i++){
        cout << summ - sum[A[i]]*(sum[A[i]]-1)/2 +  (sum[A[i]]-1)*(sum[A[i]]-2)/2 << endl;
    }
}

Measured memory_bytes: 5760
#include<iostream>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if (a<b) {
        cout << "a < b" << endl;
    } else if (a>b) {
        cout << "a > b" << endl;
    } else {
        cout << "a == b" << endl;
    }
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int K,N,S,P,Q=0;
 cin >> K >> N;
 P = K;
 vector<int> A(N);
 for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
 for (int i = 0; i < N-1; i++) {
   S = A.at(i+1)-A.at(i);
   P = P - S;
   if(S > Q)
     Q = S;
   if(i==N-2&&P > Q)
     Q = P;
  }
  cout << K - Q << endl;
}

Measured memory_bytes: 1152
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using namespace std;

const int INF=INT32_MAX/2;

struct Edge{
  int t,c;
  Edge(int t_,int c_):t(t_),c(c_){

  }
};

struct State{
  int n,c;
  State(int n_,int c_):n(n_),c(c_){

  }
  bool operator<(const State& another)const{
    return c<another.c;
  }
  bool operator>(const State& another)const{
    return c>another.c;
  }
};

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  while(true){
    int n,m,climit;
    cin>>n>>m>>climit;
    if(n==0){
      break;
    }

    const int modifier=n;
    vector<vector<Edge>> node(n*(m+1)+1);
    vector<int> result(n*(m+1)+1);
    for(int i=0;i<=n*(m+1);i++){
      result[i]=INF;
    }
    for(int i=0;i<m;i++){
      int f,t,c;
      cin>>f>>t>>c;
      int from=f,to=t;
      for(int ic=0;ic<=m;ic++){
        node[from].push_back(Edge(to,c));
        from+=modifier;
        to+=modifier;
      }
      from=f;
      to=t+modifier;
      for(int ic=0;ic<m;ic++){
        node[from].push_back(Edge(to,0));
        from+=modifier;
        to+=modifier;
      }
    }

    priority_queue<State,vector<State>,greater<>> pq;
    pq.push(State(1,0));
    result[1]=0;
    while(!pq.empty()){
      State current=pq.top();
      pq.pop();
      if(result[current.n]<current.c){
        continue;
      }

      for(auto e:node[current.n]){
        int nn=e.t;
        int nc=current.c+e.c;
        if(result[nn]>nc){
          result[nn]=nc;
          pq.push(State(nn,nc));
        }
      }
    }


    for(int i=0;i<=m;i++){
      if(result[n+modifier*i]<=climit){
        cout<<i<<endl;
        break;
      }
    }



  }

  return 0;
}



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

#define ll long long

int main() {
    ll n,c,k,t[100010],hoge,count = 0,ans=0;
    cin >> n >> c >> k;
    for(int i=0;i<n;i++) cin >> t[i];
    sort(t, t + n);
    reverse(t,t+n);
    for(int i=0;i<n;i++){
        if(t[i-count]-t[i] <= k && count < c){
            count++;
        }else{
            count = 1;
            ans++;
        }
        if(i == n - 1 && count != 0)ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>
#include<bitset>
#include<tuple>
#include<time.h>
#include<list>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int n;
vector<int> a;
void solve(){
	cin >> n;
	a.resize(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	bool b[101] = {0};
	vector<int> ans(n);
	for(int i = 0; i < n; i++){
		int cnt = 0, pos = -1;
		for(int j = 0; j < n; j++){
			if(b[j]) continue;
			cnt++;
			if(cnt == a[j]){
				pos = j;
			}
		}
		if(pos == -1){
			cout << -1 << endl;
			return;
		}
		b[pos] = 1;
		ans[n-i-1] = a[pos];
	}
	for(int i = 0; i < n; i++){
		cout << ans[i] << endl;
	}
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String S = scanner.nextLine();
        if (S.charAt(0) != 'A') {
            System.out.println("WA");
            return;
        }
        int ccount = 0;
        int cindx = -1;
        for (int i = 2; i < S.length() - 1; i++) {
            if (S.charAt(i) == 'C') {
                cindx = i;
                ccount++;
            }
        }

        if (ccount != 1) {
            System.out.println("WA");
            return;
        }

        for (int i = 1; i < S.length(); i++) {
            if (i != cindx) {
                if (Character.isUpperCase(S.charAt(i))) {
                    System.out.println("WA");
                    return;
                }
            }
        }

        System.out.println("AC");
    }
}

Measured memory_bytes: 23764
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

char tolower(char c) {
  return (c + 0x20);
}
char toupr(char c) {
  return (c - 0x20);
}

int main(){    
  int N,K;
  string S;
  cin >> N >> K >> S;
  S[K-1] = tolower(S[K-1]);
  cout << S << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

type Queue struct {
	arr [][]int
}

func NewQueue() *Queue {
	return &Queue{
		arr: [][]int{},
	}
}

func (q *Queue) GetLength() int {
	return len(q.arr)
}

func (q *Queue) Shift() []int {
	ret := q.arr[0]
	q.arr = q.arr[1:]
	return ret
}

func (q *Queue) Push(e []int) {
	q.arr = append(q.arr, e)
}

type BFS struct {
	target   [][]rune
	h        int
	w        int
	queue    *Queue
	distance [][]int
}

func NewBFS(target [][]rune, h int, w int) *BFS {
	distance := make([][]int, h)
	for i := 0; i < h; i++ {
		distance[i] = make([]int, w)
	}
	return &BFS{
		target:   target,
		h:        h,
		w:        w,
		queue:    NewQueue(),
		distance: distance,
	}
}

func (bfs *BFS) check(a []int) bool {
	if a[0] < 0 || a[0] >= bfs.h || a[1] < 0 || a[1] >= bfs.w {
		return false
	}
	if bfs.target[a[0]][a[1]] == '#' {
		return false
	}
	if bfs.distance[a[0]][a[1]] > 0 {
		return false
	}
	return true
}

func (bfs *BFS) GetDistance(s []int, g []int) int {
	bfs.queue.Push(s)
	bfs.distance[s[0]][s[1]] = 1
	for {
		if bfs.queue.GetLength() == 0 {
			break
		}

		c := bfs.queue.Shift()
		if c[0] == g[0] && c[1] == g[1] {
			break
		}

		a1 := []int{c[0] - 1, c[1]}
		a2 := []int{c[0] + 1, c[1]}
		a3 := []int{c[0], c[1] - 1}
		a4 := []int{c[0], c[1] + 1}
		d := bfs.distance[c[0]][c[1]]
		if bfs.check(a1) {
			bfs.distance[a1[0]][a1[1]] = d + 1
			bfs.queue.Push(a1)
		}
		if bfs.check(a2) {
			bfs.distance[a2[0]][a2[1]] = d + 1
			bfs.queue.Push(a2)
		}
		if bfs.check(a3) {
			bfs.distance[a3[0]][a3[1]] = d + 1
			bfs.queue.Push(a3)
		}
		if bfs.check(a4) {
			bfs.distance[a4[0]][a4[1]] = d + 1
			bfs.queue.Push(a4)
		}
	}
	return bfs.distance[g[0]][g[1]]
}

func Solve(in io.Reader, out io.Writer) {
	scanner := bufio.NewScanner(in)
	scanner.Split(bufio.ScanLines)

	scanner.Scan()
	hw := strings.Split(scanner.Text(), " ")
	h, _ := strconv.Atoi(hw[0])
	w, _ := strconv.Atoi(hw[1])

	s := make([][]rune, h)
	for i := 0; i < h; i++ {
		scanner.Scan()
		s[i] = []rune(scanner.Text())
	}

	bfs := NewBFS(s, h, w)
	d := bfs.GetDistance([]int{0, 0}, []int{h - 1, w - 1})

	ans := -1
	if d > 0 {
		cnt := 0
		for i := 0; i < h; i++ {
			for j := 0; j < w; j++ {
				if s[i][j] == '.' {
					cnt++
				}
			}
		}
		ans = cnt - d
	}
	fmt.Fprintln(out, ans)
}

func main() {
	Solve(os.Stdin, os.Stdout)
}


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

using namespace std;

#define MAX 24

int N,x[MAX],y[MAX],r[MAX],c[MAX];

int dist(int a,int b){
    return (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]);
}

bool check(int a,int b){
    int d = dist(a,b);
    int add = r[a]+r[b],sub = r[a]-r[b];
    return ((sub*sub < d && d < add*add) || d <= sub*sub);
}

int main(){
    while(cin >> N, N){
        for(int i = 0 ; i < N ; i++){
            cin >> x[i] >> y[i] >> r[i] >> c[i];
        }
        int bit[MAX] = {0};
        for(int i = 0 ; i < N ; i++){
            for(int j = 0 ; j < i ; j++){
                if(check(i,j)) bit[i] |= (1<<j);
            }
        }
        vector<bool> dp(1<<N,0);
        dp[(1<<N)-1] = 1;
        int res = 0;
        for(int i = (1<<N)-1 ; i >= 0 ; i--){
            if(dp[i] == 0) continue;
            if(N%2 == 0 && __builtin_popcount(i) % 2 == 1) continue;
            if(N%2 == 1 && __builtin_popcount(i) % 2 == 0) continue;
	    int n = __builtin_popcount(i);
            for(int j = 0 ; j < N ; j++){
                if((i&bit[j]) > 0) continue;
                for(int k = j+1 ; k < N ; k++){
                    if(c[j] != c[k]) continue;
                    if((i&bit[k]) > 0) continue;
                    int S = i & ~((1<<j) | (1<<k));
                    dp[S] = 1;
                    res = max(res,N-n);
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 5136
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<String> listAC = new ArrayList<String>();
		List<String> listWA = new ArrayList<String>();
		List<String> listTLE = new ArrayList<String>();
		List<String> listRE = new ArrayList<String>();
		for (int i = 0; i < n; i++) {
			sc.nextLine();
			String s = sc.next();
			switch (s) {
			case "AC" : listAC.add(s); break;
			case "WA" : listWA.add(s); break;
			case "TLE" : listTLE.add(s); break;
			case "RE" : listRE.add(s); break;
			}
		}
		System.out.println("AC x " + listAC.size());
		System.out.println("WA x " + listWA.size());
		System.out.println("TLE x " + listTLE.size());
		System.out.println("RE x " + listRE.size());
//		AC x 3
//		WA x 1
//		TLE x 2
//		RE x 0

	}
}


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

const int INF = 1e9;
using ll = long long;

int n,m;

vector<pair<ll,ll>> es;

map<ll,ll> s;
int k = 0;
ll id(int v, int c){
    ll x = (ll)v<<32|c;
    if(s.count(x)) return s[x];
    s[x] = k++;
    return s[x];
}

unordered_set<int> cs[100010];

struct edge { int dst, wgt; };

vector<vector<edge>> g;

void ae(int a, int b, int w){
    g[a].push_back({b,w});
    g[b].push_back({a,w});
}

deque<int> q;
int dist[500010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    rep(i,n) cs[i].insert(id(i,0));
    rep(i,m){
        int a,b,c;
        cin >> a >> b >> c;
        --a; --b;
        ll x = id(a,c);
        ll y = id(b,c);
        es.emplace_back(x,y);
        cs[a].emplace(x);
        cs[b].emplace(y);
    }
    int k = 0;
    unordered_map<ll,int> idid;
    for(auto &p : s){
        idid[p.second] = k++;
    }
    g.assign(k,{});
    for(auto &e : es){
        ll a,b;
        tie(a,b) = e;
        int x = idid[a];
        int y = idid[b];
        ae(x,y,0);
    }

    rep(i,n){
        int h = idid[id(i,0)];
        for(auto &c : cs[i]) if(c != h) ae(h,idid[c],1);
    }

    int ans = -2;

    int src = idid[id(0,0)];
    int dst = idid[id(n-1,0)];
    fill(dist, dist+k, INF);
    dist[src] = 0;
    q.push_back(src);
    while(q.size()){
        int v = q.front();
        q.pop_front();

        if(v == dst){
            ans = dist[v];
            break;
        }

        for(auto &e : g[v]){
            if(dist[e.dst] != INF) continue;
            dist[e.dst] = dist[v] + e.wgt;
            if(e.wgt == 0) q.push_front(e.dst);
            else q.push_back(e.dst);
        }
    }

    cout << ans/2 << endl;
}


Measured memory_bytes: 117868
N,K=map(int,input().split())
from collections import defaultdict
cnt=defaultdict(int)
for a in map(int,input().split()):
    now=a
    k=0
    while now>0:
        cnt[k]+=now%2
        now//=2
        k+=1
X=bin(K)[2:]
X=(40-len(X))*"0"+X
FREE=[0]*40
FREE[0]=max(N-cnt[0],cnt[0])*pow(2,0)
for i in range(1,40):
    FREE[i]=FREE[i-1]+max(N-cnt[i],cnt[i])*pow(2,i)
FREE.append(0)
ans=-1
now=0
for i in range(40):
    if X[i]=="0":
        now+=cnt[39-i]*pow(2,39-i)
    if X[i]=="1":
        ans=max(ans,now+cnt[39-i]*pow(2,39-i)+FREE[38-i])
        now+=(N-cnt[39-i])*pow(2,39-i)
ans=max(ans,now)
print(ans)

Measured memory_bytes: 11804
#include <iostream>

int main()
{
	int N;
	int X1,Y1,Z1,W1,X2,Y2,Z2,W2,aX,aY,aZ,aW;
	std::cin>>N;
	while(N){
		for(int i=0;i<N;i++){
			std::cin>>X1>>Y1>>Z1>>W1>>X2>>Y2>>Z2>>W2;
			aX=X1*X2-Y1*Y2-Z1*Z2-W1*W2;
			aY=X1*Y2+Y1*X2+Z1*W2-W1*Z2;
			aZ=X1*Z2-Y1*W2+Z1*X2+W1*Y2;
			aW=X1*W2+Y1*Z2-Z1*Y2+W1*X2;
			std::cout<<aX<<" "<<aY<<" "<<aZ<<" "<<aW<<std::endl;
		}
		std::cin>>N;
	}
}

Measured memory_bytes: 1160
def main():
    n,m=map(int,input().split())
    ab=[map(lambda x: int(x)-1,input().split()) for _ in range(m)]
    uf=UnionFind(n)
    for a,b in ab:
        uf.union(a,b)
    ans = 0
    for s in uf.roots():
        ans = max(uf.size(s),ans)
    print(ans)

class UnionFind():
    '''Union-Find'''
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def is_same(self, x, y) -> bool:
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 126464
#include<cstdio>
#include<map>
using namespace std;
const int N=1100;
int n,a,b,q,i,x,m,known[N];char ch[N][9];
int y[N],h[N];
map<int,char>T;
struct E{int l,d;E(){}E(int _l,int _d){l=_l,d=_d;}}e[N];
inline int go(int x){
    int i=m;
    while(1){
        while(i&&e[i].l>x)i--;
        int l=e[i].l,d=e[i].d;
        if(!i||!d)break;
        x-=((x-l)/d+1)*d;
    }
    return x;
}
int main(){
    scanf("%d%d%d%d",&n,&a,&b,&q);
    for(i=1;i<=a;i++)scanf("%d%s",&known[i],ch[i]);
    for(i=1;i<=b;i++)scanf("%d%d",&y[i],&h[i]);
    y[b+1]=n+1;
    for(i=1;i<=b;i++)e[++m]=E(y[i],h[i]?y[i]-h[i]:0);
    for(i=1;i<=a;i++)T[go(known[i])]=ch[i][0];
    while(q--){
        scanf("%d",&x);
        x=go(x);
        if(T.find(x)==T.end())putchar('?');else putchar(T[x]);
    }
    putchar('\n');
    return 0;
}


Measured memory_bytes: 2836
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <tuple>
#include <stack>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define print(s) cout << s << endl
typedef long long ll;
using namespace std;

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main() {
	int n,a,b; cin >> n >> a >> b;
	cout << (n*a > b? b: n*a) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ans,f,num;
string s;

int getNum(int x){
  int res=0;
  for(int i=x;s[i]!=' '&&i!=s.size();i++){
    res=res*10+s[i]-'0';
  }
  return res;
}

int main(){
  int d[14]={0,1,2,3,4,5,6,7,8,9,10,10,10,10};
  while(1){
    getline(cin,s);
    if(s=="0")break;
    ans=0,f=0;
    for(int i=0;i<s.size();i++){
      num=getNum(i);
      while(s[i]!=' '&&i!=s.size())i++;
      ans+=d[num];
      if(num==1)f=1;
    }
    if(f&&ans+10<=21)cout<<ans+10<<endl;
    else if(ans<=21)cout<<ans<<endl;
    else cout<<0<<endl;
  }
  return 0;
}

Measured memory_bytes: 1180
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

#define int long long

signed main() {
	char c;
	cin >> c;
	if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
		cout << "vowel" << endl;
	}
	else {
		cout << "consonant" << endl;
	}
	return 0;
}



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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto&& x : v){cout << x << " ";} cout << endl
#define printVV(vv) for(auto&& v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto&& p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
// const int inf = 1e9;
const int inf = 2e18;
const int mod = 1e9 + 7;
template<typename T> using Graph = vector<vector<T>>;

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

    int A, B, N;
    cin >> A >> B >> N;

    int ans = inf;
    rep2(a, 1, N + 1) {
        rep2(b, 1, N + 1) {
            if (a > 1 && b > 1 && (a % b == 0 || b % a == 0)) {
                continue;
            }
            if (B % b != 0) {
                continue;
            }
            int AA = a * (B / b);
            ans = min(ans, abs(A - AA));
            // cerr << a << " " << b << " " << AA << " " << ans << endl;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3208
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || c > '9') break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

int main()
{
    int N, H;

    gc(N);
    gc(H);

    vector<int> vA(N, 0);
    vector<int> vB(N, 0);

    for (int i = 0; i < N; i++)
    {
        gc(vA[i]);
        gc(vB[i]);
    }

    int mx = *max_element(vA.begin(), vA.end());

    sort(vB.begin(), vB.end());
    reverse(vB.begin(), vB.end());

    int ans = H;

    for (int i = 0; i < N; i++)
    {
        H -= vB[i];

        int cnt = 0;

        // 切り上げ
        if (0 < H) cnt = (H + mx - 1) / mx;

        ans = min(ans, i + 1 + cnt);
    }

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

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <utility>
#include <iomanip>
#define ll long long

using namespace std;

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

int main()
{
    ll N, t;
    cin >> N;
    ll res;
    cin >> res;
    for (int i = 1; i < N; i++) {
        cin >> t;
        res = t / gcd(res, t) * res;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
from collections import deque
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
d = {"2":0,"4":0,"other":0}
for i in readInts():
	if i%4==0:
		d["4"]+=1
	elif i%2==0:
		d["2"]+=1
	else:
		d["other"]+=1
if d["2"]>1:
	if d["4"]>=d["other"]:
		print("Yes")
	else:
		print("No")
else:
	if d["4"]+1>=d["other"]+d["2"]:
		print("Yes")
	else:
		print("No")


Measured memory_bytes: 20640
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
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; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

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

    int n;
    cin >> n;
    map<char, int> mp;

    rep(i, n) {
        char s;
        cin >> s;
        mp[s]++;
    }

    int res = 0;
    for (auto m : mp) {
        if (m.second > 0) res++;
    }

    if (res == 3) cout << "Three" << endl;
    else cout << "Four" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main (void)
{
char a[4] ,b[4];
scanf("%s",a);
scanf("%s",b);
if(a[0]==b[2]&&a[1]==b[1]&&a[2]==b[0]){
    printf("YES");
}else{
    printf ("NO");
}
return 0;
}


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

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


Measured memory_bytes: 3088
/*
 * wafuIroha.cpp
 *
 *  Created on: 2020/02/23
 *      Author: black
 */
#include <iostream>
using namespace std;

int main(){
	string a, b, c;
	cin >> a >> b >> c;

	if ((a[a.length()-1] == b[0]) && (b[b.length()-1] == c[0])){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}

	return 0;
}


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

int main()
{
    int m, tmp, i;
    vector<int> x;
    cin >> m;
    for(i = 0; i <m; i++){
        cin >> tmp;
        x.push_back(tmp);
    }
    i--;
    cout << x[i];
    for(i-- ; i >= 0; i--)
        cout << ' ' << x[i];
    cout << endl;
}

Measured memory_bytes: 1216
#include<iostream>
#include<vector>

int main(void){
	int n;
	int r;
	std::cin >> n >> r;
	if(n < 10){
		std::cout << 100 * (10 - n) + r << std::endl;
	}else{
		std::cout << r << std::endl;
	}
	return 0;
}


Measured memory_bytes: 256
#define DEBUG 0
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T>using numr=std::numeric_limits<T>;
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; }
const int INF = 1e9;
const ll LLINF = 1e16;
const int mod = 1000000007;
const int mod2 = 998244353;
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#if DEBUG
#define debug(...)\
    do {\
        std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
        debug_impl(__VA_ARGS__);\
        std::cerr << std::noboolalpha;\
    } while (false)
#else
#define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
    { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
os << "{";
    for (auto it = v.begin(); it != v.end(); it++)
        {os << (it != v.begin() ? "," : "") << *it;}
    return os << "}";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> b(n-1);
    cin >> b;
    int ans = b[0] + b[n-2];
    for(int i = 1;i<=n-2;i++){
        ans += min(b[i],b[i-1]); 
    }
    cout << ans << endl;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using namespace std;

template <typename R>
void fft_inplace(vector<complex<R> > & f, int dir) {
    int n = f.size();
    assert(n == pow(2, log2(n)));
    R theta = dir * 2 * M_PI / n;
    for (int m = n; m >= 2; m >>= 1) {
        REP (i, m / 2) {
            complex<R> w = polar<R>(1, i * theta);
            for (int j = i; j < n; j += m) {
                int k = j + m / 2;
                complex<R> x = f[j] - f[k];
                f[j] += f[k];
                f[k] = w * x;
            }
        }
        theta *= 2;
    }
    int i = 0;
    REP3 (j, 1, n - 1) {
        for (int k = n >> 1; k > (i ^= k); ) k >>= 1;
        if (j < i) {
            swap(f[i], f[j]);
        }
    }
}
template <typename T, typename R = double>
void convolution_self_inplace(vector<T> & a, int result_n) {
    int m = 2 * a.size() - 1;
    int n = pow(2, ceil(log2(m)));
    vector<complex<R> > x(n);
    copy(a.begin(), a.end(), x.begin());
    fft_inplace(x, +1);
    vector<complex<R> > z(n);
    REP (i, n) x[i] *= x[i];
    fft_inplace(x, -1);
    a.resize(result_n);
    REP (i, result_n) a[i] = x[i].real() / n;
}

int main() {
    // input
    int n; scanf("%d", &n);
    // solve
    const int height = min(n, 50);
    vector<double> dp(n + 1);
    dp[0] = 1;
    double last_dp_n = 0;
    REP3 (j, 1, height + 1) {
        convolution_self_inplace(dp, n + 1);
        REP_R (i, n) {
            dp[i + 1] = dp[i] / (i + 1);
        }
        dp[0] = 1;
        // output
        printf("%.10lf\n", double(dp[n] - last_dp_n));
        last_dp_n = dp[n];
    }
    REP3 (j, height + 1, n + 1) {
        printf("0\n");
    }
    return 0;
}

Measured memory_bytes: 5632
NN, QQ = map(int, input().split())
SS = input('')
ll = [0]*(QQ)
rr = [0]*(QQ)
for ii in range(QQ):
    ll[ii], rr[ii] = map(int, input().split())

AC_indices = [0]*(NN)
for jj in range(NN-1):
    if SS[jj] == 'A' and SS[jj+1] == 'C':
        AC_indices[jj] += 1
        
cum_AC = [0]*(NN+1)
cum_AC[0] = AC_indices[0]
for jj in range(NN):
    cum_AC[jj+1] = cum_AC[jj] + AC_indices[jj]

for ii in range(QQ):
    print(cum_AC[rr[ii]-1]-cum_AC[ll[ii]-1])

Measured memory_bytes: 16728
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		for(int i = 0; i < n; i++) {
			int a = s.nextInt();
			int b = s.nextInt();
			int c = s.nextInt();
			
			if((a * a + b * b) == c * c) {
				System.out.println("YES");
			}
			else if((b * b + c * c) == a * a) {
				System.out.println("YES");
			}
			else if((c * c + a * a) == b * b) {
				System.out.println("YES");
			}
			else {
				System.out.println("NO");
			}
			
		}
	}
}

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

using namespace std;

using ll = long long;
using ld = long double;

#define mp make_pair

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

     // freopen("a.txt", "r", stdin);

      int n, m, sum = 0;
      cin >> n >> m;
      
      vector<int> a(n);
      for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sum += a[i];
      }

      int k = 0;
      for (int i = 0; i < n; ++i) {
            if ((a[i] * 4 * m) >= sum) {
                  k++;
            }
      }

      cout << ((k >= m) ? "Yes" : "No");

      return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include <sstream>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
#include <iomanip>
#include <numeric>
#include <iterator>
#include <math.h>
#include <list>
#include <bits/stdc++.h>

using namespace std;

int main(void){
  int N;
  cin >> N;
  vector<long> L;
  for(int i =0; i < N; i++){
    int tmp;
    cin >> tmp;
    L.push_back(tmp);
  }
  int cnt = 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(L[i] != L[j] && L[j] != L[k] && L[i] != L[k]){
          int maxi = max(max(L[i],L[j]),L[k]);
          int mini = min(min(L[i],L[j]),L[k]);
          int mid = L[i]+L[j]+L[k] - maxi - mini;
          if(mini + mid > maxi){
            cnt++;
          }
        }
      }
    }
  }
  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 3644
#include <array>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

const int N_MAX = 1e5 + 1;
vector<int> F[N_MAX];
vector<int> B[N_MAX];
vector<int> Q;
vector<int> Qc;
vector<bool> Watched;
vector<bool> Seen;

void dfs(int a) {
    if (!Seen[a]) {
        Qc.push_back(a);
    }

    Watched[a] = true;
    Seen[a] = true;

    for (auto b : F[a]) {
        if (!Seen[b]) {
            dfs(b);
        }
    }
}

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

    Watched.resize(N + 1);
    Seen.resize(N + 1);
    Q.resize(N + 1);
    Q.reserve(N + 1);

    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;

        F[a].push_back(b);
        F[b].push_back(a);
        B[a].push_back(b);
        B[b].push_back(a);
    }

    for (int i = 0; i < K; ++i) {
        int a, b;
        cin >> a >> b;

        B[a].push_back(b);
        B[b].push_back(a);
    }

    Watched.assign(N + 1, false);

    for (int a = 1; a <= N; ++a) {
        if (Watched[a]) {
            continue;
        }

        Seen.assign(N + 1, false);
        Qc.clear();

        dfs(a);

        for (auto qc : Qc) {
            Q[qc] = Qc.size() - 1;

            for (auto b : B[qc]) {
                if (Seen[b]) {
                    Q[qc]--;
                }
            }
        }
    }

    for (int i = 1; i < Q.size(); ++i) {
        cout << Q[i] << " ";
    }

    cout << endl;
}

Measured memory_bytes: 14584
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll long long
#define endl "\n"
#define lu unsigned long long
#define mod 1000000007
#define ld long double
#define f(i, n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define v vector<ll>
#define vv vector<vector<ll> >
#define vs vector<string>
#define vpr vector<pair<ll,ll>>
#define fi first
#define se second
#define all(x)  x.begin(),x.end()
#define bg(x)  x.begin()
#define sz(x)  x.size()
#define in(x,n) f(i,n) cin>>x[i]
#define out(x,n) f(i,n) cout<<x[i]<<" "
#define lcm(x, y) ((x) * (y) / __gcd(x, y))
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a)  *(min_element(a.begin(),a.end()))
#define mem(x,val) memset(x,val,sizeof(x))
#define tc    ll t;cin>>t;while(t--)
#define pi pair<int,int>
#define prfloat(val,precise) cout<<fixed<<setprecision(precise)<<val<<endl;
const ld PI = 2 * acos(0.0);
void yes(){ cout<<"YES\n";}
void no(){cout<<"NO\n";}
ll m(ll a){ return (a+mod)%mod;}
ll cel(ll x1,ll y1){ ;if((x1%y1)==0)return x1/y1;return x1/y1+1;}
ll power(ll a,ll b){ if(b==0)return 1;ll d=power(a,b/2);d=m(d*d);
if(b&1)d=m(d*a);return d;}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int h,a;cin>>h>>a;
	cout<<cel(h,a)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<queue>

using namespace std;

void part(int x, vector<int> &d, vector<vector<int> > &a, int pre)
{
	if ( x == 0 ) {
		a.push_back(d);
	}
	
	for (int i = pre; i >= 1; --i) {
		if (x - i >= 0) {
			d.push_back(i);
			part(x - i, d, a, i);
			d.pop_back();
		}
	}
}

const int NPAT = 41;
int res;
int parts[NPAT][9];

inline int ideal(const vector<int> &m)
{
	return (m[0] + 2*m[1] + 3*m[2] + 4*m[3] + 5*m[4] + 6*m[5] + 7*m[6] + 8*m[7] + 9*m[8]) / 10;
}

bool solve(vector<int> &m, int pre, int step)
{
	if ( res < step ) {
		res = step;
	}
	
	if ( step + ideal(m) <= res ) {
		return false;
	}

	for (int i = pre; i < NPAT; ++i) {
		bool packable = true;

		for (int j = 0; j < 9; ++j) {
			if (m[j] < parts[ i ][ j ]) {
				packable = false;
			}
		}

		if ( packable ) {
			// Translate
			for (int j = 0; j < 9; ++j) {
				m[j] -= parts[ i ][ j ];
			}

			solve(m, i, step + 1);
			
			// Rollback
			for ( int j = 0; j < 9; ++j ) {
				m[j] += parts[ i ][ j ];
			}

		}
	}
	return false;
}


int main(void)
{
	vector<int> d;
	vector< vector<int> > s;
	part(10, d, s, 9);

	for (int sz = 2; sz < 22; ++sz){
		for (int i = 0; i < (int)s.size(); ++i){
			if ( s[i].size() == sz ){
				for (int j = 0; j < (int)s[i].size(); ++j){
					parts[i][s[i][j] - 1]++;
				}
			}
		}
	}

	while (true) {
		int n;
		vector<int> m(9,0);
		cin >> n;

		if (n == 0) {
			break;
		}

		for (int i = 0; i < n; ++i) {
			int tmp;
			cin >> tmp;
			m[tmp - 1]++;
		}

		res = 0;

		for (int i = 0; i < 4; ++i){
			int t = min(m[8 - i], m[i]);
			m[8 - i] -= t;
			m[i] -= t;
			res += t;
		}
		if (m[4] >= 2){
			res += m[4] / 2;
			m[4] %= 2;
		}

		solve(m, 0, res);
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1224
#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,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;


ll pow_mod(ll n, ll k, ll m) {
	ll r = 1;
	for (; k > 0; k >>= 1) {
		if (k & 1)r = (r*n) % m;
		n = (n*n) % m;
	}
	return r;
}

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

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

long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

int main() {
	int n;
	cin >> n;
	vector<ll> c(n);
	REP(i, n)cin >> c[i];
	sort(ALL(c));
	reverse(ALL(c));
	if (n == 1) {
		cout << c[0] * 2 % mod << endl;
		return 0;
	}
	
	vector<ll> po2(n+10,0);
	//vector<ll> po4(n + 10, 0);
	vector<ll> kake(n+10,0);
	vector<ll> ans(n+10,0);
	kake[0] = 8;
	REP(i, n + 5) {
		po2[i] = pow_mod(2, i, mod);
		//po4[i] = pow_mod(4, i, mod);
	}
	kake[1] = 1;
	kake[2] = 3;
	kake[3] = 8;
	kake[4] = 20;
	kake[5] = 1536;

	FOR(i, 5, n + 5) {
		kake[i] = kake[i - 1] + (kake[i - 1] - po2[i - 2]) + po2[i - 1];
		kake[i] += mod;
		kake[i] %= mod;
	}

	FOR(i, 1, n + 1) {
		ans[i] = (po2[i] * kake[i]) % mod;
	}


	
	ll kotae = 0;

	FOR(i, 1, n + 1) {
		ll d = pow_mod(4, n - i, mod);
		d *= ans[i];
		d %= mod;
		d *= c[i - 1];
		d %= mod;
		kotae += d;
		kotae %= mod;
	}
	cout << kotae << endl;


}



Measured memory_bytes: 6528
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: "List[List[int]]", N: int, b: "List[int]"):
    bingo_arr = [
        A[0], A[1], A[2],
        [A[0][0], A[1][0], A[2][0]], [A[0][1], A[1][1], A[2][1]], [A[0][2], A[1][2], A[2][2]],
        [A[0][0], A[1][1], A[2][2]], [A[0][2], A[1][1], A[2][0]]
    ]
    for bingo in bingo_arr:
        cnt = 0
        for i in bingo:
            if i in b:
                cnt += 1
                if cnt == 3:
                    print(YES)
                    return
                continue
    print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = [[int(next(tokens)) for _ in range(3)] for _ in range(3)]  # type: "List[List[int]]"
    N = int(next(tokens))  # type: int
    b = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(A, N, b)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::HashSet;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
  input! {
    n:usize,
    k:usize,
    mut p:[i64;n],
    }
  
    p.sort();
  
    let sums : i64 = p.iter().take(k).sum();
   
    println!("{}", sums);
}


Measured memory_bytes: 2172
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <string>
#include <utility>

#define repd(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue();
void inputArray(int*,int);
void inputVector(vector<int>*,int);
template <typename T>
void output(T,int);
int gcd(int a,int b);

int main(){
	//source
    int k;
    cin>>k;
    int odd=0,even=0;
    repd(i,1,k+1){
        if(i%2==0){
            even++;
        }else{
            odd++;
        }
    }

    cout<<even*odd<<endl;
	return 0;
}

int inputValue(){
	int a;
	cin >> a;
	return a;
}

void inputArray(int *p,int a){
	rep(i,a){
		cin >> p[i];
	}
}

void inputVector(vector<int> *p,int a){
	rep(i,a){
		int input;
		cin >> input;
		p -> push_back(input);
	}
}

template<typename T>
void output(T a,int precision){
	if(precision > 0){
		cout << setprecision(precision) << a << "\n";
	}else{
		cout << a << "\n";
	}
}

int gcd(int a,int b){
	if(b>a){
		int temp=a;
		a=b;
		b=temp;
	}
	if(b==0){
		return a;
	}
	return (b,b%a);
}


Measured memory_bytes: 256