akhauriyash/Code-Regression huggingface dataset:
from collections import Counter
from math import prod

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

factorial=[1 for i in range(N+1)]
for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i

def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1)
  
v = sorted(v,reverse=True)
  
if len(set(v[:A]))==1:
  print(v[0])
  ans=0
  for i in range(A,B+1):
    if i > 1 and v[i-1] != v[i-2]:break
    ans += comb(Counter(v)[v[0]],i)
  print(int(ans))
  exit()

print(sum(v[:A])/A)

c = Counter(v)
thr = v[A-1]

if c[thr] == 1 or v[A-1] != v[A]:
  res=[]
  for k in c.keys():
    if k >= thr:
      res.append(c[k])
    
  print(prod(res))
  exit()
  
res=[]
for k in c.keys():
  if k > thr:
    res.append(c[k])

ans=prod(res)

idx = v[:A].index(v[A-1])-1

print(int(ans*comb(c[v[A-1]],A-1-idx)))

Measured memory_bytes: 9520
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
int main(){
	ll n, m, k; cin >> n >> m >> k;
	for(ll i = 0; i <= n; ++i){
		for(ll j = 0; j <= m; ++j){
			if(i * m + j * n - 2 * i * j == k){
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
    return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>
#define max(X, Y) ((X) > (Y) ? (X) : (Y))

int main()
{
	int a, b;

	scanf("%d %d", &a, &b);

	printf("%d\n", max(a + b, max(a + a - 1, b + b - 1)));

	return 0;
}


Measured memory_bytes: 128
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	if(s[0]!=s[1]||s[0]!=s[2]) cout << "Yes";
	else cout << "No";
	return 0;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD=1e9+7;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int main(){
	int N;
	cin>>N;
	vi hoge;
	rep(i,N){
		int a;
		cin>>a;
		hoge.pb(a);
	}
	hoge.pb(0);
	int now=hoge[0];
	int cnt=0;
	int ans=0;
	rep(i,N+1){
		if(hoge[i]!=now){
			now=hoge[i];
			ans+=(cnt)/2;
			//cout<<cnt<<endl;
			cnt=0;
		}
		cnt++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
def warshall_floyd(d, next_node):
    # d: nxn adjacent matrix
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    next_node[i][j] = next_node[i][k]


INF = float("inf")

n, m = map(int, input().split())
d = [[INF] * n for _ in range(n)]
next_node = [list(range(n)) for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for j in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c

warshall_floyd(d, next_node)

used_path = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        used_path.add((i, next_node[i][j]))
        used_path.add((next_node[i][j], i))

ans = m - len(used_path) // 2

print(ans)


Measured memory_bytes: 3568
import itertools

N = int(input())
P = "".join(input().split())
Q = "".join(input().split())

nl = [i+1 for i in range(N)]

l = list(itertools.permutations(nl))
sl = []

for i in l:
    sl.append("".join(list(map(str,i))))

sl.sort()
for i in range(len(sl)):
    if (sl[i] == P):
        a = i
    if (sl[i] == Q):
        b = i

print(abs(a-b))




Measured memory_bytes: 10868
#include<stdio.h>

void DFS(int);
void DFSre(int,int);

int G[100][100],d[100],f[100],judge[100];
int visit=0;

void DFS(int n)
{
  int id;

  for(id=0;id<n;id++)
    judge[id] = 0;

  for(id=0;id<n;id++) {
    if(judge[id] == 0)
      DFSre(id,n);
  }

  for(id=0;id<n;id++)
    printf("%d %d %d\n",id+1,d[id],f[id]);
}

void DFSre(int id,int n)
{
  int a;

  judge[id] = 1;
  d[id] = ++visit;
  
  for(a=0;a<n;a++) {
    if(G[id][a] == 0)
      continue;
    if(judge[a] == 0)
      DFSre(a,n);
  }
  
  judge[id] = 2;
  f[id] = ++visit;
}

  
int main()
{
  int n,x,y,z,i,j;

  scanf("%d",&n);

  for(i=0;i<n;i++) {
    for(j=0;j<n;j++) {
      G[i][j] = 0;
    }
  }

  for(i=0;i<n;i++) {
    scanf("%d%d",&x,&y);
    x--; /* 行列用に-1 */
    for(j=0;j<y;j++) {
      scanf("%d",&z);
      z--; /* 行列用に-1 */
      G[x][z] = 1;
    }
  }

  DFS(n);

  return 0;
}
      
      



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

#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
	int a[3];
	REP(i,3) cin >> a[i];
	int num5 = 0;
	int num7 = 0;
	REP(i,3) if(a[i] == 5) num5++;
	REP(i,3) if(a[i] == 7) num7++;
	if(num5 == 2 && num7 == 1) cout << "YES" << endl;
	else cout << "NO" << endl;

}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define modulo P
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000001

int main(){
	string S;
	cin>>S;
	
	map<int,long long> mp;
	
	mp[0] ++;
	
	reverse(S.begin(),S.end());
	
	int now = 0;
	long long x=  1;
	long long ans = 0;
	for(int i=0;i<S.size();i++){
		now += x*(S[i]-'0');
		now%=2019;
		ans += mp[now];
		mp[now]++;
	//	cout<<now<<endl;
		x*=10;
		x%=2019;
	}
	
	cout<<ans<<endl;
		
	return 0;
}

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

int main(){
    int N;
    cin >> N;
    int a[N-1];
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    int dist[N],distabs[N];

    dist[0] = a[0];
    dist[N] = 0 - a[N-1];
    distabs[0] = abs(a[0]);
    distabs[N] = abs(0 - a[N-1]);
    int unko = 0;


    for (int i = 1; i < N; i++) {
        unko = a[i] - a[i-1];
        dist[i] = unko;
        distabs[i] = abs(unko);
    }

    int sum = 0;

    for (int i = 0; i <= N; i++){
        sum += distabs[i];
        //printf("distabs[%d] = %d\n",i,distabs[i]);
        //printf("sum : %d",sum);
    }

    //printf("sum : %d\n",sum);

    int cost = 0;

    for (int i = 0; i < N; i++) {
        cost = sum - (distabs[i] + distabs[i+1]) + abs(dist[i] + dist[i+1]);
        cout << cost << endl;
    }


    return 0;
}


Measured memory_bytes: 2432
#include <stdio.h>
#include <stdlib.h>

#define Mod 1000000007

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

long long permutation(long long n, long long k)
{
	long long i, x;
	for (i = n, x = 1; i >= n - k + 1; i--) x = x * i % Mod;
	return x;
}

typedef struct List {
	struct List *next;
	int v;
} list;

int main()
{
	int i, u, w, N, K;
	scanf("%d %d", &N, &K);
	list **adj = (list**)malloc(sizeof(list*) * (N + 1)), *d = (list*)malloc(sizeof(list) * (N - 1) * 2);
	for (i = 1; i <= N; i++) adj[i] = NULL;
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &u, &w);
		d[i*2].v = w;
		d[i*2+1].v = u;
		d[i*2].next = adj[u];
		d[i*2+1].next = adj[w];
		adj[u] = &(d[i*2]);
		adj[w] = &(d[i*2+1]);
	}
	
	int flag[100001] = {}, q[100001], head, tail;
	long long count, ans = 0;
	list *p;
	flag[1] = 1;
	q[0] = 1;
	for (p = adj[1], tail = 1, count = 1; p != NULL; p = p->next) {
		flag[p->v] = 1;
		q[tail++] = p->v;
		count++;
	}
	if (count <= K) ans = permutation(K, count);
	for (head = 1; head < tail; head++) {
		u = q[head];
		for (p = adj[u], count = 0; p != NULL; p = p->next) {
			if (flag[p->v] == 0) {
				flag[p->v] = 1;
				q[tail++] = p->v;
				count++;
			}
		}
		if (count <= K - 2) ans = ans * permutation(K - 2, count) % Mod;
		else ans = 0;
	}
	
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 6428
package main

import "fmt"

func main() {

	var a, b int64
	var k int
	fmt.Scan(&a, &b, &k)
	for i := 0; i < k; i++ {
		if i%2 == 0 {
			if a%2 == 1 {
				a--
			}
			a, b = a/2, b+a/2
		} else {
			if b%2 == 1 {
				b--
			}
			a, b = a+b/2, b/2
		}
	}
	fmt.Printf("%d %d\n", a, b)
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a % b == 0) {
            System.out.println(a/b);
        } else {
            System.out.println(a/b + 1);
        }
        
    }
}


Measured memory_bytes: 23764
//Strange Mathematical Expression
#include<bits/stdc++.h>
using namespace std;

stack<double> st;

double stod(string s){
  double ret=0.0;
  bool flag=false;
  if(s[0]=='-')flag=true;
  for(int p=(flag ? 1 : 0); p<s.length(); p++){
    ret=ret*10.0+(double)(s[p]-'0');
  }
  if(flag)return -ret;
  else ret;
}

int main(){
  string s;
  while(getline(cin, s)){
    stringstream ss(s);
    string t;
    while(getline(ss, t, ' ')){
      if(t=="+"){
        double c1=st.top(); st.pop();
        double c2=st.top(); st.pop();
        st.push(c2+c1);
      }
      else if(t=="-"){
        double c1=st.top(); st.pop();
        double c2=st.top(); st.pop();
        st.push(c2-c1);
      }
      else if(t=="*"){
        double c1=st.top(); st.pop();
        double c2=st.top(); st.pop();
        st.push(c2*c1);
      }
      else if(t=="/"){
        double c1=st.top(); st.pop();
        double c2=st.top(); st.pop();
        st.push(c2/c1);
      }
      else{
        st.push(stod(t));
      }
    }
    printf("%.15f\n", st.top());
    while(!st.empty())st.pop();
  }
  return 0;
}

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

int main()
{
    char ch;
  cin>>ch;

    
    if(ch=='A')cout<<'T'<<endl;
    if(ch=='T')cout<<'A'<<endl;
    if(ch=='C')cout<<'G'<<endl;
    if(ch=='G')cout<<'C'<<endl;


}

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

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

#define ALL(c)   c.begin(), c.end()
#define SORT(c)  std::sort(ALL(c))
#define RSORT(c) std::sort(ALL(c), std::greater<decltype(c)::value_type>())

using namespace std;
using ll = long long;

const int MOD  = (int)1e9 + 7;
const int INF  = (int)1e9 + 1;
const ll  LINF = (ll)1e18 + 1;

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

    int A, B, C;
    std::cin >> A >> B >> C;

    std::cout << max(C - (A - B), 0) << std::endl;

    return 0;
}


Measured memory_bytes: 256
import math

def L(x1, y1, x2, y2):
  return math.sqrt((x1 - x2)**2+(y1 - y2)**2)

def S(a, b, c):
  s=(a + b + c)/2
  return math.sqrt(s*(s - a)*(s - b)*(s - c))

while True:
  try:
    x1, y1, x2, y2, x3, y3, xp, yp = map(float, raw_input().split())
    a = L(x1, y1, x2, y2)
    b = L(x1, y1, x3, y3)
    c = L(x2, y2, x3, y3)
    p1 = L(x1, y1, xp, yp)
    p2 = L(x2, y2, xp, yp)
    p3 = L(x3, y3, xp, yp)

    if S(a, p2, p1)+S(b, p1, p3)+S(c, p3, p2)-S(a, b, c) > 0.0000001:
      print "NO"
    else:
      print "YES"
  except:
    break

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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C& _a4, C _b4) { _a4 = min(_a4, _b4); }
template<class C> void maxi(C& _a4, C _b4) { _a4 = max(_a4, _b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream& operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto& vv : V) os << vv << ","; os << "]";
  return os;
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int P = 1e9 + 7;
const int MAX = 1e6;
int dp[MAX];
int n;
int sum(int x){
  int res = 0;
  for(;x; x -= (x&-x)){
    res += dp[x];
  }
  return res;
}
void add(int x){
  for(;x <= n; x += (x & -x))
    dp[x] ++;
}

int p[MAX];
int zerd[MAX];
int md[MAX];
int sil[MAX];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n;
  sil[0] = 1;
  R(i,n){
    sil[i+1] = sil[i] * (i+1) % P;
    cin >> p[i];
  }
  int zer = 0;
  for(int i = n-1;i>=0;i--){
    zerd[i] = zer;
    if(p[i] == 0){
      zer++;
    }else{
      md[i] = sum(p[i]);
      add(p[i]);
    }
  }
  int res = 0;
  int ss = 0;
  R(i,n){
    int pom = 0;
    if(p[i] != 0){
      pom += md[i] * sil[zer] % P;
      int wolne = p[i] - sum(p[i]);
      pom += wolne * sil[zer-1] % P * zerd[i] % P;
      res += ss * (zer - wolne) % P * sil[zer-1] % P;
    }else{
      ss += sil[n-i-1];
      ss %= P;
      pom = sil[zer] * zerd[i]% P * ((P+1) / 2) % P; ;
    }
    debug(pom);
    res += (pom % P * sil[n-i-1]) % P; 
    debug(res);
  }
  debug(res);
  res += sil[zer]; // indeksowanie ??
  cout << res % P << "\n";
}


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

using namespace std;

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;
const int IV3 = (MOD + 1) / 3;

namespace {
  int inv[N], fac[N], ifac[N];
  int Add(int a, int b) { return (a += b) >= MOD? a - MOD : a; }
  int Sub(int a, int b) { return (a -= b) < 0? a + MOD : a; }
  int Mul(int a, int b) { return (long long)a * b % MOD; }
  //int Inv(int a) { return a == 1? 1 : Mul(MOD - MOD / a, Inv(MOD % a)); }
  int Ch(int a, int b) {
    assert(a >= b);
    return Mul(fac[a], Mul(ifac[b], ifac[a - b]));
  }
  void Math_Init() {
    fac[0] = inv[1] = 1;
    for (int i = 1; i < N; ++i) {
      fac[i] = Mul(fac[i - 1], i);
    }
    ifac[0] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
      inv[i] = Mul(MOD - MOD / i, inv[MOD % i]);
      ifac[i] = Mul(ifac[i - 1], inv[i]);
    }
  }
}

