akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main(){
  while(1){
    int n, i, res = 0;
    int coin[] = {500, 100, 50, 10, 5, 1};
    scanf("%d", &n);
    if(n == 0){
      return 0;
    }
    n = 1000 - n;
    for(i = 0;i < 6;i++){
      res += n / coin[i];
      n %= coin[i];
    }
    printf("%d\n",res);
  }
}

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

int gcd(int X,int Y){
    int x=min(X,Y);
    int y=max(X,Y);
    int r=y%x;
    while(r!=0){
        y=x;
        x=r;
        r=y%x;
    }
    return x;
}


int main() {
    ll A,B,C,D;
    cin>>A>>B>>C>>D;
    ll LCM =C*D/gcd(C,D);
    ll b=B/C;
    ll b1=B/D;
    ll b2=B/LCM;
    ll a =(A-1)/C;
    ll a1=(A-1)/D;
    ll a2=(A-1)/LCM;
    ll ans = b+b1-b2-a-a1+a2;
    ll ans1=B-A+1-ans;
    cout<<ans1<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int seq[32]={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};
  int K;
  cin >> K;
  cout << seq[K-1] << endl;
}

Measured memory_bytes: 3608
#include <iostream>

using namespace std;

string calc(int x, int y)
{
    for (int i = 0; i <= x; i++)
    {
        int j = x - i;
        if (i * 2 + j * 4 == y)
        {
            return "Yes";
        }
    }

    return "No";
}

int main()
{
    int x, y;
    cin >> x >> y;

    string answer = calc(x, y);

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 3600
h,w = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(10)]

from collections import defaultdict

V = defaultdict(list)
 
for x in range(10):
    al = ab[x]
    for y in range(10):
        V[x].append([y,al[y]])

def dfs(source):
    dist = [99]*10
    dist[source] = 0
    q = [source]
    while q:
        a = q.pop()
        for b in V[a]:
            if dist[b[0]]!=99:
                if dist[b[0]] > dist[a]+b[1]:
                    q.append(b[0])
                dist[b[0]] = min(dist[b[0]],dist[a]+b[1])
                continue
            dist[b[0]] = dist[a] + b[1]
            q.append(b[0])
    return dist

hw = [list(map(int, input().split())) for _ in range(h)]

import itertools
ss = list(itertools.chain.from_iterable(hw))

import collections
c = collections.Counter(ss)

res = 0
for i in range(10):
    res += c[i]*dfs(i)[1]

print(res)

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

