akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll a;
    string b;
    cin, a, b;
    if (b.size() == 1) {
        b += ".";
    }
    while (b.size() < 4) {
        b += "0";
    }
    ll c = 100 * (b[0] - '0') + (b[2] - '0') * 10 + b[3] - '0';
    a *= c;
    a /= 100;
    print(a);

    return 0;
}


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

const int MX = 1e6 + 5;

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

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

    int n; cin >> n;
    vector<int> a(n);
    vector<int> cnt(MX);

    int tot_gcd = 0;
    for (int i = 0; i < n; ++i){
        cin >> a[i];
        tot_gcd = (i == 0 ? a[i] : gcd(tot_gcd, a[i]));
        cnt[a[i]]++;
    }

    vector<bool> is_prime(MX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MX; ++i){
        if (!is_prime[i]) continue;
        for (int j = 2 * i; j < MX; j += i){
            is_prime[j] = false;
        }
    }
    vector<int> primes; primes.reserve(MX); // stricter upper bound can be fixed
    for (int i = 0; i < MX; ++i){
        if (is_prime[i])
            primes.push_back(i);
    }

    bool coprimePairFound = false;
    for (int prime: primes){
        int p_cnt = 0;
        for (int multiple = prime; multiple < MX && p_cnt < 2; multiple += prime){
            p_cnt += cnt[multiple];
        }
        if (p_cnt >= 2){
            coprimePairFound = true;
            break;
        }
    }

    if (!coprimePairFound){
        cout << "pairwise coprime\n";
    }
    else if (tot_gcd == 1){
        cout << "setwise coprime\n";
    }
    else cout << "not coprime\n";
    return 0;
}

Measured memory_bytes: 11352
n = int(input())
ans = 0
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
for i in range(n):
    ans += b[a[i]-1]
    if i > 0 and a[i] - a[i-1] == 1:
        ans += c[a[i-1]-1]
print(ans)

Measured memory_bytes: 3064
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.MSB = 1 << (N.bit_length() - 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def bisect(self, w):
        bit, N = self.tree, self.size
        i = 0
        k = self.MSB
        while k > 0:
            if i + k <= N and bit[i + k] < w:
                w -= bit[i + k]
                i += k
            k //= 2
        return i + 1

N, *A = map(int, open(0).read().split())

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10

bit = BIT(M)
for b in B:
    s = bit.sum(b - 1)
    if s > 0:
        i = bit.bisect(s)
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))