int n;
int f[N][3];

int main() {
  Math_Init();
  scanf("%d", &n);

  int tot = 3;
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    f[i][0] = Add(f[i - 1][1], f[i - 1][2]);
    f[i][1] = Add(f[i - 1][0], f[i - 1][2]);
    f[i][2] = Add(f[i - 1][0], f[i - 1][1]);
    tot = Mul(tot, IV3);
  }

  int ans = 0;
  for (int k = 1; k <= n; ++k) {
    int gk = Mul(IV3, Mul(inv[n], inv[k]));
    int fk = Mul(Mul(Ch(n, k), f[k][1]), tot);
    ans = Add(ans, Mul(gk, fk));
  }
  printf("%d\n", ans);
  
  return 0;
}

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

int main(){

  int n;
  string s;

  cin>>n;
  int m=0, g=0;
  for(int i=0;i<n;i++){
    cin>>s;
    if(s=="A") m++;
    else g++;
    if(m<g){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  if(m==g) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
  return 0;
}

Measured memory_bytes: 3144
//https://onlinejudge.u-aizu.ac.jp/#/problems/ALDS1_3_A
import java.util.*;
import java.awt.*;
import java.awt.geom.Point2D;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        ArrayDeque<String> stack=new ArrayDeque<>();
        while (sc.hasNext()){
            String s=sc.next();
            switch (s){
                case "+":
                    stack.push(String.valueOf(Long.parseLong(stack.pop())+Long.parseLong(stack.pop())));
                    break;
                case "-":
                    stack.push(String.valueOf(-Long.parseLong(stack.pop())+Long.parseLong(stack.pop())));
                    break;
                case "*":
                    stack.push(String.valueOf(Long.parseLong(stack.pop())*Long.parseLong(stack.pop())));
                    break;
                default:
                    stack.push(s);
                    break;
            }
        }
        out.println(stack.pop());
    }
}


