akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
priority_queue<ll> que;
V g[ohara];

//-------------------------↓↓↓↓↓↓------------------------

//------ 自分を天才だと信じる ------

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

    cin>>n>>m;
    rep(i,n){
        cin>>a>>b;
        g[a].push_back(b);
    }
    rrep(i,1,m+1){
        //i以下で最大はいくつか
        rep(j,Size(g[i])){
            que.push(g[i][j]);
        }
        if(Size(que)!=0){
            ans+=que.top();
            que.pop();
        }
    }
    Cout(ans);
    return 0;
}


Measured memory_bytes: 26752
n = int(input())
a = sorted([int(x) for x in input().split()])
d = {}
ans = 0

for i in range(len(a)):
    tmp = a[i]
    if tmp not in d:
        d[tmp] = 0
    d[tmp] += 1

for kk in d.keys():
    if kk > d[kk]:
        buf = d[kk]
    elif kk < d[kk]:
        buf = d[kk] - kk
    else:
        buf = 0
    ans += buf

print(ans)


Measured memory_bytes: 17780
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9+7;

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  cout << a[0]<<b[0] << c[0] << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, N) for(int i=0, i##_len=(N); i<i##_len; i++)
#define reps(i, N) for(int i=1, i##_len=(N); i<=i##_len; i++)
#define rrep(i, N) for(int i=(N)-1; i>=0; i--)
#define rreps(i, N) for(int i=(N); i>=1; i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
template<class T>bool amax(T &a, const T &b) { if (a<b) {a=b; return true;} return false; }
template<class T>bool amin(T &a, const T &b) { if (a>b) {a=b; return true;} return false; }
using ll = long long;
using namespace std;
constexpr int inf = 1e9;
constexpr int mod = 1e9+7;

ll n;
ll d[100010];

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

    cin >> n;
    rep(i, n) cin >> d[i];
    sort(d, d+n);
    ll half = n/2;
    ll ans = d[half] - d[half-1];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
import copy
n=int(input())
s=input()
k=int(input())

lsts=list(s)
a=k-1
chara=lsts[a]

ss=copy.copy(s)
lstss=list(ss)

for i in range(n):
    if lstss[i]!=chara:
        lsts[i]="*"

ans=""
for i in range(n):
    ans+=lsts[i]

print(ans)

Measured memory_bytes: 3572
#include <stdio.h>

void Merge(int*, int, int, int);
void MergeSort(int*, int, int);

int count=0;

int main(){
  int i, n, A[500000];

  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%d",&A[i]);
  }
  MergeSort(A,0,n);
  for(i=0;i<n-1;i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[n-1]);
  printf("%d\n",count);
  
  return 0;
}

void Merge(int *A, int left, int mid, int right){
  int i, j, k, n1, n2;
  int L[250002], R[250002];
  n1 = mid - left;
  n2 = right - mid;
  for(i=0;i<n1;i++)
    L[i] = A[left+i];
  for(i=0;i<n2;i++)
    R[i] = A[mid+i];
  L[n1]=2000000000;
  R[n2]=2000000000;
  i=0;
  j=0;
  for(k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      count++;
    }
    else{
      A[k]=R[j];
      j++;
      count++;
    }
  }
}

void MergeSort(int *A, int left, int right){
  int mid;
  if (left+1<right){
    mid = (left + right)/2;
    MergeSort(A, left, mid);
    MergeSort(A, mid, right);
    Merge(A, left, mid, right);
  }
}

Measured memory_bytes: 4504
/*
  AOJ #3017
  title:Piano
  @kankichi573
 */
#include <stdio.h>

#define max(x,y) (((x)>(y))?(x):(y))

int n,p,c,dir,pdir,ans,runlen;

int main()
{
  int i;

  scanf("%d",&n);
  
  
  scanf("%d",&p);
  ans=1;

  pdir=0;runlen=1;
  for(i=1;i<n;i++)
    {
      scanf("%d",&c);
      if(i!=0)
	{
	  if(c>p)
	    dir=1;
	  else if(c<p)
	    dir=-1;
	  else
	    continue;
	   
	  if(dir==pdir)
	    runlen++;
	  else
	    runlen=2;
      
	  ans=max(ans,runlen);

      //printf("[%c]prev=%d,current=%d,runlen=%d\n",(dir==1)?'+':'-',p,c,runlen);
	}
      p=c;
      pdir=dir;
    }
  printf("%d\n",ans) ;
  return(0);
}



Measured memory_bytes: 2104
n=int(input())
a=list(map(int,input().split()))
cnt=0
r=0
ga=g=a[0]
xa=x=a[0]
for l in range(n):
    while r<n-1:
        g=ga+a[r+1]
        x=xa|a[r+1]
        if g==x:
            ga=g
            xa=x
            r+=1
        else:
            break
        if r==n-1:
            break
    cnt+=r-l+1
    ga-=a[l]
    xa-=a[l]
print(cnt)

Measured memory_bytes: 25684
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;
//tuple
//cout << get<0>( x ) << " " << get<1>( x ) << " " << get<2>( x ) << endl;
//tie(a, b, c) = t;


