akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] a = new long[n];
    long max = 0;
    for(int i = 0;i < n;i++){
      a[i]=sc.nextLong();
      max = Math.max(max,a[i]);
    }
    long num = 0;
    long k = max/2;
    long min = 1000000000;
    if(max%2==0){
      for(int i = 0;i < n;i++){
        if(a[i]!=min){
          min = Math.min(min,Math.abs(a[i]-k));
          if(min==Math.abs(a[i]-k))num=a[i];
        }
      }
    }else{
      for(int i = 0;i < n;i++){
        if(a[i]!=min){
          min = Math.min(min,Math.min(Math.abs(a[i]-k),Math.abs(a[i]-k-1)));
          if(min==Math.abs(a[i]-k))num=a[i];
          else if(min==Math.abs(a[i]-k-1))num=a[i];
        }
      }
    }
    System.out.println(max+" "+num);
  }
}

Measured memory_bytes: 51328
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Runtime.InteropServices;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var n = int.Parse(spl[0]);
        var m = int.Parse(spl[1]);

        var bar = new List<int>[n];
        for (int i = 0; i < n; i++) bar[i] = new List<int>();

        var ab = new int[m][];

        for(int i=0; i<m; i++) {
            spl = input.ReadLine().Split(' ');
            var a = int.Parse(spl[0]) - 1;
            var b = int.Parse(spl[1]) - 1;
            bar[a].Add(b);
            bar[b].Add(a);

            ab[i] = new int[2];
            ab[i][0] = a;
            ab[i][1] = b;
        }

        var c = 0L;

        for (int i = 0; i < m; i++) {
            var a = ab[i][0];
            var b = ab[i][1];

            var hash = new HashSet<int>();
            var q = new Queue<int>();

            //最初の要素追加
            q.Enqueue(0);

            while (q.Any()) {
                var x = q.Dequeue();
                //Debug.WriteLine(x);

                if (hash.Contains(x)) {
                    continue;
                }
                hash.Add(x);

                foreach (var to in bar[x]) {
                    if((to == a && x == b) || (to == b && x == a)) {
                    } else {
                        q.Enqueue(to);
                    }
                }
            }

            if (hash.Count < n) c++;
        }

        return c;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 13408
#pragma GCC target ("avx2") 
#pragma GCC optimization ("O3") 
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define fast_az_fuk ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long 
#define int ll 
#define ull unsigned ll
#define ld long double 
#define pb push_back 
#define pf push_front
#define dll deque<ll> 
#define vll vector<ll> 
#define pll pair<ll,ll> 
#define mapll map<ll,ll>
#define endl "\n" 
#define all(v) v.begin(),v.end() 
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
void swap(auto*,auto*);
const ll p=1e9+7;
ull power(ll x,ull y)
{
    ull res=1;
    while(y)
    {
        if(y&1) res=(res*x)%p;
        x=(x*x)%p; y>>=1;
    }
    return res;
}
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    fast_az_fuk
    //your code goes here
    ll n; cin>>n;
    ll a=power(10,n);
    ll b=(2*power(9,n))%p;
    b=(p+b-power(8,n))%p;
    a=(p+a-b)%p;
    cout<<a;
    return 0;
}
void swap(auto &a,auto &b)
{
    auto temp=a; a=b; b=temp;
}

Measured memory_bytes: 3648
let rec calc r i n =
	let x = (Int64.sub n (Int64.div (Int64.mul i (Int64.sub i 1L)) 2L)) in
	if (Int64.compare x i)>=0 then
		if (Int64.compare (Int64.rem x i) 0L)==0 then (
				calc (Int64.add r 1L) (Int64.add i 1L) n
		) else
			calc r (Int64.add i 1L) n
	else
		r;;

try
	while true do
		Scanf.sscanf (read_line ()) "%Ld" (fun n ->
			if (Int64.compare n 0L)==0 then exit(0) else (
				print_string (Int64.to_string (calc 0L 2L n));
				print_string "\n"
			)
		)done;
with End_of_file -> ();;

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

using namespace std;

using pii = pair<int, int>;
using pll = pair<long long, long long>;

constexpr int MAXN = 100000 + 228;

vector<vector<int>> gr(MAXN);
vector<bool> used(MAXN);
vector<int> par(MAXN, -1);



