akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
struct adja {
    int v;
    int c;
};
 
int n;
vector<adja> g[10000];
int d[10000];
 
void search() {
    fill_n(d, n, 1 << 20);
    queue<int> q;
    q.push(0);
    d[0] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0, s = g[u].size(); i < s; ++i) {
            if (d[g[u][i].v] > d[u] + g[u][i].c) {
                d[g[u][i].v] = d[u] + g[u][i].c;
                q.push(g[u][i].v);
            }
        }
    }
}
 
int main() {
    int u, k, v, c;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> u >> k;
        g[u].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> g[u][j].v >> g[u][j].c;
        }
    }
    search();
    for (int i = 0; i < n; ++i) {
        cout << i << " " << d[i] << endl;
    }
 
    return 0;
}


Measured memory_bytes: 7220
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <functional>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MOD = 1000000007;

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

    vector<int> a(n);

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

    vector<int> pos(n);

    pos[0] = k - a[n-1] + a[0];

    for(int i = 1;i < n;i++){
        pos[i] = a[i] - a[i-1];
    }

    cout << k - *max_element(pos.begin(),pos.end()) << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MAX 500010
#define MOD 1000000007
typedef long long  ll;

using namespace std;

ll ans;

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

	ll N;
	cin >> N;
	vector<ll> a(N);
	rep(i,N){
		cin >> a[i];
		a[i]--;
	}
	
	ll cur = 0;
	while(true){
		if(cur == 1) break;
		if(ans > N){
			ans = -1;
			break;
		}
		cur = a[cur];
		ans++;
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

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

        int M = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(solve(M, K));

        sc.close();
    }

    static String solve(int M, int K) {
        if (M == 0) {
            if (K == 0) {
                return "0 0";
            } else {
                return "-1";
            }
        }
        if (M == 1) {
            if (K == 0) {
                return "0 0 1 1";
            } else {
                return "-1";
            }
        }

        if (K >= 1 << M) {
            return "-1";
        }

        int[] result = new int[1 << (M + 1)];
        result[0] = K;
        result[1 << M] = K;

        int leftIndex = 1;
        int rightIndex = result.length - 1;
        for (int i = 0; i < 1 << M; ++i) {
            if (i != K) {
                result[leftIndex] = i;
                result[rightIndex] = i;

                ++leftIndex;
                --rightIndex;
            }
        }

        return Arrays.stream(result).mapToObj(String::valueOf).collect(Collectors.joining(" "));
    }
}

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

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  int N;
  cin >> N;
  vector<int> A(N);
  rep (i, N) {
    cin >> A[i];
  }
  map<int, int> m1;
  map<int, int> m2;
  int m = 0;
  rep(i, N) {
    m1[abs(A[i]+i)]++;
    if (A[i]-i<0) {
      m2[abs(A[i]-i)]++;
    }
    // else {
    //   m++;
    // }
  }
  ll ans = 0;
  for (auto ite = m1.begin(); ite != m1.end(); ite++) {
    ans += (ll)ite->_2*m2[ite->_1];
    // cout << ite->_1 << ' ' << ite->_2 << ' ' << m2[ite->_1] << endl;
  }
  // ans += m*(m-1)/2;
  cout << ans << endl;
}


Measured memory_bytes: 22964
// http://algorithms.blog55.fc2.com/blog-entry-66.html

#include <iostream>
using namespace std;
#include <stdio.h>

#define MAX 100
#define INFTY (1 << 21)

int SIZE;
int R[MAX + 2];
int C[MAX+1][MAX+1]; // cost table
int B[MAX+1][MAX+1]; // best table

void compute(){
    for ( int i = 0; i <= SIZE; i++ )
    for ( int j = 0; j <= SIZE; j++ ) C[i][j] = INFTY;
    
    for ( int i = 0; i <= SIZE; i++ ) C[i][i] = 0;
    
    for ( int j = 1; j <= SIZE - 1; j++ ){
        for ( int i = 0; i < SIZE - j; i++ ){
            for ( int k = i; k < i + j; k++ ){
                // C[i][i+j] = min( C[i][i+j], 
                //                  C[i][k-1] + C[k][i+j] + R[i]*R[k]*R[i+j+1]);
                int cost = C[i][k] + C[k+1][i+j] + R[i]*R[k+1]*R[i+j+1];
                if ( cost < C[i][i+j] ){
                    C[i][i+j] =  cost;
                    B[i][i+j] = k;
                }
                
            }
        }
    }
}

void order( int i, int j ){
    if ( i == j ) cout << "M" << i;
    else{
        cout << "(";
        order( i, B[i][j]-1 ); order(B[i][j], j);
        cout << ")";
    }
}

void input(){
    cin >> SIZE;
	int z,i=0;
    for (; i < SIZE; i++ ) cin >> R[i]>>z;
	R[i]=z;
	//SIZE++;
}

void output(){
    cout <<  C[0][SIZE-1] << endl;
    //order(1, SIZE);
    //cout << endl;
}

main(){
    input();
    compute();
    output();
}

Measured memory_bytes: 1240
n,k=map(int,input().split())
a=list(map(int,input().split()))
count=[0]*n
for i in range(n):
  count[a[i]-1] += 1
count.sort()
sum=0
for i in range(k):
  sum += count[n-1-i]
print(max(0,n-sum));

