akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define DEC(i, s) for (int i = (s); i >= 0; i--)

#define SIZE(v) (int)((v).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define FIND(m, w) ((m).find(w) != (m).end())

struct Edge {
  int from;
  int to;
  double dist;
  int speed;
  Edge() {;}
  Edge(int f, int t, double d, int s) : from(f), to(t), dist(d), speed(s) {;}
  bool operator<(const Edge &rhs) const { return dist > rhs.dist; }
};

double visit[40][40][40];
vector<Edge> edge[40];

int main() {
  int n, m, s, g;
  while (scanf("%d %d", &n, &m), n|m) {
    scanf("%d %d", &s, &g);
    s--; g--;
    REP(i, n) { edge[i].clear(); }
    REP(i, m) {
      int f, t, c;
      double d;
      scanf("%d %d %lf %d", &f, &t, &d, &c);
      f--; t--;
      edge[f].push_back(Edge(f, t, d, c));
      edge[t].push_back(Edge(t, f, d, c));
    }
    priority_queue<Edge> que;
    MEMSET(visit, false);
    que.push(Edge(32, s, 0, 1));
    while (!que.empty()) {
      Edge node = que.top();
      que.pop();
      if (visit[node.from][node.to][node.speed]) { continue; }
      visit[node.from][node.to][node.speed] = true;
      if (node.to == g && node.speed == 0) {
        printf("%.4lf\n", node.dist);
        goto next;
      }
      if (node.speed == 0) { continue; }
      int from = node.to;
      REP(i, edge[from].size()) {
        int to = edge[from][i].to;
        FOREQ(s, -1, 1) {
          int ns = node.speed + s;
          if (to == node.from || visit[from][to][ns] || node.speed > edge[from][i].speed) { continue; }
          double ndist = node.dist + edge[from][i].dist / (double)node.speed;
          que.push(Edge(from, to, ndist, ns));
        }
      }
    }
    puts("unreachable");
next:;
  }
}

Measured memory_bytes: 8528
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		String a = stdIn.next();
		
		if(a.equals("ABC")){
			System.out.println("ARC");
		}else{
			System.out.println("ABC");
		}
	
		
	}
}

Measured memory_bytes: 35608
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <utility>
#include <functional>
#include <queue>
#include <cmath>
#include <numeric>
#include <map>
#define REP(i, N) for(int i=0; i<N; i++)
using namespace std;

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

int main() {
	int N, D;

	cin >> N >> D;
      
      int re = 0;
  
  int l = 1, r = N;
  
  while (l <= r) {
    re++;
    l = l + D + 1 + D;
    if (l > r) break;
    
    re++;
    r = r - D - 1 - D;
  }

	cout << re << endl;

	return 0;
}


Measured memory_bytes: 256
S = input().strip()
K = int(input())

A = ''
B = ''
C = ''

A_char = S[0]
C_char = S[-1]

for c in S:
    if c == A_char:
        A += c
    else:
        break

for c in S[::-1]:
    if c == C_char:
        C += c
    else:
        break

B = S[len(A):-len(C)]

# add End token
A += 'E'
B += 'E'
C += 'E'

def subst_counter(s):
    counter = 0
    tmp_counter = 1
    in_cont = False
    prev_char = ''
    for c in s:
        #print(prev_char)
        #print(tmp_counter)
        if c == prev_char:
            in_cont = True
            tmp_counter += 1
        elif c != prev_char and in_cont:
            counter += int(tmp_counter/2)
            tmp_counter = 1
            in_cont = False
            prev_char = c
        else:
            prev_char = c
    return counter

if B == 'E':
    if A == 'E': # ''
        print(0)
    elif A[0] == C[0]: # 'aaaa'
        N = (len(A) - 1)*K
        print(int(N/2))
    else: # 'aaaccc'
        N = subst_counter(A) + subst_counter(C)
        N = N * K
        print(N)
else:
    if A[0] == C[0]: # 'aaaxyzaaa'
        N_B = subst_counter(B)*K
        N_CA = int(((len(A)-1) + (len(C)-1))/2)*(K-1)
        print(N_B + N_CA + int((len(A)-1)/2) + int((len(C)-1)/2))
    else:
        N_A = subst_counter(A) * K
        N_B = subst_counter(B) * K
        N_C = subst_counter(C) * K
        print(N_A + N_B + N_C)

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

#define ll long long
#define ull unsigned long long

bool isPalindrome(string s) {
    string t(s.rbegin(), s.rend());
    return s == t;
}

int main(void) {
    ll A, B;
    ll temp;
    cin >> A >> B;
    temp = 1;
    temp += (B - A) / (A - 1);
    if(A + (temp - 1) * (A - 1) < B) temp += 1;
    cout << temp << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

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

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

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    char X,Y;
    cin >> X >> Y;
    if(X == Y){
        cout << "=" << "\n";
    }else{
        cout << (X > Y ? ">" : "<") << "\n";
    }
}

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

#define PI 3.141592653589
#define ll long long int
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define vv vector
#define all(v) (v).begin(),(v).end()
int MOD=1e9+7;
ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
ll min(ll a,ll b){return (a>b)?b:a;}
ll max(ll a,ll b){return (a>b)?a:b;}
int prime[1000001];

