akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static final int MAX_CITY = 10;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			long[][] dist = new long[MAX_CITY][MAX_CITY];
			for (int i = 0; i < dist.length; i++) {
				for (int j = 0; j < dist[0].length; j++) {
					dist[i][j] = Integer.MAX_VALUE;
				}
			}
			for (int i = 0; i < MAX_CITY; i++) {
				dist[i][i] = 0;
			}
			int numEdge = sc.nextInt();
			if (numEdge == 0) break;
			int numCity = -1;
			for (int i = 0; i < numEdge; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				int c = sc.nextInt();
				dist[a][b] = c;
				dist[b][a] = c;
				if (numCity < a)
					numCity = a;
				if (numCity < b)
					numCity = b;
			}
			numCity++;

			// フロイドワーシャル
			dist = floydwarshall(dist, numCity);

			// 全対最短経路情報をもとに解答を算出
			int home = -1;
			long sum = Integer.MAX_VALUE;
			for (int u = 0; u < numCity; u++) {
				long total = 0;
				for (int v = 0; v < numCity; v++) {
					total += dist[u][v];
				}
				if (total < sum) {
					sum = total;
					home = u;
				}
			}
			System.out.printf("%d %d\n", home, sum);
		}
		sc.close();
	}

	static long[][] floydwarshall(long[][] dist, int numCity) {
		for (int k = 0; k < numCity; k++) {
			for (int u = 0; u < numCity; u++) {
				if (dist[u][k] == Integer.MAX_VALUE)
					continue;
				for (int v = 0; v < numCity; v++) {
					long total = dist[u][k] + dist[k][v];
					if (total < dist[u][v])
						dist[u][v] = total;
				}
			}
		}
		return dist;
	}
}

