akhauriyash/Code-Regression huggingface dataset:
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    if 0 in A:
        print(0)
        return

    ans = 1
    for a in A:
        ans *= a
        if ans > pow(10,18):
            print("-1")
            return
    
    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 84784
#include<bits/stdc++.h>
using namespace std;
int digits(long long n){
	int ret = 0;
	while(n){
		ret++;
		n/=10;
	}
	return ret;
}
int main(){
	long long n;
	cin>>n;
	long long maxfactor = 0;
	for(long long i=1; i*i<=n; i++){
		if(n%i==0) maxfactor = max(maxfactor,i);
	}
	cout<<digits(n/maxfactor);
}

Measured memory_bytes: 3520
#include <iostream>
using namespace std;
int main()
{
	int n,i;
	cin>>n;
	int a[n],count=0,f;
	for(i=0;i<n;i++) cin>>a[i];
	do{
		f=0;
		for(i=0;i<n;i++)
		{
			if(a[i]%2==0)
			a[i]=a[i]/2;
			else
			{
			f=1;
			break;
		    }
		}
		if(f==0) count++;
	}while(f==0);
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

typedef long long ll;
ll K, A, B;
ll biscuit;

int main()
{
    cin>>K>>A>>B;

    if(A >= B)
    {
        biscuit = K + 1;
        cout<<biscuit<<endl;
    }

    else
    {
        if(B - A < 2)
        {
            biscuit = K + 1;
        }

        else
        {
            if(K == A + 1)
            {
                biscuit = B;
            }

            else if(K < A + 1)
            {
                biscuit = K + 1;
            }

            else
            {
                ll time = (K - A - 1) / 2;
                ll modify = (K - A - 1) % 2;

                biscuit = B + time * (B - A);

                biscuit += modify;
            }
        }
        cout<<biscuit<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int sum_taro,sum_hanako,n,m,taro[100],hanako[100];

  while(cin >> n >> m){
    int distance,top,ta,hana;
    if(!(n|m)) break;
    sum_taro = sum_hanako = 0;
    for(int i=0;i<n;i++)cin >> taro[i],sum_taro += taro[i];
    for(int i=0;i<m;i++)cin >> hanako[i],sum_hanako += hanako[i];
    if((sum_taro - sum_hanako) % 2 != 0){
      printf("-1\n");
      continue;
    }
    
    distance = (sum_taro - sum_hanako) / 2;
    top = 10000000;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(taro[i] ==  hanako[j] + distance){
          if(top > taro[i] + hanako[j]){
            ta = taro[i],hana = hanako[j];
            top = taro[i] + hanako[j];
          }
        }
      }
    }

    if(top == 10000000) printf("-1\n");
    else printf("%d %d\n",ta,hana);

  }

  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
const int INF = 1001001001;

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

  ll ans = 0;
  char cur = s[0];
  int l = 0;
  int r = n - 1;
  while (l < r) {
    while (s[r] == 'W' && l < r) {
      --r;
    }
    if (s[l] == 'W' && s[r] == 'R') {
      --r;
      ans++;
    }
    ++l;
  }

  cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second

int n, k;

int main() {
    cin >> n >> k;
    cout << (k > (n + 1) / 2 ? "NO" : "YES");
}

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

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

	int n;
	cin >> n;

	vector<double> dp(n + 1);
	dp[0] = 1;

	for (int i = 0; i < n; i++)
	{
		double p;
		cin >> p;

		for (int j = n; j >= 0; j--)
		{
			dp[j] *= (1 - p);
			if (j != 0)
				dp[j] += dp[j - 1] * p;
		}
	}

	double ans = 0;
	for (int i = 0; i <= n; i++)
	{
		int rest = n - i;
		if (i > rest)
			ans += dp[i];
	}
	
	cout << fixed << setprecision(20) << ans << "\n";
}

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

using ll = long long int;
using P = std::pair<int, int>;

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

constexpr int INF = 1e9;

int main()
{
    int n, m;

    std::cin >> n >> m;

    std::vector<std::vector<int>> d(m + 1, std::vector<int>(1 << n, INF));

    std::vector<int> c(m + 1);

    std::vector<int> a(m + 1);

    rep(i, m)
    {
        int b;
        std::cin >> a[i] >> b;
        int x, y = 0;
        rep(j, b)
        {
            std::cin >> x;
            y += 1 << (x - 1);
        }
        c[i] = y;
    }

    for (int i = 0; i <= m; ++i)
        d[i][0] = 0;

    auto diff = [](int a, int b) {
        int x = 1;
        for (int i = 0; i < 12; ++i)
        {
            if ((a & x) && (b & x))
                a -= 1 << i;

            x *= 2;
        }
        return a;
    };

    for (int i = 1; i < (1 << n); ++i)
    {
        rep(j, m)
        {
            d[j][i] = std::min(d[j - 1][i], a[j] + d[j - 1][diff(i, c[j])]);
            int x = 1;
            for (int k = 0; k < 12; ++k)
            {
                if (i & x)
                    d[j][i - x] = std::min(d[j][i - x], d[j][i]);
                x *= 2;
            }
        }
    }

    /*for (int i = 0; i < (1 << n); ++i)
    {
        for (int j = 0; j <= m; ++j)
            std::cerr << d[j][i] << ' ';
        std::cerr << std::endl;
    }*/

    std::cout << ((d[m][(1 << n) - 1] == INF) ? -1 : d[m][(1 << n) - 1]) << std::endl;

    return 0;
}

