akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
 
int main(){
  int m,f,b;
  cin>>m>>f>>b;

  if(b<=m+f)

   if(b<=m) cout<< 0 <<endl;
    else
    cout<<b-m<<endl;

  else
   cout<<"NA"<<endl;

  return 0;
}


Measured memory_bytes: 3108
#include<stdio.h>
#include<iostream>
int main() {
  double a,b,c,d,e,f;
  while(std::cin>>a>>b>>c>>d>>e>>f) {
    printf("%.3f %.3f\n",((c-(b*((a*f-c*d)/(a*e-b*d))))/a),(a*f-d*c)/(a*e-b*d));
  }
}

Measured memory_bytes: 0
import * as fs from 'fs';

namespace AtCoder.abc083 {
    export class Program {
        constructor(private readonly args: string[][]) {

        }

        main(this: Program) {
            const [a, b, c, d]: number[] = this.args[0].map(Number);

            if (a + b > c + d) console.log('Left');
            if (a + b < c + d) console.log('Right');
            if (a + b === c + d) console.log('Balanced');

        }
    }
}

const args: string[][] = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n').map(r => r.split(' '));
const prg: AtCoder.abc083.Program = new AtCoder.abc083.Program(args);
prg.main();


Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

// 最大公約数
ll gcd(ll m, ll n) {
  if (n==0) return abs(m);
  else return gcd(n, m%n);
}

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i=0; i<N; i++) cin >> A[i];
  ll g = A[0];
  for (int i=1; i<N; i++) g = gcd(g, A[i]);
  if (K%g!=0) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  if (K>*max_element(A.begin(), A.end())) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  cout << "POSSIBLE" << endl;
  return 0;
}

Measured memory_bytes: 3700
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

L, R, D = map(int, input().split())

ans = 0
for x in range(L, R + 1):
    if (x % D) == 0:
        ans += 1

print(ans)


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

 int main(){
 int N, X, m[101];
 cin >> N >> X;
 int S = 0, M = 1001001001;
 for(int i = 0; i < N; ++i){
 cin >> m[i];
 S += m[i];
 if(m[i] < M){
 M = m[i];
 		}
	}
 	int ans = N + (X - S) / M;
	cout << ans << endl;
}

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

int main()
{
    int b;
    long long int ans = 0;

    int N;
    cin >> N;

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

    sort(A.begin(), A.end());

    b = A[N/2];

    for( int i = 0; i < N; ++i ){
        ans += abs(A[i] - b);
    }

    //cout << b << " : " << ans << endl;
    
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1152
#include <stdio.h>
#include <math.h>
 
int main(void){
    // Your code here!
    int x, y, z, res;
    char buf[6];

    scanf("%d%d", &x, &y);
    if(y<10)
        z = x*10+y;
    else if(y<100)
        z = x*100+y;
    else
        z = x*1000+y;
        
    res = (int)sqrt(z);
     
    if(res*res == z)
        printf("Yes");
    else
        printf("No");
        
        return 0;
}


Measured memory_bytes: 128
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()
diff = []
for i in range(N-1):
    diff.append(A[i+1] - A[i])
diff.append(abs(K - A[N-1] + A[0]))
diff.sort()
print(K - diff[N-1])


Measured memory_bytes: 26436
#include <iostream>
#include <array>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int n, result = 0;
    cin >> n;
    array<int, 3> points[n + n];
    for (int i = 0; i < n; i++) {
        cin >> points[i][0] >> points[i][1];
        points[i][2] = 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> points[i + n][0] >> points[i + n][1];
        points[i + n][2] = 1;
    }
    sort(points, points + n + n);
    set<int> red;
    for (int i = 0; i < n + n; i++) {
        if (points[i][2] == 1) {
            auto it = red.lower_bound(points[i][1]);
            if (it != begin(red)) {
                red.erase(prev(it));
                result++;
            }
        } else {
            red.emplace(points[i][1]);
        }
    }
    cout << result;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()

#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,a,b) for(int i=(a); i<=(b); i++)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-10;
//int mod=1000000007;




int main(){
	int a,b;
	vi v(101,0);
	while(cin>>a>>b){
		v[a]++;
		v[b]++;
		if(a==0){
			bool f=true;
			if(v[1]%2==0||v[2]%2==0){
				f=false;
			}
			for(int i=3; i<101; i++){
				if(v[i]%2==1||!f){
					f=false;
					break;
				}
			}
			cout<<(f?"OK":"NG")<<endl;
			for(int i=0; i<101; i++){
				v[i]=0;
			}
		}
	}
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,char> P;

bool ok(P a,P b,P c){
    return a.second == b.second && b.second == c.second && ((a.first-b.first == 1 && b.first-c.first == 1) || (a.first == b.first && b.first == c.first));
}

bool comp(P a,P b){
    return a.first + (int)a.second * 10 < b.first + (int)b.second * 10;
}

int main(){
    int T;

    cin >> T;

    for(int i=0; i<T; i++){
        vector<P> v(9);

        for(auto &t:v) cin>>t.first;

        for(auto &t:v) cin>>t.second;

        bool flag=false;

        do{
            flag = (ok(v[0],v[1],v[2]) && ok(v[3],v[4],v[5]) && ok(v[6],v[7],v[8]));
        }while(!flag && next_permutation(v.begin(),v.end()));

        cout << (flag ? 1 : 0) << endl;
    }
}

Measured memory_bytes: 1188
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = Integer.parseInt(scan.next());
        int taroScore = 0, hanakoScore = 0;

        for (int i = 0; i < num; i++) {
            String taroS = scan.next(), hanakoS = scan.next();
            int comp = taroS.compareTo(hanakoS);

            if (comp > 0) {
                taroScore += 3;
            } else if (comp < 0) {
                hanakoScore += 3;
            } else {
                taroScore++;
                hanakoScore++;
            }
        }

        System.out.println(taroScore + " " + hanakoScore);
    }
}



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

