akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
// #define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
 
struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator > (long&& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
  template<typename a, std::size_t s>
  S002& operator >= (std::array<a, s>& x) {
    for(long i = 0; i < (long)s; ++i) {
      *this >= x[i];
    }
    return *this;
  }
};


struct Solver {
  long n, w;
  std::vector<long> ws, vs;
  Solver() {
    S002 reader;
    std::vector<std::array<long, 2>> ys;
    reader >= n >= w >n>= ys;
    for(auto y : ys) {
      ws.push_back(y[0]);
      vs.push_back(y[1]);
    }
  }
  long dp[128][512];
  void solve() {
    for(long i = 0; i < 128; ++i) {
      for(long j = 0; j < 512; ++j) {
        dp[i][j] = 0;
      }
    }
    for(long k = 0; k < n; ++k) {
      for(long i = n; i >= 0; --i) {
        for(long j = 0; j < 512; ++j) {
          if( j-(ws[k]-ws[0]) < 0 ) continue;
          if( i - 1 < 0 ) continue;
          dp[i][j] = std::max(dp[i][j], dp[i-1][j-(ws[k]-ws[0])] + vs[k]);
        }
      }
    }
    long res = 0;
    for(long i = 0; i <= n; ++i) {
      for(long j = 0; j < 512; ++j) {
        if( i * ws[0] + j > w ) continue;
        res = std::max(res, dp[i][j]);
      }
    }
    printf("%ld\n", res);        
  }    
  ~Solver() { fprintf(stderr, "--end--\n"); }
};
 

int main() {
  loop std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

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

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

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }

template<typename T> void fill_all(T& arr, const T& v) { arr = v; }
template<typename T, typename U> void fill_all(T& arr, const U& v) { for (auto& i : arr) fill_all(i, v); }

template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
#define DUMP(x) cout<<#x<<" = "<<(x)<<endl

struct edge { int to, cost; };

const LL LINF = 1LL<<60;
const int IINF = 1<<30;
const LL MOD = 1e9+7;

int main()
{
   vector<int> a(5);
   for (int i = 0; i < 5; ++i) {
      cin >> a[i];
   }
   int k; cin >> k;

   if (a[4] - a[0] > k) {
      cout << ":(" << endl;
   } else {
      cout << "Yay!" << endl;
   }

   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define itn int
#define nibu(K,x) binary_search(K.begin(),K.end(),x)
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define out(x) cout<<x<<endl
#define put(x) out(x)
#define in(x) cin>>x
#define maxx(a,b,c) max(a,max(b,c))
#define minn(a,b,c) min(a,min(b,c))
using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
const double pi = 3.14159265358979;

int main() {
ll N;
  in(N);
  vl H(N);
  rep(i,N) in(H[i]);
  int ans = 0;
  rep(i,N){
   bool f = true;
    for(int j=0;j<i+1;j++){
      if(H[j]>H[i]) f = false; 
    }
    if(f) ans++;
  }
  out(ans);
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100005
#define NIL -1

void print(int);

struct Node {
  int p,l,r;
};

struct Node Tree[MAX];

int depth(int,int);

int Depth[MAX];

int main(){
  int h,i,j,nu,dep,c,l,r;

  scanf("%d",&h);

  for(i=0;i<h;i++){
    
    Tree[i].p = Tree[i].l = Tree[i].r = NIL;
  }
  
  for(i=0;i<h;i++){
    
    scanf("%d%d",&nu,&dep);
    
    for(j=0;j<dep;j++){

      scanf("%d",&c);
      
      if(j==0)Tree[nu].l=c;
      
      else Tree[l].r = c;
      
      l=c;
      
      Tree[c].p = nu;
      
    }
  }

  for(i=0;i<h;i++){
    if(Tree[i].p == NIL)r=i;
  }

  depth(r,0);
  
  for(i=0;i<h;i++) print(i);

  return 0;
}

void print(int x){
  int i,p;
  
  printf("node %d: ",x);
  
  printf("parent = %d, ",Tree[x].p);
  
  printf("depth = %d, ",Depth[x]);

  if(Tree[x].p == NIL)printf("root, ");
  
  else if(Tree[x].l == NIL)printf("leaf, ");
  
  else printf("internal node, ");

  printf("[");
  
  for( i=0, p =Tree[x].l;p!=NIL;i++, p = Tree[p].r){
    
    if(i>0)printf(", ");
    
    printf("%d",p);
    
  }
  
  printf("]\n");
  
}

int depth(int x,int y){
  
  Depth[x] = y;
  
  if(Tree[x].r != NIL)depth(Tree[x].r,y);
  
  if(Tree[x].l != NIL)depth(Tree[x].l,y+1);
  
}



Measured memory_bytes: 6396
N = int(input())
s = input().rstrip().split(' ')
a = list(map(int, s))
b = list(map(int, s))

a.insert(len(a),-1)
b.insert(0,-1)

c =[a[i]-b[i] for i in range(len(a))]

tmpall = []
tmp = []

for i in range(len(a)):
    if c[i] == 0:
        tmp.append(i)
    else:
        tmpall.append(tmp)
        tmp=[]

# print(tmpall)
        

tout = [len(t) for t in tmpall]


S = 0
for kk in tout:
    S += kk//2  + kk%2

print(S)

Measured memory_bytes: 3064
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char c[] = sc.next().toCharArray();
        int k = sc.nextInt();
        int digit = c.length;
        int[] keta = new int[digit];
        for(int i=0;i<c.length;i++)keta[i]=c[i]-'0';

        long[][] dp0 = new long[digit][k+1];//桁、0以外の個数
        long[][] dp1 = new long[digit][k+1];

        dp0[0][1]=0;
        for(int i=0;i<10;i++){
            if(i==0){
                dp0[0][0]=1;
            } else if(i<keta[0]){//100のときi<1
                dp0[0][1]++;
            } else if(i==keta[0]){
                dp1[0][1]=1;
            }
        }

        for(int i=1;i<digit;i++){
            dp0[i][0]=dp0[i-1][0];
            dp1[i][0]=0;
            for(int j=1;j<k+1;j++){
                dp0[i][j]=dp0[i-1][j]+dp0[i-1][j-1]*9;

                if(keta[i]!=0)dp0[i][j]+=dp1[i-1][j]+dp1[i-1][j-1]*(keta[i]-1);
                if(keta[i]==0){
                    dp1[i][j]=dp1[i-1][j];
                }else{
                    dp1[i][j]=dp1[i-1][j-1];
                }
            }
        }

        long ans = dp0[digit-1][k]+dp1[digit-1][k];
        System.out.println(ans);
/*
        for(int i=0;i<digit;i++){
            for(int j=0;j<k+1;j++) System.out.print(dp0[i][j]+" ");
            System.out.println();
        }
        System.out.println("---");
        for(int i=0;i<digit;i++){
            for(int j=0;j<k+1;j++) System.out.print(dp1[i][j]+" ");
            System.out.println();
        }
 */






    }

}




