akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int n,m;
int V; // number of Vertex
int s,G;// number of start
vector<pii>g[10000]; // first: to second: cost
vi d(1000,INF); // start->index  mminimum distance
void dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii>>que;
    d[s]=0;
    que.push(pii(0,s));
    while(!que.empty()){
    pii now=que.top(); que.pop();
        int v=now.second;
        if(d[v]<now.first)continue;
        for(int i=0; i<g[v].size();i++){
            pii e=g[v][i];
            if(d[e.first]>d[v]+e.second){
                d[e.first]=d[v]+e.second;
                que.push(pii(d[e.first],e.first));
            }
        }
    }
}
int main(){
    cin>>V>>m;
    rep(i,m){
        int to,from,tiya,rize;
        char gomi; cin>>from>>gomi>>to>>gomi>>tiya>>gomi>>rize;
        g[from].push_back(pii(to,tiya));
        g[to].push_back(pii(from,rize));
    }
    int gotiusa,amausa;
    char gomi;
    cin>>s>>gomi>>G>>gomi>>gotiusa>>gomi>>amausa;
    dijkstra();
    int rize=d[G];
    int hoge=s;
    swap(s,G);
    vi yebi(1000,INF);
    d=yebi;
    dijkstra();
    cout<<gotiusa-amausa-rize-d[G]<<endl;
}

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

#define debug(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

int getid(const std::vector<int>& v, int x) {
    int id = std::lower_bound(v.begin(), v.end(), x) - v.begin();
    return id != v.size() && v[id] == x ? id : -1;
}

int main() {
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    --a, --b;

    std::vector<Point> points;
    std::vector<int> px, py;

    for (int i = 0, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        points.emplace_back(x + y, x - y);
        px.push_back(x + y);
        py.push_back(x - y);
    }

    std::sort(px.begin(), px.end());
    std::sort(py.begin(), py.end());
    px.erase(std::unique(px.begin(), px.end()), px.end());
    py.erase(std::unique(py.begin(), py.end()), py.end());

    int h = px.size(), w = py.size();
    std::vector<std::vector<std::pair<int, int>>> vx(h), vy(w);
    std::vector<std::set<std::pair<int, int>>> sx(h), sy(w);

    for (int i = 0; i < n; i++) {
        sx[getid(px, points[i].x)].emplace(points[i].y, i);
        sy[getid(py, points[i].y)].emplace(points[i].x, i);
        vx[getid(px, points[i].x)].emplace_back(points[i].y, i);
        vy[getid(py, points[i].y)].emplace_back(points[i].x, i);
    }

    for (auto& v : vx) {
        std::sort(v.begin(), v.end());
    }
    for (auto& v : vy) {
        std::sort(v.begin(), v.end());
    }

    int d = std::max(std::abs(points[a].x - points[b].x),
                     std::abs(points[a].y - points[b].y));

    long long ans = 0;

    std::queue<int> q;
    q.push(a);

    auto erase = [&](int id) {
        sx[getid(px, points[id].x)].erase(std::make_pair(points[id].y, id));
        sy[getid(py, points[id].y)].erase(std::make_pair(points[id].x, id));
    };

    erase(a);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        auto gao = [&](int id, int l, int r, bool d) -> int {
            if (id == -1) return 0;

            auto& v = d ? vy[id] : vx[id];
            auto& s = d ? sy[id] : sx[id];

            for (auto it = s.lower_bound(std::make_pair(l, 0));
                 it != s.end() && it->first <= r; ) {
                int v = it->second;
                q.push(v);
                ++it;
                erase(v);
            }
            return std::lower_bound(v.begin(), v.end(),
                                    std::make_pair(r, INT_MAX)) -
                   std::lower_bound(v.begin(), v.end(), std::make_pair(l, 0));
        };

        int lx = points[u].x - d, rx = points[u].x + d;
        int ly = points[u].y - d, ry = points[u].y + d;

        ans += gao(getid(px, lx), ly, ry - 1, 0);
        ans += gao(getid(px, rx), ly + 1, ry, 0);
        ans += gao(getid(py, ly), lx + 1, rx, 1);
        ans += gao(getid(py, ry), lx, rx - 1, 1);
    }

    printf("%lld\n", ans >> 1);
}


Measured memory_bytes: 28920
import java.io.*;

import java.math.BigInteger;
import java.util.*;

import java.util.ArrayList;

import java.util.Scanner;


public class Main {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static final int mod = 1000000007;

    public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        HashMap<Integer,Integer>hm=new HashMap<>();
        for(int j=0;j<n;j++)
            hm.put(j+1,1);
        for(int j=0;j<k;j++)
        {
            int d=sc.nextInt();
            for(int l=0;l<d;l++)
            {
                int m=sc.nextInt();
                if(hm.get(m)!=null)
                    hm.remove(m);

            }
        }
        System.out.println(hm.size());


    }
}









