akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, long long> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define MAX_N (1<<19)
vector<int> seg[MAX_N*2-1];
vector<P> comp[MAX_N*2-1];

vector<int> xs;
long long query(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) {
    auto it = upper_bound(all(comp[k]), P(x, 1LL<<60));
    if (it == comp[k].begin()) return 0;
    return (--it)->_2;
  }
  long long s = 1LL*(xs[min(b, r)]-xs[max(a, l)])*(upper_bound(all(seg[k]), x) - seg[k].begin());
  s += query(a, b, x, k*2+1, l, (l+r)/2);
  s += query(a, b, x, k*2+2, (l+r)/2, r);
  return s;
}
void add(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return;
  comp[k].pb(P(x, xs[min(b, r)]-xs[max(a, l)]));
  if (a <= l && r <= b) {
    seg[k].pb(x);
    return;
  }
  add(a, b, x, k*2+1, l, (l+r)/2);
  add(a, b, x, k*2+2, (l+r)/2, r);
}

int N, M, Q;
int A[100000], B[100000], C[100000];
int X[100000], Y[100000];
long long J[100000];

signed main() {
  cin >> N >> M >> Q;
  rep(i, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--;
    xs.pb(A[i]), xs.pb(B[i]);
  }
  rep(i, Q) {
    cin >> X[i] >> Y[i] >> J[i];
    X[i]--;
    xs.pb(X[i]), xs.pb(Y[i]);
  }
  sort(all(xs)); uniq(xs);
  rep(i, M) A[i] = index(xs, A[i]), B[i] = index(xs, B[i]);
  rep(i, Q) X[i] = index(xs, X[i]), Y[i] = index(xs, Y[i]);

  rep(i, M) add(A[i], B[i], C[i]);
  rep(i, MAX_N*2-1) {
    sort(all(seg[i]));
    sort(all(comp[i]));
    if (!comp[i].empty()) rep(j, comp[i].size()-1) comp[i][j+1]._2 += comp[i][j]._2;
  }

  rep(i, Q) {
    int l = X[i], r = Y[i];
    long long k = J[i];
    long long lo = 0, hi = INF;
    while (hi - lo > 1) {
      int mid = (lo + hi) / 2;
      if (query(l, r, mid) >= k) hi = mid;
      else lo = mid;
    }
    cout << hi << "\n";
  }
  return 0;
}

Measured memory_bytes: 174176
n = int(input())
orig_n = n
res=[]
i = 2
half_n = n // 2
root_n = int(n ** (1/2))
is_prime = True
while i <= (root_n):
    if orig_n % i == 0:
        is_prime = False
        break
    i += 1
if is_prime: res.append(orig_n)

while i <= half_n and not(is_prime):
    if n ==1:
        break
    if n % i == 0:
        n = n // i
        res.append(i)
        i = 1
    i += 1

print("{0}: {1}".format(orig_n, " ".join(map(str, res))))

Measured memory_bytes: 7764
// ConsoleApplication7.cpp : Defines the entry point for the console application.
//