Measured memory_bytes: 19800
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
int a,b,num;
int main() {
	cin >> a >> b;
  num = max(a + b, a - b);
  num = max(num, a * b);
  cout << num << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b;
  cin>>a>>b;
  int cnt=0;
  if(b<a)cnt--;
  for(int i=1;i<=a;i++){
    for(int j=1;j<=a;j++){
      if(i==j)cnt++;
    }
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

n = int(input())
a = list(map(int, input().split()))

ans = 0 
d = {}
for i in a:
    if i not in d:
        d[i] = 1 
    else:
        d[i] += 1

d = sorted(d.items(), key=lambda x:x[0], reverse=True)
area = 1 
cnt = 0 
allone = True
for i in d:
    if 1 < i[1] < 4:
        allone = False
        if cnt == 2:
            break
        area *= i[0]
        cnt += 1
    elif i[1] >= 4:
        allone = False
        if cnt == 0:
            area = i[0]*i[0]
            break
        else:
            if cnt == 2:
                break
            area *= i[0]
            cnt += 1

if allone:
    print(0)
else:
    print(area)


Measured memory_bytes: 21772
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set>
//#define lowbit(x)  (x&(-x))
#define pb push_back
#define lson l , m , num << 1
#define rson m+1 , r , num << 1|1
#define fi first
#define se second
#define mod (1000000000+7)
#define M(a) memset(a,0,sizeof(a))
#define inf (0x3f3f3f3f3f3f3f3f)
#define INF (0x3f3f3f3f)
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;
ll a[maxn];
ll c[maxn];
ll b[maxn];
ll n, k;
int lowbit(int x) { return x & (-x); }
void add(int x, int z) {
	while (x < maxn) {
		c[x] += z;
		x += lowbit(x);
	}
}

ll sum(int x) {
	ll res = 0;
	while (x > 0) {
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}

int main() {
		memset(c, 0, sizeof(c));
		scanf("%lld%lld", &n, &k);
		ll ans = 0;
		a[0] = 0;
		for (int i = 1; i <= n; ++i) {
			scanf("%lld", &a[i]);
			a[i] -= k;
			a[i] += a[i - 1];
		}
		for (int i = 0; i <= n; ++i) {
			b[i] = a[i];
		}
		sort(b,b+1+n);
		int m = unique(b,b+n+1)-b;
		for(int i = 0;i<=n;++i){
			a[i] = lower_bound(b,b+m,a[i])-b+1;
		}
		for (int i = 0; i <= n; ++i) {
			ans+=sum(a[i]);
			add(a[i],1);
		}
		printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4992
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
py = [LI()+[i] for i in range(m)]

py.sort(key = lambda x:(x[0],x[1]))
ans = []
flag = True
cnt = 0
for p,y,i in py:
    s = '0'*6
    t = '0'*6
    if flag:
        cnt += 1
        tmp = p
        flag = False
    elif tmp == p:
        cnt += 1
    else:
        cnt = 1
        tmp = p
    s += str(p)
    s = s[-6:]
    t += str(cnt)
    t = t[-6:]
    ans.append([s+t,i])
ans.sort(key = lambda x:x[1])
for i,j in ans:
    print(i)


Measured memory_bytes: 93788
($n,$y) = split/ /,<>;

for($i=0;$i<=$n;$i++){
	for($j=0;$j<=$n;$j++){
    	$z=$n-$i-$j;
    	$sum=10000*$i+5000*$j+1000*$z;
        if($sum==$y && $z >= 0){
        	push @out,"$i"." "."$j"." "."$z";
        }
    }
}
if(@out){
	print $out[0];
}else{
	print "-1 -1 -1";
}

Measured memory_bytes: 512
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()

mod=998244353

ans=pow(3,N,mod)
S=sum(A)
dp=[0]*(S+1)
dp[0]=1
for u in A:
    h=[0]*(S+1)
    for i in range(u):
        h[i]=2*dp[i]%mod
    for i in range(u,S+1):
        h[i]=(dp[i-u]+2*dp[i])%mod
    dp=h

ans=(ans-3*sum(dp[S-S//2:]))%mod

if S%2==0:
    dp=[0]*(S//2+1)
    dp[0]=1
    for u in A:
        h=[0]*(S//2+1)
        for i in range(u):
            h[i]=dp[i]
        for i in range(u,S//2+1):
            h[i]=(dp[i]+dp[i-u])%mod
        dp=h
    ans=(ans+dp[S//2]*3)%mod
    
print(ans)

Measured memory_bytes: 113820
#include<cstdio>
#include<vector>
using namespace std;
int main(){
    vector<int> V, C;
    int x, n, ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        V.push_back(x);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        C.push_back(x);
    }
    for(int i = 0; i < n; i++)
        if(V[i] - C[i] > 0)
            ans += V[i] - C[i];
    printf("%d\n", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(a>b){
		swap(a,b);
	}if(b>c){
		swap(b,c);
    }if(a>b){
		swap(a,b);
	}cout<<a<<" "<<b<<" "<<c<<endl;
	
}




Measured memory_bytes: 3088
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>

using namespace std;

#define ll long long

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

    vector<int> c(4, 0);

    for(int i = 0;i < n;++i){
        string s;
        cin >> s;

        if(s == "AC"){
            c[0]++;
        }else if(s == "WA"){
            c[1]++;
        }else if(s == "TLE"){
            c[2]++;
        }else{
            c[3]++;
        }
    }

    cout << "AC x " << c[0] << endl;
    cout << "WA x " << c[1] << endl;
    cout << "TLE x " << c[2] << endl;
    cout << "RE x " << c[3] << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace fast {
    const int BSZ = 1 << 15; ////// INPUT
    char ibuf[BSZ];
    int ipos, ilen;

    char nc() { // next char
        if (ipos == ilen) {
            ipos = 0;
            ilen = fread(ibuf, 1, BSZ, stdin);
            if (!ilen)
                return EOF;
        }
        return ibuf[ipos++];
    }

    void rs(string &x) { // read string
        char ch;
        while (isspace(ch = nc()))
            ;
        do {
            x += ch;
        } while (!isspace(ch = nc()) && ch != EOF);
    }

    template <class T> void ri(T &x) { // read int or ll
        char ch;
        int sgn = 1;
        while (!isdigit(ch = nc()))
            if (ch == '-')
                sgn *= -1;
        x = ch - '0';
        while (isdigit(ch = nc()))
            x = x * 10 + (ch - '0');
        x *= sgn;
    }

    template <class T, class... Ts> void ri(T &t, Ts &... ts) {
        ri(t);
        ri(ts...);
    } // read ints
////// OUTPUT (call initO() at start)
    char obuf[BSZ], numBuf[100];
    int opos;

    void flushOut() {
        fwrite(obuf, 1, opos, stdout);
        opos = 0;
    }

    void wc(char c) { // write char
        if (opos == BSZ)
            flushOut();
        obuf[opos++] = c;
    }

    void ws(string s) {
        for (char c : s)
            wc(c);
    } // write string
    template <class T> void wi(T x, char after = '\0') { /// write int
        if (x < 0)
            wc('-'), x *= -1;
        int len = 0;
        for (; x >= 10; x /= 10)
            numBuf[len++] = '0' + (x % 10);
        wc('0' + x);
        for (int i = len - 1; i >= 0; i--)
            wc(numBuf[i]);
        if (after)
            wc(after);
    }

    void initO() { assert(atexit(flushOut) == 0); } /// auto-flush output
} // namespace fast
using namespace fast;

void solve() {
    int n, s = 0, a, b;
    ri(n);
    while(n--) {
        ri(a, b);
        if(s == 3)
            break;
        if(a == b)
            s++;
        else
            s = 0;
    }
    ws((s >= 3 ? "Yes" : "No"));
}

signed main() {
    initO();
        solve();
    return 0;
}

Measured memory_bytes: 3628
from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))

mod = 10 ** 9 + 7
Asum = list(accumulate(A))
X = Asum[-1]

ans = 0
for i, a in enumerate(A[:-1]):
    ans += a * (X - Asum[i])
    ans %= mod

print(ans)

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

int main(){
 int m,f,r;
 while(1){
  cin >> m >> f >> r;
  if(m==-1&&f==-1&&r==-1) break;
  
  if(m==-1||f==-1) cout << "F";
  else if((m+f)>=80) cout << "A";
  else if((m+f)>=65) cout << "B";
  else if((m+f)>=50||r>=50) cout << "C";
  else if((m+f)>=30&&r<50) cout << "D";
  else cout << "F";

  cout << endl;
 }
 return 0;
}

Measured memory_bytes: 3080
N = int(input())
X = list(map(int, input().split()))

msum=0
for i in range(N):
  msum+=X[i]
msum = int(msum/N)

num1=0
num2=0
for i in range(N):
  num1+=pow(X[i]-msum,2)
  num2+=pow(X[i]-(msum+1),2)
print(min(num1,num2))

Measured memory_bytes: 9032
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int planA, planB, n;
  cin >> n >> planA >> planB;
  
  planA = planA * n;
  
  if (planA < planB){
    cout << planA << endl;
  }
  else {
    cout << planB << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
	int n, x, t;

	cin >> n >> x >> t;

	if (n % x == 0) {
		cout << n / x * t << endl;
	}
	else {
		cout << ((n / x) + 1) * t << endl;
	}
	
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define INF 1e9
#define all(v) v.begin(), v.end()
typedef long long ll;

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

  set<int> s;
  rep(i, n){
    int a; cin >> a;
    s.insert(a);
  }

  cout << (s.size() == n ? "YES" : "NO") << endl;

  return 0;
}


Measured memory_bytes: 9600
n , m = map(int,input().split())
a = list(map(int,input().split()))
can_choice_item_list =[]
for item in a:
  if item < sum(a) / (4 * m):
    pass
  else:
    can_choice_item_list.append(item)
if m <= len(can_choice_item_list):
  print('Yes')
else:
  print('No')

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

int dp[100010];
vector <int> adj[100010];

void dfs(int x){
	
	dp[x]=0;
	
	for(int i:adj[x])
	{
		if(dp[i]==-1)
			dfs(i);
		dp[x]=max(dp[i]+1,dp[x]);	
		
	}
}

int main() {
	 int n,m,u,v;
	 cin>>n>>m;
	 fill(dp,dp+n,-1);
	 while(m--){
	 	cin>>u>>v;
	 	u--;v--;
	 	adj[u].push_back(v);
	 }
	 
	 for(int i=0;i<n;i++)
		if(dp[i]==-1) dfs(i);
		
	int r=0	;
	for(int i=0; i<n; i++) r=max(r,dp[i]);
	cout<<r;
	 
	return 0;
}

Measured memory_bytes: 8192
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    string s1,s2;
    cin>>s1>>s2;
    int dp[s1.size()+1][s2.size()+1],dir[s1.size()+1][s2.size()+1];
    for(int i = 0 ; i<= s1.size() ; i++){
        for(int j = 0 ; j<= s2.size() ; j++){
            dp[i][j] = 0;
            dir[i][j] = 0;
        }
    }
    for(int i = 1 ; i<=s1.size() ; i++){
        for(int j = 1 ; j<=s2.size() ; j++){
            if(s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    dir[i][j] = 0;
            }
            else {
                    if(dp[i-1][j]>dp[i][j-1]){
                        dp[i][j] = dp[i-1][j];
                        dir[i][j] = 1;
                    }
                    else{
                        dp[i][j] = dp[i][j-1];
                        dir[i][j] = 2;
                    }
            }
        }
    }
    int p= 0, q= 0,m = 0;
    for(int i = 1 ; i<=s1.size() ; i++){
        for(int j = 1 ; j<=s2.size() ; j++){
            if(dp[i][j] >m){
                p = i;
                q = j;
                m = dp[i][j];
            }
        }
    }
    char str[m];
    for(int i = 0 ; i<m ; i++) str[i] = '\0';
    /*for(int i = 1 ; i<=s1.size() ; i++){
        for(int j = 1 ; j<=s2.size() ; j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    for(int i = 1 ; i<=s1.size() ; i++){
        for(int j = 1 ; j<=s2.size() ; j++){
            cout<<dir[i][j]<<" ";
        }
        cout<<endl;
    }*/
    int i = m-1;
    while(1){
        if(dir[p][q] == 0){
            if(p == 0 || q == 0) break;
            str[i] = s1[p-1];
            i--;
            p--;
            q--;
        }
        else if(dir[p][q] == 1){
            p--;
        }
        else q--;
    }
    for(int j = 0 ; j<m ; j++){
        cout<<str[j];
    }
}


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


int main(){
  string s;
  cin >> s;
  int n=s.size();
  int gcnt=0;
  int pcnt=0;
  int ans=0;
  for(int i=0;i<n;++i){
    if(gcnt>pcnt){
      if(s[i]=='g') ans++;
      pcnt++;
    }else{
      if(s[i]=='p') ans--;
      gcnt++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3748
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define alli(a, n, k) (a + k), (a + n + k)
#define FP(i, a, b, k) for (__typeof(a) i = a; i < b; i += k)
#define FS(i, a, b, k) for (__typeof(a) i = a; i > b; i -= k)
#define IT(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template <class T>
inline T gcd(T x, T y)
{
	if (!y)
		return x;
	return gcd(y, x % y);
}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector<pair<int, int>> VPII;
typedef vector<pair<int, PII>> VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
	return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
	assert(__gcd(a, m) == 1);
	ll m0 = m;
	ll y = 0, x = 1;

	if (m == 1)
		return 0;

	while (a > 1)
	{
		ll q = a / m;
		ll t = m;

		m = a % m, a = t;
		t = y;

		y = x - q * y;
		x = t;
	}

	if (x < 0)
		x += m0;

	return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
	if (y == 0)
		return 1LL;
	else if (y == 1)
		return x;
	else
	{
		ll ans = modPow(x, y / 2, m) % m;
		if (y & 1)
		{
			return (((ans * ans) % m) * x) % m;
		}
		else
		{
			return (ans * ans) % m;
		}
	}
}

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	VII arr(n);
	for(auto &x:arr)cin>>x;
	VII dp;
	for(int i=arr.size()-1;i>=0;--i)
	{
		int x=arr[i];
		auto it=upper_bound(all(dp),x);
		if(it==dp.end())
		dp.pb(x);
		else *it=x;
	}
	cout<<dp.size();
	return 0;
}

Measured memory_bytes: 1276
import java.io.PrintWriter;
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int N = Integer.parseInt(sc.next());
		int Y = Integer.parseInt(sc.next());
		Y = Y/1000;
		int man = -1;
		int gosen = -1;
		int sen = -1;
		boolean flg = true;
		for(int i=0;i<=N;i++){
			if(!flg){
				break;
			}
			for(int j=0;j<=N-i;j++){
				if(Y== i*10+j*5+(N-i-j)){
					man = i;
					gosen = j;
					sen = N-i-j;
					flg = false;
					break;
				}
			}
		}
		out.println(man+" "+gosen+" "+sen);
		out.flush();	
	}
}

Measured memory_bytes: 21972
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
	int n;
	cin >> n;
	char *ho = "Hoshino";
	rep(i,n+1) {
		char c, s[2010];
		rep(j, 2000) {
			scanf("%c", &c);
			if(c == '\n') {
				s[j] = '\0';
				break;
			} else {
				s[j] = c;
			}
		}
		for(int j = 0; s[j] != '\0'; ++j) {
			int f = 1;
			rep(k,7) {
				if(s[j + k] != ho[k]) {
					f = 0;
					break;
				}
			}
			if(f) s[j + 6] = 'a';
		}
		if(i != 0) {
			printf("%s",s);
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define se second
#define mp make_pair
#define fi first
#define del(a,vec) vec.erase(std::remove(vec.begin(), vec.end(), a), vec.end());
#define search(f,l,v) binary_search(f,l,v)
#define iter(a,b) vector<int>::iterator a,b
#define lower(v,num) lower_bound (v.begin(), v.end(), num);
#define upper(v,num) upper_bound (v.begin(), v.end(), num); 
#define removecopy(a) unique(a.begin(), a.end()); 
#define ll long long int
namespace Rahul{
    bool isPrime(int n) 
    {if (n <= 1)  return false; if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
    return true; }
    ll pow (ll x, ll n,ll mod) {//calculate x^n
    if (n == 0) return 1;

    ll res = pow (x, n / 2,mod);

    res = (res * res) % mod;
    if (n % 2) res = (res * x ) % mod;

    return res;
    }
    ll _gcd(ll a,ll b)
    {
        if(a==0)
            return b;
        else    
            return _gcd(b%a,a);
    }
    //s.erase(s.find(2)) where s={1,2,3,3,2}; 
};

using namespace Rahul;
int main()
{
     ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin>>n;
    
     string s;
     cin>>s;
    unordered_map<char,char>cn;
    for(char i='A';i<'Z';i++)
        {
            cn[i]=i+1;
            
        }
    cn['Z']='A';    
    
    for(int i=0;i<s.size();i++)
        {
            int o=n;
           char c=s[i];
            while(o--)
                {
                    c=cn[c];
                }
            cout<<c;    
        }
        
                
}


Measured memory_bytes: 256
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

cnt = 0
ans = ''
for c in S:
    if c == '(':
        cnt += 1
    if c == ')':
        cnt -= 1
    if cnt < 0:
        cnt += 1
        ans += '('
ans += S + ')' * cnt
print(ans)


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

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

  for(int i=0; i<n; i++){
    int j = i;
    while(j > 0){
      if(a[j-1] > a[j])  swap(a[j-1], a[j]);
      else  break;
      j--;
    }
    for(int j=0; j<n; j++)
      printf("%d%c", a[j], j<n-1 ? ' ' : '\n');
  }

  return 0;
}


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

typedef long long int lli;
typedef vector<long long int> vlli;
typedef vector<vector<long long int>> vvl;
typedef pair<long long int, long long int> pll;
typedef map<long long int, long long int> mll;
#define pb push_back
#define fin for (lli i = 0; i < n; i++)
#define fi(n) for (lli i = 0; i < (n); i++)
#define fj(n) for (lli j = 0; j < (n); j++)
#define fiv for (lli i = 0; i < v.size(); i++)
#define fis for (lli i = 0; i < s.size(); i++)
#define vs v.size()
#define ss s.size()

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli TC = 1;
    // cin >> TC;
    for (lli TT = 1; TT<=TC; TT++) {
        // cout << "Case #" << TT << ": ";
        lli n,k,a;
        cin >> n >> k;
        vlli v, m(n);
        fin{
            cin >> a;
            v.pb(a);
        }
        m[n-1]=0;
        // m[n-2]=abs(v[n-1]-v[n-2]);
        for(lli i=n-2;i>=0;i--){
            lli mi= abs(v[i+1]-v[i])+m[i+1];
            for(lli j=i+1;j<min(n,i+k+1);j++){
                mi=min(mi,abs(v[j]-v[i])+m[j]);
            }
            m[i] = mi;
        }
        cout << m[0];
    }
    return 0;
}

Measured memory_bytes: 2168
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	r := bufio.NewScanner(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	r.Split(bufio.ScanWords)
	r.Scan()
	n, _ := strconv.Atoi(r.Text())
	r.Scan()
	k, _ := strconv.Atoi(r.Text())
	a := make([]int, n)

	for i := 0; i < n; i++ {
		r.Scan()
		a[i], _ = strconv.Atoi(r.Text())
	}

	k1 := (k * (k + 1) / 2) % (1000000007)
	k2 := (k * (k - 1) / 2) % (1000000007)
	total := 0
	for i := 0; i < n; i++ {
		mae, ato := 0, 0
		for j := 0; j < n; j++ {
			if (j < i) && (a[i] < a[j]) {
				mae++
			}
			if (j > i) && (a[i] < a[j]) {
				ato++
			}
		}

		total += (mae * k1) % (1000000007)
		total = total % (1000000007)
		total += (ato * k2) % (1000000007)
		total = total % (1000000007)
	}

	fmt.Fprint(w, total)

}


Measured memory_bytes: 1804
import java.util.*;

public class Main {

    
    public static void main(String[] args) {
   Scanner scanner = new Scanner(System.in);
   int [] nums = new int[5];
   for(int i = 0 ; i<5;i++){
   nums[i] = scanner.nextInt();
   }
   for(int i = 0 ; i<5;i++){
   if(nums[i]  == 0){
       System.out.println(i+1);
   }
   }
    }
    
}


Measured memory_bytes: 35708
#include<bits/stdc++.h>
using namespace std;
int n;
char a[310][310],b[310][310];
long long as;
bool chk(){
	register int i,j;
	for(i = 2;i <= n;++i){
		for(j = 1;j < i;++j){
			if(b[i][j] != b[j][i]) return 0;
		}
	}
	return 1;
}
int main(){
	register int i,j,k;
	cin>>n;
	for(i = 1;i <= n;++i) scanf("%s",a[i] + 1);
	for(i = 0;i < n;++i){
		for(j = 1;j <= n;++j){
			for(k = 1;k <= n;++k) b[j][(k + i - 1) % n + 1] = a[j][k];
		}
		if(chk()) as += n;
	}
	cout<<as;
	return 0;
}

Measured memory_bytes: 384
N,Q=map(int,input().split())
S=input()
A=[0]
res=0
for i in range(N):
  if i !=0:
    if S[i-1]=="A" and S[i]=="C":
      res+=1
      A.append(res)
    else:
      A.append(res)
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])

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

using namespace std;

string s;

int main()
{
    cin >> s;

    int sum = 0;
    for(int i = 0; i < s.size(); i ++)
        sum += s[i] - '0';

    cout << (sum % 9 ? "No\n" : "Yes\n");

    return 0;
}


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

#define ll long long int
#define str string
#define ALL(a)  (a).begin(),(a).end()
#define P pair<double,ll>

using Graph = vector<vector<int>>;

const int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
ll INFL = 1ll << 60, INF = 1 << 30, mod = 1e9 + 7, Min = INFL, Max = -1;
ll a, b, c, n, sum, A[500010], B[500000], dp[5000];
str S[200010]; bool check = true;	vector<ll> v;



int main() {
	//Code Line
	cin >> n;
	map<str, ll> m;
	for (int i = 0; i < n; i++) {
		cin >> S[i];

		m[S[i]]++;

	}

	for (int i = 0; i < n; i++) {

		Max = max(Max, m[S[i]]);

	}

	sort(S, S + n);

	for (int i = 0; i < n; i++) {

		if (Max == m[S[i]])cout << S[i] << endl;

		m[S[i]] = 0;
	}



	return 0;
}


Measured memory_bytes: 27136
// review
#include <iostream>
#include <algorithm>
#include <functional>
#include <iomanip>

using namespace std;
typedef long long ll;
int n, a, b;
ll v[60];
ll combination[60][60];

void init() {
  for (int i=0;i<60;i++) {
    for (int j=0;j<=i;j++) {
      if (j == 0 || i == j) {
        combination[i][j] = 1;
      } else {
        combination[i][j] = combination[i-1][j-1] + combination[i-1][j];
      }
    }
  }
}

ll nCr(int n, int r) {
  return combination[n][r];
}

void solve() {
  init();
  sort(v, v+n, greater<ll>());
  ll sum = 0;
  for (int i=0;i<a;i++) {
    sum += v[i];
  } 
  int lastTotalCnt = 0;
  int lastRequiredCnt = 0;
  for (int i=0;i<n;i++) {
    if (v[i] == v[a-1]) {
      if (i < a) {
        lastRequiredCnt++;
      }
      lastTotalCnt++;
    }
  }
  // If v[0] = v[1] = ... = v[a-1], then we can count the combination
  // If total number of v[0] is m, sum is going to be mCa + ... + mCb.
  //
  // Since at least v[0] > v[a-1], v[a] is also less than v[0].
  // i.e. avg(v[0] + ... + v[a-1]) > v[a] so in this case, count is going to be
  // (total number of a-th value) C (required number of a-th value)
  ll tot = 0;
  if (lastRequiredCnt == a) {
    for (int i=a;i<=b;i++) {
      tot += nCr(lastTotalCnt, i);
    }
  } else {
    tot = nCr(lastTotalCnt, lastRequiredCnt);
  }
  cout << fixed << setprecision(20) << (double)sum / (double)a << endl;
  cout << tot << endl;
}

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


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var stdInScanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	stdInScanner.Scan()
	i, _ := strconv.Atoi(stdInScanner.Text())
	return i
}

func nextString() string {
	stdInScanner.Scan()
	return stdInScanner.Text()
}

func main() {
	var S, T string

	fmt.Scanf("%s", &S)
	fmt.Scanf("%s", &T)

	var counter int
	for i := range S {
		if S[i] != T[i] {
			counter++
		}
	}
	fmt.Println(counter)
}


Measured memory_bytes: 4588
#include <iostream>
#include<set>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<string,int> Ps;

multiset<string> ms;
vector<Ps> v;

int main(void){
    
    int n;
    
    cin >> n;
    
    for(int i=0;i<n;i++){
        string tmp;
        cin >> tmp;
        ms.insert(tmp);
    }
    
    multiset<string>:: iterator msi;
    string bef;
    for(msi=ms.begin();msi!=ms.end();msi++){
        
        if(bef!=*msi){
            v.push_back(make_pair(*msi,ms.count(*msi)));
        }
        bef=*msi;
    }
    
    int Max=0;
    for(int i=0;i<v.size();i++){
        if(Max<v[i].second){
            Max=v[i].second;
        }
    }
    
        for(int i=0;i<v.size();i++){
        if(Max==v[i].second){
            cout << v[i].first  << endl;
        }
    }
    
    return 0;
    
}


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

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

int main() {
  int n;
  cin >> n;
  int a[n];
  rep(i, n) cin >> a[i];
  sort(a, a + n, greater<int>());
  int Alice = 0;
  int Bob = 0;
  rep(i, n) {
    if (i % 2 == 0) {
      Alice += a[i];
    } else {
      Bob += a[i];
    }
  }
  cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long a,b,k;
  cin>>a>>b>>k;
  if(k>a){
  k-=a;
  a=0;
  }else{
    a-=k;
    k=0;
  }
  if(k>b){
  k-=b;
  b=0;
  }else{
    b-=k;
    k=0;
  }
  cout<<a<<" "<<b;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mod 1000000007 //10^9+7
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
int n,m,k;
signed main(){
    cin>>n>>m>>k;
    for(int x=0;x<=n;x++){
        for(int y=0;y<=m;y++){
            int b=m*x+n*y-2*x*y;
            if(b==k){
                puts("Yes");
                return 0;
            }
        }
    }
    puts("No");
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var items = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            var A = items[0];
            var B = items[1];
            var answer = Math.Max(A - (B * 2), 0);

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 13268
s = gets.strip
count = 0
if s.length == 1
  puts 0
  exit
end

if s.length.odd?
  1.upto((s.length - 1) / 2) do |i|
    count += 1 if s[i - 1] != s[-i]
  end
else
  1.upto(s.length / 2) do |i|
    count += 1 if s[i - 1] != s[-i]
  end
end

puts count

Measured memory_bytes: 1788
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#define int long long
#define ll getchar();getchar();return 0;
using namespace std;
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n%i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	int ans;
	for (int i = (min(x, y)); i >= 1; i--) {
		if (x%i == 0 && y%i == 0) {
			ans = i;
			break;
		}
	}
	return ans;
}
int yakusuunowa(int n) {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (n%i == 0)ans += i;
	}
	return ans;
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int ketanowa(int n) {
	int cnt = 0, sum = 0;
	for (int i = 10; i <= n * 10; i *= 10) {
		if (i == 10)cnt += n % i;
		else sum += (n%i - n % (i / 10)) / (i / 10);
	}
	return cnt + sum;
}
int a[114514], dp[114514];
signed main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	dp[0] = 0;
	dp[1] = abs(a[1] - a[0]);
	for (int i = 2; i < n; i++)dp[i] = min(dp[i - 2] + abs(a[i] - a[i - 2]), dp[i - 1] + abs(a[i] - a[i - 1]));
	cout << dp[n - 1] << endl;
	ll
}

Measured memory_bytes: 1792
/*
 ▓█████▄  ▄████▄  ▓██   ██▓ ██▓███   ██░ ██ ▓█████  ██▀███
▒██▀ ██▌▒██▀ ▀█   ▒██  ██▒▓██░  ██▒▓██░ ██▒▓█   ▀ ▓██ ▒ ██▒
 ░██   █▌▒▓█    ▄   ▒██ ██░▓██░ ██▓▒▒██▀▀██░▒███   ▓██ ░▄█ ▒
 ░▓█▄   ▌▒▓▓▄ ▄██▒  ░ ▐██▓░▒██▄█▓▒ ▒░▓█ ░██ ▒▓█  ▄ ▒██▀▀█▄
 ░▒████▓ ▒ ▓███▀ ░  ░ ██▒▓░▒██▒ ░  ░░▓█▒░██▓░▒████▒░██▓ ▒██▒
  ▒▒▓  ▒ ░ ░▒ ▒  ░   ██▒▒▒ ▒▓▒░ ░  ░ ▒ ░░▒░▒░░ ▒░ ░░ ▒▓ ░▒▓░
  ░ ▒  ▒   ░  ▒    ▓██ ░▒░ ░▒ ░      ▒ ░▒░ ░ ░ ░  ░  ░▒ ░ ▒░
  ░ ░  ░ ░         ▒ ▒ ░░  ░░        ░  ░░ ░   ░     ░░   ░
    ░    ░ ░       ░ ░               ░  ░  ░   ░  ░   ░
  ░      ░         ░ ░
*/
//focus less on how much problem you should solve within a fixed time and focus more on getting the problem solved and
//learning something from it
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define per(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vii vector <pair<ll,ll> >
#define sedes set <ll, greater <ll> >
#define seasc set <ll>
#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define MOD 1000000007
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define umap unordered_map<ll, ll>
#define map map<ll, ll>
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define mems(a, i) memset(a, i, sizeof(a))
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define printx(x) printf("%lld\n",x);
#define printxy(x,y) cout << x << y <<endl;
#define printxyz(x,y,z) cout << x << y << z <<endl;
#define deba(a) cout << #a << a << endl;
#define debab(a,b) cout << #a << a << #b << b << endl;
int main()
{
	fast;
	ll n, k, x, y, ans = 0;
	cin >> n >> k >> x >> y;
	if (n > k)
	{
		cout << k*x + (n - k)* y << endl;
	}
	else
	{
		cout << n*x << endl;
	}


	return 0;
}

Measured memory_bytes: 3624
def main():
    _, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]
    ans = 0
    if P == 2:
        for i, v in enumerate(S, start=1):
            if v % 2 == 0:
                ans += i
    elif P == 5:
        for i, v in enumerate(S, start=1):
            if v == 0 or v == 5:
                ans += i
    else:
        cnt = [0]*P
        d = 1
        pre = 0
        cnt[pre] += 1
        for v in S[::-1]:
            v *= d
            v += pre
            v %= P
            cnt[v] += 1
            d *= 10
            d %= P
            pre = v

        ans = sum(cnt[i]*(cnt[i]-1)//2 for i in range(P))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 86900
fun main(args: Array<String>) {
	val n = readLine()!!.toInt()
	var arr = IntArray(n)
	var sum = 0
	for (i in 0..(n - 1)) {
		val num = readLine()!!.toInt()
		arr[i] = num 
		sum += num
	}
	arr.sort()
	if (sum % 10 != 0) {
		println(sum)
	} else {
		var index = 0
		while (index < arr.size && arr[index] % 10 == 0) {
			index += 1
		}
		if (index == arr.size) {
			println(0)
		} else {
			println(sum - arr[index])
		}
	}
	
}

Measured memory_bytes: 34132
<?php
	fscanf(STDIN, "%d", $n);
	fscanf(STDIN, "%s", $s);

	if (($n % 2) != 0) {
		echo "No";
		exit;
	}

	$d = $n / 2;
	$before = substr($s, 0, $d);
	$after = substr($s, $d, $d);

	if ($before == $after) {
		echo "Yes";
	} else {
		echo "No";
	}



Measured memory_bytes: 3704
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e6+5;
 
bool is_prim(int x){
    if(x <= 1)
        return false;
    for(int i = 2; i*i <= x; i++){
        if(x % i == 0)
            return false;
    }
    return true;
}
 
int main(){
    int x;
    cin >> x;
    while(true){
        if(is_prim(x)){
            cout << x << "\n";
            return 0;
        }
        x++;
    }
    //
}


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

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

  sort(a, a + n);
  if (n == 2) {
    cout<<a[1]<<" "<<a[0]<<endl;
    return 0;
  }

  int b = a[n-1];
  if (a[0] >= (double)(b + 1) / 2) {
    cout<<b<<" "<<a[0]<<endl;
    return 0;
  }
  for (int i=0; i<n-1; i++) {
    if (a[i] == (double)(b + 1) / 2) {
      cout<<b<<" "<<a[i]<<endl;
      return 0;
    } else if (a[i] > (double)(b + 1) / 2) {
      double d1 = (double)(b + 1) / 2 - (b - a[i]);
      double d2 = (double)(b + 1) / 2 - a[i-1];
      if (d1 < d2) {
        cout<<b<<" "<<a[i]<<endl;
      } else {
        cout<<b<<" "<<a[i-1]<<endl;
      }
      return 0;
    }
  }
  cout<<b<<" "<<a[n-2]<<endl;
}

Measured memory_bytes: 640
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use std::mem::swap;

#[fastout]
fn main() {
    input! {
    n: usize,
    ab: [(Usize1, Usize1); n - 1]
    }
    let mut g: Vec<Vec<usize>> = vec![vec![]; n];
    let mut nc = vec![0; n];
    for i in 0..n - 1 {
        let (a, b) = ab[i];
        g[a].push(b)
    }
    for i in 0..n - 1 {
        let mut c = 1;
        for &j in &g[i] {
            if c == nc[i] {c += 1};
            nc[j] = c;
            c += 1;
        }
    }
    let k = nc.iter().max().unwrap();
    println!("{}", k);
    for i in 0..n - 1 {
        let (_, b) = ab[i];
        println!("{}", nc[b]);
    }
}



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

using namespace std;

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

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

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

	int n;
	cin >> n;

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

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

	ll aSum = accumulate(a.begin(), a.end(), 0LL);
	ll bSum = accumulate(b.begin(), b.end(), 0LL);

	if (bSum - aSum < 0) {
		cout << "No" << endl;
		return 0;
	}

	ll cnt = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] > b[i]) {
			cnt += a[i] - b[i];
		} else if (a[i] % 2 != b[i] % 2) {
			cnt++;
		}
	}

	cout << (cnt <= bSum - aSum ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include <iomanip>
#include<deque>
#include<stack>
#include<set>
#include <numeric>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
const int INF = 111111111;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const int DIV = 1000000007; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;


int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	//==================================

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

	int ans = 0;


	while (true) {
		bool end = true;
		bool past = bool(H[0]);
		bool now = false;// 水をやるかどうか

		for (int i = 0; i < N; i++) {
			if (H[i] > 0) {
				H[i]--;

				now = true;

				end = false;
			}
			else {
				now = false;
			}


			if ((!now && past) || (i == N-1 && now)) {
				ans++;
			}

			past = now;

		}

		if (end) {
			cout << ans;
			return 0;
		}


	}


}	


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int main(){
	ll n; scanf("%lld", &n);
	printf("%lld\n", n*(n-1)/2);
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val x = readLine()!!.toInt()
    val dAccum = mutableListOf(0L)
    for (i in 1..100000) {
        dAccum.add(dAccum[i - 1] + i)
    }
    println(dAccum.filter { it < x }.size)
}

Measured memory_bytes: 40440
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10;



int main()
{
    fastInp;

    ll x, k, d;
    cin >> x >> k >> d;

    x = abs(x);
    ll q = x / d;
    if (q >= k) {
        cout << x - k * d;
        return 0;
    }

    x -= q * d;
    k -= q;
    if (k % 2 == 0) {
        cout << x;
    } else {
        cout << abs(x - d);
    }

    return 0;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
//order_of_key(k)= # of items strictly smaller than 'k'  //find_by_order(x)= iterator to x'th largest element (counting from ZERO) //erase("iterator") [log(n)] //end(<name>)
//os.find_by_order(os.order_of_key(x)=iterator to 'x' in the rb tree
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef priority_queue<ll> pq;                                        //min-heap-> multiply the values by '-1'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define forr(i,a,b) for (ll i = a; i < b; i++)
#define test ll t;cin>>t;while(t--)
#define summ(a,n) accumulate(a,a+n,0)
#define bsrch(v,n) lower_bound(v.begin(), v.end(), n)
#define minindex(v) distance(v.begin(),min_element(v.begin(),v.end()))         //returns index of minimum(/max) element in the vector
#define bp(x) _builtin_popcount(x)
#define inf 1000000000000
#define PI = 3.1415926535897932384626
#define mod 1000000007

ll dp[101][100001];

int main()
{
    ll n,k; cin>>n>>k;
    ll a[n+1];
    forr(i,1,n+1) cin>>a[i];
    
    forr(i,1,n+1) dp[i][0]=1;
    forr(i,1,k+1)
    {
        if(i<=a[1]) dp[1][i]=1;
        dp[1][i]=(dp[1][i-1]%mod + dp[1][i]%mod)%mod;
    }
    
    forr(i,2,n+1)
        forr(j,1,k+1)
        {
            ll x=0;
            if(j>a[i]) x=dp[i-1][j-a[i]-1];
            dp[i][j]=(dp[i-1][j]%mod - x%mod + mod)%mod;
            if(i!=n) dp[i][j]=(dp[i][j-1]%mod + dp[i][j]%mod)%mod;
        }

    if(n==1) 
        if(k==a[1]) cout<<1;
        else cout<<0;
    else cout<<dp[n][k];
}

Measured memory_bytes: 81696
#include<stdio.h>

int main(void){
	
	int a,b,c,d;
	scanf("%d %d %d",&a,&b,&c);
	
	if(a>b){
		d=a;
		a=b;
		b=d;
		
	}
	if(a>c){
		d=a;
		a=c;
		c=d;
	}
	if(b>c){
		d=b;
		b=c;
		c=d;
	}
	
	printf("%d %d %d\n",a,b,c);
	
	
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>
#include <cstdlib> //絶対値 abs()
#include <iomanip>
using namespace std;

double PI = 3.141592653589793;

int main(){
	int a,b,h,m;
	cin >> a >> b >> h >> m;
  
	cout << setprecision(11) << pow(a*a + b*b -2 *a *b * cos( PI * (60 * h - 11 * m) /360),0.5) << endl;


}


Measured memory_bytes: 4324
N=int(input())
T,A = map(int, input().split(' '))
places=[int(x) for x in input().split()]

diff = abs( A - T - places[-1]*0.006)
num = N

for i in range(N-1):
  temperature = abs( A - (T - places[i]*0.006))
  if diff > temperature:
    diff = temperature
    num=i+1

print(num)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
int n;
pair<int,int>a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].fi,&a[i].se);
    sort(a+1,a+1+n);
    if(n&1)
    {
        int m=n/2+1,low=a[m].fi;
        for(int i=1;i<=n;i++) swap(a[i].fi,a[i].se);
        sort(a+1,a+1+n);
        int up=a[m].fi;
        printf("%d\n",up-low+1);
    }
    else
    {
        int m=n/2,low=a[m].fi+a[m+1].fi;
        for(int i=1;i<=n;i++) swap(a[i].fi,a[i].se);
        sort(a+1,a+1+n);
        int up=a[m].fi+a[m+1].fi;
        printf("%d\n",up-low+1);
    }
}


Measured memory_bytes: 5376
#include <iostream>

using namespace std;
char cell[51][51];

int main()
{
    int n, m, cnt;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        cin >> cell[i][j];

    for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (cell[i][j] == '.') {
            cnt = 0;
            for (int ln = i - 1; ln <= i + 1; ++ln)
            for (int col = j - 1; col <= j + 1; ++col)
                if ((ln != i || col != j) && cell[ln][col] == '#')
                    cnt++;
            cell[i][j] = 48 + cnt;
        }
        cout << cell[i][j];
        }
        cout << "\n";
    }

    return 0;
}


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