Measured memory_bytes: 23380
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-4;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
typedef vector<string> svec;

void Z_algorithm(const string &s, vector<int> &a) {
	int sz = s.size();
	a.resize(sz);
	a[0] = sz;
	int i = 1, j = 0;
	while (i < sz) {
		while (i + j < sz&&s[j] == s[i + j])++j;
		a[i] = j;
		if (j == 0) { ++i; continue; }
		int k = 1;
		while (i + k < sz&&k + a[k] < j)a[i + k] = a[k], ++k;
		i += k; j -= k;
	}
}

void solve() {
	string s, t; cin >> s >> t;
	int len = t.length(); int st = s.length();
	t += s;
	vector<int> r;
	Z_algorithm(t, r);
	rep(i, st) {
		if (r[len + i] >= len) {
			cout << i << endl;
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(11);
	/*while (cin >> n, n) {
		solve();
	}*/
	solve();
	//stop
	return 0;
}



Measured memory_bytes: 8920
n, m = map(int, input().split())
g = [[-1]*n for _ in range(m)]
for i in range(m):
  s = list(map(int, input().split()))
  s.pop(0)
  for j in s:
    g[i][j-1] = 1
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
  switch = [0]*n
  for j in range(n):
    if ((i >> j) & 1):
      switch[j] = 1
  
  flag = True
  for j in range(m):
    cnt = 0
    for k in range(n):
      if g[j][k] == switch[k]:
        cnt += 1
    if cnt % 2 != p[j]:
      flag = False
  if flag:
    ans += 1

print(ans)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	A -= C; B -= D;
	if (A < 0) A *= -1;
	if (B < 0) B *= -1;
	if (A == 0 || B == 0) {
		cout << 0 << endl;
	}
	else {
		int G = gcd(A, B);
		cout << A + B - G << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int count[3][10][4] = {0};
    int i, j, k;
    int n, p;
    int b, f, r, v;

    scanf("%d", &n);
    for(i=0; i<n; i++){
        scanf("%d%d%d%d", &b, &f, &r, &v);
        count[f-1][r-1][b-1] += v;
    }

    for(k=0; k<4; k++){
        for(i=0; i<3; i++){
            for(j=0; j<10; j++){
                if(count[i][j][k] == 0){
                    printf(" 0");
                }else{
                    printf(" %d", count[i][j][k]);
                }
            }
        printf("\n");
        }
        if(k != 3){
        printf("####################\n");
        }
    }
return 0;
}


Measured memory_bytes: 2068
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7; //998244353;
const int N = 1e5;
int n, L, T, c=-1, t;
V<int> XL, XR;

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> L >> T;
  FOR(i, 0, n){
    int x, w;
    cin >> x >> w;
    (w==1 ? XR : XL).pb(x);
    if(w==1 && c<0){
      c = i;
      t = x;
    }
  }
  if(c < 0){
    for(int a:XL) cout << ((a-T)%L+L)%L << endl;
    return 0;
  }
  c += T/L*sz(XL)*2;
  T %= L;
  for(int a:XL){
    if((a-t+L)%L   < T*2) c++;
    if((a-t+L)%L+L < T*2) c++;
  }
  c %= n;
  V<int> v;
  for(int a:XR) v.pb((a+T)%L);
  for(int a:XL) v.pb((a+L-T)%L);
  sort(all(v));
  int i = lower_bound(all(v), (t+T)%L) - v.begin();
  i = (i+n-c)%n;
  FOR(_, 0, n){
    cout << v[i] << endl;
    i = (i+1)%n;
  }
}

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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  string s, t;
  cin >> s >> t;
  int n = s.size();

  int cnt = 0;
  for(int i=0; i<n; ++i){
    if(s[i] != t[i]) cnt++;
  }
  cout << cnt;
}

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