int main(){
  int N,Y;
  cin >> N >> Y;
  
  int a[3]={0};
  bool flag =false;
  for(int i = 0; i <= N; i++){
    int money = i * 10000;
    if(money > Y){
      break;
    }
    for(int j = 0; j <= (N -i);j++){
      int j_money = money + j *5000;
      if(j_money > Y){
        break;
      }else{
        if(j_money + (N - i - j) * 1000 == Y){
          a[0] = i;
          a[1] = j;
          a[2] = N - i -j;
          flag = true;
        }
      }
      if(flag)break;
    }
    if(flag)break;
  }
  
  if(!flag){
      cout << "-1 -1 -1" << endl;
      return 0;
    }
  
  for(int i = 0; i < 3; i++){
    cout << a[i] << " " ;
  }
  cout << endl;
}


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

int main(){

 
  int N,M;
  
  map<long long,int> mp;
  
  cin>>N;
  rep(i,N){
   
    int a;
    cin>>a;
    mp[a]++;
    
  }

  cin>>M;
  
  rep(j,M){
    
    int b;
    cin>>b;
    if(mp[b]==0){cout<<"NO"<<endl;return 0;}
    
    mp[b]--;
  }
  cout<<"YES"<<endl;
}

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

map<int, vector<int>> mp;
int p = 0;

void Search(int pos, int par, vector<int> &ans, vector<int> &c) {
	ans[pos] = c[p++];
	for (int i = 0; i < mp[pos].size(); i++) {
		if (mp[pos][i] != par)
			Search(mp[pos][i], pos, ans, c);
	}
	return;
}