Measured memory_bytes: 46324
typedef long long ll;

#define shi5 100000+10
#define MOD 1000000007

#include <bits/stdc++.h>
using namespace std;
struct mystruct{
  long long v;
  mystruct * next;
};
int structcmp(const void *v1,const void *v2){return ((mystruct *)v1)->v - ((mystruct *)v2)->v;}
int intcmp(const void *v1,const void *v2){return *(int *)v1-*(int *)v2;}
long long minn(long long v1,long long v2){return v1<v2?v1:v2;}
long long maxx(long long v1,long long v2){return v1>v2?v1:v2;}
int main(){
  char a,b;
  cin>>a>>b;
  if(a<b){
    cout<<"<"<<endl;
  }else if(a>b){
    cout<<">"<<endl;
  }else{
    cout<<"="<<endl;
  }
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> V(N);
  vector<int> C(N);
  vector<int> A(N);
  int count = 0;
  for(int i = 0; i < N; i++) {
    cin >> V.at(i);
  }
  for(int i = 0; i < N; i++) {
    cin >> C.at(i);
  }
  for(int i = 0; i < N; i++) {
    A.at(i) = V.at(i) - C.at(i);
    if(A.at(i) > 0) {
      count = count + A.at(i);
    }
  }
  cout << count << endl;
  
}


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

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[] d = new int[N];
        for (int i = 0; i < N; i++) {
            d[i] = scan.nextInt();
        }
        Arrays.sort(d);
        int ans = Integer.MAX_VALUE;
        for (int i = d[0]; i <= d[N-1]; i++) {
            int cost = 0;
            for (int j = 0; j < N; j++) {
                cost += (d[j] - i) * (d[j] - i);
            }
            ans = Math.min(ans,cost);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define elif else if
#define ffast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);



int main()
{
    ffast;
    //freopen("0in.txt","r",stdin);
    //freopen("0out.txt","w",stdout);

    long long n,ans=0;
    cin>>n;

    if(n>=500)
    {
        ans += (n/500)*1000;
        n = n%500;
    }
    if(n>=5){
        ans += (n/5)*5;
    }
    cout<<ans<<endl;

    return 0;
}





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

using namespace std;

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

  long long n;
  int ans = 0;

  scanf("%lld", &n);
  for (int x = 1; x <= 9; ++x) {
    if (x > n) {
      break;
    }

    long long m = x;
    int sum = x;
    while (m * 10 + 9 <= n) {
      m = m * 10 + 9;
      sum += 9;
    }
    
    ans = max(ans, sum);
  }

  printf("%d\n", ans);
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (A, B) = readLine()!!.split(" ").map{it.toLong()}

    println(lcm(A, B))
}

/**
 * Calculate the greatest common divisor of `x` and `y` with Euclidean algorithm
 */
private tailrec fun gcd(x: Long, y: Long): Long = if (y == 0L) x else gcd(y, x % y)

private fun lcm(x: Long, y: Long): Long = x / gcd(x, y) * y


Measured memory_bytes: 37820
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main{
  public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] strArray;
		strArray = br.readLine().split("\\s");
		System.out.println(Integer.parseInt(strArray[0]) * Integer.parseInt(strArray[1]) +  " " + (Integer.parseInt(strArray[0]) + Integer.parseInt(strArray[1])) * 2);
	}
}

Measured memory_bytes: 16892
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include<math.h>
#define loop(i, l, r) for(i=l; i<r; i++)/*Instead of function, (for).*/
#define rep(i,r) for(i=0; i<r; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long int lli;
/*Return Combination ,(nCr)*/
int combi(int n, int r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
/*Return gcd(a, b)*/
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}
int main(void)
{
	int n, i, k=0;
	scanf("%d", &n);
	int p[n];
	rep(i,n) scanf("%d", &p[i]);

	rep(i,n){
		if(p[i] != i+1) k++;
	}
	if(k == 0 || k == 2) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
typedef long long ll;
#define INF 100000000
#define MOD 100000007
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b and b==c and c==a){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    n = max(A)

    primes = set(A)
    for ind,i in enumerate(A):
        primes.difference_update(range(i*2, n+1, i))
        if ind>=1:
            if A[ind]==A[ind-1]:
                primes -= {i}
    print(len(primes))



if __name__ == '__main__':
    main()

Measured memory_bytes: 32272
n, x = map(int, input().split())
s = [1]
for i in range(n):
    s.append(s[i] * 2 + 3)
p = [1]
for i in range(n):
    p.append(p[i] * 2 + 1)
    
def f(n,x):
    if n >= 1:
        if 0 < x <= 1:
            return 0
        if 1 < x <= s[n-1]+1:
            return f(n-1,x-1)
        if x == s[n-1]+2:
            return p[n-1] + 1
        if s[n-1]+2 < x <= s[n]-1:
            return p[n-1] + 1 + f(n-1,x-s[n-1]-2)
        if x == s[n]:
            return 2*p[n-1] + 1
    if n == 0:
        if x == 1:
            return 1
        if x == 0:
            return 0
          
print(f(n,x))

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

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

  if(x < 30){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }


}