using namespace std;

int main() {
	int n, d, x;
	cin >> n >> d >> x;
	vector<int> a(100);
	int z = x;

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

	for (int i = 0; i < n; i++) {	
		int y = (d - 1) / a[i] + 1;
			 z += y;
		}
	 cout<< z << endl;

	return 0;
}

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

int main() {
	int x, y, z;
	cin >> x >> y >> z;
	swap(x, y);
	swap(x, z);
	cout << x << ' ' << y << ' ' << z << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    ll N, M, K; cin >> N >> M >> K;
    vector<ll> A(N), B(M);
    REP(i, 0, N) cin >> A[i];
    REP(i, 0, M) cin >> B[i];

    vector<ll> Asum(N + 1, 0), Bsum(M + 1, 0);
    REP(i, 0, N) Asum[i + 1] = Asum[i] + A[i];
    REP(i, 0, M) Bsum[i + 1] = Bsum[i] + B[i];

    int ans = 0;
    REP(i, 0, N + 1) {
        if (K - Asum[i] < 0) break;
        int idx = upper_bound(ALL(Bsum), K - Asum[i]) - Bsum.begin();
        ans = max(ans, i + idx - 1);
    }
    cout << ans << endl;
    return 0;
}

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

const int P = 2019;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	#ifdef LOCAL
//		freopen("in1.txt", "r", stdin);
//		freopen("in1.txt", "w", stdout);
	#endif
	string s;
	cin >> s;
	for (char& x : s) x -= '0';
	int a[P];
	memset(a, 0, sizeof(a));
	
	int n = s.length();
	ll ans = 0;
	int suff = 0, mul = 1;
	a[0] = 1;
	for (int i=n-1; i>=0; i--) {
		suff = (suff + s[i]*mul) % P;
		ans += a[suff];
		a[suff]++;
		mul = (mul*10) % P;
	}
	cout << ans << '\n';
}

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

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef long double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


int main() {

    int N, x;
    cin >> N;
    map<string,ll> mp;
    forn(i, N) {
        string s; cin >> s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    ll ans = 0;
    for(auto p : mp) {
         x = p.second;
        ans += (ll)x*(x-1)/2;
    }
    cout << ans << "\n";

    return 0;
}

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

#define FOR1(n) for(int i=0;i<n;i++)
#define FOR2(j, n) for(int j=0;j<n;j++)
#define FOR3(i, m, n) for(int i=m;i<=n;i++)
#define ALL(c) c.begin(), c.end()
#define SCANF(x) scanf("%lld", &x)
#define MOD 1000000007
#define MAX_N 1000000
#define INF 1410065408

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
struct edge{int from, to; ll cost;};

/*
逆順ソート sort(ALL(vec), greater<ll>());
ペア定義 P pair = make_pair(100, 200);
集合find set.find(item);
小さい順に取り出したい優先度付きキュー
priority_queue<int, vector<int>, greater<int> > que;
配列の最大要素 *std::max_element(ALL(vec))
*/
int par[2][MAX_N];  //親
int ran[2][MAX_N]; //深さ

//初期化
void init(int n){
	FOR1(n){
		par[0][i] = i;
		par[1][i] = i;
		ran[0][i] = 0;
		ran[1][i] = 0;
	}
}

//根を求める
int find(int x, int t){
	if(par[t][x] == x){
		return x;
	}else{
		return par[t][x] = find(par[t][x], t);
	}
}

//xとyの属する集合の併合
void unite(int x, int y, int t){
	x = find(x, t);
	y = find(y, t);
	if(x == y) return;

	if(ran[t][x] < ran[t][y]){
		par[t][x] = y;
	}else{
		par[t][y] = x;
		if(ran[t][x] == ran[t][y]) ran[t][x]++;
	}
}

//同じ集合に属するか否か
bool same(int x, int y, int t){
	return find(x, t) == find(y, t);
}


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

	int n, k, l;
	scanf("%d %d %d", &n, &k, &l);
	init(n);

	FOR1(k+l){
		int p, q;
		scanf("%d %d", &p, &q);
		unite(p-1, q-1, i < k ? 0 : 1);
	}

	map<pair<int, int>, int> mp;
	FOR1(n){
		mp[pair<int, int>(find(i, 0), find(i, 1))]++;
	}

	FOR1(n-1){
		printf("%d ", mp[pair<int, int>(par[0][i], par[1][i])]);
	}
	printf("%d", mp[pair<int, int>(par[0][n-1], par[1][n-1])]);
}

