akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

const int M = 1000005;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> cnt(M);
    for(int x : a) {
        if(cnt[x] != 0) {
            cnt[x] = 2;
            continue;
        }
        for(int i = x; i < M; i += x) cnt[i]++;
    }
    int ans = 0;
    for(int x : a) {
        if(cnt[x] == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8012
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
int n,m,cnt; 
int d[100005],low[100005],ans;
V<int> v[100005];
void dfs(int p,int lst){
	d[p]=++cnt;
	low[p]=d[p];
	for(auto u:v[p])if(u!=lst){
		if(!d[u]){
			dfs(u,p);
			gmin(low[p],low[u]);
		}else{
			gmin(low[p],d[u]);
		}
	}
	if(low[p]==d[p]&&p!=1){
		ans++;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	int x,y;
	FOR(i,1,m){
		cin>>x>>y;
		v[x].PB(y);
		v[y].PB(x);
	}
	dfs(1,1);
	cout<<ans;
	RE 0;
}


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

long long solve(long long a, long long m) {
  long long count;
  long long x = 1;

  x =(a*x) % m;
  for (count=1; x!=1; count++) {
    x = (a*x) % m;
  }

  return count;
}

long long gcd(long long x1, long long x2) {
  long long m = max(x1, x2);
  long long n = min(x1, x2);

  while (n != 0) {
    long long tmp = n;
    n = m%n;
    m = tmp;
  }
  return m;
}

long long lcm(long long x1, long long x2) {
  long long n_gcd = gcd(x1, x2);
  return (x1/n_gcd)*x2;
}

int main() {
  int a1, a2, a3;
  int m1, m2, m3;
  
  while(scanf("%d %d %d %d %d %d",&a1,&m1,&a2,&m2,&a3,&m3),
	a1||a2||a3||m1||m2||m3) {
    long long count1 = solve((long long)a1, (long long)m1);
    long long count2 = solve((long long)a2, (long long)m2);
    long long count3 = solve((long long)a3, (long long)m3);
    
    printf("%lld\n", lcm(lcm(count1, count2), count3)); 
  }

}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
struct edge{ll to,cost;};
const int inf = 1<<28;
const ll INF = 1LL<<53;
const int COMBMAX = 500005;
const ll MOD = 1e9+7;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;++i)
#define repf(i,n) for(int i=0;i<=n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eachdo(v, e) for(const auto& e : v)
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance(v.begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance(v.begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n,ll mod=MOD){ll res=1;while(n>0){if(n&1)res=res*a%mod;a=a*a%mod;n>>=1;}return res;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v,a)-lower_index(v,a);} 
template<class T> bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
template<class T> void debug2(T v){rep(i,v.size()){rep(j,v[i].size())cout<<v[i][j]<<" ";cout<<endl;}}
template<class T> void rdv(T &v){rep(i,v.size())cin>>v[i];}
template<class T> void rdvv(T &v){rep(i,v.size()){rep(j,v[i].size())cin>>v[i][j];}}
// multimap
// mmap.emplace(key,value);
// auto ngw = list.equal_range("");
// for(auto e = ngw.first; it != ngw.second ; ++e)

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;

    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }

    ll find(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    bool merge(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return find(x) == find(y);
    }

    ll size(ll x) {
        return siz[find(x)];
    }
};


int main(){
    ll N; cin >> N;
    vl p(N); rdv(p);
    vl a(N+1),b(N+1);
    rep1(i,N){
        a[i] = N * (i - 1) + 1;
        b[i] = N * (N - i) + 1;
    }
    rep(i,N){
        a[p[i]] += i; 
    }
    rep1(i, N) cout << a[i] << " ";
    cout << endl;
    rep1(i, N) cout << b[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 1152
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/

	coding: utf-8
	lang: C (GCC 5.4.1)
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int n, m;
	int num[12][12] = { 0 };
	int k;
	int p[12] = { 0 };
	int col;
	int bitcnt, ans = 0;
	bool chkflag;
	
	// input & setup
	scanf("%d %d", &n, &m);
	for (int i = 0; i < 12; ++i){
		for (int j = 0; j < 12; ++j){
			num[i][j] = 0;
		}
	}
	for (int i = 0; i < m; ++i){
		scanf("%d", &k);
		for (int j = 0; j < k; ++j){
			scanf("%d", &col);
			num[i][col - 1] = 1;
		}
	}
	for (int i = 0; i < m; ++i) scanf("%d", &p[i]);
	
	// countup
	for (int i = 0; i < (1 << n); ++i){
		chkflag = true;
		for (int j = 0; j < m; ++j){
			bitcnt = 0;
			for (int l = 0; l < n; ++l){
				if(num[j][l] & i >> l) ++bitcnt;
			}
			if(bitcnt % 2 != p[j]) chkflag = false;
		}
		if(chkflag) ans += 1;
	}
	printf("%d\n", ans);
	return 0;
}


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

using namespace std;

signed main(){
  string s,t;
  cin>>s>>t;
  int ans = 1000000000;
  for(int i = 0; i <= (s.length()-t.length()); i++){
    int cnt = 0;
    for(int j = 0; j< (t.length()); j++){
      if(s[i+j]!=t[j]){
        cnt++;
      }
    }
    ans=min(ans,cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3608
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
const int MAX_N = 100000;
const int MAX_V = 1000000000;
int N;
int X[MAX_N];
int L[MAX_N];

void input(){//N組の入力を受けて配列X, Lに格納
    scanf("%d", &N);
    for(int i = 0; i < N; ++i){
        scanf("%d %d", &X[i], &L[i]);
    }
}

P ps[MAX_N];//typedef pair<int, int> P;

int solve(){
    for(int i = 0; i < N; ++i){
        ps[i] = P(X[i] + L[i], X[i] - L[i]);//ps[i].first:腕の届く最大値/ps[i].second:腕の届く最小値
    }
    sort(ps, &ps[N]);//ps[i].first（＝腕の届く最大値）について、最初の要素から最後の要素までを対象にsort
    int cur = -MAX_V;//確定した腕の届く値の最大値を保持する　これを初期化
    int ans = 0;
    for(int i = 0; i < N; ++i){
        if(cur <= ps[i].second){//ps[i].second:新しい機械の腕の届く最小値が確定した腕の届く値の最大値より大きければそれを採用
        ans++;
        cur = ps[i].first;
        }
    }
    return ans;
}

int main(){
    input();
    int ans = solve();
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 1664
#include <iostream>
 
using namespace std ;
 
int main ()
{
	int a , b ;
	cin >> a >> b;
	
	
	int res=0;
	int sum = 1 ;
	while (sum < b)
	{
		sum += a - 1;
		res++;
	
	}
	
	cout << res ;
}


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

using namespace std;

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

int main() {
	int n;
	double t, a;
	cin >> n;
	cin >> t >> a;
	int ans = 0;
	double d = INT_MAX;
	rep(i, n) {
	    int h;
	    cin >> h;
	    if(abs(t-h*0.006 - a) < d) {
	        d = abs(t-h*0.006 - a);
	        ans = i + 1;
	    }
	}

	cout<< ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;

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

  int n, m; cin >> n >> m;
  // コーナーケース
  if(n >= m) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> x(m);
  rep(i, m) cin >> x[i];
  sort(x.begin(), x.end());

  vector<int> btwn(m-1);
  rep(i, m-1) btwn[i] = x[i+1] - x[i];
  sort(btwn.begin(), btwn.end(), greater<int>());

  int ans = x[m-1]-x[0];
  rep(i, n-1) ans -= btwn[i];

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, N, p1, p2;
  cin >> N >> A >> B;
  p1 = A * N;
  p2 = B;
  if (p1 > p2) {
      cout << p2 << endl;
  }
  else {
      cout << p1 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> x(m);
  for (auto &e : x)
    cin >> e;

  sort(x.begin(), x.end());
  if (n >= m)
  {
    cout << 0 << endl;
    return 0;
  }
  priority_queue<int> q;
  for (int i = 0; i < m - 1; ++i)
  {
    q.push(x[i + 1] - x[i]);
  }
  ll ans = 0;
  for (int i = 0; i < n - 1; ++i)
  {
    ans += q.top();
    q.pop();
  }
  ans = x[m - 1] - x[0] - ans;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1276
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

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

    string s;
    int d;
    cin >> s >> d;
    int n = SZ(s);

    vector<int> num(n);
    rep(i, n){
        num[i] = s[i] - '0';
    }

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(d, vector<int>(2)));
    dp[0][0][1] = 1;
    rep(i, n){
        rep(j, d){
            rep(k, 10){
                dp[i+1][(j+k)%d][0] += dp[i][j][0];
                dp[i+1][(j+k)%d][0] %= MOD;
            }
            rep(k, num[i]){
                dp[i+1][(j+k)%d][0] += dp[i][j][1];
                dp[i+1][(j+k)%d][0] %= MOD;
            }
            dp[i+1][(j+num[i])%d][1] += dp[i][j][1];
            dp[i+1][(j+num[i])%d][1] %= MOD;
        }
    }

    int ans = (dp[n][0][0] + dp[n][0][1]) % MOD;
    ans = (ans + MOD - 1) % MOD;
    cout << ans << endl;

    return 0;
}


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

int main(){
  int i;//与えられる3桁の数
  int i_100, i_10, i_1;//iの100の位,10の位,1の位
  int ans;
  
  cin >> i;
  i_100 = i/100;
  i_10 = (i-i_100*100) / 10;
  i_1 = (i - i_100*100 - i_10*10 );
  
  ans = i_100 + i_10 + i_1;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

int main(){
    int A,B;
    cin>>A>>B;
    int c=0;
    int n=1;
    while(n<B){
        n--;
        n+=A;
        c++;
    }
    cout<<c<<endl;
}


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

int main()
{
	int n = 5;
	
	vector<int> c(n); for (int i = 0; i < n; i++) cin >> c[i];

	int k; cin >> k;

	string ans = "Yay!";

	for (int i = 0; i < n - 1; i++) {

		for (int j = i + 1; j < n; j++) {

			int tmp = max(c[i] - c[j], c[j] - c[i]);

			if (k < tmp) ans = ":(";

		}

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
  vector<int> a(5);
  for(int i=0;i<5;i++) cin>>a[i];
  int k;
  cin>>k;
  bool flag = true;
  for(int i=0;i<5;i++){
    for(int j=i+1;j<5;j++){
      if(a[j]-a[i] > k) flag = false;
    }
  }
  if(flag) cout << "Yay!" << endl;
  else cout << ":(" << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n];
	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
	}
	int ans = 0;
	for (int i = 0; i < n; i+=2)
	{
		if(a[i]&1) ++ans;
	}
	cout<<ans<<endl;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-6;

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

const int64 mod = 1e9+7;

int main(void){
	int32 N;
	while(cin >> N && N){
		bool st[2] = {};
		bool uping = 1;
		int32 cnt = 0;
		REP(i, N){
			string s;
			cin >> s;
			if(s == "lu" && !st[0]){
				st[0] = 1; if(st[1] == 1 && uping){ cnt++; uping = 0; }
			}else if(s == "ru" && !st[1]){
				st[1] = 1; if(st[0] == 1 && uping){ cnt++; uping = 0; }
			}else if(s == "ld" && st[0]){
				st[0] = 0; if(st[1] == 0 && !uping){ cnt++; uping = 1; }
			}else if(s == "rd" && st[1]){
				st[1] = 0; if(st[0] == 0 && !uping){ cnt++; uping = 1; }
			}
		}
		cout << cnt << endl;
	}
}


Measured memory_bytes: 3124
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

signed main() {
	int R, G, B, N;
	cin >> R >> G >> B >> N;
	int cnt = 0;
	for (int i = 0; i <= N / R; i++) {
		for (int j = 0; j <= (N - i * R) / G; j++) {
			if ((N - i * R - j * G) % B == 0)cnt++;
		}
	}
	cout << cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9+5;
const int mod = 1e9+7;
signed main(){
    int n;
    cin >> n;
    if(n==1)cout << 0 << endl;
else cout << 1 << endl;
    return 0;

}


Measured memory_bytes: 3612
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

already = [0]*n
already[0] = 0
now = 0
count = 1
while True:
  count += 1
  now = a[now]-1
  if already[now]:
    k1 = already[now]
    k2 = count-already[now]
    break
  else:
    already[now] = count

if k > k2+k1:
  k -= k2+k1
  k %= k2
  ans = 1
  for i in range(k1):
    ans = a[ans-1]
  for i in range(k):
    ans = a[ans-1]
else:
  ans = 1
  for i in range(k):
    ans = a[ans-1]
print(ans)

Measured memory_bytes: 32332
package main

import (
	"fmt"
)

func main() {
	var N int
	fmt.Scan(&N)
	A := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&A[i])
	}
	ans := 1000000000
	for i := 0; i < N; i++ {
		count := 0
		for A[i]%2 == 0 {
			A[i] = A[i] / 2
			count++
		}
		if ans > count {
			ans = count
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char const *argv[]) {
	long long int mod = 1000000007;
	long long int n ,m;
	cin >> n >> m;
	long long int s[n];
	long long int t[m];
	long long int res[m];

	for (int i = 0; i < m; ++i) {
		res[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < m; ++i) {
		cin >> t[i];
	}

	for (int i = 0; i < n; ++i) {
		long long int a = s[i];
		long long int sum = 0;
		for (int j = 0; j < m; ++j) {
			long long int b = res[j]; 
			if (t[j] == a) {
				res[j] += (1 + sum) % mod;
				res[j] = res[j] % mod;
			}
			sum += b;
			sum = sum %mod;
		}
	}

	int ans =0 ;
	for (int i=0;i< m;i++) {
		ans += res [i];
		ans = ans % mod;
		//cout << "res["<< i<< "] = "<<  res[i] << endl;
	}
	cout /*<< "ans = "*/<< ans + 1<< endl;
	


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> candle(n);
	vector<ll> sum(n,0);
	cin>>candle[0];
	REP(i,n-1){
		cin>>candle[i];
		sum[i] = sum[i-1] + (candle[i] - candle[i-1]);
	}
	ll ans = INF;
	for(int l = 0; l+k-1<n; ++l){
		int r = l+k-1;
		ll tmp = sum[r]-sum[l];
		tmp += min(abs(candle[l]), abs(candle[r]));
		ans = min(ans, tmp);
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  int sum = 0;
  int tmp = n;
  while (0 < tmp) {
    sum += tmp%10;
    tmp /= 10;
  }
  if (n % sum == 0) cout << "Yes" << endl; 
  else             cout <<  "No" << endl;
}

Measured memory_bytes: 256
/**
 *    author:  zjsdut
 *    created: 2020/03/23 15:41:02
 **/
#include <bits/stdc++.h>

using namespace std;

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

template <typename A, typename B> bool chkmin(A &a, const B &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

template <typename A, typename B> bool chkmax(A &a, const B &b) {
  if (b > a) {
    a = b;
    return true;
  }
  return false;
}

template <typename T> istream &operator>>(istream &stream, vector<T> &vec) {
  for (auto &x : vec)
    stream >> x;
  return stream;
}

void scan() {}

template <class T, class... Args> void scan(T &a, Args &... rest) {
  cin >> a;
  scan(rest...);
}

using ll = long long;
using vl = vector<ll>;
using vb = vector<bool>;
using vi = vector<int>;
using pii = pair<int, int>;
template <typename T> using vv = vector<vector<T>>;
#define rng(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define up(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define down(i, b, a) for (int i = int(b); i >= int(a); i--)
#define TOKENPASTE(x, y) x##y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)
#define rep(n)                                                                 \
  for (int TOKENPASTE2(_iter_, __LINE__) = 0,                                  \
                               TOKENPASTE2(_num_, __LINE__) = (int)(n);        \
       TOKENPASTE2(_iter_, __LINE__) < TOKENPASTE2(_num_, __LINE__);           \
       ++TOKENPASTE2(_iter_, __LINE__))
#define FOR(x, cont) for (const auto &x : cont)
#define For(x, cont) for (auto &x : cont)
#define all(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define SZ(x) (int)(x).size()
#define UNIQ(vec) (vec).erase(unique(all(vec)), end(vec))
#define LB(cont, x) int(lower_bound(all(cont), x) - begin(cont))
#define UB(cont, x) int(upper_bound(all(cont), x) - begin(cont))

template <typename T>
ostream &operator<<(ostream &stream, const vector<T> &vec) {
  if (!vec.empty()) {
    stream << vec[0];
    for (size_t i = 1; i != vec.size(); ++i)
      stream << ' ' << vec[i];
  }
  return stream;
}

template <typename T> void print(const vector<T> &t) { cout << t << '\n'; }

template <typename T> void print(const vector<vector<T>> &t) {
  for (const auto &row : t) {
    print(row);
  }
}

template <typename T> void print(const T &t) { cout << t << ' '; }

template <typename T, typename... Args>
void print(const T &t, const Args &... rest) {
  print(t);
  print(rest...);
}

template <typename T> void println(const T &t) { cout << t << '\n'; }

template <typename T, typename... Args>
void println(const T &t, const Args &... rest) {
  print(t);
  println(rest...);
}

int main() {
#if defined LOCAL && !defined DUIPAI
  ifstream in("in.txt");
  cin.rdbuf(in.rdbuf());
#endif
  string s;
  scan(s);
  sort(all(s));
  println(s.front() == s.back() ? "No" : "Yes");
  return 0;
}

Measured memory_bytes: 256
/*Whose woods these are I think I know.
His house is in the village though;
He will not see me stopping here
To watch his woods fill up with snow.

My little horse must think it queer
To stop without a farmhouse near
Between the woods and frozen lake
The darkest evening of the year.

He gives his harness bells a shake
To ask if there is some mistake.
The only other sound’s the sweep
Of easy wind and downy flake.

The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int a[110];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=0,m=0;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    cin>>m;
    pair<int, int> p[m+1];
    for(int i=1;i<=m;++i)
    {
        cin>>p[i].fi>>p[i].se;
    }
    for(int i=1;i<=m;++i)
    {
        lli sum=0ll;
        for(int j=1;j<p[i].fi;++j)
            sum+=a[j];
        sum+=p[i].se;
        for(int j=p[i].fi+1;j<=n;++j)
            sum+=a[j];
        cout<<sum<<endl;
    }
}

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



int main()
{
long A,B,C;
cin>>A>>B>>C;
long counter=0;
while(counter<1000000&&A%2==0&&B%2==0&&C%2==0)
{int copyA,copyB,copyC;
copyA=(B+C)/2;
copyB=(A+C)/2;
copyC=(A+B)/2;
A=copyA;
B=copyB;
C=copyC;
counter++;
}
if(counter==1000000){cout<<-1<<endl;}
else{cout<<counter<<endl;}


}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>

int main(){
  std::string n;
  std::cin >> n;
  for(int i=0;i<n.size();i++){
    if(n[i]=='7'){
      std::cout << "Yes";
      exit(0);
    }
  }
  std::cout << "No";
  return 0;
}

Measured memory_bytes: 3612
import sys
from collections import deque
input = sys.stdin.readline
inf = 10**8
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]


H, W, K = map(int, input().split())
grid = [input().rstrip() for _ in range(H)]


dist = [[inf]*W for _ in range(H)]
node = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 0

# まず一回普通にBFS
memo = []
while node:
    x, y = node.popleft()
    memo.append((x, y))
    d = dist[x][y]
    if d >= K:
        continue
    for dx, dy in zip(DX, DY):
        nx = x + dx
        ny = y + dy
        if nx < 0 or ny < 0 or nx >= H or ny >= W:
            continue
        if grid[nx][ny] == "#":
            continue
        if dist[nx][ny] > d + 1:
            dist[nx][ny] = d + 1
            node.append((nx, ny))


ans = inf
for x, y in memo:
    d = min(x, y, H - x - 1, W - y - 1)
    ans = min(ans, 1 + (d + K - 1) // K)
print(ans)

Measured memory_bytes: 124468
#include<iostream>
using namespace std;
const int maxn=1e5+10;
int n,a[maxn],b[maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(i==1)
		    cout<<b[i];
		else
			cout<<" "<<b[i];
	}
	return 0;
}


Measured memory_bytes: 4316
x1, y1, x2, y2 = map(int, input().split())

x3 = str(y1 - y2 + x2)
x4 = str(y1 - y2 + x1)
y3 = str(x2 - x1 + y2)
y4 = str(x2 - x1 + y1)

print(x3 + ' ' + y3 + ' ' + x4 + ' ' + y4)

Measured memory_bytes: 38256
#include <iostream>

using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b;

    cin>>a>>b;

    if(a >= 1 && a <= 9 && b >= 1 && b <= 9){
        cout<<a*b;
    }else{
        a = -1;
        b = 1;
        cout<<a*b;
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[4];
int main()
{
    int i,j,k;
    scanf("%d%d%d",&a[0],&a[1],&a[2]);
    sort(a,a+3);
    k=a[2]-a[0];
    printf("%d\n",k);
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
    int n,a,b,num;
    scanf("%d %d %d", &n, &a, &b);
    int sum = 0;
    int ans = 0;
    int i; //sum�͌��̍��v

    for(i=1; i<=n; i++){
        sum = 0;
        num = i;
        while(num>0){
            sum += num%10;
            num = num/10;
        }
        if(sum >=a && sum <= b){
            ans += i ;
        }
    }

    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back;
const int N = 1e5 + 5;
ll dp[105][N];
ll a[3][N];
ll n, w;
ll res(ll i, ll q){
    if(q>w)return -1e15;
    if(q == w || i == n+1)return 0;
    if(dp[i][q] != -1)return dp[i][q];
    dp[i][q] = 0;
    
    dp[i][q] = max(res(i+1,q), a[2][i+1] + res(i+1, q + a[1][i+1]));
    
    return dp[i][q];
}
int main(){
        
    cin >> n >> w;
    //memset(dp,-1, sizeof(dp)/sizeof(dp[0]));
   memset(dp , -1, sizeof(dp));
   for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 2; j++){
            cin >> a[j][i];
        }
   }
    cout<<res(0, 0);
}

Measured memory_bytes: 82688
W, H, N = map(int, input().split())
input_li = [list(map(int, input().split())) for i in range(N)]
dic = {"1" : 0, "2": W, "3" : 0, "4" : H}
for l in input_li :
    if l[2] == 1 and dic[str(l[2])] < l[0] :
        dic[str(l[2])] = l[0]
    if l[2] == 2 and dic[str(l[2])] > l[0] :
        dic[str(l[2])] = l[0]
    if l[2] == 3 and dic[str(l[2])] < l[1] :
        dic[str(l[2])] = l[1]
    if l[2] == 4 and dic[str(l[2])] > l[1] :
        dic[str(l[2])] = l[1]
if dic["2"] - dic["1"] < 0 and dic["4"] - dic["3"] < 0 :
    print(0)
else :
    print(max(0, (dic["2"] - dic["1"]) * (dic["4"] - dic["3"])))


Measured memory_bytes: 3064
using System;
using System.Linq;

namespace _0238
{
    class Program
    {
        static void Main(string[] args)
        {
            while(true)
            {
                int t = int.Parse(Console.ReadLine());
                if(t==0)
                {
                    break;
                }
                int n = int.Parse(Console.ReadLine());
                int X = 0;
                for(int i=0;i<n;i++)
                {
                    int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                    X += x[1] - x[0];
                }
                if(t<=X)
                {
                    Console.WriteLine("OK");
                }
                else
                {
                    Console.WriteLine(t - X);
                }
            }
        }
    }
}

Measured memory_bytes: 9652
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <set>

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 FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Point {
  ll x;
  ll y;
  int type;
  Point() {;}
  Point(double x, double y, int type) : x(x), y(y), type(type) {;}
  bool operator<(const Point &rhs) const {
    if (fabs(y - rhs.y) > EPS) { return y < rhs.y; }
    if (fabs(x - rhs.x) > EPS) { return x < rhs.x; }
    return false;
  }
};

struct Event {
  int x;
  Point p;
  int in;
  Event() {;}
  Event(int x, Point p, int in) : x(x), p(p), in(in) {;}
  bool operator<(const Event &rhs) const {
    if (x != rhs.x) { return x < rhs.x; }
    return in > rhs.in;
  }
};

inline ll square(ll x) { return x * x; }

inline ll dist2(const Point &a, const Point &b) {
  return square(a.x - b.x) + square(a.y - b.y);
}

int an, bn, n;
ll r;
Event event[500000];

int PlaneSweep() {
  int ans = 0;
  set<Point> open;
  REP(iter, n) {
    Event &e = event[iter];
    Point &p = e.p;
    if (e.in) {
      set<Point>::iterator lower = open.lower_bound(Point(0, p.y - 4.0 * r - 1, 0));
      set<Point>::iterator upper = open.upper_bound(Point(0, p.y + 4.0 * r + 1, 0));
      for (set<Point>::iterator it = lower; it != upper; it++) {
        if (dist2(*it, p) <= 16.0 * r * r) {
          ans += p.type ^ it->type;
        }
      }
      open.insert(p);
    } else {
      open.erase(open.find(p));
    }
  }
  return ans;
}

int main() {
  while (scanf("%d %d %lld", &an, &bn, &r), an|bn) {
    n = (an + bn) * 2;
    REP(i, an) {
      ll x, y;
      scanf("%lld %lld", &x, &y);
      event[2 * i + 0] = Event(x - 2 * r, Point(x, y, 0), 1);
      event[2 * i + 1] = Event(x + 2 * r, Point(x, y, 0), 0);
    }
    REP(i, bn) {
      ll x, y;
      scanf("%lld %lld", &x, &y);
      event[2 * an + 2 * i + 0] = Event(x - 2 * r, Point(x, y, 1), 1);
      event[2 * an + 2 * i + 1] = Event(x + 2 * r, Point(x, y, 1), 0);
    }
    sort(event, event + n);
    int ans = PlaneSweep();
    printf("%d\n", ans);
  }
}

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

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  int good = 0, bad = 0;
  for (int i = 0; i < n; ++i) {
    int foo;
    scanf("%d", &foo);
    if (foo % 4 == 0) {
      ++good;
    } else {
      if (foo % 2 == 1) {
        ++bad;
      }
    }
  }
  if (bad == 0) {
    puts("Yes");
    return 0;
  }
  if (bad == 1) {
    puts(good != 0 ? "Yes" : "No");
    return 0;
  }
  if (good < bad - 1) {
    puts("No");
    return 0;
  }
  if (good > bad - 1) {
    puts("Yes");
    return 0;
  }
  puts(good + bad == n ? "Yes" : "No");
}

Measured memory_bytes: 256
import sys
 
n = int(raw_input())
a = [0,0,0]
 
for i in range(n):
    a[0],a[1],a[2] = map(int,raw_input().split())
    a.sort()
    if a[0]**2 + a[1]**2 == a[2]**2:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 6340
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    if (s.begin() == s.end()) return os << "}";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    if (m.begin() == m.end()) return os << "}";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

lint pow(lint num, lint e, lint MOD) {
    lint res = 1;
    lint cur_num = num;
    while (e) {
        if (e & 1) {
            res *= cur_num;
            res %= MOD;
        }
        cur_num *= cur_num;
        cur_num %= MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    string s;
    cin >> s;
    lint first_A = s.size(), last_Z = -1;
    range(i, 0, s.size()) {
        if (s.at(i) == 'Z') last_Z = i;
    }
    reversed_range(i, 0, s.size()) {
        if (s.at(i) == 'A') first_A = i;
    }
    cout << last_Z - first_A + 1 << "\n";
}

Measured memory_bytes: 720
//  Copyright © 2020 Diego Garcia Rodriguez del Campo. All rights reserved.
#include<bits/stdc++.h>
#define MAX 200005
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
#define forn(i,a,b) for (ll i = a; i <= b; i ++ )
#define mod(n,k) (((n%k)+k)%k)
using namespace std;
typedef long long ll;

ll N, K, ans, dp[MAX];
const ll MOD = 1e9 + 7;

ll fastpow( ll b , ll e ) {
    ll ans = 1;
    while( e > 0 ) {
        if( e & 1 )
            ans = ( ans * b ) % MOD;
        
        b = ( b * b ) % MOD;
        e >>= 1;
    }
    return ans;
}

int main()
{
    optimiza_io
    cin >> N >> K;
    for( ll k = K; k >= 1; k -- ) {
        ll tot = K / k;
        dp[k] = fastpow( tot , N );
        for( ll i = 2*k; i <= K; i += k )
            dp[k] = ( dp[k] - dp[i] + MOD ) % MOD;
        ans += dp[k] * k;
        ans %= MOD;
    }
    
    cout << ans << "\n";
    return 0;
}

// CHECAR LIMITES 

Measured memory_bytes: 4416
#include <bits/stdc++.h>
#include <stdint.h>
#include <algorithm>
#include <vector>


using namespace std;

int main() {
	
	int N;
	string s;
	cin >> N;
	
	int ab = 0;
	int endA = 0;
	int beginB = 0;
	int BandA = 0;
	int flag = 0;
	
	for (int i = 0;i < N; i++) {
		flag = 0;
		cin >> s;
		for (int j = 0; j < s.size()-1;j++){
			if(s.at(j)=='A' && s.at(j+1)=='B'){
				ab++;
			}
		}
		if(s.at(0)=='B'){
			beginB++;
			flag++;
		}
		if(s.at(s.size()-1)=='A'){
			endA++;
			if (flag > 0) {
				BandA++;
			}
		}
		
//	cout << "turn:" << i << ",ab:" << ab << ",endA:" << endA << ",beginB:" << beginB << endl;

	}
	int ans = ab+min(endA,beginB);
	if((endA == N) && (beginB == N)) {
		ans--;
	} else if ((endA == BandA) && (beginB == BandA)){
		if (ans > 0 && BandA > 0) ans--;
	}
	
	cout << ans << endl;
		
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    vector<int> p(3);
    rep(i,3) cin>>p[i];
    sort(btoe(p));
    cout<<p[2]-p[0]<<endl;  
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> >vvi;
const ll MOD=1000000007LL;
int main(){
  int n,W;
  cin>>n>>W;
  vi v(n),w(n);
  rep(i,n)cin>>v[i]>>w[i];
  vector<int>dp(W+1);
  for(int i=0;i<n;i++){
    for(int j=W;j>=w[i];j--){
      dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
  }
  cout<<dp[W]<<endl;
}


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

using namespace std;

int main() {
  char c;
  cin >> c;
  char s[6] = "aiueo";
  bool flag = 0;

  for( int i = 0; i < 5; i++ ) {
    if( c == s[i] ) {
      cout << "vowel" << endl;
      flag = 1;
      break;
    }
  }
  if( flag == 0 )
    cout << "consonant" << endl;
  return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn._
object Main{
  def main(args:Array[String]){
    val N = readLine.toInt 
    var ta = readLine.split(' ').map(_.toLong)
    var u = ta(0)
    var v = ta(1)
    for(i <- 0 until N-1){
      ta = readLine.split(' ').map(_.toLong)
      var t = ta(0)
      var a = ta(1)
      if(u > t || v > a){
        val d1 = (u + t - 1l) / t
        val d2 = (v + a - 1l) / a
        val d = d1.max(d2)
        t *= d
        a *= d
      }
      u = t
      v = a
    }
    println(u+v)
  }
}


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

int main() {
    int n, m;
    cin >> n >> m;
    int a[n], b[n], c[m], d[m];
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    for (int i = 0; i < m; i++)
        cin >> c[i] >> d[i];

    for (int i = 0; i < n; i++) {
        int dist = abs(a[i] - c[0]) + abs(b[i] - d[0]);
        int idx = 1;
        for (int j = 1; j < m; j++) {
            if (abs(a[i] - c[j]) + abs(b[i] - d[j]) < dist) {
                dist = abs(a[i] - c[j]) + abs(b[i] - d[j]);
                idx = j + 1;
            }
        }
        cout << idx << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include"iomanip"
#include"iostream"
#include"limits"
#include"cmath"
#include"vector"
#include"algorithm"
#include"list"
#include"queue"
#include"stack"
#include"set"
#include"unordered_set"
#include"map"
#include"unordered_map"
#include"string"
#include"cstring"
#include"assert.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define mp make_pair
#define pb push_back
#define mset(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=305;
ll sho[maxn][maxn];
ll ans[maxn][maxn];
struct edg
{
	int u,v;
	ll co;
	bool operator<(const edg & ob)
	{
		return co<ob.co;
	}
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n;
	cin>>n;
	vector<edg>ed;
	for(int i=0;i<n;++i)for(int j=0;j<n;++j)
	{
		cin>>sho[i][j];
		if(i<j)
		{
			edg ob;
			ob.u=i;ob.v=j;
			ob.co=sho[i][j];
			ed.pb(ob);
		}
		if(i!=j)
			ans[i][j]=1e15;
		else ans[i][j]=0;
	}
	bool aa=true;
	for(int k=0;k<n;++k)
	{
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<n;++j)
			{
				if(sho[i][k]+sho[k][j]<sho[i][j])
					aa=false;
			}
		}
	}
	if(!aa)
	{
		cout<<"-1\n";
		return 0;
	}
	ll pp=0;
	sort(all(ed));
	for(edg ob:ed)
	{
		int u=ob.u,v=ob.v;
		ll co=ob.co;
		bool a=true;
		for(int k=0;k<n;++k)
		{
			ans[u][v]=min(ans[u][v],ans[u][k]+ans[k][v]);
			ans[v][u]=ans[v][u];
			/*
			if(ans[u][k]+ans[k][v]==co)
			{
				a=false;
			}
			*/
		}
		if(ans[u][v]>co)
		{
			ans[u][v]=co;
			ans[v][u]=co;
			pp+=co;
		}
		for(int i=0;i<n;++i)
		{
			ans[u][i]=min(ans[u][i],ans[u][v]+ans[v][i]);
			ans[i][u]=ans[u][i];
			ans[v][i]=min(ans[v][i],ans[v][u]+ans[u][i]);
			ans[i][v]=ans[v][i];
		}
	}
	cout<<pp<<'\n';

}















Measured memory_bytes: 2548
a_list = list(input())[::-1]
b_list = list(input())[::-1]
c_list = list(input())[::-1]

target = a_list.pop()
ans = ''

while True:
  
  if target == 'a':
    if len(a_list) == 0:
      ans = 'A'
      break
    else:
      target = a_list.pop()
      
  elif target == 'b':
    if len(b_list) == 0:
      ans = 'B'
      break
    else:
      target = b_list.pop()
      
  elif target == 'c':
    if len(c_list) == 0:
      ans = 'C'
      break
    else:
      target = c_list.pop()
      
print(ans)

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), true);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.flush();
		out.close();
	}
}

class Pair {
	int a[];

}

class TaskB {

	public void solve(int testNumber, InputReader in, PrintWriter pw) {
		int N = in.nextInt();
		int W = in.nextInt();
		long dp[] = new long[W + 1];
		for (int i = 0; i < N; i++) {
			int w = in.nextInt();
			long val = in.nextLong();
			for (int weight_already = W - w; weight_already >= 0; weight_already--) {
				dp[weight_already + w] = Math.max(dp[weight_already + w], dp[weight_already] + val);
			}
		}
		long ans = -1;
		for (int i = 0; i < W + 1; i++) {
			ans = Math.max(ans, dp[i]);
		}
		pw.println(ans);
	}

	int __gcd(int a, int b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);

	}

	public int getInt(int num) {
		int ret = -1;
		switch (num) {
		case 0:
			ret = 6;
			break;
		case 1:
			ret = 2;
			break;
		case 2:
			ret = 5;
			break;
		case 3:
			ret = 5;
			break;
		case 4:
			ret = 4;
			break;
		case 5:
			ret = 5;
			break;
		case 6:
			ret = 6;
			break;
		case 7:
			ret = 3;
			break;
		case 8:
			ret = 7;
			break;
		case 9:
			ret = 6;
			break;
		}
		return ret;
	}

	public int isPow(long num) {
		int count = 0;
		while (num > 0) {
			num /= 2;
			count++;
		}
		return count;
	}
}

class InputReader {
	BufferedReader br;
	StringTokenizer st;

	public InputReader(InputStream in) {
		br = new BufferedReader(new InputStreamReader(in));
		st = null;
	}

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

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

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

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


Measured memory_bytes: 27196
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class E
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		var N = GetString().Select(x => (int)(x - '0')).ToList();
		N.Reverse();

		int L = N.Count;	
		int INF = int.MaxValue / 2;
		var dp = new int[L + 1, 2];
		for(int i = 0; i <= L; i++)
		{
			for(int j = 0; j < 2; j++)
				dp[i, j] = INF;
		}
		dp[0, 0] = 0;

		for(int i = 0; i < L; i++)
		{
			for(int j = 0; j < 2; j++)
			{
				for(int k = 0; k < 10; k++)
				{
					int a = (j == 0) ? k : (k + 9) % 10;
					int b = (a < N[i]) ? 10 + a - N[i] : a - N[i];
					int c = ((j == 1 && k == 0) || a < N[i]) ? 1 : 0;
					chmin(ref dp[i + 1, c], dp[i, j] + k + b);
				}
			}
		}
		WriteLine(Min(dp[L, 0], dp[L, 1] + 1));
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => Enumerable.Range(0, (int)N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(long N) => Enumerable.Range(0, (int)N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDouble()).ToArray();
	public static decimal[] GetDecimals(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDecimal()).ToArray();
	public static string[] GetStrings(long N) => Enumerable.Range(0, (int)N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 31072
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

ll next_power(ll x) {
  ll pow = 1;
  while (pow <= x) {
    pow *= 2;
  }
  return pow;
}

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  multiset<ll, greater<ll>> balls;
  REP(i,0,n) {
    ll a;
    cin >> a;
    balls.emplace(a);
  }
  ll ans = 0;
  while (! balls.empty()) {
    auto max_it = balls.begin();
    ll max_b = *max_it;
    balls.erase(max_it);
    ll sum = next_power(max_b);
    auto opponent = balls.find(sum - max_b);
    if (opponent != balls.end()) {
      ans++;
      balls.erase(opponent);
    }
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

//実行部
void Main()
{
  str s;
  cin >> s;
  if(s.size() < 5) fin("NO");
  str flag = "AKIHABARA";
  if (s[0] != 'A')
  {
    s = "A" + s;
  }
  if (s[4] != 'A')
  {
    s = s.substr(0, 4) + "A" + s.substr(4);
  }
  if (s[6] != 'A')
  {
    s = s.substr(0, 6) + "A" + s.substr(6);
  }
  if (s[8] != 'A')
  {
    s = s + "A";
  }
  if (s == flag) fin("YES");
  fin("NO");
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 256