Measured memory_bytes: 24748
#include <iostream>
#include <vector>
using namespace std;
int max(int a, int b){
	return a > b ? a : b;
}
int main(){
	int n;
	cin >> n;
	vector<int>a(n), b(n), c(n);
	for (int i = 0; i < n; i++) 
		cin >> a[i] >> b[i] >> c[i];
	vector<vector<int>>dp(n, vector<int>(3, 0));
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];
	for (int i = 1; i < n; i++){
		dp[i][0] = max(dp[i][0], max(dp[i - 1][1] + a[i], dp[i - 1][2] + a[i]));
		dp[i][1] = max(dp[i][1], max(dp[i - 1][0] + b[i], dp[i - 1][2] + b[i]));
		dp[i][2] = max(dp[i][2], max(dp[i - 1][1] + c[i], dp[i - 1][0] + c[i]));
	}
	cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
}

Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std ;
int main(){
  string str ; int count = 0;
  cin >>str ;
  string qtr ;
  cin >> qtr ;
  for(int i=0;i<3;i++){
    if(str[i]==qtr[i]) count ++;
  }
  cout << count ;
  return 0;
}

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

typedef long long ll;

using namespace std;

ll n, x;
vector<ll> a;

bool check(ll a, ll b, ll c) {
	//cerr << a << " " << b << " " <<c << endl;
	if ((a < b + c) && (b < a + c) && (c < a + b)) return true;
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	vector<ll> a(n);
	for (ll i = 0; i < n; ++i) {
		cin >> a[i];
	}
	ll len = ll(a.size());
	ll ans = 0;
	sort(a.begin(), a.end());
	for (ll i = 0; i < len; ++i) {
		for (ll j = i + 1; j < len; ++j) {
			for (ll k = j + 1; k < len; ++k) {
				 if (a[i] + a[j] <= a[k]) break;
				 ++ans;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}


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

int main() {
    //
    int num;
    int harf;
    int cnt = 0;
    int cnt2 = 0;
    int tmpMax = 0;
    int maxKi;
    int maxGu;
    map<int, int> mKi;
    map<int, int> mGu;

    cin >> num;

    vector<int> vec(num);
    for (int i = 0; i < num; i++) cin >> vec.at(i);

    harf = num / 2;

    for (int i = 0; i < num; i += 2) mKi[vec.at(i)]++;
    for (int i = 1; i < num; i += 2) mGu[vec.at(i)]++;

    for (auto itr : mKi) {
        if (itr.second > tmpMax) {
            tmpMax = itr.second;
            maxKi = itr.first;
        }
    }
    cnt = harf - tmpMax;

    tmpMax = 0;
    for (auto itr : mGu) {
        if (itr.first == maxKi) continue;
        tmpMax = max(itr.second, tmpMax);
    }
    cnt += harf - tmpMax;

    tmpMax = 0;
    for (auto itr : mGu) {
        if (itr.second > tmpMax) {
            tmpMax = itr.second;
            maxGu = itr.first;
        }
    }
    cnt2 = harf - tmpMax;

    tmpMax = 0;
    for (auto itr : mKi) {
        if (itr.first == maxGu) continue;
        tmpMax = max(itr.second, tmpMax);
    }
    cnt2 += harf - tmpMax;

    cout << min(cnt,cnt2);

    //
}


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

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


vector<string> S;
int main() {
    int n;
    string s;
    cin >> n;
    rep(i, n) {
        cin >> s;
        sort(s.begin(), s.end());
        S.push_back(s);
    }

    sort(S.begin(), S.end());
    ll ans = 0;
    ll tmp = 0;
    rep(i, n-1) {
        if(S[i] == S[i+1]) {
            tmp ++;
        } else {
            if (tmp) {
            ans += tmp*(tmp+1)/2;
            tmp = 0;
            }
        }
    }

    if (tmp) {
        ans += tmp*(tmp+1)/2;
    }

    cout << ans << endl;
}



Measured memory_bytes: 5748
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int score[] = new int[5];
		int average = 0;
		for(int i=0;i<5;i++){
			score[i] = sc.nextInt();
			if(score[i]<40) score[i] = 40;
			average += score[i];
		}
		average /= 5;
		System.out.println(average);
	}

}

Measured memory_bytes: 26104
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H == 0 && W == 0) break;
			
			for(int i=0; i < H; i++){
				for(int j=0; j < W; j++){
					if(i % 2 == 0 && j % 2 == 0 || i % 2 == 1 && j % 2 == 1)
						System.out.print("#");
					else System.out.print(".");
					
				}
				System.out.println("");
			}
		System.out.println("");
	    }
	}
}


Measured memory_bytes: 35076
import java.util.Scanner;

//Milky Way
public class Main{

	final double EPS = 1e-10;
	