Measured memory_bytes: 3628
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
A, B, C, D = map(int, input().split())
E = C * D // gcd(C, D)
x = A - 1 - (A - 1) // C - (A - 1) // D + (A - 1) // E
y = B - B // C - B // D + B // E
print(y - x)

Measured memory_bytes: 3060
let n = stdin.ReadLine() |> int
let (a:int[]),(xyPairs:(int*int)[][]) =
    let rec inicialize aList xyPairs i =
        if i = n then (aList|>List.rev|>List.toArray, xyPairs|>List.rev|>List.toArray)
        else
        let a = stdin.ReadLine() |> int
        let aList = a :: aList
        let xyEachPairs = [| for _ in 1..a -> stdin.ReadLine().Split() |> fun [|x1;x2|]->(int x1 - 1, int x2) |]
        let xyPairs = xyEachPairs :: xyPairs
        inicialize aList xyPairs (i+1)
    inicialize [] [] 0 

// Nが小さいので2^Nパターン列挙して最大値を求める
let allPatern = 
    [((1<<<n)-1).. -1 .. 0] 
    |> Seq.map (fun k -> 
        [| let mutable k = k
        for i in 1..n do
            yield k % 2
            k <- k / 2 |])
    |> Seq.sortByDescending (fun array -> array |> Array.filter (fun x -> x = 1) |> Array.length)

let detect (patern:int[]) =
    let getIResult i x =
        if x = 0 then true
        else 
            xyPairs.[i]
            |> Seq.map (fun (x,y) -> patern.[x] = y)
            |> Seq.forall (fun x -> x = true)
        
    patern
    |> Seq.mapi (getIResult)
    |> Seq.forall (fun x -> x )

allPatern |> Seq.find detect |> Array.filter (fun x -> x = 1) |> Array.length |> stdout.WriteLine

Measured memory_bytes: 26684
#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>

using namespace std;

const long long N = 3e5 + 5;
long long n, a, b, k;
long long ans = 0;
const long long mod = 998244353;
long long fac[N];

long long power(long long a, long long b)
{
	if (b == 0)
	{
		return 1ll;
	}
	long long ans = power(a, b / 2);
	ans = ans * ans;
	ans = ans % mod;
	if (b % 2 == 1)
	{
		ans = ans * a;
		ans = ans % mod;
	}
	return ans;
}

long long choose(long long a, long long b)
{
	long long ans = fac[a];
	ans = ans * power(fac[b], mod - 2);
	ans = ans % mod;
	ans = ans * power(fac[a - b], mod - 2);
	ans = ans % mod;
	return ans;
}

