akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n, m;
ll x[maxn];
ll cc[maxn];
int par[maxn], siz[maxn];
int edge_deletes[maxn];

int parent(int v) {
    if (par[v]==v) return v;
    return par[v] = parent(par[v]);
}


void join(int u, int v, ll wei) {
    u = parent(u);
    v = parent(v);

    if (u == v) {
	if (wei > cc[u]) {
	    edge_deletes[u]++;
	} else {
	    edge_deletes[u]=0;
	}
    } else {
	if (siz[u]<siz[v]) swap(u,v);
	cc[u] += cc[v];
	siz[u] += siz[v];
	edge_deletes[u] += edge_deletes[v];
	par[v] = u;

	// Even if we can't defeat this edge, it's in our best interest to still join the
	// nodes so we can hopefully overpower the edge with future joins.
	if (wei > cc[u]) {
	    edge_deletes[u]++;
	} else {
	    edge_deletes[u]=0;
	}
    }
}

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

    cin>>n>>m;
    for (int i=1; i<=n; i++) {
	cin>>x[i];
    }
    for (int i=1; i<=n; i++) {
	cc[i]=x[i];
	par[i]=i;
	siz[i]=1;
    }

    vector<pair<ll,pair<int,int>>> edges;
    for (int i=0; i<m; i++) {
	int a,b,w;
	cin>>a>>b>>w;
	edges.push_back({w,{a,b}});
    }

    // Sort edges so if we find out that our sum(vertices) >= edge,
    // we can forget about all the previous edges we thought we had to delete.
    sort(edges.begin(), edges.end());


    for (auto ed: edges) {
	ll wei = ed.first;
	int u = ed.second.first;
	int v = ed.second.second;
	join(u,v, wei);
    }

    cout<<edge_deletes[parent(1)]<<endl;
    
    
    return 0;
}


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

template <typename T>
class SegmentTree {
	using func_t = function<T(T, T)>;
	const int n;
	const T id;
	func_t merge;
	vector<T> data;
	int size(int n) {
		int res;
		for (res = 1; res < n; res <<= 1);
		return res;
	}
public:
	SegmentTree(int n_, T id_, func_t merge_) :
		n(size(n_)), id(id_), merge(merge_), data(size(n_) * 2, id_) {}
	void Update(int p, T val) {
		p += n;
		data[p] = val;
		while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]);
	}
	void Add(int p, T val) {
		p += n;
		data[p] += val;
		while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]);
	}
	T Find(int i) {
		return data[i + n];
	}
	T Find(int l, int r) {
		l += n; r += n + 1;
		T res1 = id, res2 = id;
		while (l != r) {
			if (l & 1) res1 = merge(res1, data[l++]);
			if (r & 1) res2 = merge(data[--r], res2);
			l >>= 1; r >>= 1;
		}
		return merge(res1, res2);
	}
};

int main()
{
	cin.sync_with_stdio(false);
	cin.tie(0);
	int n, q, com, x, y;
	cin >> n >> q;
	SegmentTree<int> st(n, INT_MAX, [](int l, int r) { return min(l, r); });
	while (q--) {
		cin >> com >> x >> y;
		if (com) {
			printf("%d\n", st.Find(x, y));
		}
		else {
			st.Update(x, y);
		}
	}
	return 0;
}