	double dot(double[] a, double[] b){
		return a[0]*b[0]+a[1]*b[1];
	}
	double cross(double[] a, double[] b){
		return a[0]*b[1]-a[1]*b[0];
	}
	double norm(double[] a, double[] b){
		return Math.hypot(a[0]-b[0], a[1]-b[1]);
	}
	double[] sub(double[] a, double[] b){
		return new double[]{a[0]-b[0], a[1]-b[1]};
	}
	double ex(double[] a, double[] b, double[] c){
		double[] s1 = sub(b, a), s2 = sub(c, a);
		return cross(s1, s2);
	}
	boolean crossing(double[] a, double[] b, double[] s, double[] t){
		if(Math.abs(cross(sub(b, a), sub(t, s)))<EPS){
			return Math.min(dist(a, b, s), Math.min(dist(a, b, t), Math.min(dist(s, t, a), dist(s, t, b))))<EPS;
		}
		if(ex(a, b, s)*ex(a, b, t)>0)return false;
		if(ex(b, a, s)*ex(b, a, t)>0)return false;
		if(ex(s, t, a)*ex(s, t, b)>0)return false;
		return ex(t, s, a)*ex(t, s, b)<EPS;
	}
	double dist(double[] a, double[] b, double[] p){
		if(dot(sub(b, a), sub(p, a))<EPS)return norm(a, p);
		if(dot(sub(a, b), sub(p, b))<EPS)return norm(b, p);
		return Math.abs(cross(sub(b, a), sub(p, a)))/norm(a, b);
	}
	double dist(double[] a, double[] b, double[] s, double[] t){
		if(crossing(a, b, s, t))return 0;
		return Math.min(dist(a, b, s), Math.min(dist(a, b, t), Math.min(dist(s, t, a), dist(s, t, b))));
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int[][] seg = {{0, 2},{0, 3},{1, 4},{1, 3},{2, 4}};
		for(;;){
			int n = sc.nextInt(), S = sc.nextInt(), T = sc.nextInt();
			if((n|S|T)==0)break;
			S--; T--;
			double[] cx = new double[n], cy = new double[n], a = new double[n], r = new double[n];
			for(int i=0;i<n;i++){
				cx[i] = sc.nextDouble(); cy[i] = sc.nextDouble(); a[i] = sc.nextDouble(); r[i] = sc.nextDouble();
			}
			double[][][] p = new double[n][5][2];
			for(int i=0;i<n;i++){
				for(int k=0;k<5;k++){
					double x = -Math.sin((a[i]+72*k)*Math.PI/180)*r[i], y = Math.cos((a[i]+72*k)*Math.PI/180)*r[i];
					p[i][k][0] = cx[i]+x; p[i][k][1] = cy[i]+y;
				}
			}
			double[][] wf = new double[n][n];
			for(int i=0;i<n;i++)for(int j=0;j<n;j++)wf[i][j]=1<<29;
			for(int i=0;i<n;i++)wf[i][i]=0;
			for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
				double min = 1<<29;
				for(int k=0;k<5;k++){
					double[] A = p[i][seg[k][0]], B = p[i][seg[k][1]];
					for(int m=0;m<5;m++){
						double[] C = p[j][seg[m][0]], D = p[j][seg[m][1]];
						min = Math.min(min, dist(A, B, C, D));
					}
				}
				wf[i][j] = wf[j][i] = min;
			}
			for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)wf[i][j]=Math.min(wf[i][j], wf[i][k]+wf[k][j]);
			System.out.printf("%.10f\n", wf[S][T]);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

/*
,,,,
　　　　　　　　　　　　　　　　　　　　　　　　　　,.斗*''“i:i:{
　　　　　　　　　　　　　,.　｡. . . * : : : ''' : : : :” :”“ ''ｰ - 弋,,_
　　　　　 　 　 ,.斗*''“ : : : : : : : : : : : : : ' ' ' ' ' ' : : : : : : : : : : :”: '':* ｡ ,
　　　 ,.斗*''“ ” ＼：　　 ”・・． ' ' ' '　　　　　　　　 ' ' ' ' : : : : : : : : : : : : ”ミ*｡,,,,,,　　　　　　 　 　 　 ＿
　　く.　 ◎　 ﾞ:.ﾞ:..　ﾟ:,　:　───────────　　　--　　,,,,,,__ ' ' ' :.:.:.:.:.”≧s｡.　　＿,,,｡s*i:i:i:i:<
　　ﾏ*s｡ :,　 }　ﾟ:,　 :}　　　　　　　　　　　　　　　　　　　　　　　　　　　　”　''　-　”””：：”：：`*｡i:i:i:i:i:i:i;:’
　　　` .｡`　 ,　,ノ ／｡ ,,,_　　　　　　　　　　　　　　　　　　　　　　　　　　　　　＿＿`　　} }　　ﾉi:i:i:i:i:ﾂ
　　　　　 `　*　｡　　`*｡i:i:i::*=-　　　　　　　　　　　＿＿　　　　　　,,,....｡s*'i,:’　　　”`*｡＿,*’i:i:i:i:r’
　　　　　　　　　　　”　─ --　　　　｡｡｡｡｡　　 -　－`''''''''ヽ ─ '''”　　　｀ｰ“　　　　　　　`*｡i:i:i:i:i:i:
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`*｡i:i:::
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　`*ﾟ:,
         fozubaoyou    no BUGs alive!
*/

typedef long long ll;

//{
#define mp make_pair
#define nsort(a) sort(a.begin(),a.end())
#define rsort(a) sort(a.rbegin(),a.rend())
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define dumo dump
#define hi debug("hi");
//}

#define debug_interval ','
#define dump_interval endl
#define debug_toggle 0

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cout<<endl;}
template<class...A> inline void debug_rest() {cout<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cout<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cout<<first,debug_rest(rest...);}
//}

int n,f,s;

vector<int> p,q;


int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int tempo;
        cin>>tempo;
        p.push_back(tempo);
        q.push_back(tempo);
    }
    nsort(p);
    f=p[n/2-1];
    s=p[n/2];
    if(f==s){
        for(int i=0;i<n;i++){
            dump(f);
        }
        return 0;
    }
    for(int i=0;i<n;i++){
        if(q[i]<=f)dump(s);
        else dumo(f);
    }
}