Measured memory_bytes: 71228
from heapq import heappop, heapify, heappush
def main():
    n, m = list(map(int, input().split()))
    A = list(map(lambda x: -int(x), input().split()))
    heapify(A)
    for _ in range(m):
        a = heappop(A)
        if a == 0:
            break
        a = -int(-a // 2)
        heappush(A, a)
    print(sum([-a for a in A]))

if __name__ == '__main__':
    main()


Measured memory_bytes: 14252
# BFS queue
import queue
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[100]*W for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start):
    dist = [[100]*W for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        olddist = dist[x][y]
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            xx = x+dx
            yy = y+dy
            if xx>=0 and xx<= H-1 and yy>=0 and yy<=W-1:
                if b[xx][yy] != '#':
                    if dist[xx][yy] == 100:
                        dist[xx][yy] = olddist + 1
                        if far < olddist+1:
                            far = olddist+1
                        q.put((xx,yy))
        if q.empty():
            break
    return far
res = 0
while 1:
    now = qq.get()
    res = max([res, BFS(now)])
    if qq.empty():
        break
print(res)


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

int main(){
	int n;
	while( cin >> n , n ){
		int ice[10] = {};
		for(int i=0 ; i<n ; ++i ){
			int a;
			cin >> a;
			ice[a]++;
		}
		for(int i=0 ; i<10 ; ++i ){
			for(int j=0 ; j<ice[i] ; ++j ){
				cout << "*";
			}
			if(!ice[i]) cout << "-";
			cout << endl;
		}
	}
}

Measured memory_bytes: 0
def main():
    x_max, y_max, n = map(int, input().split())
    x_min, y_min = 0, 0

    for n in range(n):
        x, y, a = map(int, input().split())

        if a == 1:
            x_min = max(x_min, x)
        elif a == 2:
            x_max = min(x_max, x)
        elif a == 3:
            y_min = max(y_min, y)
        elif a == 4:
            y_max = min(y_max, y)

    print(max(0, (x_max - x_min)) * max(0, (y_max - y_min)))

        # if (a == 1) and (x > x_min):
        #     x_min = x
        # elif (a == 2) and (x < x_max):
        #     x_max = x
        # elif (a == 3) and (y > y_min):
        #     y_min = y
        # elif (a == 4) and (y < y_max):
        #     y_max = y
        # 
        # if (x_max <= x_min) or (y_max <= y_min):
        #     print(0)
        #     return

    # print((x_max - x_min) * (y_max - y_min))

if __name__ == "__main__":

    main()


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

using namespace std;

int main() {
  int N;
  
  while(cin >> N && N) {
    
    vector<int> vec(N);
    for(int i=0; i<N; i++) cin >> vec[i];
    
    int cnt = 0;
    for(int i=0; i<N; i++) {
      for(int j=0; j<N-i-1; j++) {
	if(vec[j] > vec[j+1]) {
	  cnt ++;
	  swap(vec[j], vec[j+1]);
	}
      }
    }
    
    cout << cnt << endl;
  }
  
  return 0;
}

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

using namespace std;

const int MAX = 1005;

typedef long double ld;

ld dp[MAX][MAX];
pair<int,int> arr[MAX];
int n;

ld dist(int i,int j)
{
    return hypotl(arr[i].first-arr[j].first,arr[i].second-arr[j].second);
}

ld solve(int idx,int lst)
{
    ld &ret = dp[idx][lst];
    if(ret == ret)
        return ret;
    if(idx == n-1)
        return ret = dist(idx,idx-1) + dist(idx,lst);
    return ret = min(solve(idx+1,lst) + dist(idx,idx-1), solve(idx+1,idx-1) + dist(idx,lst));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>arr[i].first>>arr[i].second;
    sort(arr,arr+n);
    cout<<fixed<<setprecision(10)<<solve(1,0)<<"\n";
    return 0;
}



Measured memory_bytes: 19236
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int a[6] = {100, 101, 102, 103, 104, 105};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int N;
    cin >> N;
    string s;
    cin >> s;
    vector<int> A(10, 0), B(100, 0), C(1000, 0);
    rep(i, N) {
        rep(j, 100) {
            if(B[j]) {
                C[j * 10 + (s[i] - '0')] = 1;
            }
        }
        rep(j, 10) {
            if(A[j]) {
                B[j * 10 + (s[i] - '0')] = 1;
            }
        }
        A[s[i] - '0'] = 1;
    }
    int ans = 0;
    rep(i, 1000) {
        if(C[i]) {
//            output(i);
            ans++;
        }
    }
    output(ans);
    
    return 0;
}


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

int main() {
    int N, X;
    cin >> N >> X;
    int L[N];
    for (int i = 0; i < N; i++)
    {
        L[i] = 0;
        cin >> L[i];
    }
    
    int D = 0;
    for (int i = 0; i < N; i++)
    {
        D += L[i];
        if (D > X)
        {
            cout << i + 1 << endl;
            return 0;
        }
        
    }
    cout << N + 1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
 
using namespace std;
int MOD = 1000000007;

signed main(){
    string s;
    cin >> s;
    int c0 = 0;
    int c1 = 0;

    rep(i,s.size()){
        if(s[i] == '0')c0++;
        else c1++;
    }
    cout << 2*min(c0,c1) << endl;

    return 0;   
}


// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://arc059.contest.atcoder.jp/tasks/arc059_a
// rm -r -f test;oj dl http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_c

Measured memory_bytes: 512
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        int[] h = new int[n];
        int hc = 0;
        for (int i = 0 ; i < n ; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            h[i] = sc.nextInt();
            if (h[i] != 0) {
                hc = i;
            }
        }
        for (int cx = 0 ; cx <= 100; cx++) {
            for (int cy = 0; cy <= 100; cy++) {
                boolean isCenter = true;
                int H = Math.abs(x[hc] - cx) + Math.abs(y[hc] - cy) + h[hc];
                for (int i = 0 ; i < n ; i++) {
                    int div = Math.abs(x[i] - cx) + Math.abs(y[i] - cy);
                    if (h[i] != Math.max(H - div , 0)) {
                        isCenter = false;
                    }
                }
                if (isCenter) {
                    System.out.println(cx+ " " + cy + " " + H);
                    return;
                }
            }
        }

    }

}

Measured memory_bytes: 23252
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL
 
struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};
typedef struct node * Node; 
Node root;

Node treeMin(Node);
Node treeMax(Node);
Node treeSearch(Node,int);
Node treeSuccessor(Node);
void treeDelete(Node);
void insert(int);
void inorder(Node);
void preorder(Node);


