akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>

using namespace std;

int dp[4][1001];
int w[4], v[4];
int N;

int main() {
	cin >> N;
	for (int i = 0; i < 4; i++)cin >> v[i];
	for (int i = 0; i < 4; i++)cin >> w[i];

	for (int i = 0; i < 4; i++)for (int j = 0; j <= 1000; j++)dp[i][j] = 1145141919;
	dp[0][0] = 0;
	for (int j = 1; j <= 1000; j++) {
		if (j - w[0] >= 0)dp[0][j] = min(dp[0][j], dp[0][j - w[0]] + v[0]);
	}

	for (int i = 1; i < 4; i++) {
		for (int j = 0; j <= 1000; j++) {
			if (j - w[i] >= 0)
				dp[i][j] = min(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	int ans = 1145141919;
	for (int i = N; i <= 1000; i++) {
		ans = min(ans, dp[3][i]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3124
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+1000;
int n,a[maxn],c,d,cnt[4];
int main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	cin>>n;
	cin>>c>>d;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]<=c)
			cnt[1]++;
		else if(a[i]>c&&a[i]<=d)
			cnt[2]++;
		else
			cnt[3]++;
	}
	cout<<min(cnt[1],min(cnt[2],cnt[3]));
	return 0;
}


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

void comb(vector<vector <long long int> > &v){
  for(int i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(int k = 1;k <v.size();k++){
    for(int j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}


void solve(long long N, long long M){
    vector<vector<long long int> > v(N+1,vector<long long int>(N+1,0));
    comb(v);
    vector<vector<long long int> > v2(M+1,vector<long long int>(M+1,0));
    comb(v2);
    cout << v[N][2] + v2[M][2] << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    solve(N, M);
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main(void)
{
    int k;
    int arr[33] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    scanf("%d",&k);
    printf("%d", arr[k-1]);
    return (0);
}

Measured memory_bytes: 128
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>

using namespace std;
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
const int MOD=1000000007;
//const int MOD=998244353;
const int INTMAX=1001001000;
const ll LLMAX=1010010010010010000;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N;
    cin>>N;
    
    ll ans=0;
    for(int i=1;i<=N;i++){
        if(i%3!=0 && i%5!=0)ans+=i;
    }
    cout<<ans<<endl;
    
    return 0;
}


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

int facctorialMethod(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}
int calrank(vector<int> a) {
  int ret = 0;
  rep(i,n){
    ret +=  facctorialMethod(n-i-1) * a[i];
    for(int j = i; j<n; j++) {
      if(a[j] > a[i]) {
        a[j]--;
      }
    }
  }
  return ret;
}

int main() {
  cin >> n;
  int a=0;
  vector<int> p(n);
  vector<int> q(n);
  rep(i,n) {
    cin >> p[i];
  }
  rep(i,n) {
    cin >> q[i];
  }

  cout << abs(calrank(q)  -calrank(p)) << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (N + 1)
d = dd(list)
for i in range(N): d[a[i]].append(i)
for i in range(N - 1, -1, -1):
  j = bl(d[a[i]], i)
  if len(d[a[i]]) - 1 > j: dp[i] = dp[d[a[i]][j + 1] + 1]
  else: dp[i] = a[i]
res = [0, dp[0]]
d[0].append(-1)
#print(dp)
if dp[0] == 0: res.pop()
while dp[d[res[-1]][0] + 1] > 0:
  res.append(dp[d[res[-1]][0] + 1])
  #print(res, i)
#print(res)
#print((K - 1) % len(res))
if K % len(res) == 0:
  print()
  exit(0)
rres = []
i = d[res[(K - 1) % len(res)]][0] + 1
while i < N:
  j = bl(d[a[i]], i)
  if len(d[a[i]]) - 1 > j: i = d[a[i]][j + 1] + 1
  else:
    rres.append(a[i])
    i += 1
print(*rres)

Measured memory_bytes: 119244
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Wed Feb  6 11:42:59 2019
//
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)

	cs := make([]int, N-1)
	ss := make([]int, N-1)
	fs := make([]int, N-1)

	for i := range cs {
		fmt.Scan(&cs[i], &ss[i], &fs[i])
	}

	for i := range cs {
		t := 0
		for j := i; j < len(cs); j++ {
			c, s, f := cs[j], ss[j], fs[j]
			if t <= s {
				t = s
			} else if t > s {
				n := (t - s + f - 1) / f
				t = s + n*f
			}
			t += c
		}
		fmt.Println(t)
	}
	fmt.Println(0)
}


Measured memory_bytes: 512
fun main(args: Array<String>) {
    val menu = IntArray(5) { readLine()!!.toInt() }
    var total = menu.map { if (it % 10 == 0) it else (it / 10 + 1) * 10 }.sum()
    val lastOrder = menu.filter { it % 10 != 0 }.minBy { it % 10 }
    if (lastOrder != null) {
        total -= 10 - lastOrder % 10
    }
    println(total)
}


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

using namespace std;
using ll = long long;

int main (void){
  ll n, a, b;
  cin >> n >> a >> b;
  cin.ignore();

  vector<ll> h;
  ll tmp;

  for (int i = 0; i < n; i++){
    cin >> tmp;
    cin.ignore();
    h.push_back(tmp);
  }

  // 最初から一体だけ
  if(n == 1){
    cout << h[0] / a + 1 << endl;
    return 0;
  }

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

  ll c = a - b;

  ll lb = 0; // 絶対に条件を満たさない
  ll ub = h.back() / b + (h.back() % b); // 絶対に条件を満たす
  ll mid; // この値について「満たすかどうか」をチェックする
  ll csum = 0; // 追加攻撃回数
  ll thp; // 各モンスター残りHP

  ll lp_dbgcnt = 0;
  while(ub - lb >= 2){
    //cout << ub << " " << lb << endl;
    csum = 0;
    mid = (lb + ub) / 2;

    // まず全モンスターにmid回bのダメージを与える
    // 次に各モンスターに合計mid回の追加攻撃
    for(auto itr = h.begin(); itr != h.end(); itr++){
      thp = (*itr - b * mid);
      csum += (thp <= 0) ? 0 : thp / c + (thp % c != 0); 
    }
    if(csum <= mid) ub = mid;
    else lb = mid;

    lp_dbgcnt++;
    /*
    if(lp_dbgcnt == 1000){
      cout << "ERR" << endl;
      exit(1);
    }
    */
  }

  cout << ub << endl;

  return 0;
}


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

int main() {
    while(true) {
        int a, b;
        cin >> a >> b;
        if(a == 0 && b == 0) return 0;
        for(int i = 0; i < a; i++) {
            for(int j = 0; j < b; j++) {
                if((i + j) % 2 == 0) cout << "#";
                else cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }
}






Measured memory_bytes: 3092
import bisect

n=int(input())
a=list(map(int,input().split()))
a.sort()
max=0
for i in range(10**5+1):
    x=bisect.bisect_left(a,i-1)
    y=bisect.bisect_right(a,i+1)
    if y-x>max:
        max=y-x
print(max)

Measured memory_bytes: 13964
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String ans = null;
    for(int i = 2; i < S.length(); i=i+2) {
    	ans = S.substring(0, S.length()-i);
    	String ans1 = ans.substring(0,(S.length()-i)/2);
    	String ans2 = ans.substring((S.length()-i)/2);
    	if(ans1.equals(ans2)) break;
    }
    System.out.println(ans.length());

  }
}

Measured memory_bytes: 35536
#include<iostream>
#include <string>
#include <cfenv>
#include <cmath>
using namespace std;
int main()
{
    // 整数の入力
    string aa;
    cin >> aa;
  	//vector<string> arr(aa.size());
    int num=0;
    int bbb=0;
    for (int i = 0; i < floor(aa.size()*1.0/2); i++) {
      if (aa[i]!=aa[aa.size()-1-i]){
        num++;
      }
    }
    //

  
    // 出力
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define All(vec) vec.begin(), vec.end()
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())
#define Next_permutation(vec) next_permutation(vec.begin(), vec.end())
#define PI acos(-1)

int main() {
    int N;
    cin >> N;
    int div4 = 0, div2 = 0;
    Rep(i, N) {
        int a;
        cin >> a;
        if (a % 4 == 0) div4++;
        else if (a % 2 == 0) div2++;
    }
    if (div4 >= N / 2) puts("Yes");
    else if (div2 >= N - div4 * 2) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	vector<int> v,b;
	int a;
	for(int i=0;i<6;i++){
		cin>>a;
		v.push_back(a);
	}
	for(int i=0;i<4;i++){
		b.push_back(0);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<6;i++){
		if(v[i]==1)
			b[0]++;
		if(v[i]==2)
			b[1]++;
		if(v[i]==3)
			b[2]++;
		if(v[i]==4)
			b[3]++;
	}
	sort(b.begin(),b.end());
	if(b[0]==1&&b[1]==1&&b[2]==2&&b[3]==2){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 384
while True:
    n,x = [ int(x) for x in input().split()]
    if n == 0 and x ==0:
        break
    count = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                if i + j + k == x:
                    count += 1
    print(count)


Measured memory_bytes: 5604
#include<stdio.h>
#define N 100
int main(){
  int i,j,k,l,m,n;
  int G[N][N]={0};
  scanf("%d",&n);
  for(m=0;m<n;m++){
    scanf("%d%d",&i,&k);
    for(l=0;l<k;l++){
      scanf("%d",&j);
      G[i-1][j-1]=1;
    }
  }
  
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j<n-1) printf("%d ",G[i][j]);
      else printf("%d\n",G[i][j]);
    }
  }
  return 0;
}

Measured memory_bytes: 648
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int r;cin >> r;
  cout << 3*r*r << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

ll a[55],b[55],c[55],d[55];
int main(){
	ll n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,0,n)scanf("%lld%lld",a+i,b+i);
	rep(i,0,m)scanf("%lld%lld",c+i,d+i);
	rep(i,0,n){
		ll idx=-1,mi=1e10;
		rep(j,0,m){
			ll dist=llabs(a[i]-c[j])+llabs(b[i]-d[j]);
			if(dist<mi){
				mi=dist;
				idx=j;
			}
		}
		printf("%lld\n",idx+1);
	}
}

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

using namespace std;
typedef long long ll;
// const ll LLONG_MAX = 9223372036854775807;

int main()
{
    ll N, K;
    cin >> N >> K;
    ll t;
    t = N % K;
    
    cout << min(t, K-t) << endl;
    // ll min=N, tmp = abs(N-K);
    // // cout << tmp << endl;
    // while(1){
    //     if(min <= tmp){
    //         break;
    //     }else{
    //         // cout << min << endl;
    //         if(tmp > min/2){
    //             min = tmp/2;
    //             tmp = abs(min - K);            
    //         }else{
    //             min = tmp;
    //             tmp = abs(min - K);
    //         }
    //     }
    // }

    return 0;
}

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

constexpr int MAX_N = 1e5+9;

int N;
vector<vector<int>> edges(MAX_N+1), costs(MAX_N+1);
int colors[MAX_N+1];

void dfs(int cur) {
  queue<int> que;
  que.push(cur);

  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i{}; i < edges[u].size(); ++i) {
      int v = edges[u][i];
      int w = costs[u][i];
      if (colors[v] >= 0)
        continue;
      colors[v] = w % 2 == 0 ? colors[u] : !colors[u];
      que.push(v);
    }
  }
}