Measured memory_bytes: 3948
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int main() {
    int m = 0;
	string S, T;
	cin >> S >> T;
    for (int i = 0; i <= S.length() - T.length(); ++i){
        
        int res = 0;
        for (int j = 0; j < T.length(); ++j){
            if (S[i+j] == T[j]) res++;
        }
        m = max(m, res);
    }

    cout << T.length() - m << endl; 
	return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>

int a[2005];

int main(){

	int N,Z,W;

	scanf("%d %d %d",&N,&Z,&W);

	int i;
	for(i=1;i<=N;i++){
		scanf(" %d",&a[i]);
	}

	if(N==1){
		printf("%d\n",abs(a[N]-W));
	}
	else{
		if(abs(a[N]-W)>=abs(a[N]-a[N-1])){
			printf("%d\n",abs(a[N]-W));
		}
		else{
			printf("%d\n",abs(a[N]-a[N-1]));
		}
	}

	return 0;
}

Measured memory_bytes: 128
N, M, C = map(int, input().split())
B_list = list(map(int, input().split()))
A_list = []

for i in range(N):
    A_list.append(list(map(int, input().split())))

# print("==================")
# print(N, M, C)
# print("==================")
# print(B_list)
# print("==================")
# print(A_list)
# print("==================")

success_count = 0

for my_list in A_list:
    num = 0
    for i in range(len(my_list)):
        num = num + my_list[i] * B_list[i]
    num = num + C

    if num > 0:
        success_count = success_count + 1

print(success_count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9
#define f first
#define s second

typedef long long ll;

using namespace std;

const int N = 1e5;
int a[N+5];

int main()

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

    int n;
    string s;
    double x, ans = 0;

    cin >> n;

    while (n--) {

        cin >> x >> s;

        if (s == "BTC") ans+=x*380000.0;
        else ans+=x;
    }

    cout << fixed << setprecision(10) << ans;

    return 0;
}



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

using namespace std;

#define ll long long
#define pb push_back

ll x, y;

vector <int> a[10];

int main(){
    for (int i = 1; i <= 3; i++){
        cin >> x >> y;
        a[x].pb(y);
        a[y].pb(x);
    }

    for (int i = 1; i <= 4; i++){
        if (a[i].size() == 3 || a[i].size() == 0){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T&a,T b){if(a>b){a=b;return 1;}return 0;}
typedef long long ll;

int n,k,c;
string s,t;

int main() {
  cin >> n >> c >> k;
  int t[n];
  rep(i,n) cin >> t[i];
  sort(t,t+n);
  int ans=0,sum=0,time;
  rep(i,n){
    if(!sum) sum++,time=t[i]+k;
    else if(sum<c && t[i]<=time) sum++;
    else if(t[i]>time) sum=1,ans++,time=t[i]+k;
    if(sum==c) sum=0,ans++;
    if(i==n-1 && sum>0) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
// " --- IN THE NAME OF ALLAH --- " // ;)
// ------------sphr_agz------------ // ;)

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <list>
#include <stack>
#include <bitset>
#include <ctime>
using namespace std;
 
typedef long double ld;
typedef long long int lli;
typedef pair <lli, pair <lli, lli> > pii;
#define pb(x) push_back(x)
#define recout(x) return cout << (x), 0
#define f first
#define s second
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define stp(x) cout << setprecision(x) << fixed
#define mk make_pair
const lli N = 1e6 + 10, N2 = 5e3 + 10, delta = 46639, mod = 1e9 + 7, oo = 1e16, LOG = 20;
const ld PI = 3.141592653589793;

//lli a[N];

int main(){
	lli n, m;
	cin >> n >> m;
	lli ans = (n * (n - 1)) / 2;
	ans += (m * (m - 1) / 2);
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
import sys
K=int(input())
L=[1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99,199,299,399,499,599,699,799,899,999]
L=set(L)
for i in range(17):
    for j in range(i*10):
        L.add(pow(10,i) * j + pow(10,i)-1)
L=list(L)
L.sort()
def f(k):
    a=0
    s=k
    while s>0:
        a+=(s %10)
        s=(s - s%10)//10
    return k/a
kou=[]
i=0
while i<len(L):
    flag = True
    for j in range(i+1,len(L)):
        if f(L[i])>f(L[j]):
            flag = False
            break
    if flag:
        kou.append(L[i])
    i +=1
ans=kou[:K]
print('\n'.join(map(str,ans)))

Measured memory_bytes: 42716
#define DEBUG
#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std; using __gnu_cxx::power;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1; const double eps = 1e-6, ldeps = 1e-9;
#define all(x) begin(x), end(x)
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
#define TCC template<class C
struct Dbg { static constexpr auto &os = cout;   // replace by cerr in interactive.
#define ENI typename enable_if<
#define DTOR , Dbg&>::type operator<<
#define RIS return *this
TCC> static auto o(C *x)->decltype(os << *x, 0);
TCC> static char o(...);
TCC> ENI sizeof o<C>(0)!=1 DTOR(const C &x) {os<<x; RIS;}
TCC> Dbg &dump(C b, C e) {
    int ii = 0;
    for(C i = (os << "\n[", b); i!=e and ii<26; i++, ii++) *this << ", "+2*(i==b) << *i;
    RIS << ']';
}
TCC> ENI sizeof o<C>(0)==1 DTOR(const C &x) {
    return dump(all(x));
}
TCC, size_t X> ENI !is_same<C, const char>::value DTOR(C (&x)[X]) {
    return dump(all(x));
}
TCC, class D> Dbg &operator<<(const pair<C, D> &x) {RIS<<'{'<<x.first<<", "<<x.second<<'}';}
Dbg &operator<<(ostream&(*x)(ostream&)) { os << x; RIS; }
} dbg;
void err(istringstream *iss) { delete iss; }
TCC, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args...);
}
#ifdef DEBUG
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl
#else
#define bug(args...) 0
#endif
#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));
int T = 1, Q, cn;
const int inf = 1000000007, mxn = 200005;

int n,K,a[mxn];

signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11), cout.setf(ios::fixed);
    // cin >> T;
    auto inputAll = [&]()->void {
        
    };
    auto kase = [&]()->void {
        // cout << "Case " << cn << ": ";
        cin>>n>>K;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=K+1;i<=n;i++)cout<<(a[i]>a[i-K] ? "Yes" : "No")<<'\n';
    };
    auto resetAll = [&]()->void {
        
    };
    while (cn++!=T) inputAll(), kase(), resetAll();
}


Measured memory_bytes: 4356
/*
   TASK: nocows
   LANG: C++14
 */

#include "bits/stdc++.h"
typedef long long ll;
typedef long double ld;

using namespace std;
#define finish(x) return cout << x, 0;

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }

const string USCAO_TAG = "nocows";
void usaco() { setIn(USCAO_TAG + ".in"); setOut(USCAO_TAG + ".out"); }
/*
template<typename... Args>
void print(Args... args) {
	((std::cout << args << " "), ...);
}
*/
ll a[100001];
ll dp[100001];

int main() {
	//usaco();
	#ifndef ONLINE_JUDGE
	//setIn("in.txt");
	#endif

	int n, k;
	cin >> n >> k;

	memset(dp, 0x3f3f3f3f, sizeof dp);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	dp[n] = 0;

	for(int i = n - 1; i >= 1; i--){
		for(int j = 1; i + j <= n && j <= k; j++){
			dp[i] = min(dp[i], dp[i + j] + abs(a[i] - a[i + j]));
		}
	}

	cout << dp[1];
}


Measured memory_bytes: 1792
n=int(input())
A=list(map(int,input().split()))
B=[0]*3
ans=1
for i in range(n):
  a=0
  for j in range(3):
    if A[i]==B[j]:
      a=a+1
  ans=ans*a
  for j in range(3):
    if A[i]==B[j]:
      B[j]=B[j]+1
      break
print(ans%(10**9+7))

Measured memory_bytes: 13964
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct stations
{
    long c;
    long s;
    long f;
} station;
int main()
{
    station stat[501];
    long time[501],t;
    long n,i,j,k;
    while(scanf("%ld",&n)!=EOF)
    {
        for(i=0; i<n-1; i++)
        {
            scanf("%ld%ld%ld",&stat[i].c,&stat[i].s,&stat[i].f);
            time[i]=0;
        }
        time[n-1]=0;
        for(i=0; i<n-1; i++)
        {
            time[i]+=stat[i].s;
            for(j=0; j<=i; j++)
            {
                if(i!=j)
                {
                    t=time[j]-stat[i].s;
                    if(t<0)
                    {
                        time[j]=stat[i].s;
                    }else if(t%stat[i].f!=0)
                    {
                        t=((long)t/stat[i].f+1)*stat[i].f;
                        time[j]=stat[i].s+t;
                    }
                }
                //t=time[j]-stat[i].c-stat[i].f;
                time[j]+=stat[i].c;
            }
        }
        for(i=0; i<n; i++)
        {
            printf("%ld\n",time[i]);
        }
    }
    return 0;
}



Measured memory_bytes: 128
N,A,B=$<.read.split.map(&:to_i)
require 'openssl'
MOD=10**9+7

def pow(a,b,mod)
    a.to_bn.mod_exp(b.to_bn,mod).to_i
    # res = 1
    # while 0 < b
    #     res = res * a % mod if b & 1 == 1
    #     a = a * a % mod
    #     b >>= 1
    # end
    # res
end

def inv(a,mod)
    pow(a,mod-2,mod)
end

def comb(a,b,mod)
    x = (a-b+1..a).inject(1) {|n,x| n*x%mod }
    y = (1..b).inject(1) {|n,x| n*x%mod }
    x * inv(y,mod) % mod
end

ret = (pow(2,N,MOD) - 1 - comb(N,A,MOD) - comb(N,B,MOD)) % MOD
puts ret

Measured memory_bytes: 5864
r, c = map(int, input().split())
_ = list()
__ = [0 for i in range(c + 1)]
for i in range(r):
    _.append(list(map(int, input().split())))
    _[i].append(sum(_[i]))
    __ = [(__[j] + _[i][j]) for j in range(c + 1)]
    print(" ".join(map(str, _[i])))
print(" ".join(map(str, __)))


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

uint readNumber() {
	return readln.chomp.to!uint;
}

