akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <double, double> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
#define y1 abc
//#define int ll

const int N = 2e5;
const int INF = 1e9;

int n;
pii a[N];
double sum;
int num;
vector <int> p;

double dist(double x1, double y1, double x2, double y2) {
	return sqrt((fabs(x2 - x1) * fabs(x2 - x1)) + (fabs(y2 - y1) * fabs(y2 - y1)));
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	fo(i, 1, n, 1) {
		cin >> a[i].F >> a[i].S;
		p.pb(i);
	}
	do {
		fo(i, 0, sz(p) - 2, 1) {
			sum += dist(a[p[i]].F, a[p[i]].S, a[p[i + 1]].F, a[p[i + 1]].S);
		}
		++num;
	} while(next_permutation(p.begin(), p.end()));
	cout << fixed << setprecision(7) << (sum / num);
	return 0;
}
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <double, double> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
#define y1 abc
//#define int ll

const int N = 2e5;
const int INF = 1e9;

int n;
pii a[N];
double sum;
int num;
//vcetor <int> p;

double dist(double x1, double y1, double x2, double y2) {
	return sqrt((fabs(x2 - x1) * fabs(x2 - x1)) + (fabs(y2 - y1) * fabs(y2 - y1)));
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	fo(i, 1, n, 1) {
		cin >> a[i].F >> a[i].S;
//		p.pb(i);
	}
	do {
		fo(i, 1, n, 1) {
			sum += dist(a[i].F, a[i].S, a[i + 1].F, a[i + 1].S);
			cout << a[i].F <<' '<< a[i].S <<'\n';
		}
		cout << '\n';
		++num;
	} while(next_permutation(a + 1, a + n + 1));
//	fo(i, 1, n, 1) {
//			sum += dist(a[i].F, a[i].S, a[i + 1].F, a[i + 1].S);
//			cout << a[i].F <<' '<< a[i].S <<'\n';
//	}
//	cout << '\n';
	++num;
	
	cout << sum <<'\n';
	cout << num <<'\n';
	
	//while(next_permutation(p.begin(), p.end()));
//	cout << sum <<' '<< num <<'\n';
//	sum = sqrt(sum);
	cout << fixed << setprecision(7) << (sum / num);
	return 0;
}
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const ll INF = +10010010000;
typedef pair<ll,ll> P;
const int mod = 1e9+7;

struct mint{
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a){
        (x+=a.x)%=mod;
        return *this;
    }
    mint& operator-=(const mint a){
        (x-=mod-a.x)%=mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x *= a.x)%= mod;
        return *this;
    }
    mint operator+(const mint a)const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a)const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a)const{
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
      if(!t)return 1;
      mint a = pow(t>>1);
      a*=a;
      if(t%1)a*=*this;
      return a;
    }

    // for prime mod
    mint inv() const {
      return pow(mod-2);
    }
    mint& operator/=(const mint a){
      return (*this) *= a.inv();
    }
    mint operator/(const mint a)const{
      mint res(*this);
      return res/=a;
    }
};

