akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#define INF 20000
#define WHITE 0
#define BLACK 1
void prim();
int w(int,int);
int n,**G,mincost,*d,*pi,*color;
int main(){
  int a,i,j,totalcost;
  scanf("%d",&n);
  G = (int**)malloc(sizeof(int*) * n);     // dynamic alloction
  for(i=0; i<n; i++){                      // *
    G[i] = (int*)malloc(sizeof(int) * n);  // *
  }                                        // *
  d = (int*)malloc(sizeof(int) * n);       // *
  pi = (int*)malloc(sizeof(int) * n);      // *
  color = (int*)malloc(sizeof(int) * n);   // end
  for(i=0; i<n; i++){                 // input data
    for(j=0; j<n; j++){               // *
      scanf("%d",&a);                 // *
      G[i][j] = (a == -1 ? INF : a);  // *
    }                                 // *
  }                                   // end
  prim();
  for(i=0,totalcost=0; i<n; i++){  // sum of cost
    totalcost += d[i];             // *
  }                                // end
  printf("%d\n",totalcost);
  return 0;
}

void prim(){
  int i,u,v;
  for(i=0; i<n; i++){
    d[i] = INF;
    pi[i] = INF;
    color[i] = WHITE;
  }
  d[0] = 0;
  while(1){
    mincost = INF;
    for(i=0; i<n; i++){
      if(color[i] != BLACK && d[i] < mincost){
        mincost = d[i];
        u = i;
      }
    }
    if(mincost == INF){
      break;
    }
    color[u] = BLACK;
    for(v=0; v<n; v++){
      if(color[v] != BLACK && w(u,v) < d[v]){
        pi[v] = u;
        d[v] = w(u,v);
      }
    }
  }
}

int w(int i,int j){
  return G[i][j];
}

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

int main() {
	int n; cin >> n;
	vector<long long> v;

	v.push_back(2);
	v.push_back(1);
	for (int i = 2; i <= n; i++) {
		v.emplace_back(v[i - 1] + v[i - 2]);
	}

	cout << v[n] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <complex>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline bool valid(const int x, const int r) { return 0 <= x && x < r; }

void initIOStream() {
  ios::sync_with_stdio(false); // stdinなどと同期しない
  cin.tie(0); // cinの前にflushしない
  cout.setf(ios::fixed);
  cout.precision(10); // 四捨五入して指定桁数表示
}

int main() {
  initIOStream();

  int N;
  vector<ull> A, B;
  cin >> N;
  A.resize(N);
  B.resize(N);
  for(int i = 0; i < N; ++i) {
    cin >> A[i] >> B[i];
  }
  ull cnt = 0;
  for(int i = N - 1; i >= 0; --i){
    A[i] += cnt;
    if(A[i] % B[i] == 0) continue;
    if(A[i] < B[i]){
      ull tmp = B[i] - A[i];
      cnt += tmp;
      A[i] += tmp;
    }else{
      ull tmp = (A[i] / B[i] + 1) * B[i] - A[i];
      cnt += tmp;
      A[i] += tmp;
    }
  }
  cout << cnt << endl;
}


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

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

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

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

int main() {
  ll N,M;
  cin>>N>>M;
  vector<ll> v(N);
  rep(i,N) cin>>v[i];
  sort(v.begin(),v.end());
  ll l = 0,r = 10000000LL;
  while(r-l>1){
    ll mid = (l+r)/2;
    ll cnt = 0;
    rep(i,N){
      ll c = v.end()-lower_bound(v.begin(),v.end(),mid-v[i]);
      cnt += c;
    }
    if(cnt>=M) l = mid;
    else r = mid;
  }
  ll cnt = 0;
  ll ans = 0;
  vector<ll> S(N);
  rep(i,N){
    if(i==0) S[N-i-1] = v[N-i-1];
    else S[N-i-1] = S[N-i] + v[N-i-1];
  }
  rep(i,N){
    ll c = lower_bound(v.begin(),v.end(),r-v[i]) - v.begin();
    if(c==N) continue;
    ans += v[i]*(N-c)+S[c];
    cnt += N-c;
  }
  ans += l * (M-cnt);
  cout<<ans<<endl;
}

Measured memory_bytes: 4796
#include <stdio.h>
#define INF 2000
#define MAX 100
 
int a();
int n,color[MAX],M[MAX][MAX],d[MAX],p[MAX];
 
int main(){
int i,j;
 
scanf ("%d",&n);
 
for(i=0; i<n; i++) {
   for(j=0; j<n; j++) {
           scanf("%d",&M[i][j]);
           if(M[i][j]==-1) {
                   M[i][j]=INF;
           }
   }
}

printf("%d\n",a());
 
return 0;
}
 
int a(){
    int u,Min,i,v,sum=0;
 
    for(i=0; i<n; i++) {
        color[i]=0;
        d[i]=INF;
        p[i]=-1;
   }
 
    d[0]=0;
 
    while(1) {
        Min=INF;
        for(i=0; i<n; i++) {
            if(color[i]!=2 &&d[i]<Min) {
                Min=d[i];
                u=i;
            }
       }
 
        if(Min==INF) {
            break;
        }

        color[u]=2;
 
        for(v=0; v<n; v++) {
            if(color[v]!=2 && M[u][v]!=INF) {
                if(M[u][v]<d[v]) {
                    d[v]=M[u][v];
                    p[v]=u;
                    color[v]=1;
                }
            }
       }
}
 
    for(i=0; i<n; i++) {
        if(p[i]!=-1) {
                sum+=M[i][p[i]];
           }
}
 
return sum; 
}

Measured memory_bytes: 640
n=int(input())
a=[int(s) for s in input().split()]
d={}
for i in range(0,n):
    if a[i] not in d:
        d[a[i]]=1
    else:
        d[a[i]]+=1 
d1={}
s=0
for i in range(0,n):
    if a[i] not in d1:
        d1[a[i]]=(d[a[i]]*(d[a[i]]-1))//2
        s+=d1[a[i]]
for i in range(0,n):
    print(s-d[a[i]]+1)

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

int main(){
  while(true){
    int n;
    cin >> n;

    if(n==0)
      break;

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

    int dif = 1000001;
    for(int i=0; i<n-1; i++){
      for(int j=i+1; j<n; j++){
        int d=abs(a[i]-a[j]);

        if(d<dif){
          dif=d;
        }
      }
    }
    cout << dif << endl;
  }
  return 0;
}


Measured memory_bytes: 3076
import java.util.Scanner;

public class Main {
    public Main () {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long ans;
        long m, a, r, c, h;
        m = 0; a = 0; r = 0; c = 0; h = 0;

        for (int i = 0; i < n; i++) {
            char s = sc.next().charAt(0);
            switch (s) {
                case 'M':
                    m++;
                    break;
                case 'A':
                    a++;
                    break;
                case 'R':
                    r++;
                    break;
                case 'C':
                    c++;
                    break;
                case 'H':
                    h++;
            }
        }

        ans = m*a*r + m*a*c + m*a*h + m*r*c + m*r*h
                + m*c*h + a*r*c + a*r*h + a*c*h + r*c*h;

        System.out.println(ans);
    }

    public static void main (String[] args) {
        new Main();
    }

}


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

#define endl '\n'
#define int long long

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n; cin >> n;
	n %= 10;
	if(n == 2 or n == 4 or n == 5 or n == 7 or n == 9) cout << "hon" << endl;
	if(n == 0 or n == 1 or n == 6 or n == 8) cout << "pon" << endl;
	if(n == 3) cout << "bon" << endl;

	return 0;
}

