akhauriyash/Code-Regression huggingface dataset:
// AOJ 1622 Go around the Labyrinth
// 2018.2.13 bal4u

#include <stdio.h>
#include <string.h>

typedef struct { char r, c; } Q;
Q q[2000]; int top;
int h, w;
char map[53][53];
int mv4[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int mv9[9][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{-1,1},{-1,0},{1,1}};
char mk[53][53];

int check()
{
	int i, r, c, nr, nc, f;

	memset(mk, 0, sizeof(mk));
	q[0].r = 1, q[0].c = 1, top = 1;
	mk[1][1] = 1;
	f = 0;
	while (top) {
		r = q[--top].r, c = q[top].c;
		if      (r == 1) { if (c == w) f++; }
		else if (r == h) {
			if      (c == 1) f++;
		    else if (c == w) f++;
		}
		if (f == 3) return 0;
		for (i = 0; i < 4; i++) {
			nr = r + mv4[i][0], nc = c + mv4[i][1];
			if (!map[nr][nc] || mk[nr][nc]) continue;
			mk[nr][nc] = 1;
			q[top].r = nr, q[top++].c = nc;
		}
	}
	return 1;
}

int main()
{
	int r, c, i, f, nr, nc;
	char buf[10], *p;

	while (fgets(buf, 10, stdin) && *buf != '0') {
		sscanf(buf, "%d%d", &h, &w);
		memset(map, 0, sizeof(map));
		for (r = 1; r <= h; r++) {
			fgets(p = map[r]+1, 52, stdin);
			c = w; while (c--) *p = (*p == '.'), p++; *p = 0;
		}

		if (check()) goto no;
		for (r = 1; r <= h; r++) for (c = 1; c <= w; c++) {
			if (r == 1 && c == 1 || r == 1 && c == w ||
				r == h && c == 1 || r == h && c == w) continue;
			if (!map[r][c]) continue;
			f = 0;
			for (i = 0; i < 9; i++) {
				nr = r + mv9[i][0], nc = c + mv9[i][1];
				if (!map[nr][nc]) { f = 1; break; }
			}
			if (f) {
				map[r][c] = 0;
				if (check()) goto no;
				map[r][c] = 1;
			}
		}
		puts("YES"); continue;
no:		puts("NO");
	}
	return 0;
}



Measured memory_bytes: 2028
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<int> vi;

//
#define ALL(c) (c).begin(),(c).end()

typedef vector<vi> Graph;

bool visit(const Graph &g, int v, vector<int> &order, vector<int> &color) {
  color[v] = 1;
  foreach(e, g[v]) {
    if (color[*e] == 2) continue;
    if (color[*e] == 1) return false;
    if (!visit(g, *e, order, color)) return false;
  }
  order.push_back(v); color[v] = 2;
  return true;
}
bool toposort(const Graph &g, vector<int> &order, bool rev) {
  int n = g.size();
  vector<int> color(n);
  if(rev==0){
	  rep(u, n) if (!color[u] && !visit(g, u, order, color))
	    return false;
  }else{
  	  for(int u=n-1;u>=0;u--) if (!color[u] && !visit(g, u, order, color))
	    return false;
  }
  reverse(ALL(order));
  return true;
}
//

int n,m;
Graph g;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>n>>m;
	g.resize(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		a--;b--;
		g[a].pb(b);
	}
	vi order1,order2;
	toposort(g,order1,0);
	rep(i,n)cout<<order1[i]+1<<endl;
	rep(i,n)reverse(g[i].begin(),g[i].end());
	toposort(g,order2,1);
	cout<<(order1!=order2)<<endl;
}

Measured memory_bytes: 2244
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	ll a, b; cin >> a >> b;
	if( (a+b)%2 == 1 ) cout << "IMPOSSIBLE" << endl;
	else cout << (a+b)/2 << endl;
	return 0;
}

Measured memory_bytes: 256
/*
2017_04_24_AC
<point>
???(?????¨????????????????????¨??????????????¨???????????°???????????????)?????¶?????¨??????????????????????????????priority_queue???
<caution>
 ???U?????????????????¶?????????????????????
*/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)
#define D first
#define C second

using namespace std;

const double INF = 1000000000.0;

double d[35][35][35];
bool visited[35][35][35];
int N,M,S,G;
pair<int, int> p[35][35];

struct ST{
  double ti;
  int bn;
  int cn;
  int sp;
  ST(double _ti, int _bn, int _cn, int _sp){
    ti = _ti;
    bn = _bn;
    cn = _cn;
    sp = _sp;
  }

  bool operator >(const ST &e) const{
    return ti > e.ti;
  }

};