int main() {
  fill_n(colors, MAX_N+1, -1);

  cin >> N;

  int u, v, w;
  for (int i{}; i < N - 1; ++i) {
    cin >> u >> v >> w;
    edges[u].push_back(v);
    costs[u].push_back(w);
    edges[v].push_back(u);
    costs[v].push_back(w);
  }

  colors[u] = 0;
  dfs(u);
  for (int i{1}; i <= N; ++i) {
    cout << colors[i] << endl;
  }

  return 0;
}


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

int main() {
	// your code goes here
	long long n,i,k=0;
	cin>>n;
	int a[n];
	for(i=0;i<n;i++)
	cin>>a[i];
	for(i=0;i<n;i++)
	{
	    while(a[i]%2==0)
	    {
	        a[i]=a[i]/2;
	        k++;
	        a[i]*=3;
	    }
	}
	cout<<k<<endl;
	return 0;
}


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


typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;

#define _  %  MOD
#define __ %= MOD

#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))

#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define fbo find_by_order
#define ook order_of_key
#define mark(x) cout<<"Here -- "<<x<<endl;
#define pv(v)   {rep(i,v.size()) cout<<v[i]<<" "; cout<<endl;}


ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;} // modular exponent

int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ll n,a,b; cin>>n>>a>>b;
    ll ans = (n/(a+b))*a;
    if(n%(a+b)<a){
        ans+=(n%(a+b));
    }
    else{
        ans+=a;
    }
    cout<<ans<<endl;

    return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string N;cin>>N;
  int A=N.at(0)-'0';
  int B=N.at(1)-'0';
  int C=N.at(2)-'0';
  int D=N.at(3)-'0';
  vector<int>ans(3);
  for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
      for(int k=0;k<2;k++){
        int b,c,d;
        if(i==0){
          b=B;
        }
        else if(i==1){
          b=-1*B;
        }
        if(j==0){
          c=C;
        }
        else if(j==1){
          c=-1*C;
        }
        if(k==0){
          d=D;
        }
        else if(k==1){
          d=-1*D;
        }
        if(A+b+c+d==7){
          ans.at(0)=i;
          ans.at(1)=j;
          ans.at(2)=k;
        }
      }
    }
  }
  cout<<A;
  if(ans.at(0)==0){
    cout<<'+';
  }
  else if(ans.at(0)==1){
    cout<<'-';
  }
  cout<<B;
  if(ans.at(1)==0){
    cout<<'+';
  }
  else if(ans.at(1)==1){
    cout<<'-';
  }
  cout<<C;
  if(ans.at(2)==0){
    cout<<'+';
  }
  else if(ans.at(2)==1){
    cout<<'-';
  }
  cout<<D;
  cout<<'='<<7<<endl;
}
  

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;