int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }

    deque<int> dq;
    dq.push_back(1);
    used[1] = true;
    while (!dq.empty()) {
        int cur = dq.front();
        dq.pop_front();
        for (auto it: gr[cur]) {
            if (!used[it]) {
                used[it] = true;
                par[it] = cur;
                dq.push_back(it);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (par[i] == -1) {
            cout << "No" << endl;
        }
    }
    cout << "Yes" << endl;
    for (int i = 2; i <= n; i++) {
        cout << par[i] << endl;
    }
    cout << endl;
}

Measured memory_bytes: 10132
N, M = map(int, input().split())

MAX = 5 * 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD

# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD

def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD

def permute(n, k):
    return comb(n, k) * fac[k]

ans = 0
for k in range(N + 1):
    ans += comb(N, k) * (-1) ** k * permute(M, k) * permute(M - k, N - k) ** 2
    ans %= MOD

print(ans)


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

public class Main {
    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int[] n = new int[in.nextInt()];
        for (int i = 0; i < n.length; i++) {
            n[i] = in.nextInt();
        }

        int count = 0;
        for (int i = 1; i < n.length - 1; ++i) {
            if (n[i] > n[i - 1]) {
                if (n[i + 1] > n[i]) {
                    count++;
                }
            } else if (n[i] < n[i - 1]) {
                if (n[i] > n[i + 1]) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 21588
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum = sum + (-sc.nextInt() + sc.nextInt() + 1);
        }
        System.out.println(sum);

    }

}

Measured memory_bytes: 25396
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef pair<ll, ll> P;

int main(){
    int n;
        cin >> n;
    int a[n], b[n];
        for(int i=0; i<n; i++) cin >> a[i];
        for(int i=0; i<n; i++) cin >> b[i];
    int c[n-1];
        for(int i=0; i<n-1; i++) cin >> c[i];
    int sum=0;
        for(int i=0; i<n; i++)
            sum += b[a[i]-1];
        for(int i=0; i<n-1; i++)
            if(a[i]+1==a[i+1]) sum += c[a[i]-1];
        cout << sum << endl;
}


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

int main(){
  int a, b;
  cin >> a >> b;
  if(a+b>=a-b && a+b>=a*b){
    cout << a+b;
  }
  else if(a-b>=a+b && a-b>=a*b){
    cout << a-b;
  }
  else if(a*b>=a+b && a*b>=a-b){
    cout << a*b;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long k = sc.nextLong();
		System.out.println(k%2==1 ? (n/k)*(n/k)*(n/k) : ((n/(k/2))-n/k)*((n/(k/2))-n/k)*((n/(k/2))-n/k)+(n/k)*(n/k)*(n/k));
	}
}

Measured memory_bytes: 23380
import java.util.*;
import java.math.*;
class Main {
    //
    static final int MOD = 1_000_000_007; // 10^9+7
    //static final int MAX = 2_147_483_646; // intの最大値
    
    static final int INF = 1_000_000_000; // 10^9
    static final int MAX = 10_000_000;
    static long[] fac = new long[1000003];
    static long[] finv = new long[1000003];
    static long[] inv = new long[1000003];
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        long ans = modpow(n);
        sc.close();        
        ans -= 1 + nCk(n, a, MOD) + nCk(n, b, MOD);
        while(ans < 0){
            ans += MOD;
        }
        System.out.println(ans);
    }
    static long modpow(final long n) {
        long ans = 1;
        long a = 2;
        long m = n;
        while (m > 0) {
            if ((m & 1) == 1)
                ans = ans * a % MOD;
            a = a * a % MOD;
            m >>= 1;
        }
        return ans;
    }
    public static int nCk(int n, int k, int M) {
		long ret = 1;
		int min = Math.min(k, n - k);
		for (int i = 1; i <= min; i++) {
			ret = (ret * pow(i, M - 2, M)) % M;
		}
		for (int i = n - min + 1; i <= n; i++) {
			ret = (ret * i) % M;
		}
		return (int) ret;
    }

    public static long pow(long a, long b, int M) {
		long ret = 1;
		long tmp = a;
		while (b > 0) {
			if ((b & 1) == 1)
				ret = (ret * tmp) % M;
			tmp = (tmp * tmp) % M;
			b = b >> 1;
        }
        
		return ret;
	}
    
}

Measured memory_bytes: 46292
var    ch:char;
      s,x:longint;
begin
   while not eoln do
      begin
         read(ch);
        s:=s*10+ord(ch)-48;
        x:=x+ord(ch)-48;
       end;
     if s mod x=0 then writeln('Yes')
      else writeln('No');
end.

Measured memory_bytes: 128
#python3
from math import factorial
from math import floor
MOD = int(1e9+7)

def comb(n, m, mod):
    comb_a = 1
    for i in range(m): 
        comb_a *= (n-i)
        comb_a %= mod
    comb_tmp = factorial(m) 
    comb_b = pow(comb_tmp, mod-2, mod)
    return (comb_a * comb_b)%mod
def main():
    x, y = map(int, input().split())
    k = (2*x-y)/3
    l = (2*y-x)/3

    if floor(k) - k != 0:
        print(0)
        return
    if floor(l) - l != 0:
        print(0)
        return 
    if k<0:
        print(0)
        return
    if l<0:
        print(0)
        return
    k = int(k)
    l = int(l)
    print(comb(k+l, k, MOD)%MOD) 

main()


Measured memory_bytes: 6780
#include "bits/stdc++.h"
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
using namespace std;



int main(){
ll N;
cin>>N;
pair<ll,ll> max = make_pair(0,0);
vector<ll> a(N);
for(ll i=0;i<N;i++){
  cin>>a[i];
  if(a[i]>max.second){
    max.first = i;
    max.second = a[i];
  }
}



sort(ALL(a));
reverse(ALL(a));
for(ll i=0;i<N;i++){
if(i==max.first)
cout<<a[1]<<endl;
else
cout<<a[0]<<endl;
}


return 0;
}