int main(void) {
	int num, a, b, i = 0, sum = 0;
	cin >> num;
	vector<int> c(num), ans(num);
	for (; i < num - 1; i++) {
		scanf("%d%d", &a, &b);
		mp[--a].push_back(--b);
		mp[b].push_back(a);
	}
	for (i = 0; i < num; i++)
		scanf("%d", &c[i]);
	sort(c.begin(), c.end(), greater<int>());
	for (i = 1; i < num; i++)
		sum += c[i];
	printf("%d\n", sum);
	Search(0, 0, ans, c);
	for (i = 0; i < num; i++)
		printf("%d ", ans[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 2560
N,M=[int(x) for x in input().rstrip().split()]
H=[int(x) for x in input().rstrip().split()]
ans=[[] for i in range(N)]
# print(ans)

for i in range(M):
  A,B=[int(x) for x in input().rstrip().split()]
  ans[A-1].append(H[B-1])
  ans[B-1].append(H[A-1])

now=0
cnt=0
for i in range(N):
  if len(ans[i])==0:
    now=0
  else:
    now=max(ans[i])
  if now<H[i]:
    cnt+=1

print(cnt)

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

int main(){
	int n;
	cin >> n;
	vector<LL> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int bad = 0;

	LL psum = 0;
	for(int i = 0; i < n; i++){
		if(psum * 2 < a[i]) bad = i;
		psum += a[i];
	}
	cout << n - bad << '\n';
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int ans = 0;
int a[25];
int val[25];
int extra[25];
main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]);
    for (int i = 1; i < n; i++)
        scanf("%d", &extra[i]);
    for (int i = 1; i < n; i++)
    {
        ans += val[i];
        if(a[i] + 1 == a[i + 1])
            ans += extra[a[i]];
    }
    ans += val[n];
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    string s; cin >> s;
    string t; cin >> t;

    int n = stoi(s+t);

    for (int i = 1; i <= 320; i++) {
        if (i*i == n) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}




Measured memory_bytes: 256
c = []
for i in range(3):
    c.append(list(map(int, input().split())))

flag = True
for i in range(2):
    x = c[i][0] - c[i+1][0]
    y = c[i][1] - c[i+1][1]
    z = c[i][2] - c[i+1][2]

    p = c[0][i] - c[0][i+1]
    q = c[1][i] - c[1][i+1]
    r = c[2][i] - c[2][i+1]
    if x != y or y != z or x != z:
        flag = False
        break
    elif p != q or q != r or p != r:
        flag = False
        break

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
import           Control.Monad
import           Data.Array
import qualified Data.ByteString.Char8 as BS
import           Data.List
import           Data.Maybe
import           Data.Ord

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

main = do
  (n:_) <- readInts
  print $ (n - 1) * n `div` 2


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

int main(){
    string s;
    cin >> s;
    bool a = false, b = false, c = false;
    for(int i = 0; i < 3; i++){
        if(s[i] == 'a'){
            a = true;
        }
        if(s[i] == 'b'){
            b = true;
        }
        if(s[i] == 'c'){
            c = true;
        }
    }
    if(a && b && c) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding:utf-8 -*-

N = int(input())
def digit(i):
    if i>0:
        return digit(i//10) + [i%10]
    else:
        return []

SN = sum(digit(N))

if (N%SN == 0): 
    print("Yes")
else:
    print("No")

Measured memory_bytes: 2940
#include <stdio.h>
#define max(p,q)((p)>(q)?(p):(q))

int main(){
	int x,a,b,n;
	scanf("%d%d%d%d",&x,&a,&b,&n);
	while(n--){
		char s[10];
		scanf(" %s",s);
		if(s[0]=='n')x+=a;
		if(s[0]=='t')x+=b;
		if(s[0]=='k')x=0;
		x=max(x,0);
	}
	printf("%d\n",x);
}


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

const int _ = 3003;
struct Edge{int end , upEd;}Ed[_ << 1];
int head[_] , cntEd , N , A[_]; bool win[_];
void addEd(int a , int b){Ed[++cntEd] = (Edge){b , head[a]}; head[a] = cntEd;}

bool getwin(int x){
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(A[Ed[i].end] < A[x] && !getwin(Ed[i].end)) return 1;
	return 0;
}

int main(){
	cin >> N; for(int i = 1 ; i <= N ; ++i) cin >> A[i];
	for(int i = 1 ; i < N ; ++i){int p , q; cin >> p >> q; addEd(p , q); addEd(q , p);}
	for(int i = 1 ; i <= N ; ++i) if(getwin(i)) cout << i << ' ';
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x = i;
        if (x % 3 == 0) {
            cout << " " << i;
            continue;
        }
        while (x) {
            if (x % 10 == 3) {
                cout << " " << i;
                break;
            }
            x /= 10;
        }
    }
    cout << endl;
}

Measured memory_bytes: 3096
#include <stdio.h>
int linearsearch(int A[],int n,int key){
  int i=0;
  A[n]=key;
  while(A[i]!=key)i++;
  if(i==n) return 0;
  return 1;
}
int main(){
  int i,n,A[10001],q,key,sum=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(linearsearch(A,n,key)==1)sum++;
  }
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 636
using System;
using System.Linq;
using System.Collections.Generic;

namespace program
{
    class Program
    {
        static void Main()
        {
          int[] num = Input.ScanIntArray();
          Console.WriteLine(((num[1]*10+num[2]) % 4) ==0 ? "YES" : "NO");
        }
    }

    static class Input
    {
        static public int ScanInt() { return int.Parse(Console.ReadLine()); }
        static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
        static public long ScanLong() { return long.Parse(Console.ReadLine()); }
        static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
        static public int[] ScanIntArray() { return Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray(); }
        static public uint[] ScanUintArray() { return Console.ReadLine().Split(' ').Select(x => uint.Parse(x)).ToArray(); }
        static public long[] ScanLongArray() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray(); }
        static public ulong[] ScanUlongArray() { return Console.ReadLine().Split(' ').Select(x => ulong.Parse(x)).ToArray(); }

        static public string ScanStr() { return Console.ReadLine(); }
        static public string[] ScanStrArray() { return ScanStr().Split(' '); }
    }

    static class MyMath
    {
        public static int GCD(int a, int b)
        {
            Func<int, int, int> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }
        public static ulong GCD(ulong a, ulong b)
        {
            Func<ulong, ulong, ulong> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }
        public static int LCM(int a, int b)
        {
            return a * b / GCD(a, b);
        }
        public static ulong LCM(ulong a, ulong b)
        {
            return a * b / GCD(a, b);
        }
    }
}


Measured memory_bytes: 13396
a = [int(input()) for i in range(1)]
n = a[0]
works = [list(map(int, input().split())) for i in range(n)]
#print(works)  
works = sorted(works, key=lambda x: x[1])
work_time = 0
for w in works:
  work_time += w[0]
  if work_time > w[1]:
    print("No")
    break
else:
  print("Yes")


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

using namespace std;
template<typename T> void in(T &x) { x = 0; bool neg = false; register T c = getchar(); if (c == '-')neg = true, c = getchar(); while ((c < 48) || (c > 57))c = getchar(); for (; c < 48 || c > 57; c = getchar()); for (; c > 47 && c < 58; c = getchar())x = (x << 3) + (x << 1) + (c & 15); if (neg) x *= -1; }
template<typename T> void out(T n) { bool neg = 0; if (n < 0)n *= -1, neg = 1; char snum[65]; int i = 0; do { snum[i++] = n % 10 + '0'; n /= 10; } while (n); --i; if (neg)putchar('-'); while (i >= 0)putchar(snum[i--]); }
template<typename T> void outln(T n) { bool neg = 0; if (n < 0)n *= -1, neg = 1; char snum[65]; int i = 0; do { snum[i++] = n % 10 + '0'; n /= 10; } while (n); --i; if (neg)putchar('-'); while (i >= 0)putchar(snum[i--]); putchar('\n'); }
#define len(_x) (sizeof((_x)) / sizeof(_x)[0])
#define fastIO ios_base::sync_with_stdio(false); cin.tie(false);
#define ll long long
#define itr(_c) for(auto i=_c.begin();i!=_c.end();i++)
#define itrr(_c)for(auto i=_c.begin();i!=_c.end();i++)
#define f1(_x)for (int i = 0; i < _x; ++i)
#define fr(_x)for (int i = _x; i >0; i--)
#define f2(_x,_y)for (int i = _x; i < _y; ++i)
#define fileIO 	freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
typedef vector<int> vi; typedef vector<string> vs; typedef vector<bool> vb; vector<long long>vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;

template<typename T>
T gcd(T __m, T __n)
{
	while (__n != 0)
	{
		T __t = __m % __n;
		__m = __n;
		__n = __t;
	}
	return __m;
}
vi v,vv;
int main() {	
	int n, p, t; in(n); in(p);
	while (n--) { in(t); v.push_back(t); }
	int numE = count_if(v.begin(), v.end(), [](int x) {return x % 2 == 0; });
	int numO = v.size() - numE;
	if (numO == 0 && p == 1) {puts("0");return 0;}
	std::cout << (ll)(pow(2, numE)*pow(2, numO==0?0:numO-1));


	
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int a,b;
	cin >> a >> b;
	vector<int>count(60);
	for(int i = 2; i<=60; i++){
		int val = 0;
		if(b%(1LL<<i)>=(1LL<<(i-1))){
			val+=b%(1LL<<i)-(1LL<<(i-1))+1;
		}
		count[i-1]+=val;
	}
	if(b%4==1LL||b%4==2LL){
		count[0]++;
	}
	a--;
	for(int i = 2; i<=60; i++){
		int val = 0;
		if(a%(1LL<<i)>=(1LL<<(i-1))){
			val+=a%(1LL<<i)-(1LL<<(i-1))+1;
		}
		count[i-1]+=val;
	}
	if(a%4==1LL||a%4==2){
		count[0]++;
	}
	int ans = 0;
	for(int i = 0; i<60; i++){
		count[i]%=2;
		if(count[i])	
		ans+=(1LL<<i);
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 3596
#include "bits/stdc++.h"
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;

int main(){
  string s;
  ll k;
  cin>>s>>k;


  if(s.size()==1){
    cout<<(k/2)<<endl;
    return 0;
  }

  ll hh =0;

  for(ll i=1;i<s.size();i++){
    if(s[i-1]!=s[i]){
      hh=1;
      break;
    }
  }

  if(hh==0){
    cout<<(s.size()*k)/2<<endl;
    return 0;
  }

ll tmp1=0;
ll kaeta=0;
char pre=s[0];
char one=s[0];
bool mae=0;

  for(ll i=1;i<s.size();i++){
    if(mae==1){
      mae=0;
      pre = s[i];
      continue;
    }
    if(pre==s[i]){
      tmp1++;
      mae=1;
    }
    pre = s[i];
  }
  ll tmp2=0;
  pre=one;
  mae=0;
  s+=s;
  for(ll i=1;i<s.size();i++){
    if(mae==1){
      mae=0;
      pre = s[i];
      continue;
    }
    if(pre==s[i]){
      tmp2++;
      mae=1;
    }
    pre = s[i];
  }

  /*

   ll tmp3=0;
  pre=one;
  mae=0;
  s+=s;
  for(ll i=1;i<s.size();i++){
    if(mae==1){
      mae=0;
      pre = s[i];
      continue;
    }
    if(pre==s[i]){
      tmp3++;
      mae=1;
    }
    pre = s[i];
  }

     ll tmp4=0;
  pre=one;
  mae=0;
  s+=s;
  for(ll i=1;i<s.size();i++){
    if(mae==1){
      mae=0;
      pre = s[i];
      continue;
    }
    if(pre==s[i]){
      tmp4++;
      mae=1;
    }
    pre = s[i];
  }

 
  cout<<tmp1<<endl;
  cout<<tmp2<<endl;
    cout<<tmp3<<endl;
      cout<<tmp4<<endl;
*/

ll kei =tmp2 - tmp1*2;

cout<<tmp1*1+(kei+tmp1)*(k-1)<<endl;







}
  


Measured memory_bytes: 256
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }
#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }
#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
const int inf = INT_MAX;
const int MOD = 1e9 + 7;



signed main(){
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif  
    IOS;

    int a, b;
    cin >> a >> b;
    cout << max({a + b, a - b, a * b});
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
using namespace std;
 
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define REPI(i, s, e) for (int i = (s); i <= (e); i++)
#define rep(i, n) REP(i, 0, n)
#define repi(i, n) REPI(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
 
#define dump(x) (cout << #x << " = " << x << endl)
#define dump2(x, y) (cout << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl)
#define dump3(x, y, z) (cout << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", "<< z << ")" << endl)
 
typedef long long ll;
typedef pair<int, int> pii;

int n;

bool not_trivial(int a, int b, int m, int n)
{
	if (a ==  1 && b ==  0) return false;
	if (a ==  0 && b ==  1) return false;
	if (a == -1 && b ==  0) return false;
	if (a ==  0 && b == -1) return false;
	if (a ==  m && b ==  n) return false;
	if (a == -n && b ==  m) return false;
	if (a == -m && b == -n) return false;
	if (a ==  n && b == -m) return false;
	return true;
}

bool can_devide(int p, int q, int m, int n)
{
	int t = m*m + n*n;
	if (t == 0) return false;
	int x = m*p+n*q;
	int y = -n*p+m*q;
	return x%t==0&&y%t==0&&not_trivial(x/t, y/t, p, q);
}

int main()
{
	cin >> n;
	rep(i, n) {
		int p, q;
		cin >> p >> q;
		bool f = false;
		for (int m = 0; m*m < 100000; m++) {
			for (int n = 0; m*m+n*n < 100000; n++) {
				if (can_devide(p, q, m, n)
					|| can_devide(p, q, m, -n)
					|| can_devide(p, q, -m, n)
					|| can_devide(p, q, -m, -n)
					) {
					f = true;
					goto END;
				}
			}
		}
END:
		printf("%c\n", f?'C':'P');
	}
	return 0;
}

Measured memory_bytes: 1144
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N; cin >> N;
    vector<int> A(N); for (auto& a : A) cin >> a;
    int sum = accumulate(begin(A), end(A), 0);
    bitset<2000*2000+1> B;
    B[0] = 1;
    for (auto a : A) {
        B |= B << a;
    }
    for (int i = sum/2; i >= 0; i--) {
        if (B[i]) {
            cout << sum - i << endl;
            break;
        }
    }
    return 0;
}


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

#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF (1LL<<60)
#define MOD 1000000007

int N, M;
vector<P> G[1001];
vector<P> R[1001];

int B[1001];
bool visited[1001];
void dfs(int x) {
  visited[x] = true;
  for (P p : R[x]) {
    if (!visited[p._1]) dfs(p._1);
  }
}

int f(int x, int d) {
  if (x == N) return d;
  if (B[x] >= d) return -INF;
  else {
    if (B[x] != -INF) return INF;
  }
  B[x] = d;
  int ret = -INF;
  for (P p : G[x]) {
    if (!visited[p._1]) continue;
    ret = max(ret, f(p._1, d+p._2));
  }
  return ret;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    G[a].pb(P(b, c));
    R[b].pb(P(a, c));
  }
  G[N-1].pb(P(N, 0));
  R[N].pb(P(N-1, 0));

  dfs(N);
  rep(i, N) B[i] = -INF;
  B[N] = 0;
  int m = f(0, 0);
  if (m == INF) cout << "inf\n";
  else cout << m << "\n";
  return 0;
}


Measured memory_bytes: 512
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,a,b,c,d=map(int,input().split())

for i in range(n):
    if c*i-d*(n-i-1)<=b-a<=d*i-c*(n-i-1):
        print("YES")
        break
else:
    print("NO")

Measured memory_bytes: 71400
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;
const double PI = acos(-1.0);


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * b / g;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}
const int MAX = 510000;
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;
}