void main() {
	uint[3 * 3] numbers;
	bool[3 * 3] checked;

	size_t contain(uint x,out size_t index) {
		foreach (size_t i, n;numbers) {
			if (n == x) {
				index = i;
				return true;
			}
		}

		return false;
	}

	bool isBingo() {
		auto c = checked;

		if (c[0] && c[1] && c[2]) return true;
		if (c[3] && c[4] && c[5]) return true;
		if (c[6] && c[7] && c[8]) return true;

		if (c[0] && c[3] && c[6]) return true;
		if (c[1] && c[4] && c[7]) return true;
		if (c[2] && c[5] && c[8]) return true;
 
		if (c[0] && c[4] && c[8]) return true;
		if (c[2] && c[4] && c[6]) return true;

		return false;
	}
	
	foreach (i;0..3) {
		numbers[i * 3..(i + 1) * 3] = readln.chomp.split(" ").map!(to!uint).array;
	}

	auto n = readNumber;
	auto r = (() => readln.chomp.to!uint).repeat(n).map!"a()";

	foreach (x;r) {
		size_t found;

		if (contain(x, found)) {
			checked[found] = true;
		}
	}
	if (isBingo) {
		writeln("Yes");
	} else {
		writeln("No");
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;
 
#define pb push_back
#define popb pop_back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair 
#define mt make_tuple
#define fi
#define se second
 
#define forz(i,n) for(long long int i=0;i<n;i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) 
 
using namespace std;
 
 
int main(){
//	ios_base::sync_with_stdio(0);
	lli n, k, m1, m2, m3, m4, m5 = 10000000;
	cin >> n >> k;
	std::vector<int> v(k, 0);
	forz(i, k)
	{
		cin >>v[i];
	}
	sort(v.begin(), v.end());
	// if (k == 1)
	// {
	// 	cout << "0"<<endl;
	// }

	
		m1 = v[k-1] -v[0];
		m2 = v[k-2]+n - v[k-1];
		m4  = min(m1, m2);
		if (min(m1 , m2) > n/2)
		{
			forz(i, k-1)
			{
				if ((v[i+1]- v[i]) <= n)
				{
					m3 = v[i]+n	- v[i+1];
					if (m5 > m3)
					{
						m5 = m3;
					}
					

				}	
			}
				
		}

		cout << min(m4, m5)  << endl;
	
	
	return 0;

}


Measured memory_bytes: 1024
import java.util.Scanner;
class Main{
    public static void main(String[] args) {
        Scanner scn=new Scanner(System.in);
        String time=scn.next().substring(5);
        if(time.charAt(0)=='1'||Character.getNumericValue(time.charAt(1))>4) {
            System.out.println("TBD");
        }else{
            System.out.println("Heisei");
        }
    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
main(){
  int t,a=0,m=11,k=5;
  while(k--&&cin>>t){a+=(t+9)/10*10;if(t%10!=0)m=min(m,t%10);}
  cout<<(m!=11?a-10+m:a)<<endl;
}


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

int main(){
	int a, b, c;
	cin >> a;
	cin >> b;
	cin >> c;
	if (a < b){
		if (b < c){
			cout << a << " " << b << " " << c << endl;
		}
		else if (a < c){
			cout << a << " " << c << " " << b << endl;
		}
		else{
			cout << c << " " << a << " " << b << endl;
		}
	}
	else if (a < c){
		cout << b << " " << a << " " << c << endl;
	}
	else if (c < b){
		cout << c << " " << b << " " << a << endl;
	}
	else{
		cout << b << " " << c << " " << a << endl;
	}
	return 0;
}

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

int main(){
    int N;
    cin >> N;

    char s[N];
    int bw=0, fe=0, min;
    for(int i=0;i<N;i++){
        cin >> s[i];
        if(i>0 && s[i] == 'E') fe++;
    }
    min = fe;
    for(int i=1;i<N;i++){
        if(s[i-1]=='W') bw++;
        if(s[i]=='E') fe--;
        if((fe+bw)<min) min = fe + bw;
    }
    cout << min <<"\n";
    return 0;
}


Measured memory_bytes: 512
n, k, s = map(int, input().split())

# 1. 全部10**9
# 2. s=10**9の時, 他は1でok

if s == 10 ** 9:
    a = [5] * n
else:
    a = [10 ** 9] * n
for i in range(k):
    a[i] = s
print(*a)


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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true; } return false; }

//INT_MAX	2,147,483,647 = 2*1.0e9

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int N, M; cin >> N >> M;

    long long xyz[3][1010];
    
    for(int i = 0; i < N; i++) cin >> xyz[0][i] >> xyz[1][i] >> xyz[2][i];

    long long ans = 0;

    for(int bit = 0; bit < (1<<3); bit++){
        vector<long long> s(N);
        for(int j = 0; j < N; j++){
            for(int i = 0; i < 3; i++){
                if((bit>>i) & 1) s[j]+= xyz[i][j];
                else s[j]-= xyz[i][j];
            }
        }
        sort(s.rbegin(), s.rend());
        long long ansTmp = 0;
        for(int m = 0; m < M; m++)ansTmp += s[m]; 
        if(ansTmp > ans) ans = ansTmp;
    }    

    cout << ans << endl;
    return 0;
}


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

using namespace std;
#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,a) REP(i,0,(int)a-1)
#define FORD(i,a) REV(i,(int)a-1,0)
#define PB push_back
#define POB pop_back
#define FI first
#define SE second
#define MP make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;
typedef pair < ll , ll > pll;

const double PI = acos(-1);
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
	

ll addMod(ll a, ll b){
	if(a + b >= MOD) return a + b - MOD;
	return a + b;
}

ll mulMod(ll a, ll b){
	return (a*b)%MOD;
}

ll fast(ll a, ll b){
	if(b == 0) return 1;
	ll tmp = fast(a,b/2);
	tmp = mulMod(tmp,tmp);
	if(b%2 == 1) tmp = mulMod(tmp,a);
	return tmp;
}

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

//////////////////////////////////////////////

ll lb, ub, a, b;

ll calculate(ll lb, ll ub, ll x){
	return ub / x - (lb-1) / x;
}

ll solve(){
	ll lcm = a * b / GCD(a,b);
	ll ret = calculate(lb,ub,a) + calculate(lb,ub,b) - calculate(lb,ub,lcm);
	return ub - lb + 1 - ret;
}

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> lb >> ub >> a >> b;
	cout << solve() << endl;
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))
l=[1]           
seen={}
k=1
for i in range (K):
  if not k in seen.keys():
      seen[k]=i
      k=A[k-1]
      l.append(k)
  else:
    r_start=seen[k]
    roop=i-r_start
    K=(K-r_start)%roop+r_start
    break