int main(){
  int n, i, x;
  Node t;
  char com[20];
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  
  return 0;
}

Node treeMin(Node x){
  while( x->l != NIL ) x = x->l; 
  return x;
}

Node treeMax(Node x){
  while( x->r != NIL ) x = x->r; 
  return x;
}

Node treeSearch(Node x, int k){
  while( x != NIL && k != x->key ){
    if( k < x->key ) x = x->l;
    else x = x->r;
  } 
  return x;
}

Node treeSuccessor(Node x){
  if( x->r != NIL ) return treeMin(x->r); 
  Node y = x->p;
  while( y != NIL && x == y->r ){
    x = y;
    y = y->p;
  } 
  return y;
}
 
void treeDelete(Node z){
  Node y, x; 
 
  if(z->l == NIL || z->r == NIL) y = z;
  else y = treeSuccessor(z);
  
  if(y->l != NIL) x = y->l;
  else x = y->r;
  
  if(x != NIL) x->p = y->p;
  
  if(y->p == NIL) root = x;
  else if(y == y->p->l) y ->p->l = x;
  else y->p->r = x;
 
  if(y != x ) z->key = y->key;
 
  free(y);
}
 
void insert(int key){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = key;
  z->l = NIL;
  z->r = NIL;
 
  while( x != NIL ){
    y = x;
    if( z->key < x->key ) x = x->l;
    else x= x->r;
  }
 z->p = y;
 if( y == NIL ) root = z;
 else if ( z->key < y->key ) y->l = z;
 else y->r = z;
}
 
void inorder(Node x){
  if( x== NIL ) return;
  inorder(x->l); 
  printf(" %d", x->key); 
  inorder(x->r);
}
 
void preorder(Node x){ 
  if( x == NIL ) return; 
  printf(" %d", x->key); 
  preorder(x->l);
  preorder(x->r); 
}
 

Measured memory_bytes: 19360
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cassert>
#include <cstring>

using namespace std;

typedef long long ll;

char s[100];
char t[100];
char u[100];
int a, b;

int main() {
	scanf("%s%s%d%d%s", s, t, &a, &b, u);
	if (strcmp(s, u)==0) a--;
	if (strcmp(t, u) == 0)b--;
	printf("%d %d", a, b);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  vector<bool> h(H,false), w(W,false);
  for(int i = 0; i < H; ++i){
    cin >> S[i];
    for(int j = 0; j < W; ++j){
      if(S[i][j] == '.') continue;
      h[i] = true;
      w[j] = true;
    }
  }
  vector<string> ans;
  for(int i = 0; i < H; ++i){
    if(not h[i]) continue;
    string t;
    for(int j = 0; j < W; ++j){
      if(w[j]) t += S[i][j];
    }
    ans.push_back(t);
  }
  for(auto s : ans) cout << s << endl;
}


Measured memory_bytes: 256
N = int(input())
S = list(input())

LE = 0
LW = 0
RE = S[1:N].count("E")
RW = N-1-RE
ans = RE

if S[0] == "E":
    LE +=1
else:
    LW +=1

for i in range(1,N-1):
    if S[i]=="E":
        RE -=1
        if LW + RE < ans:
            ans = LW +RE
        LE +=1
    elif S[i]=="W":
        RW -=1
        if LW +RE < ans:
            ans = LW+RE
        LW +=1

if S[0:N-1].count("W")<ans:
    ans = S[0:N-1].count("W")
print(ans)
    
        
        

Measured memory_bytes: 8228
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <string.h>
#define ll long long


typedef struct
{
 ll A;
 ll B;
 ll B1;
}integer;

int cmpfunc(const void * a, const void * b)
{

  integer *orderA = (integer *)a;
  integer *orderB = (integer *)b;

  return ( orderA->A - orderB->A );
}

int main(void)
{

    ll N, M;
    scanf("%lld %lld",&N,&M);
    integer array[N];
    for (ll i = 0; i<N; i++)
    {
        scanf("%lld %lld",&(array[i].A),&(array[i].B));
        array[i].B1=array[i].B;

    }
    qsort(array, N, sizeof(integer), cmpfunc);

    int c = 0;
    int i = 0;
    while (M!=0)
    {
        c = array[i].B;
        array[i].B-=M;
        if (array[i].B<0)array[i].B=0;
        M-=c;
        if (M<0)M=0;
        i++;
    }
    ll res = 0;
    for (int i=0;i<N;i++)
    {
        if (array[i].B1!=array[i].B)res+=(array[i].B1-array[i].B)*array[i].A;
    }

    printf("%lld",res);

    return 0;
}



