akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main() {
    int n, m, a, b;
    cin >> n >> m;
    int capital[n];
    for (int i = 1; i <= n; i++) capital[i] = 0;

    for (int i = 1; i <= m; i++) {
        a = 0, b = 0;
        cin >> a >> b;
        for (int j = 1; j <= n; j++) {
            if (a == j) capital[j] += 1;
            if (b == j) capital[j] += 1;
        }
    }
    

    for (int i = 1; i <= n; i++) cout << capital[i] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n, k; cin >> n >> k;
    if(k == 1) cout << 0 << endl;
    else cout << n-k << endl;
}

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

using namespace std;
typedef long long ll;

ll lcm(ll a,ll b)
{
    return (a*b)/(__gcd(a,b));
}

int main()
{
    ll a,b,c,d,div_c,div_d;

    cin>>a>>b>>c>>d;

    div_c=b/c-(a-1)/c;
    div_d=b/d-(a-1)/d;

    ll cnt=div_c+div_d-(b/lcm(c,d))+(a-1)/lcm(c,d);

    cout << b-a+1-cnt<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void kouri(int, int, int);
int  sum_max = 0;
int c[101][101];
int a, b;
int main() {
	while (1) {
		sum_max = 0;
		cin >> a >> b;
		if (a == 0 && b == 0)break;
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= a; i++) {
			for (int j = 1; j <= b; j++) {
				cin >> c[i][j];
			}
		}
		for (int i = 1; i <= a; i++) {
			for (int j = 1; j <= b; j++) {
				if (c[i][j] == 1) {
					kouri(i, j, 0);
				}
			}
		}
		cout << sum_max << endl;
	}
	return 0;
}
void kouri(int x, int y, int sum) {
	c[x][y] = 0;
	sum++;
	if (c[x][y + 1] == 1)kouri(x, y + 1, sum);
	if (c[x][y - 1] == 1)kouri(x, y - 1, sum);
	if (c[x + 1][y] == 1)kouri(x + 1, y, sum);
	if (c[x - 1][y] == 1)kouri(x - 1, y, sum);
	c[x][y] = 1;
	if (sum > sum_max)sum_max = sum;
}

Measured memory_bytes: 3096
#include<iostream>
#include<string>
#define SIZE 10005
using namespace std;
 
char str[SIZE];
 
int main() {
  int n;
  cin >> n;
  int cnt = 0;
  int a = 0, b = 0, ba = 0;
  for (int i = 0; i < n; i++) {
    cin >> str;
    int L = strlen(str);
	for (int j = 0; j + 1 < L; j++) {
	  if (str[j] == 'A' && str[j + 1] == 'B') cnt++;
	}
	if (str[0] == 'B') b++;
	if (str[L - 1] == 'A') a++;
	if (str[0] == 'B' && str[L - 1] == 'A') ba++;
  }
  cnt += min(a,b);
  if (a == ba && b == ba && b > 0) cnt--;
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1;
int a[N];
int b[N];
main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]);
    for(int i=1;i<=m;i++)b[i]+=b[i-1];
    int mx=0,sum=0;
    for(int i=0;i<=n;i++){
        sum+=a[i];
        if(sum>k)break;
        int l=0,r=m,ans;
        while(l<=r){
            int mid=(l+r)/2;
            if(sum+b[mid]<=k){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        mx=max(mx,i+ans);
    }
    cout<<mx<<endl;
}


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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define vvp vector<vector<pair<int,int>>>

const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<int>>; //Caution!! Segmentation Fault!! Don't forget to add +1!

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i--)
#define RepA(x) for(auto &item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

template<typename TypeInt> //最大公約数
TypeInt GCD(TypeInt a,TypeInt b){
    if(a%b==0) return b;
    else return GCD(b,a%b);
}
template<typename TypeInt> //最小公倍数
TypeInt LCM(TypeInt a,TypeInt b){
    return a*b/GCD(a,b);
}

int IN_int(){
    int x;
    scanf("%d",&x);
    return x;
}

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

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

const int NMAX = 100;
bool flag;

bool comp(int x,int y){
    return abs(0-x)<abs(0-y);
}