int main() {
  while(1){
    cin>>N>>M;
    if(N==0 && M==0) break;
    cin>>S>>G;
    S--; G--;

    REP(i,0,N)REP(j,0,N)REP(k,0,35) d[i][j][k] = INF;
    REP(i,0,N)REP(j,0,N)REP(k,0,35) visited[i][j][k] = false;
    REP(i,0,N)REP(j,0,N) p[i][j].D = p[i][j].C = -1;

    REP(i,0,M){
      int x,y,d,c;
      cin>>x>>y>>d>>c;
      p[x-1][y-1].D = p[y-1][x-1].D = d;
      p[x-1][y-1].C = p[y-1][x-1].C = c;
    }

    d[S][S][0] = 0.0;

    priority_queue< ST, vector<ST>, greater<ST> > PQ;
    ST st(0.0,S,S,0);
    PQ.push(st);

    bool flag = true;
    while(!PQ.empty()){
      ST u = PQ.top(); PQ.pop();
      double mtime = u.ti;
      int ubn=u.bn, ucn=u.cn, usp=u.sp;
      //visited[ubn][ucn][usp] = true;
      if(d[ubn][ucn][usp] < mtime) continue;

      if(ucn == G && usp == 1){
        printf("%.5lf\n",d[ubn][ucn][usp]);
        flag = false;
        break;
      }

      visited[ubn][ucn][usp] = true;
      for(int v = usp-1; v <= usp+1; v++){
        if(v <= 0) continue;
        REP(next,0,N){
          if(/*visited[ucn][next][v] ||*/ p[ucn][next].D == -1 || p[ucn][next].C < v || ucn == next || ubn == next) continue;
          if(d[ucn][next][v] > mtime + (double)p[ucn][next].D/(double)v){
            d[ucn][next][v] = mtime + (double)p[ucn][next].D/(double)v;
            ST tst(d[ucn][next][v], ucn,next,v);
            PQ.push(tst);
          }
        }
      }

    }
    if(flag){
      cout<<"unreachable"<<endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3804
#include <stdio.h>

int main(){
	int N;
	int AC = 0, WA = 0, TLE = 0, RE = 0;
	char S[5];
	scanf("%d", &N);
	for (int i = 0; i < N; i++){
		scanf("%s", &S);
		if (S[0] == 'A'){
			AC++;
		}else if(S[0] == 'W'){
			WA++;
		}else if(S[0] == 'T'){
			TLE++;
		}else if(S[0] == 'R'){
			RE++;
		}
	}
	printf("AC x %d\n", AC);
	printf("WA x %d\n", WA);
	printf("TLE x %d\n", TLE);
	printf("RE x %d\n", RE);
	return 0;
}

Measured memory_bytes: 1736
N = int(input())
p = list(map(int, input().split()))
t = list(map(int, input().split()))

ans = 10 ** 10
#aの最大個数
A = max(0, (N + t[0] - 1)// t[0])
for a in range(A+1):
    #aの個数が決まったときのbの最大個数
    B = max(0, (N - a * t[0] + t[1] - 1)//t[1])
    for b in range(B+1):
        #a,bの個数が決まったときのcの最大個数
        C = max(0, (N - a * t[0] - b * t[1] + t[2] - 1)//t[2])
        for c in range(C+1):
            #a,b,cの個数が決まったときのdの個数(残りは全てdとする)
            D = max(0, (N - a * t[0] - b * t[1] - c * t[2] + t[3] - 1)//t[3])
            cost = a * p[0] + b *p[1] + c * p[2] + D * p[3]
            # print (a, b, c, D, cost)
            ans = min(ans, cost)

print (ans)




Measured memory_bytes: 5612
#include<bits/stdc++.h>
#define mod 10000000000000
#define mod1 998244353
#define Mmax 1000005
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int li;
typedef unsigned long long int ull;
using namespace std;
bool sortbysec(const pair<li,li>&a,const pair<li,li>&b)
{
    return (a.second<b.second);
}
bool comp(pair<li,pair<li,li>>a,pair<li,pair<li,li>>b)
{
  if(a.first<b.first)
  return 1;
  else if(a.first>b.first)
  return 0;
  else
  {
    return a.second.first<b.second.first;
  }
}
li mpow(li x,li y)
{
  li ans=1;
  while(y)
  {
    if(y%2!=0)
    ans=(ans%mod)*(x%mod)%mod;
    y/=2;
    x=((x%mod)*(x%mod))%mod;
  }
  return ans;
}
li modInverse(li n)
{
    return mpow(n, mod-2);
}

li nCrModPFermat(li n, li r,li x,li y,li z)
{
   // Base case
   if (r==0)
      return 1;
    // li fac[n+1];
    // fac[0] = 1;
    // for (int i=1 ; i<=n; i++)
    //     fac[i] = fac[i-1]*i%mod;
    return (x* modInverse(y) % mod *modInverse(z) % mod) % mod;
}
void bfs(vector<li>v[],li visit[],li s,li ans[])
{
  deque<li>q;
  q.push_back(s);
  visit[s]=1;
  while(!q.empty())
  {
    li x=q.front();
    q.pop_front();
    for(auto i=v[x].begin();i!=v[x].end();i++)
    {
      if(!visit[*i])
      {
        q.push_back(*i);
        visit[*i]=1;
      }
    }
  }
}
void buildtree(int*tree,int*arr,int start,int end,int treeNode)
{
  if(start<end)
  {
    int mid=start+(end-start)/2;
    buildtree(tree,arr,start,mid,2*treeNode);
    buildtree(tree,arr,mid+1,end,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
  }
}
void update(int*tree,int*arr,int start,int end,int pos,int val,int treeNode)
{
  if(start==end)
  tree[treeNode]=val;
  else
  {
    int mid=start+(end-start)/2;
    if(pos<=mid)
    update(tree,arr,start,mid,pos,val,2*treeNode);
    else
    update(tree,arr,mid+1,end,pos,val,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
  }
}

void dfs(vector<li>v[],li visit[],li s,li c[],li ans[],map<li,li>*m,li pred[])
{
    visit[s]=1;
     (*m)[c[s]]++;
    for(auto i=v[s].begin();i!=v[s].end();i++)
      {
        if(!visit[*i])
        {pred[*i]=s;
           dfs(v,visit,*i,c,ans,m,pred);
        }
      }
      if((*m)[c[pred[s]]]==1)
    ans[s]=(*m).size()-1;
    else
    ans[s]=(*m).size();
}
vector<li>factor(li n)
{
  vector<li>v;
  if(n%2==0)
  {
    while(n%2==0)
    {n/=2;
    v.push_back(2);
    }
  }
  for(li i=3;i<=sqrt(n);i+=2)
  {
    if(n%i==0)
    {
      while(n%i==0)
      {n/=i;
      v.push_back(i);
      }
    }
  }
  if(n>1)
  v.push_back(n);
  return v;
}
int main()
{
// li t,i,j;
// cin>>t;
// while(t--)
// {
//
//   cout<<endl;
// }
string s;
cin>>s;
if(s=="ABC")
cout<<"ARC";
else
cout<<"ABC";
return 0;
}


Measured memory_bytes: 3724
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll W, H, x, y;
    cin >> W >> H >> x >> y;
    double ans = (W * H) / 2.0;
    int a = 0;
    if(x * 2 == W && y * 2 == H) a = 1;
    cout <<fixed << setprecision(12) <<  ans << " " << a << endl;

    return 0;
}


Measured memory_bytes: 3716
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MOD = 1000000007;
typedef long long ll;


int main(){
    int N;
    cin >> N;
    vector<int> p(N);
    rep(i, N){
        cin >> p[i];
        p[i]--;
    }
    vector<int> p1 = p;
    int cnt1 = 0;
    for(int i = 0; i < N - 1; i++){
        if(i == p1[i]){
            swap(p1[i], p1[i + 1]);
            cnt1++;
        }
    }
    if(N - 1 == p1[N - 1]) cnt1++;
//    vector<int> p2 = p;
//    int cnt2 = 0;
//    for(int i = N - 1; i > 0; i--){
//        if(i == p2[i]){
//            swap(p2[i], p2[i - 1]);
//            cnt2++;
//        }
//    }
    cout << cnt1 << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();
		String[] Ws = W.split(" ");
		int N = Integer.parseInt(Ws[0]);
		int K = Integer.parseInt(Ws[1]);

		W = in.readLine();
		Ws = W.split(" ");
		int[] p = new int[Ws.length];
		for(int i=0;i<Ws.length;i++){
			p[i] = Integer.parseInt(Ws[i]);
		}

		long[] sum = new long[N-K+1];
		Arrays.fill(sum, 0);
		for(int i=0;i<K;i++){
			sum[0]+=p[i];
		}
		int maxIdx=0;
		for(int i=1;i<N-K+1;i++){
			sum[i]=sum[i-1]-p[i-1]+p[i+K-1];
			if(sum[i] > sum[maxIdx]){
				maxIdx=i;
			}
		}

		double ans = 0;
		for(int i=maxIdx;i<maxIdx+K;i++){
			ans+=(p[i]*(p[i]+1)/2.0)/p[i];
//			ans+=(p[i]-1)/2.0;
		}
		System.out.println(ans);


	}


}


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

int main() {
    int H, W;
    while(true) {
        cin >> H >> W;
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H ; i++) {
            for(int j = 0; j < W; j++) {
                if((i + j) % 2 == 0)
                    cout << '#';
                else 
                    cout << '.';
            }
            cout << endl;
        }
        cout <<endl;
    }
    return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
#include<vector>
using namespace std;
  vector<vector<bool>>c(3,vector<bool>(3));
int main() {
    int n,b,c,d;
  cin>>n>>b;
  map<int,int>a;
  for(int i=0;i<b;i++){
      cin>>c>>d;
    if(a.count(c)){
      if(a.at(c)==d);
      else{
      cout<<"-1";
      return 0;
      }
    }
    a[c]=d;
  }
  if(a.count(1)){
    if(a[1]==0){
      if(n==1){
        cout<<0;
        return 0;
      }      
      cout<<-1;
      return 0;
    }
  }
  else{
    
    if(n==1){
      cout<<0;
      return 0;
    }
    else a[1]=1;
  }

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    int min = abs(753 - ((s[0] - '0')*100 + (s[1] - '0')*10 + (s[2] -'0')));
    for (int i = 1; i < s.size()-2; i++){
        if (min > abs(753 - ((s[i] - '0')*100 + (s[i+1] - '0')*10 + (s[i+2] -'0')))) min = abs(753 - ((s[i] - '0')*100 + (s[i+1] - '0')*10 + (s[i+2] -'0')));
    }
    cout << min;


}

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

string s;

int dp[10009][100][2],p,d;


int dfs(int idx,int z,bool tight){
  if(idx==s.size())return !z;
  int &res=dp[idx][z][tight];
  if(~res)return res;
  res=0;
  int x=s[idx]-'0';
  int r=(tight?9:x);
  for(int i=0;i<=r;i++){
    res+=dfs(idx+1,(z+i)%d,tight||i<r);
    res%=1000000007;
  }
  return res;
}

int main(){
  memset(dp,-1,sizeof dp);
  cin>>s>>d;
  cout<<(dfs(0,0,0)-1+1000000007)%1000000007<<endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 8960
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define vi vector <ll> v
#define vii vector<pair<ll,ll>>v
#define pb push_back
#define mod 1000000007
#define f(i,a,b) for(ll i=a;i<b;i++)
#define while_ int t;cin>>t;while(t--)
using namespace std;

const int m=3;

ll profit(int n, int arr2d[][m])
{
    ll dp[n][3];
    memset(dp,0,sizeof(dp));
    f(i,0,n) { f(j,0,3) dp[i][j]=arr2d[i][j]; }
    f(i,1,n)
    {
        f(j,0,3)
        {
            if(j==0) dp[i][j]+=max( dp[i-1][1], dp[i-1][2] );
            else if(j==1) dp[i][j]+=max( dp[i-1][0], dp[i-1][2] );
            else dp[i][j]+=max( dp[i-1][0], dp[i-1][1] );
        }
    }
    return max( dp[n-1][0], max( dp[n-1][1], dp[n-1][2] ) );
}

int main() {
    fastio
    
        int n; cin>>n;
        int arr2d[n][3];
        f(i,0,n) { f(j,0,3) cin>>arr2d[i][j]; }
        cout<<profit(n,arr2d);
    
}













Measured memory_bytes: 3840
import java.util.Scanner;

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

        sc.close();
        if (k <= a) {
            System.out.println(1);
            return;
        }
        if (a <= b) {
            System.out.println(-1);
            return;
        }
        long ans = (k - a) / (a - b);
        if ((k - a) % (a - b) != 0) {
            ans++;
        }
        System.out.println(ans * 2 + 1);
    }
}

Measured memory_bytes: 21716
import math
a,b,x=map(int,input().split())

if a*a*b/2<=x:
    c=2*x/(a**2)-b
    print(math.degrees(math.atan((b-c)/a)))
else:
    c=2*x/(a*b)
    print(math.degrees(math.atan(b/c)))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	stack<int> st;
	rep(i, n) {
		if (s[i] == '(') {
			st.push(1);
		}
		else {
			if (st.size() && st.top() == 1) st.pop();
			else st.push(0);
		}
	}
	int cnt0 = 0, cnt1 = 0;
	while (st.size()) {
		if (st.top() == 1) cnt1++;
		else cnt0++;
		st.pop();
	}
	rep(i, cnt0) cout << '(';
	cout << s;
	rep(i, cnt1) cout << ')';
	cout << endl;
	return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5,mod=998244353;
ll dp[N];
pair<ll,ll> a[N];
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    for(ll i=0;i<n;i++)cin>>a[i].first>>a[i].second;
    sort(a,a+n);
    dp[n]=1;
    stack< pair<ll,ll> > stk;
    stk.push({2e9,n});
    for(ll i=n-1;i>=0;i--){
        while(a[i].first+a[i].second > stk.top().first)stk.pop();
        dp[i] = (dp[i+1] + dp[stk.top().second] )%mod;
        stk.push({a[i].first,i});
    }
    cout<<dp[0];
}

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

int debug = 0;

int main()
{
    int n;
    string st;
    cin >> n >> st;
    vector<int>a(n);
    rep(i,n){
        if(st[i]=='R' ) a[i]=0;
        if(st[i]=='G') a[i]=1;
        if(st[i]=='B') a[i]=2;
    }

    vector<ll> cnt(3);
    rep(i,n) cnt[a[i]]++;
    ll ans=1;

    rep(i,3) ans *=cnt[i];

    rep(j,n)rep(i,j){
        int k =j+(j-i);
        if(k<n){
            if(a[i]==a[j])continue;
            if(a[i]==a[k])continue;
            if(a[k]==a[j])continue;
            ans --;
        }
    }
    cout <<ans << endl;
    
    return 0;
}

Measured memory_bytes: 3652
N=int(input())
S=[int(input()) for _ in range(N)]
S.sort()

x=sum(S)
if x%10!=0:
    print(x)
else:
    for i in range(N):
        if(x-S[i])%10!=0:
            print(x-S[i])
            break;
    else:
        print(0)


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

int main(){
    vector<int> v(3);
    for(int i = 0; i < 3; i++) cin >> v[i];
    sort(v.begin(), v.end());
    cout << (v[0] == v[1] ? v[2] : v[0]) << endl;
}

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

int main()
{
    int n;
    cin >> n;
    string s;
    int c1 = 0, c2 = 0, c3 = 0;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        if(s[0] == 'B')
        {
            if(s[s.size() - 1] == 'A')
            {
                c1++;
            }
            else
            {
                c2++;
            }
        }
        else
        {
            if(s[s.size() - 1] == 'A')
            {
                c3++;
            }
        }

        for (int j = 0; j < (int)s.size() - 1; j++)
        {
            if(s[j] == 'A' && s[j + 1] == 'B')ans++;
        }
        
    }

    if(c1 == 0)
    {
        ans += min(c2, c3);
    }
    else
    {
        if(c2 + c3 > 0)
        {
            ans += min(c2, c3) + c1;
        }
        else
        {
            ans += c1 - 1;
        }
        
    }
    

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N; i >= 0; i--)
const ll INF = 1000000000000000000;
//input
int N,K;
int A[100050];
 
//processing


//dpTable
//int dp[100050];

int main(){
    cin >> N >> K;
    rep(i,N) cin >> A[i];
    cout << (N - 3 + K) / (K - 1) << endl;
    return 0;
}

Measured memory_bytes: 4004
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=10000005;
char s[N];
int n;
int main()
{
    scanf("%s%d",s,&n);
    for(int i=0,sz=strlen(s);i<sz;i++){
        if(i%n==0)
            putchar(s[i]);
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <limits.h>
#include <bitset>
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const int MOD = 1000000007;
const int INF = LLONG_MAX/3;
const int MAX = 510000;

/*-----Library-----*/

struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
    vector<int> sizeuf; //要素数
    UnionFind(int n = 1) {
        init(n);
    }
    
    void init(int n = 1) {
        par.resize(n); rank.resize(n); sizeuf.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
            sizeuf[i]=1;
        }
    }
    
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        sizeuf[x]+=sizeuf[y];
        return true;
    }
    
    int size(int x){
        return sizeuf[root(x)];
    }
};

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

long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

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

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

/*-----Library-----*/

signed main(){
    int n;
    cin>>n;
    int m=sqrt(n);
    for(int i=m;i>=1;i--){
        if(n%i==0){
            cout<<i+n/i-2<<endl;
            break;
        }
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

ll dpx[2][16001];
ll dpy[2][16001];
vector<ll> ax,ay;

int main(){
    ll x,y;
    string s;
    cin>>s;
    cin>>x>>y;
    x+=8000,y+=8000;
    ll c=1,ct=0,sum=0;
    rep(i,0,s.length()){
        if(s[i]=='F'){
            if(ct==0)sum++;
            else {ct=0;sum=1;}
        }
        else{
            if(ct==0){
                if(c==1)ax.pb(sum);
                else ay.pb(sum);
                ct=1;
                sum=0;
            }
            c*=-1;
        }
    }
    if(sum>0){
        if(c==1)ax.pb(sum);
        else ay.pb(sum);
        sum=0;
    }

    dpx[0][8000]=1;
    rep(i,0,ax.size()){
        rep(j,0,16001)if(dpx[i%2][j]){
            dpx[(i+1)%2][j+ax[i]]=1;
            if(i>0)dpx[(i+1)%2][j-ax[i]]=1;
            dpx[i%2][j]=0;
        }
    }
    dpy[0][8000]=1;
    rep(i,0,ay.size()){
        rep(j,0,16001)if(dpy[i%2][j]){
            dpy[(i+1)%2][j+ay[i]]=1;
            dpy[(i+1)%2][j-ay[i]]=1;
            dpy[i%2][j]=0;
        }
    }
    if((ll)dpx[ax.size()%2][x]&&dpy[(ll)ay.size()%2][y])cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 512
#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

int main()
{
    long long N, K;
    cin >> N >> K;
    long long a[N];
    for (long long i = 0; i < N; i++)
        cin >> a[i];

    long long arrive[N] = {0};
    long long d = a[0];
    arrive[d - 1] = 1LL;
    long long step = 1;
    long long k_hold = K - 1;
    for (long long i = 2; i <= N + 1; i++)
    {
        if (k_hold == 0)
            break;

        step = i;
        d = a[d - 1];
        k_hold--;
        if (arrive[d - 1] != 0)
            break;
        arrive[d - 1] = i;
    }
    
    if (k_hold == 0) {
        cout << d << '\n';
        return 0;
    }

    long long loop = step - arrive[d - 1];
    long long r = (K - step) % loop;
    //cout << r << '\n';
    for (; r > 0; r--)
        d = a[d - 1];
    cout << d << '\n';
    return 0;
}

Measured memory_bytes: 6696
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0049
Blood Groups
"""
import sys
from collections import Counter


def main(args):
    members = []
    for line in sys.stdin:
        _, blood_type = line.strip().split(',')  # ??\??????????????????????????????????¶????(????????????)???????????????
        members.append(blood_type)

    # ?????????????¨?
    blood_type_counter = Counter(members)  # ??????????????????????????§????????????????¨???????
    print(blood_type_counter['A'])  # ?????¨?????????????´????????????????KeyError??§?????????0??????????????????????????§?????????????????????????????°OK
    print(blood_type_counter['B'])
    print(blood_type_counter['AB'])
    print(blood_type_counter['O'])


if __name__ == '__main__':
    main(sys.argv[1:])

Measured memory_bytes: 7820
import java.util.Scanner;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    
    if(a<b){
      System.out.println("a < b");
    }else if(a>b){
      System.out.println("a > b");
    }else{
      System.out.println("a == b");
    }
  }
}



Measured memory_bytes: 25988
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makel(N) ll N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007
#define re return 0
#define distance(x1,y1,x2,y2) sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

template<typename T>
void maxi(T &a, T b) {
	a = max(a, b);
}

template<typename T>
void mini(T &a, T b) {
	a = min(a, b);
}

int main() {
	string bla, whi;
	rep(100)bla.push_back('#');
	rep(100)whi.push_back('.');
	makei(A);
	makei(B);
	--A;
	--B;
	say("100 100");
	For(i, 50) {
		if (i % 2 == 0) {
			say(bla);
			continue;
		}
		For(j, 100) {
			if (j % 2 == 0 && A > 0) {
				cout << ".";
				--A;
			}
			else cout << "#";
		}
		cout << endl;
	}
	For(i, 50) {
		if (i % 2 == 0) {
			say(whi);
			continue;
		}
		For(j, 100) {
			if (j % 2 == 0 && B > 0) {
				cout << "#";
				--B;
			}
			else cout << ".";
		}
		cout << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    int ans;
    cin >> N;
    vector<int> vec(N);
    vector<int> c(N);
    for (int i = 0; i < N; i++){
        cin >> vec[i];
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; ; j++){
            if (vec[i] %2 == 0){
                vec[i] /= 2;
                c[i] += 1;
            }
            else {
                break;
            }
        }
    }
    ans = *min_element(c.begin(), c.end());
    cout << ans << endl;
}

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

int main(){
  int X,Y;
  cin >> X >> Y;
  if(Y%2==1){
    cout << "No";
    return 0;
  }
  
  int upper = Y / 2;
  int lower;
  int cnt=0;
  while(Y%4!=0){
    Y -= 2;
    cnt++;
  } 
  lower = cnt + Y / 4;
  
  if(lower<=X && X<=upper) cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 3592
import sys
n,m,x,y = map(int,input().split())

xl =  list(map(int,input().split()))
yl =  list(map(int,input().split()))	


if max(xl) < min(yl):
    for i in range(max(xl)+1, min(yl)+1):
        if x < i <= y:
            print("No War")
            sys.exit()
print("War")

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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define debug0(x) printf("! %d\n", x);
#define debug1(x, a, b) for(int (ii)=(a);(ii)<(b);(ii++)) printf("%d: %d\n", ii, x[ii]);
#define nono(x, ite) for(__typeof((x).begin()) (ite)=(x).begin();(ite)!=(x).end();(ite++))

typedef long long ll;

const int N = 2e5 + 10;

int n, lv;
ll a[N], ans[N], gar[N];
bool vis[N];
vector<int> pos;
ll s[2][N];

void add(int id, int u, ll v) {
  while (u <= lv) {
    s[id][u] += v;
    u += u & -u;
  }
}

ll get(int id, ll u) {
  ll res = 0;
  while (u) {
    res += s[id][u];
    u -= u & -u;
  }
  return res;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    gar[lv++] = a[i];
  }
  gar[lv++] = 0;
  ll mx = 0;
  pos.pb(0);
  for (int i = 1; i <= n; i++) {
    if (mx < a[i]) mx = a[i], pos.pb(i);
  }
  for (int i = 0; i < pos.size(); i++) {
    vis[pos[i]] = 1;
  }
  sort(gar, gar + lv);
  lv = unique(gar, gar + lv) - gar;
  for (int i = 0; i <= n; i++) {
    a[i] = lower_bound(gar, gar + lv, a[i]) - gar + 1;
  }
  ll tsum = 0;
  int len = pos.size() - 1;
  for (int i = n; i >= 1; i--) {
    add(0, a[i], 1);
    add(1, a[i], gar[a[i] - 1]);
    if (vis[i]) {
      ans[i] = (get(1, lv) - get(1, a[pos[len - 1]])) - tsum - (get(0, lv) - get(0, a[pos[len - 1]])) * gar[a[pos[len - 1]] - 1];
      tsum += ans[i];
      len--;
    }
  }
  for (int i = 1; i <= n; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}



Measured memory_bytes: 7800
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using ll = long long;
using namespace std;
ll x, y, z, l, m, n, r, q, k;
//0 1 2 3 4 5 6 n = 7;
void solve() {
    cin>>n>>k;
    ll a[100000];
    for(int i=0;i<n;i++)
    cin>>a[i];
    ll md = INT_MAX;
    sort(a, a+n);
    for(int i=0;i<=n-k;i++){
        md = min(md, a[i+k-1]-a[i]);
    }
    cout<<md<<'\n';
}

int main() 
{
    std::ios::sync_with_stdio(false); \
        std::cin.tie(NULL);
    int test;
    test = 1;
    while (test--) {
        solve();
    }
    return 0;
}

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;


int main() {
    string s;
    cin >> s;
    li cnt = 0;
    rep(i, 3) {
        if (s[i] == 'R')cnt++;
    }
    if (cnt != 2) {
        cout << cnt << endl;
    } else {
        cout << (s[1] == 'R' ? 2 : 1) << endl;
    }

    return 0;
}

Measured memory_bytes: 3620
/*
 *
 *   Author     : Amit Kumar
 *   Date    	: June 29
 * 
 */

#include <bits/stdc++.h>

#define FAST_INPUT_OUTPUT
//#define MORE_THAN_ONE_TESTCASE // COMMENT IT

#define vi vector<int>
#define vl vector<long long>
#define mii map<int , int>
#define mll map<long long , long long>
#define msi map<string , i>
#define msl map<string , long long>
#define umii unordered_map<int,int>
#define umll unordered_map<long long ,long long>
#define umsi unordered_map<string , int>
#define umsl map<string , long long> 
#define si set<int>
#define sl set<long long>
#define pii pair<int , int >
#define psi pair<string,int>
#define psl pair<string , long > 
#define pll pair<long long , long long>
#define vpii vector<pii>
#define vpll vector<pll>
#define vpsi vector<psi>
#define vpsl vector<psl>
#define pqi priority_queue<int>
#define pql priority_queue<long long>
#define ub upper_bound
#define lb lower_bound
#define bint long long int
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define iv(v) for(auto &i:v){cin>>i;}
#define ov(v) for(auto i:v){cout<<i<<" ";}cout<<endl;
#define ovn(v) for(auto i:v){cout<<i<<endl;}
#define euv(v) for(auto i:v){cerr<<i<<" ";}cerr<<endl;
#define eovn(v) for(auto i:v){cerr<<i<<endl;}
#define os(s) for(auto itr:s){cout<<itr<<" ";}cout<<endl;
#define osn(s) for(auto itr:s){cout<<itr<<endl;}
#define eos(s) for(auto itr:s){cerr<<itr<<" ";}cerr<<endl;
#define eosn(s) for(auto itr:s){cerr<<itr<<endl;}
#define rep(x) for(auto i=0 ; i<(x); ++i)
#define _rep(a,b) for(auto i=(a); i<(b); ++i)
#define ef else if
#define wh while
#define el else
#define ivv(x) int x; cin>>x
#define lv(x) bint x; cin>>x
#define sv(x) string x; cin>>x
#define cv(x) char x; cin>>x
#define fv(x) float x; cin>>x
#define dv(x) double x; cin>>x
#define endl '\n'
using namespace std;




auto SOLUTION_FUNCTION( void ) ->void {

    // your solution goes here 

    ivv(n);
    ivv(k);

    vi v(n);

    iv(v);

    sort(all(v));

    int ans = INT_MAX;

    for(int i=0 , j=i+k-1; j<v.size(); ++j,++i){
        ans = min(ans , abs(v.at(i)-v.at(j)));
    }

    cout<<ans<<endl;


    return ;
}




int main(void){
#ifdef FAST_INPUT_OUTPUT
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout<<setprecision(10);
    cout<<fixed;
    cout<<boolalpha;
#endif
#ifdef MY_LOCAL_PROJECT
    freopen("input","r",stdin);
    freopen("output","w",stdout);
#endif
    int testcase = 1;


#ifdef MORE_THAN_ONE_TESTCASE
    cin>>testcase;
#endif
    
    while(testcase--){
        SOLUTION_FUNCTION();
    }

#ifdef MY_LOCAL_PROJECT
    cout<<"Time : "<<1.0*(double)clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;
 
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;
 
#define _  %  MOD
#define __ %= MOD
 
#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))
 
#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
#define fbo find_by_order
#define ook order_of_key
 
ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=(res*x)%INF;y=y>>1;x=(x*x)%INF;}return res%INF;} // modular exponent
 ll n,k;
 const int N=1e5+5;
 ll fact[N];
 ll invfact[N];
 ll inv(ll x)
{
	return power(x,INF-2);
}
void work()
{
	fact[0]=1;fact[1]=1;
	invfact[0]=1;invfact[1]=1;
	for(ll i=2;i<N;i++)
	{
		fact[i]=i*fact[i-1];
		fact[i]%=INF;
		invfact[i]=inv(fact[i]);
	}
}
ll C(ll n,ll r)
{
	if(r>n) return 0ll;
	ll ans=1ll;
	ans*=fact[n];
	ans%=INF;
	ans*=invfact[r];
	ans%=INF;
	ans*=invfact[n-r];
	ans%=INF;
	return ans;
}
int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
	cin>>n>>k;
   	vector<ll> v(n+1);
	repA(i,1,n) cin>>v[i];
	sort(v.begin()+1,v.begin()+n+1);
	if(n==1)
	{
		cout<<0<<'\n';
	}
	else
	{
		work();
		ll ans1=0;
		repA(i,k,n)
		{
			ll val=v[i]*C(i-1,k-1);
			val%=INF;
			ans1+=val;
			ans1%=INF;
		}
		ll ans2=0;
		for(ll i=1;n-(i+1)+1>=(k-1);i++)
		{
			ll val=v[i]*C(n-i,k-1);
			val%=INF;
			ans2+=val;
			ans2%=INF;
		}
		 ans1-=ans2;
		ans1+=INF;
		ans1%=INF;
		cout<<ans1<<'\n';
	}
	return 0;
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!



Measured memory_bytes: 5576
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a[10000],b[10000];
    char c[10000];
    for(long i=0; i<10000; i++) {
        cin >> a[i] >> c[i] >> b[i];
        if(c[i]=='?') {
            break;
        }
        else if(c[i]=='+') {
            cout << a[i]+b[i] << endl;
        }
        else if(c[i]=='-') {
            cout << a[i]-b[i] << endl;
        }
        else if(c[i]=='*') {
            cout << a[i]*b[i] << endl;
        }
        else if(c[i]=='/') {
          if(b[i]==0) {
            break;
          }
            cout << a[i]/b[i] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3132
while true
    n = gets.to_i
    break if n == 0
    h = Hash.new{|h, k| h[k] = [0, nil, nil]}
    n.times{|i|
        e, p, q = gets.chomp.split.map(&:to_i)
        h[e][0] += p * q
        h[e][1] = e if h[e][1].nil?
        h[e][2] = i if h[e][2].nil?
    }
    arr = []
    h.values.sort_by{|t, n, i| i}.each{|total, number, index| arr << number if total >= 1_000_000}
    puts (arr.empty?) ? "NA" : arr
end


Measured memory_bytes: 6928
n = int(input())
lst_a = list(map(int,input().split()))
num_minus = sum(i<0 for i in lst_a)
lst_abs = [abs(i) for i in lst_a]
if num_minus%2 == 0:print(sum(lst_abs))
else:print(sum(lst_abs)-2*min(lst_abs))

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


int main(){

    ll n ,a,b;
    cin >> n >> a >> b ;

    if (a>b)
        swap(a,b) ;

    ll ans = abs(a-b) ;

    if (ans%2){
        ll d = b- (a-1) , e = (a+(n-b)) ;
        ans = min((b-d)+d/2,(e-a)+(n-e+1)/2) ;
       // cout << d <<  ' ' << e ;
        cout << ans << endl ;
    }
    else
        cout << ans/2 << endl ;




}


Measured memory_bytes: 256
N, P = map(int, input().split())

fac = dict()
if (P & -P) != 1:
    t = (P & -P).bit_length()
    fac[2] = t-1
    P //= (P & -P)
for f in range(3, 1001003):
    if P % f == 0:
        fac[f] = 0
        while P % f == 0:
            fac[f] += 1
            P //= f
    if P == 1:
        break
else:
    fac[P] = 1

ans = 1
for f, c in fac.items():
    ans *= pow(f, c//N)

print(ans)

Measured memory_bytes: 62976
# -*- coding: utf-8 -*-

import math

d,g = map(int,input().split())
p = [0] * d
c = [0] * d
for i in range(d):
    p[i],c[i] = map(int,input().split())

ans = 1000000000
#bit全探索
n = d
arr = [0] * n
for i in range(2 ** n):
    for j in range(n):
        if((1&i>>j) == 1):
            arr[j] = 1
        else:
            arr[j] = 0
    #ここに処理
    score = 0
    question = 0
    for j in range(len(arr)):
        if arr[j] == 1:
            score += (j+1)*100*p[j] + c[j]
            question += p[j]
    if score >= g:
        ans = min(ans,question)
    else:
        for j in range(len(arr)-1,-1,-1):
            if arr[j] == 0:
                if g - score <= (j+1)*100*(p[j]-1):
                    temp = math.ceil((g - score) / ((j+1)*100))
                    question += temp
                    ans = min(ans,question)
                break


print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    int a[100] = {};
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++)
        {
            int tmp;
            cin >> tmp;
            a[tmp]++;
        }
    }
    int ans = 0;
    for (int i = 0; i <= m; i++)
    {
        if (a[i] == n)
            ans++;
    }
    cout << ans << endl;
}

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

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 1e5 + 10;

int n;
int A[N];

int main(){

	scanf("%d", &n);
	
	long long l = 2, r = 2;
	For(i, 1, n) scanf("%d", &A[i]);
	Forr(i, n, 1){
		r = r / A[i] * A[i] + A[i] - 1;
		l = (l + A[i] - 1) / A[i] * A[i];
		if(l > r){
			puts("-1");
			return 0;
		}
	}
	printf("%lld %lld\n", l, r);

	return 0;
}

Measured memory_bytes: 640
if !ENV['RUBY_THREAD_VM_STACK_SIZE']
    require 'rubygems';RUBY=Gem.ruby
    exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},RUBY,$0) #100MB
end

V = 100_005 # 頂点の最大数

class Graph
  attr_accessor :to, :seen, :cnt

  def initialize
    @to = Array.new(V*2){ [] }
    @seen = Array.new(V*2, false)
    @cnt = Array.new(2,0)
  end

  def dfs(v)
    return if seen[v]
    seen[v] = true
    cnt[v/V] += 1
    to[v].each do |nv|
      dfs(nv)
    end
  end
end

n = gets.to_i
g = Graph.new
n.times do
  x,y = gets.split.map(&:to_i)
  y += V
  g.instance_eval do
    to[x] << y
    to[y] << x
  end
end

ans = 0
(V*2).times do |i|
  g.instance_eval do
    self.cnt = [0, 0]
    dfs(i)
    ans += cnt[0] * cnt[1]
  end
end
ans -= n
puts ans


Measured memory_bytes: 147396
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

class EncState {
	uint_least32_t data;

	static int to_bit(char c) {
		return c - 'b';
	}

	EncState(uint_least32_t data) : data(data) {}

public:
	EncState() : data(0) {}

	EncState set_used(char c) const {
		return data | (1u << to_bit(c));
	}

	bool is_used(char c) const {
		return (data >> to_bit(c)) & 1u;
	}
};

void search(std::string& input, int index, EncState state, uint_least32_t& result) {
	if (index == input.size()) {
		result++;
		return;
	}

	char c = input[index];

	if (c == 'a' || state.is_used(c)) {
		search(input, index + 1, state, result);
	}

	if (c != 'z') {
		if (!state.is_used(c + 1)) {
			search(input, index + 1, state.set_used(c + 1), result);
		}
	}
}

struct SearchContext {
	std::string& input;
	std::vector<std::string>& output;
	size_t output_count;
};

void search_ascending(SearchContext& ctx, int index, std::string candidate, EncState state) {
	if (ctx.output.size() >= ctx.output_count) return;

	if (index >= ctx.input.size()) {
		ctx.output.push_back(std::move(candidate));
		return;
	}

	char c = ctx.input[index];

	if (c == 'a' || state.is_used(c)) {
		std::string s = candidate;
		s.push_back(c);
		search_ascending(ctx, index + 1, std::move(s), state);
	}

	if (c != 'z') {
		if (!state.is_used(c + 1)) {
			candidate.push_back(c + 1);
			search_ascending(ctx, index + 1, std::move(candidate), state.set_used(c + 1));
		}
	}
}

void search_descending(SearchContext& ctx, int index, std::string candidate, EncState state) {
	if (ctx.output.size() >= ctx.output_count) return;

	if (index >= ctx.input.size()) {
		ctx.output.push_back(std::move(candidate));
		return;
	}

	char c = ctx.input[index];

	if (c != 'z') {
		if (!state.is_used(c + 1)) {
			std::string s = candidate;
			s.push_back(c + 1);
			search_descending(ctx, index + 1, std::move(s), state.set_used(c + 1));
		}
	}

	if (c == 'a' || state.is_used(c)) {
		candidate.push_back(c);
		search_descending(ctx, index + 1, std::move(candidate), state);
	}
}

int main()
{
	std::string line;
	line.reserve(20);
	std::vector<std::string> candidates;
	candidates.reserve(10);

	while (true) {
		std::getline(std::cin, line);
		if (line == "#") return 0;

		uint_least32_t count = 0;
		search(line, 0, {}, count);

		std::cout << count << std::endl;

		candidates.clear();
		SearchContext ctx = { line, candidates };

		if (count <= 10) {
			ctx.output_count = 10;
			search_ascending(ctx, 0, {}, {});
			for (std::string& s : candidates) {
				std::cout << s << std::endl;
			}
		}
		else {
			ctx.output_count = 5;
			search_ascending(ctx, 0, {}, {});
			for (std::string& s : candidates) {
				std::cout << s << std::endl;
			}

			candidates.clear();
			search_descending(ctx, 0, {}, {});
			for (auto i = candidates.rbegin(); i != candidates.rend(); i++) {
				std::cout << *i << std::endl;
			}
		}
	}
}

Measured memory_bytes: 3112