int main() {
    ll n; cin >> n;
    string s = to_string(n);
    int l = s.size();
    ll m = s[0] - '0' - 1;
    ll sum = 0;
    for(int i = 0; i < l; i++) sum += s[i] - '0';
    cout << max(sum, m + (l - 1) * 9) << endl;

    return 0;
}


Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define repp(i, l, r) for (long long i = (l); i < (r); i++)
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define per(i, n) for (long long i = (n); i >= 0; --i)
#define all(v) v.begin(), v.end()
const int INF = 1 << 30;
const long long LINF = 1LL << 60;
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

ll h;
ll max_a;

//ミョ(-ω- ?)
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n >> h;
    vector<ll> a(n, 0);
    vector<ll> b(n, 0);
    rep(i, n) { cin >> a[i] >> b[i]; }
    max_a = *max_element(all(a));
    sort(all(b) , greater<ll>());
    vector<ll> sum(n + 1, 0);
    rep(i, n) if (b[i] < max_a) b[i] = 0;
    repp(i, 1, n + 1) { sum[i] = sum[i - 1] + b[i - 1]; }
    ll res = LINF;
    repp(i,1, sum.size()) {
        ll r = 0;
        r += (i);
        ll remain = h - sum[i];
        if(remain < 0){
            chmin(res, r);
            break;
        }
        r += (remain + max_a - 1) / max_a;
        chmin(res, r);
    }
    cout << res << "\n";
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;
typedef unsigned long long ull;