Measured memory_bytes: 4860
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int x = in.nextInt();
		long[] a = new long[n];
		for(int i=0;i<n;i++) {
			a[i] = in.nextLong();
		}
		Arrays.sort(a);
		long sum = 0;
		for(int i=0;i<n;i++) {
			sum += a[i];
			if(i==n-1) {
				if(sum==x) System.out.println(n);
				else System.out.println(n-1);
				
			}else if(sum>x) {
				System.out.println(i);
				break;
			}
			
		}
		

	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#define ll long long
#define MAX(A,B) ((A)>(B)?(A):(B))
#define MIN(A,B) ((A)<(B)?(A):(B))
#define gcd(A,B) (__gcd(A,B))
#define lcm(A,B) A/(__gcd(A,B))*B
#define MP make_pair
#define PB push_back
#define EPS 1e-9
#define ld long double
#define mod 1000000007LL
#define all(x) x.begin(), x.end()
#define usecppio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int c;
int main()
{
    int a, b, k;
    scanf("%d %d %d",&a,&b,&k);
    int g = gcd(a,b);
    for (int i = g; i>=1; i--)
    {
        if (g%i==0)
            c++;
        if (c==k)
        {
            printf("%d",i);
            return 0;
        }
    }
}

Measured memory_bytes: 256
while (True):
    a=list(map(int,input().split()))
    if (a[0]==0 and a[1]==0):
        break
    if(a[0]<a[1]):
        print(str(a[0])+" "+str(a[1]))
    else:
        print(str(a[1])+" "+str(a[0]))

Measured memory_bytes: 7572
#include<bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int e['z' - 'a'] = {};
  for(int i = 0; i < s.size(); ++i) {
    ++e[s[i] - 'a'];
  }

  bool flag = true;
  for(int i = 0; i < 'z' - 'a'; ++i) {
    if(e[i] % 2) flag = false;
  }

  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
#define int long long
int n;
int maxx,maxy,minx,miny;
signed main() {
	scanf("%lld",&n);
	minx = miny = 0xfeeddeadbeef;
	maxx = maxy = -minx;
	for(int i = 1;i <= n;++i) {
		int x,y;scanf("%lld%lld",&x,&y);
		maxx = max(maxx,x + y);
		minx = min(minx,x + y);
		maxy = max(maxy,x - y);
		miny = min(miny,x - y);
	}
	printf("%lld\n",max(maxx-minx,maxy-miny));
	return 0;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    sort(all(a));
    reverse(all(a));
    ll res = 0;
    rep(i, N){
        if(i != 0){
            res += a[i/2];
        }
    }
    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 9000
#include<bits/stdc++.h>
#define RI register int
int a,b,d;
char c[52][52];
int main(){
    std::cin>>a>>b;
    for(RI i=0;i<a;i++)
        for(RI j=0;j<b;j++)std::cin>>c[i][j];
    for(RI i=0;i<a;i++){
        for(RI j=0;j<b;j++){
            d=0;
            if(c[i][j]=='#')std::cout<<"#";
            else{
                if(c[i-1][j-1]=='#')d++;
                if(c[i-1][j]=='#')d++;
                if(c[i-1][j+1]=='#')d++;
                if(c[i][j-1]=='#')d++;
                if(c[i][j+1]=='#')d++;
                if(c[i+1][j-1]=='#')d++;
                if(c[i+1][j]=='#')d++;
                if(c[i+1][j+1]=='#')d++;
                std::cout<<d;
            }
        }
        std::cout<<std::endl;
    }
}

Measured memory_bytes: 256
import Control.Monad
import Data.Bits
import Data.Char
import Data.IORef
import Data.List
import Data.Maybe
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.ByteString.Char8 as BS

main = do
  getLine
  ns <- getIntList
  let s = foldr xor 0 ns
  putStrLn . unwords . map (show . xor s) $ ns
  
getInt :: IO Int
getInt = readLn

second :: (b -> c) -> (a, b) -> (a, c)
second f (a, b) = (a, f b)

readInt :: BS.ByteString -> Maybe (Int, BS.ByteString)
readInt = fmap (second BS.tail) . BS.readInt

getIntVec :: Int -> IO (V.Vector Int)
getIntVec n = V.unfoldrN n readInt <$> BS.getLine

getIntList :: IO [Int]
getIntList = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

getIntPair :: IO (Int, Int)
getIntPair = do
  v <- getIntVec 2
  return (v V.! 0, v V.! 1)


Measured memory_bytes: 27184
s=input()

a=[1,0,0,0]

for i in range(len(s)):
    c=s[i]
    if c=="A":
        a[1]+=a[0]
    elif c=="B":
        a[2]+=a[1]
    elif c=="C":
        a[3]+=a[2]
    elif c=="?":
        a=[ a[0]*3 ] + [ a[j]*3+a[j-1] for j in range(1,4) ]

    a=[a[i]%1000000007 for i in range(4)]
    
print(a[3])

Measured memory_bytes: 3188
using System;
using System.Collections.Generic;

enum occupant
{
build, floor, room, number
}

class Program
 {



    static void Main(string[] args)
    {
        string nyuryoku;
        char[] data;

        double num,temp;
        var result = new List<double>();

        while (true)
        {

            nyuryoku = Console.ReadLine();

            if (nyuryoku[0] == '0')
                break;
            temp = 0;
            for (int i = 0; i < nyuryoku.Length; i++)
                temp += (nyuryoku[i] - '0');
            result.Add(temp);
        }
        for (int i = 0; i < result.Count; i++)
            Console.WriteLine("{0}", result[i]);


    }

 }



Measured memory_bytes: 17868
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(auto (i) = (n)*0; (i) < (n); (i)++)
#define RNG(i, a, b) for(auto (i) = (a); (i) < (b); (i)++)
#define RBF(i, v) for(auto& (i) : (v))
#define ALL(x) (x).begin(), (x).end()

using LL = long long;
using UL = unsigned;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }

signed main() {
	int n;
	cin >> n;
	string s;
	cin >> s;

	char pre = '#';
	int ans = 0;
	REP(i, n) {
		if (s[i] != pre) {
			ans++;
		}
		pre = s[i];
	}

	col(ans);
	return 0;
}

Measured memory_bytes: 3764
#include<stdio.h>
#include<string.h>

#define M 1001
#define max(a,b) (a>b?a:b)

int lcs(char X[],char Y[]){
  int i,j;
  int m,n;
  int str[M][M];
  char t;

  m = strlen(X);
  n = strlen(Y);
  
  for(i=0; i<=m; i++){
    str[i][0] = 0;
  }

  for(i=1; i<=n; i++){
    str[0][i] = 0;
  }

  for(i=0; i<m; i++){
    for(j=0; j<n; j++){
      if(X[i] == Y[j]) str[i+1][j+1] = str[i][j] + 1;
      else str[i+1][j+1] = max(str[i][j+1],str[i+1][j]);
    }
  }

  return str[m][n];
}

int main(){
  int i;
  int n;
  char X[M],Y[M];

  scanf("%d",&n);

  for(i=0; i<n; i++){
    scanf("%s",X);
    scanf("%s",Y);
    printf("%d\n",lcs(X,Y));
  }
  
  return 0;
}



Measured memory_bytes: 5636
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> a >> b >> n;
  if (b - 1 <= n)
    x = b - 1;
  else
    x = n;
  ans = a * x / b;
  ans -= a * (x / b);
  Cout(ans);
  return 0;
}


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

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORD(i, m, n) for(int i = m; i >= n; i--)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string s;
	cin >> s;
	int N=0,S=0,E=0,W=0;
	REP(i, s.length()) {
		if(s[i]=='S')S=1;
		else if(s[i]=='N')N=1;
		else if(s[i]=='W')W=1;
		else E=1;
	}
	if(S==N&&W==E)cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define N 1000500
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
pii t[N];
inline int rd() {int r;scanf("%d",&r);return r;}
int n,m;
int main() {
    n = rd(), m = rd();
    t[1] = pii(1,1);
    for (int i=2;i<=n;i++) t[i] = pii(0, 1);
    for (int i=1;i<=m;i++) {
        int a = rd(), b = rd();
        t[b].x |= t[a].x;
        t[b].y ++;
        t[a].y --;
        if (!t[a].y) t[a].x = 0;
    }

    int ans = 0;
    for (int i=1;i<=n;i++) if (t[i].x) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    int cnt = 0;
    int next = 0;
    boolean flag = false;

    for(int i = 0; i < n; i++){a[i] = sc.nextInt();}

    if(a[0] == 2){cnt = 1; flag = true;}

    while(cnt < n && flag == false){
      next = a[next] - 1;
      cnt++;
      if(a[next] == 2){
        cnt++;
        flag = true;
        break;
      }
    }

    if(flag){System.out.println(cnt);}
    else{System.out.println(-1);}
  }
}

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