Measured memory_bytes: 15104
import sys,heapq
_,a,q=[[-int(e) for e in sys.stdin.readline().split() if e!='0'] for _ in[0]*3]
heapq.heapify(q)
for e in a:
	t=[]
	for _ in [0]*-e:
		if not q:print(0);exit()
		if q[0]!=-1:heapq.heappush(t,q[0]+1)
		heapq.heappop(q)
	while t:heapq.heappush(q,t[0]);heapq.heappop(t)
print(int(not q))


Measured memory_bytes: 5688
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;


class Program {

	static long mod = 998244353;
	static void Main(string[] args) {

		char[] cs = new char[] { ' ' };
		//char[] cs = new char[] { ' ', ',' };

		//int val = int.Parse(Console.ReadLine());
		//int[] vals = parseAry(Console.ReadLine().Split(cs));
		//string str = Console.ReadLine();
		//string[] strs = Console.ReadLine().Split(cs);

		//string res="";
		//int res = 0; ;
		//int t = int.Parse(Console.ReadLine());
		//string str = Console.ReadLine();
		//int[] vals = parseAry(Console.ReadLine().Split(cs));
		//int n = int.Parse(Console.ReadLine());
		//string res="";

		int res = 0;

		int[] vals = parseAry(Console.ReadLine().Split(cs));

		res = (vals[2] / vals[0])*vals[1];

			Console.WriteLine(res);


		return;
	
	}
	//　String[]  ----->  int[]
	static int[] parseAry(string[] str) {
		int[] nums = new int[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = int.Parse(str[i]); }
		return nums;
	}
	//　String[]  ----->  long[]
	static long[] parseAryL(string[] str) {
		long[] nums = new long[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = long.Parse(str[i]); }
		return nums;
	}