int main() {
    int k, x;
    cin >> k >> x;
    for(int i=x-k+1; i<=x+k-1; i++) {
        if(i==x+k-1) cout << i << endl;
        else cout << i << " " ;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 

	public static void main(String[] args) { //GIMME AC
		Scanner input = new Scanner(System.in); 
		String S = input.next();
		int N = S.length();
		String ans = "";
		boolean[] v = new boolean[200];
		if (N<26) {
			ans+=S;
			for (int i = 0; i < N; i++) {
				v[(int)(S.charAt(i))]=true;
			}
			for (int i = (int)('a'); i <= (int)('z'); i++) {
				if (!v[i]) {
					ans+=Character.toString((char)(i));
					break;
				} 
			}
		}else {
			int L = -1; //L=0 is still valid dawg
			for (int R = N-2; R >= 0; R--) {
				if ((S.charAt(R))>(S.charAt(R+1))) continue;
				else {
					L=R;
					break;
				}
			}
			if (L==-1) ans="-1";
			else {
				ans+=S.substring(0,L);
				char cmp = S.charAt(L);
				for (int i = 0; i < L; i++) {
					v[(int)(ans.charAt(i))]=true;
				}
				for (int i = (int)('a'); i <= (int)('z'); i++) {
					if (!v[i]&&i>(int)(cmp)) {
						ans+=Character.toString((char)(i));
						break;
					}
				}
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 26820
#include <iostream>
#include <string>
using namespace std;
string arr[20];

int main()
{
    int a, b, c;
    cin>>a>>b>>c;
    if (a!=b&&a!=c){
        cout<<a;
    }
    else if(b!=a&&b!=c){
        cout<<b;
    }
    else{
        cout<<c;
    }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define uint unsigned long long
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int n, ans, ans1;

int main()
{
    n = read();
    rep(i, 1, n)
    {
    	int x = read();
    	if(x % 4 == 0) ans ++;
    	else if(x % 2 == 0) ans1 ++;
    }
    if(ans >= n / 2) puts("Yes");
    else
    {
        n -= ans * 2;
        if(ans1 >= n) puts("Yes");
        else puts("No");
    }
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ul unsigned long long int
#define vi vector<int>
#define vl vector<int64_t>
#define all(x) x.begin(),x.end()
#define pb push_back
#define fo(x,a,b) for(int x=a; x<b; x++)
int sgn(int x) { return x>0 ? 1 : ( x<0 ? -1 : 0); }
typedef pair<int,int> pairs;
double pi = 3.14159265358979323846;

void solve()
{
    int n;
    cin>>n;
    vi a(n);
    fo(i,0,n) cin>>a[i];
    int xr = a[0];
    fo(i,1,n) xr = xr^a[i];
    fo(i,0,n)
    {
        cout<<(xr^a[i])<<" ";
    }
    cout<<"\n";
    return;
}
int main()
{
#ifdef _DEBUG
    freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    //cin>>t;
    //while(t--)
    {
        solve();
    }
    return 0;
}

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

int main(){
    long long n;
    cin >> n;
    vector<long long>f(n+1,0);
    for(int i=1;i<n+1;i++){
        int x=i;
        while(x<=n){
            f[x]++;
            x+=i;
        }
    }
    long long ans=0;
    for(long long i=1;i<=n;i++){
        ans+=i*f[i];
    }
    cout << ans << endl;
}

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

int cnt, N, m;
const int step = 3;
const int MAX = 1000000;
vector<int> G;
int A[MAX];

void InsertionSort(int A[], int n, int g)
{
	int tmp, j;
	for (int i = g; i < n; ++i)
	{
		tmp = A[i];
		j = i - g;
		while (j >= 0 && A[j] > tmp)
		{
			A[j + g] = A[j];
			j -= g;
			cnt++;
		}
		A[j + g] = tmp;
	}
	
}
void ShellSort(int A[], int n)
{
	int g = 1;
	do {
		G.push_back(g);
		g = step * g + 1;
	} while (g < n);  //g不能等于n
	//for (int h = 1; ;) {
	//	if (h > n) break;
	//	G.push_back(h);
	//	h = 3 * h + 1;
	//}
	for (int i = G.size() - 1; i >= 0; --i)
	{
		//cout << i << endl;
		InsertionSort(A, n, G[i]);
	}

}
int main()
{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		scanf("%d", &A[i]);
	}
	ShellSort(A, N);
	cout << G.size() << endl;
	for (int i = G.size() - 1; i >= 0; --i)
	{
		cout << G[i];
		if (i) cout << ' ';
	}
	cout << endl;
	cout << cnt << endl;
	for (int i = 0; i < N; ++i)
	{
		cout << A[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 7064
#include<stdio.h>
int main(){
  int K,X;
  int i;
  scanf("%d %d",&K,&X);
  for(i=X+1-K;i<X;i++){
    printf("%d ",i);
  }
  printf("%d ",X);
  for(i=X+1;i<X+K;i++){
    printf("%d ",i);
  }
  return (0);
}


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

namespace ConsoleApp113
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = long.Parse(Console.ReadLine());
            var list = Console.ReadLine().Split(" "). Select(x => long.Parse(x)).ToList();
            var max = list.Max();
            var sum = list.Sum() - max;
            Console.WriteLine(max < sum ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 28392
#include <stdio.h>
#include <math.h>
int main(void)
{
	double x1, x2, y1, y2, r;
	scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
	printf("%f\n", sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1)));

	return 0;
}


Measured memory_bytes: 2112
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    long a = scan.nextLong();
    long b = scan.nextLong();
    long c = scan.nextLong();
    if (a<=c){
      long d = a;
      a = 0;
      c -= d;
    }
    else{
      a -= c;
      c = 0;
    }
    b -= c;
    if (b<0){
      b=0;
    }

    System.out.println(a+" "+b);
  }
}


Measured memory_bytes: 38828
#include<stdio.h>

int max(int a, int b){
  if(a > b) return a;
  else return b;
}

int main(){

  int h1,m1,h2,m2,k;
  scanf("%d %d %d %d %d",&h1,&m1,&h2,&m2,&k);

  int ans = (h2*60 + m2) - (h1*60 + m1) - k;
  ans = max(ans,0);

  printf("%d",ans);

  return 0;
}


Measured memory_bytes: 1732
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define rap(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
int read()
{
	int num=0,f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())num=(num<<1)+(num<<3)+c-48;
	return num*f;
}
const int mn=100010;
struct tree
{
	int l,r;
}tr[mn];
int n,m,t=0,len,ans,a[mn];
string s;
char c[mn];
void fre()
{
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
}
void init()
{
	cin>>s;
	len=s.size();
}
void bf_work()
{
	rep(i,1,len)
	{
		c[i]=s[i-1];
	}
	n=len-1;
	if(c[len]=='1')
	{
		printf("-1");
		exit(0);
	}
	if(c[1]=='0')
	{
		printf("-1");
		exit(0);
	}
	rep(i,1,(len+1)/2)
	{
		if(c[i]!=c[len-i])
		{
			printf("-1");
			exit(0);
		}
	}
}
void work()
{
	int tmp=1;
	rep(i,1,len-1)
	{
		tr[i].l=tmp;
		tr[i].r=i+1;
		if(c[i]=='1')
		{
			tmp=i+1;
		}
	}
	rep(i,1,n)
	{
		printf("%d %d\n",tr[i].l,tr[i].r);
	}
}
void re_zero()
{
	ans=0;
}
int main()
{
	//fre();
		init();
		bf_work();
		work();
		re_zero();
	return 0;
}

Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}
	
	void run() {
		int n = sc.nextInt();
		
		if(n % 2 ==0 ) {
			System.out.println((n)*(n-2)/2);
			for(int i = 1 ; i <= n; i++) {
				for(int j = i+1; j <=n ; j++) {
					if(i+j == n+1) {
						continue;
					}
					System.out.println(i+" "+j);
				}
			}
			
		}else {
			System.out.println((n-1)*(n-3)/2 + n-1);

			for(int i = 1 ; i <= n-1; i++) {
				for(int j = i+1; j <=n-1 ; j++) {
					if(i+j == n) {
						continue;
					}
					System.out.println(i+" "+j);
				}
			}
			for(int i = 1 ; i < n ; i++) {
				System.out.println(i + " "+n);
			}
		}		
	}
}

Measured memory_bytes: 27988
import std.algorithm;
import std.bigint;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(long N, long[] V, long[] C) {
    long[] X = new long[](cast(size_t) N);
    X[] = V[] - C[];
    return X.sort().filter!"a > 0".sum;
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long[] V = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        V[i] = input.front.to!long;
        input.popFront;
    }

    long[] C = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        C[i] = input.front.to!long;
        input.popFront;
    }

    static if (is(ReturnType!solve == void))
        solve(N, V, C);
    else
        solve(N, V, C).writeln;
}


Measured memory_bytes: 256
a,b,c,x,y = map(int,input().split())

ans = float('inf')
for i in range(0,2*10**5+1):
  cost = c * i
  cost += a * max(0, x - i//2)
  cost += b * max(0, y - i//2)
  ans = min(ans,cost)  
print(ans)  

Measured memory_bytes: 3060
N,M,C=map(int,input().split())
B=list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(N)]
ans=0
for i in range(N):
    sum_tmp=0
    for j in range(M):
        sum_tmp += A[i][j]*B[j]
    sum_tmp += C
    if sum_tmp>0:
        ans += 1
print(ans)

Measured memory_bytes: 3064
n, r = input().split(' ')
stack = [[] for _ in range(int(n))]
for _ in range(int(r)):
    row = list(map(int, input().split(' ')))
    c = row[0]
    i = row[1]

    if c == 0:
        stack[i].append(row[2])
    if stack[i]:
        if c == 1:
            print(stack[i][-1])
        if c == 2:
            stack[i].pop()





Measured memory_bytes: 13704
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String S = sc.next();

		if(S.length() > 2) {
			String h = S.substring(0, 1);
			String t = S.substring(S.length()-1,S.length());
			int length = S.length()-2;
			System.out.println(h + length + t);
		} else {
			System.out.println(S);
		}
	}
}


Measured memory_bytes: 23764
#include <stdio.h>
#include <utility>
#define MAX 100000
using namespace std;
#define SENTINEL 2000000000

struct Card
{
  char suit;
  int value;
};

int partition(Card A[], int p, int r)
{
  Card x = A[r];
  int i = p - 1;
  for (int j = p; j <= r - 1; j++)
  {
    if (A[j].value <= x.value)
    {
      i = i + 1;
      swap(A[i], A[j]);
    }
  }
  swap(A[i + 1], A[r]);
  return i + 1;
}

void quicksort(Card A[], int p, int r)
{
  if (p < r)
  {
    int q = partition(A, p, r);
    quicksort(A, p, q - 1);
    quicksort(A, q + 1, r);
  }
}

void merge(Card A[], int left, int mid, int right)
{
  int n1 = mid - left;
  int n2 = right - mid;
  Card L[n1 + 1], R[n2 + 1];
  for (int i = 0; i < n1; i++)
  {
    L[i] = A[left + i];
  }
  for (int i = 0; i < n2; i++)
  {
    R[i] = A[mid + i];
  }
  L[n1].value = SENTINEL;
  R[n2].value = SENTINEL;
  int i = 0, j = 0;
  for (int k = left; k < right; k++)
  {
    if (L[i].value <= R[j].value)
    {
      A[k] = L[i];
      i = i + 1;
    }
    else
    {
      A[k] = R[j];
      j = j + 1;
    }
  }
}

void mergeSort(Card A[], int left, int right)
{
  if (left + 1 < right)
  {
    int mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main()
{
  int n;
  Card A[MAX], B[MAX];
  scanf("%d\n", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%c%d\n", &A[i].suit, &A[i].value);
    B[i].suit = A[i].suit;
    B[i].value = A[i].value;
  }

  quicksort(A, 0, n - 1);
  mergeSort(B, 0, n);
  bool isStable = true;
  for (int i = 0; i < n; i++)
  {
    if (A[i].suit != B[i].suit)
    {
      isStable = false;
    }
  }
  if (isStable)
  {
    printf("Stable\n");
  }
  else
  {
    printf("Not stable\n");
  }

  for (int i = 0; i < n; i++)
  {
    printf("%c %d\n", A[i].suit, A[i].value);
  }
}


Measured memory_bytes: 4936
#include<cstdio>
int min(int x,int y) {return x<y?x:y;}
int main()
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%d\n",min(a,b)+min(c,d));
	return 0;
}

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

import sys

def solve(n, ls_lr):
    print(sum([r - l + 1 for (l,r) in ls_lr]))


def readQuestion():
    ws = sys.stdin.readline().strip().split()
    n = int(ws[0])
    ls_lr = [list(map(int, sys.stdin.readline().strip().split())) for j in range(n)]
    return (n, ls_lr,)

def main():
    solve(*readQuestion())

main()


Measured memory_bytes: 3188
#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    int a,b,c;
    cin>>a>>b>>c;
    
    int ansmax = max(a,b);
    ansmax = max(ansmax,c);
    
    int ansmin=min(a,b);
    ansmin=min(ansmin,c);
    
    cout<<ansmax-ansmin<<endl;
    
    
    
return 0;
}


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

//問題文より、入力されるデータの最大個数
#define MAXCOUNT 100

//ユークリッド距離を求める
double euclidean_distance(double x[MAXCOUNT], double y[MAXCOUNT], int n, double p);
//ヘェビシェフ距離を求める
double chebyshev_distance(double x[MAXCOUNT], double y[MAXCOUNT], int n);

int main(void)
{
	int i, j, n;
	double x[MAXCOUNT], y[MAXCOUNT];

	//データの個数を入力
	scanf("%d", &n);

	//ベクトルxを入力
	for(i = 0; i < n; i++){
		scanf("%lf", &x[i]);
	}
	//ベクトルyを入力
	for(i = 0; i < n; i++){
		scanf("%lf", &y[i]);
	}

	//p=1、p=2、p=3の結果を出力
	for(i = 1; i <= 3; i++){
		printf("%lf\n", euclidean_distance(x, y, n, (double)i));
	}
	//p=infinityの結果を出力
	printf("%lf\n", chebyshev_distance(x, y, n));

	return 0;
}

//距離 = (Σ[i = 0 → n] abs(x[i] - y[i])^p)^1/p
double euclidean_distance(double x[MAXCOUNT], double y[MAXCOUNT], int n, double p)
{
	int i;
	double ans;

	ans = 0;

	//データの数だけ繰り返す
	for(i = 0; i < n; i++){
		//fabsでdouble型の絶対値を求める
		ans += pow(fabs(x[i] - y[i]), p);
	}

	ans = pow(ans, (1 / p));

	return ans;
}

//距離 = max(Σ[i = 0 → n] abs(x[i] - y[i]))
double chebyshev_distance(double x[MAXCOUNT], double y[MAXCOUNT], int n)
{
	int i;
	double ans;

	ans = 0;

	for(i = 0; i < n; i++){
		//ansに最大値を格納する
		if(ans < fabs(x[i] - y[i])){
			ans = fabs(x[i] - y[i]);
		}
	}

	return ans;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	vector<pair<int,int>> students,chk_pts;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		students.push_back({x,y});
	}
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		chk_pts.push_back({x,y});
	}
	for(int i=0;i<n;i++)
	{
		int dis=1e9;
		int cur=-1;
		for(int j=0;j<m;j++)
		{
			int d=abs(students[i].first-chk_pts[j].first)+abs(students[i].second-chk_pts[j].second);
			if(dis>d)
			{
				dis=d;
				cur=j+1;
			}
		}
		cout<<cur<<endl;
	}
	return 0;

}


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