Measured memory_bytes: 26156
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int H = sc.nextInt();
        int N = sc.nextInt();
        int xu = W;
        int xl = 0;
        int yu = H;
        int yl = 0;
        for(int i=0; i<N; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int a = sc.nextInt();
            if(a==1){
                xl = Math.max(xl,x);
            }else if(a==2){
                xu = Math.min(xu,x);
            }else if(a==3){
                yl = Math.max(yl,y);
            }else if(a==4){
                yu = Math.min(yu,y);
            }
        }
        int xr = xu-xl;
        int yr = yu-yl;
        if(xr<0||yr<0){
            System.out.println(0);
        }else{
            System.out.println(xr*yr);
        }
    }
}

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

int main(){

   vector<long long> adiv;
   vector<long long> bdiv;
   long long a, b;
   cin >> a >> b;
   long long i;
   long long g = __gcd(a, b);
   long long result = 1;
   for(i = 2; i*i <= g; i++)
   {
       if(g % i == 0)
       {
           while(g%i == 0) g/=i;
           ++result;
       }
   }
     if(g > 1) ++result;
    cout << result;
   return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define mod (long)(998244353)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
#define long long long
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<long> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } long C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int main(){
    long A, B, C;
    cin >> A >> B >> C;
    cout << min(A + B + 1, C) + B << endl;
}


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

