akhauriyash/Code-Regression huggingface dataset:
/* primのアルゴリズム */
#include<iostream>
#include<stdio.h>
using namespace std;


static const int N_MAX=100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int color[N_MAX];
int M[N_MAX][N_MAX];
int d[N_MAX];
int p[N_MAX];
int n;


int prim()
{
    int i,minv,u,v;
    for(i=0;i<n;i++)
    {
        color[i]=WHITE;
        d[i]=INFTY;
        p[i]=-1;
    }
    d[0]=0;

    while(true)
    {
        minv=INFTY;
        //T(最小全域木)に追加するノードuの探索
        for(i=0;i<n;i++)
        {
            //未選択でT-Vの接続がもっとも小さいノードの選択
            if(color[i]!=BLACK && d[i]<minv)
            {
                minv=d[i];
                u=i;
            }
        }

        //もし最小接続コストがINFTYなら探索終了
        if(minv==INFTY) break;

        //Tに追加されたuは選択済みのフラグを立てる
        color[u]=BLACK;

        //元グラフVからu-vで最小のコストのエッジをd[v]に保存
        //親も保存
        //探査はした証拠にGRAYにする
        //ここでの代入操作は次のループで上のfor文内で使われる
        for(v=0;v<n;v++)
        {
            //未選択でuとのエッジが存在するvについて
            if(color[v]!=BLACK && M[u][v]!=INFTY)
            {
                //そのエッジコストがvが記録する
                //T - (V-T)間の最小コストより小さければ
                //エッジコスト更新
                //vの親の更新
                if(M[u][v]<d[v])
                {
                    d[v]=M[u][v];
                    p[v]=u;
                    color[v]=GRAY;
                }
            }
        }

    }

    int sum=0;
    for(i=0;i<n;i++)
    {
        //親が存在すれば、i-p[i]間コストを加算
        if(p[i]!=-1) sum+=M[i][p[i]];
    }
    return sum;
}


int main()
{
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int e;
            scanf("%d",&e);
            M[i][j]=(e==-1) ? INFTY : e ;
        }
    }

    printf("%d",prim());
    printf("\n");

    return 0;
}






Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
int a[3][3],n;
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;

vector<bool> issafe; // issafe[v] := v が壊れていないかどうか

int main() {
  int n,d;
  cin >> n >> d;
  double x[n+1][d+1];
  rep (i,n){
    rep (j,d){
      cin >> x[i][j];
    }
  }
    int cnt=0;
    double ans=0.0;
    rep (i,n){
      for (int j = i+1;j < n;j++){
        rep (k,d){
          ans += (x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
        }
        //cout << floor(sqrt(ans)) << endl;
        if (ceil(sqrt(ans))==floor(sqrt(ans))) cnt++;
        ans = 0;
      }
    }
  cout << cnt << endl;

}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
    String parametre = scan.nextLine();

    String[] element = parametre.split(" ");

    int first = Integer.parseInt(element[0]);
    int second = Integer.parseInt(element[2]);

    int result;

    if (element[1].equals("+")){
      result = first + second;
    }
    else
      result = first - second;

    System.out.println(result);

  }
}


Measured memory_bytes: 9680
#include<iostream>
#include<string>
#include<cmath>
//#include<array>
#include<algorithm>
//#include<deque>
#include<vector>
//#include<utility>
#include<set>
//#include<map>
//#include<list>

using namespace std;

const int MAX_N = 25;
int n, W;
int w[MAX_N], v[MAX_N];

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//int gcd(int x, int y) {
//	int tmp, r;
//	if (x < y) {
//		tmp = x;
//		x = y;
//		y = tmp;
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}