//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));




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

	int N, C;
	cin >> N >> C;
	VI X(N), V(N);
	REP(i, N)cin >> X[i] >> V[i];

	int ma[100010][2] = { 0 };
	int maa[100010][2] = { 0 };

	REP(i, N) {
		if(i==0)ma[i][0]+= V[i] - X[i];
		else ma[i][0] += V[i] - (X[i] - X[i - 1]);

		if (i != N - 1)ma[i + 1][0] = ma[i][0];
		//cout << ma[i][0] << endl;
	}
	int j = N - 1;
	REP(i, N) {
		if (i == 0)maa[i][0] += V[j] - (C - X[j]);
		else maa[i][0] += V[j] - (X[j+1] - X[j]);
		if (i != N - 1)maa[i + 1][0] = maa[i][0];
		//cout << maa[i][0] << endl;
		j--;
	}
	ma[0][1] = X[0];
	maa[0][1] = C - X[N - 1];
	j = N - 2;
//	cout << ma[0][0] << " " << ma[0][1] << " " << maa[0][0] << " " << maa[0][1] << endl;
	FOR(i, 1, N) {
		//ma[i] = max(ma[i], ma[i - 1]);
		//maa[i] = max(maa[i], maa[i - 1]);
		ma[i][0] = max(ma[i][0], ma[i - 1][0]);
		if (ma[i][0] > ma[i - 1][0]) {
			//ma[i][0] = max(ma[i][0], ma[i - 1][0]);
			ma[i][1] = X[i];
		}
		else ma[i][1] = ma[i - 1][1];
		maa[i][0] = max(maa[i][0], maa[i - 1][0]);
		if (maa[i][0] > maa[i - 1][0]) {
			//maa[i][0] = max(maa[i][0], maa[i - 1][0]);
			maa[i][1] = C-X[j];
		}
		else maa[i][1] = maa[i - 1][1];

		//cout << ma[i][0] << " " << ma[i][1] << " " << maa[i][0] << " " << maa[i][1] << endl;

		j--;
	}
	int ans = 0;
	REP(i, N-1) {
		int cnt = ma[i][0] + maa[N - 2 - i][0];
		cnt = max(cnt - ma[i][1], cnt - maa[N - 2 - i][1]);
		ans = max(ans, cnt);
		//cout << ans << endl;
	}
	ans = max(ans, ma[N - 1][0]);
	ans = max(ans, maa[N - 1][0]);
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 4992
#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<pair<long long,int>> A;
  for(int i = 0; i < N; ++i){
    int a;
    cin >> a;
    A.emplace_back(a,i);
  }
  sort(A.rbegin(), A.rend());
  vector<long long> dp(N+1,0);
  for(int i = 0; i < N; ++i){
    auto [a,idx] = A[i];
    vector<long long> dp_(N+1,0);
    for(int j = 0; j <= i; ++j){
      dp_[j+1] = max(dp_[j+1],dp[j]+a*abs(idx-j));
      dp_[j] = max(dp_[j],dp[j]+a*abs(N-1-i+j-idx));
    }
    swap(dp,dp_);
  }
  cout << (*max_element(dp.begin(), dp.end())) << endl;
}


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

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

    if(a == b) cout << "Draw" << endl;
    else if(a == 1) cout << "Alice" << endl;
    else if(b == 1) cout << "Bob" << endl;
    else if(b < a) cout << "Alice" << endl;
    else cout << "Bob" << endl;
    
    return 0;
}

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

using namespace std;

const int mod = 998244353;

int n, S;
int a[N], f[N];

int main() {
	scanf("%d %d", &n, &S);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		if(a[i] > S) continue;
		else if(a[i] == S) {
			ans = (ans + 1LL * i * (n - i + 1)) % mod;
		} else {
			ans = (ans + 1LL * f[S - a[i]] * (n - i + 1)) % mod;
			for(int j = S; j > a[i]; --j)
				(f[j] += f[j - a[i]]) %= mod;
			f[a[i]] = (f[a[i]] + i) % mod;
		}
	}
	
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
	int a,b;cin>>a>>b;
    int g=__gcd(a,b);int cnt=0;
    for(int i=2;i*i<=g;i++){
        if(g%i==0){
            while(g%i==0){
                g/=i;
            }
            cnt++;
        }
    }
    if(g>1) cnt++;
    cout<<cnt+1;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);	 
	int T=1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


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