int main() 
{
	fac[0] = 1;
	for (long long i = 1; i < N; i++)
	{
		fac[i] = fac[i - 1] * i;
		fac[i] = fac[i] % mod;
	}
	cin >> n >> a >> b >> k;
	for (long long i = 0; i * a <= k && i <= n; i++)
	{
		if ((k - i * a) % b != 0)
			continue;
		long long red = (k - i * a) / b;
		if (red <= n)
		{
			ans += choose(n, i) * choose(n, red);
			ans = ans % mod;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 2688
import sys
def input():
  return sys.stdin.readline().rstrip()

def rec(i,a,b,c):
  if i==N:
    if a==0 or b==0 or c==0:
      return 10**12
    return abs(a-A)+abs(b-B)+abs(c-C)

  res=rec(i+1,a,b,c);

  res=min(res,rec(i+1,a+l[i],b,c)+(10 if a else 0))
  res=min(res,rec(i+1,a,b+l[i],c)+(10 if b else 0))
  res=min(res,rec(i+1,a,b,c+l[i])+(10 if c else 0))

  return res

N,A,B,C=map(int,input().split())
l=[int(input()) for _ in range(N)]

print(rec(0,0,0,0))


Measured memory_bytes: 73580
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
tot = abs(A[1])
for i in range(2,N+1):
    tot += abs(A[i]-A[i-1])
tot += abs(A[N])
for i in range(1,N):
    a = tot-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1])
    print(a)
a = tot-abs(A[N]-A[N-1])-abs(A[N])+abs(A[N-1])
print(a)

Measured memory_bytes: 83352
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int n, l;
    cin >> n >> l;
    string s[100];
    for (int i = 0; i < n; i++)
        cin >> s[i];
    
    sort(s, s + n);
    for(int i = 0; i < n; i++)
        cout << s[i];
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
int main(void){
    string a;
    std::cin >> a;
    if(a == "SUN"){
        std::cout << 7 << std::endl;
    }
    if(a == "MON"){
        std::cout << 6 << std::endl;
    }
    if(a == "TUE"){
        std::cout << 5 << std::endl;
    }
    if(a == "WED"){
        std::cout << 4 << std::endl;
    }
    if(a == "THU"){
        std::cout << 3 << std::endl;
    }
    if(a == "FRI"){
        std::cout << 2<< std::endl;
    }
    if(a == "SAT"){
        std::cout << 1 << std::endl;
    }
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,m,hh,kk):
        e = collections.defaultdict(list)
        for _ in range(m):
            a,b,c,h,r = LI()
            e[a].append((b,c,h,r))
            e[b].append((a,c,h,r))
        ss,tt = LI()
        p = I()
        ps = []
        ii = [2**i for i in range(kk+1)]
        for _ in range(p):
            t = LI()
            d = t[1]
            ks = 0
            for i in t[2:]:
                ks += ii[i]
            ps.append((ks,d))
        pd = collections.defaultdict(lambda: inf)
        pd[0] = 0
        for ks, d in ps:
            for ts, td in list(pd.items()):
                ns = ks | ts
                nd = td + d
                if pd[ns] > nd:
                    pd[ns] = nd
        r = inf
        for ts, td in pd.items():
            ks = set()
            if td >= r:
                continue
            for i in range(kk+1):
                if ts & ii[i]:
                    ks.add(i)

            def search():
                d = collections.defaultdict(lambda: inf)
                d[(ss,0)] = 0
                q = []
                heapq.heappush(q, (0, (ss,0)))
                v = collections.defaultdict(bool)
                while len(q):
                    k, u = heapq.heappop(q)
                    if v[u]:
                        continue
                    v[u] = True
                    if u[0] == tt:
                        return k

                    for uv, ud, uh, ur in e[u[0]]:
                        if u[1] + uh > hh:
                            continue
                        vv = (uv, u[1] + uh)
                        if v[vv]:
                            continue
                        vd = k
                        if ur not in ks:
                            vd += ud
                        if d[vv] > vd:
                            d[vv] = vd
                            heapq.heappush(q, (vd, vv))

                return inf

            tr = search()
            if r > tr + td:
                r = tr + td
            if r == inf:
                break

        if r == inf:
            return -1

        return r

    while 1:
        n,m,h,k = LI()
        if n == 0:
            break
        rr.append(f(n,m,h,k))
        # print('nr',n,rr[-1])

    return '\n'.join(map(str, rr))


print(main())



Measured memory_bytes: 10072
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int main(){
	ll k,n,a[maxn],d[maxn];
	scanf("%lld%lld",&k,&n);
	memset(d,0,sizeof(d));
	for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i]);
		if(i >= 2) d[i] = a[i] - a[i - 1];
	}
	d[1] = a[1] + k - a[n];
	ll mx = -1;
	ll sum = 0;
	for(int i = 1;i <= n;i++){
		sum += d[i];
		mx = max(mx,d[i]);
	}
	sum -= mx;
	printf("%lld\n",sum);
	return 0;
}

Measured memory_bytes: 3960
use std::io;
use std::cmp::Ordering;

fn main() {
    let n = read_one::<usize>();
    let mut an = read::<usize>();
    let bn = read::<usize>();
    let mut cn = read::<usize>();
    an.sort();
    cn.sort();

    let mut ans: usize = 0;
    for b in bn.iter() {
        ans += an.lower_bound(b) * (n - cn.upper_bound(b));
    }

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


trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    /// returns the minimum index s.t. array[index] >= x
    ///
    /// ```rust
    /// let array = vec![2, 2, 5, 5, 9];
    /// assert_eq!(array.lower_bound(&2), 0);
    /// assert_eq!(array.lower_bound(&4), 2);
    /// assert_eq!(array.lower_bound(&5), 2);
    /// assert_eq!(array.lower_bound(&7), 4);
    /// assert_eq!(array.lower_bound(&100), 5);
    /// ```
    fn lower_bound(&self, x: &T) -> usize {
        let mut l = 0;
        let mut r = self.len();

        while l != r {
            let m = (l + r) / 2;
            match self[m].cmp(x) {
                Ordering::Less => { l = m + 1; },
                _ => { r = m; }
            }
        }
        l
    }

    /// returns the minimum index s.t. array[index] > x
    /// ```rust
    /// let array = vec![2, 2, 5, 5, 9];
    /// assert_eq!(array.upper_bound(&2), 2);
    /// assert_eq!(array.upper_bound(&4), 2);
    /// assert_eq!(array.upper_bound(&5), 4);
    /// assert_eq!(array.upper_bound(&7), 4);
    /// assert_eq!(array.upper_bound(&100), 5);
    /// ```
    fn upper_bound(&self, x: &T) -> usize {
        let mut l = 0;
        let mut r = self.len();
        while l != r {
            let m = (l + r) / 2;
            match self[m].cmp(x) {
                Ordering::Greater => { r = m; },
                _ => { l = m + 1; },
            }
        }
        l
    }
}