int main(void) {
	int N, A, B,a,b,res = 0;
	cin >> N >> A >> B;
	for (int i = 1; i <= N; i++) {
		a = i;
		b = 0;
		while (1) {
				b += a%10;
				a /= 10;
			if(a == 0){
				break;
			}
		}
		if (b >= A && b <= B) {
			res += i;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define INIT(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define INIT2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define LINY "YES\n"
#define Liny "Yes\n"
#define LINN "NO\n"
#define Linn "No\n"
#define umap unordered_map

ll min(ll x,ll y){return (x<y ? x:y);}
ll max(ll x,ll y){return (x>y ? x:y);}
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a*b /gcd(a,b);}
bool isPrime(int n){if(n<2){return false;}for(int i=2;i<sqrt(n)+1;i++){if(n%i==0) return false;}return true;}

int main(){
  string s,t; cin>>s>>t;
  umap<char,char> mp_trans,mp_ivrs;
  for(char i='a';i<='z';i++){
    mp_trans[i] = '0';
    mp_ivrs[i] = '0';
  }
  bool can = true;
  REP(i,s.size() ){
    char si = s[i];
    char ti = t[i];
    if(mp_trans[si]=='0'){ mp_trans[si]=ti;}
    else if(mp_trans[si]!=ti){can = false; break;}
    if(mp_ivrs[ti]=='0'){ mp_ivrs[ti]=si;}
    else if(mp_ivrs[ti]!=si){can = false; break;}
  }
  cout <<(can?Liny:Linn);
  
}


Measured memory_bytes: 776
#include<iostream>

using namespace std;

int main(){

int A,B;

cin >> A >>B; 

if((A>=2 && A<=13) && (B>=2 && B<=13)){
if(A==B){
  cout << "Draw" << endl;
}else if(A<B){
cout << "Bob" << endl;
}else if(A>B){
cout  << "Alice" << endl;
}
}else if(A==1 && (B>=2 && B<=13)){
cout << "Alice" << endl;
}else if((A>=2 && A<=13) && B==1){
cout << "Bob" << endl;
}else if(A==1 && B==1){
cout << "Draw" << endl; 
}
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,X,m[1000],sum=0,q;
	cin>>N>>X;
	for(int i=0;i<N;i++){
		cin>>m[i];
		sum+=m[i];
	}
	sort(m,m+N);
	q=((X-sum)/m[0])+N;
	cout<<q;
	return 0;
}


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

int main(){
    int n,k,ans=0;
    cin >> n >> k;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a.at(i);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++){
        if(i<(n-k))continue;
        ans+=a.at(i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
mod = 1000000007
n, k = gets.chomp.split(' ').map(&:to_i)

$memo = {}
def combination(n, k)
  $memo[n] = {} if $memo[n] == nil
  $memo[n][k] = 1 if k == 0
  return $memo[n][k] if $memo[n][k] != nil
  combination(n, k - 1) * (n - k) / k
  $memo[n][k] = combination(n, k - 1) * (n - k + 1) / k
end

1.upto(k) do |i|
  puts (combination(n - k + 1, i) % mod) * (combination(k - 1, i - 1) % mod) % mod
end


Measured memory_bytes: 3324
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
????????????
"""
inp = input().strip().split(" ")
n = int(inp[0])
m = int(inp[1])
l = int(inp[2])

# ?????????????????????????¢????
# A[n][m] B[m][l] C[n][l]
A = [[0 for i in range(m)] for j in range(n)]
B = [[0 for i in range(l)] for j in range(m)]
C = [[0 for i in range(l)] for j in range(n)]

# A???????????°??????????????????
for i in range(n):
    inp = input().strip().split(" ")
    for j in range(m):
        A[i][j] = int(inp[j])

# B???????????°??????????????????
for i in range(m):
    inp = input().strip().split(" ")
    for j in range(l):
        B[i][j] = int(inp[j])

# A x B
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
    print(" ".join(map(str,C[i])))

Measured memory_bytes: 8848
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <functional>
#define ll long long int
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
	ll N, M, K, count=0, conb;
	string tenki;
	cin >> tenki;

	if (tenki[0] == 'R'){
		count++;
		if (tenki[1] == 'R'){
			count++;
			if (tenki[2] == 'R'){
				count++;
			}
		}
	}
	else{
		if (tenki[1] == 'R'){
			count++;
			if (tenki[2] == 'R'){
				count++;
			}
		}
		else{
			if (tenki[2] == 'R'){
				count++;
			}
		}

	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 3620
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n:usize,
        m:u64,
        mut ab: [(u64, u64); n],
    }
    ab.sort_by_key(|x| x.0);
    let mut sum=0;
    let mut ans=0;
    for i in 0..n {
        if sum+ab[i].1 > m {
            ans+=ab[i].0 * (m - sum);
            break;
        }else{
            ans+=ab[i].0 * ab[i].1;
            sum+=ab[i].1;
        }
    }
    println!("{}", ans);
    
}

Measured memory_bytes: 6396
#include <iostream>
#include <cstring>

using namespace std;

using ll = long long;
constexpr int MAX = 100;

ll comb[MAX][MAX];

void make_comb()
{
    memset(comb, 0, sizeof(comb));
    comb[0][0] = 1;
    for (int i = 0; i < 65; i++) {
        for (int j = 0; j <= i; j++) {
            comb[i + 1][j]     += comb[i][j];
            comb[i + 1][j + 1] += comb[i][j];
        }
    }
}

void solve(ll N, ll s, ll M, ll n)
{
    while (s < M) {
        ll j = -1;
        for (ll i = n; i <= N; i++) {
            if (s + comb[i][n] >= M) {
                s += comb[i - 1][n];
                j = i;
                break;
            }
        }

        for (int i = 0; i < N - j; i++) {            
            cout << '0';
        }
        
        if (n > 0) {
            cout << '1';
        }

        n--;        
        N = j - 1;
    }

    cout << endl;
}

bool run()
{
    ll N, M;
    cin >> N >> M;
    if (N == 0 && M == 0) {
        return false;
    }

    if (M == 1) {
        cout << string(N, '0') << endl;
        return true;
    }
    
    make_comb();
    
    ll sum = 1;    
    for (ll i = 1; i <= N; i++) {
        sum += comb[N][i];
        if (sum >= M) {
            solve(N, sum - comb[N][i], M, i);
            break;
        }
    }
    return true;
}

int main()
{
    while (run())
        ;    
    return 0;
}

Measured memory_bytes: 3164
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vi v(n);
	REP(i, n)cin >> v[i];
	vi b(n);
	REP(i, n) {
		if (v[i] % 2 == 1) {
			b[i] = 0;
		}
		else {
			int res = 0;
			while (1) {
				if (v[i] & 1 << res) {
					b[i] = res;
					break;
				}
				res++;
			}
		}
	}
	int x = 0;
	REP(i, n) {
		x ^= v[i];
	}

	sort(ALL(b));
	int p = INF;
	int cnt = 0;

	RREP(i, 32) {
		if (x & 1 << i) {
			p = i;
			break;
		}
	}

	RREP(i, p + 1) {
		if (cnt % 2 == 0 && x&(1 << i)) {
			if (binary_search(ALL(b), i)) {
				cnt++;
			}
			else {
				cout << -1 << endl;
				return 0;
			}
		}
		else if (cnt % 2 == 1 && !(x & (1 << i))) {
			if (binary_search(ALL(b), i)) {
				cnt++;
			}
			else {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
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 /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}




#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


  




int main (){
 ll n;
 cin >> n;
 ll sum = 0;
 for (int i = 1;i <= n-1;i++){
   sum+=i;
 }
 cout << sum << endl;
}

Measured memory_bytes: 3576
#include <stdio.h>

int main() {
    int i, m, f, r;
    
    while(1) {
        scanf("%d%d%d", &m, &f, &r);
        
        if (m == -1 && f == -1 && r == -1) break;
        
        if (m == -1 || f == -1) printf("F\n");
        
        else if (m + f >= 80) printf("A\n");
        
        else if (m + f >= 65) printf("B\n");
        
        else if (m + f >= 50) printf("C\n");
        
        else if (m + f >= 30 && r >= 50) printf("C\n");
        
        else if (m + f >= 30 && r < 50) printf("D\n");
        
        else if (m + f < 30) printf("F\n");
    }
    return 0;
}


Measured memory_bytes: 2064
n = int(input())
a = list(map(int, input().split()))
data = [[0]*3 for i in range(n+1)]
mod = 10**9+7
#data[i][0] => max: data[i][1] =>  middle: data[i][2] => min:
ans = 1
for i in range(n):
    tmp = data[i]
    ans *= tmp.count(a[i])
    ans %= mod
    for j in range(3):
        data[i+1][j] = data[i][j]
    for j in range(3):
        if data[i][j] == a[i]:
            data[i+1][j] += 1
            break
print(ans)



Measured memory_bytes: 63428
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

		int[] r = new int[n + 1];
		int[] g = new int[n + 1];
		int[] b = new int[n + 1];
		for (int i = 0; i < n; i++) {
			if (s.charAt(i) == 'R') {
				r[i + 1]++;
			} else if (s.charAt(i) == 'G') {
				g[i + 1]++;
			} else {
				b[i + 1]++;
			}
		}
		for (int i = 1; i <= n; i++) {
			r[i] += r[i - 1];
			g[i] += g[i - 1];
			b[i] += b[i - 1];
		}

		long ans = 0;
		for (int i = 0; i < n; i++) {
			Set<Character> set = new HashSet<>();
			set.add(s.charAt(i));
			for (int j = i + 1; j < n; j++) {
				char sj = s.charAt(j);
				if (!set.contains(sj)) {
					set.add(sj);
					if (!set.contains('R')) {
						ans += r[n] - r[j + 1];
						int k = j + j - i;
						if (k < n && k - j == j - i && s.charAt(k) == 'R') {
							ans--;
						}
					} else if (!set.contains('G')) {
						ans += g[n] - g[j + 1];
						int k = j + j - i;
						if (k < n && k - j == j - i && s.charAt(k) == 'G') {
							ans--;
						}
					} else if (!set.contains('B')) {
						ans += b[n] - b[j + 1];
						int k = j + j - i;
						if (k < n && k - j == j - i && s.charAt(k) == 'B') {
							ans--;
						}
					}
					set.remove(sj);
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 59844
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
int a[507];
int res[507 * 507];
int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n;
	scanf("%d", &n);
	vector<pair<int, int> > go;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		go.push_back(make_pair(a[i], i));
	}
	sort(go.begin(), go.end());
	set<int> poses;
	for (int i = 1; i <= n * n; i++)
	{
		poses.insert(i);
	}
	for (int i = 0; i < (int)go.size(); i++)
	{
		if (i > 0 && go[i].first == go[i - 1].first)
		{
			printf("No\n");
			return 0;
		}
		poses.erase(go[i].first);
		res[go[i].first] = go[i].second;
	}
	for (int i = 0; i < (int)go.size(); i++)
	{
		for (int j = 1; j < go[i].second; j++)
		{
			int x = *poses.begin();
			if (x > go[i].first)
			{
				printf("No\n");
				return 0;
			}
			res[x] = go[i].second;
			poses.erase(x);
		}
	}
	for (int i = (int)go.size() - 1; i >= 0; i--)
	{
		for (int j = 1; j <= n - go[i].second; j++)
		{
			int x = *poses.rbegin();
			if (x < go[i].first)
			{
				printf("No\n");
				return 0;
			}
			res[x] = go[i].second;
			poses.erase(x);
		}
	}
	printf("Yes\n");
	for (int i = 1; i <= n * n; i++)
	{
		printf("%d ", res[i]);
	}
	printf("\n");
}


Measured memory_bytes: 13824
n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[float("inf")]*n
cost[0]=0
for i in range(n-1):
    for j in range(1,min(k+1,n-i)):
        cost[i+j]=min(cost[i+j],cost[i]+abs(h[i+j]-h[i]))

print(cost[-1])

Measured memory_bytes: 55008
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int n;
    ll answer = 0;
    string s;
    cin >> n >> s;

    int R=0,G=0,B=0;
    REP(i,n){
        if(s[i] == 'R')R++;
        else if(s[i] == 'G')G++;
        else B++;
    }
    answer = (ll)R*G*B;
    
    REP(i,n-2){
        FOR(j,i+1,n-1){
            if(s[i]==s[j])continue;
            int diff = j-i;
            if(j+diff < n and s[i]!=s[j+diff] && s[j]!=s[j+diff])answer--;
        }
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

int main(){
    ll N, M;
    cin >> N >> M;
    vll X(M);
    rep(i, M){
        cin >> X[i];
    }
    sort(ALL(X));
    vll Y(M-1);
    rep(i, M-1){
        Y[i] = X[i+1] - X[i];
    }
    sort(ALL(Y));
    ll ans = 0;
    if(N >= M){
        ans = 0;
    }else{
        rep(i, M-N){
            ans += Y[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <stdio.h>
  int main(){
    int n,a[200]={},count=0,even=0;
    scanf("%d¥n",&n);
     for(int i=0;i<n;i++){
     scanf("%d",&a[i]);
     }
     do{
       even=0;
      for(int i=0;i<n;i++){
      if(a[i]%2==0)
       even++;
       a[i]/=2;
      }
       if(even==n)
       count++;
      }while(even==n);
    printf("%d",count);
     
    return 0;
  }

Measured memory_bytes: 256
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000
const int mod = INF+7;

int main(){
  int N;
  cin >> N;
  vector<int> H(N);
  rep(i,N){
    cin >> H[i];
  }

  int start=0;
  int end=0;
  int *ans=(int *)malloc(sizeof(int)*N);
  while(1){
    while(start+1<N && H[start+1]<=H[start]){
      start++;
    }
    srep(i, end, start+1){
      ans[i]=start-i;
    }
    if(start==N-1){
      break;
    }
    start++;
    end=start;
  }

  int res=0;
  rep(i,N){
    res=max(res, ans[i]);
  }

  printf("%d\n", res);
}


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

#define watch(x) cout << (#x) << " is " << (x) << endl
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i, st, en) for(int i=st; i<=en; i++)
#define repn(i, st, en) for(int i=st; i>=en; i--)
#define sq(a) (a*a)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll mod = 1e9+7;

ll max_self(ll &a, ll b){
    a = max(a, b);
}

void solve(){
    ll n, W;
    cin>>n>>W;
    vector<ll> dp(W + 1, 0ll);
    /// dp[i] = max. value with knapsack weight not exceeding i
    fr(item, n){
        ll weight, val;
        cin>>weight>>val;
        for(ll weights_already = W - weight; weights_already >= 0; weights_already--){
            max_self(dp[weights_already + weight], dp[weights_already] + val);
        }
    }

    ll ans = 0ll;
    for(ll w = 0ll; w <= W; w++){
        max_self(ans, dp[w]);
    }
    cout<<ans;
}

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

    ll t = 1;
    //  cin>>t;
    while(t--){
        solve();
    }

    return 0;
}



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

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

    vector<int> seen(n+1, -1);

    vector<ll> a(n+1,0);

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

    ll first = 1;
    ll now = 1;
    ll cnt = 0;
    vector<ll> place;

    bool re = false;
    int roop;
    while(!re){
        cnt++;
        now = a[now];
        //cout << now << endl;
        if(seen[now] != -1){
            re = true;
            break;
        }
        seen[now] = cnt-1;
        place.push_back(now);
    }

  //  cout << cnt << endl;

 /*   for(int i = 0; i < place.size(); i++){
        cout << place[i] << endl;
    }
*/
    roop = seen[now];
//    cout << roop << endl;

    if(k >= place.size()){
        ll num = (k-roop-1)%(place.size()-roop);
        cout << place[roop+num];
    }
    else{
        ll num = (k-1)%cnt;
        cout << place[num];
    }
}

Measured memory_bytes: 7684
#include<set>  
#include<map>  
#include<cstdio>  
#include<cmath>  
#include<queue>
#include<vector>  
#include<cstring>  
#include<climits>  
#include<iostream>  
#include<algorithm>  
using namespace std; 
#define eps 1
#define MAXN 100000
int read(){  
	int f=1,x=0;  
    char c=getchar();  
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}  
    while('0'<=c&&c<='9') x=x*10+c-'0',c=getchar();  
    return f*x;  
}
int main(){
	int a=read(),b=read(),k=read(),tmp=b-k+1;
	if(b-a+1<=k)
	{
		for(int i=a;i<=b;i++)
			printf("%d\n",i);
		return 0;
	}
	for(int i=a;i<=a+k-1;i++)
		printf("%d\n",i);
	if(b-k+1<=a+k-1) tmp=a+k;
	for(int i=tmp;i<=b;i++)
		printf("%d\n",i);
	return 0;
}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG true
#define LL long long
#define MOD 1000000007

//cout << (c)?"Yay!":":(" << endl;

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    int k;
    cin >> k;
    long long int sum = 0;
    REP(a, 1, k+1)
    {
        REP(b, 1, k+1)
        {
            REP(c, 1, k+1)
            {
                int d = gcd(a, gcd(b, c));
                sum += d;
            }
        }
    }

    cout << sum << endl;
    return 0;
}


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

#define mod 1000000007

using namespace std;

int main(void){
	
	int N;
	
	int64_t count=0;
	
	cin >> N;
	
	int a[3*N];
	
	for(int i=0; i<3*N; i++)
		cin >> a[i];
	
	sort(a, a+3*N, greater<int>());
	
	for(int i=1; i<N*2; i+=2)
		count += a[i];
	
	cout << count;
	
	return 0;
}

Measured memory_bytes: 1408
Module _20190422

    Sub Main()

        Dim sRead As String = Console.ReadLine()

        Dim iInt1 As Integer = sRead.Split(" ")(0)
        Dim iInt2 As Integer = sRead.Split(" ")(1)

        If iInt2 Mod iInt1 = 0 Then

            Console.WriteLine(iInt1 + iInt2)

        Else

            Console.WriteLine(iInt2 - iInt1)

        End If

    End Sub

End Module

Measured memory_bytes: 13268
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rpd(i,a,b) for(register int i=a;i>=b;--i)
#define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
typedef long long ll;
const int N=16+5;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll n;int m,a[N],ans;
int main(){
    cin>>n;
    while(n>=10LL)ans+=n%10LL,m+=1,n/=10LL;
    printf("%d\n",max(ans+(int)n,(int)(n-1)+m*9));
    //system("pause");
    return 0;
}

Measured memory_bytes: 256
//C

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

int main(){
    int N; cin >> N;
    long long A[N+1];
    long long B[N];
    for(int i=0;i<N+1;i++) cin >> A[i];
    for(int i=0;i<N;i++) cin >>B[i];

    long long ans = 0;

    for(int i=0;i<N;i++){
        long long beat;
        if(A[i] < B[i]) beat=A[i];
        else beat = B[i];
        A[i] -= beat;
        B[i] -= beat;
        ans += beat;

        if(A[i+1] < B[i]) beat = A[i+1];
        else beat = B[i];
        A[i+1] -=beat;
        B[i] -= beat;
        ans += beat;
    }
    cout << ans << endl;
}

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

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

    ll A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    ll ans = A * X + B * Y;

    ll b = C * X * 2;
    if(X < Y) b += B * (Y - X);

    ans = min(ans, b);

    ll c = C * Y * 2;
    if(X > Y) c += A * (X - Y);

    ans = min(ans, c);

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		int count = 0;
		
		for(int i = 1; i < n; i++) {
			count += (n-1)/i;
		}
		System.out.print(count);

	}

}

Measured memory_bytes: 35600
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, k;
	cin >> n >> m >> k;	
	vector<vector<int>> a(n, vector<int> (m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			a[i][j] = (c == '#');
		}
	}
	int ans = 0;
	for (int mask = 0; mask < (1 << (n + m)); mask++) {
		int c = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				c += (a[i][j] && !((mask >> i) & 1) && !((mask >> (j + n)) & 1));
			}
		}
		ans += (c == k);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define rint register int
#define gc() getchar()
inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}
unordered_map<ll,int> G; ll Ans, S; int n;
int main()
{
	n = read(); G[0] = 1; for(rint i = 1; i <= n; S += read(), Ans += G[S], ++G[S], i++); cout << Ans << endl;





	return 0;
}

Measured memory_bytes: 8520
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<queue>
#include<utility>
using namespace std;

int main(void)
{
    int N, M;
    cin >> N >> M;

    priority_queue<pair<int, int>> task;
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;

        task.push(make_pair(A, 1));
    }

    for (int i = 0; i < M; i++) {
        int B, C;
        cin >> B >> C;

        task.push(make_pair(C, B));
    }

    long long ans = 0;
    while (N > 0) {
        auto p = task.top();
        task.pop();

        long long cnt = min(N, p.second);
        ans += cnt * p.first;
        N -= cnt;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
using namespace std;
#define reg register
#define pb push_back
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
const int MN=1e5+5;
int N,M,id[MN],rk[MN],par[MN];
ll f[MN],sz[MN],A[MN],B[MN],C[MN];
vector<int> G[MN],T[MN];
bool cmp(const int&x,const int&y){return C[x]<C[y];}
int getf(int x){return x==par[x]?x:par[x]=getf(par[x]);}
void rw(ll &x,ll y){if(y<x)x=y;}
void dfs(int x)
{
	#define y T[x][i]
	reg int i;sz[x]=B[x];f[x]=1e15;
	if(!T[x].size())return (void)(f[x]=B[x]+C[x]);
	for(i=T[x].size()-1;~i;--i)dfs(y),sz[x]+=sz[y];
	for(i=T[x].size()-1;~i;--i)rw(f[x],sz[x]-sz[y]+max(C[x],f[y]));
	#undef y
}
int main()
{
	N=read();M=read();
	reg int i,j,x,y;
	for(i=1;i<=N;++i) par[i]=id[i]=i;
	for(i=1;i<=N;++i) A[i]=read(),B[i]=read(),C[i]=max(A[i]-B[i],0LL);
	for(i=1;i<=M;++i) x=read(),y=read(),G[x].pb(y),G[y].pb(x);
	sort(id+1,id+N+1,cmp);
	for(i=1;i<=N;++i)rk[id[i]]=i;
	for(i=1;i<=N;++i)for(j=G[x=id[i]].size()-1;~j;--j)
	{
		y=getf(G[x][j]);
		if(y!=x&&rk[y]<i) par[y]=x,T[x].pb(y);
	}
	dfs(id[N]);
	return 0*printf("%lld\n",f[id[N]]);
}

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


int main(){
    ll h,w,a,b;cin>>h>>w>>a>>b;
    a--;b--;
    rep(i,0,h){
        rep(j,0,w){
            if(i<=b){
            if(j<=a)cout<<0;
            else cout<<1;
            }
            else{
                if(j<=a)cout<<1;
                else cout<<0;
            }
            
        }
        cout<<endl;
    }
}







Measured memory_bytes: 1280
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    K = int(input())
    S = input().strip()
    if len(S) <= K:
        print(S)
    else:
        print(S[:K] + "...")

    return


if __name__ == '__main__':
    main()


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

long long memo[100];
long long in[100];


long long search(int num, long long nokori){

  if(num == 0) return 1;

  long long ans = 0;
  nokori--;
  if(nokori == 0){
    return 0;
  }

  nokori -= memo[num-1];

  if(nokori < 0){
    return search(num-1, nokori+memo[num-1]);
  }

  if(nokori == 0){
    return in[num-1];
  }

  ans += in[num-1] + 1;
  nokori--;
  if(nokori == 0){
    return ans;
  }

  nokori -= memo[num-1];
  if(nokori < 0){
    return search(num-1, nokori+memo[num-1]) + ans;
  }

  return ans + in[num-1];
}

int main(){

  memo[0] = 1;
  in[0] = 1;

  for(int i = 1;i <= 50;i++){
    memo[i] = memo[i-1] * 2 + 3;
    in[i] = in[i-1] * 2 + 1;
  }

  long long n, x;
  cin >> n >> x;

  cout << search(n, x) << endl;

  return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn.{readLine,readInt}

object Main {

  def main(args:Array[String]) = {
    val b = new StringBuilder
    val n = readInt
    for(i<- 1 to n) {
      val p = readLine.split(" ").map(_.toDouble)
      val d = Math.sqrt(Math.pow(p(0)-p(3),2) + Math.pow(p(1)-p(4),2))
      if(d+p(5) < p(2))
        b.append("2\n")
      else if(d+p(2)<p(5))
        b.append("-2\n")
      else if(d > p(2) + p(5))
        b.append("0\n")
      else
        b.append("1\n")
    }
    print(b.result)
  }
}

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

struct UnionFind{
  vector<long long> par;
 
  UnionFind(int n){
    par.assign(n,-1);
  }
 
  void unite(long long x, long long y){
    x=root(x);y=root(y);
    if(x==y) return;
 
    if(par[x]>par[y]){
      swap(x,y);
    }
    par[x]+=par[y];
    par[y]=x;
  }
 
  long long root(long long x){
    if(par[x]<0){
      return x;
    }else{
      return par[x]=root(par[x]);
    }
  }

  int size(long long x) {
    return -par[root(x)];
  }

  bool same(long long x, long long y){
    return root(x)==root(y);
  }
};

int main(){
  long long n,m,x,y,z,ans=0;
  cin >> n >> m;
  UnionFind uf(n);
  for(int i=0;i<m;i++){
    cin >> x >> y >> z;
    x--;y--;
    uf.unite(x,y);
  }
  map<int, int> mp;
  for(int i=0;i<n;i++){
    if(mp[uf.root(i)]==0){
      mp[uf.root(i)]++;
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int A, B;
  int K = -1;
  cin >> A >> B;
  for(int i=0; i<=1000000000; i++) {
    if(abs(A-i) == abs(B-i)) {
      K = i;
      break;
    }
  }
  if(K == -1)
    cout << "IMPOSSIBLE" << endl;
  else
    cout << K << endl;
  return 0;
    
}

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

int main(int argc, char const* argv[]) {
  int n, k;
  cin >> n >> k;
  vector<ll> v(n);
  rep(i, n) cin >> v[i];
  ll ans = 0;
  for (int a = 0; a <= min(n, k); a++){//右からa個取る
    for (int b = 0; b + a <= min(n, k); b++) {  // 左からb個取る
      vector<ll> us;
      ll rec = 0;
      rep(i, a) us.pb(v[i]), rec += v[i];
      rep(i, b) us.pb(v[n - 1 - i]), rec += v[n - 1 - i];
      sort(all(us));
      rep(i, min(k - a - b,sz(us))) if (us[i] < 0) rec -= us[i];
      chmax(ans, rec);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
dic = {}
for i in range(N):
    if A[i] in dic:
        dic[A[i]] += 1
    else:
        dic[A[i]] = 1
cnt = 0
for key in dic:
    cnt += dic[key]*(dic[key]-1)//2
for i in range(N):
    print (cnt-dic[A[i]]+1)

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

int main() {
  int n; cin >> n;
  vector<int> a(n);
  int s = 0;
  rep(i,n) {
    cin >> a[i];
    s ^= a[i];
  }
  rep(i,n) {
    cout << (a[i] ^ s) << endl;
  }
}

Measured memory_bytes: 4044
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
using namespace std;

const int inf = 0x3f3f3f3f;
typedef long long ll;
const double pi=4*atan(1.0);

ll a[200005];
int main()
{    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        a[i]=i;a[i]+=a[i-1];
    }
    ll ans=1;
    if(k>n)printf("1\n");
    else
    {
        for(int i=k;i<=n;i++)
        {
            ans+=a[n]-a[n-i]-a[i-1]+1;
            ans%=1000000007;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Measured memory_bytes: 5324
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
#define pb push_back
#define mkp make_pair
using namespace std;

const int maxn = 100005;
typedef long long ll;


    int w, h;
int main()
{

    cin >> w >> h;
    vector<pair<int, int> > vec;
    for (int i = 0; i < w; i ++)
    {
        int t;
        cin >> t;
        vec.push_back(make_pair(t, 0));
    }
    for (int i = 0; i < h; i ++)
    {
        int t;
        cin >> t;
        vec.push_back(make_pair(t, 1));
    }
    w ++, h ++;
    sort(vec.begin(), vec.end());
    ll ans = 0;
    for (auto x : vec)
    {
        if (x.second == 0 && w > 1)
        {
            w --;
            ans += (ll)x.first * h;
        }
        else if (x.second == 1 && h > 1)
        {
            h --;
            ans += (ll)x.first * w;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 2548
#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, b, c, d;
    cin >> a >> b;
    if (a < b) {
        swap(a,b);
    }
    c = a;
    d = b;
    int gcd;
    while(1) {
        c %= d;
        if (c == 0) {
            gcd = d;
            break;
        }
        swap(c,d);
    }
    ll ans;
    if (gcd == 0) {
        ans = ll(a)*b;
    } else {
        ans = ll(a)*b/gcd;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

// -----------------------------------------------
// Framework <https://github.com/vain0x/procon>
// -----------------------------------------------

#[cfg(debug_assertions)]
include!{"./procon/debug.rs"}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($($arg:expr),*) => {};
}

#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let (N, M) = read!(i64, i64);

    let mut g = 1;

    let mut d = 1;
    while d * d <= M {
        if M % d == 0 {
            let c = M / d;

            if M/d >= N {
                g = max(g, d);
            }
            if M/c >= N {
                g = max(g, c);
            }
        }
        d += 1;
    }

    println!("{}", g)
}


Measured memory_bytes: 4352
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 2020;

using LL = long long;

LL arr[MAXN]; LL n, x;
LL jizz() {
    scanf("%lld%lld", &n, &x);
    for (int i = 0; i < n; ++i) scanf("%lld", &arr[i]);

    LL ans = 1LL<<62;

    LL cst[MAXN];
    for (int i = 0; i < n; ++i) cst[i] = arr[i];

    for (int i = 0; i < n; ++i) {
        LL c = x * i;
        for (int j = 0; j < n; ++j) c += cst[j];
        ans = min(c, ans);

        for (int j = 0; j < n; ++j)
            cst[j] = min(cst[j], arr[(j+n-i-1)%n]);
    }

    return ans;
}

int main() {
    printf("%lld\n", jizz());

    return 0;
}


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

int main() {

	int n, m, c; cin >> n >> m >> c;

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

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

	int ans = 0;
	for (int i = 0; i < n; i++) {
		int tmpSum = 0;
		for (int j = 0; j < m; j++) {
			tmpSum += a[i][j] * b[j];
		}
		if (0 < tmpSum + c) ans++;
	}

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

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

// マクロ //
#define rep(i,N) for(int i = 0; i < N; i++)
#define all(x) x.begin(), x.end()
#define sort(x) sort(all(x))
#define cou(x) cout << x << endl
#define y() cout << "Yes" << endl
#define n() cout << "No" << endl
#define Y() cout << "YES" << endl
#define N() cout << "NO" << endl
#define x2(x) x * x

// 型エイリアス //
using lint = long long;
using vi = vector<int>;
using vli = vector<lint>;
using vc = vector<char>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using msi = map<string, int>;

// 関数 //
int gcd(int a, int b) {
    int t;
    while (b != 0) {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

double distance(pii a, pii b) {
    double dist;
    dist = sqrt(x2(a.first - b.first) + x2(a.second - b.second));
    return dist;
}

// End of Template //



int main() {

    string s;
    string reverse;
    cin >> s;
    int N = s.size();

    vi vec(N + 1);

    rep(i, N) {
        reverse.push_back(s[N - i - 1]);
    }
    int conseq = 0;
    rep(i, N) {
        if (s[i] == '<') {
            conseq++;
            vec[i + 1] = conseq;
        }
        else {
            conseq = 0;
        }
    }
    conseq == 0;
    rep(i, N) {
        if (reverse[i] == '>') {
            conseq++;
            vec[N - i - 1] = max(conseq, vec[N - i - 1]);
        }
        else { conseq = 0; }
    }
    lint sum = 0;
    rep(i, N + 1) {
        sum += vec[i];
    }
    cou(sum);
}

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


int main(){
    int t;
    cin >> t;
    for (int i = 0; i < t; i++){
	int n, k;
	cin >> n >> k;
	vector<int> inp, diff;

	int b;
	for (int j = 0; j < n; j++){
	    cin >> b;
	    inp.push_back(b);
	}

	for (int j = 0; j < n - 1; j++) diff.push_back(inp[j+1] - inp[j]);

	sort(diff.begin(), diff.end(), greater<int>());

	if (k >= n){
	    cout << 0 << endl;
	} else {
	    int sum = 0;
	    sum = inp[inp.size()-1] - inp[0];
	    for (int j = 0; j < k-1; j++) sum -= diff[j];
	    
	    cout << sum << endl;
	}
    }
    
}

Measured memory_bytes: 1428