	//文字列を1文字ずつString[]に入れる
	static string[] strAry(String str) {
		string[] re = new string[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { re[i] = str[i].ToString(); }
		return re;
	}

}

Measured memory_bytes: 11220
/*
Author: Racer5x
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
#define int         long long
#define double      long double
#define pb          emplace_back
#define pf          emplace_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define tezz        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX         2000000000000000000
#define M           1000000007
using namespace std;

vi prime;
bool table[1000005] = {false};

void seive(){
	for(int i=2;i<=1000005;i++){
		if(!table[i]){
			table[i] = true;
			prime.pb(i);

			for(int j=i*i;j<1000005;j+=i){
				table[j] = true;
			}
		}
	}
}
 
signed main()
{
    tezz
    
    int n;
    cin>>n;

    seive();

    for(int x:prime){
    	if(x >= n){
    		cout<<x;
    		return 0;
    	}
    }
} 

Measured memory_bytes: 2424
import heapq
N, M =map(int, input().split())
A = [[] for i in range(10**5+1)]
 
for i in range(N):
    a, b = map(int,input().split())
    if a > M:
        continue
    A[a].append(-b)
 
work_cand = []
sum = 0
 
for i in range(M+1):
    add_jobs = A[i]
    if len(add_jobs) != 0:
        for j in add_jobs:
            heapq.heappush(work_cand, j)
    if len(work_cand) == 0:
        continue
    sum += heapq.heappop(work_cand)
ans = -(sum)
print(ans)

Measured memory_bytes: 17864
n=int(input())
arr=list(map(int,input().split()))
cnt1=[0]*(10**5+1)
cnt2=[0]*(10**5+1)
for i in range(n):
  if i%2==0:
    cnt1[arr[i]]+=1
  else:
    cnt2[arr[i]]+=1
m1=max(cnt1)
m2=max(cnt2)
p1=cnt1.index(m1)
p2=cnt2.index(m2)
cnt1=sorted(cnt1,reverse=True)
cnt2=sorted(cnt2,reverse=True)
if n==2:
  if arr[0]!=arr[1]:
    print(0)
  else:
    print(1)
else:
  if p1==p2:
    ans=min(n-m1-cnt2[1],n-cnt1[1]-m2)
  else:
    ans=n-m1-m2
  print(ans)

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

"""
input:
4 5
4 2
5 2
2 1
8 3

output:
13
"""

import sys
from collections import namedtuple


def solve():
    dp = [0] * (real_cp + 1)
    for item in item_list:
        v, w = item.v, item.w
        # for cp in range(real_cp - w, -1, -1):
        #     dp[cp + w] = max(dp[cp + w], dp[cp] + v)
        for cp in range(real_cp, w - 1, -1):
            dp[cp] = max(dp[cp], dp[cp - w] + v)

    return dp[-1]


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    c_items, real_cp = map(int, _input[0].split())
    items = map(lambda x: x.split(), _input[1:])

    Item = namedtuple('Item', ('v', 'w'))
    item_list = [Item(int(v), int(w)) for v, w in items]

    print(solve())

Measured memory_bytes: 8260
n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")

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

int N;
int A[110],B[110];
int ans=0;
int main()
{
    memset(A,0x3f,sizeof(A));
    cin>>N;
    for(int i=1;i<N;i++) cin>>B[i];
    for(int i=1;i<N;i++)
    {
        A[i]=min(A[i],B[i]);
        A[i+1]=min(A[i+1],B[i]);
    }
    for(int i=1;i<=N;i++) ans+=A[i];
    cout<<ans;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	String s=sc.nextLine();
    	int a=Integer.parseInt(s);
    	int sum=0;
    	for(int i=0;i<s.length();i++) {
    		sum+=Integer.parseInt(s.substring(i,i+1));
    	}
    	System.out.println(a%sum==0?"Yes":"No");
	}
}

Measured memory_bytes: 23636
#include <cstdio>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;
using u8t = std::uint64_t;
using i8t = std::int64_t;
#define F(I,N) for(i8t I=0,I##_N=N;I<I##_N;I++)
#define FR(I,N) for(i8t I=N;I--;)
#define R(V) i8t V;std::cin>>V;
#define RV(V,N) std::vector<i8t> V;F(_i,N){R(_x)V.push_back(_x);}
#define RL1(line) std::getline(std::cin,line);
#define RL(line) std::string line;RL1(line)
#define RM(V,L,C) std::vector<char> V;F(_i,L){RL(_l)F(_j,C)V.push_back(_l[_j]);}
#define P(X) std::cout<<(X)<<std::endl;

template<typename T>
void print_range(T arr){
  for(auto x:arr)std::cout<<" "<<x;
  std::cout<<std::endl;
}

i8t case_even(i8t const N,std::vector<i8t>const& accum){
  i8t ans=0;
  for(int x=0;x<N;x+=2){
    i8t a1=x-1>=0?accum[x-1]:0;
    i8t a2=x-2>=0?accum[x-2]:0;
    i8t c1=a2-a1;
    ans=max(ans,c1);
  }
  ans+=accum[N-1];
  return ans;
}

int main() {
  R(N)RV(A,N);

  // N 奇数
  std::vector<i8t> accum(N+1,0);//accum[N] はダミー
  F(I,N){
    if(I==0)accum[0]=A[0];
    else if(I==1)accum[1]=A[1];
    else accum[I]=accum[I-2]+A[I];
  }

  if(N%2==0){
    i8t ans=case_even(N, accum);
    ans=max(ans,accum[N-2]);
    P(ans);
    return 0;
  }else{
    std::vector<i8t> gain(N+1,0);//gain[N]=dummy for x=N-1,
    F(x,N){
      i8t a1=x-1>=0?accum[x-1]:0;
      i8t a2=x-2>=0?accum[x-2]:0;
      i8t c1=a2-a1;
      gain[x]=c1;
    }

    // これで奇数番目は全てそれ以降の物の最大値に置き換える。
    i8t mx=gain[N-2];
    for(i8t i=N-2;i>=0;i-=2){
      gain[i]=mx=std::max(mx,gain[i]);
    }

    //print_range(gain);

    i8t ans=gain[0]+gain[1];
    for(i8t i=0;i<N-2;i+=2){
      ans=max(ans,gain[i]+gain[i+1]);
    }
    ans+=accum[N-1];
    ans=max(case_even(N-1,accum),ans);
    ans=max(ans,accum[N-3]);
    P(ans);
    return 0;

  }
  return 0;
}


Measured memory_bytes: 7896
(let* ((n (read))
       (p (read))
       (a (loop repeat n collect (read)))
       (e (loop for ai in a always (evenp ai))))
  (if e
      (if (= p 0)
          (prin1 (expt 2 n))
          (prin1 0))
      (prin1 (expt 2 (1- n))))
  (terpri))

Measured memory_bytes: 5092
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String x = scan.next();
		char n = x.charAt(0);
		if(n == 'a'|| n == 'i'|| n == 'o'
				||n == 'e'|| n == 'u') {
			System.out.println("vowel");
		}else {
			System.out.println("consonant");
		}
	}

}


Measured memory_bytes: 21716
s , t = Hash.new{0} , Hash.new{0}

n = gets.to_i
n.times do |i|
	s[gets] += 1
end

m = gets.to_i
m.times do |i|
	s[gets] -= 1
end

p [s.max {|x,y| x[1] <=> y[1]}[1] , 0].max


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    double n;
    cin >> n;
    if ((int)n % 2 == 0)
        OP(0.5);
    else if (n == 1)
        OP(1);
    else
        OP(ceil(n / 2) / n);

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
int main(){
	ll n, s, ans = 0, mod = 998244353;
	scanf("%lld %lld", &n, &s);
	ll a[n], dp[n][s + 1], p[s + 1];
	for (int i = 0; i < n; i++){
		scanf("%lld", &a[i]);
		for (int j = 0; j <= s; j++) dp[i][j] = 0;
		if (a[i] <= s) dp[i][a[i]] += i + 1;
	}
	fill(p, p + s + 1, 0);
	for (int i = 0; i < n; i++){
		for (int j = a[i]; j <= s; j++){
			(dp[i][j] += p[j - a[i]]) %= mod;
		}
		for (int j = 0; j <= s; j++){
			(p[j] += dp[i][j]) %= mod;
		}
	}
	for (int i = 0; i < n; i++){
		(ans += ((n - i) * dp[i][s]) % mod) %= mod;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 70528
import java.io.*;
import java.util.*;
public class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		//Scanner reader=new Scanner(System.in);
		String s;//=reader.readLine();
		//int in=reader.nextInt();
		while((s=reader.readLine())!=null){
			String[] in2=s.split(" ");
			int[] in=new int[4];
			for(int i=0;i<4;i++)in[i]=Integer.parseInt(in2[i]);
			//
			s=reader.readLine();
			in2=s.split(" ");
			int[] in1=new int[4];
			for(int i=0;i<4;i++)in1[i]=Integer.parseInt(in2[i]);
			
			int co1=0,co2=0;
			for(int i=0;i<4;i++){
				for(int j=0;j<4;j++){
					if(i==j&&in[i]==in1[j])co1++;
					else if(in[i]==in1[j])co2++;
				}
			}
			System.out.println(co1+" "+co2);
		}
	}
}

Measured memory_bytes: 16920
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main() {
    int N; cin >> N;
    vector<int> V(N); for (auto &v : V) cin >> v;
    sort(begin(V), end(V));
    double curr = (V[0] + V[1]) / 2.0;
    for (int i = 2; i < V.size(); i++) {
        curr = (curr + V[i]) / 2.0;
    }
    cout << fixed << setprecision(9) << curr << '\n';
    return 0;
}

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

// Contest: AtCoder Beginner Contest 142 (https://atcoder.jp/contests/abc142)
// Problem: F: Pure (https://atcoder.jp/contests/abc142/tasks/abc142_f)

using namespace std;

using ll = int64_t;
using u64 = uint64_t;
using u32 = uint32_t;

int n;
vector<set<int>> adj;

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

    int m; cin >> n >> m;
    adj.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        adj[a].emplace(b);
    }

    vector<bool> vis(n);
    vector<int> prev(n);
    for (int i = 0; i < n; ++i) {
        vis.assign(n, false); prev.assign(n, -1);
        queue<int> q; q.push(i);
        while (!q.empty()) {
            auto v = q.front(); q.pop();
            for (auto v2 : adj[v]) {
                if (v2 == i) {
                    vector<int> s;
                    for (auto v3 = v; v3 != -1; v3 = prev[v3])
                        s.push_back(v3);
                    reverse(begin(s), end(s));
                    vector<int> s2;
                    int i = 0;
                    while (true) {
                        s2.push_back(s[i]);
                        for (int j = (int)s2.size() - 2; j >= 0; --j)
                            if (adj[s[i]].count(s2[j])) {
                                cout << (s2.size() - j) << '\n';
                                for (int k = j; k < s2.size(); ++k)
                                    cout << (s2[k] + 1) << '\n';
                                return 0;
                            }
                        for (int j = s.size() - 1; j > i; --j)
                            if (adj[s[i]].count(s[j]))
                                i = j;
                    }
                }
                if (!vis[v2]) {
                    vis[v2] = true;
                    prev[v2] = v;
                    q.push(v2);
                }
            }
        }
    }

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


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

using namespace std;
typedef long long ll;

const int N=200005,P=1e9+7;
int n,X,Y,mw=P,fac[N],ans=1,cur,inv[N],ifac[N],cm,se;
vector<int>col[N];

int main(){
	scanf("%d%d%d",&n,&X,&Y);
	for(int i=1,u,v;i<=n;i++){
		scanf("%d%d",&u,&v),col[u].push_back(v);
		if(v<mw)cm=u,se=mw,mw=v;else if(v<se&&u!=cm)se=v;
	}
	inv[1]=ifac[0]=ifac[1]=fac[0]=fac[1]=1;
	for(int i=2;i<=n;i++){
		fac[i]=(ll)fac[i-1]*i%P;
		inv[i]=P-(ll)P/i*inv[P%i]%P;
		ifac[i]=(ll)ifac[i-1]*inv[i]%P;
	}
	for(int i=1;i<=n;i++)if(col[i].size()){
		int m=P,s=0;
		for(int v:col[i])m=min(m,v);
		if(m+mw>Y)continue;
		if(i==cm)for(int v:col[i])s+=v+m<=X||v+se<=Y;
		else for(int v:col[i])s+=v+m<=X||v+mw<=Y;
		cur+=s,ans=(ll)ans*ifac[s]%P;
	}
	ans=(ll)ans*fac[cur]%P;
	printf("%d\n",ans);
	return 0;
}

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 8 2");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 5 1");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 9 2");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1 1000000000000000000 3");
            //333333333333333333
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(X => long.Parse(X)).ToArray();
        long a = wkArr[0];
        long b = wkArr[1];
        long x = wkArr[2];

        long FromSyou = a / x;
        if (a % x > 0) FromSyou++;

        long ToSyou = b / x;

        Console.WriteLine(ToSyou - FromSyou + 1);
    }
}


Measured memory_bytes: 3032
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<long,long>
#define INF 1000000000000000000
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long MOD = 1000000007;
using namespace std;
typedef long long ll;
map<int, int> mp;
//最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
class Union_Find {
private:
	vector<int> par;
	vector<int> rank;
public:
	Union_Find(int n) {
		rep(i, n) {
			par.push_back(i);
			rank.push_back(0);
		}
	}
	int find(int x) {
		if (par.at(x) == x) return x;
		else return par.at(x) = find(par.at(x));
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (rank.at(x) < rank.at(y)) {
			par.at(x) = y;
		}
		else {
			par.at(y) = x;
			if (rank.at(x) == rank.at(y)) rank.at(x)++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	if (n == 0) {
		cout << 0 << endl; return 0;
	}
	int i = 1;
	string s = "";
	while (n != 0) {
		if (n % (i*(-2)) != 0) {
			n -= i; s += '1';
		}
		else s += '0';
		i *= (-2);
	}
	reverse(s.begin(), s.end());
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
program ABC043D
    implicit none
    integer(8)::i
    integer(8)::flg=0
    character(100000)::s
    read(5,*)s

    do i=1,len_trim(s)-1
        if(s(i:i)==s(i+1:i+1))then
            flg=1
            print'(i0,1x,i0)',i,i+1
            exit
        else if(i<=len_trim(s)-2)then
            if(s(i:i)==s(i+2:i+2))then
                flg=1
                print'(i0,1x,i0)',i,i+2
                exit
            end if
        end if
    end do

    if(flg==0)then
        print'(i0,1x,i0)',-1,-1
    end if
end program ABC043D

Measured memory_bytes: 700
/*
	JAI JAGANNATH!
*/
//@Author : zanj0

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

typedef long long int lli;

#define ff              first
#define ss              second
#define pb              push_back
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            lli x; cin>>x; while(x--)
const lli N = 2005;
lli dp[N];
lli add(lli a, lli b) {
	return ((a  % mod) + (b % mod)) % mod;
}
void zanj0()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
lli dfs(lli sum) {
	if (sum < 0) return 0;
	if (sum == 0) return 1;
	if (dp[sum] != -1) return dp[sum];
	lli ret = 0;
	for (lli i = 3; i <= sum; i++) {
		ret = add(ret, dfs(sum - i));
	}
	return dp[sum] = ret;
}
void solve() {
	memset(dp, -1, sizeof dp);
	lli n;
	cin >> n;
	cout << dfs(n) << endl;
}
int main()
{
	zanj0();
	solve();
	return 0;
}

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

int main() {
  int S, flg = 0;
  cin >> S;
  
  if(S/100 <= 12 && S/100 > 0){
    flg++;
  }
  if(S%100 <= 12 && S%100 > 0){
    flg += 2;
  }
  switch(flg){
    case 0:
      cout << "NA";
      break;
    case 1:
      cout << "MMYY";
      break;
    case 2:
      cout << "YYMM";
      break;
    case 3:
      cout << "AMBIGUOUS";
      break;
  }
  cout << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
#総価値、現金、株数
dp = [[1000,1000,0] for i in range(N+1)]
for i in range(N):
    dp[i+1][0] = max(dp[i][0],dp[i][1]+dp[i][2]*A[i])
    dp[i+1][1] = dp[i+1][0] % A[i]
    dp[i+1][2] = dp[i+1][0] // A[i]
print(dp[N][0])

Measured memory_bytes: 62008
#include <iostream>
#include <unordered_set>

using namespace std;

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

  int N;
  cin >> N;
  unordered_set<long long> set;
  long long a;
  for (int i = 0; i < N; ++i) {
    cin >> a;
    auto it = set.find(a);
    if (it == set.end())
      set.insert(a);
    else
      set.erase(a);
  }
  cout << set.size() << endl;

  return 0;
}


Measured memory_bytes: 4388
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, P, COUNT = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> P;
		if (P != i) COUNT++;
	}
	if (COUNT <= 2) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;string st[200];
  cin>>n>>st[1];int f=0;
  for(int i=2;i<=n;i++){
    cin>>st[i];
     if(st[i-1][st[i-1].length()-1]!=st[i][0])f=1;
    for(int j=1;j<i;j++){
       if(st[i]==st[j])f=1;
     }
  }
  if(f)cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