Measured memory_bytes: 19184
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define hi cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define pf push_front
#define ins insert
#define fh(x,v) for(auto x:v)

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
unsigned XorShift(void){static unsigned x = 123456789;static unsigned y = 362436069;static unsigned z = 521288629;static unsigned w = 88675123;unsigned t;t = x ^ (x << 11);x = y; y = z; z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

int ans;

main(){
	int r,g,b,n;
	cin>>r>>g>>b>>n;
	rep(i,n+1){
		rep(j,n+1){
			if((n-(r*i+j*g))>=0&&(n-(r*i+j*g))%b==0)ans++;
		}
	}
	dans;
}





Measured memory_bytes: 256
import numpy as np
v=np.array(list(map(int, input().split())) )
mod = 10**9 +7
import math
def cmb(n, r,mod):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = (result*int(numerator[k]))%mod

    return result
  
A = np.array([[2,1],[1,2]])
inv_A = np.linalg.inv(A)

k = np.dot(inv_A,v)

if abs(round(k[0])-k[0])<10**(-10) and abs(round(k[1])-k[1])<10**(-10) and k[0]* k[1] >=0:
  print(int(cmb(int(round(k[0]+k[1])),int(round(k[0])),mod)))
else:
  print(0)

Measured memory_bytes: 57440
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long; using ll = long long; using ld = long double;
using pi = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
template<typename T> using minQ = priority_queue<T, vector<T>, greater<T>>;

#define endl '\n'
#define ALL(a)       (a).begin(),(a).end()
#define FOR(i,a,b)   for(ll i = (ll)(a); i < (ll)(b); ++i)
#define FORO(i,a,b)  for(ll i = (ll)(a); i <= (ll)(b); ++i)
#define RFOR(i,a,b)  for(ll i = (ll)(b) - 1; i >= (ll)(a); --i)
#define RFORO(i,a,b) for(ll i = (ll)(b); i >= (ll)(a); --i)
#define REP(i,n)     for(ll i = 0; i < (ll)(n); ++i)
#define REPO(i,n)    for(ll i = 1; i <= (ll)(n); ++i)
#define RREP(i,n)    for(ll i = (ll)(n) - 1; i >= 0; --i)
#define RREPO(i,n)   for(ll i = (ll)(n); i >= 1; --i)
#define SORT(a)      sort(ALL(a))
#define UNIQ(a)      a.erase(unique(ALL(a)), a.end())
#define SUNIQ(a)     SORT(a), UNIQ(a)
#define MINI(a,b)    a=min(a,(b))
#define MAXI(a,b)    a=max(a,(b))

const ll mod = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LINF = 1000000000000000000ll;
const ld eps = 1e-8;
const ld PI = acosl(-1);

ll Nll() { ll a; cin >> a; return a; }
ld Nld() { ld a; cin >> a; return a; }
int Ni() { int a; cin >> a; return a; }
char Nc() { char a; cin >> a; return a; }
string Ns() { string a; cin >> a; return a; }

template <typename T>
void O(const T &a) { cout << a << endl; }
template <typename T>
void O(T &&a) { cout << a << endl; }
template <typename T>
void Os(const vector<T> &v) { REP(i, v.size() - 1) cout << v[i] << " \n"[i + 1 == (ll)v.size()]; }
template <typename T>
void Os(vector<T> &&v) { REP(i, v.size() - 1) cout << v[i] << " \n"[i + 1 == (ll)v.size()]; }
template <typename T>
void Is(vector<T> &v) { for (auto& t : v) cin >> t; }

void yes(bool f) { cout << (f ? "yes" : "no") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }

struct Edge {
	int from, to;
	Edge() {}
	Edge(int f, int t) : from(f), to(t) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void solve();

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

//-----------------------------------------------template-------------------------------------------------------------

//-----------------------------------------------library-------------------------------------------------------------

void solve()
{
	int N = Ni();
	ll res = 1;
	while(N--) {
		ll t = Nll();
		res = res / __gcd(res, t) * t;
	}
	O(res);
}


Measured memory_bytes: 256
N, T = map(int, input().split())
t = list(map(int, input().split())) + [10 ** 9 + T]
s = 0
for i in range(N):
    if t[i + 1] - t[i] < T:
        s += t[i + 1] - t[i]
    else:
        s += T
print(s)


Measured memory_bytes: 25200
#include<iostream>
using namespace std;
bool prime(int num){
	if(num==1) return false;
	for(int i=2;i*i<=num;i++)
		if(num%i==0)
			return false;
	return true;
}
int main(){
	int n,i=11;
	cin>>n;
	while(n){
		while(prime(i)==false)
			i+=10;
		cout<<i<<' ';
		i+=10;
		n--;
	}
	return 0;
}

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

public class Main {
	MyScanner sc = new MyScanner();
	Scanner sc2 = new Scanner(System.in);
	int mod = 1000000007;

	int N;
	int[] r;
	double[][] memo;

	void run() {
		while (sc2.hasNext()) {
			String[] input = sc2.nextLine().split(" ");
			int L = Integer.valueOf(input[0]);
			N = input.length - 1;
			r = new int[N];
			memo = new double[N][1 << N];

			for (int i = 1; i < N + 1; i++) {
				r[i - 1] = Integer.valueOf(input[i]);
			}
			boolean judge = false;
			for (int i = 0; i < N; i++) {
				double ans = tsp(i, 1 << i) + r[i];
				if (ans <= L) {
					judge = true;
				}
			}
			System.out.println(judge ? "OK" : "NA");
		}
	}

	double tsp(int v, int bit) {
		if (memo[v][bit] != 0) {
			return memo[v][bit];
		}
		if (bit == (1 << N) - 1) {
			return r[v];
		}
		double res = 1 << 10;
		for (int w = 0; w < N; w++) {
			if ((bit & (1 << w)) != 0) {
				continue;
			}
			double dis = Math.sqrt((r[v] + r[w]) * (r[v] + r[w])
					- (r[v] - r[w]) * (r[v] - r[w]));
			res = Math.min(res, dis + tsp(w, bit | 1 << w));
		}
		return memo[v][bit] = res;
	}

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

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	void debug2(int[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}
	}

	class MyScanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-')
					return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
	}
}

Measured memory_bytes: 27468
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

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

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    string S, T;
    cin >> S >> T;
    int Ans = 0;
    for (int l = 0; l < S.length(); ++l) {
        if (S[l] != T[l]) ++Ans;
    }
    cout << Ans << endl;

    return 0;
}