Measured memory_bytes: 3772
#include <iostream>
using namespace std;
int main(void){
    string s;
    cin >> s;
    int count = 0;
    
    for (int i = 1; i < 4; i++) {
        if (s.at(i - 1) == s.at(i)) {
            count++;
        }
    }
    
    if (count == 0) {
        cout << "Good" << endl; 
    } else {
        cout << "Bad" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,q=map(int,input().split())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
d=deque()
d.append(0)
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
seen=[0]*n
seen[0]=1
while True:
    if not d:
        break
    i=d.pop()
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
            ans[j]+=ans[i]
print(*ans)

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

int main(){
	int a=1,b=1,c=1;
	char ch;
	string sa,sb,sc;
	cin>>sa>>sb>>sc;
	
	ch=sa[a-1];
	
	while(1){
		if(ch=='a'){
			if(a>sa.length()){
				cout<<'A'<<endl;
				break;
			}else{
				ch=sa[a-1];
				a++;
			}
		}
		if(ch=='b'){
			if(b>sb.length()){
				cout<<'B'<<endl;
				break;
			}else{
				ch=sb[b-1];
				b++;
			}
		}
		if(ch=='c'){
			if(c>sc.length()){
				cout<<'C'<<endl;
				break;
			}else{
				ch=sc[c-1];
				c++;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
s = input()

if s[0] == "R" and s[1] == "R" and s[2] == "R":
    print(3)
elif s[0] == "R" and s[1] == "R" or s[1] == "R" and s[2] == "R":
    print(2)
else:
    if "R" in s:
        print(1)
    else:
        print(0)

Measured memory_bytes: 9048
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXM=1e3+10;
int n,m;
int a[MAXM];
int b[MAXM];
int c[MAXM][15];
int dp[5000];
int main()
{
    // freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int u=1;u<=m;u++){
        cin>>a[u]>>b[u];
        for(int v=1;v<=b[u];v++){
            cin>>c[u][v];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int u=1;u<=m;u++){
        int state=0;
        for(int v=1;v<=b[u];v++){
            state|=1<<(c[u][v]-1);
        }
        for(int v=0;v<(1<<n);v++){
            dp[v|state]=min(dp[v|state],dp[v]+a[u]);
        }
    }
    if(dp[(1<<n)-1]==INF)cout<<-1;
    else cout<<dp[(1<<n)-1];
}

Measured memory_bytes: 384
#[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, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (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")
    };
}

use std::cmp;

fn main() {
    input! {
        num: usize,
        mut nums: [isize; num],
    }

    for (i, n) in nums.iter_mut().enumerate() {
        *n = *n - (i+1) as isize;
    }
    nums.sort();
    
    let ans;
    if num % 2 == 0 {
        let tmp1 = nums[num/2];
        let tmp2 = nums[num/2-1];
        let sum1 = nums.iter().fold(0, |acc, x| acc + (x-tmp1).abs());
        let sum2 = nums.iter().fold(0, |acc, x| acc + (x-tmp2).abs());
        ans = cmp::min(sum1, sum2);
    } else {
        let tmp = nums[(num-1)/2];
        let sum = nums.iter().fold(0, |acc, x| acc + (x-tmp).abs());
        ans = sum;
    }

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

Measured memory_bytes: 6396
#include <bits/stdc++.h>
using namespace std;
int a[10],n;

bool dfs(int i,int j,int k)
{
    if(i==10) return 1;
    if(a[i]>j&&a[i]>k) return dfs(i+1,a[i],k) || dfs(i+1,j,a[i]);
    else if(a[i]>j) return dfs(i+1,a[i],k);
    else if(a[i]>k) return dfs(i+1,j,a[i]);
    return 0;
}

int main()
{
    //mine
    ios::sync_with_stdio(false);
    cin>>n;
    while(n--){
        for(int i=0;i<10;i++) cin>>a[i];
        if(dfs(0,0,0)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

//素因数分解
vector<pair<ll,int>> factorize(ll n){
    vector<pair<ll,int>>res;
    for(ll i=2;i*i<=n;i++){
        if(n%i)continue;
        res.emplace_back(i,0);
        while (n%i == 0)
        {
        n /= i;
        res.back().second++;
        }
        
    }
    if(n != 1) res.emplace_back(n,1);
    return res;
}

void trace(int A[],int N){
    REP(i,N){
        if(i>0)printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
}


int main(){
    string s;
    cin >> s;
    int ans = 0;
    for(int i=0;i<s.length();i++){
        if(s[i] == '+')ans++;
        else ans--;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using iii = pair<ii, ll>;
#define vt vector
#define pq priority_queue
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define __lcm(a, b) a * b / __gcd(a, b)x
const ll MOD = 1e9 + 7;
const ll INF = 2e9;
const ll N = 3e3 + 5;

ll n, k;
ll a[N];
ll dp[N][N];

ll f(ll l, ll r) {
    if(l > r) return 0;
    ll &sol = dp[l][r];
    if(sol != -1) return sol;
    return sol = max(a[l] - f(l + 1, r), a[r] - f(l, r - 1));
}

void solve() {
    cin >> n;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << f(1, n) << "\n";
}

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

    solve();
    
}

Measured memory_bytes: 74304
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i=l,i##end=r;i<=i##end;++i)
#define per(i,r,l) for (int i=r,i##end=l;i>=i##end;--i)
#define rep0(i,r) for (int i=0,i##end=r;i<i##end;++i)
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=3e3+3;
int S[N][N],C[N][N],pw[N*N];
int fpw(int x,int y,int P){
    int s=1; for (;y;y>>=1,x=(ll)x*x%P) if (y&1) s=(ll)s*x%P; return s;
}
int main(){
    int n,P; cin>>n>>P;
    S[0][0]=1;
    rep(i,1,n+1)
        rep(j,1,i) S[i][j]=((ll)j*S[i-1][j]+S[i-1][j-1])%P;
    rep(i,0,n+1){
        C[i][0]=1;
        rep(j,1,n+1) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
    }
    pw[0]=1; rep(i,1,n*n) pw[i]=2LL*pw[i-1]%P;
    int ans=0;
    rep(i,0,n){
        int t=0;
        rep(j,0,i) t=(t+(ll)pw[(n-i)*j]*S[i+1][j+1])%P;
        t=(ll)t*fpw(2,fpw(2,n-i,P-1),P)%P*C[n][i]%P;
        if (i&1) ans=(ans+P-t)%P;
        else ans=(ans+t)%P;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 105856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
struct UnionFind{
vector<int> par,depth,Size;
UnionFind(int n){
par.resize(n); depth.resize(n); Size.resize(n);
for(int i=0; i<n; i++){
par[i]=i;
depth[i]=0;
Size[i]=1;
}
}
int find(int x){
if(par[x]==x){
return x;
}
else{
return par[x]=find(par[x]);
}
}
bool same(int x, int y){
return find(x)==find(y);
}
void unite(int x, int y){
x=find(x); y=find(y);
if(x==y) return;
if(depth[x]<depth[y]) swap(x,y);
if(depth[x]==depth[y]) depth[x]++;
par[y]=x;
Size[x]+=Size[y];
}
int size(int x){
return Size[find(x)];
}
};
int main(){
    ll n,m;cin>>n>>m;
    UnionFind uf(220000);
    rep(i,n){
        ll k;cin>>k;
        rep(j,k){
            ll l;cin>>l;
            uf.unite(i+1,l+n);
        }
    }
    bool ok=true;
    rrep(i,n){
        if(!uf.same(1,i)) ok=false;
    }
    if(ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  ll x,y;
  cin>>x>>y;
  if(x%y == 0){
    cout << -1 << endl;
  }else{
    cout << x << endl; 
  }
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int keta(int dig);
int main(){
    int N,A,B,min=5000;
    cin >> N;
    for(A=1;A<=N-1;A++){
        B=N-A;
        int sum1=0,sum2=0;
        sum1=keta(B);
        sum2=keta(A);
        if(min>sum1+sum2){
            min=sum1+sum2;
        }
    }
    cout << min;
}

int keta(int dig){
    int sum=0;
    while(dig>0){
        sum+=dig%10;
        dig/=10;
    }
    return sum;
}

Measured memory_bytes: 256
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, K = iim()
    P = list(iim())
    P2 = list(map(lambda x: x * (x + 1) / x / 2, P))

    ip = enumerate(P2)
    val = ans = 0
    for i in range(K-1):
        j, p = next(ip)
        val += p

    for i, p in ip:
        val += p
        if val > ans:
            ans = val
        #print(i, K, p, val, ans, i-K+1)
        val -= P2[i-K+1]
    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 24804
#include <bits/stdc++.h>
    using namespace std;
    #define ll long long int
    #define pb push_back
    #define mk make_pair
    #define ft first
    #define sc second
    #define ppb pop_back
    #define sz size
    #define forn(i,a,n) for(i=a;i<n;i++)
    #define M 1000000007
    #define inf 2e18
    
    int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll n;
    string s;
    cin>>n>>s;
    ll ans=0;
    for(ll i=0; i<1000; i++){
        vector<ll> v;
        v.pb(i/100);
        v.pb((i/10)%10);
        v.pb(i%10);
        ll k=0;
        for(ll j=0;j<n;j++){
            if(v[k]+'0'==s[j])k++;
            if(k==3){ans++; break;}
        }
    }
    cout<<ans;
    return 0;
    } 

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int a[maxn],b[maxn],n;
bool inq[maxn];
long long ans = 0;
queue<int> q;
void check(int x){
	if(inq[x])return ;
	int l = x-1,r = x+1;
	if(l==0)l = n;
	if(r==n+1) r = 1;
	if(b[x]>b[l]+b[r]&&b[x]>a[x]){
		inq[x] = 1;
		q.push(x);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	memset(inq,0,sizeof(inq));
	for(int i=1;i<=n;i++)
		check(i);
	while(!q.empty()){
		int x = q.front();q.pop();
		inq[x] = 0;
		int l = x-1,r = x+1;
		if(l==0)l = n;
		if(r==n+1) r = 1;
		int sum = b[l]+b[r];
		int v = (b[x]-a[x])/sum;
		b[x] -= sum*v;
		ans += v;
		check(l);check(r); 
//		cout<<"->"<<x<<endl;
//		for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;
	}
	bool ok = 1;
	for(int i=1;i<=n;i++)	
		if(a[i]!=b[i]) ok = 0;
	if(!ok)puts("-1");
	else cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const long long INF = 1LL << 60;
const int MOD = 1000000007; // 1e9 + 7
using namespace std;
using vec = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}
template <class T> inline bool chmin(T &a, T b) { if ( a > b ) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T &a, T b) { if ( a < b ) { a = b; return 1; } return 0; }
const int dy[4] = {-1, 0, 0, 1};
const int dx[4] = {0, -1, 1, 0};

int N;

int main(int argc, char *argv[]){
    cin >> N;
    vec A(N);
    rep(i, N) cin >> A[i];
    vec R(8);
    int cnt = 0;
    rep(i, N){
        if(A[i] < 400) R[0]++;
        else if(400  <= A[i] && A[i] < 800) R[1]++;
        else if(800  <= A[i] && A[i] < 1200) R[2]++;
        else if(1200 <= A[i] && A[i] < 1600) R[3]++;
        else if(1600 <= A[i] && A[i] < 2000) R[4]++;
        else if(2000 <= A[i] && A[i] < 2400) R[5]++;
        else if(2400 <= A[i] && A[i] < 2800) R[6]++;
        else if(2800 <= A[i] && A[i] < 3200) R[7]++;
        else cnt++;
    }
    int Min = 1e7;
    int Max = -1;
    int color = 0;
    rep(i, 8)
        if(R[i]) color++;

    Min = color;
    Max = color + cnt;
    // if(color == 8) Min = Max = 8;
    // else if(Max > 8) Max = 8;
    Min = max(1, Min);
    cout << Min << " " << Max << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	int n=sc.nextInt(),m=sc.nextInt(),f=0;
  	int[] a=new int[m],b=new int[m],e=new int[n],g=new int[n];
  	long[] h=new long[n];
  	for(int i=0;i<n;i++){
  		h[i]=sc.nextLong();
  		e[i]=0;
  		g[i]=0;
  	}
  	for(int i=0;i<m;i++){
  		a[i]=sc.nextInt();
  		b[i]=sc.nextInt();
  	}
  	for(int i=0;i<m;i++){
  		e[a[i]-1]++;
  		e[b[i]-1]++;
  		if(h[a[i]-1]>h[b[i]-1]){
  			g[a[i]-1]++;
  		}else if(h[a[i]-1]<h[b[i]-1]){
  			g[b[i]-1]++;
  		}
  	}
  	for(int i=0;i<n;i++){
  		if(e[i]==g[i]){
  			f++;
  		}
  	}
  	System.out.print(f);
  }
}

Measured memory_bytes: 62124
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,q,h,x[200003],f[200003],g[200003];
int main(){
	cin>>n>>m>>q;int D=0;
	for(int i=0;i<n;i++){x[i]=0;f[i]=(i+1)%n;g[i]=(i+n-1)%n;}
	for(int i=0;i<m;i++){
		scanf("%d",&h);
		if(h%2==0){
			for(int j=0;j<h;j++)D=f[D];
		}
		if(h%2==1){
			for(int j=0;j<h;j++)D=g[D];
		}
		f[g[D]]=f[D];g[f[D]]=g[D];x[D]=1;D=f[D];
	}
	for(int i=0;i<q;i++){
		scanf("%d",&h);cout<<1-x[h]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3592
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] p = new int[n];
    for(int i = 0;i<n;i++){
      p[i] = sc.nextInt();
    }
    Arrays.sort(p);
    int ans = 0;
    for(int i = 0;i<k;i++){
      ans += p[i];
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 38768
if __name__ == '__main__':
    n, k, q = map(int,input().split())
    a_list = [int(input()) for i in range(q)]

    point = [k-q for i in range(n)]
    for a in a_list:
        point[a-1]+=1

    for p in point:
        if p > 0:
            print("Yes")
        else:
            print("No")



Measured memory_bytes: 11792
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define ll long long
#define INF 999999999

const ll mod = 1e9+7;

int main(){
	string s, t;
	cin >> s >> t;
	REP(i, s.size()){
		if (s == t) {cout << "Yes" << endl; return 0;}
		s = s.back() + s;
		s.pop_back();
	}
	cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <tuple>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
typedef tuple<ll, ll> ii;
typedef vector<bool> vb;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef priority_queue<ii, vii, greater<ii>> pq;

ll n, m, s, t, u, v, a, b;

void bfs(vvii &g, vi& c, int s) {
	vb v(n);
	pq q;
	q.push(make_tuple(0, s));
	while (!q.empty()) {
		ll k, i;
		tie(k, i) = q.top();
		q.pop();
		if (v[i]) continue;
		v[i] = true;
		c[i] = k;
		for (auto &z:g[i]) {
			ll k2, i2;
			tie(k2, i2) = z;
			if (v[i2]) continue;
			q.push(make_tuple(k + k2, i2));
		}
	}
}

int main() {
	cin >> n >> m >> s >> t;
	s--; t--;
	vvii ga(n), gb(n);
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> a >> b;
		u--; v--;
		ga[u].push_back(make_tuple(a, v));
		ga[v].push_back(make_tuple(a, u));
		gb[u].push_back(make_tuple(b, v));
		gb[v].push_back(make_tuple(b, u));
	}

	vi ca(n), cb(n), c(n);
	bfs(ga, ca, s);
	bfs(gb, cb, t);
	c[n - 1] = ca[n - 1] + cb[n - 1];
	for (int i = n - 2; i >= 0; i--) c[i] = min(c[i + 1], ca[i] + cb[i]);
	for (int i = 0; i < n; i++) cout << 1000000000000000LL - c[i] << endl;
}


Measured memory_bytes: 19060
#include <iostream>
#include <vector>
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
using namespace std;
using ll = long long;

void Output(const vector<int> &a){
  REP(i,a.size()){
    cout << a[i];
    if(i != a.size()-1) cout << " ";
  }
  cout << endl;
}

int BubbleSort(vector<int> &a, int n){
  bool flag = 1;
  int res = 0;
  while(flag){
    flag = 0;
    for(int i=n-1;i>=1;--i){
      if(a[i-1] > a[i]){
        swap(a[i-1], a[i]);
        flag = 1;
        ++res;
      }
    }
  }
  return res;
}

int main(){
  int n; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  int res = BubbleSort(a,n);
  Output(a);
  cout << res << endl;
  return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("ina.txt", "r", stdin);
    //freopen("outa.txt", "w", stdout);
    int n;
    cin >> n;
    vector<int> arr;
    arr.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    int prev = arr[0];
    int cnt = 1;
    int delcnt = 0;
    for(int i = 1; i < n; i++) {
        int at = arr[i];
        if(at != prev) {
            if(prev != cnt) {
                if(cnt < prev) {
                    delcnt += cnt;
                } else {
                    delcnt += cnt - prev;
                }
            }
            prev = at;
            cnt = 1;
        } else {
            cnt++;
        }
    }
    if(cnt < arr[arr.size() - 1]) {
        delcnt += cnt;
    } else {
        delcnt += cnt - arr[arr.size() - 1];
    }
    cout << delcnt << "\n";
}


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

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

map<long, long> prime_factor(long N) {
  map<long, long> res;
  for (long i = 2; i * i <= N; i++) {
    while (N % i == 0) {
      res[i]++;
      N /= i;
    }
  }
  if (N != 1) {
    res[N] = 1;
  }
  return res;
}

int main() {

  long A, B;
  cin >> A >> B;

  long g = gcd(A, B);

  map<long, long> m = prime_factor(g);
  
  cout << m.size() + 1 << endl;

}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int x1,x2,x3,x4,y1,y2,y3,y4,a,b,c,d,x,y,n,m;
	scanf("%d %d %d %d %d %d %d %d",&x1,&x2,&y1,&y2,&a,&b,&c,&d);
	x=x1*a+x2*b;
	y=y1*a+y2*b;
	if(x1>=10){
		x3=x1/10;
		x=x+x3*c;
	}
	if(x2>=20){
		x4=x2/20;
		x=x+x4*d;
	}
	if(y1>=10){
		y3=y1/10;
		y=y+y3*c;
	}
	if(y2>=20){
		y4=y2/20;
		y=y+y4*d;
	}
	if(x>y){
		printf("hiroshi\n");
	}
	else if(x<y){
		printf("kenjiro\n");
	}
	else if(x==y){
		printf("even\n");
	}
	return 0;
}


Measured memory_bytes: 2624
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll ar[500009],br[500009];
map<string,ll>mp;
map<ll,string>mp1;
vector<ll>v;
int main()
{
    ll a,b,c,i,j,k,x,y,z,f,g,h;
    string s,d;
    cin>>s;
    if(s=="SUN")
    {
        cout<<"7"<<endl;
    }
    else if(s=="MON")
    {
        cout<<"6"<<endl;
    }
    else if(s=="TUE")
    {
        cout<<"5"<<endl;
    }
    else if(s=="WED")
    {
        cout<<"4"<<endl;
    }
    else if(s=="THU")
    {
        cout<<"3"<<endl;
    }
    else if(s=="FRI")
    {
        cout<<"2"<<endl;
    }
    else if(s=="SAT")
    {
        cout<<"1"<<endl;
    }
}


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

typedef struct {
	int untin;
	int limit;
} taxi_t;

typedef struct {
	taxi_t taxi;
	int loads_num;
	int loads_cap;
	int *loads;
} mati_t;

void add_load(mati_t *mati, int to) {
	if(mati->loads_num>=mati->loads_cap) {
		mati->loads_cap*=2;
		if(mati->loads_cap<=0)mati->loads_cap=1;
		if(mati->loads==NULL) {
			mati->loads=(int*)malloc(sizeof(int)*mati->loads_cap);
		} else {
			mati->loads=(int*)realloc(mati->loads,sizeof(int)*mati->loads_cap);
		}
	}
	mati->loads[mati->loads_num++]=to;
}

typedef struct {
	short town;
	short kaisu;
} status_t;

int heap_size;
status_t status_heap[5000*5001];
int status_mincost[5000][5001];
char in_heap[5000][5001];

int read_cost(status_t stat) {
	return status_mincost[stat.town][stat.kaisu]-1;
}

void update_cost(status_t stat,int cost) {
	if(status_mincost[stat.town][stat.kaisu]==0 ||
	status_mincost[stat.town][stat.kaisu]-1>cost) {
		status_mincost[stat.town][stat.kaisu]=cost+1;
	}
}

void adjust_heap(int idx) {
	int min_idx=idx;
	if(idx*2+1<heap_size) {
		if(read_cost(status_heap[min_idx])>read_cost(status_heap[idx*2+1])) {
			min_idx=idx*2+1;
		}
		if(idx*2+2<heap_size) {
			if(read_cost(status_heap[min_idx])>read_cost(status_heap[idx*2+2])) {
				min_idx=idx*2+2;
			}
		}
	}
	if(min_idx!=idx) {
		status_t tmp=status_heap[idx];
		status_heap[idx]=status_heap[min_idx];
		status_heap[min_idx]=tmp;
		adjust_heap(min_idx);
	} else {
		if(idx>0)adjust_heap(idx/2);
	}
}

void insert_heap(status_t stat,int cost) {
	int prev_cost=read_cost(stat);
	if(prev_cost<0 || cost<prev_cost) {
		update_cost(stat,cost);
		if(!in_heap[stat.town][stat.kaisu]) {
			in_heap[stat.town][stat.kaisu]=1;
			status_heap[heap_size]=stat;
			adjust_heap(heap_size++);
		}
	}
}

status_t get_heap(void) {
	status_t ret=status_heap[0];
	in_heap[ret.town][ret.kaisu]=0;
	status_heap[0]=status_heap[--heap_size];
	adjust_heap(0);
	return ret;
}

int N,K;
taxi_t taxi[5000];
mati_t mati[5000];

int main(void) {
	int i;
	int answer;
	status_t initial={0,0};
	if(scanf("%d%d",&N,&K)!=2)return 1;
	for(i=0;i<N;i++) {
		if(scanf("%d%d",&taxi[i].untin,&taxi[i].limit)!=2)return 1;
	}
	for(i=0;i<K;i++) {
		int A,B;
		if(scanf("%d%d",&A,&B)!=2)return 1;
		A--;B--;
		add_load(&mati[A],B);
		add_load(&mati[B],A);
	}
	/* haba yuusen tansaku */
	insert_heap(initial,0);
	while(heap_size>0) {
		status_t cur_status=get_heap();
		int cur_cost=read_cost(cur_status);
		status_t next_status;
		if(cur_status.town==N-1) {
			/* mokutekiti ni tuita */
			printf("%d\n",cur_cost);
			break;
		}
		/* tugi no mati ni iku */
		if(cur_status.kaisu>0) {
			next_status.kaisu=cur_status.kaisu-1;
			for(i=0;i<mati[cur_status.town].loads_num;i++) {
				next_status.town=mati[cur_status.town].loads[i];
				insert_heap(next_status,cur_cost);
			}
		}
		/* kakin site kono mati de taxi ni noru */
		next_status.town=cur_status.town;
		next_status.kaisu=taxi[cur_status.town].limit;
		insert_heap(next_status,cur_cost+taxi[cur_status.town].untin);
	}
	/* atosimatu */
	for(i=0;i<N;i++) {
		if(mati[i].loads!=NULL)free(mati[i].loads);
	}
	return 0;
}

Measured memory_bytes: 123856
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>

using namespace std;

/********** TEMPLATE STARTS HERE ***********/

#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define PI 3.1415926535897932384626433832795
#define gcd __gcd 

typedef unsigned long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pll> vll;
typedef vector <pii> vii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

/*********** TEMPLATE ENDS HERE *************/

main()
{
	int a, b, c, x;
	cin >> a >> b >> c >> x;
	
	int nr = 0;
	
	for(int i = 0; i <= a; i++)
		for(int j = 0; j <= b; j++)
			for(int e = 0; e <= c; e++)
				if(500 * i + 100 * j + 50 * e == x)
					nr++;
	
	cout << nr;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
using namespace std;
//#define int long long
vector <vector <int> > g;
int pp[200000];
int cnt[200000];
int dd[200000];
int dfs(int v, int p, int d) {
	dd[v] = d;
	pp[v] = p;
	cnt[v] = 1;
	for (auto it : g[v]) {
		if (it != p) {
			cnt[v] += dfs(it, v, d + 1);
		}
	}
	return cnt[v];
}
signed main() {
#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	g.resize(n + 1);
	for (int i = 1; i <= n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1, 0);
	int cntt = (dd[n] - 1) / 2;
	int cur = n;
	while (cntt--) {
		cur = pp[cur];
	}
	int nn = cnt[cur];
	int ff = n - cnt[cur];
	if (ff <= nn) cout << "Snuke" << endl;
	else cout << "Fennec" << endl;
}

Measured memory_bytes: 13184
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define fi first
#define se second
#define pii pair<int,int>
//#define int long long
#define endl '\n'
#define pll pair<long long,long long>
#define LONGLONG_MAX 100000000000000
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a)%mod;}
                a=(a*a)%mod;
                b>>=1;
        }
    return ans;
        
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    srand(time(0));
	int n;
	cin>>n;
	string s;
	cin>>s;
	int i=0,j=n-1;
	int ans=0;
	while(i!=n&&s[i]=='R')i++;
	while(j!=-1&&s[j]=='W')j--;
	while(i<j){
		ans++;
		i++;
		j--;
		while(i!=n&&s[i]=='R')i++;
		while(j!=-1&&s[j]=='W')j--;
	
	}
	cout<<ans;    
    return 0;
}

Measured memory_bytes: 3736
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int cnt = Integer.parseInt(reader.readLine()); // ignored

        char[] cs = reader.readLine().toCharArray();

        int result = 0;
        int max = result;
        for (int i = 0; i < cnt; i++) {
            if ('I' == cs[i])
                result++;
            else
                result--;
            if (result > max)
                max = result;
        }

        System.out.print(max);

//        PrintWriter writer = new PrintWriter(System.out);
//
//        writer.close();


    }
}


Measured memory_bytes: 20564
import java.io.*;
import java.util.*;
 
 
public class Main{
   public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));
      
      // Start writing your solution here. -------------------------------------
   		String s = sc.nextLine();
     if(s.charAt(4) == s.charAt(5) && s.charAt(2) == s.charAt(3))
       out.println("Yes");
     else out.println("No");
      /*
      int n      = sc.nextInt();        // read input as integer
      long k     = sc.nextLong();       // read input as long
      double d   = sc.nextDouble();     // read input as double
      String str = sc.next();           // read input as String
      String s   = sc.nextLine();       // read whole line as String

      int result = 3*n;
      out.println(result);                    // print via PrintWriter
      */

      // Stop writing your solution here. -------------------------------------
      out.close();
   }

     

   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
	  try {
	     str = br.readLine();
	  } catch (IOException e) {
	     e.printStackTrace();
	  }
	  return str;
      }

   }
   //--------------------------------------------------------
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
	int n, ans = 0;
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		if (a[i] == i) {
			ans++;
			i++;
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>

using namespace std;

#define forn(I,N) for (int I=0; I<N; I++)
#define fornd(I,N) for (int I=N-1; I>=0; I--)
#define forab(I,A,B) for (int I=A; I<=B; I++)
#define forabd(I,A,B) for (int I=B; I>=A; I--)
#define FOREACH(I,A) for (__typeof__(A)::iterator I=A.begin(); I<A.end(); I++)
#define pb push_back
#define mp make_pair

typedef long long int ll;

const ll mod = 1000000007;

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

  vector<int> col(N, -1);
  vector<vector<pair<int, int> > > edge(N);
  forn(i, N - 1) {
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    edge[a].pb(mp(b, w));
    edge[b].pb(mp(a, w));
  }

  vector<bool> added(N);
  vector<int> next;
  added[0] = true;
  next.pb(0);
  col[0] = 0;

  int cur = 0;
  while (cur < next.size()) {
    int index = next[cur];
    forn(i, edge[index].size()) {
      int nextIndex = edge[index][i].first;
      if (!added[nextIndex]) {
        int weight = edge[index][i].second;

        if (weight % 2 == 0) {
          col[nextIndex] = col[index];
        } else {
          col[nextIndex] = col[index] ^ 1;
        }

        added[nextIndex] = true;
        next.pb(nextIndex);
      }
    }

    cur++;
  }

  forn(i, N) {
    cout << col[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 7292
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int main(void)
{
    long long n;
    int i;
    long long o;

    cin >> n;
    for(i = 1, o = n + 1; (long long)i * i <= n; i ++)
        if(!(n % i))
            o = min(o, i + n / i);
    cout << o - 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(),x.end()
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define PI 3.1415926535897932384626
#define mod 1000000007
#define modd 998244353

void io() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}

const int N = 2*1e5+1;
vector<int> adj[N];
bool vis[N];

void dfs(int s, int &cnt) {
	cnt++;
	vis[s] = true;
	for(auto x:adj[s]) {
		if(vis[x]) continue;
		dfs(x,cnt);
	}
}

int main() {
	io();

	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++) {
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int ans=0;
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue;
		int cnt = 0;
		dfs(i,cnt);
		ans = max(ans,cnt);
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 24148
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long x,k,d;
	cin>>x>>k>>d;
	long long temp=abs(x)/d;
	if (temp>=k)   cout<<abs(abs(x)-k*d);
	else   
	{
		if ((k-temp)%2==0)   cout<<abs(abs(x)-temp*d);
		else
		{
			cout<<min(abs(abs(x)+d-temp*d),abs(abs(x)-(temp+1)*d));
		}
	}
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], b[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        b[i] = a[i];
    }
    int res = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        int key = lower_bound(a + 1, a + n + 1, b[i]) - a;
        res += (key + i) % 2;
    }
    cout << res/2 << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
 
int m3[101][101];
int p[100];
 
void matrixChain(int);
 
int main(){
  int n;
  int d;
  int i;
 
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d%d",&p[i],&d);
  p[i]=d;
 
  matrixChain(n);
 
  printf("%d\n",m3[1][n]);
 
  return 0;
}
 
void matrixChain(int n){
  int i,j,a,l,k;
 
  for(i=1;i<=n;i++) m3[i][i] = 0;
 
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j= i+l-1;
      m3[i][j]= 2147483647;
      for(k=i;k<j;k++){
    a= m3[i][k] + m3[k+1][j] + p[i-1] * p[k] * p[j];
    if(m3[i][j] > a) m3[i][j] = a;
      }
    }
  }
}

Measured memory_bytes: 636
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define ri register int
#define rep(i,a,b) for(ri i=(a);i<=(b);++i)
#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))
#define REP(i,a,b) for(ri i=(a);i>=(b);--i)
#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))
using namespace std;

inline ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

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

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,i,p;
    cin>>a>>b>>c;
    for(i=a;i<=b;i++){
        if(c%i==0){
            p+=1;
        }
    }
    cout<<p<<endl;
    return 0;
}



Measured memory_bytes: 3116
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int x = Integer.parseInt(sc.next());
        int y = Integer.parseInt(sc.next());

        // 主処理
        // 空のグラフを作成
        List<HashSet<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new HashSet<>());
        }

        // 無向グラフを設定
        for (int i = 0; i < n - 1; i++) {
            list.get(i).add(i + 1);
            list.get(i + 1).add(i);
        }
        list.get(x - 1).add(y - 1);
        list.get(y - 1).add(x - 1);

        // 全てのスタート地点から全ての移動距離を求める
        int[][] distanceArray = new int[n][n];
        for (int i = 0; i < n; i++) {

            // 探索の開始地点を設定
            Deque<Integer> deque = new ArrayDeque<>();
            int start = i;
            deque.add(start);

            // 探索距離を保持
            int[] distance = new int[n];
            distance[start]++;

            // 探索を開始
            while (!deque.isEmpty()) {
                int point = deque.poll();

                for (int nextPoint : list.get(point)) {
                    if (distance[nextPoint] == 0) {
                        deque.add(nextPoint);
                        distance[nextPoint] = distance[point] + 1;
                        distanceArray[i][nextPoint] = distance[nextPoint] - 1;
                    }

                }
            }
        }

        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count[distanceArray[i][j]]++;
            }
        }

        // 出力
        for (int i = 1; i < count.length; i++) {
            System.out.println(count[i] / 2);
        }
        sc.close();
    }
}