#define F first
#define S second
#define en end()
#define bg begin()
#define rev reverse
#define mp make_pair
#define pb push_back
#define y1 y1234567890
#define um unordered_map                         
#define all(x) x.bg, x.en
#define sqr(x) ((x) * (x))
#define sz(x) (int)x.size()

const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;
const double pi = acos(-1.0);
const double eps = (double)1e-9;

const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

const int N = 100500;

int n, mx, mn, a[N];

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

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

	cin >> n;

	mx = -1;
	mn = N;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mx = max(mx, a[i]);
		mn = min(mn, a[i]);
	}

	if (mx == mn) {
		bool b = 1;
		for (int i = 1; i <= n; i++)
			b &= (a[i] == n - 1);
		if (b || (mx << 1) <= n)
			cout << "Yes";
		else
			cout << "No";
	}
	else if (mx - mn == 1) {
		int x(0), y(0);
		for (int i = 1; i <= n; i++) {
			if (a[i] == mn)
				x++;
			else
				y++;
		}
		if (x + 1 <= mx && mx <= x + (y >> 1))
			cout << "Yes";
		else
			cout << "No";
	}
	else 
		cout << "No";

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<tuple<string, int, int>> AAA;
  for(int i=0;i<N;i++){
  	string a;
    int b;
    cin >> a >> b;
    b=b*(-1);
    AAA.push_back(make_tuple(a, b, i+1));
  }
  sort(AAA.begin(), AAA.end());
  for(tuple<string, int, int> x : AAA){
  	int i;
    tie(ignore, ignore, i)=x;
    cout << i << endl;
  }
}

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

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

    if((a%2 == 0 && b%2 == 0) || (a%2 != 0 && b%2 != 0))
        cout<<(a+b)/2;
    else
        cout<<"IMPOSSIBLE";
}


Measured memory_bytes: 256
use std::cmp;

#[allow(dead_code)]
pub struct Scanner<'a> {
    _buf: &'a str,
    iter: ::std::str::SplitWhitespace<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    pub fn new(buf: &'a str) -> Self {
        Scanner {
            _buf: buf,
            iter: buf.split_whitespace(),
        }
    }

    pub fn array<T>(&mut self, n: usize) -> Vec<T>
        where T: ::std::str::FromStr,
              T::Err: ::std::fmt::Debug,
    {
        let mut res = Vec::with_capacity(n);
        for _ in 0..n {
            res.push(self.value());
        }
        res
    }

    pub fn value<T>(&mut self) -> T
        where T: ::std::str::FromStr,
              T::Err: ::std::fmt::Debug,
    {
        self.next().parse().unwrap()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.next().chars().collect()
    }

    fn next(&mut self) -> &str {
        self.iter.next().unwrap()
    }
}

fn divisors(x: i64) -> Vec<i64> {
    let mut res = vec![];
    for i in 1.. {
        if i*i > x { break; }
        if x % i == 0 {
            res.push(i);
            if i*i != x {
                res.push(x/i);
            }
        }
    }
    res
}