Measured memory_bytes: 3860
#include <stdio.h>
int main(){

    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    
    if(a<b && b<c){
        
        printf("Yes\n");
        
    }else{
        
        printf("No\n");
        
    }
    
    return 0;
}

Measured memory_bytes: 580
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s;
    int n,ans=1;
    cin>>n>>s;
    
    for(int i=0;i<n-1;i++){
        if(s[i]!=s[i+1]){
            ans++;
        }
        else if(s[i]==s[i+1]){
            
        }
    }
    
    cout<<ans<<endl;
    
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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 gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

int main(){
  int n; cin >> n;
  vector<ll> a(n);
  rep(i, n){
    cin >> a[i];
    a[i] -= i+1;
  }
  sort(all(a));

  int b = a[n/2];

  ll ans = 0;
  rep(i, n) ans += abs(a[i] - b);

  std::cout << ans << '\n';
}


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

using namespace std;
const int N=5e3+10; 

int n, m, t, vis[17]; 
int c[10]= {0,2,5,5,4,5,6,3,7,6};
int dp[N][N*2];
int f[N][N*2];

void solve(int x, int used) {
	if (x==0) return;
	solve(x-1, used-c[f[x][used]]);
	cout<<f[x][used];
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i=1; i<=m; i++) {
		scanf("%d", &t);
		vis[t]=1; 
	}
	
	dp[0][0]=1;
	queue<int> Q;
	Q.push(0);
	int ans=0;
	for(int i=1; i<=5000; i++) {
		int sz=Q.size();
		for(int j=0; j<sz; j++) {
			int cost=Q.front(); Q.pop();
			for(int k=9; k>=1; k--) {
				if (!vis[k]) continue;
				if (cost+c[k]>n) continue;
				if (dp[i][cost+c[k]]) continue; 
				dp[i][cost+c[k]]=1;
				f[i][cost+c[k]]=k;
				Q.push(cost+c[k]);
			}
		}		
		if (dp[i][n]) ans=i;
	} 
	

	
	solve(ans, n); 
	cout<<endl; 
	return 0;
}

Measured memory_bytes: 389760
def inSort(n):
    print(" ".join(list(map(str,n))))
    for i in range(1,len(n)):
        v = n[i]
        j = i-1
        while j>=0 and n[j]>v:
            n[j+1]=n[j]
            j-=1
        n[j+1]=v
        print(" ".join(list(map(str,n))))
    
A=input()
N=list(map(int,input().split()))
inSort(N)

Measured memory_bytes: 7752
#include<stdio.h>
#define INF 2001001001001001001
long long vec[100010][2];
long long P[100010];

int main(void){
    int n,q;
    int i,j,k;
    long long in1;
    int in2,x;
    long long t,pos;

    vec[0][0]=(-1)*INF;
    vec[0][1]=1;

    scanf("%d%lld%d",&n,&t,&q);
    for(i=1;i<=n;i++){
	scanf("%lld%d",&in1,&in2);
	vec[i][0]=in1;
	vec[i][1]=in2;
    }

    vec[n+1][0]=INF;
    vec[n+1][1]=2;

    for(i=0;i<=n;i++){
	if(vec[i][1]==1 && vec[i+1][1]==2){
	    pos=(vec[i][0]+vec[i+1][0])/2;
	    for(j=i;j>=0;j--){
		if(vec[j][1]==2) break;
		P[j]=pos;
	    }
	    for(j=i+1;j<=n+1;j++){
		if(vec[j][1]==1) break;
		P[j]=pos;
	    }
	}
    }

    for(i=0;i<q;i++){
	scanf("%d",&x);
	
	if(vec[x][1]==1){
	    if(vec[x][0]+t<P[x]) printf("%lld\n",vec[x][0]+t);
	    else printf("%lld\n",P[x]);
	}else{
	    if(vec[x][0]-t>P[x]) printf("%lld\n",vec[x][0]-t);
	    else printf("%lld\n",P[x]);
	}
    }

    return 0;
}

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
const int DX[8]={-1,0,1,0,-1,-1,1,1},DY[8]={0,-1,0,1,-1,1,-1,1};