#include<stack>
using namespace std;
int main(){
    long long int n,a,b;
    cin>>n>>a>>b;
    if(a>b){
        cout<<0<<endl;
    }else if(n==1){
        if(a==b){
            cout<<1<<endl;
        }else{
            cout<<0<<endl;
        }
    }else{
      long long int ans=(n-2)*(b-a)+1;
      cout<<ans<<endl;
    }
}   




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
int dh[4]={-1,1,0,0};
int dw[4]={0,0,1,-1};
int main(){
    int h,w;cin>>h>>w;
    string s[h];
    for(int i=0;i<h;i++)cin>>s[i];
    queue<pipi> q;
    bool used[h][w];
    memset(used,false,sizeof used);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                q.push(make_pair(0,make_pair(i,j)));
                used[i][j]=true;
            }
        }
    }
    int ans=0;
    while(q.size()>0){
        pipi p=q.front();q.pop();
        int dis=p.first,nh=p.second.first,nw=p.second.second;
        ans=max(ans,dis);
        rep(i,0,4){
            int th=nh+dh[i],tw=nw+dw[i];
            if(th<0||th>=h||tw<0||tw>=w)continue;
            if(used[th][tw])continue;
            q.push(make_pair(dis+1,make_pair(th,tw)));
            used[th][tw]=true;
        }
    }
    cout<<ans<<endl;
}