#[allow(unused)]
fn read<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}


#[allow(unused)]
fn read_one<T>() -> T
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 5840
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
typedef long long int ll;
using namespace std;
#define FOR(i,a,n) for(int i=(ll)a;i<(ll)n;++i)
#define TFOR(i,n)FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
const int INF = 1LL << 30;
const ll LLINF = 1LL << 60;
int main() {
	string s;
	cin >> s;
	s.insert(4, " ");
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
// const int mod = 1e9 + 7;
// const int mod = 998244353;

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int w[1010], s[1010], v[1010];
int id[1010];
LL f[20010];
int n;

inline void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> s[i] >> v[i];
    }
    iota(id + 1, id + n + 1, 1);
    sort(id + 1, id + n + 1, [](int u, int v) {return w[u] + s[u] < w[v] + s[v];});
    for (int i = 1; i <= n; ++i) {
        for (int j = w[id[i]] + s[id[i]]; j >= w[id[i]]; --j) {
            f[j] = max(f[j], f[j - w[id[i]]] + v[id[i]]);
        }
    }
    cout << *max_element(f, f + w[id[n]] + s[id[n]] + 1) << "\n";
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    work();
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, a, b, k;
  cin >> n >> a >> b >> k;
  auto pow = [&](long long x, int p) {
    x %= MOD;
    long long y = 1;
    while (p) {
      if (p & 1) {
        y = x * y % MOD;
      }
      x = x * x % MOD;
      p >>= 1;
    }
    return y;
  };
  vector<long long> fact(n + 1), facti(n + 1);
  fact[0] = 1, facti[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fact[i] = fact[i - 1] * i % MOD;
    facti[i] = pow(fact[i], MOD - 2);
  }
  long long ans = 0;
  for (long long x = 0; x <= n; ++x) {
    long long y = (k - a * x) / b;
    if ((k - a * x) % b == 0 && n >= y && y >= 0) {
      long long sub = fact[n];
      sub = sub * fact[n] % MOD;
      sub = sub * facti[x] % MOD;
      sub = sub * facti[y] % MOD;
      sub = sub * facti[n - x] % MOD;
      sub = sub * facti[n - y] % MOD;
      ans = (ans + sub) % MOD;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4992
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

        int min = Integer.MAX_VALUE;
        int countNegatives = 0;
        long sum = 0;
        for (int num : nums) {
            int abs = Math.abs(num);
            sum += abs;
            min = Math.min(min, abs);
            if (num < 0) {
                countNegatives++;
            }
        }

        System.out.println(countNegatives % 2 == 0 ? sum : sum - (min*2));
    }
}

Measured memory_bytes: 50124
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int N, M;
	cin >> N >> M;

	priority_queue<int> q;
	rep(i, N) {
		int a;
		cin >> a;
		q.push(a);
	}

	rep(i, M) {
		int p = q.top();
		q.pop();
		q.push(p / 2);
	}

	ll kotae = 0;
	rep(i, N) {
		kotae += q.top();
		q.pop();
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <deque>
using namespace std;
using P = pair<int,int>;
typedef long long int ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)

int main(){ 
    ll h,w;cin >> h >> w;
    if(w==1 || h==1){
		cout << 1 << endl;
      	return 0;
    }

    if(w%2==0){
        cout<<(w/2)*h <<endl;
    }else{
        cout << ((w/2)+1)*h-(h/2)<<endl;
    }
    return 0;
}




Measured memory_bytes: 256
import sys
import re

# S' カギとなる文字列
s = input()

# T 含まれる文字列
t = input()

s = s.replace("?", ".")

# 文字列を反転
s = s[::-1]
t = t[::-1]

match = False
for i in range(len(s)-len(t)+1):
    st = s[i:i+len(t)]
    if len(st) < len(t):
        break
    pattern = re.compile(r"%s" % st)
    if re.match(pattern, t):
        match = True
        break

if match:
    cut = i + len(t)
    return_string = s[:i] + t + s[cut:]
    return_string = return_string.replace(".", "a")
    return_string = return_string[::-1]
    print(return_string)
else:
    print("UNRESTORABLE")

Measured memory_bytes: 3188
"""    Arnab Chanda    """

from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7


a,b,c = multi_int_input()
ki = int_input()
flag = 0

for i in range(ki+1):
    for j in range(ki+1):
        for k in range(ki+1):
            # print(i,j,k)
            if ((i+j+k) <= ki):
                # print(i, j, k, c*pow(2,k), b*pow(2,j), a*pow(2,i))
                if ((c*pow(2,k) > b*pow(2,j)) and (b*pow(2,j) > a*pow(2,i))):
                    flag  = 1

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