int main () {
  long long n;
  cin >> n;
  map<long long, long long> check;
  for (long long i = 0; i < n; i++) {
    long long sub;
    cin >> sub;
    check[sub]++;  
  }
  long long ans = 0;
  for (auto x = check.begin(); x != check.end(); ++x) {
    if (x->first == x->second) {
      //   
    }  
    else if (x->first <= x->second) {
      ans = ans + x->second - x->first;  
    }
    else if (x->second <= x->first) {
      ans = ans + x->second;  
    }
  }
  cout << ans << endl;
    
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll, int> plli;
typedef pair<int, pii> pipii;
typedef vector<vector<int> > mati;
typedef vector<vector<double> > matd;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)

inline void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

inline void OUT(void){
  cout << "\b\n";
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  ll N;
  IN(N);
  //OUT(N*(N+1)/2);
  printf("%d\n", (N*(N+1))/2);
  return 0;
}



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

ll modpow(ll p, ll q) {
  ll ans = 1;
  rep(i, q) ans = ans * p % mod;
  return ans;
}

int main() {
  ll n;
  cin >> n;
  ll ans = modpow(10, n) - modpow(9, n) - modpow(9, n) + modpow(8, n);
  ans %= mod;
  ans = (ans + mod) % mod;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3600
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MAXN=300050;
const int MOD=1000000007;
typedef long long ll;
typedef unsigned long long ull;
int main(){
	int x,a,b;
	cin>>x>>a>>b;
	int lb=abs(b-x),la=abs(a-x);
	if(la>lb) cout<<"B";
	else cout<<"A";
	return 0;
}


Measured memory_bytes: 256
N = gets.chomp.to_i
array = Array.new(3, 0)
chk = Array.new(3, 0)
cnt = 0
while tmp = gets  do
  array[cnt] = tmp.chomp.to_i
  cnt = cnt + 1
end

i = 0
cnt = 1
while chk[i] != 1 do
  if array[i] == 2 then
    print "#{cnt}"
    exit 0
  end
  chk[i] = 1
  i = array[i] - 1
  cnt = cnt + 1
end

print "-1"
exit 0

Measured memory_bytes: 3528
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, M;
vector <int> Graph[int(1e5 + 5)];
vector <int> NewGraph[int(1e5 + 5)];
int S, T, Dist[int(1e5 + 5)];
bool visited[int(1e5 + 5)][3];

int Solve(){
  scanf("%d%d", &S, &T);
  fill(Dist, Dist + N + 1, -1);

  priority_queue <Pii, vector<Pii>, greater<Pii> > que;
  que.push({0, S});

  while (!que.empty()){
    Pii Q = que.top(); que.pop();

    if (visited[Q.se][Q.fi % 3] == true) continue;
    visited[Q.se][Q.fi % 3] = true;

    if (Q.fi % 3 == 0) Dist[Q.se] = Q.fi / 3;

    for (int i = 0; i < Graph[Q.se].size(); i++){
      int next = Graph[Q.se][i];
      if (visited[next][(Q.fi + 1) % 3]) continue;
      que.push({Q.fi + 1, next});
    }
  }

  printf("%d\n", Dist[T]);

  return 0;
}

int main(){
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++){
    int U, V; scanf("%d%d", &U, &V);
    Graph[U].push_back(V);
  }
  Solve();

  return 0;
}