signed main(){
    CIN(A,B,K);
    RepS(i,A,min(B,A+K-1)){
        printf("%d\n",i);
    }
    RepS(i,max(B-K+1,A+K),B){
        printf("%d\n",i);
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

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

	while ( true )
	{
		int n, m;
		cin >> n >> m;

		if ( !( n | m ) )
		{
			break;
		}

		VI ps( n );
		FOR( p, ps )
		{
			cin >> p;
		}
		ps.PB( 0 );

		vector<LL> totals;
		REP( i, 0, ps.size() )
		{
			REP( j, i, ps.size() )
			{
				totals.PB( (LL)ps[i] + ps[j] );
			}
		}
		sort( ALL( totals ) );

		LL res = 0;
		REP( i, 0, totals.size() )
		{
			if ( m < totals[i] )
			{
				break;
			}

			int pos = upper_bound( ALL( totals ), m - totals[i] ) - totals.begin();
			if ( totals[i] + totals[ pos - 1 ] <= m )
			{
				res = max( res, totals[i] + totals[ pos - 1 ] );
			}
		}

		cout << res << endl;
	}

	return 0;
}

Measured memory_bytes: 9200
#include <bits/stdc++.h>
#define range(i, a, n) for(int (i) = (a); (i) < (n); (i)++)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
using namespace std;
int main(void){
    vector<int> a(10), b(10);
    for(auto & e : a) cin >> e;
    for(auto & e : b) cin >> e;

    sort(begin(a), end(a), greater<int>());
    sort(begin(b), end(b), greater<int>());

    cout << a[0] + a[1] + a[2] << " " << b[0] + b[1] + b[2] << endl;

	return 0;
}

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

#define INF 1e9
using namespace std;

int main() {

    int N; cin >> N;

    vector<int> V(N);
    for (int i = 0; i < N; ++i) {
        cin >> V[i];
    }

    vector<int> C(N);
    for (int j = 0; j < N; ++j) {
        cin >> C[j];
    }

    int ans = 0;
    for (int k = 0; k < N; ++k) {
        if (V[k] - C[k] > 0) {
            ans += V[k] - C[k];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <stack>
#include <regex>

#define mod 1000000007
#define INF2 9999999999
#define INF (1<<30)
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)
#define P pair<int, int>

using namespace std;
//using ll = long long;
using ll = int64_t;

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

int n, k;
char d[10];

bool check(int n){
    string s = to_string(n);
    for(int i = 0; i < s.length(); i++){
        for(int j = 0; j < k; j++){
            if(s[i] == d[j]) return false;
        }
    }
    return true;
}

void solve(){
    cin >> n >> k;
    rep(i, k) cin >> d[i];

    while(!check(n)){
        n++;
    }
    cout << n << endl;
}

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


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

int main(){ 
    int n;
    int d[32]={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};
    cin>>n;
    cout<<d[n-1];
    }


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String Str = sc.nextLine();
        String Ans = "";
        int l = Str.length();
        int i;
        char c1,c2;
        for(i=0;i<l;i++){
            c1 = Str.charAt(i);
            if(Character.isLowerCase(c1) == true) {
                c2 = Character.toUpperCase(c1);
            }else{
                c2 = Character.toLowerCase(c1);
            }
            Ans += c2;
        }
        System.out.println(Ans);
    }
}



Measured memory_bytes: 31372
n = int(input())
w = [input() for i in range(n)]
for i in range(len(w)):
	for j in range(i + 1, len(w)):
		if w[i] == w[j]:
			print('No')
			exit()

for i in range(len(w) - 1):
	if w[i][-1] != w[i + 1][0]:
		print('No')
		exit()

print('Yes')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn = 2e5 + 50;
const ll mod = 1e9+7;
const int N = 52;
struct matrix{
  ll val[N][N];
  matrix(){memset(val,0,sizeof(val));}
  matrix operator*(const matrix & rhs)const{
    matrix ret;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
        for(int k = 0; k < N; k++)
          ret.val[i][j] += val[i][k] * rhs.val[k][j]%mod,
          ret.val[i][j] %= mod;
    return ret;
  }
};
matrix pow_mod(const matrix& b, ll p){
  matrix ret, cur = b;
  for(int i = 0; i < N; i++)
    ret.val[i][i] = 1;
  while(p){
    if(p & 1)
      ret = ret * cur;
    cur = cur * cur;
    p>>=1;
  }
  return ret;
}
matrix G;
int n;
ll k;
int main(){
    scanf("%d %lld", &n, &k);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%lld", &G.val[i][j]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < i; j++)
            swap(G.val[i][j], G.val[j][i]);
    G = pow_mod(G, k);
    ll ans = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            ans = (ans + G.val[i][j]) % mod;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<algorithm>
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
void over(){puts("-1"),std::exit(0);}
const int N=500007;
std::vector<int>e[N];
int n,m,ans,eu,ev,a[N],fa[N],dep[N],f[N];
void dfs(int u)
{
    dep[u]=dep[fa[u]]+1,f[u]=dep[u]&1? 1:-1;
    for(int v:e[u]) if(v^fa[u]) dep[v]? (eu=u,ev=v):(fa[v]=u,dfs(v),f[u]+=f[v]);
}
void work1()
{
    if(f[1]) over();
    for(int i=1;i<=n;++i) ans+=abs(f[i]);
    printf("%d",ans);
}
void work2()
{
    if(f[1]&1) over();
    int x=-f[1]/2;
    for(;eu;eu=fa[eu]) f[eu]+=x;
    for(;ev;ev=fa[ev]) f[ev]+=x;
    for(int i=1;i<=n;++i) ans+=abs(f[i]);
    printf("%d",ans+abs(x));
}
void work3()
{
    if(f[1]) over();
    int c=0,x;
    for(;ev^eu;ev=fa[ev]) a[++c]=f[ev],dep[ev]=0;
    std::sort(a+1,a+c+1),x=a[(c+1)/2];
    for(int i=1;i<=n;++i) if(dep[i]) ans+=abs(f[i]);
    for(int i=1;i<=c;++i) ans+=abs(a[i]-x);
    printf("%d",ans+abs(x));
}
int main()
{
    n=read(),m=read();
    for(int i=1,u,v;i<=m;++i) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    dfs(1);
    m==n-1? work1():(abs(dep[eu]-dep[ev])&1? work3():work2());
}

Measured memory_bytes: 25984
import java.util.*; 

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int a = 1;
        
        for (int i = 0; i < n; i++) {
        	if (a * 2 < a + k) {
        	    a *= 2;
        	} else {
        	    a += k;
        	}
        }
        System.out.print(a);
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<double> v(N);
  for (int i=0;i<N;i++){
    cin >> v[i];
  }
  sort(v.begin(),v.end());
  for (int i=0;i<N-1;i++){
    v[i+1]=(v[i]+v[i+1])/2;
  }
  cout << fixed << setprecision(5);
  cout << v[N-1] << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s,t;
    int ans=0;
    cin>>s;
    cin>>t;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3780
from itertools import count

def factorials_with_inv(k,mod):
    """
    0! ... k! とそれらのmod逆元を求めて返す
    """
    fac = [1]*(k+1)
    inv = [1]*(k+1)
    t = 1
    for i in range(1,k+1):
        t *= i
        t %= mod
        fac[i] = t

    t = pow(t,-1,mod)
    for i in reversed(range(1,k+1)):
        inv[i] = t
        t *= i
        t %= mod

    return fac, inv

S = int(input())
MOD = 10**9+7
res = 0
fac,inv = factorials_with_inv(S*2,MOD)

for n in count(1):
    s = S - 3*n
    if s < 0:
        break

    res += fac[s+n-1]*inv[s]*inv[n-1]
    res %= MOD


print(res)



Measured memory_bytes: 9352
#include<algorithm>
#include<cstdio>
#include<functional>
#include<iostream>
#include<cfloat>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<time.h>
#include<vector>
using namespace std;
int main()
{
	int x,y,z,a,n;
	cin >> x >> y >> z >> a;
	for (int i=0;i<=x;i++)
	{
		for (int j=0;j<=y;j++)
		{
			for (int m=0;m<=z;m++)
			{
				if (i*500+j*100+m*50==a)
				{
					n++;
				}
			}
		}
	}
	cout << n << endl;
	system("pause");
	return 0;
}

Measured memory_bytes: 504
N,M = map(int,input().split())
S = [list(map(int,input().split())) for _ in range(N)]
S.sort()
ans = 0
for s in S:
    if M > s[1]:
        ans += s[1]*s[0]
        M -= s[1]
    else:
        ans += M*s[0]
        break
print(ans)

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

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

using namespace std;

namespace utils{
  template <typename T> void print(vector<vector<T>> mat) {
    rep (i, mat.size()) {
      rep (j, mat[0].size()) cout << mat[i][j] << ' ';
      cout << endl;
    }
  }

  template <typename T> void print(vector<T> v) {
    rep (i, v.size()) cout << v[i] << ' ';
    cout << endl;
  }

  template <typename T> pair<T, T> shape(vector<vector<T>> mat) {
    int d1, d2;

    d1 = mat.size();
    if (d1 > 0) d2 = mat[0].size();
    else int d2 = 0;
    cout << "(" << d1 << ", " << d2 << ")" << endl;
    return make_pair(0, 0);
  }

  template <typename T> vector<vector<T>> empty(int n, int m) {
    vector<vector<T>> mat(n, vector<T>(m));
    return mat;
  }
}


int main() {
  int n, m;
  cin >> n >> m;

  vector<int> c(m+1);
  rep (i, m) cin >> c[i+1];

  vector<vector<int>> dp = utils::empty<int>(m+1, n+1);
  rep (i, m+1) fill(dp[i].begin(), dp[i].end(), 0);
  rep (i, n+1) dp[0][i] = 1<<29;

  for (int i=1; i<=m; i++) {
    for (int j=1; j<=n; j++) {
      // cout << i << ',' << j << endl;
      if (j - c[i] < 0) {
        dp[i][j] = dp[i-1][j];
      }
      else {
        dp[i][j] = min(dp[i-1][j], dp[i][j-c[i]]+1);
      }
    }
  }

  // utils::print(dp);
  cout << dp[m][n] << endl;
}

Measured memory_bytes: 7080
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define mp			make_pair
#define fi			 first
#define se			 second
#define for0(i,n)        for(int i=0;i<n;i++)
#define for1(i,n)        for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)    cout<<"Case "<<z<<": "<<x<<"\n"
vi used(10,0),a,b,per;
int n,p,q,cnt=0;
void search(){
	if(per.size()==n){
		cnt++;
		if(per==a) p=cnt;
		if(per==b)q=cnt;
		}
	for(int i=1 ; i<=n ; i++){
		if(used[i]) continue;
		used[i]=1;
		per.pb(i);
		search();
		per.pop_back();
		used[i]=0;
		}
	}
int main()
{
	int x;
	cin>>n;
	for0(i,n){
		cin>>x;
		a.pb(x);
		}
	for0(i,n){
		cin>>x;
		b.pb(x);
		}
	search();
	cout<<abs(p-q)<<nw;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
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;}

int main(){
    int n, x; cin >> n >> x;
    vector<int> l(n);
    vector<int> sum(n);
    rep(i, n) cin >> l[i];

    int cnt=0;
    rep(i, n){
        sum[i+1] = sum[i]+l[i];
    }
    for(int i=0; i<=n; i++) {
        if(sum[i] <= x) {
        cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007; // 998244353
using ll = long long;
using namespace std;

int n; ll m;
vector<ll> a;

bool judge( int x ){
	ll sum = 0;
	for( auto k : a ){
		sum += (ll)(a.end() - lower_bound( a.begin(), a.end(), x-k ));
	}
	return sum >= m;
}

int main(){
	cin >> n >> m;
	a.resize(n);
	for( auto &k : a ) cin >> k;
	sort( a.begin(), a.end() );
	int ok = -1;
	int ng = 2*a.back()+1;
	while( abs(ok-ng) > 1 ){
		int mid = (ok+ng)/2;
		( judge(mid) ? ok : ng ) = mid;
	}
	vector<ll> sum(n+1, 0);
	for( int i = 0; i < n; ++i ) sum[i+1] = sum[i] + a[i];
	ll cnt = 0;
	ll ans = 0;
	for( auto x : a ){
		int t = lower_bound( a.begin(), a.end(), ok-x ) - a.begin();
		ans += sum[n]-sum[t]+((n-t)*x);
		cnt += n-t;
	}
	ans -= (cnt-m)*ok;
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main() {
  char s[4]={};
  
  for(int i=0;i<4;i++){
    cin >> s[i];
  }
  
  int a = 0;
  
  for(int i=0; i<4; i++){
    
    if(s[i] == '+'){
      a++;
    }
    
    else{
      a--;
      }
  }
  cout << a <<endl;
}

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

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

#define INF 1 << 29
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n,d,x;

int main(){
  cin >> n>>d>>x;
  REP(i,n){
    int a;
    cin >> a;
    x += d/a + 1;
    if(d%a==0) x--;
  }
  cout << x << endl;
}


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

int main(){
  string B;
  cin >> B;
  vector<char>A(22);
  A[1]='S';
  A[2]='A';
  A[3]='T';
  A[4]='F';
  A[5]='R';
  A[6]='I';
  A[7]='T';
  A[8]='H';
  A[9]='U';
  A[10]='W';
  A[11]='E';
  A[12]='D';
  A[13]='T';
  A[14]='U';
  A[15]='E';
  A[16]='M';
  A[17]='O';
  A[18]='N';
  A[19]='S';
  A[20]='U';
  A[21]='N';
  for(int i=1;i<20;i+=3){
    if(A[i]==B.at(0)){
      if(A[i+1]==B.at(1)){
        cout << (i+2)/3 << endl;
      }
    }
  }
}


Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<30;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

int main(){
	double w, h, x, y;
	cin >> w >> h >> x >> y;
	cout << fixed << setprecision(10) << w*h/2 << " ";
	if(x*2 == w && y*2 == h) cout << 1 << endl;
	else cout << 0 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <utility>
using namespace std;

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

int gcdArray(int a[], int start, int stop){
	int ans = a[start];
	for(int i = start; i<stop; i++){
		ans = gcd(a[i], ans);
	}
	return ans;
}

int gcdArraySkip(int a[], int skip, int n){
	int ans = a[0];
	if(skip==0){
		ans = a[1];
	}
	for(int i = 1; i<n; i++){
		if(i == skip){
			continue;
		}
		ans = gcd(a[i], ans);
	}
	return ans;
}

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

	if(n>100){
		result = max(gcdArray(a, 0, n/2), gcdArray(a, n/2, n));
		cout << result << '\n';
	}
	else{
		for(int i = 0; i<n; i++){
			result = max(result, gcdArraySkip(a, i, n));
		}
		cout << result << '\n';		
	}

}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long INT;

INT A[200100], n, C[200100][3];

INT f(INT i, INT c){
    if(C[i][c]) return C[i][c];
    INT k;
    if(i+c==n) return A[i];
    if(i>n) return 0;
    k = f(i+2, c) + A[i];
    if(c>0) k = max(k,f(i+3, c-1) + A[i]);
    if(c>1) k = max(k,f(i+4, c-2) + A[i]);

    return C[i][c]=k;
}
int main(){
    INT i;
    cin >>n;
    for(i=1;i<=n;i++) cin >> A[i];
    if(n%2==0) cout << max(f(1, 1),f(2,0));
    else cout <<max(f(1, 2),max(f(2,1),f(3,0)));
}


Measured memory_bytes: 14568
# SelectionSort(A)
#1 for i = 0 to A.length-1
#2     mini = i
#3     for j = i to A.length-1
#4         if A[j] < A[mini]
#5             mini = j
#6     swap A[i] and A[mini]

# リストの宣言
A = []

# 入力の最初の行に、数列の長さを表す整数 N が与えられます。
# 2 行目に、N 個の整数が空白区切りで与えられます。
LENGTH =int(input())
A = input().split()

# 変数
i = 0
CHANGE_COUNT = 0

while i <= LENGTH -1:
    j = i + 1
    mini = i
    while j <= LENGTH -1:
        if int(A[j]) < int(A[mini]) :
            mini = j
        j += 1
    if mini != i:
        tmp = A[i]
        A[i] = A[mini]
        A[mini] = tmp
        CHANGE_COUNT += 1
    i += 1

print(" ".join(map(str,A)))
print (CHANGE_COUNT)


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

int M = 1e9+7;

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

    int n , k;
    cin >> n >> k;
    int a[n+1];
    for(int i = 1; i <= n; i++) cin >> a[i];
    int dp[n+1][k+1];
    memset(dp , (int)0 , sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= k; i++) dp[0][i] += dp[0][i-1];
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            int x = min(j, a[i]) , sum = dp[i-1][j];
            if(j-x > 0) sum = (sum - dp[i-1][j-x-1] + M)%M;
            dp[i][j] = sum;
        }
        for(int j = 1; j <= k; j++) dp[i][j] = (dp[i][j] + dp[i][j-1])%M;
    }
    int ans = dp[n][k];
    if(k > 0) ans = (ans - dp[n][k-1] + M)%M;
    cout << ans << "\n";

    return 0;
}



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

using namespace std;

int main(int argc, char const* argv[])
{
	int data_x[10000], data_y[10000];
	int i;
	for (i=0 ;; i++) {
		cin >> data_x[i] >> data_y[i];
		if (data_x[i] == 0 && data_y[i] == 0) {
			break;
		}
	} 

	for (int j=0; j<i; j++) {
		cout << min(data_x[j], data_y[j]) << " " << max(data_x[j], data_y[j]) << endl;
	}
	return 0;
}


Measured memory_bytes: 1184
#include<bits/stdc++.h>
using namespace std;
#define maxn 320
#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x) for(register int i = head[x] ; i ; i = e[i].next)
#define pb push_back
#define prev prev_
#define stack stack_
#define inf 0x3f3f3f3f

typedef unsigned long long ll;

int n,k,mod;
ll f[maxn][maxn],sum[maxn][maxn];
ll c[maxn][maxn];

inline void up(ll &x,ll y) { x = (x + y) % mod; }
void init(){
	c[0][0] = 1;
	rep(i,1,n + 1){
		c[i][0] = 1;
		rep(j,1,i){
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
		}
	}
}
int main(){
	cin>>n>>k>>mod;
	init();
	repd(i,k,0) f[1][i] = 1 , sum[1][i] = (sum[1][i + 1] + f[1][i]) % mod;
	rep(i,2,n + 1){
		rep(j,0,k){
			rep(l,1,i - 1){
				up(f[i][j],c[i - 2][l - 1] * sum[l][j + 1] % mod * f[i - l][j] % mod);
			}
		}
		repd(j,k,0) up(sum[i][j],sum[i][j + 1] + f[i][j]);
	}
	cout<<f[n + 1][0]<<endl;
}


Measured memory_bytes: 2560
h,w,m = map(int,input().split())
H = [set() for _ in range(h)]
W = [set() for _ in range(w)]
cord = []
for _ in range(m):
    a,b = map(int,input().split())
    H[a-1].add(b-1)
    W[b-1].add(a-1)
    cord.append((a-1,b-1))
X = 0
set_x = set()
for i in range(h):
    if X<len(H[i]):
        X = len(H[i])
        set_x= set()
        set_x.add(i)
    elif X ==len(H[i]):
        set_x.add(i)

    
Y = 0
set_y = set()
for i in range(w):
    if Y<len(W[i]):
        Y = len(W[i])
        set_y = set()
        set_y.add(i)
    elif Y ==len(W[i]):
        set_y.add(i)
# print(set_x,set_y,X,Y)
n = len(set_x)*len(set_y)
for x,y in cord:
    if x in set_x and y in set_y:
        n -=1
if n:
    cnt =0
else:
    cnt = -1

print(X+Y+cnt)


Measured memory_bytes: 321760
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define eps 1.0e18
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define memset(x,y) memset(x,y,sizeof(x))
#define lson i << 1,l,m
#define rson i << 1 | 1,m + 1,r
#define ll long long
using namespace std;
map <ll,int> mp;
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("text1.in","r",stdin);
	//freopen("text1.out","w",stdout);
	ll ans=0;
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++){
			for(ll k=1;k<=n;k++){
				ans+=gcd(i,gcd(j,k));
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

int main(void){
    int A,B,C,K;
    cin >> A >> B >> C >> K;
    
    for(int i = 0; i <= K; i++){
        for(int j = 0; j <= K; j++){
            for(int k = 0; k <= K; k++){
                if(i+j+k > K) continue;
                
                int a = A * pow(2,i);
                int b = B * pow(2,j);
                int c = C * pow(2,k);
                
                if(a < b && b < c){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    
    cout << "No" << endl;
}

Measured memory_bytes: 4088
import java.util.*;
public class Main
{
    public static void main(String[] args) 
    {
        Scanner in=new Scanner(System.in);
        int m[][]={
                {1,2,1,2,1,4,1,4},
                {1,2,1,4,1,4,1,2},
                {1,4,1,2,1,2,1,4},
                {1,4,1,4,1,2,1,2},
                {2,1,2,1,4,1,4,1},
                {2,1,4,1,4,1,2,1},
                {4,1,2,1,2,1,4,1},
                {4,1,4,1,2,1,2,1},
        };
        while(in.hasNext())
        {
            int a[]=new int[8];
            for(int i=0;i<8;i++)
                a[i]=in.nextInt();
             
            int id=-1;
            int min=Integer.MAX_VALUE;
            for(int i=0;i<8;i++)
            {
                int sam=0;
                for(int j=0;j<8;j++)
                {
                    int cnt=m[i][j]-a[j];
                    if(cnt>0)
                        sam+=cnt;
                }
                if(sam<min)
                {
                    min=sam;
                    id=i;
                }
            }
            for(int i=0;i<7;i++)
                System.out.print(m[id][i]+" ");
            System.out.println(m[id][7]);
        }
    }
 
    static public void debug(Object... o)
    {
        System.out.println(Arrays.deepToString(o));
    }
}


Measured memory_bytes: 30004
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define llu unsigned long long
#define sf scanf
#define pf printf
#define pi acos(-1)
#define time_save ios_base::sync_with_stdio(false); cin.tie(NULL);

int main()
{
    time_save;
    ll h,n;
    while(cin>>h>>n)
    {
        ll sum=0,x;
        for(ll i=0;i<n;i++)
        {
            cin>>x;
            sum+=x;
        }
        if(sum>=h)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
using System;

class Program
{
    static void Main()
    {
        // long A, B = long.Parse(Console.ReadLine());
        // int[] IntArr => StrArr.Select(int.Parse).ToArray();
        string[] sarr = Console.ReadLine().Split(" ", StringSplitOptions.RemoveEmptyEntries);
        int A = Int32.Parse(sarr[0]);
        int B = Int32.Parse(sarr[1]);

        Console.Write(A * B);
    }
}

Measured memory_bytes: 27432
#include<bits/stdc++.h>
using namespace std;
int p;
int gcd(int a,int b){
  if(b==0)return a;
  p++;
  return gcd(b,a%b);
}
int main(){
  int a,b;
  while(cin>>a>>b,a){
    p=0;
    if(a<b)swap(a,b);
    cout<<gcd(a,b)<<' ';
    cout<<p<<endl;
  }
}

Measured memory_bytes: 3104
#include <stdio.h>
#include <ctype.h>

int main() {

  char ch[1200];
  int i,n;
  n=0;
  char a[1200];

  while(1) {
    scanf("%c",&a[n]);
    if(a[n] == '\n') {
      break;
    }
    ch[n] = a[n];
    if('A' <= a[n] && a[n] <= 'Z') {
      ch[n] = a[n] + 32;
    } else if(a[n] >= 'a' && a[n] <= 'z') {
      ch[n] = a[n] - 32;

    }
    
    
    n = n +1;
    
  }
  
  for(i=0; i<n ; i++) {
    printf("%c" ,ch[i]);
  }
  printf("\n"); 
  return 0;
  
}



Measured memory_bytes: 2112
#include <stdio.h>
#include <string.h>
#define N 100000
int main() {
	int n,m,i,ans,pena;
	int flag[N][2];
	int question;
	char str[3];
	ans=0;
	pena=0;
	for(i=0;i<N;i++) {
		flag[i][0]=0;
		flag[i][1]=0;
	}
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++) {
		scanf("%d %s",&question,&str);
		if(strcmp(str,"AC")==0) {
			if(flag[question-1][0]==0) {
				flag[question-1][0]=1;
				ans++;
			}
		} else {
			if(flag[question-1][0]==0) {
				flag[question-1][1]++;
			}
		}
	}
	for(i=0;i<N;i++) {
		if(flag[i][0]==1) {
			pena+=flag[i][1];
		}
	}
	printf("%d %d",ans,pena);
	return 0;
}	

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

int main(void) {
  int N, M, X, Y;
  cin >> N >> M >> X >> Y;
  vector<int> x(N);
  vector<int> y(M);
  for (int i = 0; i < N; i++) {
    cin >> x[i];
  }
  for (int i = 0; i < M; i++) {
    cin >> y[i];
  }
  sort(x.begin(), x.end());
  sort(y.begin(), y.end());
  string out = "War";
  for (int i = X + 1; i <= Y; i++) {
    if (x[x.size() - 1] < i && i <= y[0]) {
      out = "No War";
      break;
    }
  }
  cout << out << endl;

  return 0;
}

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

using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    sort(A.begin(), A.end());
    cout << A[n / 2] - A[n / 2 - 1] << endl;
}


Measured memory_bytes: 640
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
using ll = long long;
using namespace std;

const long long MOD = 1000000007;
const ll LINF = 1LL << 50;


int main() {
  int H, W, K;
  cin >> H >> W >> K;

  vector<vector<int>> masu(H ,vector<int>(W));

  REP(h,H){
    REP(w,W){
      char tmp;
      cin >> tmp;
      if (tmp=='.'){
        masu[h][w] = 0;
      } else{
        masu[h][w] = 1;
      }
    }
  }

  vector<vector<int>> masutmp(H ,vector<int>(W));

  int ans = 0;

  for (int bit = 0; bit < (1<<H); ++bit){
    vector<int> S(H);
    REP(h,H) S[h] = 0;
    for (int i = 0; i < H; ++i) if (bit & (1<<i)) S[i] = 1;

    for (int b = 0; b < (1<<W); ++b){
      vector<int> T(W);
      REP(w,W) T[w] = 0;
      for (int i = 0; i < W; ++i) if (b & (1<<i)) T[i] = 1;
      masutmp = masu;

      REP(h,H){
        if (S[h]==0) REP(w,W) masutmp[h][w] = 3;
      }

      REP(w,W){
        if (T[w]==0) REP(h,H) masutmp[h][w] = 3;
      }

      int count = 0;
      REP(h,H){
        REP(w,W){
          if(masutmp[h][w] == 1) count += 1;
        }
      }
      if (count == K) ans += 1;
    }
  }
  cout << ans << endl;
}


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

int main()
{

    int n;
    cin >> n;

    int ac_count = 0;
    int wa_count = 0;
    int tle_count = 0;
    int re_count = 0;

    while (n--)
    {

        string str;
        cin >> str;

        if (str.at(0) == 'A')
        {

            ac_count++;
        }
        else if (str.at(0) == 'W')
        {

            wa_count++;
        }
        else if (str.at(0) == 'T')
        {

            tle_count++;
        }
        else if (str.at(0) == 'R')
        {

            re_count++;
        }
    }

    cout << "AC x " << ac_count << endl;
    cout << "WA x " << wa_count << endl;
    cout << "TLE x " << tle_count << endl;
    cout << "RE x " << re_count << endl;

    return 0;
}

Measured memory_bytes: 3080
N,x,*A=map(int,open(0).read().split());A.sort();s=sum(A)
if s==x:print(N)
else:
    W=[0]
    for a in A[::-1]:W+=[W[-1]+a]
    for i,w in enumerate(W[1:],1):
        if w>=s-x:print(N-i);break

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



int main (int argc, char const* argv[]){
    int n, tmp, a[5];
    
    cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
    
    for(int i=4; i>=0; i--){
        for(int j=0; j<i; j++){
            if(a[j]<a[j+1]){
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
            
            
        }
    }
    for(int i=0; i<5;i++){
        cout << a[i];
        if(i<4) cout<<" ";
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 1164
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty())return out;
    constexpr bool is_vector_v = is_vector<T>::value;
    if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr),out << ((++itr != v.end()) ? "\n" : "");
    else for (auto itr = v.begin(); itr != v.end();)out << (*itr),out << ((++itr != v.end()) ? " " : "");
    return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first; printf("\n"); }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first; printf(" "); put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first; printf("\n"); putn(rest...); }


int main(){
    int n;
    cin >> n;
    unordered_map<string, int> mp;
    set<string> st;
    REP(i,n){
        string s,t;
        cin >> s >> t;
        if(s=="insert"){
            mp[t]=1;
        }else{
            auto itr = mp.find(t);
            if(itr!=mp.end()){
                put("yes");
            }else{
                put("no");
            }
        }
    }
    return 0;
}



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

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

    if(a<=0&&b>=0)
    {
        cout<<"Zero";
        return 0;
    }

    if(a>0&&b>0||(b-a+1)%2==0)
    {
        cout<<"Positive";
        return 0;
    }

    cout<<"Negative";
    return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  int n; cin >> n;
  vector<int> mp(n,0);
  rep(i,n-1){
    int a; cin >> a;
    a--;
    mp[a]++;
  }
  for(auto p: mp){
    cout << p << endl;
  }
  return 0;
}


Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define int long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));

#define dl(line) cerr << "RUN: until " << (line) << "th line." << endl
#define dv(name, value) cerr << (name) << " is " << (value) << endl
#define da(itr, v)  cerr << "["; REPI(itr, v){cerr << *itr << (itr != --v.end() ? ", " : "");} cerr << "]" << endl

int gcd(int vEd, int vIng) {
  if (vEd % vIng == 0) {
    return vIng;
  }

  gcd(vIng, vEd % vIng);
}

signed main(){
  int K; cin >> K;
  int sum = 0;

  FOR(x, 1, K+1){
    FOR(y, 1, K+1){
      FOR(z, 1, K+1){
        sum += gcd(gcd(x, y), z);
      }
    }
  }

  cout << sum << endl;
}


Measured memory_bytes: 3588
use std::io::BufRead;

pub struct StdinReader<R: BufRead> {
    pub buf_reader: R,
    pub buf: String,
}

impl<R: BufRead> StdinReader<R> {
    pub fn new(r: R) -> Self {
        StdinReader {
            buf_reader: r,
            buf: String::with_capacity(10000),
        }
    }
}

#[macro_export]
macro_rules! input {
    ($reader : expr, $t : ty) => { // one variable
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: $t = reader.buf.trim().parse().unwrap();
                reader.buf.clear();
                tmp_var
            },
        }
    };
    ($reader : expr, $t0 : ty, $t1 : ty) => { // 2 tuple
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                (tmp_var[0].clone(), tmp_var[1].clone())
            }
        }
    };
    ($reader : expr, $t0 : ty, $t1 : ty, $t2 : ty) => { // 3 tuple
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                (tmp_var[0].clone(), tmp_var[1].clone(), tmp_var[2].clone())
            }
        }
    };
    ($reader : expr, $t : ty; $size : expr) => { // Vector
        match &mut $reader {
            reader => {
                use std::io::BufRead;
                reader.buf_reader.read_line(&mut reader.buf).unwrap();
                let tmp_var: $t = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();
                reader.buf.clear();
                tmp_var
            }
        }
    };
}