Measured memory_bytes: 3200
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }


void solve(LL cur, LL parent, LL cum, vector<vector<LL>>& edge, vector<LL>& cnt, vector<LL>& ans){
    cum += cnt[cur];
    ans[cur] = cum;
    for(LL next: edge[cur]){
        if(next == parent) continue;
        solve(next, cur, cum, edge, cnt, ans);
    }
}

int main(){
    LL n, q;
    cin >> n >> q;
    vector<vector<LL>> edge(n);
    for(LL i = 0; i < n-1; ++i){
        LL a, b;
        cin >> a >> b;
        --a; --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    vector<LL> cnt(n);
    for(LL i = 0; i < q; ++i){
        LL p, x;
        cin >> p >> x;
        --p;
        cnt[p] += x;
    }
    vector<LL> ans(n);
    solve(0, -1, 0, edge, cnt, ans);
    for(LL i = 0; i < n; ++i){
        if(i+1 == n){
            cout << ans[i] << endl;
        }else{
            cout << ans[i] << " ";
        }
    }
    return 0;
}



Measured memory_bytes: 32128
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

const int INF = 1 << 24;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<P,int> State;
 
bool compareState(const State& ls, const State& rs){
    const P& lp = ls.first, rp = rs.first;
    if(lp.second == rp.second){
        return lp.first < rp.first;
    }
    return lp.second < rp.second;
}

int main(){
    int N, R;
    while(std::cin >> N >> R, N){
        int minX = INF, maxX = 0, minY = INF, maxY = 0;
        std::vector<State> S;
        REP(i, N){
            int x1, y1, x2, y2;
            std::cin >> x1 >> y1 >> x2 >> y2;

            minX = std::min(minX, x1);
            maxX = std::max(maxX, x2);
            minY = std::min(minY, y1);
            maxY = std::max(maxY, y2);

            S.push_back(mp(mp(x1, y1), 1));
            S.push_back(mp(mp(x1, y2), -1));
            S.push_back(mp(mp(x2, y1), -1));
            S.push_back(mp(mp(x2, y2), 1));
        }

        std::sort(S.begin(), S.end(), compareState);

        int board[2][10001], pos = 0;
        REP(i, 2){
            REP(j, 10001){
                board[i][j] = 0;
            }
        }

        // REP(i, S.size()){
        //     printf("(%d, %d): %d\n", S[i].first.first, S[i].first.second, S[i].second);
        // }

        //std::cout << minX << ", " << maxX << std::endl;
        //std::cout << minY << ", " << maxY << std::endl;

        int l = 0, sq = 0;
        FOR(i, minY, maxY+1){
            FOR(j, minX, maxX+1){
                board[1][j] = 0;
            }

            if(pos < S.size()){
                while(S[pos].first.second == i){
                    board[1][S[pos].first.first] += S[pos].second;
                    pos++;
                }
                //printf("%d, %d\n", i, pos);

                FOR(j, minX+1, maxX+1){
                    board[1][j] += board[1][j-1];
                }
            }
        
            FOR(j, minX, maxX+1){
                board[1][j] += board[0][j];
            }

            FOR(j, minX, maxX+1){
                //printf("%d, ", board[1][j]);
                
                if(board[1][j] > 0){
                    sq += 1;
                
                    if(j == 0 || board[1][j-1] == 0){
                        l += 1;
                    }
                    if(j == 10000 || board[1][j+1] == 0){
                        l += 1;
                    }
                    l += (board[0][j] == 0) * 2;
                }
            }
            //puts("");
            //printf("%d\n", l);
        
            std::swap(board[0], board[1]);
        }

        FOR(i, minX, maxX+1){
            if(board[0][i] > 0){
                l += 1;
            }
        }
    

        std::cout << sq << std::endl;
        if(R == 2){
            std::cout << l << std::endl;
        }
    }
}

Measured memory_bytes: 2448
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nya_n "(=^･ω･^=)"
typedef long long ll;
using namespace std;

int n, m, k, mem;
vector<int>p[100000];
vector<int>l[100000];
bool vtdp[100000], vtdl[100000];

int dfsl(int x);
int dfsp(int x);

int dfsp(int x) {
	lp(p[x].size()) {
		if (!vtdl[p[x][i]]) {
			vtdl[p[x][i]] = true;
			dfsl(p[x][i]);
		}
	}
	return 0;
}

int dfsl(int x) {
	lp(l[x].size()) {
		if (!vtdp[l[x][i]]) {
			vtdp[l[x][i]] = true;
			dfsp(l[x][i]);
		}
	}
	return 0;
}



int main() {
	cin >> n >> m;
	lp(n) {
		cin >> k;
		LP(k, j) {
			cin >> mem;
			p[i].push_back(mem - 1);
			l[mem - 1].push_back(i);
		}
	}
	lp(m)
		vtdl[i] = false;
	lp(n)
		vtdp[i] = false;
	vtdp[0] = true;
	dfsp(0);
	lp(n)
		if (!vtdp[i]) {
			cout << "NO" << endl;
			return 0;
		}
	cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 8704
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static void Main()
    {
        new Magatro().Solve();
    }
}

class Magatro
{
    private int N;
    private int[] A, B;
    private List<int>[] Node;
    private int[] SDist, FDist;

    private void Scan()
    {
        N = int.Parse(Console.ReadLine());
        A = new int[N - 1];
        B = new int[N - 1];
        for (int i = 0; i < N - 1; i++)
        {
            var line = Console.ReadLine().Split(' ');
            A[i] = int.Parse(line[0]);
            B[i] = int.Parse(line[1]);
        }
    }

    private int[] Dist(int s)
    {
        int[] result = (new int[N]).Select(i => -1).ToArray();
        Queue<int> Q = new Queue<int>();
        Q.Enqueue(s);
        result[s] = 0;
        while (Q.Count > 0)
        {
            int j = Q.Dequeue();

            foreach (int ii in Node[j])
            {
                if (result[ii] == -1)
                {
                    result[ii] = result[j] + 1;
                    Q.Enqueue(ii);
                }
            }
        }
        return result;
    }

    public void Solve()
    {
        Scan();
        Node = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            Node[i] = new List<int>();
        }

        for (int i = 0; i < N - 1; i++)
        {
            Node[A[i] - 1].Add(B[i] - 1);
            Node[B[i] - 1].Add(A[i] - 1);
        }

        FDist = Dist(0);
        SDist = Dist(N - 1);
        int snuke = 0;
        int fennec = 0;

        for (int i = 0; i < N; i++)
        {
            if (FDist[i] > SDist[i])
            {
                snuke++;
            }
            else
            {
                fennec++;
            }
        }
        if (snuke >= fennec)
        {
            Console.WriteLine("Snuke");
        }
        else
        {
            Console.WriteLine("Fennec");
        }
    }
}