Measured memory_bytes: 12240
n= int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
if sum(a) < sum(b):
	    print(-1)
	    exit()
c= 0
for i in range(n):
	    if a[i]>=b[i]:c+=1
if c == n:
	    print(0)
	    exit()
chcnt = 0
needpoint = 0
for i in range(n):
	    a[i]-=b[i]
	    if a[i]<0:
	    	    chcnt+=1
	    	    needpoint-=a[i]
a.sort(reverse = True)
if a[0]== 0:
	    print(0)
	    exit()
givepoint = 0
for i in range(n):
	    givepoint += a[i]
	    if givepoint >= needpoint:
	    	    chcnt+=1
	    	    break
	    chcnt+=1
print(chcnt)

Measured memory_bytes: 18612
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
#define rep(i,n) for(int i=0;i<n;i++) 
#define all(v) v.begin(),v.end()
#define F first
#define S second
 
void solve()
{
	ll n;
	cin>>n;
	ll arr[n];
	rep(i,n)
	{
		cin>>arr[i];
	}
	ll count=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if(arr[i]!=arr[j] && arr[j]!=arr[k] && arr[k]!=arr[i])
				{
					if(arr[i]+arr[j]>arr[k] && arr[i]+arr[k]>arr[j] && arr[j]+arr[k]>arr[i])
					{
						count++;
					}
				}
			}
		}
	}
	cout<<count<<endl;
	
}
int main()
{
//	ios_base::sync_with_stdio(false); 
  //  cin.tie(NULL);  
	int t;
	t=1;
	while(t--)
	{
		solve();
	}
}

Measured memory_bytes: 3632
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define ln '\n'
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    set<int> dic;
    rep(i,N) {
        int a; cin >> a;
        dic.emplace(a);
    }

    cout << dic.size() << ln;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>

using namespace std;



int main()
{
    string a;
    int string_length;
    cin >> string_length >> a;
    int count = 0;
    while (count < a.length() && count < string_length) {
        cout << a[count];
        count++;
    }
    if (a.length() > string_length) {
        cout << "...";
    }
    
    return 0;
}


Measured memory_bytes: 3136
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

using ll = long long;
using namespace std;

