akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(j,n) for(int i=(int)(j);i<(int)(n);i++)
#define int int64_t
signed main(){
  int ans=0;
  int N,K;
  cin>>N>>K;
  int X=(K-1)*K/2;
  X%=1000000007;
  vector<int> A(N);
  rep(0,N) cin>>A[i];
  rep(0,N){int count=0,sum=0;
           for(int j=0;j<N;j++){if(A.at(j)<A.at(i)){sum++;
                                                    if(j>i)count++;}
                               }
           ans+=count*K;
           ans+=sum*X;
           if(ans>=1000000007) ans%=1000000007;
             }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
def scalc():
    while (True):
        a, op, b = input().split(" ")
        a = int(a)
        b = int(b)
        if op == '?':
            break
        elif op == '+':
            print(a+b)
        elif op == '-':
            print(a-b)
        elif op == '*':
            print(a*b)
        elif op == '/':
            print(int(a/b))
        else :
            break
    return 0

if __name__ == "__main__":
    ret = scalc()


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

int main() {
    int N;
    int d[110];
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> d[i];
    
    int num[110] = {0};
    for (int i = 0; i < N; ++i) {
        num[d[i]]++;
    }
  
    int res = 0;
    for (int i = 1; i <= 100; ++i) {
        if (num[i]) {
            ++res;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  long long int n,a,b;
  cin>>n;
  cin>>a>>b;
  int c=0;
  for(int i=a;i<=b;i++)
  {
    if(i%n==0)
    {
      c=1;break;
    }
  }
  if(c==1)
    cout<<"OK";
  else
    cout<<"NG";
}


Measured memory_bytes: 3624
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int N; cin >> N;
    string S; cin >> S;

    vector<int> CNT{};
    int cnt;
    if (S[0] == '(') cnt = 1;
    else cnt = -1;

    for (int i = 1; i < N; i++)
    {
        if (S[i - 1] == S[i])
        {
            cnt += cnt / abs(cnt);
        }
        else
        {
            CNT.push_back(cnt);
            cnt = cnt * (-1) / abs(cnt);
        }
    }
    CNT.push_back(cnt);

    if (CNT[0] < 0)
    {
        CNT.insert(CNT.begin(), CNT[0] * (-1));
    }

    if (CNT[CNT.size() - 1] > 0)
    {
        CNT.insert(CNT.end(), CNT[CNT.size() - 1] * (-1));
    }

    cnt = 0;
    for (int j = 0; j < CNT.size(); j++)
    {
        cnt += CNT[j];
        if (cnt < 0)
        {
            CNT[0] += cnt * (-1);
            cnt = 0;
        }
    }
    if (cnt > 0)
    {
        CNT[CNT.size() - 1] += cnt * (-1);
    }

    /*
    for (int a : CNT)
    {
        cout << a << " ";
    }
    cout << endl;
    */

    string ans = "";
    for (int p : CNT)
    {
        if (p > 0)
        {
            for (int k = 1; k <= abs(p); k++) ans += "(";
        }
        else
        {
            for (int k = 1; k <= abs(p); k++) ans += ")";
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

#define ll long long
#define rep(i, n) for (long double i = 0; i < n; i++)
// #define req(j, n) for (ll j = 1; j < (n+1); j++)
// #define rer(k, n) for (ll k = 1; k < (n+1); k++)


int main()
{   
    ll N;
    cin >> N;
    ll count;
    vector<ll> a(N);
    ll ans=0;
    int wi = 0;
    rep(i, N) {
        cin >> a[i];
        if (a[i] == 0) {
            wi = 1;
            cout << "0" << endl;
            break;
        }
    }
    if (wi == 0) {
        rep(i, N) {
            if (i == 0) {
                ans = a[i];
            } else {
                count = powl(10.0,18.0) / a[i];
                if (count < ans) {
                    cout << "-1" << endl;
                    return 0;
                }
                ans = ans * a[i];
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 4000
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    vector<P> v(n);
    vector<int> pos(n);
    int fact = 1;
    for(int i = 1;i<=n;i++){
        fact*=i;
    }
    rep(i,n){
        cin >> v[i].first >> v[i].second;
        pos[i] = i;
    }
    double res = 0;
    do{
        rep(i,n-1){
            int x = v[pos[i]].first - v[pos[i+1]].first;
            int y = v[pos[i]].second-v[pos[i+1]].second;
            res+=sqrt(x*x+y*y);
        }
    }while(next_permutation(pos.begin(),pos.end()));
    printf("%.12lf\n",res/fact);
    return 0;
}

Measured memory_bytes: 256
L, A, B, M = gets.split.map(&:to_i)

require 'matrix'

def mpow(x, n)
  ret = Matrix.I(3)
  while n > 0
    if n.even?
      x = (x * x).map{|e| e % M}
      n >>= 1
    else
      ret = (ret * x).map{|e| e % M}
      n -= 1
    end
  end
  ret
end

s = ->(n){A + B*n}
u = ->(k){(0 ... L).bsearch{|i| s[i] >= 10**(k - 1)} || L}
x = ->(k, n){mpow(Matrix[[10**k, 1, 0], [0, 1, B], [0, 0, 1]], n)}
m = 19.downto(1).each_cons(2).map{|a, b| x[b, u[a] - u[b]]}.inject(:*) * Matrix.column_vector([0, A, 1])
puts m.first % M

Measured memory_bytes: 2684
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int H,W,K;
const int MAX_HW = 810;
const int MAX_K = MAX_HW * MAX_HW;
char board[MAX_HW][MAX_HW];
bool visited[MAX_HW][MAX_HW];
int sy,sx;
int main() {
  cin >> H >> W >> K;
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> board[i][j];
      if (board[i][j] == 'S'){
        sy = i;
        sx = j;
      }
    }
  }
  queue<pair<pii, int>> que;
  que.emplace(mp(mp(sy, sx), 0));
  while (not que.empty()){
    auto p = que.front();
    que.pop();
    auto pos = p.first;
    int cnt = p.second;
    if (cnt > K){
      break;
    }
    int py,px;
    py = pos.first;
    px = pos.second;
    if (py == 0 or py == H - 1 or px == 0 or px == W - 1){
      cout << 1 << endl;
      return 0;
    }
    if (visited[py][px])continue;
    visited[py][px] = true;
    for (int i = 0; i < 4; i++){
      int ny = py + dy[i];
      int nx = px + dx[i];
      if (visited[ny][nx])continue;
      if (board[ny][nx] == '#')continue;
      que.emplace(mp(mp(ny, nx), cnt + 1));
    }
  }
  int result = 1 << 30;
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      if (visited[i][j]){
        int c1,c2,c3,c4;
        c1 = abs(i - 0);
        c2 = abs(i - (H - 1));
        c3 = abs(j - 0);
        c4 = abs(j - (W - 1));
        result = min(result, c1);
        result = min(result, c2);
        result = min(result, c3);
        result = min(result, c4);
      }
    }
  }
  cout << (result + (K - 1)) / K + 1 << endl;
  return 0;
}


Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        boolean found = false;
        char[][] in = new char[N][N];
        char[][] temp = new char[M][M];
        for (int i=0; i<N; i++) {
            in[i] = sc.next().toCharArray();
        }
        for (int i=0; i<M; i++) {
            temp[i] = sc.next().toCharArray();
        }
        for (int i=0; i<=N-M; i++) {
            for (int j=0; j<=N-M; j++) {
                found = true;
                label1:for (int ii=0;ii<M; ii++) {
                    for (int jj=0; jj<M; jj++) {
                        if (in[i+ii][j+jj]!=temp[ii][jj]) {
                            found = false;
                            break label1;
                        }
                    }
                }
                if (found) {
                    System.out.println("Yes");
                    sc.close();
                    return;
                }
            }
        }
        System.out.println("No");
        sc.close();
    }

}


Measured memory_bytes: 22996
package main

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

func main() {
	stdin := bufio.NewScanner(os.Stdin)
	for stdin.Scan() {
		n, _ := strconv.Atoi(stdin.Text())
		if n == 0 {
			break
		}
		stdin.Scan()
		res := stdin.Text()
		prev := ""
		c := 0
		for ; res != prev; c++ {
			elm := strings.Split(res, " ")
			cnt := make(map[string]int)
			nxt := make([]string, n)
			for _, v := range elm {
				cnt[v]++
			}
			for i, v := range elm {
				nxt[i] = strconv.Itoa(cnt[v])
			}
			prev = res
			res = strings.Join(nxt, " ")
		}
		if res == prev {
			fmt.Println(c - 1)
			fmt.Println(res)
		}
	}
}



Measured memory_bytes: 1292
#include <bits/stdc++.h>
using namespace std;
int main(){
int A,B,C,D,E,F;
  cin>>A>>B>>C>>D;
  E=A+B;F=C+D;
  if(E>F){
    cout<<"Left"<<endl;
  }else if(E<F){
  cout<<"Right"<<endl;
  }else{
  cout<<"Balanced"<<endl;
  }





}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 200100
#define int long long 
using namespace std;
typedef long long ll;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
int n,A,B,x,y,tot;
signed main()
{
	n=read(); A=read(); B=read();
	x=read(); for(int i=2;i<=n;i++)
	{
		y=read(); if(1ll*A*(y-x)>B) tot+=B;
		else tot+=(1ll*A*(y-x));
		x=y;
	}
	cout << tot << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std; typedef long long ll; int an=0; const ll INF = 1e18; const ll MOD = 1e9+7;
typedef pair<int,int> P; const int xx[4]={1,-1,0,0}, yy[4]={0,0,1,-1};
int a[90][90]; int n,m; struct tlp {int x,y,cs;};

int main(){
  while(true) {
    int n,m; cin>>n>>m; if (n==0) break;
    ll c[m], x[n];
    for(int i=0;i<m;i++) cin>>c[i];
    for(int i=0;i<n;i++) cin>>x[i];
    ll p[2][256]; fill(p[0],p[2],INF); p[0][128]=0;
    for(int i=0;i<n;i++) {
      int bb=i%2, aa=(i+1)%2;
      for(int j=0;j<256;j++) p[aa][j]=INF;
      for(ll j=0;j<256;j++) {
        if (p[bb][j] == INF) continue;
        for(int k=0;k<m;k++) {
          int pc = max(0LL,min(255LL,j+c[k])); //cout<<pc<<endl;
          p[aa][pc] = min(p[aa][pc], p[bb][j]);
        }
      }
      /*
      for(int j=0;j<256;j++) {
        if (p[aa][j]!=INF) cout<<"("<<j<<":"<<p[aa][j]<<") "<<endl;
      }*/
      for(ll j=0;j<256;j++) {
        if (p[aa][j] != INF) p[aa][j] += (x[i]-j) * (x[i]-j);
      }
    }
    ll an=INF;
    for(int j=0;j<256;j++) {
      //if (p[n%2][j]!=INF) cout<<"("<<j<<":"<<p[n%2][j]<<") "<<endl;
      an = min(p[n%2][j],an);
    }
    cout<<an<<endl;
  }
}


Measured memory_bytes: 3276
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
#define pi 3.141592653589
#define eps 1e-6
//#define p 2173412051LL
//#define sz 2

using namespace std;

bool ok[ 200010 ];

int main() {
	int n, ma = 0;
	int x;
	ok[ 0 ] = true;
	scanf( "%d", &n );
	for( int i = 0; i < n; ++i ) {
		scanf( "%d", &x );
		ok[ x ] |= ok[ x - 1 ];
		if( ok[ x ] )
			ma = max( ma, x );
	}
	if( ma == 0 )
		ma = n + 1;
	printf( "%d", n - ma );
	return 0;
}

Measured memory_bytes: 3976
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K, N;
    cin >> N >> K;
    vector<ll> hi(N);
    REP(i, N)
    cin >> hi.at(i);

    sort(hi.begin(), hi.end());

    ll tmp = hi.at(K - 1) - hi.at(0);
    REP(j, N - K + 1)
    {
        ll x = hi.at(K - 1 + j) - hi.at(j);
        if (tmp > x)
            tmp = x;
    }

    cout << tmp << endl;
}

Measured memory_bytes: 1024
h, w, a, b = map(int, input().split())


class Combination:
    """
    Usage：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 10 ** 9 + 7
comb = Combination(h+w, mod)

ans = 0
for i in range(h-a):
    ans += comb(b+i-1, i) * comb(w-b+h-i-2, w-b-1)
    ans %= mod

print(ans)

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

int cnt[9];

int main() {
  int n;
  cin >> n;
  rep(i, n) {
    int a;
    cin >> a;
    ++cnt[min(8, a/400)];
  }
  int l = 0, r = 0;
  rep(i, 8) if (cnt[i]) ++l;
  r = l + cnt[8];
  l = max(1, l);
  cout << l << " " << r << endl;
  return 0;
}

Measured memory_bytes: 256
#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(){
  ll n,a,b;
  cin >> n >> a >> b;
  if(a == 0) cout << 0 << endl;
  else{
    ll amari = n%(a+b);
    if(amari > a) amari = a;
    ll kai = n/(a+b);
    cout << kai*a + amari << endl;
  }

}


Measured memory_bytes: 3628
use std::io::*;
use std::str::*;

fn read<T: FromStr>(s: &mut StdinLock) -> Option<T> {
    let s = s.by_ref()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

pub fn main() {
    use std::collections::HashMap;

    let stdin = stdin();
    let mut stdin = stdin.lock();

    let n: u32 = read(&mut stdin).unwrap();
    let blue: Vec<String> = (0..n).map(|_| read(&mut stdin).unwrap()).collect();

    let m: u32 = read(&mut stdin).unwrap();
    let red: Vec<String> = (0..m).map(|_| read(&mut stdin).unwrap()).collect();

    let mut map = HashMap::new();

    for bc in blue {
        if let Some(x) = map.get_mut(&bc) {
            *x += 1;
            continue;
        }

        map.insert(bc, 1);
    }

    for rc in red {
        if let Some(x) = map.get_mut(&rc) {
            *x -= 1;
            continue;
        }

        map.insert(rc, -1);
    }

    let max_value = map.values().max().unwrap();

    if max_value > &0 {
        println!("{}", max_value);
    } else {
        println!("0");
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<20);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n;
vector<pair<int, int> > adj[MAX];  // 重み付き有向グラフの隣接リスト表現

void dijkstra() {
  priority_queue<pair<int, int> > PQ;
  int color[MAX];
  int d[MAX];
  for ( int i = 0; i < n; i++ ) {
    d[i] = INFTY;
    color[i] = WHITE;
  }

  d[0] = 0;
  PQ.push(make_pair(0, 0));
  color[0] = GRAY;

  while ( !PQ.empty() ) {
    pair<int, int> f = PQ.top(); PQ.pop();
    int u = f.second;

    color[u] = BLACK;

    // 最小値を取り出し、それが最短でなければ無視
    if ( d[u] < f.first * (-1) ) continue;

    for ( int j = 0; j < adj[u].size(); j++ ) {
      int v = adj[u][j].first;
      if ( color[v] == BLACK ) continue;
      if ( d[v] > d[u] + adj[u][j].second ) {
        d[v] = d[u] + adj[u][j].second;
        // priority_queue はデフォルトで大きい値を優先するため -1 を掛ける
        PQ.push(make_pair(d[v] * (-1), v));
        color[v] = GRAY;
      }
    }
  }

  for ( int i = 0; i < n; i++ )
    cout << i << " " << ( d[i] == INFTY ? -1 : d[i] ) << endl;
}

int main() {
  int k, u, v, c;

  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    cin >> u >> k;
    for ( int j = 0; j < k; j++ ) {
      cin >> v >> c;
      adj[u].push_back(make_pair(v, c));
    }
  }

  dijkstra();

  return 0;
}


Measured memory_bytes: 8000
#include<stdio.h>

int main(void){
    long int a, b, k;
    scanf("%ld""%ld""%ld", &a, &b, &k);
    if(a < k){
        k -= a;
        a = 0;
        if(b < k){
            printf("%d %d\n", 0, 0);
            return 0;
        }else{
            b -= k;
            printf("%ld %ld\n", a, b);
            return 0;
        }
    }else{
        a -= k;
        printf("%ld %ld\n", a, b);
        return 0;
    }

    printf("%ld %ld\n", a, b);
    return 0;
}

Measured memory_bytes: 128
def create_dice(nums):
    a, b, c, d, e, f = nums
    ver = [a, b, f, e]
    hor = [b, c, e, d]
    return Dice(ver, hor, nums)


class Dice:
    def __init__(self, v, h, r):
        self.ver = v
        self.hor = h
        self.raw = r

    def __str__(self):
        l = [self.ver[0], self.ver[1], self.hor[1],
             self.hor[3], self.ver[3], self.ver[2]]
        s = map(str, l)
        return "".join(s)

    def v2h(self):
        self.hor[0] = self.ver[1]
        self.hor[2] = self.ver[3]

    def h2v(self):
        self.ver[1] = self.hor[0]
        self.ver[3] = self.hor[2]

    def roll(self, direction):
        if direction == 'N':
            tmp1 = self.ver[0]
            tmp2 = self.ver[1:]
            self.ver = tmp2 + [tmp1]
            self.v2h()
        elif direction == 'S':
            tmp1 = self.ver[-1]
            tmp2 = self.ver[:-1]
            self.ver = [tmp1] + tmp2
            self.v2h()
        elif direction == 'E':
            tmp1 = self.hor[0]
            tmp2 = self.hor[1:]
            self.hor = tmp2 + [tmp1]
            self.h2v()
        elif direction == 'W':
            tmp1 = self.hor[-1]
            tmp2 = self.hor[:-1]
            self.hor = [tmp1] + tmp2
            self.h2v()


def match_dice(d1, d2):
    if str(d1) == str(d2):
        return True
    return False


def test(d1, d2):
    s1 = set(d1.raw)
    s2 = set(d2.raw)
    if s1 != s2:
        return False

    for v in range(2):
        if match_dice(d1, d2):
            return True

        for h in range(3):
            if match_dice(d1, d2):
                return True
            d2.roll("E")

        d2.roll("N")

    for v in range(2):
        if match_dice(d1, d2):
            return True

        for h in range(3):
            if match_dice(d1, d2):
                return True
            d2.roll("E")

        d2.roll("S")

    for v in range(2):
        if match_dice(d1, d2):
            return True

        for h in range(3):
            if match_dice(d1, d2):
                return True
            d2.roll("E")

        d2.roll("N")

    return False


def check(dices):
    for i in range(len(dices) - 1):
        for j in range(i + 1, len(dices)):
            t = test(dices[i], dices[j])
            if t:
                return True

    return False

data_count = int(input())
dices = []
for _ in range(data_count):
    s = list(map(int, input().split(" ")))
    d = create_dice(s)
    dices.append(d)

result = check(dices)
if not result:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 5620
#include <cstdio>
#include <cmath>
using namespace std;
int len = 10, a, b;
int main() {
	scanf("%d%d", &a, &b);
	while (len <= b) len *= 10;
	a = a * len + b;
	b = sqrt(a);
	if (b * b == a) puts("Yes");
	else puts("No");
}

Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

template<int MOD>
class ModInt {
public:
    ModInt() :value(0) {}
    ModInt(long long val) :value((int)(val<0 ? MOD + val % MOD : val % MOD)) { }

    ModInt& operator+=(ModInt that) {
        value = value + that.value;
        if (value >= MOD)value -= MOD;
        return *this;
    }
    ModInt& operator-=(ModInt that) {
        value -= that.value;
        if (value<0)value += MOD;
        return *this;
    }
    ModInt& operator*=(ModInt that) {
        value = (int)((long long)value * that.value % MOD);
        return *this;
    }
    ModInt &operator/=(ModInt that) {
        return *this *= that.inverse();
    }
    ModInt operator+(ModInt that) const {
        return ModInt(*this) += that;
    }
    ModInt operator-(ModInt that) const {
        return ModInt(*this) -= that;
    }
    ModInt operator*(ModInt that) const {
        return ModInt(*this) *= that;
    }
    ModInt operator/(ModInt that) const {
        return ModInt(*this) /= that;
    }
    ModInt pow(long long k) const {
        ModInt n = *this, res = 1;
        if (k < 0) {
            k = -k;
            n = n.inverse();
        }
        while (k) {
            if (k & 1)res *= n;
            n *= n;
            k >>= 1;
        }
        return res;
    }
    ModInt inverse() const {
        long long a = value, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return ModInt(u);
    }
    int toi() const { return value; }

private:
    int value;
};
typedef ModInt<1000000007> mint;
ostream& operator<<(ostream& os, const mint& x) {
    os << x.toi();
    return os;
}

void solve() {
    int N;
    cin >> N;
    vi C(N);
    rep(i, N) {
        cin >> C[i];
    }
    sort(C.rbegin(), C.rend());

    mint two = 2, ans = 0;
    rep(i, N) {
        mint x = two.pow(i - 1)*(i + 2);
        mint y = two.pow(N - 1 - i);
        ans += x * y * C[i];
    }
    ans *= two.pow(N);

    cout << ans  << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 D; cin >> D;
    if (D == 25) cout << "Christmas" << endl;
    else if (D == 24) cout << "Christmas Eve" << endl;
    else if (D == 23) cout << "Christmas Eve Eve" << endl;
    else if (D == 22) cout << "Christmas Eve Eve Eve" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define IOS                                                                    \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0);                                                                  \
  cout.tie(0)
#define ll long long int
#define ld long double
#define el '\n'
#define PI (ld)3.14159265358979323846
#define inf (ll)1000000000
#define mod (ll)1000000007
#define mod1 (ll)998244353
#define fo(i, n) for (long long i = 0; i < int(n); i++)
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define sz(a) a.size()
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define vl vector<ll>
//#define x ff
//#define y ss
#define pt(a) for(auto it:a)cout<<it<<" ";cout<<endl;
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;

double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }

/*vector<int> parent, rak;

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rak[a] < rak[b])
            swap(a, b);
        parent[b] = a;
        rank[a]+=rank[b];
    }
}*/

long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1)
      res = res * a % m;
      a = a * a % m;
      b >>= 1;
  }
  return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll ans =extend_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;

    return ans;
}
ll inverse(ll a,ll m){
    ll x,y;
    extend_gcd(m,a,x,y);
    y%=m;
    y+=m;
    y%=m;
    return y;
}

/*const int N = 1000001;
int lp[N+1];
vector<int> pr;
void s(){
for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}*/


ll kv;
ll t,n,x,y,h,k,z,p,q,w;

vector<vector<pll>>v,v1,v2;
//vector<ll>vis,d;
  

int main() {
    IOS;
    cin>>n;
    p=inf*inf;
    fo(i,n){
        cin>>x;kv+=abs(x);p=min(p,abs(x));h+=x<0;
    }
    if(h%2)kv-=2*p;
    cout<<kv;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int i,j;
int n[10];
char s[11];
while(scanf("%s",s)!=-1){
for(i=0;i<10;i++)
n[i]=s[i]-'0';
for(i=9;i>0;i--)
for(j=0;j<i;j++)
n[j]=(n[j]+n[j+1])%10;
printf("%d\n",n[0]);
}
return 0;
}

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

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != t[i]) ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3784
#include <bits/stdc++.h>
  using namespace std;
#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) int ab;cin>>ab;(p).push_back(ab);
#define vecpl2(p) long long ab;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main() {
	
	int a,b;
	cin>>a>>b;
	if(a%2==0||b%2==0){
		ce("Even")
	}else{
		ce("Odd")
	}

}

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

int main() {
long long int n,b;
cin>>n>>b;
long long int lcm,h;
for(int i=1;i<=n&&i<=b;i++)
{
    if(n%i==0&&b%i==0){
        h=i;
    }
}
cout<<n*b/h;
return 0;	
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vec<int> S(2),T(2);
    cin >> S[0] >> S[1] >> T[0] >> T[1];
    string ans = "";
    int X = T[0]-S[0],Y = T[1]-S[1];
    
    auto print = [&](int N,char c){
        for(int i=0;i<N;i++) ans += c;
    };

    print(X,'R');
    print(Y+1,'U');
    print(X+1,'L');
    print(Y+1,'D');
    print(1,'R');
    print(1,'D');
    print(X+1,'R');
    print(Y+1,'U');
    print(X+1,'L');
    print(Y,'D');
    cout << ans << "\n";

}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
class dice
{
  private:
  int status[6];
  public:
  dice();
  int showfront(void);
  bool is(int,int);
  bool isfront(int);
  void rotate(char);
  bool rtfront(int);
  bool operator==(dice);
};

bool dice::rtfront(int a)
{
  int j;
  for(j=0;j<=3;j++)
  {
    if((*this).isfront(a)) break;
    (*this).rotate('N');
  }
  if(j==4)
  {
    (*this).rotate('E');
    (*this).rotate('S');
  }
  if(!(*this).isfront(a))
  {
    (*this).rotate('N');
    (*this).rotate('N');
  }
  if(!(*this).isfront(a))
    return false;
  else
    return true;
}

bool dice::operator==(dice d)
{
  int i=0;
  for(i=0;i<6;i++)
    if((*this).status[i]!=d.status[i]) break;
  if(i==6) return true;
  else return false;
}

dice::dice()
{
  for(int i=0;i<6;i++)
    cin>>status[i];
}

bool dice::isfront(int a)
{
  if(status[1]==a) return true;
  else return false;
}

bool dice::is(int a,int b)
{
  if((status[0]==a)&&(status[1]==b)) return true;
  else return false;
}

int dice::showfront()
{
  return status[1];
}

void dice::rotate(char s)
{
  switch(s)
  {
    int tmp;
    case 'N':
      tmp=status[0];
      status[0]=status[1];
      status[1]=status[5];
      status[5]=status[4];
      status[4]=tmp;
      break;
    case 'E':
      tmp=status[0];
      status[0]=status[3];
      status[3]=status[5];
      status[5]=status[2];
      status[2]=tmp;
      break;
    case 'W':
      tmp=status[0];
      status[0]=status[2];
      status[2]=status[5];
      status[5]=status[3];
      status[3]=tmp;
      break;
    case 'S':
      tmp=status[0];
      status[0]=status[4];
      status[4]=status[5];
      status[5]=status[1];
      status[1]=tmp;
      break;
  }
}

int main()
{
  dice di1;
  dice di2;
  if(!di2.rtfront(di1.showfront()))
    cout<<"No"<<endl;
  else
  {
    int i;
    for(i=0;i<4;i++)
    {
      if (di1==di2)
      {
        cout<<"Yes"<<endl;
        break;
      }
      di2.rotate('E');
    }
    if(i==4) cout<<"No"<<endl;
  }
}

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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


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

	int n = s.size();

	for(int i = 1; i < s.size()/2; i++)
	{
		n -= 2;
		if(s.substr(0, n/2) == s.substr(n/2, n/2))
		{
			break;
		}
	}

	cout << n << endl;
	return 0;	
}

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


def solve(x_max, y_max, d):

    c_table = [[-1] * 100 for _ in range(100)]

    for a in range(100):
        c_table_a = c_table[a]
        for x in range(x_max):
            ax = a * (x + 1)
            dx = d[x]
            for b in range(100):
                c = -1
                for y in range(y_max):
                    c = max(c, dx[y] - ax - b * (y + 1))
                c_table_a[b] = max(c_table_a[b], c)

    ab_max = 0
    c_set = {}
    for x in range(x_max):
        dx = d[x]
        for y in range(y_max):
            dxy = d[x][y]
            f = False
            for a in range(100):
                c_table_a = c_table[a]
                ax = a * (x + 1)
                for b in range(100):
                    if dxy == ax + b * (y + 1) + c_table_a[b]:
                        ab_max = max(ab_max, a, b)
                        c_set[(a, b)] = c_table_a[b]
                        f = True
                        break
                if f: break
            if not f:
                print('Impossible')
                return


    print('Possible')
    print('{} {}'.format((ab_max + 1) * 2, ab_max * 2 + len(c_set)))
    for i in range(ab_max):
        print('{} {} X'.format(i + 1, i + 2))
    for i in range(ab_max):
        print('{} {} Y'.format(ab_max + i + 3, ab_max + i + 2))
    for k, c in c_set.items():
        print('{} {} {}'.format(k[0] + 1, k[1] + ab_max + 2, c))
    print('{} {}'.format(1, ab_max + 2))


def main():
    A, B = input().split()
    A = int(A)
    B = int(B)
    d = [list(map(int, input().split())) for _ in range(A)]

    solve(A, B, d)


if __name__ == '__main__':
    main()



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


int main(){

    int64_t A, B, K;
    cin >> A >> B >> K;
    int64_t cntA=A;
    int64_t cntB=B;

    if(A >= K){
        cntA -=K;
    }else{
        cntA = 0;
        if(B >= K-A){
            cntB -= K-A;
        }
        else{
            cntB = 0;
        }
    }

    cout << cntA << " "<< cntB << endl;
}


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

bool data[55][31];
int N;

int main() {
  
  while(cin >> N && N) {
    memset(data, false, sizeof data);
    for(int i=0; i<N; i++) {
      int k; cin >> k;
      while(k--) {
	int h; cin >> h; data[i][h] = true;
      }
    }
    
    bool flag = false;
    set<int> st[51];
    for(int i=0; i<N; i++) {
      st[i].insert(i);
    }
    
    for(int i=1; i<31; i++) {
      for(int j=0; j<N; j++) {
	if(!data[j][i]) continue;
	for(int k=j+1; k<N; k++) {
	  if(!data[k][i]) continue;
	  set<int>::iterator it = st[k].begin();
	  for(; it!=st[k].end(); it++) {
	    st[j].insert(*it);
	  }
	  st[k] = st[j];
	}
	
	if(st[j].size() == N) {
	  cout << i << endl;
	  flag = true;
	  goto EXIT;
	}
      }
    }
    
  EXIT:;
    if(!flag) cout << -1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1308
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int a, b, h;
    cin >> a >> b >> h;

    int ans = (a+b)*h/2;

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

Measured memory_bytes: 256
//Created by Kira

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

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);
    
using ld = long double;


int main(){
   IOS

    ll a;
    string b; 
    cin>>a>>b;

    ll c = (b[0] - '0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');

    cout<<(a * c)/100<<"\n";



}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
    if(b&1)
        res = res * a % mod;
        a = a * a % mod;
    b >>= 1;
    }

    return res;
}



Measured memory_bytes: 3640
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let x = read::<i64>();
  let y = read::<i64>();

  println!("{}", (x * x - y).abs());
}



Measured memory_bytes: 4352
let lcs x y =
  let m = String.length x in
  let n = String.length y in
  let dp = Array.make_matrix (m + 1) (n + 1) 0 in
  for i = 1 to m do
    for j = 1 to n do
      dp.(i).(j) <-
        if x.[i-1] = y.[j-1] then dp.(i-1).(j-1) + 1
        else if dp.(i-1).(j) > dp.(i).(j-1) then dp.(i-1).(j)
        else dp.(i).(j-1)
    done
  done;
  dp.(m).(n)

let () =
  let q = read_int () in
  for _ = 0 to q - 1 do
    let x = read_line () in
    let y = read_line () in
    lcs x y |> Printf.printf "%d\n"
  done

Measured memory_bytes: 18648
#include<stdio.h>
#define LEN 100010

int partion(int *, int, int);

int main()
{
  int n, A[LEN];
  int p, r;
  int i, j, k;

  //read
  scanf("%d", &n);
  for(i=0; i<n; i++)scanf("%d", &A[i]);

  //partion
  p=0;
  r=n-1;
  j=partion(&A[0], p, r);

  //print
  printf("%d", A[0]);
  for(i=1; i<n; i++)
    {
      if(i==j)printf(" [%d]", A[i]);
      else printf(" %d", A[i]);
    }
  printf("\n");

  return 0;
}

//partion
int partion(int *A, int p, int r)
{
  int x = A[r];
  int i = p-1;
  int j, k;

  for(j=p; j<=r-1; j++)
    {
      if(A[j]<=x)
	{
	  i++;
	  k=A[i];
	  A[i]=A[j];
	  A[j]=k;
	}
    }

  k=A[i+1];
  A[i+1]=A[r];
  A[r]=k;
  return i+1;
}

Measured memory_bytes: 800
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define DB double
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define rep(i,n) FOR(i,0,n)
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000000000001
#define NUM 200010

void swap(LL* a,LL* b){LL tmp=*a;*a=*b;*b=tmp;}
void YN(int a){if(a==1)printf("Yes\n");if(a==0)printf("No\n");}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL GCD(LL a,LL b){LL c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int lcmpr(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return -1;if(*(LL*)a<*(LL*)b)return 1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int ccmpr(const void* a,const void* b){return *(char*)b-*(char*)a;}
int scmp(const void* a,const void* b){return strcmp((char*)a,(char*)b);}
int scmpr(const void* a,const void* b){return strcmp((char*)b,(char*)a);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(&m,&d);x-=k*y;swap(&x,&y);}return mod(a*mod(x,MOD),MOD);}
LL FAC(LL a){LL i,ans=1;FOR(i,1,a+1){ans*=i;if(MOD>0&&ans>MOD)ans%=MOD;}return ans;}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}

int main(){
  LL N,M,i,j,dp[6010][2010]={0},ans=0;
  scanf("%lld %lld",&N,&M);
  dp[0][0]=1;
  rep(i,3*N)rep(j,N+1){
    dp[i+1][j]+=dp[i][j];
    dp[i+1][j]%=M;
    dp[i+2][j+1]+=dp[i][j]*(i+1);
    dp[i+2][j+1]%=M;
    dp[i+3][j+1]+=dp[i][j]*(i+2)*(i+1);
    dp[i+3][j+1]%=M;
  }
  rep(i,N+1)ans=(ans+dp[3*N][i])%M;

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


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

#define ll long long
using namespace std;

const int N = 105, K = 1e5 + 5, M = 1e9 + 7;
int n, k, a[N];
ll dp[N][K];

ll mod(ll a, ll b) {
    return ((a % b) + b) % b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        dp[i][0] = 1;
        for(int j = 1; j <= k; j++) {
            dp[i - 1][j] = mod(dp[i - 1][j] + dp[i - 1][j - 1], M);
            dp[i][j] = dp[i - 1][j];
            if(j - a[i] > 0) dp[i][j] -= dp[i - 1][j - a[i] - 1];
            dp[i][j] = mod(dp[i][j], M);
        }
    }
    cout << dp[n][k] << endl;
}

Measured memory_bytes: 80128
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい
// https://github.com/atcoder/live_library
// cppdbg: test.exeのterminalに標準入力を打てる

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
#define ub(a,x) (upper_bound(ALL(a),x)-a.begin())
#define lb(a,x) (lower_bound(ALL(a),x)-a.begin())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<ll, vector<ll>, greater<ll> > gpq; //逆順priority_queue
typedef priority_queue<ll> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b+c || b==c+a || c==a+b){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3564
# https://atcoder.jp/contests/abc175/tasks/abc175_c

X, K, D = gets.split.map(&:to_i)

sgn = X >= 0 ? 1 : -1
x = X.abs

if x >= K * D
  puts (x - K * D)
  exit 0
end

q, r0 = x.divmod(D)
r1 = D - r0
if (K - q).even?
  puts r0
else
  puts r1
end


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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

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

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

#define FF first
#define SS second

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N, M;
  while(cin>>N>>M,N&&M){
	VS pat(N); REP(i,N) cin >> pat[i];
	VI sz(N); REP(i,N) sz[i] = SZ(pat[i]);
	string T;
	REP(i,M){
	  string tmp; cin >> tmp;
	  T += tmp;
	}
	M = SZ(T);
	vector<vector<bool>> match(N, vector<bool>(M+1,false));
	REP(i,N) for(int j=0;j+sz[i]<=M;++j)
	  match[i][j] = pat[i] == T.substr(j, sz[i]);

	VI szb(1<<N);
	REP(b,1<<N) REP(i,N)
	  if(b>>i&1) szb[b] += sz[i];
	  
	vector<vector<bool>> dp(1<<N, vector<bool>(M+1,false));
	REP(i,M+1) dp[0][i] = true;
	REP(b,1<<N){
	  REP(i,N){
		if(b>>i&1) continue;
		int nxtb = b | (1<<i);
		for(int pos=0;pos+sz[i]+szb[b]<=M;++pos){
		  if((dp[b][pos] && match[i][pos+szb[b]])
			 || (match[i][pos] && dp[b][pos+sz[i]]))
			 dp[nxtb][pos] = true;
		}
	  }
	}
	cout << count(ALL(dp[(1<<N)-1]), true) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 5696
#include<iostream>
#include<algorithm>
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;
int N,L;
int main()
{
    cin>>N>>L;
    string a[N];
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
    }
    sort(a,a+N);
    for(int i=0;i<N;i++)
    {
        cout<<a[i];
    }
return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
f.sort()
a.sort()
a.reverse()
l=0
r=10**12+1
import math
while r-l>1:
	mid=(l+r)/2
	cnt=0
	for i in range(n):
		if a[i]*f[i]>mid:
			cnt+=a[i]-mid//f[i]
	if cnt<=k:
		r=mid
	else:
		l=mid
print(int(r))



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

#define Int long long int

int main(){
    int n;
    cin >> n;
    //int table[10000]={};a
    map<string, int> table;
    string a;

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

    int sum=0;
    for(pair<string,int> p:table){
        if(stoi(p.first)>p.second)sum+=p.second;
        else sum+=min(p.second-stoi(p.first),p.second);
    }
    cout << sum << endl;
}


Measured memory_bytes: 12160