Measured memory_bytes: 110316
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;


int main() {
    int n; cin >> n;
    int total = 0;
    vector<int> v(n);
    rep(i,n){
        cin >> v[i];
        total += v[i];
    } 
    total -= *max_element(v.begin(), v.end())/2;
    cout << total << endl;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace arc096_a
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] x = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long ret = long.MaxValue;
            for (int i = 0; i <= Math.Max(x[3], x[4]); i++)
            {
                long now = Math.Max(0, (x[3] - i)) * x[0] + Math.Max(0, (x[4] - i)) * x[1] + (i * 2) * x[2];
                ret = Math.Min(ret, now);
            }
            Console.WriteLine(ret);
        }
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

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

using namespace std;

int main() {
  while(1) {
    int n,k;
    cin >> n >> k;
    if (!n) break;
    vector<int> v(n+1);
    for (int i = 0; i < k; ++i) {
      int a;
      cin >> a;
      v[a] = 1;
    }
    int l=0;
    int zero = 0;
    int max_len = 0;
    for (int i = 1; i <= n; ++i) {
      if (v[i] == 0) {
        zero++;
      }
      while(zero > v[0]) {
        if(v[++l] == 0) {
          zero--;
        }
      }
      max_len = max(max_len, i - l);
    }
    cout << max_len << endl;
  }
  return 0;
}