bool one, nine, seven, four;

int main() {
    rep(i,4){
        int n;
        cin >> n;
        if (n == 1) one = true;
        if (n == 9) nine = true;
        if (n == 7) seven = true;
        if (n == 4) four = true;
    }
    puts((one && nine && seven && four ? "YES" : "NO"));
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
int main(){
  int N;
  cin >> N;
  vector<ll> d(N);
  for(int i = 0;i < N;i++)cin >> d[i];
  ll ans = 0;
  for(int i = 0;i < N - 1;i++){
    for(int j = i + 1;j < N;j++){
      ans += d[i] * d[j];
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
/// referenced: https://beta.atcoder.jp/contests/abc106/submissions/3039549
#include<bits/stdc++.h>
using namespace std;
int N,M,Q;
vector<vector<int>>trains(501,vector<int>(501));
vector<vector<int>>xss(501,vector<int>(501));
main(){
  cin>>N>>M>>Q;
  for(int i=1;i<=M;++i){
    int L,R;
    cin>>L>>R;
    ++trains[L][R];
  }
  for(int left=1;left<=N;++left){
    xss[left][left]=trains[left][left];
    for(int right=left+1;right<=N;++right){
      xss[left][right]=xss[left][right-1];
      for(int mid=left;mid<=right;++mid){
        xss[left][right]+=trains[mid][right];
      }
    }
  }
  for(int i=1;i<=Q;++i){
    int p,q;
    cin>>p>>q;
    cout<<xss[p][q]<<endl;
  }
}


Measured memory_bytes: 2944
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long a = cin.nextLong();
        long b = cin.nextLong();
        long c = cin.nextLong();
        long k = cin.nextLong();
        long r = a - b;
        if (Math.abs(r) > 1_000_000_000_000_000_000L)
            System.out.println("Unfair");
        else if (k % 2 == 0)
            System.out.println(r);
        else
            System.out.println(-r);
    }
}


Measured memory_bytes: 24276
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  int x = A;
  int y = B;
  
  int ans = 0;
  for (int i = 0; i < B - A + 1; i++) {
    int x1 = x % 10;
    int x2 = (x / 10) % 10;
    int x4 = (x / 1000) % 10;
    int x5 = x / 10000;
    
    if (x1 == x5 && x2 == x4) {
      ans++;
    }
    
    x++;
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
n,m,x=map(int,input().split())
ar=[list(map(int,input().split())) for i in range(n)]
cost=1e9
p=pow(2,n)
for i in range(p):
    temp=[0 for y in range(m+1)]
    pt=bin(i)[2:].zfill(n)
    for j in range(n):
        if pt[j]=='1':
            for k in range(m+1):
                temp[k]+=ar[j][k]
    z=1
    for j in range(1,m+1):
        if temp[j]<x: z=0
    if z: cost=min(temp[0],cost)
if cost==1e9: print(-1)
else: print(cost)
        
            


Measured memory_bytes: 74516
#include <iostream>
using namespace std;
int main()
{
	int n,a[100];
	cin>>n;
	double f=0;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		f=f+((float)1/a[i]);
	}
	cout<<1/f;
	return 0;
}

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

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

// #define DEBUG_IS_VALID

#ifdef DEBUG_IS_VALID
#define DEB 1 
#else
#define DEB 0
#endif
#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<"  "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<"    "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr << (next(itr)!=st.end() ? ", " : "\n"); return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : "}\n"); return os; }

void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline void chmax(T& a,T const& b){a=max(a,b);}
template<class T> inline void chmin(T& a,T const& b){a=min(a,b);}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60; 

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,k; cin >> a >> b >> c >> k;
  if(k%2==0LL){
    cout << a-b << endl;
  }else{
    cout << b-a << endl;
  }
  return 0;
}


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

int main() {
	int S,s[5], i=1;
	cin >> S;
	s[1] = S / 1000;
	s[2] = S / 100 - 10*s[1];
	s[3] = S / 10 - 100 * s[1] - 10 * s[2];
	s[4] = S - 1000 * s[1] - 100 * s[2] - 10 * s[3];

	int ans = 0;
	if (s[1] == s[2])ans = 1;
	else if (s[2] == s[3])ans = 1;
	else if (s[3] == s[4])ans = 1;

	if (ans == 1)cout << "Bad";
	else cout << "Good";

	return 0;
}

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

void solve(std::string b){
    if (b == "A") cout << "T" << '\n';
    else if (b == "T") cout << "A" << '\n';
    else if (b == "C") cout << "G" << '\n';
    else if (b == "G") cout << "C" << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::string b;
    std::cin >> b;
    solve(b);
    return 0;
}


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

int main(){
	string s;
	while(getline(cin,s)){
		while(s.find("the") == string::npos
				&& s.find("this") == string::npos
				&& s.find("that") == string::npos){
					for(int i = 0; i < s.size(); i++){
						if(s[i] == 'z')
							s[i] = 'a';
						else if(s[i] >= 'a' && s[i] <= 'z')
							s[i]++;
					}
				}
		cout << s << endl;		
	}
}

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

using namespace std;

void Main() {
    long long A, B, C, K;
    cin >> A >> B >> C >> K;

    long long ans = 0LL;
    if (K <= A) {
        ans = K;
    }
    else if (K <= A + B) {
        ans = A;
    }
    else {
        ans = A - (K - A - B);
    }
    cout << ans << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,w,wei[102],val[102],visit[100002][102];

ll dp(ll pos, ll we)
{
    ll j,p,q;
    if(pos==n)return 0;
    if(visit[we][pos]!=-1)return visit[we][pos];
    p=q=0;
    if(we+wei[pos]<=w)p=val[pos]+dp(pos+1,wei[pos]+we);
    q=dp(pos+1,we);
    return visit[we][pos]=max(p,q);
}

int main()
{
    ll i,ans;
    scanf("%lld %lld",&n,&w);
    for(i=0; i<n; i++)scanf("%lld %lld",&wei[i],&val[i]);
    memset(visit,-1,sizeof(visit));
    ans=dp(0,0);
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 79872
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int max = 0;
	for(int i = 1; i*i<=N; i++) {
	    max = Math.max(max, i*i);
	}
	System.out.println(max);
    }
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  int n;
  cin >> n;
  int sum = 0;
  rep(i, n) {
    int l, r;
    cin >> l >> r;
    sum += r-l+1;  
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
import fractions


N = int(input())
A = list(map(int, input().split()))

gcd_l = [0]
gcd_r = [0]
for i in range(N):
    gcd_l.append(fractions.gcd(gcd_l[i], A[i]))
    gcd_r.append(fractions.gcd(gcd_r[i], A[-(i+1)]))
gcd_r = gcd_r[::-1]

ans = []
for i in range(N):
    ans.append(fractions.gcd(gcd_l[i], gcd_r[i+1]))

print(max(ans))

Measured memory_bytes: 16140
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;

const int MAX_N = 200005;

char S[MAX_N];

int N, val[MAX_N], f[MAX_N];
int pos[1 << 26];

int main() {
  scanf("%s", S + 1), N = strlen(S + 1);
  
  for (int i = 1; i <= N; ++i) 
    val[i] = val[i - 1] ^ (1 << (S[i] - 'a'));
  
  memset(f, 0x3f, sizeof f);

  pos[val[N]] = N, f[N] = 0;
  
  for (int i = N - 1; i >= 0; --i) {
    if (pos[val[i]]) f[i] = f[pos[val[i]]] + 1;
    for (int j = 0; j < 26; ++j) {
      int temp = val[i] ^ (1 << j);
      if (pos[temp]) f[i] = min(f[i], f[pos[temp]] + 1);
    }
    if (!pos[val[i]] || f[pos[val[i]]] > f[i]) pos[val[i]] = i;
  }

  printf("%d\n", f[0]);
  
  return 0;
}


Measured memory_bytes: 263680
#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007
#define INF -99999999 
using namespace std;
 
int main()
{
    int x1,x2,y1,y2;  cin >> x1 >> y1 >> x2 >> y2;
    int dx = x2-x1;
    int dy = y2-y1;
    cout << x2-dy << " " << y2+dx << " " << x1-dy << " " << y1+dx << endl;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{min,max};
#[allow(unused_imports)]
use std::collections::{BTreeMap,BTreeSet};
#[allow(unused_imports)]
use std::ops::*;
#[allow(unused_imports)]
use std::collections::BinaryHeap;

#[allow(unused_macros)]
macro_rules! tf {
    ($c:expr, $t:expr, $f:expr) => {{
        if $c { $t } else { $f }
    }};
}

struct BIT<T> {
    xs: Vec<T>,
    n: usize,
}

// 0-indexed
impl<T:Add<T,Output=T>+Sub<T,Output=T>+Default+Clone+Copy> BIT<T> {
    fn new(n: usize) -> BIT<T> {
        let mut m = 1;
        while m <= n {
            m *= 2;
        }
        let n = m;
        BIT::<T> {
            xs: vec![T::default(); n+1],
            n: n
        }
    }
    fn sum(&self, i: usize) -> T {
        let mut i = i + 1;
        let mut res = T::default();
        while i > 0 {
            res = res + self.xs[i];
            i = i - (1usize << i.trailing_zeros());
        }
        res
    }
    fn range_sum(&self, l: usize, r: usize) -> T {
        if l < r {
            self.sum(r) - self.sum(l)
        }
        else {
            T::default()
        }
    }
    fn add(&mut self, i: usize, x: T) {
        let mut i = i + 1;
        while i <= self.n {
            self.xs[i] = self.xs[i] + x;
            i = i + (1usize << i.trailing_zeros())
        }
    }
}

fn compression<T:Ord+Copy>(xs: &Vec<T>) -> BTreeMap<T, usize> {
    let mut res: BTreeMap<T, usize> = BTreeMap::new();
    let mut ys = xs.clone();
    ys.sort();
    for i in 0..ys.len() {
        if i == 0 || ys[i-1] != ys[i] {
            let k = res.len();
            res.insert(ys[i], k);
        }
    }
    res
}

fn inversions<T:Copy+Ord>(xs: &Vec<T>) -> usize {
    let n = xs.len();
    let map = compression(&xs);
    let mut bit: BIT<usize> = BIT::new(n);
    let mut res = 0;
    for i in 0..n {
        res += bit.range_sum(map[&xs[i]], n);
        bit.add(map[&xs[i]], 1);
    }
    res
}

fn main() {
    let n = read_i64() as usize;
    let xs = read_vec_i64();
    let res = inversions(&xs);
    println!("{}", res);
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    //ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}

use std::fmt::Display;
#[allow(dead_code)]
fn write_vec<T: Display>(xs: &Vec<T>) {
    if xs.len() == 0 {
        println!("");
        return;
    }
    print!("{}", xs[0]);
    for i in 1..xs.len() {
        print!(" {}", xs[i]);
    }
    println!("");
}



Measured memory_bytes: 13272
use std::io::Read;

fn main() {
    let buf = {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    };
    let out = solve(&buf);
    println!("{}", &out);
}

fn solve(buf: &str) -> String {
    let mut sc = Scanner::new(&buf);
    let n: usize = sc.read();
    let mut a: Vec<usize> = sc.read_vec(n);
    let mut ans = 0;

    for i in 1..n {
        if a[i] == a[i-1] {
            ans += 1;
            a[i] = 10000000;
        }
    }
    ans.to_string()
}

struct Scanner<'a> {
    iter: std::str::SplitWhitespace<'a>,
}

impl<'a> Scanner<'a> {
    fn new(s: &'a str) -> Scanner<'a> {
        Scanner {
            iter: s.split_whitespace(),
        }
    }

    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.iter
            .next()
            .unwrap()
            .parse()
            .ok()
            .expect("parsing failed")
    }

    fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
long long n,isnp[1000009],pr[500000],prs,ans;
int main(){
	cin>>n;
	for(long long i=2;i<=1000002;i++){
		if(!isnp[i]){
			pr[prs++]=i;
			for(long long j=i+i;j<=1000002;j+=i)isnp[j]=1;
		}
	}
	isnp[0]=isnp[1]=1;
	for(long long i=0;i<prs;i++){
		if(n%pr[i]==0){
			long long j=0,p=1;
			while(n%pr[i]==0){
				n/=pr[i];
				j++;
				if(j==p){
					p++;ans++;j=0;
				}
			}
		}
	}
	if(n!=1)ans++;
	cout<<ans;
	return 0;
}

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

using namespace std;



int main(){
	
	int n;cin>>n;
	long long A[n];
	for(int i=0; i<n; i++)cin>>A[i];
	long long dp[n][n];
	for(int l=n-1; l>=0; l--){
		for(int r = l; r<n; r++){
			if(l==r){
				dp[l][r] = A[l];
			}else{
				dp[l][r] = max(A[l]-dp[l+1][r],A[r]-dp[l][r-1]);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
	return 0;
}



Measured memory_bytes: 46464
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1e+9 + 7;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

ll dp[100005][4];

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

    string s;
    cin >> s;
    int n = s.length();
    dp[0][0] = 1;
    for(int i = 0; i < n; ++i){
        if(s[i] == '?'){
            // ? -> A
            chadd(dp[i + 1][0], dp[i][0]);
            chadd(dp[i + 1][1], dp[i][0] + dp[i][1]);
            chadd(dp[i + 1][2], dp[i][2]);
            chadd(dp[i + 1][3], dp[i][3]);

            // ? -> B
            chadd(dp[i + 1][0], dp[i][0]);
            chadd(dp[i + 1][1], dp[i][1]);
            chadd(dp[i + 1][2], dp[i][1] + dp[i][2]);
            chadd(dp[i + 1][3], dp[i][3]);

            // ? -> C
            chadd(dp[i + 1][0], dp[i][0]);
            chadd(dp[i + 1][1], dp[i][1]);
            chadd(dp[i + 1][2], dp[i][2]);
            chadd(dp[i + 1][3], dp[i][2] + dp[i][3]);
        }
        else{
            dp[i + 1][0] = dp[i][0];
            if(s[i] == 'A'){
                chadd(dp[i + 1][1], dp[i][0] + dp[i][1]);
                dp[i + 1][2] = dp[i][2];
                dp[i + 1][3] = dp[i][3];
            }
            else if(s[i] == 'B'){
                dp[i + 1][1] = dp[i][1];
                chadd(dp[i + 1][2], dp[i][1] + dp[i][2]);
                dp[i + 1][3] = dp[i][3];
            }
            else if(s[i] == 'C'){
                dp[i + 1][1] = dp[i][1];
                dp[i + 1][2] = dp[i][2];
                chadd(dp[i + 1][3], dp[i][2] + dp[i][3]);
            }
        }
    }
    cout << dp[n][3] << endl;
}

Measured memory_bytes: 3664
#include <cmath>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(false);

	ll n, m;
	cin >> n >> m;

	ll ans = min(n,m/2);
	ans += (m-2*ans)/4;
	
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
using System;

namespace ConsoleApp12
{
    class Program
    {
        static void Main(string[] args)
        {
            int nyuuryoku = int.Parse(Console.ReadLine());
            int gohyaku = nyuuryoku / 500;
            int goen = (nyuuryoku - gohyaku*500) / 5;
            Console.WriteLine(gohyaku * 1000+goen*5);
            
        }
    }
}


Measured memory_bytes: 13140
import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


fun solve() {
    val N = rd.readInt()
    val A = rd.readListIntCol(N)

    val B = A.sorted()
    val odd = mutableSetOf<Int>()
    val even = mutableSetOf<Int>()
    for (i in 0 until N) {
        if (i%2==0) odd.add(B[i])
        else even.add(B[i])
    }

    var cnt = 0
    for (i in 0 until N) {
        when (i%2) {
            0 -> {
                if (!odd.contains(A[i])) cnt++
            }
            else -> {
                if (!even.contains(A[i])) cnt++
            }
        }
    }

    val ans = cnt/2
    println(ans)
}


//val rd = debug.Reader("agc", "003", "c", "sample-1")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!! }
    catch (e: Exception) { throw e }
    finally { rd.close() }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
const val EPS = 1e-9; fun DBLEQ(a: Double, b: Double): Boolean {return abs(a - b) < EPS}
data class IntPair(val first: Int, val second: Int); data class LongPair(val first: Long, val second: Long)
data class To(val idx: Int, val cost: Long)
typealias ALI = ArrayList<Int>
fun <T>edge(V: Int): Array<ArrayList<T>> { return Array(V){ArrayList<T>()} }
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readDouble: () -> Double = { br.readLine().toDouble() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
    val readIntArray: () -> IntArray = { readListInt().toIntArray() }
    val readLongArray: () -> LongArray = { readListLong().toLongArray() }
    val readListStringCol: (Int) -> List<String> = { N -> (0 until N).map { readString() } }
    val readListIntCol: (Int) -> List<Int> = { N -> (0 until N).map { readInt() } }
    val readListIntCols: (Int) -> List<List<Int>> = { N -> (0 until N).map { readListInt() } }
    val readListLongCol: (Int) -> List<Long> = { N -> (0 until N).map { readLong() } }
    val readListLongCols: (Int) -> List<List<Long>> = { N -> (0 until N).map { readListLong() } }
    val close: () -> Unit = { br.close() }
    protected fun finalize() { close() }
}


Measured memory_bytes: 61436
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

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


int main(){
	int a,b;
	cin >> a >> b;

	if(a<b){
		cout << "0" << endl;
	}else{
		cout << "10" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
d='URLD'
*y,s,t=open(0).read().split()
h,w,n,r,c=map(int,y)
a=0
for i,j in enumerate(d):
  x=[h-r+1,c,w-c+1,r][i]
  for k in range(n):
    x+=(s[k]==j)
    a|=x>[h,w,w,h][i]
    x-=(dict(zip(d,d[::-1]))[t[k]]==j)*x>1
print('YNEOS'[a::2])

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

using namespace std;

#define int long long

struct Fenwick {
	int n;
	vector<int> f;

	Fenwick(int n_) {
		n = n_;
		f.resize(n);
	}

	int get(int x) {
		int res = 0;
		for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
			res += f[i];
		}
		return res;
	}

	void add(int x, int v) {
		for (int i = x; i < n; i = (i | (i + 1))) {
			f[i] += v;
		}
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (auto &t : a) {
		cin >> t;
	}
	vector<int> ps(n + 1);
	for (int i = 0; i < n; i++) {
		ps[i + 1] = ps[i] + a[i];
	}
	vector<int> v(n + 1);
	for (int i = 0; i <= n; i++) {
		v[i] = k * i - ps[i];
		v[i] *= -1;
	}
	{
		vector<int> seen = v;
		sort(seen.begin(), seen.end());
		seen.resize(unique(seen.begin(), seen.end()) - seen.begin());
		for (auto &t : v) {
			t = lower_bound(seen.begin(), seen.end(), t) - seen.begin();
		}
	}
	int ans = 0;
	Fenwick f(n + 1);
	for (int i = 0; i <= n; i++) {
		ans += f.get(v[i]);
		f.add(v[i], 1);
	}
	cout << ans << endl;
}


Measured memory_bytes: 6528
#include <iostream>

using namespace std;

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

  int a, b;
  cin >> a >> b;

  if (a + b >= 24) {
    cout << a + b - 24 << endl;
  } else {
    cout << a + b << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import defaultdict

def main():
	n,m=MI()
	A=[0]+LI()

	for i in range(n):
		A[i+1]+=A[i]
		A[i+1]%=m
	#print(A)

	d=defaultdict(int)

	for i in A:
		d[i]+=1
	#print(d)

	ans=0
	for k,v in d.items():
		ans+=v*(v-1)//2
	print(ans)











if __name__ == "__main__":
	main()


Measured memory_bytes: 93908
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define rep11(i, n) for (int i = 1; i < (int)(n); ++i)
#define rep0(i, n) for (int i = 1; i <= (int)(n); ++i)
#define repo(i, o, n) for (int i = o; i < (int)(n); ++i)
#define repm(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LO

int main(){
    long long n;
    cin>>n;
    vector<string> s;
    rep(i,n){
        string S;
        cin>>S;
        s.push_back(S);
    }
    map<string,long long> mp;
    rep(i,n){
        sort(s[i].begin(),s[i].end());
        mp[s[i]]+=1;
    }
    long long ans_a=0;
    for(auto it=mp.begin(); it!=mp.end(); ++it){
        pair<string,long long> v =*it;
        ans_a+=v.second*(v.second-1)/2;
    }
    cout<<ans_a<<endl;
    
}


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

typedef pair<int,int> pii;

vector<pii>train;
const int H=60*60;
const int M=60;
const int S=1;
int unit[3]={H,M,S};

int getTime(string s){
  string tmp;
  int res=0;
  for(int i=0;i<3;i++){
    tmp=s.substr(3*i,2);
    int val=unit[i]*atoi(tmp.c_str());
    res+=val;
  }
  return res;
}

void makeEvent(string start,string arrival){
  int st=getTime(start);
  int at=getTime(arrival);
  train.push_back(make_pair(st,1));
  train.push_back(make_pair(at,0));
}

int main(){
  int n;
  while(cin>>n,n){
    train.clear();
    for(int i=0;i<n;i++){
    string start,arrival;
    cin>>start>>arrival;
    makeEvent(start,arrival);
    }
    int ans=0,tmp=0;
    sort(train.begin(), train.end());
    for(pii i:train){
      if(i.second==1){
	tmp++;
      }else{
	tmp--;
      }
      ans=max(tmp,ans);
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main()
{
	int i = 0 , n = 0 , num , card[4][13] = {};
	char e ;
	cin >> n ;
	for ( i = 0 ; i < n ; i++ )
	{
		cin >> e >> num ;
		if ( e == 'S' ) card[0][num-1] = 1 ;
		if ( e == 'H' ) card[1][num-1] = 1 ;
		if ( e == 'C' ) card[2][num-1] = 1 ;
		if ( e == 'D' ) card[3][num-1] = 1 ;
	}
	for ( i = 1 ; i <= 13 ; i++ )
	{
		if ( card[0][i-1] != 1 ) cout << "S " << i << endl ;
	}
	for ( i = 1 ; i <= 13 ; i++ )
	{
		if ( card[1][i-1] != 1 ) cout << "H " << i << endl ;
	}
	for ( i = 1 ; i <= 13 ; i++ )
	{
		if ( card[2][i-1] != 1 ) cout << "C " << i << endl ;
	}
	for ( i = 1 ; i <= 13 ; i++ )
	{
		if ( card[3][i-1] != 1 ) cout << "D " << i << endl ;
	}
	return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;

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

	ll N,X;
	cin >> N >> X;
	vector<ll> S(N);
	FOR(i,0,N)cin>>S[i];
	SORT(S);
	REV(S);
	ll dp[N+2][X+1]={};
	dp[0][X]=1;

	FOR(i,0,N){
		FOR(j,0,X+1){
			(dp[i+1][j%S[i]] += dp[i][j])%=MOD;
			(dp[i+1][j] += dp[i][j]*(N-i-1))%=MOD;
		}
	}
	ll ans = 0;
	FOR(j,1,X+1){
		(ans += dp[N][j]*j)%=MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 158080
#include<stdio.h>

int main(void){
   char s[100];
   int k;
   int n=0;

   scanf("%d",&k);
   scanf("%s",s);

   for(int i=0;s[i]!='\0';i++){
      n++;
   }

   if(n<=k){
      printf("%s",s);
   }else{
      for(int j=0;j<k;j++){
        printf("%c",s[j]);
      }
      printf("...");
   }

   return 0;
}


Measured memory_bytes: 1688
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

int main(int argc, char const *argv[]) {
	int n;
	cin >> n;
	vector<int> v(n);
	int tmp;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v[i] = tmp;
	}
	int min = *min_element(v.begin(), v.end());
	int max = *max_element(v.begin(), v.end());
	std::cout << abs(max -min) << '\n';
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<stack>
#include<set>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn =1000100;
typedef pair<ll,ll>p1;
typedef pair<pair<ll,ll>,ll>p2;
map<pair<pair<ll,ll>,ll>,ll>m1;
map<pair<ll,ll>,ll>m2;
const int MOD = 1e9;
const int N=351;
const int inf = 0x3f3f3f3f;
typedef pair<char, int> PAIR;
map<string,int>mm;
char a[maxn],b[maxn];
int dp[3003][3003];
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int n=strlen(a);
    int m=strlen(b);
    for(int i=n-1;i>=0;i--)
    {
        for(int j=m-1;j>=0;j--)
        {
            if(a[i]==b[j])
            {
                dp[i][j]=dp[i+1][j+1]+1;
            }else
            {
                dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
            }
        } 
     }
     int i=0;
    int j=0;
    while(i<n&&j<m)
    {
        if(a[i]==b[j])
        {
            printf("%c",a[i]);
            i++;
            j++;
        }else if(dp[i][j]==dp[i+1][j])
        {
            i++;
        }else
        {
            j++;
        }
    }
}

Measured memory_bytes: 38864
#include<bits/stdc++.h>
#define long long long 
#define mod %
using namespace std;

//pdf見て回答

int main(){
    int k;
    queue<long> q;
    cin >> k;

    for(int i = 1; i < 10; i++){q.push(i);}

    for(int i = 0; i < k; i++){
        long x = q.front(); 
        if(x mod 10 != 0){
            q.push(x * 10 + (x mod 10) - 1);
        }
        q.push(10 * x + (x mod 10));
        if(x mod 10 != 9){
            q.push(10 * x + (x mod 10) + 1);
        }
        if(i == k - 1){cout << q.front() << endl;}
        q.pop();
    }
}

Measured memory_bytes: 1792