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

int main()
{
	int N, num, amin = 100;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> num;
		int count = 0;
		while (num % 2 == 0)
		{
			num /= 2;
			count++;
		}
		amin = min(amin, count);
	}
	cout << amin << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long divisors[1000001];
void pre()
{
    for(int i=1; i<=1000000; i++)
    {
        for(int j=i; j<=1000000; j+=i)
        {
            divisors[j]++;
        }
    }
    for(int i=1; i<=1000000; i++)
    {
        divisors[i] += divisors[i-1];
    }
}
int main()
{
    long long n;
    while(cin >> n){
       n--;
       long long sum = 0;
       for(int i=1; i<=n; i++)
       {
            sum += (n/i);
       }
       sum += divisors[n];
       cout << sum << endl;
    }
}


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

int main() {
    int n;
    scanf("%d", &n);
    multiset<int> s;
    for (int i=0; i<(1<<n); i++) {
        int a;
        scanf("%d", &a);
        s.insert(a);
    }
    vector<int> cr((1<<n));
    auto it = s.end();
    it--;
    cr[0] = *it;
    s.erase(it);
    int l = 1;
    int ind = 1;
    while (l<=(n)) {
        int k = ind;
        for (int i=0; i<ind; i++) {
            //printf("%d ", cr[i]);
            auto it = s.lower_bound(cr[i]);

            if (it==s.begin()) {
                printf("No\n");
                return 0;
            }
            it--;
            cr[k++] = *it;
            s.erase(it);
        }  
        //printf("\n"); 
        ind = k;
        l++;
    }
    printf("Yes\n");
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
using namespace std;
const int limit = 50;

int n, m;
int a[limit], b[limit];

bool graph[limit][limit];
bool visited[limit];

void dfs(int v) {
  visited[v] = true;
  for (int v2 = 0; v2 < n; ++v2) {
    if (graph[v][v2] == false) continue;
    if (visited[v2] == true) continue;
    dfs(v2);
  }
}

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

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

  int ans = 0;

  for (int i = 0; i < m; ++i) {
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;

    for (int j = 0; j < n; ++j) visited[j] = false;

    dfs(0);

    bool bridge = false;
    for (int j = 0; j < n; ++j)
      if (visited[j] == false) bridge = true;
    if (bridge) ++ans;

    graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < n; i++) list.add(sc.nextInt());
    sc.close();

    List<Integer> bloks = new ArrayList<>();
    int target = Collections.min(list);
    for (int idx = list.indexOf(target); idx <= n; idx++) {
      int index = list.subList(idx, n).indexOf(target);
      if (index == -1) break;

      bloks.add(target);
      target += 1;
    }

    if (bloks.size() == 0) {
      System.out.println(0);
    } else if (bloks.get(0) != 1) {
      System.out.println(-1);
    } else {
      System.out.println(n - bloks.size());
    }
  }
}

Measured memory_bytes: 96776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

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

    if(a.back() == b[0] && b.back() == c[0]) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 100003
#define mod 1000000007
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;

int n;
int mn[2];
int mx[2];

int main() {
	scanf("%d",&n);
	mn[0] = mn[1] = INT_MAX;
	mx[0] = mx[1] = INT_MIN;
	for( int i = 0 , x,y ; i < n ; i++ ) {
		scanf("%d%d",&x,&y);
		mn[0] = min(mn[0],x+y);
		mn[1] = min(mn[1],x-y);
		mx[0] = max(mx[0],x+y);
		mx[1] = max(mx[1],x-y);
	}
	LL diff1 = (LL) mx[0]-mn[0];
	LL diff2 = (LL) mx[1]-mn[1];
	printf("%lld\n",max(diff1,diff2));
	return 0;
}