Measured memory_bytes: 31456
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a, b, c, k;
	int ans = 0;
	cin >> a >> b >> c >> k;
	ans += min(a, k);
	k -= min(a, k);
	if (k) {
		k -= min(b, k);
		if (k) {
			ans -= k;
		}
	}
	cout << ans;
}

Measured memory_bytes: 3652
/*
ID: thanhvq1
LANG: C++14
PROB: namenum
*/

#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
//#define int long long
#define double long double
#define vec vector
#define vi vector<int>
#define FZ(n) memset((n),0,sizeof(n))
#define FMO(n) memset((n),-1,sizeof(n))
#define unset unordered_set
#define ii pair<int, int>
#define vii vector<ii>
#define F first
#define S second
#define PB push_back
#define ALL(x) begin(x),end(x)
#define SZ(x) ((int)(x).size())
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define bitcount(n) __builtin_popcountll(n)
template <typename T,typename U>
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {
  return {l.first+r.first, l.second+r.second};
} 
typedef void (*callback_function)(void); // type for conciseness
const long long ZERO = 0LL;
const long long INF64 = 1e18;
const int INF32 = 1e9;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0L);
const double EPS = static_cast<double>(1e-9);
typedef long long ll;

void FILEIO() {  freopen("in.txt", "r", stdin);  freopen("out.txt", "w", stdout); }
//void FILEIO() {  freopen("namenum.in", "r", stdin);  freopen("namenum.out", "w", stdout); }

int n, m;
vi a;
set<int> sa;
int dp[123456][2]; // dp[k][0]: qua k but not qua k-1; dp[k][1]: qua k, qua k-1

void solve() {
	cin >> n >> m;
	a.resize(m);
	FOR(i, 0, m) cin >> a[i], sa.insert(a[i]);
	if(n==1) {cout << 1 << endl; return;}
	FOR(i, 1, m-1) if(a[i] == a[i-1]+1) {cout << 0 << endl; return;}
	if(sa.count(1)>0) dp[1][0] = 0, dp[1][1] = 0; // step 1 broken
	else dp[1][0] = 0, dp[1][1] = 1;
	if(sa.count(1)>0) { // step 1 broken (step 2 is good)
		dp[2][0] = 1, dp[2][1] = 0;
	}
	else { // step 1 is good
		if(sa.count(2) > 0) { // step 2 broken
			dp[2][0] = 0, dp[2][1] = 0;
		}
		else { // step 2 is good
			dp[2][0] = 1, dp[2][1] = 1;
		}
	}
	if(n==2) {cout << dp[2][0] + dp[2][1] << endl; return;}
	FOR(i, 3, n+1) {
		if(sa.count(i)==0) {
			dp[i][0] = (sa.count(i-2)==0)? (dp[i-2][0]+dp[i-2][1])%MOD : 0;
			dp[i][1] = (sa.count(i-1)==0)? (dp[i-1][0]+dp[i-1][1])%MOD : 0;
		}
		else dp[i][0] = dp[i][1] = 0;
	}

//	for(auto x: sa) cout << x << " "; cout << endl;
//	FOR(i, 1, n+1) cout << dp[i][0] << " "; cout << endl;
//	FOR(i, 1, n+1) cout << dp[i][1] << " "; cout << endl;

	cout << (dp[n][0] + dp[n][1])%MOD << endl;
}