int main()
{
    int A;
    int B;
    int C;
    cin >> A;
    cin >> B;
    cin >> C;
    if(A == B)
        cout << C;
    if(A==C)
        cout << B;
    if(B==C)
        cout << A;
    

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>

using namespace std;

int main()
{
	int N, D, X;
	cin >> N >> D >> X;

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

	int ans = X;
	for (int i = 0; i < N; i++)
	{
		int j = 0;
		while (j * A[i] + 1 <= D)
		{
			ans++;
			j++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/
*/

#include <bits/stdc++.h>
using namespace std;

// utility of stdin,stdout
#define OUT cout << 
#define BR << endl
#define RET return 0
#define TLong long long

int main(int argc, char const *argv[]){
	int n,k;
	int d = 0;

	cin >> n >> k;
	std::vector<int> x(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> x.at(i);
		d += (abs(k - x.at(i)) < abs(x.at(i)) ? (2 * abs(k - x.at(i))) : (2 * abs(x.at(i))));
	}
	OUT(d) BR;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool even(string s){
	int n=s.length()/2;
	for(int i=0;i<n;i++){
		if(s[i]!=s[i+n])return false;
	}
	return true;
}
int main (){
	string s;
	cin>>s;
	s.erase(s.begin()+s.length()-1,s.end());
	while(!even(s)){
		s.erase(s.begin()+s.length()-1,s.end());
	}
	cout<<s.length()-1<<endl;
	return 0;
}

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

int main(){
  int n,c,count=1;
  cin>>n;
  vector<int> vec(n);
  for(int i=0;i<n;i++){
    cin>>vec.at(i);
  }
  for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
      if(vec.at(i)<vec.at(j)){
        c=vec.at(i);
        vec.at(i)=vec.at(j);
        vec.at(j)=c;
      }
    }
  }
  for(int i=0;i<n-1;i++){
    if(vec.at(i+1)<vec.at(i)){
      count++;
    }
  }
  cout<<count;
}


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

long long int gcd(long long int x, long long int y)
{
	if (y == 0) { return x; }
	return gcd(y, x % y);
}

int main(void)
{
	int n;
	cin >> n;
	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		p.at(i) = make_pair(a, i + 1);
	}
	sort(p.begin(), p.end());
	for (int i = 0; i < n - 1; i++)
	{
		cout << p.at(i).second << " ";
	}
	cout << p.at(n - 1).second << endl;
	return 0;
}


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

int main()
{
	int A,B;
	cin >> A >> B;
	int ans = 0;
	for (int i = A; i <= B; ++i)
	{
		bool flag = true;
		if (i / 10000 != i % 10) flag = false;
		if ((i / 1000) % 10 != (i % 100) / 10) flag = false;
		if (flag) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
fn main() {
    let s = input();
    let h = s / 3600;
    let m = (s - h * 3600) / 60;
    let s = s % 60;
    println!("{}:{}:{}", h, m, s);
}


fn input() -> u32 {
    let mut buf = String::new();
    let stdin = std::io::stdin();
    stdin.read_line(&mut buf).unwrap();
    return buf.trim().parse().unwrap();
}



Measured memory_bytes: 5028
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

#define rep(i, o) for (ll i = 0; i < (o);i++)
#define rep_s(i, o) for (int i = 1; i < (o);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
#define NUM 1e5

typedef long long ll;
typedef unsigned long long ull;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }


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

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

int main() {
    ll n;
    cin >> n;

    vector<ll> p(n);
    rep(i, n) {
        cin >> p[i];
    }

    ll count = 0; bool both = false;
    rep(i, n-1) {
        if (p[i] == i+1) 
        {
            swap(p[i], p[i+1]);
            count++;
        }
    }
    if (p[n-1] == n) count++;
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
    int i,n,a;
    long long int h, sum = 0;
    scanf("%lld %d", &h,&n);
    for(i = 1;i<=n;i++)
    {
        scanf("%d", &a);
        sum = sum+a;
    }
    if(sum >= h)
        printf("Yes\n");
    else
        printf("No\n");
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inf 9223372036854775807
#define mini 9223372036854775807
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<double, null_type,less<double>, rb_tree_tag,tree_order_statistics_node_update>
pair<ll,ll>s4[4]={{-1,0},{1,0},{0,-1},{0,1}};
pair<ll,ll>s8[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};
ll power(ll a,ll b)
{
	if(b==0)
		return 1;
	ll c=power(a,b/2);
	if(b%2==0)
		return ((c%mod)*(c%mod))%mod;
	else
		return ((((c%mod)*(c%mod))%mod)*a)%mod;
}
ll n;
ll a[200005];
ll dp[200005];
ll func(ll i)
{
	if(dp[i]!=-1)
		return dp[i];
	ll ans1=inf;
	ll ans2=inf;
	if(i==n-1)
		return 0;
	if(i+2<n)
		ans1=abs(a[i+2]-a[i])+func(i+2);
	if(i+1<n)
		ans2=abs(a[i+1]-a[i])+func(i+1);
	dp[i]=min(ans1,ans2);
	return dp[i];
}
int main()
{
	boost
	cin>>n;
	ll i;
	for(i=0; i<200005; i++)
		dp[i]=-1;
	for(i=0; i<n; i++)
		cin>>a[i];
	ll ans=func(0);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4224
#include <stdio.h>

int main() {
    int n, k;
    long long array[200001] = {0};
    long long thisTerm = 1;
    long long lastTerm = 1;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &array[i]);
        thisTerm *= array[i];
        if (i > k) {
            if (array[i] > array[i - k]) {
                printf("Yes\n");
            }
            else {
                printf("No\n");
            }
            /*printf("%lld ", thisTerm);
            lastTerm = thisTerm * array[i - k] / array[i];
            printf("%lld ", lastTerm);
            if (thisTerm > lastTerm) {
                
            }
            */
        }
    }
    return 0;
}

Measured memory_bytes: 4732
#include<bits/stdc++.h>
#define succeed return 0*printf("Possible\n")
#define fail return 0*printf("Impossible\n")
using namespace std;
const int N=110;
int n,a[N],num[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[a[i]]++;
	sort(a+1,a+n+1);
	if(n==1) succeed;
	for(int i=a[n];i>=(a[n]+1)/2+1;i--)
	 if(num[i]<2) fail;
	if(a[n]&1)
	{
		if(num[(a[n]+1)/2]!=2) fail;
	}
	else if(num[a[n]/2]!=1) fail;
	succeed;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define mod 1000000007
#define N 200002

ll n,col[N],sub[N],cnt[N],ans[N],cur;
vector <ll> adj[N];

void dfs(ll u, ll p){
    sub[u]++;
    ll tmp=cnt[col[u]];
    for(auto v:adj[u]){
        if(v!=p){
            ll a=cur-cnt[col[u]];
            dfs(v,u);
            sub[u]+=sub[v];
            ll b=cur-cnt[col[u]];
            debug()<<imie(u)imie(v)imie(b-a);
            ans[col[u]]-=(b-a)*(b-a+1)/2;
        }
    }
    cnt[col[u]]=tmp+sub[u];
    cur++;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    cin>>n;
    for(int i=1;i<=n;i++) cin>>col[i];
    ll tot=n*(n+1)/2;
    for(int i=1;i<=n;i++) ans[i]=tot;
    for(int i=0;i<n-1;i++){
        ll u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++){
        ans[i]-=(n-cnt[i])*(n-cnt[i]+1)/2;
        cout<<ans[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 39428
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var ss = Console.ReadLine().Split();
            var A = long.Parse(ss[0]);
            var B = long.Parse(ss[1]);
            var C = long.Parse(ss[2]);
            var D = long.Parse(ss[3]);
            var c = C;
            var d = D;

            var x = c * d;

            if (c < d)
            {
                var tmp = c;
                c = d;
                d = tmp;
            }

            var r = c % d;
            while (r != 0)
            {
                c = d;
                d = r;
                r = c % d;
            }

            var CD = x / d;

            var countB = (B / C) + (B / D) - (B / CD);
            var countA = ((A - 1) / C) + ((A - 1) / D) - ((A - 1) / CD);

            Console.WriteLine((B - A + 1) - (countB - countA));
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
using pii = pair<int, int>;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);

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

  int min = *min_element(a.begin(), a.end());

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

  ll ans = a[0];

  for (int i = 0; i < n; i++) {
    ans = gcd(ans, a[i]);
  }

  cout << ans << endl;
}

Measured memory_bytes: 3740
/* Manish Pant - insider_pants */

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.h"
#endif

#define F first
#define S second
#define endl "\n"
#define pb push_back
typedef long long ll;
typedef long double ldob;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    fast();
    int n, m; cin >> n >> m;
    int k; cin >> k;
    vector<vector<int>> v(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            char a; cin >> a;
            if(a == '#')
                v[i][j] = 1;
        }

    int ans = 0;
    for(int i = 0; i < (2 << (n - 1)); i++)
    {
        for(int j = 0; j < (2 << (m - 1)); j++)
        {
            vector<vector<int>> t;
            t = v;

            for(int x = 0; x < n; x++)
                if((i >> x) & 1)
                    for(int y = 0; y < m; y++)
                        t[x][y] = 2;

            for(int y = 0; y < m; y++)
                if((j >> y) & 1)
                    for(int x = 0; x < n; x++)
                        t[x][y] = 2;
            int c = 0;
            for(int x = 0; x < n; x++)
                for(int y = 0; y < m; y++)
                    if(t[x][y] == 1)
                        c++;

            if(c == k)
                ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <decimal/decimal>
using namespace std;
using namespace __gnu_pbds;

#define rep(i, s, t) for (int i = s; i < int(t); ++i)

#define sc	scanf
#define pr	printf
#define ff	first
#define ss	second
#define mp	make_pair
#define pb	push_back
#define eb	emplace_back
#define range(c)	c.begin(), c.end()
#define lowbit(x)	((x) & -(x))
#define pop_count	__builtin_popcount
#define pop_count_64	__builtin_popcountll
#define tail_count	__builtin_ctz
#define tail_count_64	__builtin_ctzll
#define lead_count	__builtin_clz
#define lead_count_64	__builtin_clzll

#define TEMP template<typename
#define CONST(type) constexpr type const

TEMP... Ts> struct is_con { static CONST(bool) value = false; };
TEMP... Ts> struct is_con<vector<Ts...>> { static CONST(bool) value = true; };
TEMP... Ts> struct is_con<list<Ts...>> { static CONST(bool) value = true; };
TEMP... Ts> struct is_con<deque<Ts...>> { static CONST(bool) value = true; };
TEMP... Ts> struct is_con<set<Ts...>> { static CONST(bool) value = true; };
TEMP... Ts> struct is_con<unordered_set<Ts...>> { static CONST(bool) value = true; };
TEMP... Ts> struct is_con<map<Ts...>> { static CONST(bool) value = true; };
TEMP... Ts> struct is_con<unordered_map<Ts...>> { static CONST(bool) value = true; };

TEMP T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2> const& p) { return os << "<" << p.ff << "," << p.ss << ">"; }
TEMP T> typename enable_if<is_con<T>::value, ostream>::type& operator<<(ostream& os, T const& c) {
	os << "{";
	bool first = true;
	for (auto const& x : c) {
		if (first) first = false;
		else os << ",";
		os << " " << x;
	}
	return os << " }";
}

TEMP T, typename... Ts> void dbg(T h, Ts... t) { cerr << " " << h; dbg<Ts...>(t...); }
template<> void dbg<int>(int x) { cerr << endl; }

#ifdef LOCAL
#define debug(...) cerr << "[ "#__VA_ARGS__" ] :", dbg(__VA_ARGS__, 0)
#else
#define debug(...) 0
#endif

TEMP T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
TEMP T> using ordered_set = ordered_map<T, null_type>;

typedef long long i64;
typedef decimal::decimal128 i99;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef float f32;
typedef double f64;
typedef long double f80;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;

TEMP T> T& minn(T& lhs, T const& rhs) { return lhs = min(lhs, rhs); }
TEMP T> T& maxx(T& lhs, T const& rhs) { return lhs = max(lhs, rhs); }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin >> s;
	for (auto& c : s) {
		if (c == '?') {
			c = 'D';
		}
	}
	cout << s << endl;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	vector<string>s;
	for(ll i=0;i<n;i++){
		string t;
		cin>>t;
		s.push_back(t);
	}
	ll ab,b,a,ba;
	ab=b=a=ba=0;
	for(ll i=0;i<n;i++){
		string now=s[i];
		for(ll j=1;j<now.size();j++){
			if(now[j-1]=='A'&&now[j]=='B'){
				ab++;
			}
		}
		if(now[0]=='B'&&now[now.size()-1]=='A'){
			ba++;
		}
		else if(now[now.size()-1]=='A'){
			a++;
		}
		else if(now[0]=='B'){
			b++;
		}
	}
	ll ans=ab;
	if(ba>0){
		ans+=ba-1;
		if(a>0){
			ans++;
			a--;
		}
		if(b>0){
			ans++;
			b--;
		}
		ans+=min(a,b);
	}
	else{
		if(a>0&&b>0){
			ans+=min(a,b);
		}
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>

struct Sweets{
	int i, p, q, r;
};

int main(){
	int n;
	while(std::cin >> n, n){
		std::vector<Sweets> v;
		for(;n--;){
			Sweets s;
			std::cin >> s.i >> s.p >> s.q >> s.r;
			v.push_back(s);
		}

		int P, Q, R, C;
		std::cin >> P >> Q >> R >> C;

		for(int i=0;i<v.size();i++){
			Sweets s = v[i];
			int cal = s.p * 4 + s.q * 9 + s.r * 4;
			if(s.p <= P && s.q <= Q && s.r <= R && cal <= C){

			}else{
				v.erase(v.begin() + i--);
			}
		}

		if(v.empty()){
			std::cout << "NA" << std::endl;
		}else{
			for(int i=0;i<v.size();i++){
				std::cout << v[i].i << std::endl;
			}
		}
	}
}

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

#define ll long long
const int MOD = 1e9+7;
ll mod(ll x) {
	return (x%MOD + MOD) %MOD;
}
ll mul(ll a,ll b) {
	return mod(mod(a) * mod(b));
}

int main() {
	int x,n;
	cin >> x >> n;
	unordered_map<int,int> hash;
	for (int i = 0; i < n; ++i)
	{
		/* code */
		int tmp;
		cin >> tmp;
		hash[tmp]++;
	}
	int left = x;
	int right = x;
	while(left >= 0) {
		if(hash.find(left) == hash.end())
			break;
		left--;
	}
	while(right <= 101) {
		if(hash.find(right) == hash.end())
			break;
		right++;
	}

	int result = ((x-left) > (right-x))?right:left;
	cout << result << endl;
}

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

import heapq


def dijkstra_heap(s, edge):
    # 始点sから各頂点への最短距離
    d = [10 ** 20] * n
    used = [True] * n  # True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a, b in edge[s]:
        heapq.heappush(edgelist, a * (10 ** 6) + b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        # まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge % (10 ** 6)]:
            continue
        v = minedge % (10 ** 6)
        d[v] = minedge // (10 ** 6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, (e[0] + d[v]) * (10 ** 6) + e[1])
    return d


n = int(readline())
edge = [[] for i in range(n)]
for i in range(n - 1):
    a, b, c = map(int, readline().split())
    edge[a - 1].append([c, b - 1])
    edge[b - 1].append([c, a - 1])
q, k = map(int, readline().split())
check = dijkstra_heap(k - 1, edge)
for i in range(q):
    x, y = map(int, readline().split())
    print(check[x - 1] + check[y - 1])


Measured memory_bytes: 49784
#[allow(unused_imports)] use proconio::{input, marker::{Bytes, Chars, Usize1, Isize1}};
#[allow(unused_imports)] use std::cmp::{min, max};
#[allow(unused_imports)] use superslice::Ext as _;

#[proconio::fastout]
fn main() {
	input! {
		n: usize,
		cnum: usize,
		d: [[usize; cnum]; cnum],
		c: [[Usize1; n]; n],
	}

	let inf = 99999999999999usize;

	// 各マスを、(i+j)%3 = 0 or 1 or 2 の3つのグループに分割する。 
	// 各グループについて、C通りの色を塗りつぶしたときの違和感の和を前処理しておき, 
	// C^3通りの組み合わせを検証して最小値を出力する

	// 前処理
	let mut cost = vec![vec![0usize; cnum]; 3];
	for color in 0..cnum {
		for i in 0..n {
			for j in 0..n {
				cost[(i+j)%3][color] += d[c[i][j]][color];
			}
		}
	}

	// 解を求める
	let mut ans = inf;
	for c0 in 0..cnum {
		for c1 in 0..cnum {
			if c0 == c1 {
				continue;
			}
			for c2 in 0..cnum {
				if c2 == c0 || c2 == c1 {
					continue;
				}
				let mut tmp = 0usize;
				tmp += cost[0][c0];
				tmp += cost[1][c1];
				tmp += cost[2][c2];
				ans = min(ans, tmp);
			}
		}
	}

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


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

int main() {
	int n, m, num = 0;
	cin >> n >> m;
	vector<int> x(m),g(m - 1);
	for (int i = 0; i < m; i++)
		cin >> x[i];
	if (n >= m) {
		cout << 0 << endl;
		return 0;
	}
	sort(x.begin(), x.end());
	for (int i = 0; i < m - 1; i++)
		g.at(i) = x[i + 1] - x[i];
	sort(g.begin(), g.end());
	for (int i = 0; i < m - n; i++)
		num += g[i];
	cout << num << endl;
}


Measured memory_bytes: 1024
import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)


Measured memory_bytes: 21440
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut ans = 0;
    if n > 0 {
        ans += n * (n - 1) / 2;
    }
    if m > 0 {
        ans += m * (m - 1) / 2;
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

monster = 0

for i in range(N):

    if A[i] >= B[i]:
        monster += B[i]
        A[i] -= B[i]
        B[i] = 0

    else:
        monster += A[i]
        B[i] -= A[i]
        A[i] = 0

        if A[i + 1] >= B[i]:
            A[i + 1] -= B[i]
            monster += B[i]
            B[i] = 0

        else:
            monster += A[i + 1]
            B[i] -= A[i + 1]
            A[i + 1] = 0


# print(A)
# print(B)
print(monster)

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

const int N=2e5+5;
int ar[N];

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

    int p, n; cin>>p>>n;
    int maxd = -1;
    for(int i=1; i<=n; i++){
        cin>>ar[i];
        if(i>1) maxd = max(maxd, ar[i]-ar[i-1]);
    }
    maxd = max(maxd, p-ar[n]+ar[1]);
    cout<<p-maxd<<'\n';
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#define rep(i, n) for(ll i=0; i<n; i++)
using namespace std;
typedef long long ll;

const ll INF = ll(1e18)+1;

int main(){
    ll n, k; cin >> n >> k;
    ll tmp;
    vector<ll> a;
    rep(i, n){ cin >> tmp; a.push_back(tmp);}
    sort(a.begin(), a.end());
    ll left = -INF;
    ll right = INF;
    while(left+1 < right){
        //cout << "left="<<left<<" ,right="<< right<<endl;
        ll mean = (left+right)/2;
        //cout << "mean " << mean << endl;
        bool ok = [&]{
            ll c = 0;
            rep(i, n){
                //cout <<"  i="<<i << endl;
                ll l=-1, r=n;
                ll m;
                if(a[i] < 0){
                    while(l+1 < r){
                        //cout << "l="<<l<<" ,r="<< r<<endl;
                        m = (l+r)/2; 
                        //cout << "    m " << m<< endl; 
                        if(a[i]*a[m] < mean) r = m; else l = m;
                    }
                    c += n-r;
                }else{
                    while(l+1 < r){
                        m = (l+r)/2;  
                        if(a[i]*a[m] < mean) l = m; else r = m;
                    }
                    c += r;
                }
                if(a[i]*a[i] < mean) c--;
            }
            c /= 2;
            return c < k;
        }();
        //cout << "count "<< count << endl <<endl;
        if(ok) left = mean; else right = mean;
    }
    cout << left << endl;
    return 0;
}

Measured memory_bytes: 5348
import java.util.*;

public class Main{
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int count = 0;
        int cnum = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else {
                count--;
                if (count < 0) {
                    cnum++;
                    count = 0;
                }
            }
        }
        
        for (int i = 0; i < cnum; i++) {
            System.out.print("(");
        }    
        System.out.print(s);
        for (int i = 0; i < count; i++) {
            System.out.print(")");
        }    
    }
}


Measured memory_bytes: 23764
Imports System
Module ABC101B
	Sub Main()
		Dim n,t as Integer
		n = Integer.Parse(Console.ReadLine())
		t = n
		Dim sn as Integer = 0
		While t > 0
			sn += (t Mod 10)
			t  \= 10
		End While
		
		If n Mod sn = 0
			Console.WriteLine("Yes")
		Else
			Console.WriteLine("No")
		End If
		
	End Sub
End Module


Measured memory_bytes: 13140
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	static int n;
	static int a[100010];
	scanf("%d",&n);
	rep1(i,n)scanf("%d",&a[i]);
	
	static int dp[100010][2] = {};
	dp[1][0] = 1;
	dp[1][1] = 1;
	for(int i = 2 ; i <= n ; i ++){
		dp[i][0] = dp[i][1] = min( dp[i-1][0] , dp[i-1][1] ) + 1;
		if(a[i] >= a[i-1])dp[i][0] = min( dp[i][0] , dp[i-1][0] );
		if(a[i] <= a[i-1])dp[i][1] = min( dp[i][1] , dp[i-1][1] );
	}
	cout << min( dp[n][0] , dp[n][1] ) << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

#define rep(i, n) for (int i=0; i<int(n); i++)
#define all(c) (c).begin(), (c).end()

#define MAX_N 1010
const int MOD = 10007;

int N;
int seki[MAX_N];
int dp[MAX_N][8];


int main() {
  cin >> N;
  rep(i, N) {
    char c;
    cin >> c;
    seki[i] = (c=='J'?1:c=='O'?2:4);
  }

  rep(s, 8) {
    if ((s & 1) == 1 && (s & seki[0]) != 0) dp[0][s] = 1;
  }

  for (int i=0; i<N; i++) {
    rep(s1, 8) {
      //if ((s1 & seki[i]) == 0) continue; // ??¬????????????????????´???
      if (dp[i][s1] <= 0) continue;
      rep(s2, 8) {
        // ??????????????????????????????
        if ((s1 & s2) != 0 && (s2 & seki[i+1])!=0) {
          dp[i+1][s2] += dp[i][s1];
          dp[i+1][s2] %= MOD;
        }
      }
    }
  }

  int ans = 0;
  rep(i, 8) ans = (ans + dp[N-1][i]) % MOD;
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 3140
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

using namespace std;

class CShoppingStreet {
public:
void solve(std::istream& cin, std::ostream& cout) {
    int n;
    cin >> n;
    vector<vector<int>> F(n, vector<int>(10));
    for (auto &f: F) for (auto &g: f) cin >> g;
    vector<vector<int>> P(n, vector<int>(11));
    for (auto &p: P) for (auto &q: p) cin >> q;

    int ans = -int(1e9);

    for (int bits = 1; bits < 1024; bits++){
        int S = 0;
        for (int i = 0; i < n; i++){
            int cnt = 0;
            for (int j = 0; j < 11; j++)
                cnt += F[i][j] & (bits >> j);
            S += P[i][cnt];
        }
        ans = max(ans, S);
    }

    cout << ans << endl;
}
};

int main() {
	CShoppingStreet solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		int hp = scan.nextInt();
		int count = scan.nextInt();
		
		int sum = 0;
		for (int i=0; i<count; i++) {
			sum += scan.nextInt();
		}
		
		if (sum >= hp) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 47980
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mp  make_pair
#define pb  push_back
#define endl "\n"
#define rep(i,a,n) for(int i=a;i<n;i++)
const int mod = 1e9 + 7;
void solve() {
	string s;
	cin >> s;
	int m = 0;
	rep(i, 0, 3) {
		int c = 0;
		while (s[i] == 'R') {
			c++;
			i++;
		}
		m = max(c, m);
	}
	cout << m << endl;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	int t;
	t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define IOS cin.tie(0); ios::sync_with_stdio(false)
const int INF = 1e9;
using namespace std;

main() {
    int N; cin >> N;
    ll minus=0; vector<ll> plus;
    ll ans=0;
    int A[N],B[N];
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    rep(i,N) {
        if(A[i]-B[i]>=0){
            plus.push_back(A[i]-B[i]);
        }
        else {
            minus+=B[i]-A[i];
            ans++;
        }
    }
    sort(plus.begin(),plus.end(),greater<int>());
    for(auto a:plus){
        if(minus<=0) break;
        ans++;
        minus-=a;
    }
    if(minus>0) cout << -1 << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 2808
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
        s: [Chars;n],
    }

    let mut name: Vec<usize> = vec![0;5];
    for i in s {
        match i[0] {
            'M' => name[0]+=1,
            'A' => name[1]+=1,
            'R' => name[2]+=1,
            'C' => name[3]+=1,
            'H' => name[4]+=1,
            _ => continue,
        }
    }
    
    let mut cnt = 0;
    for &i in &name {
        if i!=0 {
            cnt += 1;
        }
    }

    let mut ans = 0;
    for i in 0..name.len()-2 {
        for j in i+1..name.len()-1 {
            for k in j+1..name.len() {
                ans += name[i]*name[j]*name[k];
            }
        }
    }
    
    println!("{}", ans);

}


Measured memory_bytes: 10492
let () =
  let n = read_int () in
  let rec doit i m ans =
    if i >= n then ans
    else let r = read_int () in let x = r - m in doit (i + 1) (if m < r then m else r) (if x > ans then x else ans)
  in
  Printf.printf "%d\n" (doit 1 (read_int ()) min_int)

Measured memory_bytes: 4480
#include <iostream>

int main()
{
    int x, y;
    int small, large;

    while (1){
        std::cin >> x >> y;

        if (x == 0 && y == 0) {
            break;
        }

        if (x <= y) {
            small = x;
            large = y;
        } else {
            small = y;
            large = x;
        }

        std::cout << small << " " << large << std::endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	int pn = 1;
	if (*ci == '-') {
		pn = -1;
		ci++;
	}
	ll tmp = *(ll*)ci;
	int dig = ((tmp & ma0) ^ ma0) ? 68 - __builtin_ctzll((tmp & ma0) ^ ma0) : 0;
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += (64 - dig >> 3);
	while ((ct = *ci++) >= '0') tmp = tmp * 10 + ct - '0';
	return pn * tmp;
}

ll A[200001];
void pakuri_sort(int N, ll A[]) {
	const int b = 8;
	ll tmp[200001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint();
	rep1(i, N) {
		A[i] = getint() + A[i - 1];
	}

	pakuri_sort(N + 1, A);

	ll kotae = 0;
	int kazu = 1;
	rep(i, N) {
		if (A[i + 1] != A[i]) kazu = 1;
		else kotae += kazu++;
	}

	printf("%lld\n", kotae);

	Would you please return 0;
}

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

int main() {
  int N;
  int an=0;
  int bn=0;
  int cn=0;

  cin >> N;

  an=N/100;
  bn=(N-(an*100))/10;
  cn=(N-(an*100)-(bn*10));

  bool chk=false;

  if(an==7){
    chk=true;
  }
  if(bn==7){
    chk=true;
  }
  if(cn==7){
    chk=true;
  }

  if(chk==true){
    cout << "Yes" << endl;
  }
  else if(chk==false){
    cout << "No" << endl;
  }

return 0;
}


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

int a[100005];

int main() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
   	int t; cin >> t;
    a[t] = i;
  }
  for (int i = 1; i <= n; i++) cout << a[i] << " ";
  cout << endl;
}

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

int main(){
  double n; int a=0, b=0; cin >>n;
  vector<int>v(n);
  for(int i=0; i<n; i++)
  {cin >>v[i]; a+=v[i];}
  for(int i=0; i<n; i++)
  {b+=v[i]*v[i];}

  double c=a/n; int p;
  if(c-floor(c)>0.5){p=floor(c)+1;}
  else{p=floor(c);}

  cout <<b-2*p*a+n*p*p;

return 0;
}

Measured memory_bytes: 256
n,W=map(int,input().split())
dp=[[0 for _ in range(W+1)] for _ in range(n+1)]
w=[]
v=[]
for i in range(n):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
for i in range(n):
  for j in range(W+1):
    if j<w[i]:dp[i+1][j]=dp[i][j]
    else:dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])
print(dp[-1][-1])

Measured memory_bytes: 218848
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue = BinaryHeap!(Array!long, "a<b");
// dfmt on

void main()
{
    long N = lread();
    auto A = aryread();
    long[3] M;
    long ans = 1;
    foreach (a; A)
    {
        bool b = true;
        long cnt;
        foreach (i; 0 .. 3)
            if (M[i] == a)
            {
                if (b)
                {
                    b = false;
                    M[i]++;
                }
                cnt++;
            }
        ans = ans * cnt % MOD;
    }
    writeln(ans);
}


Measured memory_bytes: 4560
#include<cstdio>
#include<cstring>
using namespace std;

#define N 50002
bool is_prime[N];

void sieve(){
	memset(is_prime,1,sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	for(int x=2;x<N;++x){
		if(is_prime[x]){
			for(int i=x+x;i<N;i+=x){
				is_prime[i] = false;
			}
		}
	}
}

int main(){
	sieve();
	int j;
	while(scanf("%d",&j) != EOF , j){
		int t = 0;
		bool mat[j+1];
		memset(mat,0,sizeof(mat));
		for(int x=2;x<=j;++x){
			if( is_prime[x] && is_prime[j-x] && !mat[x]){
				mat[x] = true;
				mat[j-x] = true;
				t++;
			}
		}
		printf("%d\n",t);
	}
	return 0;
}

Measured memory_bytes: 1132
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }
 
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }
 
template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}
 
struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};
 
void solve(string A) {
  const ll n = A.size();
  vector<ll> cnt(26);
  for (char c: A) cnt[c - 'a'] += 1;
  ll res = n * (n - 1) / 2;
  for (ll i: cnt) res -= i * (i - 1) / 2;
  cout << res + 1 << endl;
}
 
int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	string A;
	cin >> A;
	solve(A);
	return 0;
}

Measured memory_bytes: 768