void SieveOfEratosthenes(int n) 
{ 
    for (int p=2; p<=n; p++) 
    { 
        if (prime[p] == 0) 
        { 
            for (int i=p; i<=n; i += p) 
                prime[i] = p; 
        } 
    } 
}
ll fact[100010];
ll finv[100010];
void factorial(int n){
    fact[0]=1;
    finv[0]=1;
    for(int i=1;i<=n;i++)
        fact[i]=fact[i-1]*i,fact[i]%=MOD,finv[i]=fermat_inv(fact[i]);
}
ll ncr(ll n,ll r)
{
    if(n<r)
        return 0;
    else{
        ll x=finv[r]*finv[n-r]%MOD;
        return fact[n]*x%MOD;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int te=1;
    //cin>>te;
    SieveOfEratosthenes(1000000);
    //factorial(100005);
    while(te--){
        ll n;
        cin>>n;
        ll ans=0;
        for(ll i=1;i<n;i++){
            ll y=i;
            ll cnt=1;
            ll j=prime[y];
            //cout<<j<<'\n';
            while(y>1&&j>1){
                ll c=0;
                while(y%j==0)
                    y/=j,c++;
                cnt*=(c+1);
                j=prime[y];
            }
            ans+=cnt;
        }
        cout<<ans;
    }
}


Measured memory_bytes: 7560
// C++ program to compute LCM of array elements modulo M 
#include <bits/stdc++.h> 
#define F first 
#define S second 
#define MAX 10000003 
using namespace std; 
#define int long long 
typedef long long ll; 
const int mod = 1000000007; 

int prime[MAX]; 
unordered_map<int, int> max_map; 

// Function to return a^n 
int power(int a, int n) 
{ 
	if (n == 0) 
		return 1; 
	int p = power(a, n / 2) % mod; 
	p = (p * p) % mod; 
	if (n & 1) 
		p = (p * a) % mod; 
	return p; 
} 
int inv(int a){
    return power(a,mod-2);
}
// Function to find the smallest prime factors 
// of numbers upto MAX 
void sieve() 
{ 
	prime[0] = prime[1] = 1; 
	for (int i = 2; i < MAX; i++) { 
		if (prime[i] == 0) { 
			for (int j = i * 2; j < MAX; j += i) { 
				if (prime[j] == 0) { 
					prime[j] = i; 
				} 
			} 
			prime[i] = i; 
		} 
	} 
} 

// Function to return the LCM modulo M 
ll lcmModuloM(const int* ar, int n) 
{ 

	for (int i = 0; i < n; i++) { 
		int num = ar[i]; 
		unordered_map<int, int> temp; 

		// Temp stores mapping of prime factor to 
		// its power for the current element 
		while (num > 1) { 

			// Factor is the smallest prime factor of num 
			int factor = prime[num]; 

			// Increase count of factor in temp 
			temp[factor]++; 

			// Reduce num by its prime factor 
			num /= factor; 
		} 

		for (auto it : temp) { 

			// Store the highest power of every prime 
			// found till now in a new map max_map 
			max_map[it.first] = max(max_map[it.first], it.second); 
		} 
	} 

	ll ans = 1; 

	for (auto it : max_map) { 

		// LCM is product of primes to their highest powers modulo M 
		ans = (ans * power(it.F, it.S)) % mod; 
	} 

	return ans; 
} 

// Driver code 
int32_t main() 
{ 
	sieve(); 
	int n;
	cin>>n;
	ll arr[n];
	for(int i=0;i<n;++i)
	cin>>arr[i];
	ll pp=lcmModuloM(arr, n);
	int sum=0;
	for(int i=0;i<n;++i){
	    ll xp=pp*inv(arr[i]);
	    xp%=mod;
	    sum+=xp;
	    sum%=mod;
	}
	cout<<sum;
	return 0; 
} 


Measured memory_bytes: 78848
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append((v, w))
    graph[v].append((u, w))
qu = [0]
colors = [0 for _ in range(N)]
visited = set()
while len(qu) != 0:
    cur = qu.pop()
    visited.add(cur)
    for nxt, weight in graph[cur]:
        if nxt not in visited:
            colors[nxt] = (colors[cur] + weight)%2
            qu.append(nxt)
for v in colors:print(v)


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

int main() {
  int n, m;
  cin >> n >> m;
  int ball_cnt[n];
  bool red[n];
  for (int i = 0; i < n; i++) {
    ball_cnt[i] = 1;
    red[i] = false;
  }
  red[0] = true;

  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    if (red[x]) red[y] = true;

    ball_cnt[x]--;
    ball_cnt[y]++;
    if (!ball_cnt[x]) red[x] = false;
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (red[i]) ans++;
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3980
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
#n = int(input())
h, w, K = map(int, sys.stdin.readline().split())
#s = input()
#A = list(map(int, sys.stdin.readline().split()))

l = []
for i in range(h):
    l.append(list(input()))

ans = 0
for i in range(2**(h+w)):
    b = format(i, "0"+str(h+w)+"b")
    m = copy.deepcopy(l)
    for j in range(h):
        if b[j] == "1":
            for k in range(w):
                m[j][k] = "R"

    for j in range(w):
        if b[h+j] == "1":
            for k in range(h):
                m[k][j] = "R"

    cnt = 0
    for j in range(h):
        for k in range(w):
            if m[j][k] == "#":
                cnt += 1



    if cnt == K:
        ans += 1


print(ans)
        


Measured memory_bytes: 10156
import java.util.*;

/*

*/



public class Main {
    public static void main(String[] args){

        //スキャン
        Scanner s = new Scanner(System.in);
        float  sumLen =s.nextInt();
        float devi  =sumLen/3;
        float  ans = devi*devi*devi;
        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
N = int(input())
W = list(map(int,input().split()))
accumsum = []
unko = 0
for i in range(N):
    unko += W[i]
    accumsum.append(unko)

min = float("inf")
last = accumsum[-1]
for i in range(N-1):
    if abs(last-2*accumsum[i]) <= min:
        min = abs(last-2*accumsum[i])
print(min)

Measured memory_bytes: 3064
import itertools
A=[int(i) for i in input().split()]
S=list(itertools.permutations(A,3))
ans=30000
for sg in S:
    tmp=0
    tmp+=abs(sg[1]-sg[0])
    tmp+=abs(sg[2]-sg[1])
    if tmp<ans:
        ans=tmp
print(ans)


Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long A = long.Parse(str[0]);
		long B = long.Parse(str[1]);
		long ans = 0;
		for(var i=1;i<=40;i++){
			long C = (long)Math.Pow(2,i);
			long a = A%(C*2);
			long b = B%(C*2);
			if(a<C && b>=C){
				ans += (b-C+1)%2*C;
			} else if(a>=C && b<C){
				ans += (C*2-a)%2*C;
			} else if(a>=C && b>=C){
				ans += (Math.Abs(b-a)+1)%2*C;
			}
		}
		long a1 = A%4;
		long b1 = B%4+4;
		long c1 = 0;
		for(var i=a1;i<=b1;i++){
			if(i%2==1){
				c1 = (c1+1)%2;
			}
		}
		ans += c1;
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 13140
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    cin >> N >> M;
    string S;
    cin >> S;
    ll pos = N;
    vector<ll> res;
    vector<ll> maru;
    rep(i,0,N+1){
        if(S[i] == '0') maru.push_back(i);
    }
    while(pos != 0){
        ll lv = max(0LL, pos - M);
        ll p = lower_bound(maru.begin(), maru.end(), lv) - maru.begin();
        ll val = maru[p];
        if(maru[p] == pos){
            print(-1);
            return 0;
        }
        res.push_back(pos - maru[p]);
        pos = maru[p];
    }
    reverse(res.begin(), res.end());
    printa(res, res.size());

    

}

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

using namespace std;

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main()
{
	int n,d;
	cin>>n>>d;
	d=2*d+1;
	cout<<(n+d-1)/d<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;

int main()
{
    int n;
    double x[100], y[100], sum1 = 0, sum2 = 0, sum3 = 0, max;
    double D[100];
    cin >> n;
    for (int i = 0; i<n; i++)cin >> x[i];
    for (int i = 0; i<n; i++)cin >> y[i];
    max = fabs(x[0] - y[0]);
    for (int i = 0; i < n; i++)
        D[i]=fabs(x[i] - y[i]);
    for (int i = 0; i<n; i++) {
        sum1 += D[i];
        sum2 += fabs(D[i]*D[i]);
        sum3 += fabs(D[i]*D[i]*D[i]);
        if (max<D[i])max = D[i];
    }
    printf("%.8f\n", sum1);
    printf("%.8f\n", sqrt(sum2));
    printf("%.8f\n", pow(sum3, 1.0 / 3.0));
    printf("%.8f\n", max);
    return 0;
}

Measured memory_bytes: 1288
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)


@lru_cache(maxsize=1000000)
def get_ways(n):
    if n == 1 or n == 2:
        return n
    elif n == 0:
        return 1
    elif n == -1:
        return 0
    else:
        return get_ways(n - 2) + get_ways(n - 1)


N, M = map(int, input().split())
ans = 1
tmp = 0
for i in range(M):
    a = int(input())
    ans *= get_ways(a - tmp - 1)
    tmp = a + 1
ans *= get_ways(N - tmp)
print(ans % 1000000007)


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

using namespace std;
using ll = long long int;
constexpr ll M = 1e9 + 7;
inline ll sum_1(const ll n) { return ((n * (n + 1)) / 2) % M; }
inline ll sum_2(const ll n) { return ((n * (n + 1) * (2 * n + 1)) / 6) % M; }
inline ll sum_3(const ll n) { return (((n * (n + 1)) / 2) % M * ((n * (n + 1)) / 2) % M) % M; }
inline ll sum_1(const ll i, const ll j) { return (sum_1(j) - sum_1(i - 1) + M) % M; }
inline ll sum_2(const ll i, const ll j) { return (sum_2(j) - sum_2(i - 1) + M) % M; }
inline ll sum_3(const ll i, const ll j) { return (sum_3(j) - sum_3(i - 1) + M) % M; }

void solve() {
    ll n;
    cin >> n;

    /**
     *  K  2......N
     *  
     *  If K|N, replace N/K; no other choice
     *  otherwise, replace N-K
     * 
     * For K == N,
     *      op : 1
     * if K|N, then N/K until cannot divide
     * N%K == 1
     * N == 1 mod K
     * N-1 == 0 mod K
     * K divides N-1 : find divisor of N-1...
     */
    ll ans = 0;
    
    /**
    for (ll i = 2; i <= n; ++i) {
        ll t = n;
        ll k = i;
        while (t%k == 0) {
            t = t/k;
        }
        t = t%k;
        if (t==1) {
            ans++;
        }
    }
    */
   for (ll i = 1; i*i <= n; ++i) {
       ll k = i;
       if (n%k == 0) {
           ll _n = n;
           //k is a divisor
           while (k != 1 && _n%k==0) {
               _n = _n/k;
           }
           _n = _n%k;
           if (k != 1 && _n == 1) {
               ++ans;
           }

           if (n != k*k) {
                //n/k is a divisor
                k = n/k;
                _n = n;
                while (k != 1 && _n%k==0) {
                    _n = _n/k;
                }
                _n = _n%k;
                if (k != 1 && _n == 1) {
                    ++ans;
                }
           }
       }
   }

   for (ll i = 1; i*i <= n-1; ++i) {
       ll k = i;
       if ((n-1)%k == 0) {
           if (k != 1) {
               ++ans;
           }
           if ((n-1) != k*k) {
               k = (n-1) / k;
               if (k != 1) {
                   ++ans;
               }
           }
       }
   }

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef D_LOCAL
        freopen("in.in", "r", stdin);
        freopen("out.out", "w", stdout);
    #endif

    solve();

    return 0;
}

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

int main() {
  string s; cin >> s;
  string ans = "ABC";
  if (s == "ABC") ans = "ARC";
  cout << ans << endl;
}

Measured memory_bytes: 3628
n,k = map(int, input().split())
a = list(map(int,input().split()))
aa = sorted(a)
c = 0
d = 0
for i in range(n):
  c += len([l for l in a[i:] if l < a[i]]) % (10**9+7)
  c = c % (10**9+7)
  d += aa.index(a[i])
  d = d % (10**9+7)
c *= k
K = (0+k-1)*k // 2
c += (d*K) % (10**9+7)
c = c % (10**9+7)
print(c)

Measured memory_bytes: 3188
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

signed main(){
    FastIO;
    int n;
    cin>>n;
    int f[n+5]{0};
    rep(i,1,n-1){
        int x;
        cin>>x;
        f[x]++;
    }
    rep(i,1,n) cout<<f[i]<<'\n';
    return 0;
}


Measured memory_bytes: 4424
def reconstruct(l, r):
    if l >= r:
        return
    root = pre_list.pop(0)
    center = in_list.index(root)
    reconstruct(l, center) # 左部分木
    reconstruct(center+1, r) #右部分木
    ans_list.append(str(root))
    
N = int(input())
pre_list = list(map(int, input().split()))
in_list = list(map(int, input().split()))

#answer_output
ans_list = []
reconstruct(0, N)
print(" ".join(ans_list))



Measured memory_bytes: 5596
#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  long long int n,a,b;
  cin>>n>>a>>b;
  if(a>b||(n==1&&a!=b)){
    cout<<"0"<<endl;
  }else{
    long long int mini=a*(n-1)+b;
    long long int maxi=a+(n-1)*b;
    cout<<maxi-mini+1<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <list>
#include <stack>
#include <math.h>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

#define ll long long
#define ull unsigned long long

#define	max	1000000007

class mod
{
public:
	ll val;

	mod(ll v)
	{
		val = v % max;
	}

	mod()
	{
		val = 0;
	}

	void operator -=(const mod &v)
	{
		val -= v.val;

		if (val < 0)
			val += max;		
	}

	void operator +=(const mod &v)
	{
		if (val + v.val >= max)
			val -= max;
		val += v.val;
	}

	void operator +=(ll &v)
	{
		if (val + v >= max)
			val -= max;
		val += v;
	}

	void operator *=(const mod &v)
	{
		val *= v.val;
		val %= max;
	}

	void operator *=(ll &v)
	{
		val *= v;
		val %= max;
	}

	ll modinv(ll a)
	{
		ll b = max, u = 1, v = 0;
		while (b) 
		{
			ll t = a / b;
			a -= t * b; swap(a, b);
			u -= t * v; swap(u, v);
		}
		u %= max;
		if (u < 0)
			u += max;
		return u;
	}

	void operator /=(const mod &v)
	{
		val *= modinv(v.val);
		val %= max;
	}

	void operator /=(ll &v)
	{
		val *= modinv(v);
		val %= max;
	}
};

vector<int> xm, ym;
int x, y;

int main()
{
	int n, k;
	int s;
	cin >> n >> k >> s;
	const int m = 1000000000;

	if (s == 1)
	{
		for (int i = 0; i < k; i++)
			printf("%d ", 1);
		for (int i = k; i < n; i++)
			printf("%d ", m);

	}
	else if (n != k)
	{
		for (int i = 0; i < k + 1; i++)
			printf("%d ", s / 2 + (s % 2 == 1 && i % 2 == 1 ? 1 : 0));
		for (int i = k + 1; i < n; i++)
			printf("%d ", (s != m ? m : 1));
	}
	else
	{
		for (int i = 0; i < n; i++)
			printf("%lld ", s);
	}

	//printf("%d", r);
	return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <cctype>
#include <string>

using namespace std;

string s;

bool check(int a, int b)
{
	int i;
	
	if (s[a] != '-')
	{
		return false;
	}
	for (i = 0; i < a; ++i)
	{
		if (!isdigit(s[i]))
		{
			return false;
		}
	}
	for (i = a + 1; i < s.size(); ++i)
	{
		if (!isdigit(s[i]))
		{
			return false;
		}
	}
	
	return true;
}

int main(void)
{
	int a, b;
	
	scanf("%d%d", &a, &b);
	cin >> s;
	
	printf("%s", check(a, b) ? "Yes" : "No");
	
	return 0;
}

Measured memory_bytes: 256
#coding : utf8


"""
@param {int}
@return {int}
"""
def calcTakahashi(a,b):

    if( a <= b):
        return a
    else:
        return (a-1)

    # takahashi_count = 0
    # for i in range(1,a+1):
    #     for j in range(1,b+1):
    #         if( i == j ):
    #                 takahashi_count += 1
    #
    # return takahashi_count

if __name__ == '__main__':

    a,b = map(int,input().split())

    print(calcTakahashi(a,b))


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
using namespace std;
long long mod = 1e9+7;
int n, k; 

int main(void) {
  cin >> n >> k;
  // if(k == 0) {
  //   cout << 0 << endl;
  //   return 0;
  // }
  // if(n == 2) {
  //   cout << -1 << endl;
  //   return 0;
  // }
  int d = (n-1) * (n-2) / 2;
  if(k > d) {
    cout << -1 << endl;
    return 0;
  }
  vector<pair<int, int> > p;
  for(int i=2; i<=n; i++) {
    p.push_back({1, i});
  }
  for(int i=2; i<=n; i++) {
    for(int j=i+1; j<=n; j++) {
      if(k == d) {
        cout << p.size() << endl;
        for(int l=0; l<p.size(); l++) {
          cout << p[l].first << " " << p[l].second << endl;
        }
        return 0;
      }
      d--;
      p.push_back({i, j});
    }
  }
  if(k == d) {
    cout << p.size() << endl;
    for(int l=0; l<p.size(); l++) {
      cout << p[l].first << " " << p[l].second << endl;
    }
    return 0;
  }

  cout << -1 << endl;
  return 0;
}

// EOF


Measured memory_bytes: 384
import copy
N = int(input())
A = list(input().split())
B = []
for i in A:
    temp = list(i)
    B.append(temp)
C = copy.copy(B)

def bubble_sort(A):
    for i in range(len(A)):
        for j in range(len(A)-1,i,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
    return A

def selection_sort(A):
    for i in range(len(A)):
        minj = i
        for j in range(i+1,len(A)):
            if int(A[minj][1]) > int(A[j][1]):
                minj = j
        A[minj],A[i] = A[i],A[minj]
    return A

ans = []
for k in bubble_sort(B):
    ans.append(k[0]+k[1])
print(*ans)
print("Stable")

ans_2 = []
for k in selection_sort(C):
    ans_2.append(k[0]+k[1])

print(*ans_2)

if ans == ans_2:
    print("Stable")
else:
    print("Not stable")


Measured memory_bytes: 6344
K = int(input())
S = input()

s = len(S)
mod = int(1e9+7)


n = pow(26, K, mod)
ans = n

for i in range(K):
    n = n*25*(s+i)*pow(26*(i+1),-1,mod)%mod
    ans = (ans +n) % mod


print(ans)

Measured memory_bytes: 10984
import java.util.Scanner;

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



Measured memory_bytes: 26372
#include <iostream>
#include <math.h>
#define ll long long int
using namespace std;

int main(){
    int N;
    cin >> N;
    int a[110];
    int min=100;
    int max=-100;
    for(int i=0;i<N;++i){
        cin >> a[i];
        if(a[i] > max) max = a[i];
        if(a[i] < min) min = a[i];
    }

    ll ans=1000000000000;
    for(int j=min; j<= max; j++){
        ll cost = 0;
        for(int i=0; i<N; i++){
            cost += pow(j-a[i],2);
        }
        if(ans >= cost){
            ans = cost;
        }
    }
    cout << ans <<endl;

    return 0;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
g=[[] for _ in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  g[A-1].append(B-1)
  g[B-1].append(A-1)
from collections import deque  
queue = deque([0])
d = [None] * N
d[0] = 0 
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = d[v] + 1
      queue.append(i)
  
l=[0]*(N-1)
for i in range(1,N):
  for j in g[i]:
    if d[j]==(d[i]-1):
      l[i-1]=j+1
      break
if 0 in l:
  print('No')
else:
  print('Yes')
  for i in range(len(l)):
    print(l[i])

Measured memory_bytes: 37696
#include <iostream>
using namespace std;
int main() {
	int a, b;
	char op;
	bool condition = true;
	while (condition) {
		cin >> a >> op >> b;
		switch (op) {
			case '+':
				cout << a + b << endl;
				break;
			case '-':
				cout << a - b << endl;
				break;
			case '*':
				cout << a * b << endl;
				break;
			case '/':
				cout << a / b << endl;
				break;
			case '?':
				condition = false;
		}
	}
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

template<typename T>bool chkmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool chkmin(T &a,T b){return (a>b)?a=b,1:0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
vector<int>G[1000005];
int tree[4000005];
int p[1000005];
int q[1000005];
int in[1000005];
priority_queue<int ,vector<int> ,greater<int> >Q;
#define mid ((l+r)>>1)
void update(int rt,int l,int r,int pos,int val){
   if(l==r){
     tree[rt]=val;
	 return ;
   }
   if(pos<=mid)update(rt<<1,l,mid,pos,val);
   else update(rt<<1|1,mid+1,r,pos,val);
   tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);
}
int now;
void query(int rt,int l,int r,int L,int R){
	if(L>R)return ;
	if(L<=l&&r<=R){
		chkmin(now,tree[rt]);
	   return ;
	}
	if(L<=mid)query(rt<<1,l,mid,L,R);
	if(R>mid)query(rt<<1|1,mid+1,r,L,R);
	return ;
}
int n,k;
int ans[1000005],top;
int main () {
#ifndef ONLINE_JUDGE
//file("agc001f");
#endif
    Set(tree,0x3f3f3f3f);
    n=read();
	k=read();
    F(i,1,n){
	  p[i]=read();
	  q[p[i]]=i;
	}
    f(i,n,1){
	   now=0x3f3f3f3f;
		query(1,1,n,q[i]+1,min(q[i]+k-1,n));
	   if(now!=0x3f3f3f3f){
	       G[q[i]].push_back(q[now]);
           in[q[now]]++;
	   }
	   now=0x3f3f3f3f;
		   query(1,1,n,max(1,q[i]-k+1),q[i]-1);
	   if(now!=0x3f3f3f3f){
	      G[q[i]].push_back(q[now]);
		  in[q[now]]++;
	   }
	   update(1,1,n,q[i],i);
	}
    F(i,1,n)if(!in[i])Q.push(i);
	while(!Q.empty()){
		int x=Q.top();
		Q.pop();
	    ans[x]=++top;
		for(int v:G[x]){
		    if(--in[v]==0)Q.push(v);
		}
	}
	F(i,1,top)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 73856
#include<iostream>
using namespace std;
int cnt[10001];
int N;
main()
{
	cin>>N;
	for(int x=1;x<=100;x++)for(int y=1;y<=100;y++)for(int z=1;z<=100;z++)
	{
		int t=x*x+y*y+z*z+x*y+y*z+z*x;
		if(t<=N)cnt[t]++;
	}
	for(int i=1;i<=N;i++)cout<<cnt[i]<<endl;
}


Measured memory_bytes: 3592
numerosStr = input().split(" ")
numero=[]
for j in numerosStr:
    numero.append(int(j))

if numero[0] >= 13:
    print(numero[1])
elif numero[0] >= 6 and numero[0] <=12:
    print(int(numero[1]/2))
elif numero[0]<=5:
    print(0)

Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

int N;
vector<int> A;
map<int,int> number;
int zeros;

string solve(void) {
    if(zeros == N)
        return "Yes";

    if(number.size() == 1 && zeros == N / 3)
        return "Yes";

    if(number.size() != 3)
        return "No";

    vector<int> X;
    for(auto v:number) {
        X.push_back(v.first);
        if(v.second != N / 3)
            return "No";
    }

    if((X[0]^X[1]^X[2]) == 0)
        return "Yes";

    return "No";
}

int main(void) {
    cin>>N;

    for(int i = 0;i < N;i++) {
        int a;
        cin>>a;
        if(a == 0)
            zeros++;
        else
            number[a]++;
        A.push_back(a);
    }

    cout<<solve()<<endl;
    return 0;
}




Measured memory_bytes: 4216
/*

*/

#include<bits/stdc++.h>
using namespace std;
typedef pair<long,long>P;
int main(){
  long N,M;cin>>N>>M;
  vector<long>A(N),B(N),C(N),D(M),E(M),F(M);
  set<long>xs,ys;
  for(long i=0;i<N;i++){
    cin>>A[i]>>B[i]>>C[i];
    xs.insert(A[i]);
    xs.insert(B[i]);
    ys.insert(C[i]);
  }
  for(long i=0;i<M;i++){
    cin>>D[i]>>E[i]>>F[i];
    ys.insert(E[i]);
    ys.insert(F[i]);
    xs.insert(D[i]);
  }
  vector<long>X,Y;//id->実座標
  map<long,long>IX,IY;// 実座標->id
  X=vector<long>(xs.begin(),xs.end());sort(X.begin(),X.end());
  Y=vector<long>(ys.begin(),ys.end());sort(Y.begin(),Y.end());
  for(long i=0;i<X.size();i++)IX[X[i]]=i;
  for(long i=0;i<Y.size();i++)IY[Y[i]]=i;
  
  vector<vector<long>>R(2*X.size()+1,vector<long>(2*Y.size()+1));
  //実際の白黒
  vector<vector<long>>Q(2*X.size()+1,vector<long>(2*Y.size()+1));
  //面積
  
  for(long i=0;i<N;i++){
    for(long j=IX[A[i]]*2+1;j<=IX[B[i]]*2+1;j++)R[j][IY[C[i]]*2+1]=1;
  }
  for(long i=0;i<M;i++){
    for(long j=IY[E[i]]*2+1;j<=IY[F[i]]*2+1;j++)R[IX[D[i]]*2+1][j]=1;
  }
  
  for(long i=0;i<X.size()-1;i++)for(long j=0;j<Y.size()-1;j++){
    Q[i*2+2][j*2+2]=(X[i+1]-X[i])*(Y[j+1]-Y[j]);
  }
  long W=X.size()*2+1;
  long H=Y.size()*2+1;
  long sx=X.size()-1;while(X[sx]>0)sx--;
  long sy=Y.size()-1;while(Y[sy]>0)sy--;
  queue<P>q;q.push(P(
    (X[sx]==0?2*sx+1:2*sx+2),
    (Y[sy]==0?2*sy+1:2*sy+2))
  );
  vector<vector<long>>U(2*X.size()+1,vector<long>(2*Y.size()+1));
  U[(X[sx]==0?2*sx+1:2*sx+2)][(Y[sy]==0?2*sy+1:2*sy+2)]=1;
  
  
  while(q.size()){
    P p=q.front();q.pop();
    if(p.first>0&&
       R[p.first-1][p.second]==0&&
       U[p.first-1][p.second]==0){
      U[p.first-1][p.second]=1;
      q.push(P(p.first-1,p.second));
    }
    if(p.first<W-1&&
       R[p.first+1][p.second]==0&&
       U[p.first+1][p.second]==0){
      U[p.first+1][p.second]=1;
      q.push(P(p.first+1,p.second));
    }
    if(p.second>0&&
       R[p.first][p.second-1]==0&&
       U[p.first][p.second-1]==0){
      U[p.first][p.second-1]=1;
      q.push(P(p.first,p.second-1));
    }
    if(p.second<H-1&&
       R[p.first][p.second+1]==0&&
       U[p.first][p.second+1]==0){
      U[p.first][p.second+1]=1;
      q.push(P(p.first,p.second+1));
    }  
  }
  if(U[0][0]==1){cout<<"INF";return 0;}
  long ans=0;
  for(long i=0;i<W;i++)for(long j=0;j<H;j++)if(U[i][j])
    ans+=Q[i][j];
  cout<<ans;
    
}

Measured memory_bytes: 848784
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  ll N; cin >> N;
  ll ans = 0;

  for (ll i = 1; i <= N; i++){
    ll now = N / i;
    ans += (i + now * i) * now / 2;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3648
#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;
  rep(i, 5){
    cin >> x;
    if(x == 0) cout << i+1 << endl;
  }
  
return 0;
}

Measured memory_bytes: 3544
#include<bits/stdc++.h>
using namespace std;
const long long MX=1e18;
const long long MD=1e9+7;
const int N=1e5+5;
int n,m,dp[100005],ans;
bool vis[100005];
vector<int>gr[100005];
void dfs(int x)
{
    vis[x]=true;
    dp[x]=0;
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i];
        if(vis[u]==false)dfs(u);
        dp[x]=max(dp[x],dp[u]+1);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        gr[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==false)dfs(i);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}


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

int main()
{
  int n,k,m;
  while(cin >> n >> k >> m, (n || k || m))
    {
      vector<int> stone;
      for(int i=1;i<=n;i++)
	stone.push_back(i);
 
      m--;
      for(;stone.size() > 1;)
	stone.erase(stone.begin()+m),m = (m+k-1)%stone.size();
      cout << stone[0] << endl;
    }    
  return 0;
}

Measured memory_bytes: 3204
#include<iostream>
#include<cstdlib>
#include<set>
#include<queue>
using namespace std;
int vx[]={ 1, 1, 0, 0,-1,-1};
int vy[]={ 0,-1, 1,-1, 1, 0};
struct P{
	int x,y;
};
int n,k;
struct Snake{
	int step;
	P body[8];
	bool operator<(const Snake&b)const{
		for(int i=0;i<n;i++){
			if(body[i].x!=b.body[i].x)return body[i].x<b.body[i].x;
			if(body[i].y!=b.body[i].y)return body[i].y<b.body[i].y;
		}
		return false;
	}
	P& operator[](int i){
		return body[i];
	}
};
queue<Snake> que;
int X,Y;
int ans;
P rock[100];
Snake body;
set<Snake> s;
int distance(){
	int dis, dx=X-body[0].x, dy=Y-body[0].y;
	if(dx*dy<0)dis= abs(dx)<abs(dy)? abs(dy):abs(dx);
	else dis= abs(dx)+abs(dy);
	return dis;
}
inline bool overlap(P &a,P &b){
	return a.x==b.x && a.y==b.y;
}
bool neibor(P &a,P &b){
	int dx=a.x-b.x;
	int dy=a.y-b.y;
	return abs(dx)+abs(dy)<=1
		|| abs(dx)==1 && -dx==dy;
}
bool is_dead(int no){
	for(int i=0;i<no-1;i++){
		if(neibor(body[no], body[i])){
				return true;
		}
	}
	return false;
}
bool on_rock(int no){
	for(int i=0;i<k;i++){
		if(rock[i].x==body[no].x && rock[i].y==body[no].y)
			return true;
	}
	return false;
}
void search(int step);
bool move(int no){
	if(no==1||no==2)if(ans-body.step <= distance())return false;
	for(int i=0;i<6;i++){
		body[no].x+=vx[i];
		body[no].y+=vy[i];
		if(!is_dead(no) && !on_rock(no) 
			&& (no==0  ||neibor(body[no-1],body[no]) && !overlap(body[no-1],body[no]))
			&& (n<=no+1||neibor(body[no],body[no+1]) && !overlap(body[no],body[no+1])) ){
			if(no+2<n){if(move(no+2))return true;}
			else {
				if(X==body[0].x && Y==body[0].y)return true;
				body.step++;
				if(s.find(body)==s.end()){
					s.insert(body);
					que.push(body);
				}
				body.step--;
			}
		}
		body[no].x-=vx[i];
		body[no].y-=vy[i];
	}
	if(!is_dead(no) ){
		if(no+1<n){if(move(no+1))return true;}
		else {
			if(X==body[0].x && Y==body[0].y)return true;
			body.step++;
			if(s.find(body)==s.end()){
				s.insert(body);
				que.push(body);
			}
			body.step--;
		}
	}
	return false;
}
main(){
	while(cin>>n,n){
		s.clear();
		while(!que.empty())que.pop();
		body.step=0;
		for(int i=0;i<n;i++){
			cin>>body[i].x>>body[i].y;
			
		}
		cin>>k;
		for(int i=0;i<k;i++){
			cin>>rock[i].x>>rock[i].y;	
		}
		cin>>X>>Y;
		ans=20;
		que.push(body);
		while(!que.empty()){
			body=que.front();
			que.pop();
			if(ans-body.step <= distance())continue;
			if(body.step==20-1)break;
			if(move(0)){
				ans= body.step+1;
				break;
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 6648
N, K = map(int, input().split())

def f(x, y):
    a, b = divmod(x,y)
#    print("aa",b*(a+1))
    return y*a*(a+1)//2 + (b+1)*(a+1)

r = 0
for b in range(K+1, N+1):
#    print(f(N-K, b), f(N-b, b))
    r += f(N-K, b)- f(N-b, b)
    if K == 0:
        r -= 1
#    print(b, N-b+1, N-K+1)
#    print(b, (N-K)//b, (N-b)//b, (N-K)%b, (N-b)%b, b-K)
#    for j in range(N-b+1,N-K+1):
#        r += j//b + 1
print(r)


Measured memory_bytes: 3060
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

INF = float("inf")
route_list=[[INF]*N for _ in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

print(ans)

Measured memory_bytes: 4720
from sys import stdin

n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))+[0]
li = [li[i] for i in range(len(li)-1) if li[i] != li[i+1]]
#長さが2以下の数列に関しては絶対答えは1になる
if n <= 2:
    print(1)
    exit()
#そうでない場合
count = 1
flag = 0
for i in range(1,len(li)-1):
    if flag == 1:
        flag = 0
        continue
    else:
        if li[i-1] > li[i] < li[i+1] or li[i-1] < li[i] > li[i+1]:
            flag = 1
            count += 1
print(count)

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    int k,t;
    cin >> k >> t;
    priority_queue<pair<int,int>,vector<pair<int,int>>> que;
    rep(i,0,t){
        int a;
        cin >> a;
        que.push(make_pair(a,i));
    }
    int prev=-1,ans=0;
    rep(i,0,k){
        vector<pair<int,int>> ps;
        for(;;){
            auto p=que.top();
            que.pop();
            if(que.empty() or p.second!=prev){
                if(p.second==prev) ++ans;
                if(p.first-1>0) que.push(make_pair(p.first-1,p.second));
                prev=p.second;
                break;
            }else ps.push_back(p);
        }
        for(auto &p:ps) que.push(p);
    }
    cout << endl;
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000LL

long dp[2][5003];

int main(){
  int n;
  cin>>n;
  using P = pair<int,int>;
  vector<P> v(n);
  rep(i,n) cin>>v[i].first>>v[i].second;
  sort(all(v), [](const P &l, const P &r){
    return l.first + l.second < r.first + r.second;
  });

  auto pre = dp[0];
  auto nxt = dp[1];

  fill(pre, pre+n+1, 2*INF);
  pre[0] = 0;

  rep(i,n){
    fill(nxt, nxt+n+1, 2*INF);
    rep(j,n){
      nxt[j] = min(nxt[j], pre[j]);
      if(pre[j] <= v[i].first) nxt[j+1] = min(nxt[j+1], pre[j] + v[i].second);
    }
    // dbg(vector<int>(nxt,nxt+n+1));
    swap(pre, nxt);
  }

  cout << lower_bound(pre, pre+n+1, 2*INF) - pre - 1 << endl;

  return 0;
}


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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define per(i,n) for(ll i = n-1; i >= 0; i--)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define PER(i,n) for(ll i = n; i >= 1; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
using vP = vector<P>;
using vPP = vector<vP>;
using vPl = vector<Pl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



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

  int s;
  cin >> s;
  vi a(4);
  a[0] = s / 1000; s %= 1000;
  a[1] = s / 100; s %= 100;
  a[2] = s / 10; s %= 10;
  a[3] = s;
  rep(i,(1<<3)+1) {
    bitset<3> b(i);
    int p = a[0];
    rep(j,3) {
      if(b[j]) p += a[j+1];
      else p -= a[j+1];
    }
    if(p == 7) {
      vc op(3);
      rep(j,3) {
        if(b[j]) op[j] = '+';
        else op[j] = '-';
      }
      cout << a[0] << op[0]
           << a[1] << op[1]
           << a[2] << op[2]
           << a[3] << "=7" << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
main(){
  int tate,yoko,nagasa;
  int men;
  int n;
  int han;
  int i;
  double tai;
  while(1){
    scanf("%d %d %d",&tate,&yoko,&nagasa);
    if(tate==0 && yoko==0 && nagasa==0) break;
    tai=yoko*yoko+nagasa*nagasa;
    tai=sqrt(tai);
    scanf("%d",&n);
    for(i=0;i<n;i++){
      scanf("%d",&han);
      han=han*2;
      if(han>tai) printf("OK\n");
      else{
	printf("NA\n");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INF = 1e18;
#define foreach(ix,a) for(auto& (ix) : (a)
typedef long double ld;
const ld eps = 1.0e-10; // 許容される誤差

ld mysqrtl(ld x)
{
  ld a = sqrt((double)x); // 近似値
  do {
    a = (a + x/a) / 2.0L;
  } while (fabsl(x - a*a) > eps);
  return a;
}
int main(){
  //std::cout<<std::fixed<<std::setprecision(10);
  ll a,b,c;
  cin>>a>>b>>c;
  ld v = sqrtl(a*b);
  if(a+b+2*v<c)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
a,b,x=map(int,input().split())
if a==0:
    #0以上b以下でbで割り切れる個数
    if b%x==0:
        ans_b = b//x +1
    else:
        ans_b = b//x +1
    #0以上a未満でbで割り切れる個数
    if a%x==0:
        ans_a = a//x
    else:
        ans_a = a//x + 1
else:
    ans_b = b//x
    if a%x==0:
        ans_a = a//x -1
    else:
        ans_a = a//x

print(ans_b-ans_a)

Measured memory_bytes: 9068
N = int(input())
#A = [int(x) for x in input().split()]
A = input().split()

M = 1
if '0' in A:
    M = 0
else:
    for a in A:
        a = int(a)
        M *= a
        if M > 1000000000000000000:
            M = -1
            break

print(M)

Measured memory_bytes: 19352
import java.util.*;

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

    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
      // 位置iを含む左半分を切断。出現文字の個数をカウント。
      int[] seen = new int[26];
      for (int j = 0; j <=i; j++) {
        int k = s.charAt(j) - 'a';
        seen[k]++;
      }

      // 右半分に対して、左半分で出現した文字をカウント。
      // 同じ文字を重複して数えないようにする。
      int cnt = 0;
      for (int j = i + 1; j < n; j++) {
        int k = s.charAt(j) - 'a';
        if (seen[k] != 0) {
          cnt++;
          seen[k] = 0;
        }
      }
      if (ans < cnt) ans = cnt; // 最大値更新
    }

    System.out.print(ans);
  } 
}


Measured memory_bytes: 23764
import java.util.*;

class Main {
        public static void main(String args[]) {
                Scanner sc = new Scanner(System.in);
                System.out.println(calc(sc.nextInt(), sc.nextInt()));
        }
        public static int calc(int a, int b) {
                if (a < b) {
                        return calc(b, a);
                }
                if (b == 0) {
                        return a;
                }
                return calc(b, a % b);
        }
}

Measured memory_bytes: 26200
#include <stdio.h>

int main(void){
    int n=-1,x=-1,i,j,k,cnt,l=0,res[1000];
    while (!(n==0 && x==0)){
        cnt=0;
        scanf("%d %d",&n,&x);
        for(i=1;i<=n;i++){
            for(j=i+1;j<=n;j++){
                for(k=j+1;k<=n;k++){
                    if (i+j+k==x) cnt++;
                }
            }
        }
        res[l]=cnt, l++;
    }
    for(i=0;i<l-1;i++) printf("%d\n",res[i]);
    return 0;
}



Measured memory_bytes: 2048
#include<iostream>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a<b)swap(a,b);
  if(b<c)swap(b,c);
  if(a<b)swap(a,b);
  if(c-b==b-a)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256