#include "iostream"
using namespace std;
typedef long long i64;
int n;
int D;
int Q;
i64 d[500005];
i64 a[500005];
i64 b[500005];
i64 q[500005];
bool f[500005];
int main()
{
	scanf("%d%d", &n, &D);
	for (int i = 0; i < n; ++i) {
		scanf("%d", d + i);
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; ++i) {
		scanf("%d", q + i);
		--q[i];
	}
	b[n] = 1;
	for (int i = 0; i < n; ++i) {
		if (abs((i > 0 ? a[i - 1] : 0) + d[i] - D) < abs((i > 0 ? a[i - 1] : 0) - D)) {
			a[i] = D - abs((i > 0 ? a[i - 1] : 0) + d[i] - D);
		}
		else {
			a[i] = (i > 0 ? a[i - 1] : 0);
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		if (d[i] >= 2 * b[i + 1]) {
			b[i] = b[i + 1];
		}
		else {
			b[i] = b[i + 1] + d[i];
		}
	}
	for (int i = 0; i < Q; ++i) {
		bool f = (q > 0 ? a[q[i] - 1] : 0) <= (D - b[q[i] + 1]);
		if (f) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	return 0;
}



Measured memory_bytes: 17536
import sys

A = list(list(map(int, input().split())) for _ in range(3))
N = int(input())
num = list(int(input()) for _ in range(N))

for i in range(3):
    for j in range(3):
        if A[i][j] in num:
            A[i][j] = -1
            
if A[0][0] == -1 and A[0][1] == -1 and A[0][2] == -1:
    print("Yes")
    sys.exit()
elif A[1][0] == -1 and A[1][1] == -1 and A[1][2] == -1:
    print("Yes")
    sys.exit()
elif A[2][0] == -1 and A[2][1] == -1 and A[2][2] == -1:
    print("Yes")
    sys.exit()
elif A[0][0] == -1 and A[1][0] == -1 and A[2][0] == -1:
    print("Yes")
    sys.exit()
elif A[0][1] == -1 and A[1][1] == -1 and A[2][1] == -1:
    print("Yes")
    sys.exit()
elif A[0][2] == -1 and A[1][2] == -1 and A[2][2] == -1:
    print("Yes")
    sys.exit()
elif A[0][0] == -1 and A[1][1] == -1 and A[1][1] == -1:
    print("Yes")
    sys.exit()
elif A[0][2] == -1 and A[1][1] == -1 and A[2][0] == -1:
    print("Yes")
    sys.exit()
    
print("No")

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

int main()
{
	int A,B,M;
	cin>>A>>B>>M;
	vector<int> a(A);
	vector<int> b(B);
	for(size_t i = 0; i<A; i++)
		cin>>a[i];
	for(size_t i = 0; i<B; i++)
		cin>>b[i];
	int ans = 0;
	ans += *min_element(a.begin(),a.end());
	ans += *min_element(b.begin(),b.end());
	int x,y,c;
	for(size_t i = 0; i<M; i++)
	{
		cin>>x>>y>>c; x--; y--;
		ans = min(ans,(a[x]+b[y]-c));
	}
	cout<<ans<<endl;
	return 0;
}

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

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

using node = pair<string, bool>; // left : true  right : false
map<node, ll> dp;
using P = pair<ll, node>;
priority_queue<P, vector<P>, greater<P>> que;

ll ans = INF;

void calcu (const string &left, const string &right, ll cost) {
    int l = (int)left.size(), r = (int)right.size();
    int i = l - 1, j = 0;
    while ( i >= 0 && j < r ) if ( left[i--] != right[j++] ) return;

    if (l == r) { chmin(ans,cost); return; }

    node save;
    if (l > r) save = node(left.substr(0, l-r), true);
    else save = node(right.substr(l), false);

    if ( dp.count(save) ) { if ( chmin(dp[save], cost) ) que.push(P(cost, save)); }
    else { dp[save] = cost; que.push(P(cost, save)); }
    return;
}

int main() {
    int n; cin >> n;
    vector<string> s(n);
    vector<ll> c(n);
    for (int i = 0; i < n; i++) cin >> s[i] >> c[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= (int)s[i].size(); j++) {
            string left = s[i].substr(0,j), right = s[i].substr(j);
            calcu(left, right, c[i]);
        }
        for (int j = 0; j < (int)s[i].size(); j++) {
            string left = s[i].substr(0,j), right = s[i].substr(j+1);
            calcu(left, right, c[i]);
        }
    }

    while (!que.empty()) {
        auto p = que.top(); que.pop();
        ll dist = p.first;
        string ns = p.second.first;
        if ( dist > dp[p.second] ) continue;
        for (int i = 0; i < n; i++) {
            if (p.second.second) calcu(ns, s[i], dist + c[i]);
            else calcu(s[i], ns, dist + c[i]);
        }
    }

    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

Measured memory_bytes: 3688
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    if(n%2 == 1) {
        out(0);
        re0;
    }

    ll p = 10;
    ll ans = 0;
    while(p <= n) {
        ans += n/p;
        p *= 5;
    }

    out(ans);
    re0;
}

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



int main()
{
    
    int a, b, c;

    cin >> a >> b >> c;
    bool flag = false;

    for(int i = 1; i <= b; i++)
    {
        
        if((i * a) % b == c)
        {
            flag = true;
            break;
        }
    }

    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define MAX 100000
#define LEN 100005


typedef struct pp{
  char name[100];
  int t;
}P;

void enqueue(P);
P dequeue(void);
int isEmpty(void);
int isFull(void);


P Q[LEN+1];
int head, tail, n;


void enqueue(P x){
  if(isFull()==1){
    printf("error! overflow");
  }
  Q[tail]=x;
  if(tail+1==MAX) tail=0;
  else tail++;
}

P dequeue(void){
  P a1;
  if(isEmpty()==1){
    printf("error! underflow");
  }
  a1=Q[head];
  if(head+1==MAX) head=0;
  else head++;
  return a1;

}

int isFull(void){
  if((head==tail+1)%MAX) return 1;
  else return 0;
}
int isEmpty(void){
  if(head==tail) return 1;
  else return 0;
}

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head=1;
  tail=n+1;
  while(n!=0){
    u=Q[head];
    u.t=Q[head].t-q;
    if(u.t>0){
      elaps=elaps+q;
      enqueue(u);
      Q[head]=dequeue();
    }
    else{
      elaps=elaps+Q[head].t;
      printf("%s %d\n",u.name,elaps);
      Q[head]=dequeue();
      n--;
    }
  }


  
  return 0;
}

Measured memory_bytes: 10756
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
template <class Key, class Compare = less<Key>>
using Tree = __gnu_pbds::tree<Key, __gnu_pbds::null_type, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;



int N;
ll a[3000];
ll dp[3003][3003][2];

ll dfs(int i, int j, int p) {
  ll& res = dp[i][j][p];
  if (res != -1) {
    return res;
  } else {
    if (p == 0) { // taro
      if (i == j) {
        return res = a[i];
      } else {
        return res = max(a[i] + dfs(i+1, j, 1), a[j] + dfs(i, j-1, 1));
      }
    } else { // jiro
      if (i == j) {
        return res = -a[i];
      } else {
        return res = min(-a[i] + dfs(i+1, j, 0), -a[j] + dfs(i, j-1, 0));
      }
    }
  }
}

void Main() {
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
  }
  memset(dp, -1, sizeof(dp));
  ll ans = dfs(0, N-1, 0);
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
//  cin.tie(nullptr);
  #ifdef _DEBUG
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  #endif
  Main();
  return 0;
}


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

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

    ll count = 0;
    char last = '#';
    rep(i, n){
        if(s[i]!=last) ++count;
        last = s[i];
    }
    cout << count << endl;
}


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

bool isPalindromic(int n) {
  vector<int> v(5);
  for(int i = 0; i < 5; i++) {
    v.at(i) = n % 10;
    n /= 10;
  }
  if(v.at(0) == v.at(4) && v.at(1) == v.at(3)) {
    return true;
  } else {
    return false;
  }
}