ans=l[K]
print(ans)

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

#define INF (2e9)
#define FOR(i, a, b) for (ll (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<ll>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;
using vai = va<ll>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template<class T>
void DumpRow(const T& A) {
    for (const auto& value : A)
        cout << value << "\n";
}

template<class T>
void DumpColumn(const T& A) {
    auto isFirst = true;
    for (const auto& value : A) {
        if (isFirst) {
            cout << value;
            isFirst = false;
        } else {
            cout << " " << value;
        }

    }
    cout << endl;
}

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

    ll n;
    cin >> n;
    auto v = Read(n);

    v.erase(unique(ALL(v)), v.end());

    DumpColumn(v);
    return 0;
}



Measured memory_bytes: 3608
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}

int64 dp[101][101010];

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

  int n, W; cin >> n >> W;
  vector<int64> w(n), v(n);
  for (int i = 0; i < n; ++i) cin >> w[i] >> v[i];

  fill(dp[0], dp[101], (int64) 0);

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= W; ++j) {
      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[n][W]);

  return 0;
}

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

#define ll long long

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

	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;

	int aa[a], bb[b], cc[c + x + y];
	for (int i = 0; i < a; ++i) cin >> aa[i];
	for (int i = 0; i < b; ++i) cin >> bb[i];
	for (int i = 0; i < c; ++i) cin >> cc[i];

	sort(aa, aa + a, greater<int>());
	sort(bb, bb + b, greater<int>());

	for (int i = 0; i < x; ++i) cc[c + i] = aa[i];
	for (int i = 0; i < y; ++i) cc[c + x + i] = bb[i];

	sort(cc, cc + c + x + y, greater<int>());

	cout << accumulate(cc, cc + x + y, 0LL);
}


Measured memory_bytes: 2176
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        int t = sc.nextInt();
        
        if(x > t){
            System.out.println(x - t);
        }else{
            System.out.println(0);
        }
    }
}

Measured memory_bytes: 21844
i,k,m,t,a[100];main(n){while(scanf("%d%d",&n,&m),n|m){for(i=0;i<n*m;scanf("%d",&t),a[i++%m]+=t);n=m;while(n--){for(t=i=0;i<m;++i)t=t<a[i]?a[k=i]:t;printf("%d%c",k+1,n?32:10),a[k]=0;}}}

Measured memory_bytes: 416
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <map>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

template<typename T>
void inputVector(vector<T> * p, int a){
    rep(i, a){
        T input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

#define Max 110000
int N;
int a[Max], b[Max], c[Max];
ll dp[3][Max];

int main(int argc, const char * argv[]) {
    N = inputValue();
    rep(i, N) {
        a[i] = inputValue();
        b[i] = inputValue();
        c[i] = inputValue();
    }
    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];

    repd(i, 1, N){
        dp[0][i] = a[i] + max(dp[1][i-1], dp[2][i-1]);
        dp[1][i] = b[i] + max(dp[0][i-1], dp[2][i-1]);
        dp[2][i] = c[i] + max(dp[0][i-1], dp[1][i-1]);
    }

    ll ans = max(dp[0][N-1], dp[1][N-1]);
    ans = max(ans, dp[2][N-1]);
    output(ans);

    return 0;
}

Measured memory_bytes: 3840
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce

# a, b = [int(v) for v in input().split()]


def main():
    mod = 1000000007

    N = int(input())
    A = [int(v) for v in input().split()]

    dig = 60

    ans = 0
    for i in range(dig + 1):
        mask = 1 << i
        zero = sum(1 for a in A if a & mask == 0)
        ans += zero * (N - zero) * mask
        ans %= mod

    print(ans % mod)


main()


Measured memory_bytes: 42156
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    s =input()
    k = int(input())
    cnt = 0
    mci = 0
    while cnt < k:
        mci = min([ord(i) for i in s if ord(i) > mci])
        a = set()
        for i in range(len(s)):
            if ord(s[i]) != mci:
                continue
            for j in range(1, 6):
                a.add(s[i:i+j])
        if len(a) + cnt < k:
            cnt += len(a)
        else:
            print(sorted(a)[k-cnt-1])
            return


main()


Measured memory_bytes: 9460
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    long long k;
    cin>>n>>k;
    long long sum=0;
    long long c[100001]={0};
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        c[a]+=b;
    }
    int i;
    for(i=0;i<100001;i++){
        if(c[i]!=0){
            sum+=c[i];
            if(k<=sum)break;
        }
    }
    cout<<i<<endl;
    return 0;
}


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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b); }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int x,y;
  cin>>x>>y;
  ll ans=0;
  if(x==1) ans+=300000;
  else if(x==2)ans+=200000;
  else if(x==3)ans+=100000;
  
  if(y==1) ans+=300000;
  else if(y==2)ans+=200000;
  else if(y==3)ans+=100000;
  
  if(x==y&&x==1)ans+=400000;
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;