Measured memory_bytes: 1524
import java.util.*;

public class Main {               
    
  public static void main(String[] args) {     
     Scanner sc = new Scanner(System.in);
      
     int N = sc.nextInt();
     
     HashMap<Integer,Integer> map = new HashMap<>();
     
     for(int i = 0;i < N;i++){
       int a = sc.nextInt();
       if(!map.containsKey((a))){
           map.put(a,1);
       }else{
           map.put(a,map.get(a) + 1);
       }         
     }
     
     int M = sc.nextInt();

     for(int i = 0;i < M;i++){
         int t = sc.nextInt();
         
         if(map.get(t) == null || map.get(t) == 0){
             System.out.println("NO");
             return;
         }
         
         if(map.get(t) > 0){
             map.put(t,map.get(t) -  1);
         }
     }     
     
     System.out.println("YES");
     
  }   
   
}
    

Measured memory_bytes: 146156
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = LI()

#  # 山1の雨量は、左右のダムの大きい方
#  # 山1の雨量は、左右の山を見て候補値を絞り込む
#  # 例えば左右にそれぞれ6と4溜まっている場合、自分を0,2,4降った可能性を検討する
#  # ダムxの水量を見て、ありうる候補を見つける
#  # 最小値から見ると速いかも
#  # 山を-2すると、ダムを-2することができる
#  # 最小のダムを見つける
#  min_dam = min(A)
#  min_dam_idx = A.index(min_dam)
#  tmp_A = A[min_dam_idx:] + A[:min_dam_idx]
#  if min_dam == 0:
#      # 0のダムがある場合、その周りのダムは0が確定する
#      yamas = [0,0]
#      for i in range(2, N):
#          yamas.append(int((tmp_A[i]-yamas[-1]/2)*2))
#      yamas = yamas[N-min_dam_idx:] + yamas[:N-min_dam_idx]
#      print(yamas)
#  else:
#      # 最小のダムが0になるまで-2していく
#      tmp_A = [i - min_dam for i in tmp_A]
#      print(tmp_A)
#      yamas = [0,0]
#      for i in range(2, N):
#          yamas.append(int((tmp_A[i]-yamas[-1]/2)*2))
#      yamas = yamas[N-min_dam_idx:] + yamas[:N-min_dam_idx]
#      print(yamas)