int main(){;
	while(1){
		int n;
		cin>>n;
		if(n==0) break;
		vi a(26);
		bool flag=0;
		for(int i=1;i<=n;i++){
			char c;
			cin>>c;
			a[c-'A']++;
			vp b(26);
			for(int j=0;j<26;j++) b[j]={a[j],j};
			sort(b.rbegin(),b.rend());
			if(b[0].first>b[1].first+n-i){
				cout<<(char)('A'+b[0].second)<<' '<<i<<endl;
				flag=1;
				for(int j=i+1;j<=n;j++) cin>>c;
				break;
			}
		}
		if(!flag) cout<<"TIE"<<endl;
	}
}


Measured memory_bytes: 3100
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    H,W,K = LI()
    c = [SI() for _ in range(H)]
    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            cnt = 0
            for a in range(H):
                if (1 << a) & i:
                    for b in range(W):
                        if (1<<b) & j:
                            cnt += (c[a][b] == "#")

            if cnt == K: ans+= 1
    print (ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 70484
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    // 辺
    val sides = Array(m) {
        readLine()!!.split(" ").map(String::toInt).let { it[0] to it[1] }
    }

    val vertexes = (1..n).toList()
    var count = 0

    fun dfs(index: Int, routes: IntArray) {
        if (index == n) {
            count++
            return
        }
        sides.filter { it.first == routes[index - 1] || it.second == routes[index - 1] }.forEach { side ->
            vertexes.filter { !routes.contains(it) }.filter { side.first == it || side.second == it }.forEach {
                val array = routes.copyOf()
                array[index] = it
                dfs(index + 1, array)
            }
        }
    }

    dfs(1, IntArray(n).apply { this[0] = 1 })
    println(count)
}

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

struct SegTree{
    int sz;
    vector<int> dat,laz;
    SegTree(int x,int v){
        sz=1;while(sz<x)sz<<=1;
        dat.resize(sz<<1,v);
        laz.resize(sz<<1,v);
    }

    void upd(int id,int l,int r,int ql,int qr,int val){
        if(qr<l||r<ql)return;
        if(ql<=l&&r<=qr){
            laz[id]=min(laz[id],val);
            dat[id]=min(dat[id],val);
            return;
        }
        laz[id<<1]=min(laz[id<<1],laz[id]);
        dat[id<<1]=min(dat[id<<1],laz[id]);
        laz[id<<1|1]=min(laz[id<<1|1],laz[id]);
        dat[id<<1|1]=min(dat[id<<1|1],laz[id]);
        upd(id<<1,l,l+r>>1,ql,qr,val);
        upd(id<<1|1,(l+r>>1)+1,r,ql,qr,val);
        dat[id]=min(dat[id<<1],dat[id<<1|1]);
    }

    int qry(int id,int l,int r,int q){
        if(q<l||r<q)return 1e9;
        if(q==l&&r==q){
            return dat[id];
        }
        laz[id<<1]=min(laz[id<<1],laz[id]);
        dat[id<<1]=min(dat[id<<1],laz[id]);
        laz[id<<1|1]=min(laz[id<<1|1],laz[id]);
        dat[id<<1|1]=min(dat[id<<1|1],laz[id]);
        return min(qry(id<<1,l,l+r>>1,q),qry(id<<1|1,(l+r>>1)+1,r,q));
    }
};

typedef long long ll;

int n,q,sz;
ll ans;

int main(){

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

    cin>>n>>q;
    ans=(ll)(n-2)*(n-2);
    SegTree tp(n,n),lm(n,n);
    while(q--){
        char typ;
        int x;
        cin>>typ>>x;
        if(typ=='1'){
            ans-=tp.qry(1,1,tp.sz,x)-2;
            lm.upd(1,1,lm.sz,1,tp.qry(1,1,tp.sz,x),x);
        }else{
            ans-=lm.qry(1,1,lm.sz,x)-2;
            tp.upd(1,1,tp.sz,1,lm.qry(1,1,lm.sz,x),x);
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 11372
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>

#define _GLIBCXX_DEBUG
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    string s;
    cin >> s;
    if(s.at(0) == s.at(1) ||
       s.at(1) == s.at(2) ||
       s.at(2) == s.at(3) ){
        cout << "Bad" << endl;
    }else{
        cout << "Good" << endl;
    }
    
    
 }


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n, a, flag = 1;
    cin>> n;
    for (int i=0; i<n; i++) {
        cin >> a;
        if (a % 2 == 0) {
            if (a % 3 != 0 && a % 5 != 0) flag = 0;
        }
    }
    
    if(flag) cout << "APPROVED";
    else cout << "DENIED";
    return 0;
}


Measured memory_bytes: 256
# B
s = str(input())
ans = 'WA'
c_list = [c  for c in s]
if s[0] == 'A':
    if s[2:-1].count('C') == 1:
        c_list.remove('A')
        c_list.remove('C')
        if all((ord('a') <= ord(x) <= ord('z') for x in c_list)):   
            ans = 'AC'
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
const ll MOD = 1000000007;

int main() {
  string s, fest = "FESTIVAL";
  cin >> s;
  cout << s.substr(0, s.length() - fest.length()) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;


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

	if (a % 3 == 0 || b % 3 == 0 || c % 3 == 0) {
		cout << "Possible" << endl;
}
	else {
		cout << "Impossible" << endl;
	}
	}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

typedef long long ll;

void solve(std::vector<long long> A, long long N, long long numbers[],
           long long ans[])
{
    long long tot = 0;
    rep(i, 200005) { tot += ans[i]; }
    // cout << sum << endl;
    for (int i = 0; i < N; i++)
    {
        cout << tot - numbers[A[i]] * (numbers[A[i]] - 1) / 2 +
                  (numbers[A[i]] - 1) * (numbers[A[i]] - 2) / 2
             << endl;
    }
}

int main()
{
    long long N;
    long long numbers[200005] = {};
    long long ans[200005] = {};
    scanf("%lld", &N);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
        numbers[A[i]]++;
        ans[A[i]] = numbers[A[i]] * (numbers[A[i]] - 1) / 2;
    }
    solve(std::move(A), N, numbers, ans);
    return 0;
}


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