int main() {
    string s = "";
    cin >> s;
    ll ans = 0;
    int n = s.size();
    for (int i=0; i<n; i++) {
        int num = s.at(i) - '0';
        ll ten = pow(10, n-i-1);
        ll two = pow(2, i);
        ans += num * ten * two;
        ten /= 10;
        while (ten > 0) {
            ans += num * ten * two;
            ten /= 10;
            two *= 2;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	int i, j;
	int a[10];
	
	while (1){
		scanf("%d", &n);
		if (n == 0){
			break;
		}
		
		for (i = 0; i < 10; i++){
			a[i] = 0;
		}
		
		for (i = 0; i < n; i++){
			scanf("%d", &j);
			a[j]++;
		}
		
		for (i = 0; i < 10; i++){
			for (j = 0; j < a[i]; j++){
				printf("*");
			}
			
			if (a[i] == 0){
				printf("-");
			}
			puts("");
		}
	}
	
	return (0);
}

Measured memory_bytes: 588
S = input()
T = input()

f = lambda c,l:[i for i,x in enumerate(l) if c == x]

sc = []
ts = []
for s,t in zip(S,T):
	if not s in sc:
		sc.append(s)
		sind = f(s,S)
		tind = f(t,T)
		if sind != tind:
			print("No")
			exit()
print("Yes")


Measured memory_bytes: 15548
line = gets.split(' ')

monster_count = line[0].to_i
skill_count = line[1].to_i

monsters = gets.split.map(&:to_i)

if monster_count <= skill_count
  puts 0
else
  monsters.sort!.reverse!

  monsters.slice!(0..(skill_count - 1)) if skill_count != 0
  count = 0
  monsters.each {|monster| count += monster }

  puts count
end

Measured memory_bytes: 17648
package main

import "fmt"

func main() {
	// Code for B - Comparison
	var A, B float64
	fmt.Scanf("%f\n%f", &A, &B)

	if A > B {
		fmt.Println("GREATER")
	} else if A == B {
		fmt.Println("EQUAL")
	} else {
		fmt.Println("LESS")
	}
}


Measured memory_bytes: 1836
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; 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 maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////

int a[3][3];

int main() {
    rep(i, 3) rep(j, 3) cin >> a[i][j];
    int n;
    cin >> n;
    rep(i, n) {
        int x;
        cin >> x;
        rep(i, 3) rep(j, 3) {
            if (a[i][j] == x) a[i][j] = 0;
        }
    }
    bool res = false;
    res |= (!a[0][0] && !a[0][1] && !a[0][2]);
    res |= (!a[1][0] && !a[1][1] && !a[1][2]);
    res |= (!a[2][0] && !a[2][1] && !a[2][2]);
    
    res |= (!a[0][0] && !a[1][0] && !a[2][0]);
    res |= (!a[0][1] && !a[1][1] && !a[2][1]);
    res |= (!a[0][2] && !a[1][2] && !a[2][2]);

    res |= (!a[0][0] && !a[1][1] && !a[2][2]);
    res |= (!a[0][2] && !a[1][1] && !a[2][0]);
    cout << (res ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
int main(void){
    int n,m,a;
    while(std::cin>>n>>m,!(n==0&&m==0)){
        a=1;
        for(int i=2;i<=n;i++){
            a=(a+m)%i;
            if(a==0)a=i;
        }
        std::cout<<a<<std::endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <cstdio>

int T,H,W,N;
char map[20][20],cmd[100];
int x,y,d;

int main(){
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&H,&W);
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
	scanf(" %c",&map[i][j]);
	switch(map[i][j]){
	case '^': x=i,y=j,d=0,map[i][j]='.'; break;
	case 'v': x=i,y=j,d=1,map[i][j]='.'; break;
	case '>': x=i,y=j,d=2,map[i][j]='.'; break;
	case '<': x=i,y=j,d=3,map[i][j]='.'; break;
	}
      }
    }
    scanf("%d",&N);
    for(int i=0;i<N;i++){
      scanf(" %c",&cmd[i]);
    }
    for(int i=0;i<N;i++){
      switch(cmd[i]){
      case 'U':	d=0; if(x>0&&map[x-1][y]=='.') x--; break;
      case 'D': d=1; if(x<H-1&&map[x+1][y]=='.') x++; break;
      case 'R': d=2; if(y<W-1&&map[x][y+1]=='.') y++; break;
      case 'L': d=3; if(y>0&&map[x][y-1]=='.') y--; break;
      case 'S': 
	switch(d){
	case 0:{
	  int X=x,Y=y;
	  for(;;){
	    if(X>=0){
	      if (map[X][Y]=='*') { map[X][Y]='.'; break; }
	      if (map[X][Y]=='#') break;
	      X--;
	    }else{
	      break;
	    }
	  }
	  break;
	}
	case 1:{
	  int X=x,Y=y;
	  for(;;){
	    if(X<H){
	      if (map[X][Y]=='*') { map[X][Y]='.'; break; }
	      if (map[X][Y]=='#') break;
	      X++;
	    }else{
	      break;
	    }
	  }
	  break;
	}
	case 2:{
	  int X=x,Y=y;
	  for(;;){
	    if(Y<W){
	      if (map[X][Y]=='*') { map[X][Y]='.'; break; }
	      if (map[X][Y]=='#') break;
	      Y++;
	    }else{
	      break;
	    }
	  }
	  break;
	}
	case 3:{
	  int X=x,Y=y;
	  for(;;){
	    if(Y>=0){
	      if (map[X][Y]=='*') { map[X][Y]='.'; break; }
	      if (map[X][Y]=='#') break;
	      Y--;
	    }else{
	      break;
	    }
	  }
	  break;
	}
	}
      }
    }
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
	if (i==x&&j==y){
	  switch(d){
	  case 0: printf("^"); break;
	  case 1: printf("v"); break;
	  case 2: printf(">"); break;
	  case 3: printf("<"); break;
	  }
	}else{
	  printf("%c",map[i][j]);
	}
      }
      puts("");
    }
    if (T!=0) puts("");
  }
}