Measured memory_bytes: 14352
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll K,A,B,NUM = 1,total=0;
bool flg = false;


cin >> K >> A >> B;

while(total <= B){

    total = K * NUM;

    if(A <= total && total <= B) flg = true;

    ++NUM;

}

cout << ( flg ? "OK" : "NG") << endl;

return 0;

}

Measured memory_bytes: 3636
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)
#define REPIT(i,x) for(auto i{(x).begin()}; i != (x).end(); i++)

#define PB push_back
#define MP make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

typedef int64_t ll;
typedef double dbl;
typedef vector<bool> Vb;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<string> Vs;
typedef vector<vector<int> > VVi;
typedef vector<vector<ll> > VVl;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }
inline void YES() { cout << "YES" << endl; } inline void Yes() { cout << "Yes" << endl; }
inline void NO() { cout << "NO" << endl; } inline void No() { cout << "No" << endl; }

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

	REP1C(i, 9)
		REP1C(j, 9)
	{
		if (i * j == N)
		{
			Yes();
			return 0;
		}
	}

	No();
}


Measured memory_bytes: 256
#include<iostream>
#define shiharai 1000
using namespace std;
int main(){
    int Aio[2][3] = {0};
    int Bio[2][3] = {0};
    int Cio[2][3] = {0};
    int At[3] = {0};
    int Bt[3] = {0};
    int Ct[3] = {0};
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < 3;j++){
                cin >> Aio[i][j];
        }
    }
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < 3;j++){
                cin >> Bio[i][j];
        }
    }
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < 3;j++){
                cin >> Cio[i][j];
        }
    }
    for(int i = 2;i >= 0;i--){
        At[i]+=(Aio[1][i] - Aio[0][i]);
        if(At[i] < 0){
            At[i]+=60;
            At[i-1]-=1;
        }
        Bt[i]+=(Bio[1][i] - Bio[0][i]);
        if(Bt[i] < 0){
            Bt[i]+=60;
            Bt[i-1]-=1;
        }
        Ct[i]+=(Cio[1][i] - Cio[0][i]);
        if(Ct[i] < 0){
            Ct[i]+=60;
            Ct[i-1]-=1;
        }
    }
    for(int i = 0;i < 3;i++){
        cout << At[i];
        if(i != 2){
            cout << " ";
        }
    }
    cout << endl;
    for(int i = 0;i < 3;i++){
        cout << Bt[i];
        if(i != 2){
            cout << " ";
        }
    }
    cout << endl;
    for(int i = 0;i < 3;i++){
        cout << Ct[i];
        if(i != 2){
            cout << " ";
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3092
#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 INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main()
{
  ll N;
  cin >> N;
  vector<ll> vec=divisor(N);
  ll ans = 0;
  for(auto x:vec){
    if((N-x)/x>x){
      ans+=(N-x)/x;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

bool check(VL &a, ll k, ll d){
    int n = a.size();
    VL r;
    REP(i,n){
        if (a[i] % d) r.push_back(a[i] % d);
    }
    n = r.size();
    if (n == 0) return true;
    sort(ALL(r));
    ll s = 0;
    REP(i,n) s += d - r[i];
    ll x = 0;
    REP(i,n){
        x += r[i];
        s -= d - r[i];
        if (x == s){
            return x <= k;
        }
    }
    return true;
}

int main() {
    ll n, k;
    cin >> n >> k;
    VL a(n);
    ll sum = 0;
    REP(i,n){
        a[i] = in();
        sum += a[i];
    }
    ll ans = 1;
    for (ll x = 1; x * x <= sum; x++){
        if (sum % x == 0){
            if (check(a, k, x)) chmax(ans, x);
            if (check(a, k, sum / x)) chmax(ans, sum / x);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256