//#undef int
signed main() {
//#define int long long
  ios_base::sync_with_stdio(false); cin.tie();
//  FILEIO();
//auto beginProgram = chrono::steady_clock::now();

// int t; cin >> t;
//  while (t--)
  {
		solve();
  }

  //auto endProgram = chrono::steady_clock::now();

  return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define REP(i, n)     for(int i = 0;i < n;i++)
#define REPR(i, n)    for(int i = n;i >= 0;i--)
#define FOR(i, m, n)  for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VRSORT(v) sort(v.begin(), v.end(),greater<int>());
#define ALL(X) (X).begin(),(X).end()
#define INF 99999999
#define M_PI 3.14159265358979323846
#define MOD 1000000007

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) os << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

// ナップサック問題なんだけど
// ふつうのナップサックと異なる。


int H,N;
vector<int> A,B;
struct magic{
  double A,B,R;
  magic(double a, double b, double r):A(a), B(b),R(r){}
};

vector<magic> M;

void input(){
  #ifdef __LOCAL
      fs::path p = __FILE__;
      fs::path input,output;
      input = output = p.parent_path();
      input += string("/input/") + string(p.stem()) + string(".txt");
      output += string("/output/") + string(p.stem()) + string(".txt");
      freopen(input.c_str(), "r", stdin);
      freopen(output.c_str(), "w", stdout);
  #endif

  fast_io();
  cin >> H >> N;
  for(int i=0;i<N;i++){
    double a,b;
    cin >> a >> b;
    A.push_back(a);
    B.push_back(b);
    // M.push_back(magic(a,b,a/b));
  }
  // sort(M.begin(),M.end(),[](magic m, magic n){return m.R > n.R;});
}


int DP[100000];
int solve(){
  input();
  DP[0] = 0;
  int m = *max_element(ALL(A));
  for(int k=1;k<=(H+m);k++){
    DP[k] = INT_INF;
    for(int i=0;i<N;i++){
      if(k-A[i]>=0) DP[k] = min(DP[k],DP[k-A[i]]+B[i]) ;
      else DP[k] = min(DP[k],B[i]);
    }
  }
  int ans = DP[H];
  for(int i=1;i<=m;i++) ans = min(ans,DP[H+i]);
  return ans;
}

int main()
{
  cout << solve() << endl;
  return 0;
}


Measured memory_bytes: 384
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect


N = int(input())
ans = 0
if N < 105:
    print(0)
    exit()

num = N

ans = 0
for n in range(105,N+1):
    yakusuu_array = []
    if n % 2 == 1:
        for i in range(1,n):
            if n % i == 0:
                yakusuu_array.append(i)
        if len(yakusuu_array)+1 == 8:
            ans += 1
print(ans)


Measured memory_bytes: 5672
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n , k , a[100]; short dp[200001][2];
bool f( bool p = 0 , int k = k )
{
    if( k == 0 )
        return 0;
    if( k < 0 )
        return 1;
    short &d = dp[k][p];
    if( d != -1 )
        return d;
    bool mn = 1;
    for(int i=0;i<n;++i)
        mn = min( mn , f( !p , k-a[i] ) );
    return d = !mn;
}
int main()
{
    memset(dp,-1,sizeof dp);
    cin >> n >> k;
    for(int i=0;i<n;++i)
        cin >> a[i];
    cout <<( f() == 1 ? "First" : "Second" );
    
    return 0;
}


Measured memory_bytes: 8832
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  if n==1:
    return 0
  ans=10
  a=9
  b=9
  c=8
  for _ in range(n-1):
    ans*=10
    ans%=mod
    a*=9
    a%=mod
    b*=9
    b%=mod
    c*=8
    c%=mod

  return (ans-(a+b-c))%mod

# main()
print(main())


Measured memory_bytes: 10684
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val s = sc.next()
  val t = sc.next()

  var count = 0
  for (i in 0 until s.length) {
    if (s[i] != t[i]) {
      count++
    }
  }

  println(count)
}


Measured memory_bytes: 41760
#include <cstdio>
using namespace std;
#define ll long long
ll a,b;

ll gcd(ll a,ll b)
{
    ll t;
    while (b!=0)
    {
        t=b;
        b=a % b;
        a=t;
    }
    return a;
}

ll lcm(ll a,ll b)
{
    return a*b / gcd(a,b);
}

int main()
{
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",lcm(a,b));
    return 0;
}

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

#define ff first
#define ss second
#define mp make_pair

using namespace std;

typedef long long ll;

vector<int> G[100005];
vector<pair<int,int>> e;
int ans[100005];
int k;

void dfs(int v, int p, int c) {
	int cur = 1;
	// printf("%d -> %d\n", v, c);

	for(int x : G[v]) {
		auto aux = e[x];
		int u = aux.ff == v ? aux.ss : aux.ff;
		if(u == p) continue;
		if(cur == c) cur++;
		ans[x] = cur;
		dfs(u, v, cur);
		cur++;
	}
}