using Graph = vector<VE>;

int dp[100010][13];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	double a, b, x; cin >> a >> b >> x;
	double now = 0;
	double v = a * a*b;
	if (2 * x < v) {
		now = a * b*b / (2*x);
	}
	else {
		now = 2 * (v - x) / (a*a*a);
	}
	double ans = atan(now)*180.0 / PI;
	cout << fixed << setprecision(15) << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<stdlib.h>

using namespace std;

int p,t,x;
int main(){
  int n;
  scanf("%d",&n);
  int a[n];
  for (int i = 0; i<n; i++){
    scanf("%d",&a[i]);
  }p = 1;
  int t = 0;
  for (int i = 0; i<n; i++){
    if (x == a[i]){
      p *= -1;
      if (p == -1)
        t ++;
    }else{
      x = a[i];
      p = 1;
    }
  }printf("%d\n",t);
  return 0;
}


Measured memory_bytes: 256
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    l, r, d = mi()

    print(r//d - (l-1)//d)

    return

main()


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

int main(){
  string S;
  cin >> S;
  vector<char> v;
  for(int i=0;i<S.size();i++){
    if(S[i]!='B') v.push_back(S[i]);
    else if(!v.empty()) v.pop_back();
  }
  for(auto c:v) cout << c;
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S; cin>>S;
  int ans=0;
  vector<char> s(4);
  for(int i=0; i<4; i++){
    s[i]=S.at(i);
  }
  sort(s.begin(), s.end());
  if(s[0]!=s[1]){
    ans=1;
  }
  if(s[2]!=s[3]){
    ans=1;
  }
  if(s[1]==s[2]){
    ans=1;
  }
  if(ans==0){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
int H, W, N;
bool  solve(vector<int> &A, vector<int> &B, int W, int X) {
	vector<int> dpR(2 * N + 1);
	vector<int> dpL(2 * N + 1);
	dpR[2 * N] = W + 1;
	dpL[2 * N] = 0;
	for (int i = N - 1; i >= 0; i--) {
		int t;
		t = 2 * i + 1;
		dpR[t] = dpR[t + 1];
		dpL[t] = dpL[t + 1];
		if (B[i] == -1) {
			if (dpR[t + 1] < W + 1) {
				dpR[t] = dpR[t + 1] + 1;
			}
		}

		if (B[i] == 1) {
			if (dpL[t + 1] > 0) {
				dpL[t] = dpL[t + 1] - 1;
			}
		}


		t = 2 * i;
		dpR[t] = dpR[t + 1];
		dpL[t] = dpL[t + 1];

		if (A[i] == 1) {
			dpR[t] = dpR[t + 1] - 1;
		}

		if (A[i] == -1) {
			dpL[t] = dpL[t + 1] + 1;
		}
	}

	if (dpR[0] <= X || dpL[0] >= X)return false;
	
	for (int i = 0; i < 2 * N; i++) {
		//cerr << i <<" " << dpL[i] << " " << dpR[i] << endl;
		if (dpL[i] + 1 >= dpR[i])return false;
	}
	return true;

}


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

	cin >> H >> W >> N;
	int Y, X;
	cin >> Y >> X;
	string S;
	cin >> S;
	string T;
	cin >> T;
	vector<int> SX(N);
	vector<int> SY(N);
	vector<int> TX(N);
	vector<int> TY(N);
	map<char, pair<int, int> > mp;
	mp['U'] = make_pair(-1, 0);
	mp['D'] = make_pair(1, 0);
	mp['L'] = make_pair(0, -1);
	mp['R'] = make_pair(0, 1);
	for (int i = 0; i < N; i++) {
		SY[i] = mp[S[i]].first;
		SX[i] = mp[S[i]].second;
		TY[i] = mp[T[i]].first;
		TX[i] = mp[T[i]].second;
	}


	bool f = (solve(SX, TX, W, X) && solve(SY, TY, H, Y));
	if (f) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 13464
#include <iostream>
#include <vector>

int main(){
    int32_t N;
    std::cin >> N;

    std::vector<int32_t> eatA(N);
    std::vector<int32_t> scoreB(N);
    std::vector<int32_t> bonusC(N-1);

    for(auto& i : eatA){
        std::cin >> i;
    }
    for(auto& i : scoreB){
        std::cin >> i;
    }
    for(auto& i : bonusC){
        std::cin >> i;
    }

    int32_t res = 0;
    int32_t prev = N;
    for(int32_t i = 0; i < N; i++){
        res += scoreB[eatA[i]-1];
        if(eatA[i] == (prev + 1)){
            res += bonusC[eatA[i] - 2];
        }
        prev = eatA[i];
    }

    std::cout << res;
    return 0;
}


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

void disp(vector<int>& vec) {
  cout << "[";
  for (int i = 0; i < vec.size(); i++) cout << " " << vec[i];
  cout << " ]" << endl;
}

int main(void)
{
  int N,max;

  cin >> N;
  
  vector<int> A(N);
  for(int i=0;i<N;i++) cin >> A[i];
  
  sort(A.begin(),A.end(), greater<int>() );
//  disp(A);
  
  int sum=0;
  for(int i=0; i<N; i++)
  {
    if(i%2==0)
    {
      sum += A[i];
    }
    else
    {
      sum -= A[i];
    }
  }
  cout << sum;
  
  return 0;
}

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

int main(void) {
    ll a, b, c;
    cin >> a >> b >> c;
    ll d = c - a - b;
    if (d > 0 and d * d > 4 * a * b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int data[3], x, i, j, k, stock;

  scanf("%d",&x);

  for(i = 0; i < x; i++){
    scanf("%d %d %d",&data[0],&data[1],&data[2]);

    for(j = 0; j < 2; j++){
      for(k = 1; k < 3; k++){
	if(data[j] < data[k]){
	  stock = data[j];
	  data[j] = data[k];
	  data[k] = stock;
	}
      }
    }

    if(data[0]*data[0] == data[1]*data[1] + data[2]*data[2]){
      printf("YES\n");
    }else{
      printf("NO\n");
    }


  }


  return 0;
}

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

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

    int n1=0, n2=0;
    for(int i=0; i<n; i++){
        if(n1 < a[i]){
            n2 = n1; n1 = a[i];
        }
        else if(n2 < a[i]){
            n2 = a[i];
        }
    }

    for(int i=0; i<n; i++){
        if(a[i]==n1)
            cout<<n2<<endl;
        else
            cout<<n1<<endl;
    }

    return 0;
}


Measured memory_bytes: 2432
#include <iostream>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;

int digitSum(ll num) {
  int ret = 0;
  while (num) {
    ret += num % 10;
    num /= 10;
  }
  return ret;
}

int main(void) {
  ios::sync_with_stdio(false);
  int M;
  cin >> M;

  ll Ans = 0;
  ll tmp = 0;
  rep(i, M) {
    ll d, c;
    cin >> d >> c;
    Ans += c;
    tmp += d * c;
  }
  Ans += ((tmp - 1) / 9);
  Ans--;
  cout << Ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
double w, h, x, y;

ll pow(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2)
	{
		return pow(x, y - 1) * x % mod;
	}
	else
	{
		ll yyy = pow(x, y / 2);
		return yyy * yyy % mod;
	}
}

ll div(ll x)
{
	return pow(x, mod - 2);
}

int main(void)
{
	cin >> w >> h >> x >> y;
	cout << w * h / 2 << ' ';
	if (x * 2 == w && y * 2 == h)
	{
		cout << 1 << endl;
	}
	else
	{
		cout << 0 << endl;
	}
	int www;
	cin >> www;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define y_n(ans) cout<<(ans?"Yes":"No")<<endl;

int main() {
    int ans;
    for (int i=0; i<5; ++i) {
        int n; cin >> n;
        if (n == 0) ans = i+1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, i, j, k, x;
	cin >> n;
	vector<int> ct(3, 0);
	for (i = 0; i < n; i++) {
		cin >> x;
		if (x % 4 == 0) ct[2]++;
		else if (x % 2 == 0) ct[1]++;
		else ct[0]++;		
	}

	bool ans = false;
	if (ct[2] >= ct[0]) ans = true;
	else if ((ct[2] == ct[0] - 1) && (ct[1] == 0)) ans = true;

	if (ans) cout << "Yes\n";
	else cout << "No\n";

	return 0;
}



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

int main() {
	int a, b;
	cin >> a >> b;
	vector<int> ans;
	ans.push_back(a+b);
	ans.push_back(a-b);
	ans.push_back(a*b);
	sort(ans.begin(), ans.end());
	cout << ans.back() << endl;
	return 0;
}



Measured memory_bytes: 256
n=int(input())

li=[list(map(int,input().split())) for i in range(n)]
li.insert(0,[0,0,0])
#print(li)

for i in range(n) :
  cr=li[i]
  nx=li[i+1]
  dist=abs(nx[1]-cr[1])+abs(nx[2]-cr[2])
  dt=nx[0]-cr[0]
  if dt<dist :
    print("No")
    exit()
  if (dt%2) != (dist%2) :
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 27380
using System;
using System.Collections.Generic;

class Program
{
	static void Main(string[] args)
	{
		string t = Console.ReadLine();
		long N = long.Parse(t);
		string[] s = Console.ReadLine().Split(' ');
		long [] A = new long[N];
		for(var i=0;i<N;i++){
			A[i] = long.Parse(s[i]);
		}
		long count = 0;
		Dictionary<long, long> dic = new Dictionary<long, long>();
		dic[0] = 1;
		long sum = 0;
		for(var i=0;i<N;i++){
			sum += A[i];
			bool b = dic.ContainsKey(sum);
			if(b){
				count += dic[sum];
				dic[sum] += 1;
			} else {
				dic[sum] = 1;
			}
		}
		Console.WriteLine(count);
	}
}

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

int main(){
    string w;
    string t;
    cin >> w;
    int i;
    for(i = 0;i < w.size(); i++) {
        if('A' <= w[i] && w[i] <= 'Z') w[i] += 'a' - 'A';
    }
    int o = 0;
    cin >> t;
    while(t != "END_OF_TEXT"){
        for(i = 0;i < t.size(); i++) {
            if('A' <= t[i] && t[i] <= 'Z') t[i] += 'a' - 'A';
        }
        if(w == t) o++;
        cin >> t;
    }
    cout << o << endl;
}


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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <class T, class U>
void chmax(T &a, U b) {
    if (a < b) a = b;
}
template <class T, class U>
void chmin(T &a, U b) {
    if (b < a) a = b;
}

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

int dp[10001][2][101];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    string K;
    ll D;
    cin >> K >> D;
    dp[0][1][0] = 1;
    rep(i, K.size()) {
        int x = K[i] - '0';
        rep(j, 2) {
            for (int d = 0; d <= (j == 1 ? x : 9); d++) {
                rep(d2, D) {
                    dp[i + 1][(j == 1 and d == x)][(d + d2) % D] += dp[i][j][d2];
                    dp[i + 1][(j == 1 and d == x)][(d + d2) % D] %= mod;
                }
            }
        }
    }
    // rep(i, K.size() + 1) rep(j, 2) rep(k, D) {
    //     cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
    // }
    cout << (dp[K.size()][0][0] + dp[K.size()][1][0] - 1 + mod) % mod << endl;
    return 0;
}


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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) (int)((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	//~ cout.tie(0);
	int k, n;
	scanf("%d%d", &k, &n);
	vi a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);

	int ans = k;
	for (int i = 0; i < n; i++) {
		int x;
		if (i == 0)
			x = a[n-1] - a[0];
		else
			x = k + a[i-1] - a[i];
		ans = min(ans, x);
	}
	printf("%d\n", ans);
}


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

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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  
  int answer = 0;
  
  for (int i = 1; i <= N; i++) {
      int sim = sum(i);
      if (sim >= A && sim <= B) {
        answer += i;
      }
  }
  cout << answer << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MOD 1000000007
#define f(i,a,n) for(lli i = a; i < n; i++)
#define pb push_back
#define mp make_pair

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

// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    lli r,d,a;
    cin>>r>>d>>a;
    lli arr[11];
    arr[0]=a;
    for(int i=1;i<=10;i++)
    {
    	arr[i]=r*arr[i-1]-d;
    	cout<<arr[i]<<endl;
    }
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
#define ll long long
#define ld long double
using namespace std;

int main() {
	ll N, K;
	cin >> N >> K;
	vector<int> a(N), prev(200005, -1), mae(N, -1), nns;
	for(int i=0; i<N; ++i){
	    cin >> a[i];
	    if(prev[a[i]]>=0) mae[i]=prev[a[i]];
	    else nns.push_back(i);
	    prev[a[i]]=i;
	}
	for(int i=0; i<nns.size(); ++i){
	    mae[nns[i]]=prev[a[nns[i]]];
	}
	ll cyc=1, now=N;
	vector<int> made;
	while(now>0){
	    --now;
	    bool flag=(now<=mae[now]);
	    now=mae[now];
	    if(flag){
	        made.push_back(now);
	        ++cyc;
	    }
	}
	//cout << cyc << endl;
	K %= cyc;
	if(K==0){
	    cout << endl;
	    return 0;
	}
	K=cyc-K-1;
	vector<int> sel, jump(200005, -1);
	for(int i=made[K]; i<N; ++i){
	    if(jump[a[i]]<0 || jump[a[i]]>=sel.size()){
	        jump[a[i]]=sel.size();
	        sel.push_back(a[i]);
	    }else if(sel[jump[a[i]]]!=a[i]){
	        jump[a[i]]=sel.size();
	        sel.push_back(a[i]);
	    }else{
	        sel.erase(sel.begin()+jump[a[i]], sel.end());
	        jump[a[i]]=-1;
	    }
	}
	for(int i=0; i<sel.size(); ++i){
	    if(i==0) cout << sel[i];
	    else cout << ' ' << sel[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 7156
#include <bits/stdc++.h>
using namespace std;
bool even(string S, int l, int r) {
  for (int i = l; i+(r-l+1)/2 <= r; i++) {
    if (S[i] != S[i+(r-l+1)/2]) return false;
  }
  return true;
}
int main() {
  string S;
  int answer=0;
  cin >> S;
  for (int i = 0; i < S.length(); i++) {
    for (int j = S.length()-1; j > i; j--) {
      if ((j-i)%2 && j-i != S.length()-1 && even(S,i,j)) {
        answer=max(answer,j-i+1); 
      }
    }
  }
  cout << answer;
}

Measured memory_bytes: 3632
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  ll n, y, k;
  cin >> n >> y;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      if ((y - 10000 * i - 5000 * j) % 1000 == 0) {
        k = (y - 10000 * i - 5000 * j) / 1000;
      }
      if (i + j + k == n && k >= 0) {
        cout << i << " " << j << " " << k << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}

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

using namespace std;

int n, k;
long long dp[100005];
int h[100005];
const long long INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


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

    for (int i = 0; i < 100005; ++i) dp[i]=INF;
    dp[0] = 0;

    for(int i=1;i<n;i++){
        // printf("at %d, abs: %d \n", i, abs(h[i]-h[i-1]));
        for(int j=1;j<=k;j++){
            if((i-j) >= 0){
                chmin(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
            }
        }
    }

    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1408
n,m=map(int,input().split())
h=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(m)]
c=0
pair = [[] for _ in range(n)]
for i in a:
    pair[i[0]-1].append(i[1]-1)
    pair[i[1]-1].append(i[0]-1)
for i in range(n):
    for hi in pair[i]:
        if h[i]<=h[hi]:
            break
    else:
        c+=1
print(c)

Measured memory_bytes: 106644
use proconio::{fastout, input};
use std::cmp;

macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

const N_MAX: usize = 1e5 as usize;
const INF: i32 = std::i32::MAX;

#[fastout]
fn main() {
    input!{
        n: usize,
        k: usize,
        h: [i32; n],
    }

    let mut dp = [INF; N_MAX];
    dp[0] = 0;
    dp[1] = (h[0] - h[1]).abs();

    for i in 2..n {
        for m in 1..cmp::min(i+1, k+1) {
            chmin!(dp[i], dp[i - m] + (h[i] - h[i - m]).abs());
        }
    }

    println!("{}", dp[n-1]);
}


Measured memory_bytes: 3288
S= list(input())
a=[]
for i in range(0,len(S)):
  if i%2==0:
    if S[i]=="R" or S[i] == "U" or S[i]=="D":
      a.append(1)
  elif i%2!=0:
    if S[i]=="L" or S[i]=="U" or S[i]=="D":
      a.append(1)
if len(S)==sum(a):
  print("Yes")
else:
  print("No")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
vector<int>g[100005];
int vis[100005],c[100005];
queue<int>q;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vis[1]=1;
	vis[n]=1;
	c[1]=0;
	c[n]=1;
	q.push(1);
	q.push(n);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		int xx=c[x];
		for(int i=0;i<g[x].size();i++)
		{
			int t=g[x][i];
			if(!vis[t])
			{
				c[t]=xx;
				vis[t]=1;
				q.push(t);
			}
		}
	}
	int s1=1,s2=1;
	for(int i=1;i<=n;i++)if(c[i])s1++;else s2++;
	if(s1<s2)printf("Fennec\n");else printf("Snuke\n");
	return 0;
}

Measured memory_bytes: 6656
let N = stdin.ReadLine() |> int
let a = stdin.ReadLine().Split(' ') |> Array.map int |> Array.sort |> Array.rev

let sum_odd = Array.mapi (fun i v -> if i%2=0 then 0 else v) a |> Array.sum
let sum_even =  Array.sum a - sum_odd

printfn "%d" (sum_even - sum_odd)


Measured memory_bytes: 14812
import sys
import collections
import itertools
import math
import re
from collections import deque

MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

N, K = [int(x) for x in input().split()]

H = [None] * N

for i in range(N):
    h = int(input())
    H[i] = h

H.sort()

mi = 10 ** 12
for i in range(0, N - K + 1):
    h1 = H[i + K - 1]
    h2 = H[i]

    mi = min(mi, h1 - h2)

print(mi)


Measured memory_bytes: 7984