Measured memory_bytes: 0
import Control.Applicative
import Control.Monad
import Data.List
import Data.Char (isSpace)
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = do
  n <- readLn
  unless (n == 0) $ do
    solve <$> f <*> f >>= print
    main
  where
    f = readil B.readInt <$> B.getLine

solve :: [Int] -> [Int] -> Int
solve ps js = let js' = sort js
                  l = sum ps + sum js 
              in f l 1 l js'
  where
    f mx c l [] = mx
    f mx c l (x:xs) = f (max mx ((c + 1) * (l - x))) (c + 1) (l - x) xs

readil :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> [a]
readil f = unfoldr $ \s -> do
  (n, s') <- f s
  return (n, B.dropWhile isSpace s')



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

int main(){
    int n,ans=0;
    cin>>n;
    string s;
    cin>>s;
    rep(i,n-1){
        if(s[i]==s[i+1]) continue;
        ans+=1;
    }
    ans++;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Node
    {
        internal List<int> target;
        internal int inDegree;
        internal bool isVisit;

        public Node()
        {
            target = new List<int>();
        }
    }

    class Program
    {
        static List<int> result;

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int V = int.Parse(input[0]);
            int E = int.Parse(input[1]);

            Node[] nodeList = Enumerable.Range(0, V).Select(a => new Node()).ToArray();

            int s, t;
            for (int i = 0; i < E; i++)
            {
                input = Console.ReadLine().Split(' ');
                s = int.Parse(input[0]);
                t = int.Parse(input[1]);

                nodeList[s].target.Add(t);
                nodeList[t].inDegree++;
            }

            result = new List<int>();
            TopologicalSort(nodeList);
        }

        static void TopologicalSort(Node[] NL)
        {
            for (int i = 0; i < NL.Length; i++)
            {
                if (NL[i].inDegree == 0 && !NL[i].isVisit)
                {
                    BFS(NL, i);
                }
            }

            StringBuilder sb = new StringBuilder();
            foreach (int node in result)
            {
                sb.AppendLine(node.ToString());
            }
            Console.Write(sb);
        }

        static void BFS(Node[] NL, int s)
        {
            Queue<int> que = new Queue<int>();
            que.Enqueue(s);

            NL[s].isVisit = true;

            while (que.Count > 0)
            {
                int u = que.Dequeue();
                result.Add(u);

                for (int i = 0; i < NL[u].target.Count; i++)
                {
                    int v = NL[u].target[i];
                    NL[v].inDegree--;

                    if (NL[v].inDegree == 0 && !NL[v].isVisit)
                    {
                        NL[v].isVisit = true;
                        que.Enqueue(v);
                    }
                }
            }
        }
    }
}

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

int A[2010];
bitset<2000010> bs;

int main() {
	int N;
	cin >> N;
	int sum=0;
	for(int i=0; i<N; ++i){
		cin >> A[i];
		sum += A[i];
	}
	bs[0]=1;
	for(int i=0; i<N; ++i){
		bs |= (bs<<(A[i]));
	}
	int ans=sum/2;
	while(!bs[ans]) --ans;
	cout << sum-ans << endl;
	return 0;
}

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

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main()
{
	for(int n,k;cin>>n>>k,n|k;){
		vi a(n);
		rep(i,n)
			cin>>a[i];
		
		int sum=accumulate(a.begin(),a.begin()+k,0);
		int res=sum;
		repi(i,k,n){
			sum=sum+a[i]-a[i-k];
			res=max(res,sum);
		}
		cout<<res<<endl;
	}
	
	return 0;
}

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

using namespace std;

////typedef
////------------------------------------------
//typedef vector<int> vi;
//typedef vector<vi> vii;
//typedef vector<string> vs;
//typedef vector<bool> vb;
//typedef vector<vb> vbb;
//typedef pair<int, int> pii;
//typedef long long ll;
//typedef unsigned long long ull;
//
////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 iter(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
//
////repetition
////------------------------------------------
//#define loop(i,a,b) for(int i=(a);i<(b);++i)
//#define rep(i,n)  loop(i,0,n)
//
////constant
////--------------------------------------------
//const double eps = 1e-10;
//const double pi  = acos(-1.0);
//const double inf = (int)1e8;
//
//// output vector
//// ------------------------------------------
//namespace std {
//    template<typename T> ostream & operator<<(ostream& os, vector<T> const& v){
//        for(auto it=v.begin(); it!=v.end(); ++it){
//            os << *it << (it+1==v.end() ? "" : ",");
//        }
//        return os;
//    }
//}
//
////clear memory
//#define clr(a) memset((a), 0 ,sizeof(a))

int main(){
    int n;
    while(cin >> n, n){
        int ans = 0;
        while(n/5 != 0){
            ans += n/5;
            n /= 5;
        }
        cout << ans << endl;
    }
}

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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    ll n, sum= 0;

    cin>> n;

    ll t= n;

    while (t> 0)
    {
        sum+= (t%10);
        t/=10;
    }



    cout << (n% sum== 0 ? "Yes\n" : "No\n");

    return 0;
}