int main() {
	int n,a,b;

	scanf("%d", &n);

	for(int i = 0; i < n-1; i++) {
		scanf("%d%d", &a, &b);
		G[a].push_back(i);
		G[b].push_back(i);
		e.emplace_back(a,b);
		k = max<int>(k, G[a].size());
		k = max<int>(k, G[b].size());
	}

	dfs(1,1,0);

	printf("%d\n", k);
	for(int i = 0; i < n-1; i++)
		printf("%d\n", ans[i]);

    return 0;
}

Measured memory_bytes: 9720
#include <bits/stdc++.h>
using namespace std;
int main(){
	priority_queue<int> pq;
	int n, k, m , x=0;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> k;
		pq.push(k);
	}
	for(int i=1;i<=m;i++){
		x = x + pq.top();
		if(!pq.empty()){
			pq.pop();
		}
	}
	cout << x;
}

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

int main()
{
  int n;
  cin>>n;
  if(n&1) cout<<n/2+1;
  else cout<<n/2;
  return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector<string> blue(n);
    for(int i =0; i < n; i++){
        cin >>blue.at(i);
    }
    int m;
    cin >> m;
    vector<string> red(m);
    for(int i =0; i < m; i++){
        cin >> red[i];
    }

    int ans = 0;
    for(string s:blue){
        int score = 0;
        for(string t:blue) if(s == t) ++score;
        for(string t:red) if(s == t) --score;
        ans = max(ans, score);
    }
    cout << ans << endl;

}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<vvvll> vvvvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<vvc> vvvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<pair<ll,ll> > > vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;

#define PI 3.141592653589793
#define MOD 1000000007

template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, ll m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }


int main()
{
	IOS;
	ll h,w;
	cin>>h>>w;
	vvll ans(h,vll(w));
	ll n;
	cin>>n;
	vll v(n);
	for(ll i=0;i<n;i++)
	{
		cin>>v[i];
	}
	ll ind=0;
	for(ll i=0;i<h;i++)
	{
		if(i%2==0)
		{
			for(ll j=0;j<w;j++)
			{
				if(v[ind]==0)
				{
					ind++;
				}
				v[ind]--;
				ans[i][j]=ind+1;
			}
		}
		else
		{
			for(ll j=w-1;j>=0;j--)
			{
				if(v[ind]==0)
				{
					ind++;
				}
				v[ind]--;
				ans[i][j]=ind+1;
			}
		}
	}
	for(ll i=0;i<h;i++)
	{
		for(ll j=0;j<w;j++)
		{
			cout<<ans[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define endl '\n'
#define inf (ll)(1e18+5)
#define maxn 3000001
#define mod (ll)(1e9+7)
#define int ll
 
using namespace std;
 
void io(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

int t,n,m,l,r,x,y,z,a,b,c,mn=inf,mx=-inf,w,sum=0;
int ar[maxn];
int dp[105][100005];
int wei[maxn];
int val[maxn];

// https://discuss.codechef.com/t/help-with-knapsack-2-on-atcoder/58548/4

int32_t main(){
io();
IOS;    
		
		cin>>n>>w;
		for(int i=1;i<=n;i++){
			cin>>wei[i];cin>>val[i];
			sum+=val[i];
		}

		for(int i=0;i<=n;i++)dp[i][0]=0;
		for(int i=1;i<=sum;i++){
			dp[0][i]=inf;
		}

		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=sum;j++){
				dp[i][j]=dp[i-1][j];
				if(j>=val[i])dp[i][j]=min(dp[i][j],dp[i-1][j-val[i]]+wei[i]);
				if(dp[i][j]<=w){
					ans=max(ans,j);
				}

			}
		}

		cout<<ans<<endl;
		




        

        


        
    
        
        
                


 
        
 
 
 
        
 
 
 
 
        
        
 
        
        
 
    
    
    
    
 
 
       
 
 
 
 
      
   
 
 
 
 
}

Measured memory_bytes: 82416
#include <stdio.h>
int main(void){
    int A1,A2,A3,all;
    scanf("%d",&A1);
    scanf("%d",&A2);
    scanf("%d",&A3);
    all=A1+A2+A3;
    if(all>21){
        printf("bust\n");
    }else{
        printf("win\n");
    }
}

Measured memory_bytes: 128
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::io::Read;
use std::io::{stdout, BufWriter, Write};
 
fn main() {
    let mut buf = String::new();
    
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
 
    // 標準入力から全部bufに読み込む
    std::io::stdin().read_to_string(&mut buf).unwrap();
 
    // 読み込んだStringを空白で分解する
    let mut iter = buf.split_whitespace();
    
    const M_MAX : usize = 100000;
 
    let n: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();
    
    let mut left : i64 = 1;
    let mut right : i64 = n as i64;
    
    //let mut cards = [1; M_MAX];
    
    for i in 0..m{
        let l: i64 = iter.next().unwrap().parse().unwrap();
        let r: i64 = iter.next().unwrap().parse().unwrap();
        if left < l {
            left = l;
        }
        if r < right {
            right = r;
        }
    }
    
    let mut nums = right - left + 1;
    if nums < 0 {
        nums = 0;
    }
        
    write!(out, "{}", nums);
 
}

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

#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
#define int long long
#define ld long double
#define pb emplace_back
#define range(v) v.begin(),v.end()
#define mod (int)(1e9 + 7)
#define inf (int)(1e15)
#define pii pair<int,int>
#define ff first
#define ss second
// #define N (int)()

using namespace std;

int32_t main() {
    fast
    int t_c = 1;
//	cin >> t_c;
    while (t_c--) {
        ld a, b;
        cin >> a >> b;
        int c = a * b;
        cout << c << endl;
    }
}

Measured memory_bytes: 3744
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<stack>
#include<climits>
using namespace std;
#define ll long long int
#define gc getchar_unlocked
#define fo(i,n) for(i=0; i<n; i++)
#define Fo(i,k,n) for(i=k; k<n?i<n:i>n; k<n?i+=1:i-=1)
#define deb(x) cout << #x << "=" << x <<"\n"
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y <<"\n"
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortall(x) sort(x.begin(), x.end())
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it,a) for(auto it = a.begin; it != a.end; it++)
#define PI 3.1415926535897932384626
typedef vector<ll> vl;
typedef map<ll, ll> ml;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<vl> vvl;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);   
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(a>=b) {
        while(k--) {
            b *= 2;
            if(b>a)
                break;
        }
    }
    if(b>=c) {
        while(k--) {
            c *= 2;
            if(c>b)
                break;
        }
    }

    if(b>a && c>b)
        cout<<"Yes";
    else
        cout<<"No";

	return 0;
}