int main(void)
{
    long long N, A, B;
    cin >> N >> A >> B;

    if (A == 0) {
        cout << 0 << endl;
    }
    else if (B == 0) {
        cout << N << endl;
    }
    else if (A >= N) {
        cout << N << endl;
    }
    else if (A + B >= N) {
        cout << A << endl;
    }
    else{
        long long x = N % (A + B);
        if (x > A) {
            cout << (((N / (A + B)) * A) + A) << endl;
        }
        else {
            cout << (((N / (A + B)) * A) + (N % (A + B))) << endl;
        }
    }

    return 0;
}

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

using namespace std;
typedef pair<int, int> P;

void solve()
{
	int n;
	while(cin >> n, n)
	{
		vector<P> Vec(n);
		for(int i = 0; i < n; ++i)
		{
			int temp1, temp2;
			cin >> Vec[i].second >> temp1 >> temp2;
			Vec[i].first = temp1 + temp2;
		}
		sort(Vec.begin(), Vec.end(), greater<P>() );
		cout << Vec[0].second << " " << Vec[0].first << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 984
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd
#include <limits> // std::numeric_limits<int>::max()

template<typename T>
T powint (const T& x, const T& y) {
  T ret = 1;
  for(int i=0; i<y; ++i) ret *= x;
  return ret;
}

int main() {
  long int N;
  std::cin >> N;
  std::vector<long int> X(N);
  for (int i=0; i<N; ++i) std::cin >> X[i];
 
  long int maxrange = 0;
  for (const auto x : X) maxrange = std::max(maxrange, x);

  long int minsum = std::numeric_limits<long int>::max();
  for (int i=1; i<maxrange+1; ++i) {
    long int sum = 0;
    for (const auto x : X) sum += (x-i)*(x-i);
    minsum = std::min(minsum, sum);
  }

  std::cout << minsum << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<unordered_map>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 50
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
ll ans = 0;
struct UnionFind {
	vector<int> rank, parent;
	UnionFind() {};
	UnionFind(int size) :rank(size, 0), parent(size, 0) {
		for (int i = 0; i < size; i++)makeset(i);
	}

	void makeset(int x) {
		parent[x] = x;
		rank[x] = 0;
	}

	bool same(int x, int y) {
		return findset(x) == findset(y);
	}

	int findset(int x) {
		if (x != parent[x]) {
			parent[x] = findset(parent[x]);
		}
		return parent[x];
	}

	void unite(int x, int y) {
		link(findset(x), findset(y));
	}

	void link(int x, int y) {
		if (rank[x] > rank[y])parent[y] = x;
		else {
			parent[x] = y;
			if (rank[x] == rank[y])rank[y]++;
		}
	}
};
int main() {
	cin >> N >> M;
	vector<int> p(N + 1);
	UnionFind uf(N + 1); //UFの下準備
	for (int i = 1; i <= N; i++)cin >> p[i];
	for (int i = 1; i <= M; i++) {
		int x, y;
		cin >> x >> y;
		uf.unite(x, y);
	}
	for (int i = 1; i <= N; i++) {
		if (uf.same(p[i],i))ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1408
s = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'

ls = list(map(int, s.split(', ')))

k = int(input())

print(ls[k-1])

Measured memory_bytes: 2940
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
for x in range(h):
    for y in range(w):
        if(s[x][y] == '#'):
            up = s[max(0, x-1)][y]
            down = s[min(h-1, x+1)][y]
            right = s[x][max(0, y-1)]
            left = s[x][min(w-1,  y+1)]
            if(up == '.' and down == '.' and right == '.' and left == '.'):
                print("No")
                exit()
print("Yes")


Measured memory_bytes: 3064