fn main() {
    let mut _input = String::new();
    {
        use ::std::io::Read;
        ::std::io::stdin().read_to_string(&mut _input).unwrap();
    }
    let mut sc = Scanner::new(&_input);

    let n = sc.value::<i64>();
    let m = sc.value::<i64>();

    let ds = divisors(m);

    let mut ans = 1_i64;
    for d in ds {
        if m / d >= n {
            ans = cmp::max(ans, d);
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    int n, m; cin >> n >> m;
    vll xs(n), ys(m);
    ll sumx = 0, sumy = 0;
    for(auto& e : xs) cin >> e, sumx = ADD(sumx, e, mod);
    for(auto& e : ys) cin >> e, sumy = ADD(sumy, e, mod);

    ll resx = 0, resy = 0;
    rep(i, n){
        resx = ADD(resx, SUB(sumx, MUL(n - i, xs[i], mod), mod), mod);
        sumx = SUB(sumx, xs[i], mod);
    }
    rep(i, m){
        resy = ADD(resy, SUB(sumy, MUL(m - i, ys[i], mod), mod), mod);
        sumy = SUB(sumy, ys[i], mod);
    }

    cout << MUL(resx, resy, mod) << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
  vector<int> v;
  rep(i, 5) {
    int a;
    cin >> a;
    v.push_back(a);
  }

  int k;
  cin >> k;

  bool result = true;
  rep(i, 5) {
    rep(j, 5) if (abs(v[i] - v[j]) > k) { result = false; }
  }

  if (result) {
    cout << "Yay!" << endl;
  } else {
    cout << ":(" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
double V[16],s,p;
int D,i,j,k,l;
main(){for(;scanf("%d",&D),D;){D+=3;
	for(i=0;i<D;++i)scanf("%lf",V+i);
	for(i=0;i<D;++i){
		for(j=0;j<D;++j)if(j!=i){
			for(s=k=0;k<D;++k)if(k!=i&&k!=j){
				p=V[k];
				for(l=0;l<D;++l)if(l!=k&&l!=i&&l!=j)p=p*(j-l)/(k-l);
				s+=p;
			}
			if(fabs(s-V[j])>0.1)break;
		}
		if(j==D){
			printf("%d\n",i);
			break;
		}
	}
}}

Measured memory_bytes: 1072
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
//		int[] A = {5, 4, 3, 2, 1, 0,};
//		int n = A.length;
//		insertionSort(A, n, 2);
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

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

		Counter counter = new Counter(0);
		//int count = 0;
		int m = 1;

		int h = 1;
		while (h <= n/9) {
			h = 3*h + 1;// (1,) 4, 13, 40, 121, 364, 1093, ...
			m++;//		   (1,) 2,  3,  4,   5,   6,    7, ...
		}

		int[] G = new int[m];// [... 1093, 364, 121, 40, 13, 4, 1] : G[n] = G[n+1]*3 + 1
		for (int i=0; i < m; i++) {
			G[i] = h;
			h = (h-1)/3;
		}

		for (int i=0; i < m; i++) {
			insertionSort(A, n, G[i], counter);
		}

		System.out.println(m);

		for (int i = 0; i < m-1; i++) {
			System.out.print(G[i] + " ");
		}
		System.out.println(G[m-1]);

		System.out.println(counter.count);

		for (int i=0; i < n; i++) {
			System.out.println(A[i]);
		}
	}

	static class Counter {
		int count;

		Counter(int n) {
			this.count = n;
		}

		Counter counting() {
			this.count++;
			return this;
		}
	}

	static void insertionSort(int[] A, int n, int g, Counter counter) {
		for (int i=g; i < n; i++) {
			int temp = A[i];
			int j = i - g;
			while (j >= 0 && A[j] > temp) {
				A[j+g] = A[j];
				j = j - g;
				counter.counting();
			}
			A[j+g] = temp;
//			System.out.println(java.util.Arrays.toString(A));
		}
	}

	static void shellSort(int[] A, int n) {
		Counter counter = new Counter(0);
		int m = 1;

		int h = 1;
		while (h <= n/9) {
			h = 3*h + 1;
			m++;
		}

		int[] G = new int[m];// [... 1093, 364, 121, 40, 13, 4, 1] : G[n] = G[n+1]*3 + 1
		for (int i=0; i < m; i++) {
			G[i] = h;
			h = (h-1)/3;
		}

		for (int i=0; i < m; i++) {
			insertionSort(A, n, G[i], counter);
		}
	}
}

Measured memory_bytes: 298976
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,sse")
using namespace std;

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

    int x;
    cin >> x;
    int tot = (x / 500) * 1000;
    x %= 500;
    tot += (x / 5) * 5;
    cout << tot << '\n';

    fflush(stdout);
    return 0;
}


Measured memory_bytes: 3652
N = int(input())
r = [int(input()) for i in range(N)]
 
min = r[0]
max = -9999999999999999
 
for i in range(1, N):
    if r[i] - min > max:
        max = r[i] - min
    if r[i] < min:
        min = r[i]
 
print(max)

Measured memory_bytes: 15604
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define PI 4*atan(1)
#define INF 1e8

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

typedef pair<int, pair<int, int>> P;

int main(){
  vector<P> REC;
  for(int i = 1; i <= 150; i++){
    for(int j = i + 1; j <= 150; j++){
      REC.push_back(pair<int,pair<int, int>>(i*i+j*j,pair<int, int>(i,j)));
    }
  }

  sort(REC.begin(), REC.end());
 
  int h, w;
  while(cin >> h >> w, h || w){
    int tmp = h * h + w * w;
    for(int i = 0; i < 150*150; i++){
      if(REC[i].first == tmp && REC[i].second.first > h){
        cout << REC[i].second.first << " " << REC[i].second.second << endl;
        break;
      }else if(REC[i].first > tmp){
        cout << REC[i].second.first << " " << REC[i].second.second << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 3160
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
  long long int n,happy=0;
  scanf("%lld",&n);
  while(n>=500)
  {
      n = n - 500;
      happy = happy + 1000;
  }
  while(n>=5) {
      n = n - 5;
      happy = happy + 5;
  }
  printf("%lld", happy)
;
   return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define INF 1e9
#define all(v) v.begin(), v.end()
typedef long long ll;

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

  int cnt = 0;
  repr(i, 100){
    if(a%i == 0 && b%i == 0) cnt++;
    if(cnt == k){
      cout << i << endl;
      return 0;
    }
  }

  return 0;
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if(A < C && C < B && A < B){
    cout << "Yes" << endl;
  }
  
  else if(B < C && C < A && B < A){
    cout << "Yes" << endl;
  }
  
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
<?php
fscanf(STDIN, '%d %d', $n, $k);
for ($i = 0; $i < $n; $i++) {
    fscanf(STDIN, '%d', $h[]);
}
sort($h);
$ans = 10 ** 9;
for ($i = 0; $i < $n - $k + 1; $i++) {
    $ans = min($h[$i + $k - 1] - $h[$i], $ans);
}
echo $ans;


Measured memory_bytes: 12792
argv = input().split()
n = int(argv[0])
y = int(argv[1])

a = y // 10000
b = (y % 10000) // 5000
c = (y % 5000) // 1000

ta = a
tb = b
tc = c

if ta + tb + tc == n:
    print(ta, tb, tc)
    exit(0)


while ta >= 0:
    while tb >= 0:
        if ta + tb + tc == n:
            print(ta, tb, tc)
            exit(0)
        tb -= 1
        tc += 5
    ta -= 1
    tb = b + (a-ta)*2
    tc = c
print(-1, -1, -1)


Measured memory_bytes: 3064
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;

int main() {
  int n,x;
  cin >> n >> x;
  int ans;
  int tmp;
  cin >> tmp;
  ans=abs(x-tmp);
  for(int i=0;i<n-1;i++){
    cin >> tmp;
    ans=__gcd(ans,abs(tmp-x));
  }
  cout << ans << endl;
}

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

using namespace std;

int n, c;
int a[35][100005];
int sum[100005];
int ans;

int main()
{
    scanf("%d%d", &n, &c);
    for(int i = 0; i < n; i++)
    {
        int t1, t2, t3;
        scanf("%d%d%d", &t1, &t2, &t3);
        for(int j = t1; j <= t2; j++)
        {
            sum[j] += 1 - a[t3][j];
            a[t3][j] = 1;
            ans = max(ans, sum[j]);
        }
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 12416
#include <cstdio>
#include <cctype>
#include <utility>
#include <vector>
using namespace std;

const auto gcu = getchar_unlocked;
const auto pcu = putchar_unlocked;
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _sc _il bool scan
_T T in(int c){T n=0;int m=1;while(isspace(c)){c=gcu();}if(c=='-')m=-1,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
_il int in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _ot _il void out
#define _ol _il void outl
_ot(bool b) {pcu('0'+b);}
_ot(const char *s){while(*s)pcu(*s++);}
_ot(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_ot(string s){for(char c:s)pcu(c);}
#endif
_T _ot(T n){static char b[20];char *p=b,m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=n%10*m+'0',n/=10;while(p!=b)pcu(*--p);}
_ol(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _ot(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _ot(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _ol(T&&... t){out(move(t)...);outl();}

int main() {
	int r = 1, M = 1000000007;
	for (long m = in(), n = in(); n; n >>= 1, m = m * m % M)
		if (n & 1)
			r = r * m % M;
	outl(r);
}


Measured memory_bytes: 2620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    long double n, k; cin >> n >> k;
    vector<long double> p(n);
    for(int i=0; i<n; ++i){cin >> p[i];}
    for(int i=0; i<n; ++i){p[i] = (p[i]+1)/2;}

    vector<long double> sum(n, 0); 
    for(int i=0; i<n+1; ++i){
        sum[i+1] = sum[i]+p[i]; 
    }
    
    long double res = 0;
    for(int i=0; i<n-k+1; ++i){
        res = max(res, sum[i+k]-sum[i]);
    }
    cout << fixed << setprecision(10) << res << endl;
    return 0;
}

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

int main(){
    string S; cin >> S;
    if( S.at(0)!=S.at(1) && S.at(1)!=S.at(2) && S.at(2)!=S.at(3) ){
        cout << "Good" << endl;
    }
    else cout << "Bad" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
 
using namespace std;
 
int main(){
  int N,M; cin>>N>>M;
  vector<pair<unsigned long,int>> v;
  for(int i=0;i<N;i++){
    int a, b; cin>>a>>b;
    v.push_back(make_pair(a,b));
  }
  sort(v.begin(), v.end());
  
  int c=0;
  unsigned long ans=0;
  while(M>0){
    int d = v[c].second;
    ans += min(M,d)*v[c].first;
    M -= min(M,d);
    c++;
  }
  cout<<ans<<endl;
  return 0;
}


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

void main()
{
  auto rd1 = readln.split.to!(size_t[]), n = rd1[0], m = rd1[1];
  auto c = new int[](n);
  foreach (_; 0..m) {
    auto rd2 = readln.splitter;
    auto a = rd2.front.to!size_t-1; rd2.popFront();
    auto b = rd2.front.to!size_t-1;
    if (a > b) swap(a, b);
    if (a == 0) ++c[b];
    if (b == n-1) ++c[a];
  }
  writeln(c.canFind!"a>1" ? "POSSIBLE" : "IMPOSSIBLE");
}


Measured memory_bytes: 3836
seq = list(map(int, "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51".split(',')))

K = int(input())
print(seq[K-1])

Measured memory_bytes: 2940
using System;
using CompLib.Util;

public class Program
{
    private int K, N;
    private int[] A;

    public void Solve()
    {
        var sc = new Scanner();
        K = sc.NextInt();
        N = sc.NextInt();
        A = sc.IntArray();

        int max = int.MinValue;
        for (int i = 0; i < N; i++)
        {
            int d;
            if (i == 0)
            {
                d = A[i] + K - A[N - 1];
            }
            else
            {
                d = A[i] - A[i - 1];
            }

            max = Math.Max(max, d);
        }

        Console.WriteLine(K - max);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 34524
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <cmath>
#include <cassert>
#define SIZE 55

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

int A[SIZE];
bool use[SIZE];

int main()
{
	int n,K;
	scanf("%d %d",&n,&K);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	vector <int> ans;
	for(int t=0;t<=K;t++)
	{
		vector <P> vx;
		for(int i=0;i<n;i++)
		{
			if(use[i]) continue;
			vx.push_back(P(A[i],i));
		}
		sort(vx.begin(),vx.end(),greater <P>());
		memset(use,false,sizeof(use));
		for(int i=0;i<vx.size();i++)
		{
			int v=vx[i].second;
			A[v]--;
			if(A[v]<0)
			{
				puts("-1");
				return 0;
			}
			ans.push_back(v);
			if(i+1==vx.size()) use[v]=true;
		}
	}
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++) printf("%d ",ans[i]+1);
	puts("");
	return 0;
}


Measured memory_bytes: 256
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=100000+19;

struct Edge{
	int y,nxt;
} E[N*2];
int las[N],fa[N],val[N],col[N],sum[N],sz[N],tar[N],coef[N];
int n,cnt,x,y,u,v,m,ji,ou;
Vi V;
ll ans;

void Link(int x,int y){
	E[cnt]=(Edge){y,las[x]};las[x]=cnt++;
	E[cnt]=(Edge){x,las[y]};las[y]=cnt++;
}
int getf(int x){
	if (fa[x]==x) return x;
	int f=fa[x];
	fa[x]=getf(fa[x]);
	val[x]^=val[f];
	return fa[x];
}
void Union(int x,int y){
	int fx=getf(x),fy=getf(y);
	fa[fx]=fy;
	val[fx]=1^val[x]^val[y];
}
void dfs(int x,int fa){
	sum[x]=col[x];
	sz[x]=1;
	for (int i=las[x],y;~i;i=E[i].nxt)
		if ((y=E[i].y)!=fa){
			col[y]=col[x]^1;
			dfs(y,x);
			sum[x]+=sum[y];
			sz[x]+=sz[y];
		}
	tar[x]=sz[x]-sum[x];
}
void Dfs(int x,int fa){
	sum[x]=col[x];
	for (int i=las[x],y;~i;i=E[i].nxt)
		if ((y=E[i].y)!=fa){
			Dfs(y,x);
			sum[x]+=sum[y];
			ans+=abs(sum[y]-tar[y]);
		}
}
void Dfs2(int x,int fa){
	for (int i=las[x],y;~i;i=E[i].nxt)
		if ((y=E[i].y)!=fa){
			Dfs2(y,x);
			coef[x]+=coef[y];
			if (coef[y]==0){
				ans+=abs(sum[y]-tar[y]);
			} else{
				V.pb(coef[y]==1?tar[y]-sum[y]:sum[y]-tar[y]);
			}
		}
}
void Work1(){
	if (n%2==1||sum[1]!=n/2){
		puts("-1");
		exit(0);
	}
	Dfs(1,-1);
}
void Work2(){
	if (n%2==1||sum[1]!=n/2){
		puts("-1");
		exit(0);
	}
	coef[u]=1;
	coef[v]=-1;
	Dfs2(1,-1);
	V.pb(0);
	sort(V.begin(),V.end());
	For(i,0,V.size()) ans+=abs(V[i]-V[int(V.size())/2]);
}
void Work3(){
	if ((n-sum[1]-sum[1])%2!=0){
		puts("-1");
		exit(0);
	}
	int tmp=(n-sum[1]-sum[1])/2;
	col[u]+=tmp;
	col[v]+=tmp;
	Dfs(1,-1);
	ans+=abs(tmp);
}

int main(){
	//freopen("2_13.txt","r",stdin);
	memset(las,-1,sizeof(las));
	n=IN(),m=IN();
	For(i,1,n+1) fa[i]=i,val[i]=0;
	For(i,0,m){
		x=IN(),y=IN();
		if (getf(x)!=getf(y)){
			Union(x,y);
			Link(x,y);
		} else{
			u=x,v=y;
			if ((val[x]^val[y])==0) ji=1;else ou=1;
		}
	}
	dfs(1,-1);
	if (m==n-1) Work1();
	if (m==n&&ou) Work2();
	if (m==n&&ji) Work3();
	cout<<ans<<endl;
}

Measured memory_bytes: 11388
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sum := int64(0)
	min := 10000000001
	isNegaOdd := false
	for i := 0; i < n; i++ {
		sc.Scan()
		a, _ := strconv.Atoi(sc.Text())
		if a < 0 {
			isNegaOdd = !isNegaOdd
			a = -a
		}
		sum += int64(a)
		if a < min {
			min = a
		}
	}
	if isNegaOdd {
		sum -= int64(min * 2)
	}
	fmt.Println(sum)
}


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

using namespace std;

const int mod = 1e9 + 7;
const int DIM = 2007;

#define int long long

int v[DIM];
int inv[DIM];
int low[DIM];
bool ok[DIM];

main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	
	for(int j = 1; j <= n; j++)
	{
		for(int i = j + 1; i <= n; i++)
			if(v[j] > v[i])
				inv[j]++;
		
		if(ok[v[j]] == false)
		{
			ok[v[j]] = true;
			
			for(int i = 1; i <= n; i++)
				if(v[i] < v[j])
					low[v[j]]++;
		}
	}
	
	int p = ((k - 1LL) * (k) / 2) % mod;
	int ans = 0;
	
	for(int i = 1; i <= n; i++)
	{
		ans = (ans + ((inv[i] * k) % mod + (p * low[v[i]]) % mod) % mod) % mod;
	}
	
	cout << ans;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cmath>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<stdio.h>
#include<queue>
using namespace std;
int main()
{
  int g,m;
  cin>>g>>m;
  for(int i=0;i<=m/10000;i++)
    for(int j=0;j<=g-i;j++)
    {
      if(10000*i+5000*j+1000*(g-i-j)==m)
      {
        cout<<i<<" "<<j<<" "<<g-i-j<<endl;
        system("pause");
        return 0;
      }
    }
  cout<<"-1 -1 -1"<<endl;
  system("pause");
  return 0;
}

Measured memory_bytes: 504
#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>;
 
 
int main() {
    vector<int>x(5);
    rep(i,5) cin >> x.at(i);
    rep(i,5){
        if(x.at(i)==0) cout << i+1 << endl;
    }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,N) for(int i = 0; i < N; i++)
typedef pair<int,int> Pi;
#define F first
#define S second

int main()
{
  int N, M;
  int cost[1005];
  int cnt[1005] = {0};
  cin >> N >> M;
  Rep(i,N)cin >> cost[i];
  int data;
  while(M--) {
    cin >> data;
    Rep(i,N) {
      if(data >= cost[i]) {
	cnt[i]++;
	break;
      }
    }
  }
  cout << max_element(cnt,cnt + N) - cnt + 1 << endl;
  return 0;
}

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,d,c;
ll p[51],b[51],pb[51];
void dfs(ll i,ll j){
  if(i==j){
  }else if(i==1){
    if(j==2)
      c++;
    else if(j==3)
      c+=2;
    else if(j>3)
      c+=3;
  }else if(j<=pb[i-1]+1)
    dfs(i-1,j-1);
  else if(j==pb[i-1]+2)
    c+=p[i-1]+1;
  else{
    if(i==1)
      c+=3;
    else{
      c+=p[i-1]+1;
      dfs(i-1,j-pb[i-1]-2);
    }
  }
}
int main(){
  cin>>n>>d;
  p[0]=1;
  b[0]=0;
  pb[0]=p[0]+b[0];
  for(ll i=1;i<=50;i++){
    p[i]=p[i-1]*2+1;
    b[i]=b[i-1]*2+2;
    pb[i]=p[i]+b[i];
  }
  dfs(n,d);
  cout<<c<<endl;
}

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

int main(){
    int n;
    cin >> n;
    int a1,a2,a3,a4,l1,l2,l3;
    a1 = n % 10;
    a2 = (n % 100 - n % 10) / 10;
    a3 = (n % 1000 - n % 100) / 100;
    a4 = (n % 10000 - n % 1000) / 1000;
    bool t = false;
    for (int a = 0; a < 2; a++){
        for (int b = 0; b < 2; b++){
            for (int c = 0; c < 2; c++){
                if (a4 + (2*a -1)*a3 + (2*b -1)*a2 + (2*c -1)*a1 == 7){
                    l1 = a;
                    l2 = b;
                    l3 = c;
                    t = true;
                    break;
                }    
            }
            if (t){
                break;
            }
        }
        if (t){
            break;
        }
    }
    char c1,c2,c3;
    if (l1 == 0){
        c1 = '-';
    }
    else{
        c1 = '+';
    }
    if (l2 == 0){
        c2 = '-';
    }
    else{
        c2 = '+';
    }
    if (l3 == 0){
        c3 = '-';
    }
    else{
        c3 = '+';
    }
    cout << a4 << c1 << a3 << c2 << a2 << c3 << a1 << '=' << 7 << endl; 
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    string s; cin>>s;
    ll k,n=s.size(); cin>>k;
    vector<pair<char,ll>> c;
    ll cnt=1;
    rep(i,n-1){
        if(s[i]!=s[i+1]){
            c.push_back(mk(s[i],cnt));
            cnt=1;
        }
        else cnt++;
    }
    c.push_back(mk(s.back(),cnt));
    if(c.size()==1){
        cout<<k*n/2<<endl;
        return 0;
    }
    if(s[1]==s.back()){
        ll ans=0;
        for(int i=1;i<c.size()-1;i++)
        ans+=c[i].second/2;
        ans*=k;
        ans+=c[0].second/2+c.back().second/2;
        ans+=(c[0].second+c.back().second)/2*(k-1);
        cout<<ans<<endl;
    }
    else{
        ll ans=0;
        for(auto q:c) ans+=q.second/2;
        cout<<ans*k<<endl;
    }
}


Measured memory_bytes: 3608
A, B, C = map(int, input().split())
K = int(input())

while K >0:
    if A >= B:
        B *= 2
        K -= 1
    elif B >= C:
        C *= 2
        K -= 1
    else:
        break

if A < B and B < C:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  string s[n];
  vector<char>v={};
  for(int i=0;i<n;i++){
    cin>>s[i];
  }
  sort(s[0].begin(),s[0].end());
  if(n==1) cout<<s[0]<<endl;
  else{
    for(int i=0;i<s[0].size();i++){
      bool b=true;
      for(int j=1;j<n;j++){
        if(s[j].find(s[0][i])==string::npos){
          b=false;
          break;
        }
        else s[j].erase(find(s[j].begin(),s[j].end(),s[0][i]));
      }
      if(b) v.push_back(s[0][i]);
    }
    for(int i=0;i<v.size();i++)cout<<v.at(i);
  }
}




Measured memory_bytes: 256