Measured memory_bytes: 3648
# -*- coding: utf-8 -*-
from itertools import product

N = int(input())
INF = float("inf")
adj = []

for _ in range(N):
    adj.append([int(n) if n != "-1" else float("inf") for n in input().split()])

not_MST = list(range(1, N))
MST = [0]

cost = 0
while len(not_MST):
    tmp_min = INF
    tmp_idx = -1
    for m, n in product(MST, not_MST):
        if adj[m][n] < tmp_min:
            tmp_min = adj[m][n]
            tmp_idx = n
    MST.append(tmp_idx)
    not_MST.remove(tmp_idx)
    cost += tmp_min

print(cost)

Measured memory_bytes: 7876
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
g = [set() for _ in range(n)]
for i in range(m):
    a,b = inpl()
    a -= 1; b -= 1
    g[a].add(b)
    g[b].add(a)
res = 0
for a in itertools.permutations(range(1,n)):
    a = [0] + list(a)
    for i in range(n-1):
        x = a[i]; y = a[i+1]
        if x in g[y]:
            continue
        else:
            break
    else:
        # print(a)
        res += 1
print(res)

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

int main()
{
  int n;
  string s;
  
  cin >> n;
  cin >> s;
  
  if( n<3 ){
    cout << "0" << endl;
    exit(0);
  }
  
  ll cnt1 = 0;
  
  ll c_r=0,c_g=0,c_b=0;
  
  int d[3*4010];
  
  ll rg=0,rb=0,gb=0,gr=0,br=0,bg=0;
  
  for(int i=n-1;i>=0;i--){
    int rr=0,gg=0,bb=0;
    if( s[i]=='R' ){
      for(int j=i+1;j<n;j++){
        if( s[j]=='G' ) cnt1 += d[j*3+2];
        if( s[j]=='B' ) cnt1 += d[j*3+1];
      }
      c_r ++;
    }
    if( s[i]=='G' ){
      for(int j=i+1;j<n;j++){
        if( s[j]=='R' ) cnt1 += d[j*3+2];
        if( s[j]=='B' ) cnt1 += d[j*3  ];
      }
      c_g ++;
    }
    if( s[i]=='B' ){
      for(int j=i+1;j<n;j++){
        if( s[j]=='R' ) cnt1 += d[j*3+1];
        if( s[j]=='G' ) cnt1 += d[j*3  ];
      }
      c_b ++;
    }
    d[i*3   ] = c_r;
    d[i*3+1 ] = c_g;
    d[i*3+2 ] = c_b;
  }
  
  // cout << "cnt1=" << cnt1 << endl;
  
  ll cnt3 = 0;
  ll maxd = ( n - 1 ) / 2;
  // cout << maxd << endl;
  for(int i=1;i<=maxd;i++){
    int w = 1 + 2 * i;
    for(int j=0;j<=n-w;j++){
      if( s[j]!=s[j+i] && s[j+i]!=s[j+2*i] && s[j]!=s[j+2*i] ) cnt3++;
    }
  }
  
  // cout << ",c3=" << cnt3 << endl;
  
  ll total = cnt1 - cnt3;
  
  cout << total << endl;
  return 0;
}




Measured memory_bytes: 3668
n=int(input()) 
s=list(input())

dp=[0]*(n+1)
for i in range(n):
  if s[i]=="#":
    dp[0]+=1

for i in range(n):
  if s[n-i-1]=="#":
    dp[i+1]=dp[i]-1
  else:
    dp[i+1]=dp[i]+1

print(min(dp))

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

typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<bool> > vvb;
typedef map<int, bool> mib;

typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vpll;

typedef vector<string> vs;

typedef long double ld;

#define _GLIBCXX_DEBUG