int main(void){
  int a, b;
  cin >> a >> b;
  
  int count = 0;
  
  for (int i = a; i >= a && i <= b; i++) {
    if (isPalindromic(i)) count++;
  }
  cout << count << endl;
}

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

int main()
{
    string S;
    cin>>S;
    int n = S.length();
    int a=0,b=0,c=0;
    for(int i=0; i<n; i++)
    {
        if(S[i]=='a')
            a++;
        else if (S[i] == 'b')
            b++;
        else if(S[i]=='c')
            c++;
    }
    if(max(max(a,b),c)-min(min(a,b),c)<=1)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 512
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

from collections import deque

MOD = 10**9+7
INF = float('inf')

def inv(n): return pow(n, MOD-2, MOD)

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

N = int(input())
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
p = [-1 for i in range(N)] 
a = [[] for i in range(N)]

shori = []
def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    shori.append(u)
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      p[v] = u
      a[u].append(v)
      q.append(v)
  return d

bfs(graph,0)

size = [0 for i in range(N)]
def calc_size(x):
  if size[x]: return size[x]
  temp = 1
  for y in a[x]:
    temp += calc_size(y)
  size[x] = temp
  return size[x]
calc_size(0)

narabi = [0 for i in range(N)]
def calc_narabi(x):
  if narabi[x]: return narabi[x]
  temp = kaijo(size[x]-1)
  for y in a[x]:
    temp *= gyaku_kaijo(size[y])*calc_narabi(y)
    temp %= MOD
  narabi[x] = temp
  return narabi[x]
calc_narabi(0)

pnarabi = [1 for i in range(N)]
for i in shori[1:]:
  pnarabi[i] = narabi[p[i]] * inv(narabi[i]) * inv(nCr(size[p[i]]-1,size[i])) * pnarabi[p[i]] * nCr(N-1-size[i],N-size[p[i]])
  pnarabi[i] %= MOD

for i in shori[1:]:
  temp = narabi[i] * nCr(N-1,size[i]-1) *pnarabi[i]
  temp %= MOD
  narabi[i] = temp

print(*narabi,sep="\n")

Measured memory_bytes: 207704
#include<stdio.h>
int main()
{
	int n,m,i;
	for(;scanf("%d%d",&n,&m),n;printf("%d %d\n",n,i))
	{
		if(n<m)
			m^=n^=m^=n;
		for(i=0;m!=0;i++)
		{
			n=n%m;
			m^=n^=m^=n;
		}
	}
	return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int x = N%10;

		if (x == 3) {
			System.out.println("bon");
		} else if (x == 0 || x == 1 || x == 6 || x == 8) {
			System.out.println("pon");
		} else {
			System.out.println("hon");
		}
	}
}

Measured memory_bytes: 35792
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

#define REP(i,n) for(ll i =0;i<n;++i)

constexpr ll INF = 1e9 + 1;
vector<ll> x, cnt, sum;
ll  a;
void init(vector<vector<int>>& g, int i, int p) {
	ll cnt0 = 1, sum0 = x[i];
	REP(j, g[i].size()) {
		if (g[i][j] == p)continue;
		init(g, g[i][j], i);
		cnt0 += cnt[g[i][j]];
		sum0 += sum[g[i][j]];
	}
	cnt[i] = cnt0;
	sum[i] = sum0;
}

ll f(int v, int i) {
	//cout<<v<<endl;
	return abs(a * cnt[v] + i - sum[v]);
}