struct combination{
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1){
    fact[0] = 1;
    for(int i = 1; i<n;++i)fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i>=1;--i) ifact[i-1] = ifact[i] * i;
  }
  mint operator()(int n, int k){
    if(k<0 || k>n)return 0;
    return fact[n] * ifact[k] + ifact[n-k]; 
  }
};
int main(){
    int k;
    cin >> k;
    string s;
    cin >> s;
    if(s.size()<=k){
        cout << s << endl;
    }else{
        s = s.substr(0,k);
        s += "...";
        cout << s <<endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#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;
const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
const 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

//------ 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[ohara], b[ohara], 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 >> n;
  rep(i, n + 1) cin >> a[i];
  rep(i, n) cin >> b[i];

  rep(i, n) {
    ans += min(a[i] + a[i + 1], b[i]);
    ll cost = min(a[i], b[i]);
    a[i] -= cost;
    b[i] -= cost;

    cost = min(a[i + 1], b[i]);
    a[i + 1] -= cost;
    b[i] -= cost;
  }
  Cout(ans);
  return 0;
}

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

int main(){
  string s;
  cin >> s;
  
  if(s.substr(2, 1) == s.substr(3, 1) && s.substr(4, 1) == s.substr(5, 1)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
w,h,n=list(map(int,input().split()))
x=[]
y=[]
a=[]

for i in range(n):
    x1,y1,a1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)
    a.append(a1)

lp=0
x_max=[0]
x_min=[w]
y_max=[0]
y_min=[h]

for aa in a:
    
    if aa== 1:
        x_max.append(x[lp])

    elif aa==2:
        x_min.append(x[lp])

    elif aa==3:
        y_max.append(y[lp])

    elif aa==4:
        y_min.append(y[lp])
    
    lp+=1

x=min(x_min)-max(x_max)
y=min(y_min)-max(y_max)

if x<=0:
    x=0
if y<=0:
    y=0

ans=x*y

print(ans)

Measured memory_bytes: 3064
use proconio::{fastout, input};

fn main() {
    input! {
        a: i32,
        b: i32,
        c: i32,
        k: i32
    };

    let mut sum = 0;

    let mut acc = 0;

    if a > k {
    println!("{}", k);
    } else {
        sum = a;
        acc = k - a;
        if acc > b {
            acc = acc - b;
            sum -= acc;
    println!("{}", sum);

        } else {
            println!("{}", sum);

        }
    }

}


Measured memory_bytes: 2128
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int N;
    int a[10000] = {0};
    cin >> N;
    for (int i=0;i<N;i++) cin >> a[i];
    int ans=0;
    for(int i=0;i<N;i++){
        while(a[i]%2==0){
            ans++;
            a[i] = a[i]/2;
        }
    }
    cout << ans << endl;
    return 0;
}


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

typedef pair<long,int> P;

int main(){
  int n,m;
  cin >> n >> m;
  vector<long> a(n);
  vector<P> cb(m);
  for(int i = 0;i < n;i++){
    cin >> a.at(i);
  }
  for(int i = 0;i < m;i++){
    cin >> cb.at(i).second >> cb.at(i).first;
  }
  sort(a.begin(),a.end());
  sort(cb.begin(),cb.end());
  reverse(cb.begin(),cb.end());
  int cur = 0,cnum = 0;
  while(cur < n && cnum < m){
    while(cb.at(cnum).first > a[cur] && cb.at(cnum).second > 0 && cur < n && cnum < m){
      a[cur] = cb.at(cnum).first;
      cb.at(cnum).second--;
      cur++;
    }
    cnum++;
  }
  long ans = 0;
  for(int i = 0;i < n;i++){
    ans += a[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s,ans;
    cin>>n>>s;
    ans = s.at(0);
    for(int i=1;i<n;i++){
        if(s.at(i)!=s.at(i-1)){
            ans += s.at(i);
        }
    }
    cout<<ans.size()<<endl;

    return 0;
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

typedef pair< int, int > pii;
typedef pair< pii, int > piii;

int M, T, P, R;

int main() {
	while (cin >> M >> T >> P >> R, M) {
		vector< int > cnt(T, 0);
		vector< vector< int > > pen(T, vector< int >(P, 0));
		
		for_(i,0,R) {
			int m, t, p, j;
			cin >> m >> t >> p >> j;
			--t; --p;
			
			if (m <= M) {
				if (j == 0) {
					pen[t][p] = (-pen[t][p]) + m;
					++cnt[t];
				} else if (pen[t][p] <= 0) {
					pen[t][p] -= 20;
				}
			}
		}
		
		vector< piii > info(T, piii(pii(0, 0),0));
		
		for_(i,0,T) {
			info[i].first.first = cnt[i];
			for_(j,0,P) if (pen[i][j] > 0) info[i].first.second -= pen[i][j];
			info[i].second = i + 1;
		}
		
		sort(info.begin(), info.end(), greater< piii >());
		
		for_(i,0,T) {
			cout << info[i].second;
			
			if (i < T - 1) {
				pii p = info[i].first, pn = info[i+1].first;
				if (p == pn) cout << "=";
				else cout << ",";
			}
		}
		cout << endl;
	}
}

Measured memory_bytes: 1224
n=input()
count=0
for i in range(len(n)):
    if i==0:
        if n[i]=='A':
            continue
        else:
            print('WA')
            exit()

    elif i==1 or i==len(n)-1:
        if n[i].islower():
            continue
        else:
            print('WA')
            exit()

    else:
        if n[i]=='C':
            count+=1
            if count>=2:
                print('WA')
                exit()
        elif n[i].islower():
            continue
        else:
            print('WA')
            exit()

if count==1:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 38256
n = int(input())
songs = []
subs_total = 0
total = 0
for _ in range(n):
    s, t = input().split()
    total += int(t)
    songs.append([s,t])
x = input()
for i in range(n):
    subs_total += int(songs[i][1])
    if songs[i][0] == x:
        break
ans = total - subs_total
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define prev(a, x) a[a.size() - x - 1]
#define forn(i, n) for(int i = 0; i < n; i++)
using namespace std;
struct pnt{
	int x, y;
	pnt(){}
	pnt(int x, int y) : x(x), y(y) {}
	bool operator<(const pnt &b) const{
		return (y != b.y)? y < b.y : x < b.x;
	}
	pnt operator+(const pnt &b){
		return pnt(x + b.x, y + b.y);
	}
	pnt operator-(const pnt &b){
		return pnt(x - b.x, y - b.y);
	}
	int operator%(const pnt &b){
		return x * b.y - b.x * y;
	}
};
bool in(pnt a, pnt b, pnt c){
	//cout<<a.x<<" "<<a.y<<" "<<b.x<<" "<<b.y<<" "<<c.x<<" "<<c.y<<"\n";
	a = b - a;
	b = c - b;
	//cout<<a.x<<" "<<a.y<<" "<<b.x<<" "<<b.y<<"\n";
	if(a % b < 0) return 0;
	return 1;
}
vector<pnt> convexhull(vector<pnt> &a){
	sort(a.begin(), a.end());
	int n = a.size();
	vector<pnt> ret;
	ret.push_back(a[0]);
	ret.push_back(a[1]);
	for(int i = 2; i < n; i++){
		while(ret.size() > 1 && !in(prev(ret, 1), prev(ret, 0), a[i])) ret.pop_back();
		ret.push_back(a[i]);
	}
	for(int i = n - 2; i >= 0; i--){
		while(ret.size() > 1 && !in(prev(ret, 1), prev(ret, 0), a[i])) ret.pop_back();
		ret.push_back(a[i]);
	}
	ret.pop_back();
	return ret;
}
int main(){
	int n;
	cin>>n;
	vector<pnt> a(n);
	forn(i, n) cin>>a[i].x>>a[i].y;
	vector<pnt> ch = convexhull(a);
	n = ch.size();
	cout<<n<<"\n";
	forn(i, n) cout<<ch[i].x<<" "<<ch[i].y<<"\n";
	return 0;
}


Measured memory_bytes: 4340
n, h = list(map(int, input().split()))

wield = 0
bs = []

for i in range(n):
    a, b = list(map(int, input().split()))

    if a > wield:
        wield = a

    bs.append(b)

throw = []

for i in range(n):
    if bs[i] > wield:
        throw.append(bs[i])

total = sum(throw)

if total > h:
    throw = sorted(throw, reverse=True)

    total = 0
    ind = 0
    while total < h:
        total += throw[ind]
        ind += 1

    print(ind)
else:
    print((h-total+wield-1)//wield + len(throw))

Measured memory_bytes: 14372
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String A = sc.next();
		String B = sc.next();
		
		Node a = toNode(A);
		Node b = toNode(B);
		
		Node c = merge(a,b);
		
		System.out.println(toString(c));
		
	}
	static char[] S;
	static int id;
	public static Node toNode(String a) {
		S = a.toCharArray();
		id = 0;
		return N();
	}
	public static Node N() {
		Node node = new Node();
		if(S[id+1] != ')') {
			id++;
			node.l = N();
		}
		id += 3;
		String num = "";
		while(S[id] != ']') {
			num += S[id++];
		}
		node.number = Integer.parseInt(num);
		id++;
		if(S[id+1] != ')') {
			id++;
			node.r = N();
		}
		id++;
		return node;
			
	}
	public static Node merge(Node a, Node b) {
		Node next = new Node();
		next.number = a.number + b.number;
		if(a.l != null && b.l != null) {
			next.l = merge(a.l,b.l);
		}
		if(a.r != null && b.r != null) {
			next.r = merge(a.r,b.r);
		}
		return next;
	}
	public static String toString(Node a) {
		String ret = "(";
		if(a.l != null) {
			ret += toString(a.l);
		}
		ret += ")[" + a.number + "](";
		if(a.r != null) {
			ret += toString(a.r);
		}
		ret += ")";
		return ret;
	}
	static class Node {
		int number;
		Node l;
		Node r;
	}
}
	
	
		

Measured memory_bytes: 27648
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define MAX 100
#define MOD 1000000007
#define pb push_back

/* add vars here */

ll n;

/* add your algorithm here */

int main() {
  cin >> n;
  vector<ll> a(n,0);
  rep(i,n) cin >> a[i];

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

  ll res = 0;
  ll e1 = 0, e2 = 0;
  ll cnt = 0;
  for (int i = n-1; i >= 0; --i) {
    cnt++;
    if (i == 0) {
      if (cnt == 2) {
        e2 = a[i];
      }
      break;
    }
    if (cnt == 2) {
      if (!e1) e1 = a[i];
      else if (!e2) {
        e2 = a[i];
        break;
      }
      cnt = 0;
    } else if (a[i] != a[i-1]) {
      cnt = 0;
    }
  }

  res = e1 * e2;
  cout << res << endl;
}


Measured memory_bytes: 1024
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
 
minimum = min(a,b,c,d,e)
 
ans = 5+n//minimum

if n%minimum == 0:
    ans -=1
 
print(ans)

Measured memory_bytes: 3064
N = int(input())
a = list(map(int, input().split()))

forward = [0] * (N - 1)
backward = [0] * (N - 1)

# forward
f = 0
for _ in range(N-1):
    f += a[_]
    forward[_] = f

b = 0
for _ in range(-1, -N, -1):
    b += a[_]
    backward[_] = b

diff = [abs(fi - bi) for fi, bi in zip(forward, backward)]

print(min(diff))

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

int main() {
    string S;
    cin >> S;
    int n = S.size();
    vector<int> RtoL(n, 0), LtoR(n, 0);

    for (int i = 0; i < n; i++) {
        RtoL[i] = LtoR[i] = i;
    }

    for (int i = n - 1; i >= 0; --i) {
        if (S[i] == 'R') {
            RtoL[i] = RtoL[i + 1];
        }
    }

    for (int i = 0; i < n; i++) {
        if (S[i] == 'L') {
            LtoR[i] = LtoR[i - 1];
        }
    }

    vector<int> res(n, 0);
    for (int i = 0; i < n; i++) {
        if (S[i] == 'L') {
            ++res[LtoR[i] + ((i - LtoR[i]) % 2 == 1 ? 1 : 0)];
        } else {
            ++res[RtoL[i] - ((RtoL[i] - i) % 2 == 1 ? 1 : 0)];
        }
    }
    for (int i = 0; i < n; i++) {
        cout << res[i] << (i == n - 1 ? '\n' : ' ');
    }

    return 0;
}

Measured memory_bytes: 4512
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

int main(){
  int n;

  for(;;){
    cin >> n;
    if ( n == 0 ) break;

    double scores[1000] ={}, sum = 0;
    double m = 0, sigma = 0, stddev = 0;

    for (int i=0; i<n; i++){
      cin >> scores[i];
      sum += scores[i];
    }
    m = sum / n;

    for ( int i=0; i<n; i++){
      sigma += pow(scores[i] - m, 2);
    }
    stddev = sqrt(sigma/n);

    printf("%lf\n", stddev);
  }

  return 0;
}

Measured memory_bytes: 3152
import java.util.Scanner;

/**
 * Created by Santa on 2016/10/16.
 */
public class Main {

    static class pair {
            public int a;
            public int b;

            pair(){
                this.a = 0;
                this.b = 0;
            }

            pair(int a, int b){
                this.a = a;
                this.b = b;
            }

            public void set(int a, int b) {
                this.a = a;
                this.b = b;
            }
        }

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

        int H = scanner.nextInt();
        int W = scanner.nextInt();
        int D = scanner.nextInt();

        pair[] map = new pair[H * W];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                map[Integer.parseInt(scanner.next()) - 1] = new pair(j ,i);
            }
        }



        int[][] point  = new int[D][H * W / D + 1];

        for (int i = 0; i < D; i++) {
            int j = 1;
            point[i][0] = 0;
            while (j * D + i < H * W){
//                System.out.println(j * D + i);
                point[i][j] = point[i][j - 1] + Math.abs(map[j * D + i].a - map[(j - 1) * D + i].a) + Math.abs(map[j * D + i].b - map[(j - 1) * D + i].b);
                j++;
            }

        }

        int Q = scanner.nextInt();


//        for (int i = 0; i < D; i++) {
//            for (int j = 0; j <= H * W / D; j++) {
//                System.out.print(point[i][j] + " ");
//            }
//            System.out.println();
//        }


        for (int i = 0; i < Q; i++) {
            int L = scanner.nextInt();
            int R = scanner.nextInt();

            int aa = R % D == 0 ? 1 : 0;
            System.out.println(point[(R + D - 1) % D][(R - aa) / D] - point[(R + D - 1) % D][(L - aa) / D]);
//            System.out.println(point[(R + D - 1) % D][(L - aa) / D]);
        }


    }



}