Measured memory_bytes: 9624
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B
import Data.Char

toTuple :: B.ByteString -> (Int, Int)
toTuple bs =
    let
        Just (a, bs') = B.readInt bs
        Just (b, _) = B.readInt $ B.dropWhile isSpace bs'
    in
        (a, b)

step :: (Bool, Int) -> Char -> (Bool, Int)
step (b, c) x
    | x == 'A' = (True, c)
    | b && (x == 'C') = (False, c+1)
    | otherwise = (False, c)

main = do
    [n,q] <- map read . words <$> getLine
    xs <- VU.fromList . B.unpack <$> B.getLine :: IO (VU.Vector Char)
    fts <- VU.replicateM q (toTuple <$> B.getLine) :: IO (VU.Vector (Int, Int))
    let xs' = VU.map snd $ VU.scanl' step (False,0) xs
    VU.forM_ fts $ \(f,t) -> do
        print $ (xs' VU.! t) - (xs' VU.! f) 

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

int gcd(int a, int b)  // positive number only.
{
    int r = a % b;
    if(r == 0) return b;
    return gcd(b, r);
}

int main()
{
    int i, n, *A;
    int lcm, g;
    scanf("%d", &n);
    A = new int [n];

    scanf("%d", &A[0]); lcm = A[0];
    for(i = 1; i < n; i++){
        scanf("%d", &A[i]);
        if(lcm < A[i]){ g = gcd(A[i], lcm); }else{ g = gcd(lcm, A[i]); }
        lcm = (lcm * A[i]) / g;
    }
		
    printf("%d\n", lcm);

    return 0;
}

Measured memory_bytes: 1192
import java.util.Arrays;
import java.util.Collections;
import java.util.*;
class Main
{
	public static void main (String[] args)
	{
		Scanner sc=new Scanner(System.in); 
		int t,i;	
		int n=sc.nextInt();
		int k=sc.nextInt();
		int h[]=new int[n];
		for(i=0;i<n;i++)
			h[i]=sc.nextInt();
		int dp[]=new int[n];
		Arrays.fill(dp, 0);
		dp[0]=0;
		int ans=0;
		for(i=1;i<n;i++)
		{
			int min=Integer.MAX_VALUE;
			for(int j=i-k;j<i;j++)
			{
				if(j<0)
					continue;
				min=Math.min(min, dp[j]+Math.abs(h[j]-h[i]));
			}
			dp[i]=min;
		}
		System.out.println(dp[n-1]);
	}
}

Measured memory_bytes: 59636
/* * time: v2018-09-29_17.44.56

*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define dd double
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair

int main()
{
	string a;
	cin >> a;
	for(int i=0;i<a.length();i++)
		if(a[i] == '1')
			cout << '9';
		else
			cout << '1';

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

Measured memory_bytes: 256
n = int(input())
lis = []
for i in range(n - 1):
    lis.append(list(map(int, input().split())))
for j in range(n):
    now = 0
    for i in range(j, n - 1):
        if now < lis[i][1]:
            now += lis[i][1] - now + lis[i][0]
        else:
            if now % lis[i][2] == 0:
                now += lis[i][0]
            else:
                now += lis[i][2] - (now % lis[i][2]) + lis[i][0]
    print(now)


Measured memory_bytes: 3188
#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<sstream>
using namespace std;
#define MOD 1000000007
#define ll long long
const long long INF = 1LL << 60;

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;
}

class UnionFind {
	vector<int> data;
public:
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};


int find(vector<long long> &arr, long long obj) {
	if (arr[arr.size() - 1] < obj)return arr.size()-1;
	if (arr[0] > obj)return -1;

	int min = 0; int max = arr.size() - 1;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[min+(max-min) / 2] > obj) {
			max = min + (max - min) / 2;
		}
		else {
			min = min + (max - min) / 2;
		}
		if (max - min == 1) {
			return min;
		}
	}


}

void divisor(ll n,vector<ll> &ret) {
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(ret.begin(), ret.end());
	
}//約数求める

ll dp[210][100010];
ll kaijou(int n) {
	ll temp = 1;
	for (int i = 2; i <= n; i++) {
		temp *= i;
		temp %= MOD;
	}
	return temp;
}

int main() {
	ll N, X;
	cin >> N >> X;
	vector<ll> s(N);
	for (int i = 0; i < N; i++) {
		cin >> s[i];
	}
	sort(s.begin(), s.end(), greater<int>());

	dp[0][X] = 1;
	for (int i = 0; i <N; i++) {
		for (int j = 0; j <=X; j++) {
			
			dp[i + 1][j%s[i]] += dp[i][j] % MOD;
			dp[i + 1][j] += ((N - i-1)*dp[i][j]) % MOD;
			dp[i+1][j] %= MOD;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= X; i++) {
		ans += dp[N][i] * i;
		ans %= MOD;
	}
	cout << ans;



	return 0;
}

Measured memory_bytes: 157184
import java.util.Scanner;
 
 
public class Main{
     
    public static void main(String[] args){
    	
    	final Scanner sc = new Scanner(System.in);
    	
    	final int n = sc.nextInt();
    	
    	long left = 0, right = 0;
    	for(int i = 0; i < n; i++){
    		final long p = sc.nextLong();
    		final char c = sc.next().toCharArray()[0];
    		final int q = sc.nextInt();
    		
    		if(c == ')'){
    			left += q;
    		}else if(c == '('){
    			right += q;
    		}
    		
    		System.out.println(left == right ? "Yes" : "No");
    	}
    	
    }
     
}

Measured memory_bytes: 48772
import fractions

N, X = list(map(int,input().split()))
x = list(map(int,input().split()))
x.append(X)
x = sorted(x)

difs=[]
for i in range(N):
    difs.append(x[i+1] - x[i])

    if i == 0:
        ans = difs[0]
        continue

    ans = fractions.gcd(ans, difs[i])

print(ans)

Measured memory_bytes: 16300
#include <iostream>

using namespace std;

void solve()
{
    int A,B;

        cin>>A>>B;

        if(A<10 && B<10)

        {
            cout<<A*B<<endl;
        }else{
            cout<<"-1"<<endl;
        }

}

int main()
{
    solve();

    return 0;
}



Measured memory_bytes: 256
import re,functools as f;d=f.lru_cache(999)(lambda n,b:n<1or sum(d(n-1,b[1:]+s)for s in'ACGT'if not re.match('.AGC|.ACG|.GAC|A.GC|AG.C',b+s))%(10**9+7));print(d(int(input()),'TTT'))

Measured memory_bytes: 4688
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define PI 3.1415926535897932
#define MOD 1000000007;
using namespace std;
long long GCD(long long A,long long B){
  if(B==0){
    return A;
  }
  else{
    return GCD(B,A%B);
  }
}
long long LCM(long long A,long long B){
  long long g=GCD(A,B);
  return A/g*B;
}
long long num_order(long long X){
  long long ans=0;
  while(true){
    if(X==0){
      break;
    }
    else{
      X/=10;
      ans++;
    }
  }
  return ans;
}
int main() {
  
  int N;
  cin>>N;
  
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  
  
  if(N%2==0){
    for(int i=0;i<N/2;i++){
      cout<<A[N-2*i-1]<<" ";
    }
    for(int i=0;i<N/2;i++){
      cout<<A[2*i]<<" ";
    }
  }
  else{
    for(int i=0;i<N/2;i++){
      cout<<A[N-2*i-1]<<" ";
    }
    cout<<A[0]<<" ";
    for(int i=0;i<N/2;i++){
      cout<<A[2*i+1]<<" ";
    }
  }
}

Measured memory_bytes: 3976
from collections import defaultdict
d = defaultdict(int)

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

for v in a:
    d[v] += 1

for i in range(m):
    b, c = map(int, input().split())
    d[c] += b
ans_list = []
for key, value in d.items():
    temp = [key, value]
    ans_list.append(temp)
ans_list.sort(key=lambda x: x[0])
ans_list.reverse()
ans = 0
for (value, count) in ans_list:
    if 0 > n - count:
        ans += n*value
        break
    else:
        n -= count
        ans += count*value
print(ans)



Measured memory_bytes: 50196
while True:
    h, w = map(int,input().split())
    if h == 0 and w == 0:
        break
    square = [['#' for i in range(w)] for j in range(h)]
    for i in range(0, h):
        for j in range(0, w):
            if (i + 1) % 2 == 1 and ((j + 1) + (i * w)) % 2 == 0:
                square[i][j] = '.'
            if (i + 1) % 2 == 0 and ((j + 1) + (i * w) + (w % 2)) % 2 == 1:
                square[i][j] = '.'

    [print(''.join(i)) for i in square]
    print('')




Measured memory_bytes: 5764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();

		int count = 0;
		for(int i = 0; i < 3; i++)
		{
			if(str.charAt(i) == '1')
			{
				count++;
			}
		}

		System.out.println(count);
    }
}

Measured memory_bytes: 23764
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 21 20:39:09 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

A.sort(reverse = True,key=lambda x:x[1])
eat,noteat =[],[]
a = [0 for i in range(N+1)]
k = K
for i in range(N):
    if k != 0:
        if a[A[i][0]] ==0:
            a[A[i][0]] = 1
            eat.append(A[i][1])
            k -= 1
        else:
            noteat.append(A[i][1])
    else:
        noteat.append(A[i][1])
        
ans = [0 for i in range(min(K-k,len(noteat))+2)]
ans[0] = sum(eat)+ sum(noteat[:k])+ pow(K-k,2)

for i in range(1,min(K-k,len(noteat[k:])+1)):
    ans[i] = ans[i-1]-(pow(K-k-(i-1),2)+eat[-i]) +(pow(K-k-i,2)+noteat[k+i-1])

print(max(ans))


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const string YES = "Yes";
const string NO = "No";

int main(){
    vector<vi> c(3, vi(3));
    rep(i, 3) rep(j, 3) cin >> c[i][j];
    bool ans = true;
    int sum = 0;
    rep(i, 3) rep(j, 3) sum += c[i][j];
    if (sum%3!=0) ans = false;
    vi a(3), b(3);
    rep(i, 3) rep(j, 3) a[i] += c[i][j];
    rep(j, 3) rep(i, 3) b[j] += c[i][j];
    rep(i, 3) if (abs(a[i]-a[(i+1)%3])%3!=0) ans = false;
    rep(i, 3) if (abs(b[i]-b[(i+1)%3])%3!=0) ans = false;
    if (ans) cout << YES << endl;
    else cout << NO << endl;
    return 0;
}


Measured memory_bytes: 3584
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define INF (int)1e9
#define INFL (ll)1e11
using namespace std;
typedef long long ll;
typedef pair<int, int> P;


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

	int n;
	cin >> n;
	
	int res = 111;
	while (res < n) res += 111;

	cout << res << "\n";

	return 0;
}



Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))



using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;


ll N, A, B;




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

	ll l = (N - 1) * A + B;
	ll r = (N - 1) * B + A;

	if (A <= B && ((N >= 2) || (A == B && N == 1))) {
		cout << r - l + 1 << endl;
	}
	else {
		cout << 0 << endl;
	}

	return 0;
}

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

namespace A
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var S = Console.ReadLine().Trim().Split(' ');
            var answer = new char[] { S[0][0], S[1][0], S[2][0] };

            Console.WriteLine(new string(answer).ToUpper());
        }
    }
}


Measured memory_bytes: 26296
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.NoSuchElementException;


public class Main {
    public static ArrayList<String> ans = new ArrayList<>();
    public static void main(String[] args) {
        FastScanner fsc = new FastScanner();
        int n = fsc.nextInt();
        dfs("a", 0, 1, n);
        StringBuilder sb = new StringBuilder();
        for (String str : ans) {
            sb.append(str).append('\n');
        }
        System.out.print(sb);
    }

    public static void dfs(String s, int max, int len, int n) {
        if (len == n) {
            ans.add(s);
        } else {
            for (int i = 0; i <= max + 1; i++) {
                dfs(s + String.valueOf((char)('a' + i)), Math.max(max, i), len + 1, n);
            }
        }
    }
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 50072
#include <stdio.h>

int main(){
  int i,j,k,l,n,a,b,c,d;
  while(scanf("%d",&n)!=EOF){
    int count=0;
    for (i=0;i<=9;i++){
      for (j=0;j<=9;j++){
        for (k=0;k<=9;k++){
          for (l=0;l<=9;l++){
            if (i+j+k+l==n){
              count++;
            }
          }
        }
      }
    }
    printf("%d\n",count);
  }

  return 0;
}

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

struct Card {
  char suit, value;
};

void bubble(struct Card A[], int N) {
  for (int i = 0; i < N; i++) {
    for (int j = N - 1; j >= i + 1; j--) {
      if (A[j].value < A[j - 1].value) {
        Card t = A[j];
        A[j] = A[j - 1];
        A[j - 1] = t;
      }
    }
  }
}

void selection(struct Card A[], int N) {
  for (int i = 0; i < N; i++) {
    int minj = i;
    for (int j = i; j < N; j++) {
      if (A[j].value < A[minj].value) minj = j;
    }
    Card t = A[i];
    A[i] = A[minj];
    A[minj] = t;
  }
}

void print(struct Card A[], int N) {
  for (int i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << A[i].suit << A[i].value;
  }
  cout << endl;
}

bool isStable(struct Card C1[], struct Card C2[], int N) {
  for (int i = 0; i < N; i++) {
    if (C1[i].suit != C2[i].suit) return false;
  }
  return true;
}

int main() {
  Card C1[100], C2[200];
  int N;
  char ch;

  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> C1[i].suit >> C1[i].value;
  }

  for (int i = 0; i < N; i++) C2[i] = C1[i];

  bubble(C1, N);
  selection(C2, N);

  print(C1, N);
  cout << "Stable" << endl;
  print(C2, N);
  if (isStable(C1, C2, N)) {
    cout << "Stable" << endl;

  } else {
    cout << "Not stable" << endl;
  }

  return 0;
}


Measured memory_bytes: 3096