int main() {
  string s;
  int p;
  map<string,set<int> > m;
  while(cin >> s >> p) {
    m[s].insert(p);
  }
  for(map<string,set<int> >::iterator i = m.begin();
      i != m.end(); ++i) {
    cout << i->first << endl;
    bool first = true;
    for(set<int>::iterator j = i->second.begin();
        j != i->second.end(); ++j) {
      if(first) first = false;
      else cout << " ";
      cout << *j;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1228
package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

func main(){
    n := nextInt()
    a := nextInts(n)
    fmt.Printf("%v %v %v\n", Min(a), Max(a), Sum(a))
}
 
/* templates */
 
func Max(a []int) int {
    r := a[0]
    for i := 0; i < len(a); i++ {
        if r < a[i] {
            r = a[i]
        }
    }
    return r
}
 
func Min(a []int) int {
    r := a[0]
    for i := 0; i < len(a); i++ {
        if r > a[i] {
            r = a[i]
        }
    }
    return r
}
 
func Sum(a []int) (r int) {
    for i := range a {
        r += a[i]
    }
    return r
}
 
func Abs(a float64) float64 {
    if a < 0 {
        return -a
    }
    return a
}
 
type Pair struct {
    a, b int
}
 
type Pairs []Pair
 
func (p Pairs) Len() int {
    return len(p)
}
 
func (p Pairs) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}
 
func (p Pairs) Less(i, j int) bool {
    return p[i].b < p[j].b
}
 
var nextReader func() string
 
func init() {
    nextReader = NewScanner()
}
 
func NewScanner() func() string {
    r := bufio.NewScanner(os.Stdin)
    r.Buffer(make([]byte, 1024), int(1e+11))
    r.Split(bufio.ScanWords)
    return func() string {
        r.Scan()
        return r.Text()
    }
}
 
func nextString() string {
    return nextReader()
}
 
func nextInt64() int64 {
    v, _ := strconv.ParseInt(nextReader(), 10, 64)
    return v
}
 
func nextInt() int {
    v, _ := strconv.Atoi(nextReader())
    return v
}
 
func nextInts(n int) []int {
    r := make([]int, n)
    for i := 0; i < n; i++ {
        r[i] = nextInt()
    }
    return r
}
 
func nextFloat64() float64 {
    f, _ := strconv.ParseFloat(nextReader(), 64)
    return f
}


Measured memory_bytes: 1268
int main(void){
 char a[4];
 int i = 0;
 int bIs1 = 0;
 int bIs9 = 0;
 int bIs7 = 0;
 int bIs4 = 0;
 scanf("%s %s %s %s",&a[0],&a[1],&a[2],&a[3]);
   
 for(i =0; i < 4; i++) {
    if (a[i] == '1') {
       bIs1 = 1;
       break;
   }
}

 for(i =0; i < 4; i++) {
    if (a[i] == '9') {
       bIs9 = 1;
       break;
   }
}

  for(i =0; i < 4; i++) {
    if (a[i] == '7') {
       bIs7 = 1;
       break;
   }
}

  for(i =0; i < 4; i++) {
    if (a[i] == '4') {
       bIs4 = 1;
       break;
   }
}


 if(bIs1 * bIs9 * bIs7 * bIs4) {
    printf("YES\n");
} else {
   printf("NO\n");
}

return 0;
}

Measured memory_bytes: 128
while True:
  a, ope, b = input().split()
  result = 0
  if ope == '?':
    break

  if ope == '+':
    result = int(a) + int(b)
  elif ope == '-':
    result = int(a) - int(b)
  elif ope == '*':
    result = int(a) * int(b)
  elif ope == '/':
    result = int(int(a) / int(b))
  print(result)



Measured memory_bytes: 5592
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<"\n"
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define mp make_pair
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll> tll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
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; 
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
//二項係数 nCr
const int MAX = 700000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(){
  COMinit();
  ll n,m,k;
  cin>>n>>m>>k;
  ll no=COM(n*m-2,k-2);
  ll nn=0;
  rep(i,n){
    nn+=i;
    nn%=MOD;
  }
  ll mm=0;
  rep(i,m){
    mm+=i;
    mm%=MOD;
  }
  ll nnn=0;
  ll mmm=0;
  rep(i,n){
    nnn+=nn;
    nn-=n-1-i;
    if(nn<0) nn+=MOD;
    nnn%=MOD;
  }
  rep(i,m){
    mmm+=mm;
    mm-=m-1-i;
    if(mm<0) mm+=MOD;
    mmm%=MOD;
  }
  ll ans=0;
  ll cu=m*m%MOD;
  cu*=no;
  cu%=MOD;
  cu*=nnn;
  cu%=MOD;
  ll ccu=n*n%MOD;
  ccu*=no;
  ccu%=MOD;
  ccu*=mmm;
  ccu%=MOD;
  ans=ccu+cu;
  ans%=MOD;
  COUT(ans);
}

Measured memory_bytes: 19960