Measured memory_bytes: 3752
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
int main(void){
    string s,t;
    cin>>s>>t;
    if(s[2]==t[0] && s[1]==t[1] && s[0]==t[2]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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

int main() {
  int a;
  cin >> a;
  int ans = a + a * a + a * a * a;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
N=int(input())
l=[0]*10000
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            s=i**2+j**2+k**2+i*j+j*k+k*i
            if s<=10000:
                l[s-1]+=1
print(*l[:N],sep="\n")

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

#define int long long

#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
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001;
const int INFLL=1001001001001001001ll;
inline void am(int &a,int b){
    a+=b;
}

int N,P;
int A[111];

int dp[111][2];

signed main(){
    cin>>N>>P;
    rep(i,N)cin>>A[i];

    dp[0][0]=1;
    for(int i=0;i<N;i++){
        if(A[i]&1){
            am(dp[i+1][0],dp[i][1]);
            am(dp[i+1][1],dp[i][0]);
        }
        else{
            am(dp[i+1][0],dp[i][0]);
            am(dp[i+1][1],dp[i][1]);
        }

        am(dp[i+1][0],dp[i][0]);
        am(dp[i+1][1],dp[i][1]);

    }

    cout<<dp[N][P]<<endl;
    return 0;
}


Measured memory_bytes: 256
let () =
  let rec loop () =
    let x = read_line ()in
    match x with
      "0" -> ()
    | x -> let rec sum result = function
               0 -> result
             | i -> sum (result + (int_of_char x.[i-1]) - (int_of_char '0')) (i-1)
           in
           print_int @@ sum 0 (String.length x);
           print_char '\n';
           loop ()           
  in
  loop ()
;;


Measured memory_bytes: 2184
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
using namespace std;
void TxtRead(){
    freopen("input.txt","r", stdin);
    freopen("output.txt","w", stdout);
}
void TheTime(){
    ios_base::sync_with_stdio(false);
	cin.tie();
}
const int N = 3e3+5;
const ll INF = 1e9+5;
const ll MOD = 1e9+7;
const double PI = 3.141592653589793116;

string s1, s2;
int dp[N][N];

int main()
{
    //TxtRead();
    TheTime();
	
	cin>>s1>>s2;
	s1='#'+s1;
	s2='$'+s2;
	for(int i=1; i<s1.size(); i++){
		for(int j=1; j<s2.size(); j++){
			if(s1[i]==s2[j])
				dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1);
			else 
				dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
		}
	}
	
	string ans="";
	int a=1, b=1, mx=0;
	for(int i=1; i<s1.size(); i++){
		for(int j=1; j<s2.size(); j++){
			if(dp[i][j]>=mx) a=i, b=j;
		}
	}
	
	while(a!=0 || b!=0){
		if(a!=0 && (b==0 || dp[a][b]==dp[a-1][b])) a--;
		else if(b!=0 && (a==0 || dp[a][b]==dp[a][b-1])) b--;
		else{
			ans+=s1[a];
			a--, b--;
		}
	}
	reverse(ans.begin(), ans.end());
	cout<<ans<<'\n';
}

Measured memory_bytes: 35456
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
#include <list>
#include <string>
using namespace std;

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

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

int main()
{
    int n;
    cin >> n;
    ll a[100000];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n-1;i++){
        a[i+1] = gcd(a[i],a[i+1]);
    }
    cout << a[n-1];
}


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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}