using namespace std;

int main(){

	int n, m, a, b;
	vector<int> x;

	cin>> n >> m;

	x.resize(n);
	for(int i=0;i<n;i++) x[i]=0;

	for(int i=0;i<m;i++){
		cin>> a >> b;
		x[a-1]++;
		x[b-1]++;
	}

	for(int i=0;i<n;i++) cout<< x[i] << endl;


}

Measured memory_bytes: 256
#include "algorithm"
#include "iostream"
#include "numeric"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
using namespace std;
typedef long long ll;

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

  ll m1, d1, m2, d2;
  cin >> m1 >> d1 >> m2 >> d2;

  if (m1 != m2) {
    cout << 1 << endl;
    return 0;
  } else {
    cout << 0 << endl;
    return 0;
  }

  return 0;
}


Measured memory_bytes: 256
M, D = map(int,input().split())
if D<22:
  print(0)
else:
  count = 0
  for i in range(22,D+1):
    d1 = i%10
    d10 = (i-d1)//10
    if d1>1 and d10>1 and d1*d10 <= M:
      count+=1
  print(count)

Measured memory_bytes: 3060
list_l = []
list_R = []
ID,gate = map(int,input().split())
s = 0
for i in range(gate):
  l,r = map(int,input().split())
  list_l.append(l)
  list_R.append(r)
a = max(list_l)
b = min(list_R)

for i in range(ID+1):
  if a <= i <= b:
    s += 1
  else:
    None
print(s)

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

int main(){
    int A, B, ans;
    cin >> A >> B;
    if (A > B){
        ans = A + A - 1;
    }
    else if (A < B){
        ans = B + B - 1;
    }
    else {
        ans = A + B;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,a,n) for(int i=(a);i<(int)(n);i++)
using namespace std;
typedef long long ll;
struct start { start() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(10);
}; }start;
void in() {}
template <class Head , class... Tail>
void in(Head&& head, Tail&&... tail) {
  cin >> head;
  in(move(tail)...);
}
template <class T>
  void out(T& t) {
  cout << t << '\n';
}
template <class Head , class... Tail>
void out(Head& head , Tail&... tail) {
  cout << head << ' ';
  out(move(tail)...);
}
int main(void) {
  int a,b,ans,ans1,ans2,ans3;
  in(a,b);
  ans1 = a + b;
  ans2 = a - b;
  ans3 = a * b;
  ans = max(ans1,ans2);
  ans = max(ans,ans3);
  out(ans);
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main ()
{

    int w,a,b,t;
    scanf("%d%d%d",&w,&a,&b);
    if(a>b)
    {
        t=a;
        a=b;
        b=t;
    }
    a=a+w;
    if(a>b)
        printf("0\n");
    else
        printf("%d\n",b-a);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  string s;
  cin >> s;
  cout << s.substr(0, s.size() - 8) << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		int n = sc.nextInt();

		int[] v = new int[n];
		int[] c = new int[n];

		for (int i = 0; i < n; i++) {
			v[i] = sc.nextInt();
		}

		for (int i = 0; i < n; i++) {
			c[i] = sc.nextInt();
		}

		int ans = 0;

		for (int i = 0; i < n; i++) {
			int value = v[i];
			int cost = c[i];

			if (value > cost) {
				ans += value - cost;
			}
		}
		System.out.println(ans);
		sc.close();
	}

}


Measured memory_bytes: 21844
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int[][] counts = new int[h][3];
		for (int i = 0; i < h; i++) {
		    char[] arr = sc.next().toCharArray();
		    for (char c : arr) {
		        if (c == 'W') {
		            counts[i][0]++;
		        } else if (c == 'B') {
		            counts[i][1]++;
		        } else {
		            counts[i][2]++;
		        }
		    }
		}
		int min = Integer.MAX_VALUE;
		int white = 0;
		for (int i = 0; i < h - 2; i++) {
		    white += counts[i][1] + counts[i][2];
		    int blue = 0;
		    for (int j = i + 1; j < h - 1; j++) {
		        blue += counts[j][0] + counts[j][2];
		        int red = 0;
		        for (int k = j + 1; k < h; k++) {
		            red += counts[k][0] + counts[k][1];
		        }
		        min = Math.min(min, white + red + blue);
		    }
		}
		System.out.println(min);
	}
}



Measured memory_bytes: 26492
/**
 * ?????¢

?????? P1(x1, y1), P2(x2, y2) ????????¢????±???????????????°????????????????????????

Input
x1, y1, x2, y2 ????????°???????????????????????§?????????????????????

Output
P1??¨P2????????¢????????°??§?????????????????????????????????0.0001??\????????????????????£????????????????????¨????????????

Sample Input
0 0 1 1
Sample Output
1.41421356

 */