signed main() {
    int N, x;
    cin >> N >> x;

    vector<int> a(N);
    for (int& x : a) cin >> x;

    vector<vector<int>> mem(N, vector<int> (N, 1LL<<62));
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            int t = a[(i + N - k) % N];
            mem[i][k] = min(mem[i][(k ? k - 1: k)], t);
        }
    }

    int ans = 1LL<<62;
    for (int k = 0; k < N; k++) {
        int t = 0;
        for (int i = 0; i < N; i++) {
            t += mem[i][k];
        }
        ans = min(ans, t + k * x);
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

long long n,m;

int main()
{
    cin>>n>>m;
    if (n==1 || m==1) 
    {
        cout<<1;
        return 0;
    }
    cout<<(n/2+n%2)*(m/2+m%2)+(n/2)*(m/2);
    return 0;
}


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

long long mid(long long a, long long b, long long c){
	return a + b + c - max(max(a, b), c) - min(min(a, b), c);
}

int main(){
	long long a, b, c;
	cin >> a >> b >> c;
	long long ans;
	if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0){
		ans = 0;
	}else{
		ans = min({a, b, c}) * mid(a, b, c);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa):
    sum = 0

    prev = 0
    for i in range(len(aa)):
        sum += abs(prev - aa[i])
        prev = aa[i]

    sum += abs(prev)
    return sum

aa = [0] + a + [0]
price_all = 0

for i in range(len(aa) - 1):
    price_all += abs(aa[i] - aa[i + 1])

for i in range(1, len(aa) - 1):
    p = price_all
    p -= abs(aa[i - 1] - aa[i])
    p -= abs(aa[i] - aa[i + 1])
    p += abs(aa[i - 1] - aa[i + 1])
    print(p)


Measured memory_bytes: 67260
#include<stdio.h>
#include<string.h>
typedef long long int lli;
int main() {
  char s[10000];
  scanf("%s", &s);
  int l = strlen(s);
  
  if(s[l-1]=='s'){
      printf("%s%c%c", s,'e','s');
  }
  else if(s[l-1] !='s'){
      printf("%s%c", s,'s');
  }

}



Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, a = 0;
  cin >> N;
  int b = N;
  
  while(b){
  a += b % 10;
  b /= 10;
  }
  
  if(N % a == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3548
#include <iostream>

using namespace std;

int main(){
    int R, G, B, N;
    cin >> R >> G >> B >> N;
    long ans = 0;
    for(int r = 0; r*R <= N; r++){
        for(int g = 0; r*R+g*G <= N; g++){
            if((N-(r*R+g*G))%B == 0){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <istream>
#include <ostream>

#include <cstdlib>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define rep(i,n) for(ll i=0; i < (n); ++i)
#define rrep(i,n) for(ll i=((n)-1); i >= 0; --i)

#define OPLT(T) bool operator<(const T & lop_, const T & rop_)
#define OPEQ(T) bool operator==(const T & lop_, const T & rop_)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

istream& operator>>(istream& istr, __float128& obj) { double d; istr >> d; obj = d; return istr; };
ostream& operator<<(ostream& ostr, __float128& obj) { ostr << static_cast<double>(obj); return ostr; };

int uf[100100];
void init() {
	rep(i,100100) uf[i] = i;
}
int find(int a) {
	if(uf[a] == a) return a;
	return uf[a] = find(uf[a]);
}
int same(int a, int b) {
	return find(a) == find(b);
}
bool mage(int a, int b) {
	if(find(a) == find(b)) return false;
	uf[find(a)] = find(b);
	return true;
}

int main() {
	int N; cin >> N;
	vector<pll> x(N), y(N);
	vector<pair<ll,pii> > d;
	rep(i,N) {
		cin >> x[i].fi >> y[i].fi;
		x[i].se = y[i].se = i;
	}
	sort(all(x));
	sort(all(y));
	for(int i = 1; i < N; i++) {
		d.push_back(pair<ll,pii>(abs(x[i].fi-x[i-1].fi),pii(x[i].se, x[i-1].se)));
		d.push_back(pair<ll,pii>(abs(y[i].fi-y[i-1].fi),pii(y[i].se, y[i-1].se)));
	}
	sort(all(d));
	ll res = 0;
	init();
	rep(i,d.size()) {
		if(mage(d[i].se.fi, d[i].se.se))
			res += d[i].fi;
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 9584
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    int i,n,ans=0;
    cin>>n;
    ans=n*(n-1)/2;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var nk = Console.ReadLine().Split();
        var n = int.Parse(nk[0]);
        var k = int.Parse(nk[1]);
        var d = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        var ans = 0;

        for (int a = 0; a <= Math.Min(n, k); a++)
        {
            for (int b = 0; a + b <= Math.Min(n, k); b++)
            {
                var list = new List<int>();

                for (int i = 0; i < a; i++)
                {
                    list.Add(d[i]);
                }

                for (int i = 0; i < b; i++)
                {
                    list.Add(d[n - i - 1]);
                }

                list.Sort();

                var c = k - a - b;
                var sum = 0;
                for (int i = 0, j = 0; i < list.Count; i++)
                {
                    if (list[i] < 0 && j < c)
                    {
                        j++;
                    }
                    else
                    {
                        sum += list[i];
                    }
                }

                ans = Math.Max(ans, sum);
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11220
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
#define ll long long int

int main(){
    int n, k;
    cin>>n>>k;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v.begin(), v.end());
    ll sum=0;
    for(int i=0;i<k;i++){
        sum+=v[i];
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



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

  int n;
  cin >> n;
  vector<int> p(n);
  rep(i, n) {
    cin >> p[i];
    p[i]--;
  }

  vector<int> a(n);
  rep(i, n) a[p[i]] = i;
  int ans = 0, res = 0, idx = -1;
  rep(i, n) {
    if (a[i] > idx) res++;
    else {
      chmax(ans, res);
      res = 1;
    }
    idx = a[i];
  }
  chmax(ans, res);
  ans = n - ans;
  cout << ans << '\n';
  




  
  return 0;
}

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

typedef long long ll;
typedef  unsigned long long ull;
const ll mod = 1e9 + 7;
const int N=2000000;
const int M=2000;

void Run()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
ll n,cnt,res,k,m,t,b,c,z,a;
main()
{
   long n;
    cin >> n;
 
    long ans = 1000 - (n % 1000);
    if (ans == 1000) ans = 0;
    printf("%lld\n", ans);
}



Measured memory_bytes: 3704
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();

        Scanner inp = new Scanner(System.in);

        int end = 1;
        while (end != 0) {
            int num1 = inp.nextInt();
            int num2 = inp.nextInt();

            if (num1 == 0 && num2 == 0) {
                end = 0;
            } else {
                list1.add(num1);
                list2.add(num2);
            }
        }

        /*
        for (int i = 0; i < list1.size(); i++) {
            System.out.println(list2.get(i) + " " + list1.get(i));
        } */

        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) > list2.get(i)) {
                int temp = list1.get(i);

                list1.remove(i);
                list1.add(i, list2.get(i));

                list2.remove(i);
                list2.add(i, temp);
            }
        }

        for (int i = 0; i < list1.size(); i++) {
            System.out.println(list1.get(i) + " " + list2.get(i));
        }
    }
}


Measured memory_bytes: 36072
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1<<29;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}
inline int powerexp(int a,int b,int m = MOD){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
inline int modinv(int a){return powerexp(a,MOD-2,MOD);}
inline int lcm(int a,int b){int g=__gcd(a,b);return a/g*b;}

//-------------------< start here >-------------------------// 
const int N = 5005;
int fact[N], invfact[N];
int n,k ;
void pre(){
   fact[0] = 1;
   invfact[0] = modinv(fact[0]);
   for(int i = 1; i < N ; i++){
	     fact[i] = i * fact[i-1];
	     fact[i] %= MOD;
	     invfact[i] = modinv(fact[i]); 
	  }	
}
int nCr(int n,int r){
  if(r > n)
     return 0;
  int ret = fact[n];
  ret *= invfact[n-r];
  ret %= MOD;
  ret *= invfact[r];
  ret %= MOD;
  return ret;  	
}
int fastnCr(int n,int r){
	if(n<r or r<0)return 0;
	int ans=1;
	for(int i=0;i<r;i++){
		ans*=(n-i);ans%=MOD;
	}
	ans*=invfact[r];
return ans%MOD;
}
void solve(){
	pre();
	cin >> n >> k;
	int blue = k, red = n - k;
	for(int i = 1; i <= k; i++){
	   int ret = fastnCr(red + 1, i);
	   int y = fastnCr(blue - 1,i - 1);
	   ret *= y;
	   ret %= MOD;
	   cout << ret << endl; 	
	}
}
//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
   #endif
}


Measured memory_bytes: 384
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int N,B;
vector<pair<pair<int,int>,short> >item;//<value,weight>,i
vector<int>bag;

int main(){
	int i,j,r,m;
	scanf("%d%d",&N,&B);
	item.resize(N);
	bag.resize(B+1);bag[0]=1;
	for(i=0;i<N;i++)scanf("%d%d",&item[i].first.first,&item[i].first.second),item[i].second=i;
	for(i=0;i<N;i++){
		for(j=item[i].first.second;j<=B;j++){
			if(bag[j-item[i].first.second]&&bag[j]<bag[j-item[i].first.second]+item[i].first.first){
				bag[j]=bag[j-item[i].first.second]+item[i].first.first;
			}
		}
	}
	for(r=i=0;i<=B;i++){
		if(r<bag[i]){
			r=bag[i];
			m=i;
		}
	}
	printf("%d\n",r-1);
}

Measured memory_bytes: 1072
import itertools as itl

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))
S = []

for i in range(n):
    cmb = list(itl.combinations(A, i+1))
    for j in cmb:
        S.append(sum(j))

for m in M:
    flg = False
    for s in S:
        if s == m:
            flg = True
            break
    if flg:
        print("yes")
    else:
        print("no")



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

#define ll long long

int n,m;
int L,R,D;
vector<pair<int,int> >mp[100100];
int dis[100100];
bool vis[100100];
int flag;

void dfs(int u,int pre)
{
    if(!flag) return;
     int sz=mp[u].size();
     pair<int,int>tmp;
     for(int i=0;i<sz;++i)
     {
        tmp=mp[u][i];
        if(vis[tmp.first])
        {
            if(dis[u]+tmp.second!=dis[tmp.first])
            {
                flag=0;return;
            }
        }
        else
        {
            vis[tmp.first]=1;
            dis[tmp.first]=dis[u]+tmp.second;
            dfs(tmp.first,u);
        }
     }
}

int main(int argc, char const *argv[])
{
    /* code */
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&L,&R,&D);
        mp[R].push_back(make_pair(L,D));
        mp[L].push_back(make_pair(R,-D));
    }
    flag=1;
    for(int i=1;i<=n;++i) if(!vis[i])
    {
        vis[i]=1;
        dfs(i,-1);
    }
    if(flag) puts("Yes");else puts("No");
    return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>  // sort, 二分探索, etc
#include <iomanip>  // setprecision (浮動小数点の出力の誤差)
#include <map>
#include <queue>
#include <set>
#include <stack>

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=a,i##_len=(b);i<i##_len;++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define cauto const auto&
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define SIZE(x) ((ll)(x).size()) // sizeをsize_tからllに直しておく
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define INF 1000000000000
#define MOD 1000000007
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

using namespace std;
using ll = long long;
using ull = unsigned long long;

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

const char newl = '\n';

ll qp(ll a,ull b){ll ans=1;do{if(b&1u)ans*=a;a*=a;}while(b>>=1u);return ans;}
ll qp(ll a,ull b,ll mod){ll ans=1;do{if(b&1u)ans=ans*a%mod;a=a*a%mod;}while(b>>=1u);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll comb(int n, int r) {
    vector<vector<ll> > v(n+1, vector<ll>(r+1, 0));
    for(int i=0;i<n+1;i++) {v[i][0]=1; if(i < r+1)v[i][i]=1; }
    for(int i=1;i<n+1;i++) {for(int j=1;j<min(i,r+1);j++) {v[i][j]=v[i-1][j-1]+v[i-1][j];}}
    return v[n][r];
}

// INT_MAX   = 2.1e+09 (2147483647)
// LONG_MAX  = 9.2e+18 (9223372036854775807)
// LLONG_MAX = 9.2e+18 (9223372036854775807)


int main() {
    ll N, M, X;
    cin >> N >> M >> X;
    vector<ll> costs;
    vector<vector<ll> > aas;
    rep(n, N) {
        ll c; cin >> c; costs.push_back(c);
        vector<ll> as;
        rep(m, M) {
            ll a; cin >> a; as.push_back(a);
        }
        aas.push_back(as);
    }

    vector<ll> total_costs;
    rep (i, qp(2, N)) {
        vector<ll> total_as = vector<ll>(M, 0);
        ll cost = 0;
        rep (n, N) {
            if ((i >> n) & 1) {
                rep(m, M) {
                    total_as[m] += aas[n][m];
                }
                cost += costs[n];
            }
        }
        bool flag = true;
        for (cauto val : total_as) {
            if (val < X) {
                flag = false;
            }
        }
        if (flag) {
            total_costs.push_back(cost);
        }
    }

    if (!total_costs.empty()) {
        cout << MIN(total_costs) << newl;
    } else {
        cout << "-1" << newl;
    }

    return 0;
}


Measured memory_bytes: 3220