#define REP(i,n) for (int i = 0; i < (n); ++i)
#define REPD(i,n) for (int i = (n-1); i >= 0; --i)
#define FORE(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORED(i, s, n) for (int i = (s); i >= (int)(n); i--)
#define debug(x) cerr << #x << ": " << x << '\n'
#define debug2(x, y) cerr << #x << ": " << x << ", " << #y << ": " << y << '\n'
#define debug3(x, y, z) cerr << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << '\n'
#define debugs(s) cerr << s << "\n"
#define hyphen() cerr << "--\n"

#define ALL(vec) (vec).begin(), (vec).end()
#define REVALL(vec) (vec).rbegin(), (vec).rend()

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

#define fst first
#define snd second
#define pb push_back
#define mk(x,y) make_pair((x),(y))

// http://ehafib.hatenablog.com/entry/2015/12/23/164137
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
int qpm(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
// gcd : O(logN)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a, int b) { return a / gcd(a, b) * b; }

#define sz(v) int(v.size())

// x1, x2ライブラリとの被りを避ける
#define x1 x192837465
#define x2 x123456789
#define y1 y192837465
#define y2 y123456789

// typo
#define itn int
#define reutrn return
#define reutnr return
#define srting string

#define make(type, x) type x; cin>>x;
#define make2(type, x, y) type x, y; cin>>x>>y;
#define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
#define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;

int ctoi(const char c){
    if('0' <= c && c <= '9') return (c-'0');
    return -1;
}

#define uniq(v) (v).erase(unique(ALL((v))), (v).end());

// area of (0, 0)(a, b)(c, d)
double area(double a, double b, double c, double d){
    return abs(a * d - b * c) / 2.0;
}

const int PREC = 10;
#define coutf(val) cout << fixed << setprecision(PREC) << (val) << endl;

const int MOD = (int)1e9 + 7;
const int INF = numeric_limits<int>::max();

signed main() {
    make3(int, N, A, B);

    if ((N == 1 && A != B) || A > B) {
        cout << 0 << endl;
        return 0;
    }

    // maxからminまで柔軟に動かせるので、maxとminがわかればOK
    int min_sum = A * (N-1) + B;
    int max_sum = A + B * (N-1);

    int ans = max_sum - min_sum + 1;
    cout << ans << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
//#define all(v) v.begin(), v.end()
//bool chmin(ll & a, ll  b) { if (b < a) { a = b; return 1; } return 0; }
//bool chmax(ll & a, ll b) { if (b > a) { a = b; return 1; } return 0; }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
//const ll MAX_N=500010;
ll a, b, c, d, e, f, h, k, l, m, n, p, q, r, t, w, x, y, z, ans;
int main() {
  cin >> n >> a >> b;
  c = a+b;
  
  cout << (n/c)*a+min(n%c,a) << endl;
  return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL dp[2];
string s;

int main() {
	cin >> s;
	
	dp[0] = s[0] - '0' - 1;
	dp[1] = s[0] - '0';
	incID(i, 1, s.size()) {
		dp[0] += 9;
		dp[1] += s[i] - '0';
	}
	
	cout << max(dp[0], dp[1]) << endl;
	
	return 0;
}


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

int main(){

int R;
int G;
int B;
int N;

cin >> R >> G >> B >> N;

int i = -1;
int j = -1;
int k = -1;
int times = 0;

while (true){
    i += 1;
    if (i*R > N){
        i = -1;
        break;
    }
        
    while (true){          
        j += 1;
        if ((i*R + j*G) > N){
            j = -1;
            break;
        }
        if ((N - i*R - j*G) % B == 0){
          times++;
        }
    }
}
                
cout << times << endl;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
f = int(input())
g = int(input())
h = int(input())
i = int(input())
j = int(input())


print(a+b+c+d+e+f+g+h+i+j)



Measured memory_bytes: 5588
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int s,w;
    cin>>s>>w;
    if(s<=w) cout<<"unsafe"<<endl;
    else cout<<"safe"<<endl;
    return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int>s1,s2,s3;
    s1.insert(1);
    s1.insert(3);
    s1.insert(5);
    s1.insert(7);
    s1.insert(8);
    s1.insert(10);
    s1.insert(12);
    s2.insert(4);
    s2.insert(6);
    s2.insert(9);
    s2.insert(11);
    s3.insert(2);
    int x,y;
    cin>>x>>y;
    if(s1.find(x)!=s1.end()&&s1.find(y)!=s1.end()){
        cout<<"Yes"<<endl;
    }
    else
    if(s2.find(x)!=s2.end()&&s2.find(y)!=s2.end()){
        cout<<"Yes"<<endl;
    }
    else
    if(s3.find(x)!=s3.end()&&s3.find(y)!=s3.end()){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

}

Measured memory_bytes: 3540
void main() {
	auto N = readAs!ulong;
	auto ip = readAs!(int[]), A = ip[0], B = ip[1];
	int a = A, b = B;
	foreach(i; 0..(N % 12)) {
		if(i % 2 == 0) {
			A = A - B;
		} else B = A + B;
	}
	writefln("%d %d", A, B);
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 2516