#include <iostream>
#include <sstream>
#include <complex>
#include <iomanip>

int main(int argc, char const *argv[]) {
  double x1, y1, x2, y2;
  std::string Param;
  std::istringstream iss;
  getline(std::cin, Param);
  iss.str(Param);
  iss >> x1 >> y1 >> x2 >> y2;

  std::cout << std::fixed << std::setprecision(8) << sqrt(pow(std::abs(x1 - x2), 2) + pow(std::abs(y1 - y2), 2)) << std::endl;

  return 0;
}

Measured memory_bytes: 3236
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef long long int ll;
void swap(ll *x,ll *y){ll temp;temp=*x;*x=*y;*y=temp;}
ll compare_asc(const void *a,const void *b){return *(ll*)a-*(ll*)b;}
ll compare_desc(const void *a,const void *b){return *(ll*)b-*(ll*)a;}
ll max(ll x,ll y){return x>y?x:y;}
ll min(ll x,ll y){return x>y?y:x;}
/*void qsort(配列のアドレス,配列のサイズ,sizeof(配列の型),比較関数(昇順or降順)) */

int main(){
    int n,k,x,y;
    scanf("%d %d %d %d",&n,&k,&x,&y);
    int ans=0;

    if(n>k){
        ans+=x*k;
        ans+=y*(n-k);
    }
    else ans+=x*n;

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

Measured memory_bytes: 128
n,k,l=map(int,input().split())
load=[[] for _ in range(n)]
train=[[] for _ in range(n)]
for _ in range(k):
  a,b=map(int,input().split())
  a-=1
  b-=1
  load[a].append(b)
  load[b].append(a)
for _ in range(l):
  a,b=map(int,input().split())
  a-=1
  b-=1
  train[a].append(b)
  train[b].append(a)

# 道路の連結グループ
load_grp_id=[-1]*n
not_grp=set(range(n))
while not_grp:
  t0=not_grp.pop()
  todo=[t0]
  load_grp_id[t0]=t0
  while todo:
    t=todo.pop()
    l=load[t]
    for li in l:
      if load_grp_id[li]==-1:
        load_grp_id[li]=t0
        not_grp.discard(li)
        todo.append(li)
# 鉄道の連結グループ
train_grp_id=[-1]*n
not_grp=set(range(n))
while not_grp:
  t0=not_grp.pop()
  todo=[t0]
  train_grp_id[t0]=t0
  while todo:
    t=todo.pop()
    l=train[t]
    for li in l:
      if train_grp_id[li]==-1:
        train_grp_id[li]=t0
        not_grp.discard(li)
        todo.append(li)

d={}
for i in range(n):
  lid=load_grp_id[i]
  tid=train_grp_id[i]
  if (lid,tid) in d:
    d[(lid,tid)]+=1
  else:
    d[(lid,tid)]=1
ans=[]
for i in range(n):
  lid=load_grp_id[i]
  tid=train_grp_id[i]
  ans.append(str(d[(lid,tid)]))
print(' '.join(ans))

Measured memory_bytes: 114944
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
    int t,next;
}e[N];
int head[N],cnt;
void init(){
    memset(head,-1,sizeof(head));
    cnt=0;
}
void add(int u,int v){
    e[cnt]=node{v,head[u]};
    head[u]=cnt++;
}
int fa[N];
int father(int x){return x==fa[x]?x:fa[x]=father(fa[x]);}
int join(int x,int y){x=father(x);y=father(y);if(x!=y)fa[x]=y;}//并查集 
void initfa(int n){for(int i=1;i<=n;i++)fa[i]=i;}//父亲都是他们自己； 
 
int vis[N],ans[N];
 
void dfs1(int u,int tag,map<int,int>&M)  //块计数
{
    if(vis[u]==tag)return;
    vis[u]=tag;
    M[father(u)]++;
    for(int i=head[u];~i;i=e[i].next)
    {
        dfs1(e[i].t,tag,M);
    }
}
 
void dfs2(int u,int tag,map<int,int>&M)
{
    if(vis[u]==tag)return;
    vis[u]=tag;
    ans[u]+=M[father(u)];
    for(int i=head[u];~i;i=e[i].next)
    {
        dfs2(e[i].t,tag,M);
    }
}
 