signed main() {
	int n, ans = 0, c[10656], d[10656];
	cin >> n;
	vector<int>go[10656];
	rep(i, n - 1) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		go[x].push_back(y);
		go[y].push_back(x);
	}
	rep(i, n) {
		cin >> c[i];
		ans += c[i];
	}
	sort(c, c + n), reverse(c, c + n);
	cout << ans - c[0] << endl;
	int now = 0;
	queue<int>que;
	que.push(0);
	fill(d, d + n, inf);
	while (!que.empty()) {
		int q = que.front(); que.pop();
		d[q] = c[now];
		now++;
		rep(i, go[q].size()) {
			if (d[go[q][i]] == inf) {
				que.push(go[q][i]);
				d[go[q][i]] = mod;
			}
		}
	}
	rep(i, n) {
		cout << d[i] << " ";
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 1152
#include <algorithm>
// #include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double db;
const int oo=2139063143;
const int N=610;
const int P=1000000007;
const db eps=1e-7;
#define pritnf printf
//char buf[1<<22],*p1=buf,*p2=buf,obuf[1<<22],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
    if (x< 0) putchar('-'),x=-x;
    if (x>=10) print(x/10);
    putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
template <typename T1,typename T2>
void chkmax (T1 &A,T2 B) { A=A>=B?A:B; }
template <typename T1,typename T2>
void chkmin (T1 &A,T2 B) { A=A<=B?A:B; }
bool vis[N][N];
int n,d1,d2;
void solve (int d)
{
	int t=0;
	while (d%4==0) d/=4,++t;
	if (d&1)
	{
		for (int i=0; i< n; i++)
			for (int j=0; j< n; j++)
				if (((i>>t)+(j>>t))&1) vis[i][j]=1;
	}
	else
	{
		for (int i=0; i< n; i++) if ((i>>t)&1)
			for (int j=0; j< n; j++)
				vis[i][j]=1;
	}
}
int main ()
{
    // freopen (".in","r",stdin);
    // freopen (".out","w",stdout);
	sc(n),sc(d1),sc(d2); int m=n*n; n<<=1;
	solve (d1);
	solve (d2);
	for (int i=0; i< n; i++)
		for (int j=0; j< n; j++) if (!vis[i][j])
		{
			printf ("%d %d\n",i,j);
			if (!--m) return 0;
		}

    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define drep(i,n) for (int i = n; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
using namespace std;
typedef long long ll;

int gcd(int a, int b)
{
   if (a%b == 0) return(b);
   else          return(gcd(b, a%b));
}
int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}


//------------------------------------------------------------
int main() {
  int N, sum=0, flag=0;
  cin >> N;

  vector<ll> vec(N);
  rep(i, N) cin >> vec.at(i);

  while (1)
  {
    rep(i, N)
    {
      if(vec.at(i)%2==0)
      {
        vec.at(i) = vec.at(i)/2;
      }
      else
      {
        flag=1;
        break;
      }
    }

    if (flag==0) sum++;
    else break;
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = 1e9;
const double pi = acos(-1.0);

int main() {
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
	Cout((a + b * 5 + c * 10 + d * 50 + e * 100 + f * 500) >= 1000);
}


Measured memory_bytes: 3080
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
B = [int(input()) for _ in range(N)]

A = sum(A,[])
for b in B:
    if b in A:
        A[A.index(b)] = -1

if A[0]==A[1]==A[2] or A[3]==A[4]==A[5] or A[6]==A[7]==A[8] or A[0]==A[3]==A[6] or A[1]==A[4]==A[7] or A[2]==A[5]==A[8] or A[0]==A[4]==A[8] or A[2]==A[4]==A[6]:
    print('Yes')
else:
    print('No')

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

int main() {
	string S;
	cin >> S;
	int N = S.size();
	vector<int> mod(N),d(N);
	rep(i, N) {
		if (i == 0) {
			d[i] = 1;
			continue;
		}
		d[i] = 10 * d[i - 1];
		d[i] %= 2019;
	}
	rep(i, N) {
		int a = S.at(N - 1 - i) - '0';
		if (i == 0) {
			mod[i] = a;
			//cout << mod[i] << endl;
			continue;
		}
		mod[i] = (a * d[i]) % 2019 + mod[i-1];
		mod[i] %= 2019;
		//cout << mod[i] << endl;
	}
	vector<int> cnt(2019);
	cnt[0]++;
	rep(i, N) {
		cnt[mod[i]]++;
	}
	ll ans = 0;
	rep(i, 2019) {
			ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	cout << ans;
}


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

int main() {
  int n;
  cin >> n;
  cout << (n-1)/2 << endl;
  return 0;
}

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

void BubbleSort(vector<int> &A, int &count)
{
	for(int i = 0; i < A.size(); i++){
		int minj = i;
		for(int j = i; j < A.size(); j++){
			if(A[j] < A[minj]){
				minj = j;
			}
		}
		if(minj != i){
			swap(A[i], A[minj]);
			count++;
		}
	}
}

void Output(vector<int> A)
{
	int n = A.size() - 1;
	for(int i = 0; i < n; i++){
		cout << A[i] << ' ';
	}
	cout << A[n] << endl;
}

vector<int> Input()
{
	int N;
	cin >> N;
	vector<int> A;
	A.resize(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	return A;
}

int main()
{
	vector<int> A = Input();
	int count = 0;
	BubbleSort(A, count);
	Output(A);
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 1220
s = input()
k = int(input())

# s='aaaabba'
# k=13

leng = len(s)
if(leng==1):
    print(k//2)
    exit()
elif(leng==2):
    if(s[0]==s[1]):
        print(k)
    else:
        print(0)
    exit()

if(s[:-1]==s[1:]):
    print(leng*k//2)
    exit()

ct_1 = 0
s1 = s
s2 = s+s
for i in range(1,leng):
    if(s1[i-1]==s1[i]):
        s1 = s1[:i] + '?' + s1[i+1:]
        ct_1 += 1

ct_2 = 0
for i in range(1,leng*2):
    if(s2[i-1]==s2[i]):
        s2 = s2[:i] + '?' + s2[i+1:]
        ct_2 += 1

ans = ct_1 + (ct_2 - ct_1)*(k-1)

print(ans)


Measured memory_bytes: 3064
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
 
                if ((a + b + c == 17) && (a == 5 || a == 7) && (b == 5 || b == 7) && (c == 5 || c == 7)){
                    System.out.println("YES");
                }else{
                   System.out.println("NO");
                }
     }
}              

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
int main() {
    Int X; cin >> X;
    Int curr = 100;
    int year = 0;
    while (curr < X) {
        curr = curr + curr / 100;
        year++;
    }
    cout << year << endl;
    return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        double first = 1.0d/(double) n;

        double res = 0.0d;
        for (int i = 1; i <= n; i++) {
            int tmp = i;
            double zyo = 0.0d;
            while (tmp <= k-1) {
                zyo++;
                tmp *= 2;
            }
//            if (zyo == 0.0d) zyo = 1.0d;
            res += Math.pow(0.5d, zyo);
        }
        System.out.println(res * first);
    }
}


Measured memory_bytes: 21844
#include<iostream>

int main(void){
    int n,m,l;
    std::cin>>n>>m>>l;
    long A[n][m],B[m][l],sum=0;
    int i,j,k;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            std::cin>>A[i][j];
        }
    }
    for(i=0;i<m;i++){
        for(j=0;j<l;j++){
            std::cin>>B[i][j];
        }
    }
    
    for(i=0;i<n;i++){
        for(j=0;j<l;j++){
        sum=0;
            for(k=0;k<m;k++){
                sum+=A[i][k]*B[k][j];
            }
            if(j)std::cout<<" ";
           std::cout<<sum;
          
        }
        std::cout<<std::endl;
    }
    return 0;
}

Measured memory_bytes: 3220
#include <iostream>
#include <cstdio>
#include <vector>
#include <complex>
using namespace std;

int main() {
    int N,D;
    cin >> N>>D;
    vector<vector<int>> var;
    for(int i=0;i<N;i++){
        vector<int> tmp;
        for(int i=0;i<D;i++){
            int j =0;
            cin >> j;
            tmp.push_back(j);
        }
        var.push_back(tmp);
    }

    int flag =0;
    int tmp[D];
    for(int i=0;i<var.size();i++){
        for(int j=0;j<var[i].size();j++){
            tmp[j] = var[i][j];
        }
        int comp[D];
        for(int j=i+1;j<var.size();j++){
            for(int k=0;k<var[j].size();k++){
                comp[k] = tmp[k]-var[j][k];
            }

            int dis_i = 0;
            for(int k=0;k<D;k++){
                dis_i+=abs(comp[k])*abs(comp[k]);
            }
            int dis = sqrt(dis_i);
            int dis_tmp = dis*dis;
            if(dis_i == dis_tmp){
                flag++;
            }
        }

    }
    cout <<flag<<endl;
    return 0;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  
  vector<int> checker(N, 0);
  int a = 0;
  for (int i = 0; i < 2 * M; i++){
    cin >> a;
    checker.at(a - 1)++;
  }
  
  for (int i = 0; i < N; i++){
    cout << checker.at(i) << endl;
  }
}

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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    LL N;
    cin >> N;
    vector<LL> v(N + 1, 0);
    vector<LL> A(N);
    REP(i, N) {
        cin >> A[i];
        v[A[i]]++;
    }
    LL s = 0;
    for(auto i : v) {
        s += i*(i - 1)/2;
    }
    REP(i, N) {
        int a = A[i];
        LL c = v[a];
        LL res = s;
        res = res - c*(c - 1)/2 + (c - 1)*(c - 2)/2;
        cout << res << endl;
    }
    return 0;
}


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

namespace Main
{
    class Program
    {
        static void Main(string[] args)
        {
            //ここから
            //string[] str = Console.ReadLine().Split(' ');
            //int n = int.Parse(Console.ReadLine());



            long[] gojo = new long[1000];
            for (int i = 0; i < 1000; i++)
            {
                gojo[i] = (long)(Math.Pow(i, 5));
               // Console.WriteLine(gojo[i]);
            }
            long x = int.Parse(Console.ReadLine());

            for (int i = 0; i < 1000; i++)
            {
                long t = gojo[i] - x;
                if (t >= 0)
                {
                    if (gojo.Any(s => s == t))
                    {
                        Console.WriteLine("{0} {1}", i, (long)Math.Pow(t, 1.0 / 5.0));
                        return;
                    }
                }
                else
                {
                    if (gojo.Any(s => s == -1 * t))
                    {
                        Console.WriteLine("{0} {1}", i, -1 * (long)Math.Pow(-1 * t, 1.0 / 5.0));
                        return;
                    }
                }

            }

            //ここまで
        }

        static long Max(long a, long b)
        {
            if (a > b) return a;
            else return b;
        }


    }

}


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

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

    int k;
    int X[5];
    for (int & x : X) {
        cin >> x;
    }
    cin >> k;

    if (X[4] - X[0] > k) {
        cout << ":(" << '\n';
    } else {
        cout << "Yay!" << '\n';
    }



    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ
 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SWAP(type, x, y) do { type tmp = x; x = y; y = tmp; } while (0)
 
#define MOD 1000000007 
 
//降順
int desc(const void* a, const void* b){
    return *(int*)b-*(int*)a;
}
 
int main(void){
    int N;
    scanf("%d",&N);
 
    //A[0]~A[N-1]に格納する
    int* A;
    NEW(A,N);
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    qsort(A,N,sizeof(int),desc);
 
    long H=0;
    long W=0;
    for(int i=1;i<N;i++){
        if(A[i]==A[i-1]){
            if(H==0) H=A[i];
            else{
                W=A[i];
                break;
            }
            i++;
        }
    }
 
    long ans=H*W;
    printf("%ld\n",ans);
 
    return 0;
}

Measured memory_bytes: 892
#include <iostream>

using namespace std;

int main(){
  int count, add;
  cin >> count >> add;

  int num = 1;
  for(int i = 0; count > i; i++){
    if(num * 2 > num + add){
      num += add;
    }else{
      num *= 2;
    }
  }

  cout << num << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define task "tst"
using namespace std;
const ll N = 3e5 + 9;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
string res;
ll n,i,a[N],cnt[N];
ll q,x,y,sum;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n;
    for (i = 1;i <= n;i++){
        cin>>a[i];
        cnt[a[i]]++;
        sum += a[i];
    }
    cin>>q;
    while(q--){
        cin>>x>>y;
        sum -= x*cnt[x]; sum += y*cnt[x];
        cnt[y] += cnt[x]; cnt[x] = 0;
        cout<<sum<<"\n";
    }
}



Measured memory_bytes: 5212
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
/* テンプレートここまで */
const int MOD = 1e9 + 7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  int N;  cin >> N;
  int a[N][N]; REP(i, N) REP(j, N){cin >> a[i][j];}
  vector<vector<ll>> dp(N, vector<ll>(1<<N, 0));

  REP(k, N){
    if(a[0][k] == 0) continue;
    dp[0][1<<k] = 1;
  }

  REP(i, N-1) REP(j, N) REP(k, 1<<N){
    if(a[i+1][j] == 1 && !(1<<j & k) ){
      (dp[i+1][k+(1<<j)] += dp[i][k]) %= MOD;
    }
  }

  ll ans = 0;
  REP(k, 1<<N){
    (ans += dp[N-1][k]) %= MOD;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 360832
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#define INF 1<<19
const int MOD = 1000000007;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
string S;

int main(){
    int w;
    cin >> S;
    cin >> w;
    int i;
    for(i = 0; i < S.size(); i += w){
        cout << S[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
class Array
  include Comparable
end

n = gets.to_s.to_i

cnt = 0
# cr = n.to_s.chars.map{|t|t.to_i}
sz = n.to_s.size
3.upto(sz) do |i|
  
  [3, 5, 7].repeated_permutation(i) do |a|
    
    if a.include?(3) && a.include?(5) && a.include?(7) && a.join.to_i <= n
      cnt += 1
      # p a
    end
  end
end

puts cnt

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

using namespace std;

int main(){
  int n;
  cin>> n;
  int ac = 0, wa =0, tle = 0, re = 0;
  
  for(int i = 0; i<n; ++i){
    string s;
    cin>> s;
    if(s =="AC") ac++;
    else if(s == "WA") wa++;
    else if(s == "RE") re++;
    else tle++;
  }
  cout<< "AC x "<< ac<< endl;
  cout<<"WA x "<< wa<< endl;
  cout<<"TLE x " <<tle<< endl;
  cout<< "RE x " << re<< endl;
}

Measured memory_bytes: 3624
def main():
    n, k = [int(i) for i in input().split()]
    h = [int(i) for i in input().split()]
    memo = [10e9 for _ in range(n)]
    memo[0] = 0
    for i in range(n):
        for j in range(1, min(n-i,k+1)):
            memo[i+j] = min(memo[i+j], memo[i] + abs(h[i] - h[i+j]))
    print(memo[-1])


if __name__ == '__main__':
    main()



Measured memory_bytes: 58848
#include<bits/stdc++.h>
using namespace std;
int main(void) {
  int n,ans=0;
  cin >> n;
  long long a[n];
  for(int i=0;i<n;++i) cin >> a[i];
    for(int i=0;i<n;++i) {
      if(a[i]%2==0) {
        while(true) {
        a[i] /= 2;
        ++ans;
          if(a[i]%2==1) break;
      }
    }
    }
    cout << ans << endl;
}



Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp(a,b) std::make_pair(a,b)
using std::cin;
using std::cout;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
int sx,sy,tx,ty;
int main(){
  cin>>sx>>sy>>tx>>ty;
  rep(i,tx-sx) cout<<'R';
  rep(i,ty-sy) cout<<'U';
  rep(i,tx-sx) cout<<'L';
  rep(i,ty-sy) cout<<'D';  
  cout<<'D';
  rep(i,tx-sx+1) cout<<'R';
  rep(i,ty-sy+1) cout<<'U';
  cout<<'L'<<'U';
  rep(i,tx-sx+1) cout<<'L';
  rep(i,ty-sy+1) cout<<'D';
  cout<<'R'<<"\n";
  return 0;
}


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

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);


int main(void)
{
    ll a,b,c; cin>>a>>b>>c;
    if(a+b>c && b+c>a && c+a>b && a==b && b==c && c==a) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3540
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mod 1000000007
int32_t main()
{
    fast;
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int > v1, v2, v3;
    map<int , int > m;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'R')
        {
            v1.push_back(i);
        }
        else if (s[i] == 'G')
        {
            v2.push_back(i);
        }
        else
        {
            m[i] = 1;
            v3.push_back(i);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (s[i] != s[j])
            {
                if (s[i] == 'R')
                {
                    if (s[j] == 'G')
                    {
                        int u = lower_bound(v3.begin(), v3.end(), j) - v3.begin();
                        ans += v3.size() - u;
                        if (j + (j - i) < n and s[j + (j - i)] == 'B')
                            ans--;
                    }
                    else
                    {
                        int u = lower_bound(v2.begin(), v2.end(), j) - v2.begin();
                        ans += v2.size() - u;
                        if (j + (j - i) < n and s[j + (j - i)] == 'G')
                            ans--;
                    }
                }
                else if (s[i] == 'G')
                {
                    if (s[j] == 'R')
                    {
                        int u = lower_bound(v3.begin(), v3.end(), j) - v3.begin();
                        ans += v3.size() - u;
                        if (j + (j - i) < n and s[j + (j - i)] == 'B')
                            ans--;
                    }
                    else
                    {
                        int u = lower_bound(v1.begin(), v1.end(), j) - v1.begin();
                        ans += v1.size() - u;
                        if (j + (j - i) < n and s[j + (j - i)] == 'R')
                            ans--;
                    }
                }
                else
                {
                    if (s[j] == 'R')
                    {
                        int u = lower_bound(v2.begin(), v2.end(), j) - v2.begin();
                        ans += v2.size() - u;
                        if (j + (j - i) < n and s[j + (j - i)] == 'G')
                            ans--;
                    }
                    else
                    {
                        int u = lower_bound(v1.begin(), v1.end(), j) - v1.begin();
                        ans += v1.size() - u;
                        if (j + (j - i) < n and s[j + (j - i)] == 'R')
                            ans--;
                    }
                }
            }
        }
    }
    cout << ans;




}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int N;
vector<pair<int,ll>> G[100005];
int color[100005];

void dfs(int v){
  if(color[v] == -1) color[v] = 0;
  //cout << " " << v << endl;
  
  rep(i,G[v].size()){
    if(color[G[v][i].first] != -1) continue;
    if(G[v][i].second % 2 == 0){
      color[G[v][i].first] = color[v];
      dfs(G[v][i].first);
    }else{
      color[G[v][i].first] = 1-color[v];
      dfs(G[v][i].first);      
    }
  }
}

int main(){
  cin >> N;
  rep(i,N-1){
    int u, v;
    ll w;
    cin >> u >> v >> w;
    G[u].emplace_back(v,w);
    G[v].emplace_back(u,w);
  }
  rep(i,100005){
    color[i] = -1;
  }

  REP(i,1,N+1){
    if(color[i] == -1) dfs(i);
  }

  REP(i,1,N+1){
    cout << color[i] << endl;
  }
  
  return 0;
}


Measured memory_bytes: 9856
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
const ll mod=1e9+7;
template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
const ll N=1e6+8;
const ll INF=1e18;
ll n;
ld a[3001];
ld dp[3001][3001];
bool vis[3001][3001];
ld func(ll size,ll req){
  if(req<0)
  return 0.0;
  if(size==-1){
    if(req==0)
    return 1.0;
    else 
    return 0.0;
  }
if(vis[size][req])
return dp[size][req];
ld res=a[size]*func(size-1,req-1)+(1-a[size])*func(size-1,req);
vis[size][req]=1;
return dp[size][req]=res;
}
int main(){
  cin>>n;
  for(ll i=0;i<n;i++)
  cin>>a[i];
  ld ans=0.0;
  memset(vis,0,sizeof(vis));
  for(ll i=(n/2)+1;i<=n;i++){
   ans+=func(n-1,i);
  }
  cout<<fixed<<setprecision(12)<<ans<<endl;
}

Measured memory_bytes: 150016
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
 
#define ull unsigned long long
#define ll long long
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define PI acos(-1.0)
const int N=1e5 + 5;
const int M=1e5 + 5;
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    int i,n;
    char s[N];
    int arr[N],R[N],L[N];
    cin>>s;
    n=strlen(s);
    for(i=0;i<N;i++){
        arr[i]=0;
    } 
    int id=0;
    for(i=1;i<n;i++){
        if(s[i]=='L'){
            R[i]=id;
        }
        if(s[i]=='R') id=i;
    }

    id=n-1;
    for(i=n-2;i>=0;i--){
        if(s[i]=='R'){
            L[i]=id;
        }
        if(s[i]=='L') id=i;    
    }

    for(i=0;i<n;i++){
        if(s[i]=='R'){
            int d = L[i]-i;
            if(d%2==0) arr[L[i]]++;
            else arr[L[i]-1]++;
        }
        else{
            int d = i-R[i];
            if(d%2==0) arr[R[i]]++;
            else arr[R[i]+1]++;
        }
    }

    for(i=0;i<n;i++) cout << arr[i] << " ";
    cout << endl;
 
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <string>

using namespace std;

int tempmarge[1000100];

int N, A[10000000];

int preorder[1000], inorder[1000];

bool bsearch(const int array[], int left, int right, int value) {
	while (left + 1 < right) {
		int med = (left + right) / 2;
		if (array[med] > value)right = med;
		else left = med;
	}
	return left < right  && array[left] == value;
}

long long int MargeSort(int x[], int left, int right) {
	long long int mid, i, j, k, cl, cr, c;

	if (left >= right)
		return 0;

	mid = (left + right) / 2;
	cl = MargeSort(x, left, mid);
	cr = MargeSort(x, mid + 1, right);


	for (i = left; i <= mid; i++)
		tempmarge[i] = x[i];
	for (i = mid + 1, j = right; i <= right; i++, j--)
		tempmarge[i] = x[j];

	i = left;
	j = right;
	c = 0;
	for (k = left; k <= right; k++)
		if (tempmarge[i] <= tempmarge[j])
			x[k] = tempmarge[i++];
		else {
			c += mid + 1 - i;
			x[k] = tempmarge[j--];
		}

	return c + cl + cr;
}

void recover(int fp, int lp, int fi, int li) {
	int root, i;
	for (i = fi; i < li + 1; i++) {
		if (preorder[fp] == inorder[i]) break;
	}
	root = i;
	if (fi < root) {
		recover(fp + 1, fp + root - fi, fi, root - 1);
		cout << " ";
	}
	if (root < li) {
		recover(fp + root - fi + 1, lp, root + 1, li);
		cout << " ";
	}
	cout << inorder[root];
}

int main() {
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> preorder[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> inorder[i];
	}

	recover(0, N - 1, 0, N - 1);
	cout << endl;

	return 0;
}

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

long long n;
vector<long double> v;

long double solve();

int main() {
  cout << fixed << setprecision(10);
  cin >> n;
  v.resize(n);
  for(int i = 0; i < n; ++i) cin >> v[i];

  cout << solve() << endl;
  return 0;
}

long double solve() {
  while(v.size() > 1) {
    sort(v.begin(), v.end(), greater<long double>());
    long double now = 0;
    now += v[v.size() - 1];
    now += v[v.size() - 2];
    now /= 2.0;
    v.erase(v.begin() + v.size() - 2, v.end());
    v.push_back(now);
  }
  return v[0];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for (int i=a; i<b; ++i)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    bool occured=false;
    int count=0;
    for (int i=0; i<N; ++i)
    {
        int x, y;
        cin >> x >> y;
        if (x==y)
        {
            count++;
            if (count>=3) occured=true;
        }
        else count=0;
    }
    if (occured) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 3656
#include "bits/stdc++.h"
using namespace std;

/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = 1000100010010010;
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};


/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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; }
template<class T>auto cut(T &a, int l, int r){return T(a.begin()+l, a.begin()+r);}

/* main */



signed main(){


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

    char a, b; cin >> a >> b;

    int c = (a == 'H' ? 1 : 0);
    int d = (b == 'H' ? 1 : 0);

    if(c ^ d){
        print('D');
    }else{
        print('H');
    }




    

    

    


    

}



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

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        int output;
        double diff = 100;
        for (int i = 0; i < n; i++) {
            int num;
            double h, w;
            cin >> num >> h >> w;
            double bmi = w / pow(h / 100, 2);
            if (fabs(bmi - 22) < diff) {
                diff = fabs(bmi - 22);
                output = num;
            }
        }
        cout << output << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
//#define MOD 1000000007
const int INF = 1LL<<30;

int G[10][10];

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

    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--,b--;
        G[a][b]=1;
        G[b][a]=1;
    } 

    vector<int> ord(n);
    rep(i,n) ord[i]=i;

    int ans=0;
    do{
        if(ord[0]!=0) continue;
        bool ok=true;
        rep(i,n-1){
            if(G[ord[i]][ord[i+1]]==0) ok=false;
        }
        if(ok) ans++;
    }while(next_permutation(all(ord)));

    cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
const ll MOD = 1e9+7;

int A[100100];
ll DP[110][100100];
int main(){
    int N, K;
    cin >> N >> K;
    REP(i,N){
        int a;
        cin >> a;
        A[i] = a;
    }

    for(int i = 0; i <= A[0]; i++){
        DP[0][i] = 1;
    }

    for(int i = 1; i < N; i++){
        DP[i][0] = DP[i-1][0];
        for(int j = 1; j <= K; j++){
            DP[i][j] = DP[i][j-1] + DP[i-1][j];// - DP[i-1][j-1-A[i]];
            if(j-1-A[i] >= 0) DP[i][j] -= DP[i-1][j-1-A[i]];
        }
        for(int j = 0; j <= K; j++){
            DP[i][j] %= MOD;
        }
    }

    //cout << DP[N-1][K] % MOD << endl;
    printf("%lld\n", DP[N-1][K] % MOD);
    return 0;
}


Measured memory_bytes: 80128
#!/usr/bin/python3
# -*- coding: utf-8 -*-

N = int(input())
prev_dst = [0,0,0]

for n in range(N):
    t, x, y = map(int, input().split(" "))
    a = (t - prev_dst[0]) - (abs(prev_dst[1]-x) + abs(prev_dst[2]-y))
    if a >= 0 and a % 2 == 0:
        prev_dst = [t, x, y]
    else:
        print("No")
        exit(0)

print("Yes")



Measured memory_bytes: 3060
#include<stdio.h>

int main()
{
int n,sum=0,k;
 scanf("%d",&n);
 int d = n;
 while(n>0)
{
 k = n%10;
sum+=k;
n=n/10;
}
//printf("sum  =  %d",sum);
if(d%sum== 0)
printf("Yes");
else
printf("No");
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(abs(a-c) <= d) cout << "Yes" << endl;
    else if(abs(a-b) <= d && abs(b-c) <= d) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())

N = ni()
g1, s1, b1 = nm()
g2, s2, b2 = nm()

INF = 10 ** 15


def solve():
    x1 = [g1, s1, b1]
    x2 = [g2, s2, b2]

    # dp[i] := max future donguri when we use i donguri
    dp = [-INF] * (N + 1)
    dp[0] = N
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 >= t2:
            continue
        for j in range(t1, N + 1):
            r = dp[j - t1] - t1
            if r >= 0 and dp[j] < r + t2:
                dp[j] = r + t2

    don = max(dp)
    dp = [0] * (don + 1)
    dp[0] = don
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 <= t2:
            continue
        for j in range(t2, don + 1):
            r = dp[j - t2] - t2
            if r >= 0 and dp[j] < r + t1:
                dp[j] = r + t1
    return max(dp)


print(solve())


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

int main(void){
  int n;
  cin >> n;
  
  int dai = n / 500;
  int s = n % 500;
  int syo = s / 5;
  
  cout << dai * 1000 + syo * 5 << endl;

}

Measured memory_bytes: 3576
n = gets.chomp.to_i
a = gets.chomp.split(' ').map(&:to_i).sort

c = {}
n.times do |i|
  if c[a[i]]
    c[a[i]] += 1
  else
    c[a[i]] = 1
  end
end

answer = 0
(n - 1).downto(0) do |i|
  next if c[a[i]] <= 0
  c[a[i]] -= 1
  l = a[i].to_s(2).length
  t = (1 << l) - a[i]
  if c[t] && c[t] > 0
    c[t] -= 1
    answer += 1
  end
end
puts answer


Measured memory_bytes: 39276
import sys
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

r = ni()
g = ni()
print(2 * g - r)

Measured memory_bytes: 5280
import java.util.*;


public class Main {

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

	public Main(){
		new A().doIt();
	}
	public class A {
		Scanner sc = new Scanner(System.in);
		String ans(char ctr[],int a[]){
			String alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
			char[] alf2 = alf.toCharArray();
			for(int i = 0;i < ctr.length;i++){
				for(int j = 0;j < alf2.length;j++){
					if(ctr[i] == alf2[j]){
						ctr[i] = alf2[((j - a[i % a.length]) + 52) % 52];
						break;
					}
				}
			}
			String result = "";
			for(int i = 0;i < ctr.length;i++){
				result = result + ctr[i];
			}
			return result;
		}
		void doIt(){
			while(true){
				int n = sc.nextInt();
				if(n == 0)break;
				int a[] = new int[n];
				for(int i = 0;i < n;i++)a[i] = sc.nextInt();
				String str = sc.next();
				char ctr[] = str.toCharArray();
				System.out.println(ans(ctr,a));
			}
		}		
	}
}

Measured memory_bytes: 26964
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    F = [int(f) for f in input().split()]
    A.sort(reverse = True)
    F.sort()
    low, high = -1, 10 ** 12 + 1
    while high - low > 1:
        mid = (low + high) // 2
        count = 0
        for i in range(N):
            if A[i] * F[i] > mid: count += A[i] - (mid // F[i])
        if count > K: low = mid
        else: high = mid
    print(high)

    return 0

if __name__ == "__main__":
    solve()

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

vector<pair<long long, long long> > prime_fact(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; a++) {
        if (N % a != 0) continue;
        long long ex = 0;
         
        while (N % a == 0) {
            ex++;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    long long n; cin >> n;
    vector<pair<long long, long long> > res = prime_fact(n);
    cout << n << ":";
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].second; j++) {
            cout << " " << res[i].first;
        }
    }
    cout << endl;

}


Measured memory_bytes: 3124