'''
コンテスト後
雨の総量をSとおくと、
S = A1 + A2 + ... An
S = (W1+ W2 + ... Wn)/2
A1 = (W1+W2)/2
つまり、
2 = (W1+W2)/2
A2 = (W2+W3)/2
つまり、
2 = (W2 + W3)/2
S = 2A1 + 2A3 + ... 2AN//2

W1 = S - (W2 + W3 + ... Wn) = S - 2(A2 + A4 ... + An-1)
W1 = 8 - 2(2)
W2 = 8 - 2()

W1 + W2 = 2A1
W2 = 2A1 - W1
W2 = 2*2 - 4 = 0
W3 = 2A2 - W2 = 2*2 - 0 = 4
'''

S = sum(A)
W = [0 for i in range(N)]
W[0] = S - 2*sum([i for idx, i in enumerate(A[1:]) if idx % 2 == 0])
for i in range(1, N):
    W[i] = 2*A[i-1] - W[i-1]
for w in W:
    print(w, end=' ')


Measured memory_bytes: 88800
P = 10**9+7
B, W = map(int, input().split())

inv2 = [1]
fact = [1]
for i in range(B+W+10):
    inv2.append((inv2[-1] + (inv2[-1] % 2) * P)//2)
    fact.append(fact[-1] * (i+1) % P)

def C(a, b):
    return fact[a]*pow(fact[b]*fact[a-b]%P, P-2, P) % P

L, R = 0, 0
for i in range(B+W):
    if i >= B:
        L *= 2
        L += C(i-1, B-1)
        L %= P
    if i >= W:
        R *= 2
        R += C(i-1, W-1)
        R %= P
    print(((R-L)*inv2[i+1]+inv2[1])%P)
    


Measured memory_bytes: 20968
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using static System.Math;
using System.Linq;
using static System.Array;

namespace ConsoleApp2
{
    class Program
    {
        static int N;
        static long mod = 1000000007;
        
        static void Main(string[] args)
        {
            N = int.Parse(Console.ReadLine());
            //R = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            var S = Console.ReadLine();

            var dic = new Dictionary<char, int>();
            for (int i = 0; i < N; i++)
            {
                var now = S[i];
                if (dic.ContainsKey(now))
                {
                    dic[now]++;
                }
                else
                {
                    dic.Add(now, 1);
                }
            }

            long ans = 1;
            foreach (var item in dic)
            {
                var tmp = item.Value;
                ans *= (tmp + 1);
                ans %= mod;
            }

            Console.WriteLine(ans - 1);
        }


    }
}


Measured memory_bytes: 28256
/**
 * @Author:      G_bg
 * @DateTime:    2019-08-04 20:06:30
 * @Description: 
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI = 3.1415926535898;
const double E = 2.718281828459;
const int INF = 0x7fffffff;
const int mod = 1e9+7;
const int maxn = 1e5+10;
int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin >> n;
    int sum = 0;
    for(int i = 1;i <= n;i++){
        int num = 0,j = i;
        while(j){
            num++;
            j /= 10;
        }
        if(num&1) sum++;
    }
    cout << sum << endl;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256