int main()
{
    int n,k,L,u,v;
    scanf("%d%d%d",&n,&k,&L);
    init();
    initfa(n);
    while(k--){
        scanf("%d%d",&u,&v);
        join(u,v);
    }
    while(L--){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        map<int,int>M;
        dfs1(i,i,M);
        dfs2(i,-i,M);
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",ans[i],i<n?' ':'\n');
}


Measured memory_bytes: 20224
#include <iostream>
#include <stdio.h>
#include <cstring>

using namespace std;

int main()
{
	int n = 0, suma = 0, sumb = 0;
	cin >> n;
	long long counta = 0, countb = 0;
	int* a = new int [n];
	int* b = new int [n];
	for(int i = 0; i < n; i++){
		
		cin >> a[i];
		b[i] = a[i];
	}
	
	if(a[0] >= 0){
		
		counta += (a[0]+1);
		a[0] = -1;
	}
	
	suma += a[0];
	for(int i = 1; i < n; i ++){
		
		if(suma <= -1){
			
			if(suma + a[i] <= 0){
				
				counta += (1-suma-a[i]);
				suma = 1;
			}
			
			else
				suma += a[i];
		}
		
		else if(suma >= 1){
			
			if(suma + a[i] >= 0){
				
				counta += (suma+a[i]+1);
				suma = -1;
			}
			
			else
				suma += a[i];
		}	 
	}
	
	if(b[0] <= 0){
		
		countb += (1-b[0]);
		b[0] = 1;
	}
	
	sumb += b[0];
	for(int i = 1; i < n; i ++){
		
		if(sumb <= -1){
			
			if(sumb + b[i] <= 0){
				
				countb += (1-sumb-b[i]);
				sumb = 1;
			}
			
			else
				sumb += b[i];
		}
		
		else if(sumb >= 1){
			
			if(sumb + b[i] >= 0){
				
				countb += (sumb+b[i]+1);
				sumb = -1;
			}
			
			else
				sumb += b[i];
		}	 
	}
	
	if(counta < countb)
		cout << counta;
		
	else
		cout << countb;
}


Measured memory_bytes: 1024
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
dic = {}
for i in range(N):
    dic[i] = 0
for a in list(map(lambda x: int(x)-1, input().split())):
    dic[a] += 1
for i in range(N):
    if dic.get(i):
        print(dic.get(i))
    else:
        print(0)


Measured memory_bytes: 48644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    vector<ll> cnt(300000);
    for(int x=1;x<=100;x++){
        for(int y=1;y<=100;y++){
            for(int z=1;z<=100;z++){
                cnt[x*x+y*y+z*z+x*y+y*z+z*x]++;
            }
        }
    }
    
    int N;cin>>N;
    for(int i=1;i<=N;i++){
        cout<<cnt[i]<<endl;
    }
}


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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        int N; cin >> N;
        vector<int> A(N); cin >> A;
        map<int, int> mp;
        rep(i, N) mp[A[i]]++;
        if(mp.size() > 2) no();
        int a = mp.begin()->second;
        int AA = mp.begin()->first;
        if(mp.size() == 1) {
            if(AA != N - 1 and AA > N / 2) no();
        } else {
            if(mp.rbegin()->first - AA != 1) no();
            int x = a, y = N - a;
            debug(x); debug(y);
            if(AA < x or y < 2 or AA + 1 > x + y / 2) no();
        }
        cout << "Yes" << endl;
        return 0;
    }
    void no() {
        cout << "No" << endl;
        exit(0);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 5376
#include<iostream>
using namespace std;
#define N 100000
int main(){
	int n,a;
	a=N;
	cin >> n;
	while(n--){
		a+=a/20;
		if(a%1000)a=a-a%1000+1000;
	}
	cout << a <<endl;
	return 0;
}

Measured memory_bytes: 3024
import std.stdio, std.string, std.conv;
import std.array, std.algorithm, std.range;

void main()
{
    auto s = readln().chomp();
    string t;
    for(int i=0; i<s.length; )
    {
        if(startsWith(s[i..$],"apple")) t~="peach", i+=5;
        else if(startsWith(s[i..$],"peach")) t~="apple", i+=5;
        else t~=s[i], ++i;
    }
    writeln(t);
}

Measured memory_bytes: 1036
//2020年4月17日現在

#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>
#include <cstdio>

using namespace std;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }
template <class T, class... A>
void printd(const T &first, const A &... rest) { cout << fixed << setprecision(15) << first; prints_rest(rest...); }


namespace {
	// printElems(&a[0], &a[n]);　みたいな感じで使う。
	void printElems(const int* begin, const int* end)
	{
		for (const int* p = begin; p != end; ++p) {
			cout << *p << ' ';
		}
		cout << endl;
	}
}

#define rep(i,n) for(ll i=0; i<n; i++)
#define rep1(i,n) for(ll i=1; i<n+1; i++)
#define repr(i,n) for(ll i=n-1; i>=0; i--)
#define repr1(i,n) for(ll i=n; i>0; i--)
#define FOR(i,j,n) for(ll i=j; i < n; i++)
#define souatari(i,j,n) rep1(i,n-1)rep(j,i)
#define souatari1(i,j,n) for(ll i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<int,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const ll BIG = 1LL<<60;
const string yes = "Yes";
const string no = "No";

//----------------------------------------------




int main(){
	ll n;
	cin >> n;
	ll ans = 0;
	rep(i,n-1){
		ll u,v;
		cin >> u >> v;
		ll x,y;
		x = min(u,v);
		y = max(u,v);
		ans-=x*(n+1-y);
	}
	rep1(i,n){
		ans+=i*(n+1-i);
	}
	prints(ans);

	return 0;
}




Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const int MOD = 1e9+7;


#define REP(i, N) for (int i = 0; i < (N); i++)
#define REPP(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((int)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<int>>

using namespace std;

struct Node{
    int me,parent,left,right;
};