vector<ll> merge(vector<ll>& l, vector<ll>& r, int rv) {
	//cout<<l.size()<<" "<<r.size()<<endl;
	vector<ll> res(l.size() + r.size() - 1, INF * INF);
	REP(i, l.size())REP(j, r.size()) {
		res[i + j] = min(res[i + j], l[i] + r[j] + f(rv, j));
	}

	//cout<<"end"<<endl;
	return res;

}
void dfs(vector<vector<int>>& g, vector<vector<ll>>& dp, int v, int p) {
	vector<ll> res(2, 0);
	REP(i, g[v].size()) {
		if (g[v][i] == p)continue;
		dfs(g, dp, g[v][i], v);
		res = merge(res, dp[g[v][i]], g[v][i]);
		// cout<<g[v][i]<<endl;
	}
	dp[v] = res;
}
int main() {
	int n; cin >> n;
	x.resize(n);
	cnt.resize(n);
	sum.resize(n);
	REP(i, n)cin >> x[i];
	vector<vector<int>>g(n);
	REP(i, n - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	init(g, 0, -1);
	a = sum[0] / n;
	vector<vector<ll>> dp(n);
	dfs(g, dp, 0, -1);
	cout << dp[0][sum[0] % n] << endl;
}



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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

llint gcd(llint a, llint b) {
    if (a<b) swap(a, b);

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

llint lcm(llint a, llint b) {
    return (a/gcd(a, b)*b);
}

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

    llint t, ans;
    for(int in=0;in<n;in++) {
        cin >> t;
        if(in==0) ans = t;
        else {
            ans = lcm(ans, t);
        }
    }
    cout << ans << endl;
    return 0;
}


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

const double eps = 1e-10;

int dcmp(double x) {
        if(fabs(x) < eps) return 0;
        return x < 0 ? -1 : 1;
}

bool same(double a, double b) {return dcmp(a - b) == 0;}
#define Vector P
struct P {
        double x, y;
        P(double x = 0, double y = 0): x(x), y(y) {}
        P operator + (P b) {return P(x + b.x, y + b.y);}
        P operator - (P b) {return P(x - b.x, y - b.y);}
        P operator * (double b) {return P(x * b, y * b);}
        P operator / (double b) {return P(x / b, y / b);}
        double operator * (P b) {return x * b.x + y * b.y;} // Dot
        double operator ^ (P b) {return x * b.y - y * b.x;} // Cross
        double abs() {return hypot(x, y);}
        P unit() {return *this / abs();}
        P spin(double o) {
                double c = cos(o), s = sin(o);
                return P(c * x - s * y, s * x + c * y);
        }
};

struct Line {
        //ax + by + c = 0
        double a, b, c, theta;
        P pa, pb;
        Line(): a(0), b(0), c(0), theta(0), pa(), pb() {}
        Line(P pa, P pb): a(pa.y - pb.y), b(pb.x - pa.x), c(pa ^ pb), theta(atan2(-a, b)), pa(pa), pb(pb) {}        P projection(P p) {return pa + (pb - pa).unit() * ((pb - pa) * (p - pa) / (pb - pa).abs());}                P reflection(P p) {return p + (projection(p) - p) * 2;}
        double get_ratio(P p) {return (p - pa) * (pb - pa) / ((pb - pa).abs() * (pb - pa).abs());}
        P dis(P p) {return ((pb - pa) ^ (p - pa)) / (pb - pa).abs();} // directed distance
};

struct Circle {
        P c;
        double r;
        Circle(P c, double r = 0): c(c), r(r) {}
};
bool onsegment(P p, P a, P b) {
        return dcmp((a - p) ^ (b - p)) == 0 && dcmp((a - p) * (b - p)) <= 0;
}
bool segment_intersection(P p1, P p2, P p3, P p4) { // end points are not allowed
        return dcmp((p2 - p1) ^ (p3 - p1)) * dcmp((p2 - p1) ^ (p4 - p1)) < 0
                && dcmp((p4 - p3) ^ (p1 - p3)) * dcmp((p4 - p3) ^ (p2 - p3)) < 0;

}
bool parallel(Line l1, Line l2) {return same(l1.a * l2.b, l1.b * l2.a);}
P line_intersection(Line l1, Line l2) {
        return P(-l1.b * l2.c + l1.c * l2.b, l1.a * l2.c - l1.c * l2.a) / (-l1.a * l2.b + l1.b * l2.a);     }
double Area(vector<P> &p) {
        double res = 0;
        for(int i = 1; i < (int)p.size() - 1; i++)
                res += (p[i] - p[0]) ^ (p[i + 1] - p[0]);
        return res * 0.5;
}
int main() {
        ios_base::sync_with_stdio(false); cin.tie(0);
        int n; cin >> n;
        vector<P> vec;
        for(int i = 0; i < n; i++) {
                P p; cin >> p.x >> p.y;
                vec.push_back(p);
        }
        bool flag = 1;
        for(int i = 0; i < n; i++) {
                P p0 = vec[i], p1 = vec[(i + 1) % n], p2 = vec[(i + 2) % n];
                Vector v1 = p1 - p0, v2 = p2 - p1;
                if(dcmp(v1 ^ v2) == -1) flag = 0;
        }
        cout << flag << '\n';
        return 0;
}


Measured memory_bytes: 3296
h, w = map(int, input().split())
c = []
for i in range(10):
    c.append(list(map(int, input().split())))
a = []
for i in range(h):
    a.append(list(map(int, input().split())))
cost = [float("inf") for i in range(10)]
flag = [False for i in range(10)]
cost[1] = 0
test = [1]
while test:
    num = test.pop(0)
    flag[num] = True
    for i in range(10):
        cost[i] = min(cost[i], cost[num] + c[i][num])
    temp = [[cost[i], i] for i in range(10)]
    temp.sort()
    for i in range(10):
        if flag[temp[i][1]] == True:
            continue
        else:
            test.append(temp[i][1])
            break
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == -1:
            continue
        else:
            ans += cost[a[i][j]]
print(ans)

Measured memory_bytes: 9580
import math
from itertools import combinations
N, D = map(int, input().split())
X = [list(map(int , input().split())) for i in range(N)]
P = list(combinations(range(1,N+1), 2))
#print(X)
count = 0
for p in P :
    x = X[p[0] - 1]
    y = X[p[1] - 1]
    #print(x,y)
    ans = 0
    for d in range(D) :
        ans += (x[d] - y[d]) * (x[d] - y[d])
    ans = math.sqrt(ans)
    #print(ans)
    if ans.is_integer() :
        count += 1
print(count)


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

#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define int long long
#define endl '\n'

using namespace std;

const int N = 2e5 + 77;
vector<int> g[N];
int n , m , vis[N] ,ans , c;

void dfs(int x){
    if(vis[x]) return;
    vis[x] = 1;
    c++; 
    for(auto i : g[x]) dfs(i);
}

int32_t main(){
    cin >> n >> m ;
    for(int i = 0 ; i < m ; ++i){
        int a , b ; cin >> a >> b ;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1 ; i <= n ; ++i){
        if(vis[i]) continue;
        dfs(i);
        ans = max(ans,c);
        c = 0;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 22324
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define T(a, b, c) make_pair(a, make_pair(b, c))
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	ll n, k;
	cin >> n >> k;
	ll q = n % k;
	ll p = k - q;
	cout << min(q, p);





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
ll gcd(ll a,ll b){
    ll m = min(a,b);
    ll M = max(a,b);
    if(M%m==0){
        return m;
    }else{
        return gcd(m,M%m);
    }
}
ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}
int main(){
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    ll ans=b-a+1;
    ans -= b/c-(a-1)/c;
    ans -= b/d-(a-1)/d;
    ll e = lcm(c,d);
    ans += b/e-(a-1)/e;
    cout<<ans<<endl;

    

  return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#define MAX 10000
  
struct node{
  int p, q, r;
};
struct node T[MAX];
int n;
  
void preorder(int t){
  if(t == -1) return;
  printf(" %d",t);
  preorder(T[t].q);
  preorder(T[t].r);
}
  
void inorder(int t){
  if(t == -1) return;
  inorder(T[t].q);
  printf(" %d",t);
  inorder(T[t].r);
}
  
void post(int t){
  if(t == -1) return;
  post(T[t].q);
  post(T[t].r);
  printf(" %d",t);
}
  
int main(){
  int i, v, q, r, root;
  
  scanf("%d", &n);
  for(i = 0; i < n; i++) T[i].p = -1;
  
  for(i = 0; i < n; i++){
    scanf("%d %d %d", &v, &q, &r);
    T[v].q = q;
    T[v].r = r;
    if(q != -1) T[q].p = v;
    if(r != -1) T[r].p = v;
  }
  
  for(i = 0; i < n; i++)
    if(T[i].p == -1) root = i;
  printf("Preorder\n");
  preorder(root);
  printf("\n");
  printf("Inorder\n");
  inorder(root);
  printf("\n");
  printf("Postorder\n");
 post(root);
  printf("\n");
  
  return 0;
}

Measured memory_bytes: 620
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <unordered_map>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

long long GCD(long long a, long long b) {
    if(b == 0)
        return a;
    else
        return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}
bool compare_by_a(pair<int, long long> a, pair<int, long long> b) {
    if(a.first != b.first) {
        return a.first > b.first;
    } else {
        return a.second < b.second;
    }
}
vector<pair<int, int>> ap(vector<int> ve) {
    vector<pair<int, int>> res;
    unordered_map<int, int> st;
    rep(i, 0, ve.size()) {
        int p = ve[i];
        auto itr = st.find(p);
        if(itr != st.end()) {
            st[p]++;
        } else {
            st.emplace(p, 1);
        }
    }
    st.emplace(0, 0);
    for(auto itr = st.begin(); itr != st.end(); ++itr) {
        pair<int, int> p;
        p.first = itr->second;
        p.second = itr->first;
        res.push_back(p);
    }
    sort(res.begin(), res.end(), compare_by_a);
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<int> ki;
    vector<int> gu;
    rep(i, 1, n + 1) {
        int a;
        cin >> a;
        if(i % 2 == 1) {
            ki.push_back(a);
        } else {
            gu.push_back(a);
        }
    }
    vector<pair<int, int>> apki;
    vector<pair<int, int>> apgu;
    apki = ap(ki);
    apgu = ap(gu);
    if(apki[0].second != apgu[0].second) {
        cout << n - apki[0].first - apgu[0].first << endl;
    } else {
        int res = min(n - apki[1].first - apgu[0].first,
                      n - apki[0].first - apgu[1].first);
        cout << res << endl;
    }
}

Measured memory_bytes: 4172
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using E = System.Linq.Enumerable;
using System.IO.Pipes;
using System.Threading;

class Program
{
    static char[] abc = "abcdefghijklmnopqrstuvwxyz".ToCharArray();
    static long mod = 1000000007;
    static void Main(string[] args)
    {
        //var S = Console.ReadLine();
        //var N = long.Parse(Console.ReadLine());
        //var N = long.Parse(Console.ReadLine());
        var NP = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
        var N = NP[0];
        var P = NP[1];

        var dic = PrimeFactorization(P);
        long ans = 1;
        foreach (var item in dic)
        {
            ans *= (long)Math.Pow(item.Key, item.Value/N);
        }

        Console.WriteLine(ans);

    }

    public static Dictionary<long, long> PrimeFactorization(long n)
    {
        var result = new Dictionary<long, long>();

        for (long i = 2; i * i <= n; i++)
        {
            if (n % i != 0) continue;
            long exponents = 0;

            // 割り続ける
            while (n % i == 0)
            {
                exponents++;
                n /= i;
            }

            result[i] = exponents;
        }

        // 素数が残っている場合
        if (n != 1) result[n] = 1;
        return result;
    }

}

Measured memory_bytes: 28524
def dijkstra(s, g):
    import heapq

    n = len(g)
    heap = [(0, s)]
    heapq.heapify(heap)

    prev = [-1] * n
    cost = [float("Inf")] * n
    cost[s] = 0

    while heap:
        c, v = heapq.heappop(heap)
        x = cost[v]
        if c > x:
            continue
        for d, u in g[v]:
            path = d + x
            if path < cost[u]:
                cost[u] = path
                prev[u] = v
                heapq.heappush(heap, (path, u))

    return prev, cost


def main():
    from collections import deque

    n, *uv = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for i, j in zip(*[iter(uv)] * 2):
        g[i].append([1, j])
        g[j].append([1, i])

    dk, cost = dijkstra(n, g)
    l = cost[1] - 1
    k = l // 2 if l % 2 == 0 else l // 2 + 1
    vis = [False] * (n + 1)

    def f(now):
        if vis[now]:
            return 0
        vis[now] = True
        c = 1
        for _, nxt in g[now]:
            c += f(nxt)

        return c

    nw = dk[1]

    cnt = []
    i = 0
    vis[1] = True
    vis[n] = True
    while i < k:
        i += 1
        nx = dk[nw]
        vis[nx] = True
        tmp = f(nw)
        vis[nx] = False
        cnt.append(tmp)
        nw = nx

    fn = 0
    q = deque([1])
    vis[1] = False

    while q:
        i = q.popleft()
        if vis[i]:
            continue

        vis[i] = True
        fn += 1
        for _, j in g[i]:
            q.appendleft(j)

    fn += sum(cnt)
    sn = n - fn

    print("Fennec" if fn > sn else "Snuke")


if __name__ == '__main__':
    main()


Measured memory_bytes: 49216
n,m = map(int,input().split())
g = list(map(int, input().split()))
n_ = max(g)+1
l = [False]*n_
p = [0]*m
b = [0]*m
for x in g:
  b[x%m] += 1
  if l[x]:
    p[x%m] += 2
    l[x] = False
  else:
    l[x] = True
ans = b[0]//2
for i in range(1,(m+1)//2):
  cur = min(b[i],b[m-i])
  ans += cur
  ans += min(b[i]-cur, p[i])//2
  ans += min(b[m-i]-cur,p[m-i])//2
if not m%2:
  ans += b[m//2]//2
print(ans)

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

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int aka[][]=new int[n][2];
		int ao[][]= new int[n][2];
		for(int i=0;i<n;i++) {
			aka[i][0]=sc.nextInt();
			aka[i][1]=sc.nextInt();
		}
		for(int i=0;i<n;i++) {
			ao[i][0]=sc.nextInt();
			ao[i][1]=sc.nextInt();
		}

		Arrays.sort(aka, (a, b) -> Integer.compare(a[0], b[0]));
		Arrays.sort(ao, (a, b) -> Integer.compare(a[0], b[0]));


		int count=0;
		boolean used[]= new boolean[n];
		for(int i=0;i<n;i++) {
			used[i]=false;
		}

		for(int i=0;i<n;i++) {
			int k=0;

			for(int j=0;j<n;j++) {
				if(!used[j]){
					k=j;
					break;

				}
			}

			for(int j=k;j<n&&aka[j][0]<ao[i][0];j++) {
				if(!used[j]) {
					if(aka[k][1]<ao[i][1]) {
						if(aka[k][1]<=aka[j][1]&&aka[j][1]<ao[i][1]) {
							k=j;
						}
					}
					else {
						if(aka[j][1]<ao[i][1]) {
							k=j;
						}
					}
				}

			}

			if(!used[k]&&aka[k][0]<ao[i][0]&&aka[k][1]<ao[i][1]){
				used[k]=true;
				count++;
			}
		}

		System.out.print(count);
	}

}


Measured memory_bytes: 28244
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
count = B[A[0]-1]
j = 0
for i in range(1,N):
    manzoku = B[A[i]-1]
    if A[i-1] == A[i]-1:
        # print("C",C[A[i-1]-1])
        manzoku += C[A[i-1]-1]
    count += manzoku
print(count)


Measured memory_bytes: 3064
N=int(input())
L=['a','b','c','d','e','f','g','h','i','j']

A = [L[0]]
B = [A[0]+L[i] for i in range(2)]
C = [i+L[j] for i in B for j in range(len(set(i))+1)]
D = [i+L[j] for i in C for j in range(len(set(i))+1)]
E = [i+L[j] for i in D for j in range(len(set(i))+1)]
F = [i+L[j] for i in E for j in range(len(set(i))+1)]
G = [i+L[j] for i in F for j in range(len(set(i))+1)]
H = [i+L[j] for i in G for j in range(len(set(i))+1)]
I = [i+L[j] for i in H for j in range(len(set(i))+1)]
J = [i+L[j] for i in I for j in range(len(set(i))+1)]

Z = [A,B,C,D,E,F,G,H,I,J]

for i in Z[N-1]:
    print(i)

Measured memory_bytes: 14592
#include <iostream>

using namespace std;

int main(void){
    int N, M, sum=0, res=0;
    cin >> N >> M;
    int A[N];
    for(int i=0; i<N; i++) {
        cin >> A[i];
        sum += A[i];
    }

    for(int i=0; i<N; i++){
        res += (A[i] >= sum * (1.0 / (4*M))) ? 1 : 0;
    }
    cout << (res>=M ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using p = pair<int, int>;

int n, t;
int dx[6] = {0, 1, 1, 0, -1, -1};
int dy[6] = {1, 1, 0, -1, -1, 0};
map<p, bool> mp;
p st;

int solve();

int main() {
  while(1) {
    cin >> t >> n;
    if(t + n == 0) break;
    for(int i = 0; i < n; ++i) {
      int x, y;
      cin >> x >> y;
      mp[{x + 60, y + 60}] = 1;
    }
    cin >> st.fi >> st.se;
    st.fi += 60;
    st.se += 60;
    cout << solve() << endl;
    mp.erase(mp.begin(), mp.end());
  }
  return 0;
}

int solve() {
  vector<vector<int>> v;
  int ans = 0;
  queue<p> qu;
  v.resize(121);
  for(int i = 0; i < 121; ++i) v[i].assign(121, -1);
  v[st.fi][st.se] = 0;
  qu.push(st);
  while(qu.size() > 0) {
    p now = qu.front();
    qu.pop();
    int nowt = v[now.fi][now.se];
    if(nowt >= t) continue;
    for(int i = 0; i < 6; ++i) {
      p nextp = now;
      nextp.fi += dx[i];
      nextp.se += dy[i];
      if(mp.find(nextp) != mp.end() ||
         v[nextp.fi][nextp.se] >= 0)
        continue;
      v[nextp.fi][nextp.se] = nowt + 1;
      qu.push(nextp);
    }
  }
  for(int i = 0; i < 121; ++i)
    for(int j = 0; j < 121; ++j)
      if(v[i][j] >= 0 && v[i][j] <= t) ++ans;
  return ans;
}


Measured memory_bytes: 3240
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int a, b;
    cin >> a >> b;
    int res = 0;
    if (a >= 13)res = b;
    else if (a >= 6)res = b / 2;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int isprime(int n){
	int i;
	for( i = 2; i * i <= n; i++){
		if( n % i == 0) return 0;
	}
	return 1;
}

int main(){
	int n, i;
	while(1){
		scanf("%d", &n);
		if( n == 0) break;
		int max = 0;
		for( i = n; i >=2; i--){
			if( isprime(i)){
				if(isprime( i - 2)){
					max = i;
					break;
				}
			}
		}
		printf("%d %d\n", max - 2, max);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i,l,r) for(int i=l;i<=r;i++)
vector<int>dp(100001,-1);
int fun(int n,int h[])
{    
     

      if(dp[n]!=-1)return dp[n];

       if(n==0)
    {
        dp[0]=0;
        return 0;
    }
      if(n==1)
     {
        dp[1]=abs(h[1]-h[0]);
        return dp[1];
     }
    
   dp[n]=min(abs(h[n]-h[n-1])+fun(n-1,h),abs(h[n]-h[n-2])+fun(n-2,h));
    return dp[n];
}
signed main()
{  // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
   
   int h[n];
   for(int i=0;i<n;i++)cin>>h[i];

   cout<<fun(n-1,h);
    return 0;
}

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

int main() {
    string S;
    cin >> S;
    if(S == "Sunny") {
        cout << "Cloudy" << endl;
    }
    else if(S == "Cloudy"){
        cout << "Rainy" << endl;
    }
    else cout << "Sunny" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int N, M;
    long d[100][100];
    long e[100][100];
    cin >> N >> M;

    for(int i = 0; i < N; i++){
        d[i][i] = 0;
        for(int j = 0; j < N; j++){
            d[i][j] = INT32_MAX;
            e[i][j] = INT32_MAX;
        }
    }
    for(int i = 0; i < M; i++){
        int a, b, c;
        cin >> a >> b >> c;
        d[a-1][b-1] = c;
        d[b-1][a-1] = c;
        e[a-1][b-1] = c;
        e[b-1][a-1] = c;
    }
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < i; j++){
            
            if(e[i][j] != INT32_MAX && e[i][j] > d[i][j] && i != j) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,m,k,tot,a[N][N];
char s[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(s[i][j]=='#')
    {
        a[i][j]=++tot;
        for(int k=i+1;k<=n&&s[k][j]=='.';k++)
            a[k][j]=a[k-1][j];
    }
    for(int i=n;i>=1;i--)
        for(int j=1;j<=m;j++)
        if(!a[i][j])
        a[i][j]=a[i+1][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(!a[i][j])
        a[i][j]=a[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
        if(!a[i][j])
        a[i][j]=a[i][j+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        printf(j==m?"%d\n":"%d ",a[i][j]);
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

int N, A[2020];
bitset<4020202> bit;
int SUM;

void solve() {
    bit[0] = 1;
    FOR(N) {
        SUM += A[i];
        bit |= (bit << A[i]);
    }
    int ans;
    FOR(i, (SUM + 1) / 2, INF) {
        if (bit[i]) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N;
    FOR(N)
    cin >> A[i];
    solve();
    return 0;
}


Measured memory_bytes: 1920
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**18

def bfs(start):
    d = [INF]*n
    d[start] = 0
    q = collections.deque([])
    q.append(start)
    pre = [0]*(n)
    while q:
        c = q.popleft()
        next_v = edge[c]
        for v in next_v:
            if v == 0 and start != 0:
                d[v] = d[c]+1
                pre[v] = c
                return [pre,d]
            if d[v] == INF and v != c:
                q.append(v)
                d[v] = d[c]+1
                pre[v] = c
    #経路を復元したい
    return [pre,d]
n,m = map(int,input().split())
edge =[[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
ans = bfs(0)
judge = ans[1]
for i in judge:
    if i == INF:
        print("No")
        sys.exit()
print("Yes")
for i in range(1,n):
    print(ans[0][i]+1)

Measured memory_bytes: 96300
N = int(input())
red = [list(map(int, input().split())) for _ in range(N)]
blue = [list(map(int, input().split())) for _ in range(N)]
blue.sort()
flg = [0]*N
for i in range(N):
    tmp_y = -1
    tmp_index = -1
    for k in range(N):
        if blue[i][0] > red[k][0] and flg[k] == 0:
            if tmp_y < red[k][1] and blue[i][1] > red[k][1]:
                tmp_y = red[k][1]
                tmp_index = k
    if tmp_index != -1:
        flg[tmp_index] = 1
print(flg.count(1))

Measured memory_bytes: 3316
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <cstdint>
#include <tuple>
#include <numeric>
#define M_PI       3.14159265358979323846


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define MT make_tuple
#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 FILL(a, x) memset(a, x, sizeof(a))

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int main() {
	int n;
	scanf("%d", &n);
	VI v(n), c(n);
	REP(i, n)scanf("%d", &v[i]);
	REP(i, n)scanf("%d", &c[i]);
	int ret = 0;
	REP(i, n)ret += max(v[i] - c[i], 0);
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 50000001
using namespace std;
typedef pair<int,int> P;
int n,k;
int c[5000],r[5000],d[5000];
vector<int> G[5000],A[5000];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d %d",c+i,r+i);
    }
    for(int i=0;i<k;i++){
        int from,to;
        scanf("%d %d",&from,&to);
        A[from-1].push_back(to-1);
        A[to-1].push_back(from-1);
    }
    for(int i=0;i<n;i++){
        queue<P> q;
        q.push(P(i,r[i]));
        int flag[5000];
        fill(flag,flag+n,-1);
        while(!q.empty()){
            P s=q.front();
            q.pop();
            if(flag[s.first]>=s.second) continue;
            G[i].push_back(s.first);
            flag[s.first]=s.second;
            if(s.second==0) continue;
            for(int j=0;j<A[s.first].size();j++){
                q.push(P(A[s.first][j],s.second-1));
            }
        }
    }
    priority_queue<P,vector<P>,greater<P> > q;
    fill(d,d+n,INF);
    d[0]=0;
    q.push(P(0,0));
    while(!q.empty()){
        P p=q.top(); q.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++){
            if(d[G[v][i]]>d[v]+c[v]){
                d[G[v][i]]=d[v]+c[v];
                q.push(P(d[G[v][i]],G[v][i]));
            }
        }
    }
    printf("%d\n",d[n-1]);
    return 0;
}

Measured memory_bytes: 69000
N, M = map(int, input().split())
lights = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(1<<N):
    onoff = bin(i)[2:].zfill(N)
    for j, switches in enumerate(lights):
        if sum(onoff[s-1] == '1' for s in switches[1:]) % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Measured memory_bytes: 74484
from collections import deque

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] * (N + 1)
for i in range(N):
    a[i + 1] = a[i] + A[i]

b = [0] * (M + 1)
for i in range(M):
    b[i + 1] = b[i] + B[i]

mx = 0
j = M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    mx = max(mx, i + j)

print(mx)


Measured memory_bytes: 47772
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,m=0; cin>>n;
  vector<int> a(n);
  vector<int> e(n);
  vector<vector<int>> x(16,vector<int>(16)); //int x[16][16];
  vector<vector<int>> y(16,vector<int>(16)); //int y[16][16];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    for (int ii = 0; ii < a[i]; ii++) {
      cin >> x[i][ii] >> y[i][ii];
    }
  }
  int t,f;
  for(int bit=0;bit<(1<<n);bit++){ //n個のものをそれぞれ選ぶor選ばないの2択
    t=0; f=0;
    for(int i=0;i<n;i++){
      if(bit & (1 << i)){ //bitのときiは選ばれているか
        e[i]=1;
      }else{
        e[i]=0;
      }
    }
    for(int i=0;i<n;i++){
      if(e[i]==1){
        for(int ii=0;ii<a[i];ii++){
          if(e[x[i][ii]-1]!=y[i][ii]){
            ii=a[i]+1; f=2;
          }
        }
        t++;
      }
    }
    if(f==2) continue;
    m=max(m,t);
  }
  cout<<m<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;

int main(){
  int n, m, x;cin>>n>>m>>x;
  int pre=0, post=0;
  for(int i=0;i<m;i++){
    int a;cin>>a;
    if(a<x)pre++;
    else post++;
  }
  cout << min(pre, post) << endl;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef unsigned long long ull;

const int N = int(5e5) + 5;
const int inf = (int)1e9 + 7;

ll k;
ll a[N];

int main(){
  scanf("%lld", &k);
  // n - 1, n - 1, n - 1, n - 1, n - 1, n - 1
  ll n = 50;
  for(int i = 1; i <= n; ++i){
    a[i] = (n - 1) + (k / n);
  }
  for(int i = 1; i <= k % n; ++i){
    int id = 1;
    for(int j = 1; j <= n; ++j){
      if(a[j] < a[id]){
        id = j;
      }
    }
    for(int j = 1; j <= n; ++j){
      if(j != id){
        a[j]--;
      } else{
        a[j] += n;
      }
    }
  }
  printf("%lld\n", n);
  for(int i = 1; i <= n; ++i){
    printf("%lld ", a[i]);
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t A , B , K ;
  cin >> A >> B >> K ;
  if(K - A <= 0){
    cout << A - K << " " << B << endl;
  }
  else if(K - A >= 0 && A + B >= K){
    cout << "0" << " " << B - (K - A) << endl;
  }
  else if(K - A >= 0 && A + B < K){
    cout << "0" << " " << "0" << endl;
  }
}
  

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

int main(void){
	long long int a,b,v,w,t;
	int flag=0;
	cin >> a >> v >> b >> w >>t;
	
	for(int i=0; i<t; i++){
		if(a<b){
			if(a+v>=b+w){
			flag=1;
			break;
			}
			a += v;
			b += w;
		}
		else if(a>b){
			if(a-v<=b-w){
				flag=1;
				break;
			}
			a -=v;
			b -=w;
		}
	}
	
		if(a==b||flag==1){
			cout <<"YES" <<endl;
		}else
			cout << "NO" <<endl;
return 0;
}


Measured memory_bytes: 3636