Measured memory_bytes: 100540
//***********************
//*** writer : Alan Hu **
//***********************
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#include<list>
#include<stack>
#include<cstdio>
#include<fstream>
#include<numeric>
#include<functional>
#include<utility>
#include<memory>
#include<cstring>
#include<cmath>
using namespace std;
     
#define CLEAN(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define pb push_back
#define sz(a) a.size()
#define rept(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
     
typedef long long ll;
typedef pair<int, int> pii;

int main()
{	
	ll n,m,d;
	cin>>n>>m>>d;
	double ans=(double)((n-d)*(m-1)/(n*n*1.0));
	if (d!=0) ans*=2;
	printf("%.10lf",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int main(void)
{
    int N; cin >> N;
    int p[N]; rep(i, N) cin >> p[i];
    int ans = 0;
    for (int i = 0; i < N; i++){
        if (p[i] == i + 1) {
            i++; ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 640
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;

int n;
int ar[100005],br[100005];
int main(){
  cin>>n;
  lint totA=0,totB=0;
  REP(i,n) cin>>ar[i],totA+=ar[i];
  REP(i,n) cin>>br[i],totB+=br[i];
  if(totA<totB){
    puts("-1");
    return 0;
  }
  vector<int>surp;
  int lack=0;
  lint need=0;
  REP(i,n){
    if(ar[i]>br[i]){
      surp.pb(ar[i]-br[i]);
    }else if(ar[i]<br[i]){
      ++lack;
      need+=br[i]-ar[i];
    }
  }
  sort(ALL(surp),greater<int>());
  lint sum=0;
  int res=surp.size();
  REP(i,surp.size()){
    if(need<=sum){
      res=i;
      break;
    }else{
      sum+=surp[i];
    }
  }
  res+=lack;
  cout<<res<<endl;
  return 0;
}





Measured memory_bytes: 1408
#include <stdio.h>
#include <stdlib.h>
#define START(a) (a>0?a:0)
int s,ans,ttt,a,b;
int main(void){
	while(scanf("%d",&s)!=EOF){
		ans=0;
		for(a=START(s-2000);a<=2000 && s>=a;a++){
			ans+=(1001-abs(1000-(s-a)))*(1001-abs(1000-a));
		}
		printf("%d\n",ans);
	}
	return 0;
}

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

using namespace std;

#define ll long long
#define ar array



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

	string s;
	int n;
	cin >> n >> s;
	int cnt = 0;
	for(int i = 0; i+2 < n;i++){
			string abc = s.substr(i,3);
			if(abc=="ABC"){
				cnt++;
			}
	}
	cout << cnt;
	return 0;
}


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

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

  if (S == "RRR")
    cout << 3 << endl;
  else if (S == "SRR" || S == "RRS")
    cout << 2 << endl;
  else if (S == "SSR" || S == "RSS" || S == "SRS" || S == "RSR")
    cout << 1 << endl;
  else if (S == "SSS")
    cout << 0 << endl;

  return 0;
}


Measured memory_bytes: 3628
#include<iostream>
using namespace std;
int main()
{
	int n,c,a,m;
	int i;
	int cnt;
	cin >> n;
	for(i=0;i<n;i++)
	{
		cnt=0;
		cin >> c >> a >> m ;
		if(c==0);
		else if(a>0)
		{
			while(c>0 && a>0 && m>0)
			{
				c--;
				a--;
				m--;
				cnt++;
			}
			while( c>1 && a>0 )
			{
				c-=2;
				a--;
				cnt++;
			}
		}
		cnt+=c/3;
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
ll mod=1000000007;

int main() {
  int n; cin >> n;
  vector<int> v(n);
  bool isall10 = true;
  for (int i=0;i<n;++i){
    cin >> v[i];
    if(v[i]%10 != 0) isall10 =false;
  }
  sort(all(v));
  int sum = accumulate(all(v), 0);
  if(sum%10 !=0){
    cout << sum << endl;
    return 0;
  }
  if(isall10){
    cout << 0 << endl;
    return 0;
  }
  for(int i=0;i<n;++i){
    if(v[i]%10!=0){
      sum -= v[i];
      break;
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
#include <map>
using namespace std;

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

int main() {
	string s; cin >> s;
	vector<int> data;
	char now = s.at(0);
	int cnt = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s.at(i) == now) {
			cnt++;
		}
		else {
			data.push_back(cnt);
			cnt = 1;
			now = s.at(i);
		}
	}
	if (cnt > 0) {
		data.push_back(cnt);
	}
	cout << data.size() - 1 << endl;
	return 0;
}

Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define mod 998244353
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=200001 ;
ll n;
ll c[N] ;
vector<ll>v[N] ;
ll dp[N] ;
vector<ll>col[N] ;
ll lol[N] ;
ll dfs(ll i,ll p)
{
    ll pre=lol[c[i]] ;
    ll sz=0 ;
    for(ll j:v[i])
    {
        if(j==p)
            continue ;

        ll x=lol[c[i]] ;
        ll y=dfs(j,i) ;
        ll inc=y-lol[c[i]]+x ;

        dp[i]+=(inc*(inc+1))/2 ;
        sz+=y ;
    }
    sz++ ;
    lol[c[i]]=pre+sz ;
    return sz ;
}
int main()
{
   fast ;
   cin>>n ;
   for(ll i=1;i<=n;i++)
    {
        cin>>c[i] ;
        col[c[i]].pb(i) ;
    }

   for(ll i=0;i<n-1;i++)
   {
       ll x,y ;
       cin>>x>>y ;
       v[x].pb(y) ;
       v[y].pb(x) ;
   }
   memset(lol,0,sizeof(lol))  ;
   memset(dp,0,sizeof(dp)) ;

   dfs(1,-1) ;
   for(ll i=1;i<=n;i++)
   {
       ll ans=(n*(n+1))/2 ;
       ll f=0 ;
       for(ll j:col[i])
       {
          if(j==1)
          {
              f=1 ;
          }
          ans-=dp[j] ;
       }

       if(f==0)
       {
           ll x=n-lol[i] ;
           ans-=(x*(x+1))/2 ;
       }
       cout<<ans<<endl ;
   }



}



Measured memory_bytes: 46848
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define pb(x) push_back(x)
#define fi first
#define se second
#define mp(x,y) make_pair(x,y);
/*struct comp
{
    bool operator()()
    {
        
    }
};*/
int32_t main() {
    int t=1;
    //cin>>t;
    while(t--)
    {
      int K,A,B;
      cin>>K>>A>>B;
      bool flag=1;
      for(int i=A;i<=B&& flag;i++)
      {
          if(i%K==0)
          {
              cout<<"OK";
              flag=0;
          }
      }
      if(flag)
      {
          cout<<"NG";
      }
      
        
    }
}

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

int main(){
    int r,g,b;
    cin>>r>>g>>b;
    int s;
    s = (r*100)+(g*10)+b;
    if(s%4==0){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 3508
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin>>n;
	for(int i=sqrt(n);i>=1;i--)
	{
		if(n%i==0)
		{
			int s=n/i,ans=0;
			while(s>0)
			{
				s/=10;
				ans++;
			}
			cout<<ans<<endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <cstdio>
#define INF 1e9
#define eps 1e-6
typedef long long ll;

int n, a[200010], x, y, ans;
char s[200010];

void swap(char &p, char &q){
	char t = p;
	p = q;
	q = t;
}

int main(){

	scanf("%d %s", &n, s + 1);
	for(int i = 1; i <= n; i++)
		if(s[i] == 'W'){
			x = i;
			break;
		}
	if(!x) x = n + 1;
	for(int i = n; i >= 1; i--)
		if(s[i] == 'R'){
			y = i;
			break;
		}
	if(!y) y = 0;
	while(x <= y){
		ans++, swap(s[x], s[y]);
		while(s[x] == 'R') x++;
		while(s[y] == 'W') y--;
	}
	printf("%d\n", ans);
		
	
	return 0;
}


Measured memory_bytes: 1892
//                   * In The Name of Allah *
// Writer: arianBASS
//#include "stdafx.h"
#include <bits/stdc++.h>
#define Turbo std::ios::sync_with_stdio(false)
#define int long long
#define pb push_back
#define ever ( ; ; )

using namespace std;

const int N = 1e6 + 2;
int a[N], f[N];
pair<int, int> af[N];

int32_t main() {
	Turbo;
	int a, b;
	cin >> a >> b;
	if (a >= 1 && a <= 9 && b >= 1 && b <= 9)
		cout << a * b << '\n';
	else
		cout << -1 << '\n';
	return 0;
}

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

#define INF 0x3F3F3F3F
#define DINF 1e+12
#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define pb push_back
#define debug(x) if(1) cout << #x << " = " << x << endl;
#define debug2(x,y) if(1) cout << #x << " = " << x << " --- " << #y << " " << y << "\n";
#define all(S) (S).begin(), (S).end()
#define F first
#define S second
#define EPS 1e-9
#define mp make_pair

// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);

using namespace std;

typedef long long ll;
typedef pair < int, int >  ii;

int main(){

	int n, a, b;
	while(cin >> n >> a >> b){
		int dif = b-a;
		if(dif&1) printf("Borys\n");
		else printf("Alice\n");
	}

	return 0;
}


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

#define loop(s, e, i) for (int i = s; i < e; ++i)
#define print(s) cout << s << endl;
#define DIV 1000000007
#define ll long long
using namespace std;

/*
浮動小数点の入力
cout << fixed << setprecision(9) << endl;
*/

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

  string s;
  cin >> s;
  if (s[s.size()-1] == 's') {
    s += "es";
  } else {
    s += "s";
  }
  print(s);
}


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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	long long int n, d, x, y;
	cin >> n >> d;
	long long int cnt = 0;
	for(long long int i = 0; i < n; i++) {
		cin >> x >> y;
		if(x * x + y * y <= d * d) cnt += 1;
	}
	cout << cnt;
	return 0;
}


Measured memory_bytes: 3616
def main():
    N = int(input())
    s = [input() for _ in range(N)]

    a = 0
    b = 0
    ab = 0

    count = 0

    for i in range(N):
        for j in range(len(s[i])-1):
            if s[i][j:j+2] == 'AB':
                count += 1


    for i in range(N):
        if (s[i][0] == 'B' or s[i][-1] == 'A'):
            if (s[i][0] == 'B' and s[i][-1] == 'A'):
                ab += 1
            elif (s[i][0] == 'B'):
                b += 1
            else:
                a += 1

    if (a==b==0) and (ab > 0):
        ab -= 1
    print(count+min(a+ab, b+ab))


if __name__=='__main__':
    main()

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

int convert_to_minutes(int H, int M)
{
	if(H < 0 || H > 23 || M > 59 || M < 0)
		return 0;
	return H * 60 + M;
}

int solve(int H1, int M1, int H2, int M2, int K)
{
	int start;
	int end;
	int res = 0;
	start = convert_to_minutes(H1, M1);
	end = convert_to_minutes(H2, M2);
	int delta = end - start;
	if (delta > K)
		res = delta - K;
	return res;
} 

int main()
{
	int H1, M1, H2, M2, K;
	cin >> H1 >> M1 >> H2 >> M2 >> K;
	int res = solve(H1,M1, H2, M2, K);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
int main(){
  double x1,y1,x2,y2;
  cin >> x1 >> y1 >> x2 >> y2;
  //cout << sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) << endl;
  printf("%.5f\n",sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
  return 0;
}



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

int n, a;
set<int> s;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a;
        if(s.find(a) == s.end()) s.insert(a);
        else s.erase(a);
    }
    cout << s.size();
}


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

#define range(i, start, end) for(int i=start; i<end; i++)
#define rep(i, n) for(int i=0; i<n; i++)

int main() {
  int a, b;
  cin >> a >> b;
  int cnt = 0;
  range(i, a, b+1) {
     if (i/10000 == i%10 && (i/1000)%10 == (i%100)/10 ) {
       cnt++; 
     }
  }
  cout << cnt << "\n";
}


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

using namespace std;

template <typename T>std::string NumberToString ( T Number ){std::ostringstream ss; ss << Number;return ss.str(); } // Usages NumberToString(3)
template <typename T>T StringToNumber ( const string &Text ){istringstream ss(Text);T result;return ss >> result ? result : 0;} // StringToNumber<int>("3")

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    string str;
    cin >> str;
    int count = 0;
    if(str[0] == 'A' || str[1] =='A' || str[2] == 'A'){
        count ++;
    }
    if(str[0] == 'B' || str[1] =='B' || str[2] == 'B'){
         count ++;
    }
    if(count==2) cout << "Yes" << endl;
    else cout << "No" << endl;




   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define int long long
#define swap(x,y) (x^=y^=x^=y)

#define debug1(a) cerr<<#a<<" = "<<(a)<<endl;
#define debug2(a,b) cerr<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define debug3(a,b,c) cerr<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;
#define debug4(a,b,c,d) cerr<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<", "<<#d<<" = "<<(d)<<endl;

using namespace std;
 
#define mod 1000000007
long long modexpo(long long x, long long p){
    int res = 1;x = x%mod;
    while(p){
        if(p%2)res = res * x;
        p >>= 1;
        x = x*x % mod;
        res %= mod;
    }
    return res;
}

struct compare{
    bool operator() (const pair<int,int> a, const pair<int,int> b) const{
        return a.first < b.first;
    }
};

const int nax = 1e6 + 5;
int arr[nax], sieve[nax], n, cnt[nax];

int32_t main(){
    IOS
    cin >> n;
    for(int i = 2; i < nax; i++){
        for(int j = i; j < nax; j += i){
            if(sieve[j]){
                continue;
            }
            sieve[j] = i;
        }
    }
    int g = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        g = __gcd(g,x);
        while(x > 1){
            int y = sieve[x];
            cnt[y]++;
            while(x%y == 0){
                x /= y;
            }
        }
    }
    if(g > 1){
        cout << "not coprime" << endl;
        return 0;
    }
    for(int i = 2; i < nax; i++){
        if(cnt[i] > 1){
            cout << "setwise coprime" << endl;
            return 0;
        }
    }
    cout << "pairwise coprime" << endl;
} 

Measured memory_bytes: 19276
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long k = sc.nextLong();

		long x;
		long y;

		if (n > k) {
			x = n % k;
			y = k - x;
		} else if (n == k) {
			x = 0;
			y = 0;
		} else {
			x = Math.abs(n - k);
			y = Math.abs(x - k);
		}

		System.out.println(Math.min(x, y));
		sc.close();

	}
}

Measured memory_bytes: 23636
#include<iostream>
#include <algorithm>
#include<vector>
#include<map>
#include <set>
#include<string>
#include <queue>
#include <stack>
#include <random>
#define INF 10000001

int main()
{    

    int A,B,T;
    std::cin >> A >> B >> T ;
  std::cout << (int)(T / A)*B << std::endl;
}

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

void solve() {
  int64_t n, k;
  cin >> n >> k;

  vector<int64_t> a(n);
  for (int64_t i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());

  auto pos = lower_bound(a.begin(), a.end(), 0);
  auto rpos = make_reverse_iterator(pos);
  auto non_zero_pos = upper_bound(a.begin(), a.end(), 0);

  auto pos_cnt = a.end() - pos;
  auto neg_cnt = n - pos_cnt;
  auto non_zero_pos_cnt = a.end() - non_zero_pos;
  auto zero_cnt = pos_cnt - non_zero_pos_cnt;

  int64_t left = numeric_limits<int64_t>::min() / 2;
  int64_t right = numeric_limits<int64_t>::max() / 2;
  while (1 < right - left) {
    int64_t lcnt = 0;
    int64_t ucnt = 0;
    auto mid = (left + right) / 2;

    if (mid == 0) {
      lcnt = neg_cnt * non_zero_pos_cnt;
      ucnt = lcnt;
      for (int64_t i = 0; i < zero_cnt; ++i) {
        ucnt += n - 1 - i;
      }
      assert(lcnt <= ucnt);
    } else if (mid < 0) {
      for (auto it = a.begin(); it != pos; ++it) {
        auto lcmp = [=](int64_t elem, int64_t val) {
          assert(val == mid);
          return elem * *it < val;
        };
        auto ucmp = [=](int64_t val, int64_t elem) {
          assert(val == mid);
          return elem * *it > val;
        };
        auto lit = lower_bound(a.rbegin(), rpos, mid, lcmp);
        auto uit = upper_bound(a.rbegin(), rpos, mid, ucmp);
        auto dl = lit - a.rbegin();
        auto du = uit - a.rbegin();
        assert(dl <= du);
        lcnt += dl;
        ucnt += du;
      }
    } else {
      for (auto it = a.begin(); it != pos; ++it) {
        auto lcmp = [=](int64_t elem, int64_t val) {
          assert(val == mid);
          return elem * *it < val;
        };
        auto ucmp = [=](int64_t val, int64_t elem) {
          assert(val == mid);
          return elem * *it > val;
        };
        auto end = make_reverse_iterator(it + 1);
        auto lit = lower_bound(rpos, end, mid, lcmp);
        auto uit = upper_bound(rpos, end, mid, ucmp);
        auto dl = pos_cnt + lit - rpos;
        auto du = pos_cnt + uit - rpos;
        assert(dl <= du);
        lcnt += dl;
        ucnt += du;
      }
      for (auto it = pos; it != a.end(); ++it) {
        auto lcmp = [=](int64_t elem, int64_t val) {
          assert(val == mid);
          return elem * *it < val;
        };
        auto ucmp = [=](int64_t val, int64_t elem) {
          assert(val == mid);
          return elem * *it > val;
        };
        auto lit = lower_bound(it + 1, a.end(), mid, lcmp);
        auto uit = upper_bound(it + 1, a.end(), mid, ucmp);
        auto dl = lit - it - 1;
        auto du = uit - it - 1;
        assert(dl <= du);
        lcnt += dl;
        ucnt += du;
      }
    }
    assert(lcnt <= ucnt);
    if (k <= lcnt) {
      right = mid;
    } else if (ucnt < k) {
      left = mid;
    } else {
      cout << mid << endl;
      return;
    }
  }
  assert(false);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}


Measured memory_bytes: 1792
// Author : Mohamed Sameh
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SZ(a) (int)a.size()
#define Flush fflush(stdout);
typedef long long ll ;
using namespace std ;
const int M = 100 ;
const int MAXV = 1e5+1;
const ll MAX = 2e18+9;
ll dp[M][MAXV];
int w[M],v[M];
int N , W ;
ll solve(int i , int rm)
{
  if (!rm)return 0;
  if (rm < 0 || i == N) return MAX;
  ll &ret = dp[i][rm];
  if (~ret)return ret;
  ret = solve(i+1, rm);
  ret = min(ret, w[i] + solve(i+1, rm - v[i]));
  return ret;
}
int main ()
{
    scanf ("%d%d" , &N ,&W);
    for (int i =0 ; i < N ;i++)
    {
        scanf ("%d%d" ,w+i , v+i);
    }
    memset(dp, -1, sizeof dp);
    int ans = 0;
    for (int i= 0 ; i < MAXV ;i++)
    {
      if (solve(0, i) <= W)
        ans = i;
    }
    printf ("%d\n" , ans);
}


Measured memory_bytes: 81888
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;

const int MOD=998244353;
int INF=100100100100100;

int add(int a,int b){
  return (a+b)%MOD;
}
int prod(int a,int b){
  return (a*b)%MOD;
}
int beki(int a,int b)
{
	if(b==0)return 1;
	int x=beki(a,b/2);
	if(b%2==0)return (x*x)%MOD;
	else return (((a*x)%MOD)*x)%MOD;
}
int inv(int a)
{
	return beki(a,MOD-2);
}
int a[310];
int dp[310][90010];
int dp2[310][90010];
signed main(){
  int n;cin>>n;
  int sum=0;
  int ans=0;
  rep(i,n){
    cin>>a[i];
    sum+=a[i];
  }
  dp[0][0]=1;
  dp2[0][0]=1;
  for(int i=0;i<n;i++){
    rep(j,90005){
      int po=max(j-a[i],(int)0);
      dp[i+1][j]=add(2*dp[i][j],dp[i][po]);
      //
      if(j-a[i]>=0)dp2[i+1][j]=add(dp2[i][j],dp2[i][j-a[i]]);
      else dp2[i+1][j]=dp2[i][j];
      
    }
  }
  int mid=(sum+1)/2;
  ans=prod(3,dp[n][mid]);
  ans=add(beki(3,n),MOD-ans);
  if(sum%2==0)ans=add(ans,prod(3,dp2[n][mid]));
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 425472
//dlang template---{{{
import std.stdio;
import std.conv;
import std.string;
import std.array;
import std.algorithm;
import std.typecons;
import std.math;
import std.range;

// MIT-License https://github.com/kurokoji/nephele
class Scanner
{
  import std.stdio : File, stdin;
  import std.conv : to;
  import std.array : split;
  import std.string;
  import std.traits : isSomeString;

  private File file;
  private char[][] str;
  private size_t idx;

  this(File file = stdin)
  {
    this.file = file;
    this.idx = 0;
  }

  this(StrType)(StrType s, File file = stdin) if (isSomeString!(StrType))
  {
    this.file = file;
    this.idx = 0;
    fromString(s);
  }

  private char[] next()
  {
    if (idx < str.length)
    {
      return str[idx++];
    }

    char[] s;
    while (s.length == 0)
    {
      s = file.readln.strip.to!(char[]);
    }

    str = s.split;
    idx = 0;

    return str[idx++];
  }

  T next(T)()
  {
    return next.to!(T);
  }

  T[] nextArray(T)(size_t len)
  {
    T[] ret = new T[len];

    foreach (ref c; ret)
    {
      c = next!(T);
    }

    return ret;
  }

  void scan()()
  {
  }

  void scan(T, S...)(ref T x, ref S args)
  {
    x = next!(T);
    scan(args);
  }

  void fromString(StrType)(StrType s) if (isSomeString!(StrType))
  {
    str ~= s.to!(char[]).strip.split;
  }
}

//Digit count---{{{
int DigitNum(int num) {
  int digit = 0;

  while (num != 0) {
    num /= 10;
    digit++;
  }

  return digit;
}
//}}}
//}}}

void main() {
  Scanner sc = new Scanner;

  int N, K;
  sc.scan(N, K);

  int[] h = new int[N];
  foreach (i; 0 .. N)
    sc.scan(h[i]);

  sort(h);

  int min = abs(h[0] - h[K - 1]);
  foreach (i; 1 .. (N - K) + 1) {
    if (min > abs(h[i] - h[i + K - 1]))
      min = abs(h[i] - h[i + K - 1]);
  }

  writeln(min);
}


Measured memory_bytes: 3324
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void){
  long long int v;
  int n, a=0, b=0, c, l;
  scanf("%d %lld",&n, &v);
  c = v/1000;
  //printf("c: %d\n",c);
  l = c-n;
  if(l<0) printf("-1 -1 -1\n");
  else if(l==0) printf("0 0 %d\n",c);
  else{
    if(5*l<=4*c) b=l/4;
    else b=c/5;
    l-=4*b;  c-=5*b;
    if(b<2*l) printf("-1 -1 -1\n");
    else printf("%d %d %d\n",l,b-2*l,c);
  }
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N,K,s;
  cin >> N >> K >> s;
  if(s < 1000000000) {
    rep(i,K) {
      cout << s << " ";
    }
    rep(i,N-K) {
      cout << s+1 << " ";
    }
    cout << endl;
  } else {
    rep(i,K) {
      cout << s << " ";
    }
    rep(i,N-K) {
      cout << 1 << " ";
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,M,p;
vector<int>D;//???????????????????§?

int solve(){
    if(D.size()==1){
        return D[0]<N/2?D[0]:N-D[0];
    }
    
    int ans=min(D.back(),N-D[0]);
    for(int i=0;i<M-1;i++){
        int d=D[i]<N/2?D[i]:N-D[i+1];
        d=d+N-D[i+1]+D[i];
        ans=min(ans,d);
    }
    return ans;
}

int main(void){
  int k;
  cin>>N>>M>>p;
  for(int i=0;i<M;i++){
      cin>>k;
     k= k>p?k-p:k+N-p;
      D.push_back(k);
  }
  sort(D.begin(),D.end());
  cout<<100*solve()<<endl;
  return 0;
}

Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
 
int main() {
   long long zian,sunio,eats;
   cin >> zian >> sunio >> eats;
   if(eats < zian) cout << zian - eats << " " << sunio << endl;
   else if (eats <= zian + sunio) cout << "0 " << sunio - (eats-zian) << endl;
   else cout <<"0 0\n";
   return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

using namespace std;

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

int main() {
	int fpb = 0, n, x[100010];
	scanf("%d", &n);
	for (int i = 0; i <= n; i++)
		scanf("%d", &x[i]);
	sort(x, x + n + 1);
	for (int i = 0; i < n; i++)
		fpb = gcd(x[i + 1] - x[i], fpb);
	printf("%d\n", fpb);
	return 0;
}

Measured memory_bytes: 512
#!/usr/bin/ruby
while(n=gets.to_i)>0 do
	idx=[]
	m=[]
	n.times{m.push gets.split.map(&:to_i);idx.push [0]*n}
	m.length.times{|i|idx[i][m[i].enum_for(:each_with_index).min[1]]+=1}
	m.length.times{|i|idx[m.transpose[i].enum_for(:each_with_index).max[1]][i]+=2}
	k=0
	n.times{|i|n.times{|j|k=m[i][j] if idx[i][j]==3}}
	p k
end

Measured memory_bytes: 2400
#include <iostream>

using namespace std;

int main(){
  int n;
  int house[4][3][10] = {};
  int b,r,f,v;

  cin >> n;
  for(int i = 0; i < n; ++i){
    cin >> b >> r >> f >> v;
    house[b-1][r-1][f-1] += v;
  }

  for( int i = 0; i < 4; ++i){
    for( int j = 0; j < 3; ++j){
      for( int k = 0; k < 10; ++k){
        cout << " " << house[i][j][k];
      }
      cout << endl;
    }
    if( i != 3){
      cout << "####################" << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3112
while True:
	try:
		n = str(raw_input())
	except EOFError:
		break
	
	if n[0:3] == "ooo" or n[3:6] == "ooo" or n[6:9] == "ooo" or n[0:1]+n[3:4]+n[6:7] == "ooo" or n[1:2]+n[4:5]+n[7:8] == "ooo" or n[2:3]+n[5:6]+n[8:9] == "ooo" or n[0:1]+n[4:5]+n[8:9] == "ooo" or n[2:3]+n[4:5]+n[6:7] == "ooo":
		print "o"
		
	elif n[0:3] == "xxx" or n[3:6] == "xxx" or n[6:9] == "xxx" or n[0:1]+n[3:4]+n[6:7] == "xxx" or n[1:2]+n[4:5]+n[7:8] == "xxx" or n[2:3]+n[5:6]+n[8:9] == "xxx" or n[0:1]+n[4:5]+n[8:9] == "xxx" or n[2:3]+n[4:5]+n[6:7] == "xxx":
		print "x"
		
	else:
		print "d"

Measured memory_bytes: 6464