void preorder(vector<Node> nodes, int now){
    cout << " " << nodes[now].me;
    if(nodes[now].left != -1)  preorder(nodes,nodes[now].left);
    if(nodes[now].right != -1) preorder(nodes,nodes[now].right);
}
void inorder(vector<Node> nodes, int now){
    if(nodes[now].left != -1)  inorder(nodes,nodes[now].left);
    cout << " " << nodes[now].me;
    if(nodes[now].right != -1) inorder(nodes,nodes[now].right);
}
void postorder(vector<Node> nodes, int now){
    if(nodes[now].left != -1)  postorder(nodes,nodes[now].left);
    if(nodes[now].right != -1) postorder(nodes,nodes[now].right);
    cout << " " << nodes[now].me;
}


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

    int n;
    cin >> n;
    vector<Node> nodes(n);
    int id;
    for(int i = 0; i < n;i++){
        cin >> id;
        cin >> nodes[id].left;
        cin >> nodes[id].right;
        nodes[id].me = id;
        nodes[id].parent = -1;
    }

    for(int i = 0; i < n;i++){
        {
            if(nodes[i].left != -1) nodes[nodes[i].left].parent = i;
            if(nodes[i].right != -1) nodes[nodes[i].right].parent = i;
        }
    }
    int root;
    for(int i = 0; i < n;i++){
        if(nodes[i].parent == -1){
            root = i;
        }
    }
    cout << "Preorder" << endl;
    preorder(nodes,root);
    cout << endl;
    cout << "Inorder" << endl;
    inorder(nodes,root);
    cout << endl;
    cout << "Postorder" << endl;
    postorder(nodes,root);
    cout << endl;

    return 0;
}


Measured memory_bytes: 3156
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
typedef long long ll;

using namespace std;

#define MAX 401

signed main() {
	int n, m1, m2; cin >> n >> m1 >> m2;
	vector<vector<int>> v(MAX, vector<int>(MAX, INF));
	v[0][0] = 0;
	rep(_, n) {
		int a, b, c; cin >> a >> b >> c;
		for (int i = MAX - 1; i >= 0; i--)
			for (int j = MAX - 1; j >= 0;j--) {
			if (v[i][j] != INF) {
				v[i + a][j + b] = min(v[i + a][j + b], v[i][j] + c);
			}
		}
	}
	int ans = INF;
	int k = 1;
	while (k * max(m1, m2) < 401) {
		ans = min(ans, v[k * m1][k * m2]);
		k++;
	}
	if (ans == INF)cout << -1 << endl;
	else cout << ans << endl;
}

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int N;
    cin >> N;

    int A;
    cin >> A;

    rep(i,N-1) {
        int tmp;
        cin >> tmp;
        A = gcd(A, tmp);
    }

    print(A);

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
bool poss(int mid, int k, vector<int> len)
{
    for(int i:len)
    {
        k -= (ceil(i*1.0/mid*1.0)-1);
    }
    return (k>=0);
}

signed main()
{
    int n,k;
    int t;
    cin>>n>>k;
    vector<int> len;
    int maxi = INT_MIN;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        //maxi = max(maxi,t);
        len.push_back(t);
    }
    sort(len.begin(),len.end());
    int s = 1;
    int e = 1e9;
    int ans=e;
    int mid;
    //exit(0);
    while(s!=e)
    {
        mid = (s+e)/2;
        if(poss(mid,k,len))
        {
            e = mid;
            ans = min(ans,mid);
        }
        else
        {
            s = mid+1;
        }
    }

   cout<<ans;
    return 0;
}


Measured memory_bytes: 6384
/*
https://abc006.contest.atcoder.jp/tasks/abc006_4
Thratarr
18/10/19
*/
#include <stdio.h>
#include <algorithm>
using namespace std;

int n;
int dp[100000];
int x;int i;
int val;


int main(){
	scanf("%d",&val);
	scanf("%d",&n);
	dp[0] = 1;
	for(int k=0;k<n;k++){
		scanf("%d",&x);
		for(i=0;i<=val;i++){
			if(dp[i]!=0){
				if(dp[i+x]==0 || (i+x<=val && (dp[i]+1<dp[i+x]))) dp[i+x] = dp[i]+1;
			}
		}
	}
	printf("%d\n",dp[val]-1);
	return 0;
}


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

const int INF = 1001001001;
vector<int> to[100005];

int main() {
  int n, m;
  cin >> n >> m;
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    --a; --b; //頂点を0からにするためにディクリメント
    //a  ⇄  b の辺 (これは無向グラフのため両方向にいける)
    to[a].push_back(b);  //bからaに向く辺を配列に入れる
    to[b].push_back(a);  //aからbに向く辺を配列に入れる
  }

  queue<int> q;
  //頂点までの各点からの距離をINFで初期化
  vector<int> dist(n, INF);
  //最短経路における一つ前の点をメモする配列を-1で初期化
  vector<int> pre(n, -1);
  dist[0] = 0; //頂点の距離は0
  q.push(0);   //頂点をqueueにいれる
  while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int u : to[v]) {     //uにto[v]の中身をto[v]のリストの先頭から代入 
      if (dist[u] != INF) continue;
      dist[u] = dist[v]+1;   //距離の更新 
      pre[u] = v;            //前の点をメモ
      q.push(u);
    }
  }
  
  cout << "Yes" << endl;
  rep(i,n) {
    if (i == 0) continue;
    int ans = pre[i];
    ++ans;
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 10664
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main(){
    int a, b, d, r;
    double f;

    cin >> a >> b;
    
    d = a / b;
    r = a % b;
    f = (double)a / (double)b;

    printf("%d %d %f\n", d, r, f);
    return 0;
}


Measured memory_bytes: 3208