Measured memory_bytes: 3528
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> ipair;
typedef pair<ll, ll> lpair;
typedef tuple<int, int, int> ituple;

// const int INF = INT_MAX;
// const ll INF = LLONG_MAX;
// const int MOD = ((int)1e9 + 7);
// const ld EPS = (1e-10);
#define PI acosl(-1)
#define MAX_N (200000 + 2)

class UnionFind {
protected:
  const static int MAX = 200000 + 5;
  int par[MAX];
  int rank[MAX];
  int size;

public:
  UnionFind(){}
  UnionFind(int n) {
    size = n;
    for (int i = 0; i < n; i++){
      par[i] = i;
      rank[i] = 0;
    }
  }
  int find(int x){
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]) par[x] = y;
    else{
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
};

void exec(){
  int n, m, a, b;
  cin >> n >> m;
  UnionFind uf = UnionFind(n);

  for (int i = 0; i < m; i++){
    scanf("%d%d", &a, &b);

    uf.unite(a-1, b-1);
  }

  map<int, int> mmap;
  for (int i = 0; i < n; i++){
    mmap[uf.find(i)]++;
  }

  int ans = 0;

  for (const auto x: mmap){
    ans = max(ans, x.second);
  }

  cout << ans << endl;

}

void solve(){
  int t = 1;
  // scanf("%d", &t);
  for (int i = 0; i < t; i++){
    exec();
  }
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 14352
#include <iostream>
#include <string>

using namespace std;

string table(int a, int b) {
    string str;
    for(int i = 'a'; i <= 'z'; ++i)
        str += ((i-'a')*a+b) % 26 + 'a';
    string rev;
    rev.resize(26);
    for(int i = 0; i < str.size(); ++i)
        rev[str[i]-'a'] = i+'a';
    return rev;
}

int main() {
    int N;
    cin >> N;
    cin.ignore();
    while(N--) {
        string str;
        getline(cin, str);
        for(int a = 0; a < 26; ++a) {
            if(a % 2 == 0 || a % 13 == 0) continue;
            for(int b = 0; b < 26; ++b) {
                string tbl = table(a, b);
                string tmp = str;
                for(int i = 0; i < tmp.size(); ++i) 
                    if(tmp[i] != ' ') tmp[i] = tbl[tmp[i]-'a'];
                if(tmp.find("that") != string::npos || tmp.find("this") != string::npos) {
                    cout << tmp << endl;
                    goto next;
                }
            }
        }
next:
        ;
    }
    return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>

using namespace std;
int const nmax = 100;
int v[5 + 2 * nmax];

int main() {
  int n;
  cin>>n;
  for(int i = 1 ; i <= n * 2 ;i++){
    cin>>v[i];
  }
  sort(v + 1 , v + n * 2 + 1);
  int result = 0;
  for(int i = 1 ; i < n * 2 ;i += 2){
    result += v[i];
  }
  cout<<result;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include  <queue>
#include <vector>
#include  <cstdio>
#include <cstring>
#include<map>
#include<set>
//#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T mul(T p, T e, T M)
{
    ll ret = 0;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret + p) ;
        p = (p + p) ;
        if(ret>=M)ret-=M;
        if(p>=M)p-=M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 

#define  mx 200004
#define base 193ll
 
typedef pair<int,int >P;
//////////////////////////
////////////////////////
#define F(i,a,b) for(int i=a;i<b; i++)
#define LL long long
#define MX  200007
#define md 998244353ll
///////////////////////////
///////////////////////////
///

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

    int res = a * 10 + b + c;
    res = max(res , b * 10 + a + c);
    res = max(res, c * 10 + a + b);
    
    cout<<res<<endl;
    
    return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <cstdio>

using namespace std;

int F[200010], P[200010];
bool vis[200010];
int M, N;

int FindFather(int x) {
    return F[x] == x ? x : F[x] = FindFather(F[x]);
}

int Merge(int a, int b) {
    int Fa = FindFather(a),
        Fb = FindFather(b);

    if (Fa != Fb) F[Fb] = F[Fa];

    return 0;
}

int main()
{
    scanf("%d%d", &N, &M);

    for (int i = 1; i <= N; i++) {
        F[i] = i;
        vis[i] = false;
        scanf("%d", &P[i]);
    }

    for (int i = 0, u, v; i < M; i++) {
        scanf("%d%d", &u, &v);
        Merge(u, v);
    }

    int ans = 0;
    for (int i = 1; i <= N; i++) if (FindFather(i) == FindFather(P[i])) ans++;

    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 1152
def main():
    n,m = map(int,input().split())

    A = []
    B = []
    array = []
    for i in range(n):
        array.append(tuple(map(int, input().split())))
    array_sorted = sorted(array, key=lambda item : (item[0]))

    ans = 0
    num = 0
    for pair in array_sorted:
        capacity = m-num
        if capacity >= pair[1]:
            ans += pair[0]*pair[1]
            num += pair[1]
        else:
            ans += pair[0]*capacity
            break
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 63448
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define ull unsigned ll
#define pb push_back
#define popb pop_back
#define mt make_tuple
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair <int,int>
#define piii pair <pii,int>
#define piiii pair <pii,pii>
#define pll pair <ll,ll>
#define plll pair <pair <ll, ll>, ll>
#define rep0(i,n) for(ll i=0;i<(ll)n;i++)
#define rep1(i,n) for(ll i=1;i<=(ll)n;i++)
#define rep(i,x,y) for(ll i=(ll)x;i<=(ll)y;i++)
#define reprev(i,n) for(ll i=(ll)n;i>=0;i--)
#define all(c) c.begin(),c.end()
#define print(a) rep0(i,a.size()) cout << a[i] << " "
#define hi() cout << "\nHello, I am error. Can you find me? :):):)\n"
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_eppoch().count())
 
using namespace __gnu_pbds;
using namespace std;
using ordered_set =  tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>;

// FOR DEBUGGING
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", ";
	else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifndef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

const int mod = 1e9+7;
const long double pi = acos(-1);
const ll INF = 1e15;

ll power(ll x, ll y){
	x %= mod;
	ll ans = 1;
	while(y){
		if(y&1) ans = (ans*x)%mod;
		y /= 2;
		x = (x*x)%mod;
	}
	return ans;
}

void solve(){

	int n;
	cin >> n;
	vector <int> a(n);
	rep0(i,n) cin >> a[i];

	int mn = 1e8;
	rep1(i,100){
		int tmp = 0;
		rep0(j,n) tmp += (i-a[j])*(i-a[j]);
		mn = min(mn, tmp);
	}
	cout << mn;

	return;
}

int main(){

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

	int TC = 1,t = 0;
	// cin >> TC;
	while(t++ < TC){
		// cout << "Case #" << t << ": ";
		solve();
		// cout << "\n";
	}

	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";

	return 0; 
}

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

public class Main {
	//?????°
	/**
	 * ??????????????°
	 */
	private static int valueOfCard = 9;
	/**
	 * ?????????????????????????¨??????°(1???9 = 9)
	 */
	private static int numberOfCard = 9;
	/**
	 * ??????????????????????¨??????°(R,G,B = 3)
	 */
	private static int colorOfCard = 3;
	/**
	 * 1?????????????????°
	 */
	private static int valueOfSet = 3;
	/**
	 * ???????????¶(???????????°)
	 */
	private static int winSetCount = 3;
	/**
	 * 1??????????????????????????¨???????????????????????????
	 * @author SS
	 *
	 */
	static class Card {
		private int number;
		private String color;

		public int getNumber() {
			return number;
		}
		public void setNumber(int number) {
			this.number = number;
		}
		public String getColor() {
			return color;
		}
		public void setColor(String color) {
			this.color = color;
		}
	}
	/**
	 * ??????????????????
	 * ???????????????????????°?????\??????????????¨???????????????1????????¨?????????
	 * ???????????¶??????????????????????????°'1'???????????§???????????°'0'?????????
	 * @param args
	 */
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		//??\????????°?????????
		int intLoop = scan.nextInt();
		//????¨?????´???´????¢????
		ArrayList<Integer> ansList = new ArrayList<Integer>();
		ArrayList<Card> cards = new ArrayList<Card>();

		//??\?????????
		for(int i = 0; i < intLoop; i++){

			for(int j = 0; j < valueOfCard; j++){
				Card card = new Card();
				card.setNumber(scan.nextInt());
				cards.add(card);
			}
			for(int j = 0; j < valueOfCard; j++){
				Card card = cards.get(j + i * valueOfCard);
				card.setColor(scan.next());
				cards.set(j + i * valueOfCard, card);
			}
		}
		scan.close();
		for(int i = 0; i < intLoop; i++){
			int setCount = 0; //?????????????????°
			int[][] arrayRGB = new int[colorOfCard][numberOfCard];
			//RGB???????????\?????????
			for(int j = 0; j < valueOfCard; j++){
				Card card = cards.get(j + i * valueOfCard);
				String color = card.getColor();
				if("R".equals(color)){
					arrayRGB[0][card.getNumber() - 1]++;
				}else if("G".equals(color)){
					arrayRGB[1][card.getNumber() - 1]++;
				}else if("B".equals(color)){
					arrayRGB[2][card.getNumber() - 1]++;
				}
			}
			//???????????§??????
			for(int j = 0; j < colorOfCard; j++){
				for(int k = 0; k < valueOfCard - 2; k++){
					boolean isReplay = false;
					if(arrayRGB[j][k] != 0 && arrayRGB[j][k+1] != 0 && arrayRGB[j][k+2] !=0){
						arrayRGB[j][k]--;
						arrayRGB[j][k+1]--;
						arrayRGB[j][k+2]--;
						setCount++;
						isReplay = true;
					}
					if(isReplay && arrayRGB[j][k] != 0){
						k--;
					}
				}
			}
			//???????????§??????
			for(int j = 0; j < colorOfCard; j++){
				for(int k = 0; k < valueOfCard; k++){
					if(arrayRGB[j][k] == valueOfSet){
						setCount++;
						arrayRGB[j][k] -= valueOfSet;
					}
				}
			}
			if(setCount == winSetCount){
				ansList.add(1);
			}else{
				ansList.add(0);
			}
		}
		//??????
		for(int i = 0; i < ansList.size(); i++){
			System.out.println(ansList.get(i));
		}
	}
}

Measured memory_bytes: 20832
#define _USE_MATH_DEFINES
#include <set>
#include <array>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <vector>
#include <tuple>
#include <string>
#include <math.h>
#include <time.h>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <climits>
#include <numeric>
#include <functional>
#include <iomanip>
#include <cmath>

#define lnd '\n'
// #define reverse(i, n) for(ll i = n-1; i >= 0; --i)
#define from(i, n) for (ll i = 0; i < n; ++i)
#define loop(i, n) for(ll i = 0; i < n; i++)
#define REPN(i, n) for (ll i = 1; i <= n; ++i)
#define ALL(s) (s).begin(), (s).end()
#define rALL(s) (s).rbegin(), (s).rend()
#define sz(s) (int)(s).size()
#define mk make_pair
#define pb push_back
#define sqr(s) ((s) * (s))

using namespace std;

typedef long long ll;
typedef long long int lli;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;

template <class T>
T GCD (T a, T b) {
  if(a == 0) return b;
  return GCD(b%a, a);
}

template <class T>
T LCM(T a, T b){
  return a*b/GCM(a,b);
}

template <class T>
T modpow(T x, T p){
    T res = 1;
    while(p > 0){
        if(p&1) res *= x;
        x *= x;
        p /= 2;
    }
    return res;
}

template <class T>
T modpow(T x, T p, ll mod){
    T res = 1;
    while(p > 0){
        if(p&1) res = (res*x)%mod;
        x = (x*x)%mod;
        p /= 2;
    }
    return res%mod;
}

template <class T>
void print(T a[], ll n){
    for (ll i = 0; i < n; i++) std::cout << a[i] << ' ';
    cout << endl;
}

template<class T>
void printc(T c){
    for(auto const& v: c) std::cout << v << ' ';
    cout << endl;
}

struct HASH{
  size_t operator()(const pair<long,long>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

bool pair_sort(const pair<int, int> &p1, const pair<int,int> &p2){
    if(p1.first != p2.first) return p1.first < p2.first;
    else return p1.second < p2.second;
}

const int INF = std::numeric_limits<int>::max();
const ll M_INF = std::numeric_limits<ll>::min();
const ll LL_INF = std::numeric_limits<ll>::max();

void solution();
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solution();
    return 0;
}

void solution(){
  ll n;
  cin >> n;
  ll ans = 0;
  for(ll i = 2; i <= 1000010; i++){
    if(n%i) continue;
    ll count = 0;
    while(n%i == 0){
      n = n/i;
      count++;
    }

    ll index = 1;
    while(count >= index){
      ans++;
      count -= index;
      index++;
    }
  }
  if(n>1) ans++;

  cout << ans << endl;
}    
  




Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define range(i, l, r) for(long long int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (long long int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    if (v.size() == 0) return os << "]";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    string X; cin >> X;
    lint num_T_to_remain = 0;
    lint cur_level = 0;
    for (const char& c : X) {
        if (c == 'S') cur_level += 1;
        else if (cur_level == 0) num_T_to_remain += 1;
        else cur_level -= 1;
    }
    cout << 2 * num_T_to_remain << "\n";
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
int n,l;
int main(){
	scanf("%d %d",&n,&l);
	l--;
	int x=l+1,y=l+n,ans=l*n+(n+1)*n/2;
	if(x<=0&&y>=0){
		printf("%d",ans);
	}
	else {
		if(x>=0){
			printf("%d",ans-x);
		}
		else printf("%d",ans-y);
	}
}

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

class Main{
        public static void main(String[] args){
                Scanner scanner=new Scanner(System.in);
                int N=scanner.nextInt();
                boolean[] a=new boolean[N];
                for(int i=0;i<N;i++){
                        if(i+1==scanner.nextInt()){
                                a[i]=true;
                        }else{
                                a[i]=false;
                        }
                }
                int ans=0;
                int i=0;
                for(;i<N-1;i++){
                        if(a[i]){
                                ans++;
                                if(a[i+1]){
                                        i++;
                                }
                        }
                }
                if(i==N-1 && a[i]){
                        ans++;
                }
                System.out.println(ans);
        }
}

Measured memory_bytes: 51148
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: usize,
        b: usize,
        c: usize,
        d: usize,
    }
    let mut v = vec![0; max(b, d) + 1];
    v[a] += 1;
    v[b] -= 1;
    v[c] += 1;
    v[d] -= 1;

    for i in 1..v.len() {
        v[i] += v[i - 1]
    }

    println!("{}", v.iter().filter(|x| *x == &2).count());
}


Measured memory_bytes: 4352
from collections import Counter
from heapq import heapify, heappop, heappush
from itertools import groupby

n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

cnt_b = Counter(bbb)
hq_both = []
free_a = []
idx_a = {}
cnt_a = {}
i = 0
for a, itr in groupby(aaa):
    cnt = len(list(itr))
    idx_a[a] = i
    cnt_a[a] = cnt
    if a in cnt_b:
        cnt_ab = cnt + cnt_b[a]
        if cnt_ab > n:
            print('No')
            exit()
        hq_both.append((-cnt_ab, a))
    else:
        free_a.append(a)
    i += cnt
heapify(hq_both)

ans = [-1] * n
remaining = n

while hq_both:
    cnt_ab, b = heappop(hq_both)
    cnt_ab = -cnt_ab
    assert cnt_ab == cnt_a[b] + cnt_b[b]
    assert cnt_ab <= remaining

    cb = cnt_b[b]
    while cb:
        if hq_both:
            _, a = heappop(hq_both)
        else:
            a = free_a.pop()
        ca = cnt_a[a]

        fill_len = min(ca, cb)
        i = idx_a[a]
        ans[i:i + fill_len] = [b] * fill_len
        remaining -= fill_len
        idx_a[a] += fill_len
        cnt_a[a] -= fill_len
        cnt_b[b] -= fill_len
        cb -= fill_len

        if cnt_a[a] > 0:
            if a in cnt_b and cnt_b[a] > 0:
                heappush(hq_both, (-(cnt_a[a] + cnt_b[a]), a))
            else:
                free_a.append(a)

    free_a.append(b)

for b, cb in cnt_b.items():
    if cb == 0:
        continue
    while cb:
        a = free_a.pop()
        ca = cnt_a[a]

        fill_len = min(ca, cb)
        i = idx_a[a]
        ans[i:i + fill_len] = [b] * fill_len
        idx_a[a] += fill_len
        cnt_a[a] -= fill_len
        cb -= fill_len

        if cnt_a[a] > 0:
            free_a.append(a)

print('Yes')
print(*ans)


Measured memory_bytes: 90092
from math import factorial as fac
x,y=map(int,input().split())
a=(2*y-x)/3
b=(2*x-y)/3
mod=10**9+7
if a>=0 and b>=0 and a==int(a) and b==int(b):
  a=int(a)
  b=int(b)
  a1=1
  a2=1  
  n3=10**9+7
  for i in range(a):
    a1*=a+b-i
    a2*=i+1
    a1%=n3
    a2%=n3
  a2=pow(a2,n3-2,n3)
  print((a1*a2)%n3)
else:
  print(0)

Measured memory_bytes: 9128
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long 
#define mp make_pair
#define pb push_back
#define gcd(a, b)   __gcd(a, b)
#define lcm(a, b)  ((a)*((b)/gcd(a,b)))
#define pi 3.14159265358979323846
#define reus ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int32_t main()
{
	reus;

//	#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//	#endif
    
    int a,b,c,x,R=0,G=0,B=0;
    cin>>a>>b>>c>>x;
    bool f=false;
    for(int i=0;i<=x;i++)
    {
    	for(int j=0;j<=x;j++)
    	{
    		for(int k=0;k<=x;k++)
    		{
    			B=c*(1<<k);
    			G=b*(1<<j);
    			R=a*(1<<i);
    			if(B>G&&G>R &&(i+j+k<=x))
    			f=true;
			}
		}
	}
    if(f==true)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3652
[N,K] = list(map(int,input().split()))

A=[]
d=[0]*K
for i in range(K):
    d[i] = int(input())
    A.append(list(map(int,input().split())))


sunuke=[0]*N
for j in range(K):

    for x in range(d[j]):
        sunuke[A[j][x]-1] +=1

print(sunuke.count(0))

Measured memory_bytes: 67892
#include<iostream>
#include<stdio.h>

using namespace std;

int main(){
	char op;
	int a, b;
	for (;;){
		cin >> a >> op >> b;
		if (op == '+'){
			cout << a + b << endl;
		}
		else if (op == '-'){
			cout << a - b << endl;
		}
		else if (op == '*'){
			cout << a*b << endl;
		}
		else if (op == '/'){
			cout << a / b << endl;
		}
		else if (op == '?'){
			break;
		}
	}
	return 0;
	}


Measured memory_bytes: 3108
/* 
 * Author: aps
 * Time: 19-06-2019 19:25:32
**/
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ll mod = 1e9+7;

inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x;}
inline ll sub(ll x, ll y) { x -= y; if (x < 0) x += mod; return x;}
inline ll mul(ll x, ll y) { return ((x % mod) * (y % mod)) % mod;}
inline ll power(ll a, ll b) {
    ll x = 1;
    while (b) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline ll inv(ll a) { return power(a, mod - 2);}

const int N = 1e6+6;

ll dp[N][2];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    string l; cin >> l;
    int n = l.length();

    dp[0][0] = 0;
    dp[0][1] = 1;

    for(int i=1;i<=n;i++){
        if(l[i-1] == '0'){
            dp[i][0] = mul(3LL,dp[i-1][0]);
            dp[i][1] = dp[i-1][1];
        } else {
            dp[i][0] = add(mul(3LL,dp[i-1][0]), mul(1LL,dp[i-1][1]));
            dp[i][1] = mul(2LL,dp[i-1][1]);
        }
    }

    cout << add(dp[n][0], dp[n][1]) << endl;

    return 0;
}


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

const int N = 1e5 + 77;
int in[N];
signed main()
{
#ifdef home
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#else
    // freopen("poly.in", "r", stdin);
    // freopen("poly.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> in[i];
    int ans = 0;
    for (int i = 0, lst = 0; i < n; i++)
    {
        ans += min(lst, in[i]);
        in[i] -= min(lst, in[i]);
        ans += in[i] / 2;
        lst = in[i] & 1;
    }
    cout << ans;
}

Measured memory_bytes: 1024
/* ****GT_18**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        ll i,j,k,l,m,n,a[100];
        cin>>n;
        for(i=0;i<n;i++)
            cin>>a[i];
        ll ans=0;
        for(i=1;i<n-1;i++)
        {
            if((a[i]>a[i-1]&&a[i]<a[i+1])||(a[i]<a[i-1]&&a[i]>a[i+1]))
                ans++;
        }
        cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define NMAX 100000
#define INF 1e+6
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
const ll MAX_P=10000000;
const ll MOD=998244353;
ll fact[MAX_P];

void make_fact(){
  fact[0]=fact[1]=1;
  for(ll i=2;i<MAX_P;i++){
    fact[i]=(fact[i-1]*i)%MOD;
  }
}
ll Extgcd(ll a,ll b,ll &x,ll &y){
  ll d=a;
  if(b!=0){
    Extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }
  else{
    x=1;y=0;
  }
  return d;
}

ll mod_inv(ll a,ll p){//mod pでのaの逆元を求める
  ll x,y;
  Extgcd(a,p,x,y);
  return (x%p+p)%p;
}
//n!=a*p^e (a,p互いに素,p素数) とした時のeとa mod p を求める
ll mod_fact(ll n,ll p,ll& e){
  e=0;
  if(n==0) return 1;
  
  ll res=mod_fact(n/p,p,e);
  e+=n/p;

  if(n/p%2!=0) return res*(p-fact[n%p])%p;
  return res*fact[n%p]%p;
}

//nCk mod pを求める
ll mod_comb(ll n,ll k,ll p){
  if(n<0||k<0||n-k<0) return 0;
  ll e1,e2,e3;
  ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
  if(e1>e2+e3) return 0;
  return a1*mod_inv(a2*a3%p,p)%p;
}
ll n,a,b,k;

int main(){
  make_fact();
  scan(n);scan(a);scan(b);scan(k);
  ll res=0;
  rep(x,n+1){
    if((k-a*x)%b==0){
      ll y=(k-a*x)/b;
      res=(res+mod_comb(n,x,MOD)*mod_comb(n,y,MOD)%MOD)%MOD;
    }
  }
  prin(res);  
  return 0;
}


Measured memory_bytes: 78336
#include<cstdio>
using namespace std;
#define N 4050
int n,m,st[N],fg,head[N],cnt,vl[N],ct,s,t,as,v[N][2],ct2,is[N],nt[N],v2[N][2];
struct edge{int t,next,id;}ed[N*2];
struct sth{int f,t,v;};bool operator <(sth a,sth b){return a.v<b.v;}
void adde(int f,int t,int id){ed[++cnt]=(edge){t,head[f],id};head[f]=cnt;ed[++cnt]=(edge){f,head[t],id};head[t]=cnt;}
void adde2(int f,int t,int id){ed[++cnt]=(edge){t,head[f],id*2};head[f]=cnt;ed[++cnt]=(edge){f,head[t],id*2+1};head[t]=cnt;}
void dfs(int u,int fa)
{
	if(!fg)st[++ct]=u;
	if(u==t)fg=1;
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs(ed[i].t,u);
	if(!fg)ct--;
}
void dfs2(int u,int fa)
{
	for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs2(ed[i].t,u);
	int ls=0;
	for(int i=1;i<=ct2;i++)
	if(v[i][0]==u||v[i][1]==u)
	{
		if(!ls)ls=i;
		else
		{
			int l=v[ls][0],r=v[i][1];
			if(v[ls][0]==u)l=v[ls][1],is[ls]=1;
			if(v[i][1]==u)r=v[i][0],is[i]=1;
			nt[ls]=nt[i]=++ct2;
			v[ct2][0]=l;v[ct2][1]=r;
			v[ls][0]=v[ls][1]=v[i][0]=v[i][1]=0;ls=0;
			if(v[ct2][0]==v[ct2][1])v[ct2][0]=v[ct2][1]=0;
		}
	}
	if(ls)
	{
		if(v[ls][0]==u)v[ls][0]=fa;
		else v[ls][1]=fa;
		if(v[ls][0]==v[ls][1])v[ls][0]=v[ls][1]=0;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)scanf("%d%d",&s,&t),adde(s,t,i);
	for(int r=1;r<=m;r++)
	{
		scanf("%d%d",&s,&t);ct=fg=0;dfs(s,0);v[r][0]=s,v[r][1]=t;v2[r][0]=s;v2[r][1]=t;
		for(int i=1;i<ct;i++)for(int j=head[st[i]];j;j=ed[j].next)if(ed[j].t==st[i+1]&&vl[ed[j].id]<2)vl[ed[j].id]++,as++;
	}
	printf("%d\n",as);
	ct2=m;dfs2(1,0);
	for(int i=ct2;i>=1;i--)
	is[i]^=is[nt[i]];
	for(int i=1;i<=m;i++)if(is[i])printf("%d %d\n",v2[i][1],v2[i][0]);
	else printf("%d %d\n",v2[i][0],v2[i][1]);
}

Measured memory_bytes: 384
a,b,c = input().split()
 
a = int(a)
b = int(b)
c = int(c)
 
 
if(a + b + c) != 17:
  print("NO")
elif(a + b + c) == 17:
    if(a + b == 10) | (b + c == 10) | (c + a == 10):
      print("YES")
    else:
      print("NO")
else:
  print("NO")

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

int main() {
  int n;
  cin>>n;
  int b[105],a[105];
  rep(i,n) a[i]=1e9;
  rep(i,n-1) cin>>b[i];
  rep(i,n-1) {
    a[i]=min(b[i],a[i]);
    a[i+1]=min(b[i],a[i+1]);
  }
  int ans;
  rep(i,n) ans+=a[i];
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;

const int W = 4000100;
typedef bitset<W> bs;

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VI a(n);
  REP(i, 0, n) {
    cin >> a[i];
  }
  int tot = 0;
  REP(i, 0, n) {
    tot += a[i];
  }
  if (tot - a[n - 1] <= a[n - 1]) {
    cout << a[n - 1] << endl;
    return 0;
  }
  int margin = tot - 2 * a[n - 1];
  int lim = margin / 2;
  assert (lim < W);
  bs dp;
  dp[0] = true;
  REP(i, 0, n - 1) {
    dp |= dp << a[i];
  }
  int ma = -1, ma2 = -1;
  for(int j=lim;j>=0;--j){
    if (dp[j]) {
      ma = j;
      break;
    }
  }
  for(int j=lim;j>=0;--j){
    if (dp[margin - j]) {
      ma2 = j;
      break;
    }
  }
  assert (ma >= 0);
  assert (ma2 >= 0);
  cout << tot - a[n - 1] - max(ma, ma2) << endl;
}


Measured memory_bytes: 1920
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N = int(input())
D, X = map(int, input().split())

ans = X
for _ in range(N):
    a = int(input())
    ans += 1 + (D - 1)// a

print(ans)

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

int main() {
  unordered_map<string,int> hashmap;
  hashmap["AC"] = 0;
  hashmap["WA"] = 0;
  hashmap["TLE"] = 0;
  hashmap["RE"] = 0;
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    string s;
    cin >> s;
    hashmap[s]++;
  }
  cout << "AC x " << hashmap["AC"] << endl;
  cout << "WA x " << hashmap["WA"] << endl;
  cout << "TLE x " << hashmap["TLE"] << endl;
  cout << "RE x " << hashmap["RE"] << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
template <typename T = int>
T in() {
    T temp; cin >> temp; return temp;
}

template <typename VType = int>
list<VType> const LR(VType start, VType end) {
    list<VType> ret; for (VType i = start; i < end; i++) ret.push_back(i); return move(ret);
}

int main() {
    char S[4];
    cin >> S;
    char x[2];
    int count[2] = {0, 0};
    bool ret = false;
    for (size_t i = 0; i < 4; i++) {
        if (i == 0) {
            x[0] = S[0];
            count[0] = 1;
            continue;
        }
        
        if (x[0] != S[i]) {
            if (count[1] == 2) break;
            if (count[1] == 0) {
                x[1] = S[i];
                count[1] = 1;
            } else {
                if (x[1] == S[i]) {                    
                    count[1]++;
                }
                else {
                    break;
                }
            }
        } else {
            if (count[0] == 2) break;
            count[0]++;
        }
    }
    cout << (((count[0] == 2) && (count[1] == 2)) ? "Yes" : "No") << endl;
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


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

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

typedef unsigned long int Ulong;

Ulong gcd(Ulong a, Ulong b);
Ulong lcm(Ulong a, Ulong b);

int main(void)
{
	Ulong a,b,temp;

	while(scanf("%lu%lu",&a,&b)!=EOF){
		if(a<b){
			temp=a;
			a=b;
			b=temp;
		}
		printf("%lu %lu\n",gcd(a,b),lcm(a,b));
	}

	return 0;
}

Ulong gcd(Ulong a, Ulong b)
{
	Ulong r;

	for(r=a%b; r!=0; a=b,b=r,r=a%b);

	return b;
}

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

Measured memory_bytes: 604
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

int main() {

	int n;
	cin >> n;
	int r_count = 0;

	vector<char> c(n);
	for (int i = 0;i < n;i++) {
		cin >> c[i];
		if (c[i] == 'R') {
			r_count++;
		}
	}

	int ans = r_count;

	for (int i = 0;i < r_count;i++) {
		if (c[i] == 'R') {
			ans--;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3596
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
    static final int MAX = 2_147_483_646; // intMax 
    static final int INF = 1_000_000_000; // 10^9  
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int H = saori.saori_hayami();
		int W = saori.saori_hayami();
		int h = saori.saori_hayami();
		int w = saori.saori_hayami();
		System.out.println((H-h)*(W-w));
		
		saori.close();
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 24532
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits.h>
#include <climits>
#include <map>
#include <unordered_map>
#include <cmath>
#include <set>
#include <iterator>
#include <deque>
#include <assert.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
ull min(ull x, ull y){ if (x<y) return x; return y;}
ull max(ull x, ull y){ if (x<y) return y; return x;}
ll min(ll x, ll y){ if (x<y) return x; return y;}
ll max(ll x, ll y){ if (x<y) return y; return x;}
double min(double x, double y){ if (x<y) return x; return y;}
double max(double x, double y){ if (x<y) return y; return x;}
ull gcd(ull x, ull y){
    if (!x) return y;
    if (!y) return x;
    if (x>y) swap(x,y);
    return gcd(x, y%x);
}
ull inv(ull a, ull c){ // a,c are coprime and a<c
    if (a==1){
        return 1;
    }
    return ((c-(c/a))*inv(c%a,c))%c;
}


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

    
    int n, m;
    cin>>n>>m;

    cout << n*(n-1)/2 + m*(m-1)/2 << "\n";

    return 0;
    
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def ok(n):
	print(n)
	exit(0)

def main():
	#N = int(input())
	#S = input().rstrip()
	X,Y = map(int,input().split())
	
	res = 0
	if X==Y:
		ok(res)
	if X>Y:
		res += 1
		X = -X
	res += abs(abs(Y)-abs(X))
	if X*Y<0:
		res += 1
	
	print(res)
	
main()


Measured memory_bytes: 3060