Measured memory_bytes: 3644
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())

if a<=b:
    if a+v*t>=b+w*t:
        print('YES')
    else:
        print('NO')
else:
    if a-v*t<=b-w*t:
        print('YES')
    else:
        print('NO')

Measured memory_bytes: 9180
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;
  
// 検索タグ
int main() {
	// 入力
	ll A,B,C;cin>>A>>B>>C;
    
	//出力
	printf("%lld %lld %lld\n", C, A, B);
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
 
int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int total = 0;
  for (int i = 1; i <= N; ++i) {
    int sum = findSumOfDigits(i);
    if (sum >= A && sum <= B) {
      total += i;
    }
  }
  cout << total << endl;
}
  

Measured memory_bytes: 256
N = input()
K = int(input())
m = len(N)

dp = [[[0] * (K+1) for _ in range(2)] for _ in range(m+1)]
dp[0][0][0] = 1

for i in range(1,m+1):
    l = int(N[i-1])
    for k in range(K+1):
        if k-1>=0:
            if l!=0:
                dp[i][0][k]=dp[i-1][0][k-1]
                dp[i][1][k] = dp[i-1][1][k] + 9 * dp[i-1][1][k-1]+dp[i-1][0][k] + (l-1) * dp[i-1][0][k-1]
            else:
                dp[i][0][k] = dp[i-1][0][k]
                dp[i][1][k] = dp[i-1][1][k] + 9 * dp[i-1][1][k-1]
        else:
            dp[i][0][k] = 0
            dp[i][1][k] = 1

print(dp[m][0][K] + dp[m][1][K])

Measured memory_bytes: 62476
#include <iostream>
#include <string>
 
using namespace std;
 
int main(int argc, char const* argv[])
{
	string input1;
	int calcResult;
  	cin >> input1;
	int n;

  calcResult = 0;
	for(int i = 0; i < (int)input1.size(); ++i){
	    char ch = input1[i];
      	n = 0;
		n = (int)(ch - '0');
		calcResult = calcResult + n;
	}

	cout << calcResult;    

        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll A,V,B,W,T;
    cin >> A >> V >> B >> W >> T;
    if(A<B)
    {
        if(V<=W)
        {
            cout << "NO" << endl;
          return 0;
        }
        if((A+V*T)>=(B+W*T))
        {
            cout << "YES" << endl;
            return 0;
        }
        cout << "NO" << endl;
        return 0;
    }

    if(V<=W)
    {
        cout << "NO" << endl;
        return 0;
    }
    if((A-V*T)<=(B-W*T))
    {
        cout << "YES" << endl;
        return 0;
    }
    cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 3564
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define MMP(a, b, c) make_pair(make_pair(a, b), c)
#define MAX 1000000000
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define PI 3.14159265359

int N;
int a[100000], b[100000], c[100000];
LL dp[100000][3][3];

LL solve(int now, int yesterdayActivity, int days){
	if(days >= 2) return -MAX;
	if(now == N) return 0;
	if(dp[now][yesterdayActivity][days] != -1) return dp[now][yesterdayActivity][days];
	int dayA = 1;
	int dayB = 1;
	int dayC = 1;
	switch (yesterdayActivity){
	case 0:
		dayA = days + 1;
		break;
	case 1:
		dayB = days + 1;
		break;
	case 2:
		dayC = days + 1;
		break;
	}
	return dp[now][yesterdayActivity][days] = 
			max(a[now] + solve(now+1, 0, dayA), max(b[now] + solve(now+1, 1, dayB), c[now] + solve(now+1, 2, dayC)) );
}

int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a[i] >> b[i] >> c[i];
		for(int j=0; j<3; j++){
			for(int k=0; k<3; k++){
				dp[i][j][k] = -1;
			}
		}
	}
	cout << solve(0,0,0) << endl;
	

	return 0;
}

Measured memory_bytes: 16256