fn main() {
    solve_b();
}

fn solve_b() {
    let handle = std::io::stdin();
    let mut r = StdinReader::new(handle.lock());
    let s = input!(r, String);
    let mut max_len = 0;
    let mut tmp_len = 0;
    for c in s.chars() {
        match c {
            'A' | 'T' | 'G' | 'C' => tmp_len += 1,
            _ => if max_len < tmp_len {
                max_len = tmp_len;
                tmp_len = 0;
            },
        }
    }

    println!("{}", if max_len < tmp_len { tmp_len } else { max_len });
}



Measured memory_bytes: 4352
# -*- coding: utf-8 -*-
import sys
import math

#区間加算，1点取得
class SegTree2:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 更新[l,r)にxを加算
    def update(self,l,r,x):
        if r<=l:
            return self.ide_ele
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
         
        while r-l>1:
            if l&1 == 0:
                self.seg[l] = self.segfunc(self.seg[l],x)       
            if r&1 == 1:
                self.seg[r] = self.segfunc(self.seg[r],x)
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            self.seg[r] = self.segfunc(self.seg[r],x)
        else:
            self.seg[l] = self.segfunc(self.seg[l],x)
            self.seg[r] = self.segfunc(self.seg[r],x)
  
    # k番目の要素に加算されている合計値を計算
    def query(self,k):    
        k += self.num-1 #葉のノードのインデックス
        ret = self.seg[k]
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            ret = self.segfunc(ret, self.seg[k])
        return ret
    
            
def segfunc(x,y):
    return x|y



N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()

#%%
ans = 0
damage = 0
seg = SegTree2(N,[0]*N,lambda x,y:x+y,0)

right = 1
for i in range(N):
    d = XH[i][1] - seg.query(i)
    if d<=0:
        continue
    else:
        c = math.ceil(d/A)
        ans += c
        
        while right<N and XH[right][0]<=XH[i][0]+2*D :
            right += 1
        
        seg.update(i,right,c*A)

print(ans)
            
        
        


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

int main(){
  int i,j,cnt=0;
  int n;
  cin>>n;
  int p[n+1];
  for(i=1;i<=n;i++)cin>>p[i];
  int a[n+1];
  for(i=0;i<=n;i++)a[i]=0;
  for(i=1;i<=n;i++){
    if(p[i]==i)a[cnt]++;
    else cnt++;
  }
  int sum=0;
  for(i=0;i<=n;i++){
    if(a[i]!=0)sum+=(a[i]+1)/2;
  }
  cout<<sum;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
int main()
{
	/*int n, r;
	cin >> n >> r;
	if (n >= 10)
		cout << r;
	else
		cout << r + (10 - n) * 100;*/

	//long long n, k = 0;
	//cin >> n >> k;
	//int ans = 1;
	//while (n >= k)
	//{
	//	n /= k;
	//	ans += 1;
	//}
	//cout << ans;

	int n;
	cin >> n;
	int dog[101];
	float key = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> dog[i];
		key += dog[i];
	}
	key =key/n;
	int point = key;
	if (key - point > 0.5)point++;
	long long ans=0;
	for (int i = 0; i < n; i++)
	{
		ans += pow(dog[i] - point, 2);
	}
	cout << ans;
}


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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


/*************************************************************************/
ll ans=0;
int main()
{
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    VVI tab(n, VI(n));
    FOR(i,0,n-1) FOR(j,0,n-1)
    {
        cin >> tab[i][j];
        ans+=tab[i][j];
    }

    FOR(k,0,n-1) FOR(i,0,n-1) FOR(j,0,n-1)
    {
        if (tab[i][j] > tab[i][k] + tab[k][j])
        {
            cout << -1;
            return 0;
        }
    }

    ll total = 0;
    FOR(k,0,n-1) FOR(i,0,n-1)
    {
        bool found = false;

        FOR(j,0,n-1) if (j != i && j != k && tab[i][k] == tab[i][j] + tab[j][k])
        {
            found = true;
        }

        if (found)
        {
            total += tab[i][k];
        }
    }

    cout << ans/2-total / 2;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
  int i,j,k;
  string s;
  string t;
  cin >> s >> t;
  int n = s.size();
  int m = t.size();
  
  vector<int> a(n, 0);
  for(i = 0; i < n;i++){
    a.at(i) = s.at(i);
  }
  vector<int> b(m, 1);
  for(i = 0; i < m;i++){
    b.at(i) = t.at(i);
  }
  
  int wa = 0;
  int ans = 0;
  
  for(i = 0; i <= n-m;i++){
    for(j = 0; j < m;j++){
      
        if(a.at(i+j) == b.at(j)){
            wa++;
            
          }
     
        
    }
    ans = max(wa,ans);
    wa = 0;

    
  }
  
  
  cout << m-ans;
      

  
  
    
}


Measured memory_bytes: 3520