akhauriyash/Code-Regression huggingface dataset:
N = int(input())
costs = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dps = [[inf for _ in range(N)] for _ in range(N)]


for k in range(N):
    for i in range(N):
        for j in range(N):
            # costs[i][j]は最短経路でないといけない。
            if costs[i][j] > costs[i][k] + costs[k][j]:
                print(-1)
                exit()
max_cost = 0


for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if k == i or k == j:
                continue
            if costs[i][j] == costs[i][k] + costs[k][j]:
                flag = False
                break
        if flag:
            max_cost += costs[i][j]
print(max_cost)


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<pair<T, T>>& vp) {
	for (int i = 0; i < vp.size(); ++i) {
		s << "(" << vp[i].first << "," << vp[i].second << ")" << ( i+1 == vp.size() ? "" : ",\t" );
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
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...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

LL gcd(LL a,LL b) {
	LL bigger = max(a,b);
	LL smaller = min(a,b);
	if (smaller == 0) return bigger;
	if (smaller < 0) {
		cerr << "smaller of gcd is negative number" << endl;
		return 1;
	}
	if (bigger % smaller != 0) {
		return gcd(smaller,(bigger % smaller));
	}
	return smaller;
}

//main code
int main(int argc, char const* argv[])
{
	LL n,X;
	cin >> n >> X;
	VL x(n);
	cin >> x;
	VL d_from_X(n);
	for (int i = 0; i < n; i++) {
		d_from_X[i] = abs(x[i] - X);
	}

	LL ans = d_from_X[0];
	for (int i = 1; i < n; i++) {
		ans = gcd(ans, d_from_X[i]);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 1792
// educational dp - frog 2
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pr cout<<
#define in cin>>
#define tc(t) ll t;cin>>t;while(t--)
#define fr(i,n) for(ll i=0;i<n;i++)
#define mod 1e9+7
#define nl pr "\n"
#define rt return
//ll a[10000];


int main()
{
    ll n,k;
    in n;
    in k;
    ll a[n];
    fr(i,n) in a[i];
    ll dp[n];
    fr(i,n) dp[i]=mod;
    dp[0]=0;
    fr(i,n)
    {
        for(ll j=1;j<=k;j++)
            if(i+j<n)
                dp[i+j]=min(dp[i]+abs(a[i]-a[i+j]),dp[i+j]);
    }
    //fr(i,n) pr dp[i];
    pr dp[n-1];
	rt 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();

		if (a >= 2800) {

			System.out.println("AGC");

		} else if (a >= 1200) {

			System.out.println("ARC");

		} else {

			System.out.println("ABC");
		}

	}
}


Measured memory_bytes: 21716
using System;
 
namespace abc052
{
    public class Program
    {
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
 
            int a = Convert.ToInt32(str[0]);
            int b = Convert.ToInt32(str[1]);
            int c = Convert.ToInt32(str[2]);
            int d = Convert.ToInt32(str[3]);
 
            int rectangle1 = a * b;
            int rectangle2 = c * d;
 
            if (rectangle1 == rectangle2)
            {
                Console.WriteLine(rectangle1.ToString());
            }
            else if(rectangle1 > rectangle2)
            {
                Console.WriteLine(rectangle1.ToString());
            }
            else
            {
                Console.WriteLine(rectangle2.ToString());
            }
        }
    }
}

Measured memory_bytes: 2776
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<functional>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;

ll N;
ll a[100010];
ll b[100010];
string s;
int main(){
    cin>>N;
    for(int i=0;i<N+1;i++){
        cin>>a[i];
    }
    for(int i=0;i<N;i++){
        cin>>b[i];
    }
    ll ans=0;
    for(int i=0;i<N;i++){
        if(a[i]<b[i]){
            ans+=a[i];
            b[i]-=a[i];
            ans+=min(b[i],a[i+1]);
            a[i+1]=max(a[i+1]-b[i],0LL);
            //cout<<a[i+1]<<endl;
            
            //cout<<min(b[i],a[i+1])<<endl;
        }else{
            ans+=b[i];
        }
        //cout<<ans<<endl;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//Guidebook
struct rest{
	int id;
	string place;
	int score;
 	rest(int i,string p, int s){
 		id = i;
		place = p;
		score = s;
 	}
};

bool cmp(const rest &a, const rest &b){
	if(a.place !=  b.place){
		return a.place < b.place;
	}else{
		return a.score > b.score;
	}
}
int main(){
	int n;
	cin >> n;
	vector<rest> rests;
	for(int i=0;i<n;i++){
		string place_i;
		int score_i;
		cin >> place_i >> score_i;
		rests.push_back(rest(i+1,place_i,score_i));
	}
	sort(rests.begin(),rests.end(),cmp);
	for(int i= 0;i<n;i++){
		cout << rests[i].id << endl;
	}
	return 0;
}


Measured memory_bytes: 256
def resolve():
    '''
    code here
    '''
    A, B, C, D = [int(item) for item in input().split()]

    turn = 0
    while A > 0 and C > 0:
        turn += 1
        # print(turn, A, C)

        if turn % 2 == 1:
            C -= B
        else:
            A -= D
        
        # print(A, C)
    
    
    if A <= 0:
        print('No')
    else:
        print('Yes')

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9180
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>

using namespace std;

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(b - a == c - b) cout << "YES" << endl;
    else cout << "NO" << endl;
}


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

#ifndef ULLONG
typedef unsigned long long ULLONG;
#endif
#ifndef LLONG
typedef long long LLONG;
#endif

static void D_task();

int main()
{
	D_task();
	
	fflush(stdout);
	return 0;
}

class D_set
{
public:
	int Bm = 0;
	int Cm = 0;
	int greaterCount = 0;

	static bool sort_cm_asc(const D_set& a, const D_set& b) {
		return(a.Cm < b.Cm);
	}
	static bool sort_cm_dsc(const D_set& a, const D_set& b) {
		return(a.Cm > b.Cm);
	}
};

static void D_task()
{
	int N, M;
	scanf(" %d %d", &N, &M);

	int A;
	std::map<int, LLONG> numbers;
	for (int i = 0; i < N; i++) {
		scanf(" %d", &A);
		numbers[A] += 1;
	}

	D_set card;
	std::vector<D_set> vCards;
	for (int i = 0; i < M; i++) {
		scanf(" %d %d", &(card.Bm), &(card.Cm));
		vCards.push_back(card);
	}

	//std::sort(vCards.begin(), vCards.end(), D_set::sort_cm_asc);
	std::sort(vCards.begin(), vCards.end(), D_set::sort_cm_dsc);

	int sortEnd = 0;
	for (int j = 0; j < M; j++) {
		auto numIt = numbers.begin();
		while ((vCards[j].Cm > numIt->first) && (numIt->second) && (vCards[j].Bm)) {
			vCards[j].Bm--;
			numIt->second--;
			if (numIt->second == 0) {
				numbers.erase(numIt->first);
			}
			numbers[vCards[j].Cm] += 1;
			numIt = numbers.begin();
		}
	}

	LLONG sum = 0;
	for (auto it = numbers.begin(); it != numbers.end(); it++) {
		sum += (it->first) * (it->second);
	}
	printf("%lld\n", sum);
}


Measured memory_bytes: 8184
#include <stdio.h>
int main(void){
    int a,b,c,x;
    scanf("%d %d %d",&a,&b,&c);
    if(a<=b && b<=c){
        }
        else if(a<=c && c<=b){
            x = c;
            c = b;
            b = x;
        }
        else if(b<=a && a<=c){
            x = a;
            a = b;
            b = x;
        }
        else if(b<=c && c<=a){
            x = a;       
            a = b;
            b = c;
            c = x;
        }
            else if(c<=a && a<=b){
            x = a;
            a = c;
            c = b;
            b = x;
        }
        else if(c<=b && b<=a){
            x = a;
            a = c;
            c = x;
        }
    printf("%d %d %d\n",a,b,c);
    return 0;
}



Measured memory_bytes: 2040
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}


int main() {
  string s; cin >>s;
  int n = s.size();
  int res = 0;
  char c = s.at(n/2);
  if (n % 2 == 0){
    int x = n/2-1, y = n/2;
    if (s[x] != s[y]) res = n/2;
    else{
      while (x-1 >= 0 && y < n && s[x-1] == c && s[y+1] == c){
        x--; y++;
      }
      res = y + 1;
    }
  }else{
    int x = n/2-1, y = n/2+1;
    if (s[x] != c || s[y] != c) res = n/2+1;
    else{
      while (x-1 >= 0 && y < n && s[x-1] == c && s[y+1] == c){
        x--; y++;
      }
      res = y + 1;
    }
  }
  cout <<res <<endl;
}


Measured memory_bytes: 512
function bomb(y,x){
   var dy=[-1,-1,-1,0,0,1,1,1];
   var dx=[-1,0,1,-1,1,-1,0,1];
   for(var i=0;i<8;i++){
      var yy=y+dy[i];
      var xx=x+dx[i];
      if(yy<0 || yy>=H || xx<0 || xx>=W)continue;
      if(yx[yy][xx]=="a"){yx[yy][xx]=cnt;bomb(yy,xx);}
   }
}

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var WH=(Arr.shift()).split(" ").map(Number);
   var W=WH[0];
   var H=WH[1];
   if(W==0 && H==0)break;
      var yx=[];
      var Y,X;
      for(var i=0;i<H;i++){
         var str=Arr.shift();
         str=str.replace(/1/g,"a");
         var arr=str.split(" ");
         yx.push(arr);
      }
     var cnt=0;
     for(var i=0;i<H;i++){
        for(var j=0;j<W;j++){
           if(yx[i][j]=="a"){cnt++;yx[i][j]=cnt;bomb(i,j);}
        }
     }
      console.log(cnt);
}

Measured memory_bytes: 10364
#define CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void)
{
	int a;
	int b = 3600;
	int c = 60;

	scanf("%d", &a);

	printf("%d:", a / b);
	printf("%d:",( a -( a / b * 3600))/ 60);
	printf("%d\n", (a - ((a / b * 3600) + (((a - (a / b * 3600)) / 60) * 60))));
	
	return 0;
}


Measured memory_bytes: 2140
#include <stdio.h>

#define EPSILON 1.0e-6

int main(int argc, char** argv)
{
  double x1, y1, x2, y2, x3, y3, xp, yp;

  while (fscanf(stdin,
		"%lf %lf %lf %lf %lf %lf %lf %lf",
		&x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp) == 8) {

    double s = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);

    double u = ((xp - x1) * (y3 - yp) - (yp - y1) * (x3 - xp)) / s;
    double v = ((x2 - x1) * (yp - y2) - (y2 - y1) * (xp - x2)) / s;

    if (u > -EPSILON && v > -EPSILON && u + v < 1.0 + EPSILON) {
      fputs("YES\n", stdout);
    }
    else {
      fputs("NO\n", stdout);
    }
  }
}

Measured memory_bytes: 0
N,M=list(map(int, input().split()))
KA=[[0,0]]*N
for i in range(0,N):
    KA[i]=list(map(int, input().split()))
MS=[0]*M
for i in range(0,N):
    for j in range(1,len(KA[i])):
        MS[KA[i][j]-1]+=1
print(MS.count(N))

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

public class Main {
	private static FastScanner sc = new FastScanner();

	public static void main(String[] args) {
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		if(A + B >= 10) {
			System.out.println("error");
		} else {
			System.out.println(A + B);
		}
	}

	static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}


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

#define int ll

#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

int32_t main() {
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	int res = 0;
	res += min(a, k);
	k -= min(a, k);
	k -= min(b, k);
	res -= min(c, k);
	k -= min(c, k);
	assert(k == 0);
	cout << res << '\n';
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    rep(i,V){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    rep(i,V){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};
class UnionFind
{
public:
  int par[100005];
  int depth[100005];
  int nGroup[100005];
 
  UnionFind(int n) {
    init(n);
  }
 
  void init(int n) {
    for(int i=0; i<n; i++) {
      par[i] = i;
      depth[i] = 0;
      nGroup[i] = 1;
    }
  }
 
  int root(int x) {
    if(par[x] == x) {
      return x;
    } else {
      return par[x] = root(par[x]);
    }
  }
 
  bool same(int x, int y) {
    return root(x) == root(y);
  }
 
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return;
 
    if(depth[x] < depth[y]) {
      par[x] = y;
      nGroup[y] += nGroup[x];
      nGroup[x] = 0;
    } else {
      par[y] = x;
      nGroup[x] += nGroup[y];
      nGroup[y] = 0;
      if(depth[x] == depth[y])
        depth[x]++;
    }
  }
};
const ll MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
} 
int main() {
ll n; cin>>n;
graph g(n);
rep(i,n-1){
ll a,b,c; cin>>a>>b>>c;
g.add_edge(a-1,b-1,c);
g.add_edge(b-1,a-1,c);
}
ll q,k; cin>>q>>k;
g.dijkstra(k-1);
rep(i,q){
ll x,y; cin>>x>>y;
cout << g.d[x-1]+g.d[y-1] << endl;}
}


Measured memory_bytes: 14080
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, N) for(int i = 0; i < N; i++)

int A, B, C;

int main() {
    cin >> A >> B >> C;
    cout << min(C, B/A) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cout << (a) << endl

typedef pair<int,int> P;

const int INF = 100000009;
int m, n;
int dist[101][101];
bool used[101];
int f, t, c;

int solve() {
	memset(used, 0, sizeof(used));

	priority_queue<P, vector<P>, greater<P> > que;
	used[0] = true;
	REP(i,m) {
		if(dist[0][i] != INF) {
			que.push(P(dist[0][i], i));
		}
	}

	int cost = 0;
	while(!que.empty()) {
		P p = que.top();
		que.pop();

		int from = p.second;
		if(used[from]) continue;
	
		used[from] = true;
		cost += p.first;
		REP(i,m) {
			if(dist[from][i] != INF && !used[i]) {
				que.push(P(dist[from][i], i));
			}
		}
	}
	return cost;
}

void coding() {
	while(scanf("%d", &m) != EOF) {
		if(m == 0) break;
		scanf("%d", &n);

		REP(i,m) {
			REP(j,m) {
				dist[i][j] = INF;
			}
		}

		REP(i,n) {
			scanf("%d,%d,%d", &f, &t, &c);
			c = c / 100 - 1;
			dist[f][t] = c;
			dist[t][f] = c;
		}
		printf("%d\n", solve());
	}
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
	freopen("a.in", "r", stdin);
#endif

	coding();

#ifdef _LOCAL_TEST
	cout << endl;
	cout << "This is local test" << endl;
	cout << "Do not forget to comment out _LOCAL_TEST" << endl;
#endif
}

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

int main()
{
	ll n;
	cin>>n;
	ll ar[n]={0};
	ll z=0;
	for(ll i=0;i<n;i++)
	{
		cin>>ar[i];
		if(ar[i]==0)
			z++;
	}
	if(z>0)
	{
		cout<<'0'<<endl;
		return 0;
	}
	ll res=1;
	for(ll i=0;i<n;i++)
	{
		if(ar[i]<=1000000000000000000/res)
		{
			res=res*ar[i];
		}
		else
		{
			cout<<"-1"<<endl;
			return 0;
		}
	}
	cout<<res<<endl;
	return 0;
}
	

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

struct UnionFind
{
	vector<int> uni;

	UnionFind(int n) : uni(n, -1) {}
	int root(int a)
	{
		if (uni[a] < 0) return a;
		return uni[a] = root(uni[a]);
	}

	bool connect(int a, int b)
	{
		a = root(a);
		b = root(b);
		if (a == b) return false;
		if (uni[a] > uni[b])
		{
			a ^= b;
			b ^= a;
			a ^= b;
		}
		uni[a] = uni[a] + uni[b];
		uni[b] = a;
		return true;
	}

	bool isConnect(int a, int b)
	{
		return root(a) == root(b);
	}

	int size(int a)
	{
		return -uni[root(a)];
	}
};

signed main(void)
{
	int n, q;
	cin >> n >> q;
	UnionFind uf(n);
	rep(i, q)
	{
		int t, u, v;
		cin >> t >> u >> v;
		if (t == 0)
		{
			if (!uf.isConnect(u, v)) uf.connect(u, v);
		}
		else if (t == 1)
		{
			if (uf.isConnect(u, v))
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	}
	return 0;
}


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

using namespace std;

const int INF = 1145141919;

string c[305];
int cost[305][305][305], dp[305][305][305];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> c[i];
	}

	for (int i = 0; i < W - 1; i++) {
		for (int j = 0; j <= H; j++) {
			for (int k = 0; k <= H; k++) {
				cost[i][j][k] = cost[i][max(j - 1, 0)][max(k - 1, 0)];
				if (j == 0 || k == 0) continue;
				cost[i][j][k] += (c[j - 1][i] == c[k - 1][i + 1]);
			}
		}
	}

	for (int i = 0; i < W - 1; i++) {
		for (int j = 0; j <= H; j++) {
			for (int k = 0; k <= H; k++) {
				dp[i][j][k] = INF;
			}
		}
	}
	for (int i = 0; i < W - 1; i++) dp[i][H][H] = 0;

	int ans = 0;
	for (int i = 0; i < W - 1; i++) {
		for (int j = H; j >= 0; j--) {
			for (int k = H; k >= 0; k--) {
				if (j > 0) dp[i][j - 1][k] = min(dp[i][j - 1][k], dp[i][j][k] + cost[i][j][k]);
				if (k > 0) dp[i][j][k - 1] = min(dp[i][j][k - 1], dp[i][j][k] + cost[i][j][k]);
			}
		}
		ans += dp[i][0][0];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 221568
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

typedef long long ll;

const int MOD = 1e9+7;

ll dp[60][3];

int main(void) {
    ll n;
    cin >> n;
    int i;
    for (i = 0; 1LL<<i <= n; i++);
    i--;
    dp[i+1][0] = 1;
    for (; i >= 0; i--) {
        if (1LL<<i&n) {
            dp[i][0] = dp[i+1][0];
            dp[i][1] = (dp[i+1][0] + dp[i+1][1]) % MOD;
            dp[i][2] = (3 * dp[i+1][2] + 2 * dp[i+1][1]) % MOD;
        }
        else {
            dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % MOD;
            dp[i][1] = dp[i+1][1];
            dp[i][2] = (3 * dp[i+1][2] + dp[i+1][1]) % MOD;
        }
    }
    int ans = 0;
    REP (i,3) ans = (ans + dp[0][i]) % MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
W, H, N = map(int, input().split())
x_max = 0
x_min = 100
y_max = 0
y_min = 100
for i in range(N):
    x, y, a = map(int, input().split())
    if a == 1:
        if x_max < x:
            x_max = x
    elif a == 2:
        if x_min > x:
            x_min = x
    elif a == 3:
        if y_max < y:
            y_max = y
    elif a == 4:
        if y_min > y:
            y_min = y

if x_max > x_min or y_max > y_min:
    print(0)
else:
    if y_min == 100:
        y_min = H
    if x_min == 100:
        x_min = W
    print((y_min-y_max)*(x_min-x_max))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
main()
{
	int N,M,s=0;
	cin>>N>>M;
	vector <int> A(M);
	for(int i=0;i<M;i++)
	{
		cin>>A[i];
	}
	for(int i=0;i<M;i++)
	{
		N=N-A[i];
	}
	if(N<=0)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main()
{
  int N;
  cin >> N;
  unordered_map<int, bool> D;
  for (int n = 0; n < N; ++n) {
    int d;
    cin >> d;
    D[d] = true;
  }
  cout << D.size() << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)    for(long long i = 0; i < (n) ; ++i)
#define orep(i,n)   for(long long i = 1; i <= (n); ++i)   // one rep
#define drep(i,n)   for(long long i = (n)-1; i >= 0; --i) // down rep
#define srep(i,s,t) for(long long i = (s); i < (t); ++i)  // set rep
#define rng(x)  (x).begin(),(x).end()

  // range
#define rrng(a) (a).rbegin(),(a).rend() // reverse range
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define ru(x,y) (((x)+(y)-1)/(y)) // round up
#define fi first
#define se second
#define eb emplace_back
#define fcout cout << fixed << setprecision(15)


using namespace std;
using ll  = long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vvi = vector<vi>;
using vp  = vector<P>;
using vl  = vector<ll>;

template<typename T> void Yes(T flag) {
  cout << (flag ? "Yes" : "No") << endl;
}

template<typename T> void pv(vector<T> vec) {
  cout << "[";
  for(auto& v : vec) { cout << v << ","; }
  cout << "]" << endl;
}

template<>
void pv(vector<P> vec) {
  cout << "[";
  for(auto& v : vec) {
    cout << "<" << v.fi << ","<< v.se << ">" << ",";
  }
  cout << "]" << endl;
}

template<typename T> void pv2(vector<vector<T>> vec) {
  for(auto& v : vec) pv(v);
}

int main() {
  string s;
  cin >> s;
  int a = s[0] - '0';
  if(17 <= a and a <= 42) cout << "A" << endl;
  else cout << "a" << endl;

  return 0;
}


Measured memory_bytes: 3628
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
public static class P
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        int[] parents = Enumerable.Repeat(-1, n).ToArray();
        int[][] childs = new int[n][];
        for (int i = 0; i < n; i++)
        {
            var data = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var id = data[0];
            childs[id] = data.Skip(2).ToArray();
            foreach (var child in childs[id])
                parents[child] = id;
        }

        int[] depths = new int[n];
        Stack<int> stack = new Stack<int>();
        stack.Push(Array.IndexOf(parents, -1));
        while (0 < stack.Count)
        {
            var elem = stack.Pop();
            foreach (var item in childs[elem])
            {
                depths[item] = depths[elem] + 1;
                stack.Push(item);
            }
        }

        for (int i = 0; i < n; i++)
        {
            Console.WriteLine($"node {i}: parent = {parents[i]}, depth = {depths[i]}, {(parents[i] == -1 ? "root" : childs[i].Length == 0 ? "leaf" : "internal node")}, [{string.Join(", ", childs[i])}]");
        }
    }
}



Measured memory_bytes: 37632
#!/usr/bin/env python

n = int(input())
x_plus_y = [0 for _ in range(n)]
x_minus_y = [0 for _ in range(n)]
for i in range(n):
    x, y = map(int, input().split())
    x_plus_y[i] = x+y 
    x_minus_y[i] = x-y 

ans = max(max(x_plus_y)-min(x_plus_y), max(x_minus_y)-min(x_minus_y))
print(ans)


Measured memory_bytes: 24864
#include<bits/stdc++.h>
#define fr(i,n) for(int i=0;i<(n);++i)
#define foor(i,a,b) for(int i=(a);i<=(b);++i)
#define rf(i,n) for(int i=(n);i--;)
#define roof(i,b,a) for(int i=(b);i>=(a);--i)
#define all(x) x.begin(),x.end()
#define Sort(x) sort(all(x))
#define Reverse(x) reverse(all(x))
#define PQ priority_queue
#define print(x) cout<<(x)<<endl
using namespace std;            typedef vector<int>  vi;
typedef long long ll;           typedef vector< ll>  vl;
typedef unsigned long long ull; typedef vector<ull>  vu;
typedef double dbl;             typedef vector<dbl>  vd;
typedef pair<int,int>pii;       typedef vector<pii>vpii; typedef map<int,int>mii;
typedef pair< ll, ll>pll;       typedef vector<pll>vpll; typedef map< ll, ll>mll;
typedef pair<dbl,dbl>pdd;       typedef vector<pdd>vpdd; typedef map<dbl,dbl>mdd;
typedef pair< ll,int>pli;       typedef vector<pli>vpli; typedef map< ll,int>mli;
typedef pair<dbl,int>pdi;       typedef vector<pdi>vpdi; typedef map<dbl,int>mdi;
template<typename T>vector<T>&operator<<(vector<T>&v,const T t){v.push_back(t);return v;}
template<typename T>multiset<T>&operator<<(multiset<T>&m,const T t){m.insert(t);return m;}
template<typename T>set<T>&operator<<(set<T>&s,const T t){s.insert(t);return s;}
template<typename T,typename U>PQ<T,vector<T>,U>&operator<<(PQ<T,vector<T>,U>&q,const T t){q.push(t);return q;}
template<typename T,typename U>istream&operator>>(istream&s,pair<T,U>&p){return s>>p.first>>p.second;}
template<typename T>istream&operator>>(istream&s,vector<T>&v){fr(i,v.size()){s>>v[i];}return s;}
template<typename T,typename U>ostream&operator<<(ostream&s,const pair<T,U>p){return s<<p.first<<" "<<p.second;}
template<typename T>ostream&operator<<(ostream&s,const vector<T>v){for(auto a:v){s<<a<<endl;}return s;}
const int MD=1e9+7;
vpli dijkstra(const int N,const vpli E[],const int s,const ll inf){vpli d;fr(i,N)d<<pli{inf,i};d[s].first=0;PQ<pli,vpli,greater<pli>>pq;pq<<(d[s]=pli{0,s});while(pq.size()){pli a=pq.top();pq.pop();int v=a.second;if(d[v].first>=a.first){for(pli e:E[v]){if(d[v].first+e.first<d[e.second].first){d[e.second]=pli{d[v].first+e.first,v};pq<<pli{d[v].first+e.first,e.second};}}}}return d;}
ll gcd(const ll a,const ll b){return a?gcd(b%a,a):b;}
ll pow(const ll a,const ll n,const int m){ll t;return n?(n&1?a>=0?a%m:~-m+~a%m:1)*((t=pow(a,n>>1,m))*t%m)%m:1;}
ll C2(const int n){return(ll)n*~-n/2;}

ll F[300001];
ll I[300001];

main(){cin.tie(0);ios::sync_with_stdio(false);
	const ll M=998244353;
	ll N,A,B,K;
	cin>>N>>A>>B>>K;
	F[0]=1;
	foor(i,1,N){
		F[i]=F[i-1]*i%M;
	}
	I[N]=pow(F[N],M-2,M);
	roof(i,N-1,1){
		I[i]=I[i+1]*(i+1)%M;
	}
	I[0]=I[1];
	ll z=0;
	foor(i,0,N){
		ll j=K-A*i;
		if(j%B==0){
			j/=B;
			if(0<=j&&j<=N){
				(z+=F[N]*I[i]%M*I[N-i]%M*F[N]%M*I[j]%M*I[N-j]%M)%=M;
			}
		}
	}
	print(z);
}


Measured memory_bytes: 4992
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = "North:South:East:West:Right:Left".split(":");
        int[][] l = { { 0, 1, 1, 2, 2, 3 }, { 3, 2, 2, 1, 1, 0 }, { 0, 5, 2, 4, 4, 5 }, { 0, 4, 2, 5, 5, 4 }, { 1, 4, 3, 5, 4, 5 }, { 1, 5, 3, 4, 4, 5 } };
        Map<String, int[]> m = new HashMap<>();
        for (int i = 0; i < 6; i++) {
            m.put(s[i], l[i]);
        }
        for (;;) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            int sum = 1;
            int[] d = { 1, 2, 6, 5, 3, 4 };
            while (n-- > 0) {
                int[] t = m.get(sc.next());
                for (int i = 0; i < t.length; i += 2) {
                    int p = d[t[i]];
                    d[t[i]] = d[t[i + 1]];
                    d[t[i + 1]] = p;
                }
                sum += d[0];
            }
            System.out.println(sum);
        }

    }
}



Measured memory_bytes: 34324
#include <bits/stdc++.h>
#include <string.h>  
#include <iostream>  
#include <map>  
#include <utility>  
using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;
    string s;
    for(int i = 0; i < w+2; i++)
    cout << "#";
    cout << "\n";
    for(int i = 0; i < h; i++)
    {
        cin >> s;
        cout << "#";
        cout << s;
        cout << "#\n";

    }
   
    for(int i = 0; i < w+2; i++)
    cout << "#";
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;

ll gcd (ll a, ll b) {
    if (b > a) {
        ll tmp = b;
        b = a;
        a = tmp;
    }
    if (b == 0) return a;
    return gcd(b, a % b);
}

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


int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    ll tmp = 1;
    for(int i = 0; i < N; i++) {
        cin >> a.at(i);
        //tmp = lcm(tmp, a.at(i));
    }

    //tmp--;
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        //ans += tmp % a.at(i);
        ans += a.at(i) - 1;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
s = input()
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        print(i+1,i+2)
        exit()
for i in range(len(s)-2):
    if s[i]==s[i+2]:
        print(i+1,i+3)
        exit()
print(-1,-1)


Measured memory_bytes: 3188
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll H, W;
  cin >> H >> W;
  vector<string> M(H);
  for (int i = 0; i < H; i++) {
    cin >> M[i];
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (M[i][j] == '#') {
        if ((i + 1 < H && M[i + 1][j] == '#') ||
            (0 <= i - 1 && M[i - 1][j] == '#') ||
            (j + 1 < H && M[i][j + 1] == '#') ||
            (0 <= j - 1 && M[i][j - 1] == '#'))
          continue;
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <deque>
#include <vector>

bool floodStep(std::vector<bool> &vis, std::deque<int> &q, std::deque<int> &q2,
std::vector<std::vector<int> > &al) {
    while (!q.empty()) {
        int it = q.front();
        q.pop_front();
        if (vis[it])
            continue;
        vis[it] = true;
        for (int i = 0; i < al[it].size(); ++i)
            q2.push_back(al[it][i]);
        return true;
    }
    return false;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<bool> vps(N, false);
    std::vector<bool> vls(M, false);
    std::vector<std::vector<int> > alp(N);
    std::vector<std::vector<int> > all(M);
    for (int i = 0; i < N; ++i) {
        int K;
        std::cin >> K;
        for (int x = 0; x < K; ++x) {
            int L;
            std::cin >> L;
            alp[i].push_back(L-1);
            all[L-1].push_back(i);
        }
    }

    std::deque<int> people;
    std::deque<int> langs;
    people.push_back(0);
    while (floodStep(vps, people, langs, alp)
    ||     floodStep(vls, langs, people, all))
        continue;

    int ret = 1;
    for (int i = 0; i < N; ++i)
        ret = ret && vps[i];

    std::cout << (ret ? "YES\n" : "NO\n");

    return 0;
}


Measured memory_bytes: 9080
def run(s, t):
    sc = {}
    tc = {}
    for i in 'abcdefghijklmnopqrstuvwxyz':
        sc[i] = 0
        tc[i] = 0
    counter = 1
    for ss in s:
        if sc[ss] == 0:
            sc[ss] = counter
            counter += 1
    counter = 1
    for tt in t:
        if tc[tt] == 0:
            tc[tt] = counter
            counter += 1
    slist = [sc[ss] for ss in s]
    tlist = [tc[tt] for tt in t]
    if slist == tlist:
        return 'Yes'
    else:
        return 'No'
    '''
    ss = sorted(list(collections.Counter(s).values()))
    tt = sorted(list(collections.Counter(t).values()))
    if ss == tt:
        return 'Yes'
    else:
        return 'No'
    '''


def main():
    s = input()
    t = input()
    print(run(s, t))


if __name__ == '__main__':
    main()


Measured memory_bytes: 6832
#include<stdio.h>

int main(void)
{
	int year,month,day;
	char gengou[5][30]={
		"pre-meiji",
		"meiji",
		"taisho",
		"showa",
		"heisei"
	};
	long start[5]={
		0,
		18680908,
		19120730,
		19261225,
		19890108
	};
	long input;
	while(1){
		//input
		if(scanf("%d %d %d",&year,&month,&day)==EOF) return 0;
		//solve
		//solve_gengou
		input = year*100*100+month*100+day;
		int gengou_ans=4;
		for(int i=1;i<5;i++){
			if(input<start[i]){
				gengou_ans=i-1;
				break;
			}
		}
		//solve_year
		year = year-start[gengou_ans]/10000+1;
		//output
		if(gengou_ans==0){
			printf("pre-meiji\n");
		}else{
			printf("%s %d %d %d\n",gengou[gengou_ans],year,month,day);
		}
	}
	return 0;
}

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


int main(){
    int A,B,ans=0;
    cin >> A >> B;
    for (int i=0;i<2;++i){
    if(A>=B){
        ans += A;
        --A;
    }
    else{
        ans += B;
        --B;
    }
    }
    cout << ans << endl;
}




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
using namespace std;

#define rep(i,end)          rep2(i,0,(end))
#define rep2(i,beg,end)   for (int i=(beg);i<(end);i++)
#define all(cont)           begin(cont), end(cont)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
typedef pair<ll, string> pis;
typedef pair<string, ll> psi;

string gets(bool skipnewline);


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string line = gets(false);
    line[5] = line[13] = ' ';
    cout << line << endl;
    return 0;
}

string gets(bool skipToNextline)
{
    if (skipToNextline) gets(false);
    const int LINE_MAX = 1024;
    char buf[LINE_MAX];
    cin.getline(buf, sizeof(buf));
    return buf;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>

#define X first
#define Y second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())


//INT_MAX
//INT_MIN
//LLONG_MAX
//LLONG_MIN
//DBL_MIN
//DBL_MAX
//LDBL_MIN
//LDBL_MAX

using namespace std;
using ll = long long;

ll gcd(ll x, ll y);

int main(int argc, const char * argv[]) {
    ll n, x, a, ans = -1;
    cin >> n >> x;
    ll now;
    for (ll i = 0; i < n; i++) {
        cin >> a;
        now = abs(x - a);
        if (i == 0) {
            ans = now;
        }else{
            ans = gcd(ans, now);
        }
    }
    cout << ans << endl;
    
}

// 最大公約数
ll gcd(ll x, ll y){
    ll r;
    
    // 引数チェック
    if(x == 0 || y == 0){
        return 0;
    }
    
    // ユーグリッドの互除法
    // yで割り切れるまでループ
    while((r = x % y) != 0){
        x = y;
        y = r;
    }
    return y;
}


Measured memory_bytes: 256
function Main(input) {
	input = input.split("\n");
	var a = input[0].split(" ");
	var b = input[1].split(" ");
	var c = input[2].split(" ");
	var arr = [a,b,c]
	input.shift();
	input.shift();
	input.shift();
	input.shift();
	for(var i=0;i<input.length;i++){
		for(var n=0;n<3;n++){
			for(var m=0;m<3;m++){
				if(arr[n][m]==input[i]){
					arr[n][m] = "#";
					break;
				}
			}
		}
	}

	var flag = false;
	if(arr[0][0]=="#"){
		if(arr[0][1]=="#"&&arr[0][2]=="#"){
			flag = true;
		}else if(arr[1][0]=="#"&&arr[2][0]=="#"){
			flag = true;
		}else if(arr[1][1]=="#"&&arr[2][2]=="#"){
			flag = true;
		}
	}
	if(arr[0][1]=="#"){
		if(arr[1][1]=="#"&&arr[2][1]=="#"){
			flag = true;
		}
	}
	if(arr[0][2]=="#"){
		if(arr[1][2]=="#"&&arr[2][2]=="#"){
			flag = true;
		}else if(arr[1][1]=="#"&&arr[2][0]=="#"){
			flag = true;
		}
	}
	if(arr[1][0]=="#"&&arr[1][1]=="#"&&arr[1][2]=="#"){
		flag = true;
	}
	if(arr[2][0]=="#"&&arr[2][1]=="#"&&arr[2][2]=="#"){
		flag = true;
	}
	if(flag){
		console.log("Yes")
	}else{
		console.log("No")
	}
}Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

Measured memory_bytes: 21064
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    n = int(input())
    to = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]

    for i in range(n - 1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        to[ui].append(vi)
        to[vi].append(ui)
        cost[ui].append(wi)
        cost[vi].append(wi)

    ans = [-1 for _ in range(n)]
    q = deque()
    ans[0] = 0
    q.append(0)

    while q:
        vj = q.popleft()

        for j in range(len(to[vj])):
            uj = to[vj][j]
            wj = cost[vj][j]

            if ans[uj] != -1:
                continue

            ans[uj] = (ans[vj] + wj) % 2
            q.append(uj)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38292
s=int(input())
a=[0]*1000000
a[s-1]+=1
i=1
while True:
  i+=1
  if s%2==0:
    s=s//2
  else:
    s=3*s+1
  a[s-1]+=1
  if a[s-1]==2:
    print(i)
    break


Measured memory_bytes: 16444
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define all(A) A.begin(),A.end()
typedef long long ll;

int main(){
  int x;
  cin >> x;
  rep(i,1000){
    if(100*i<=x && x<=105*i){
      cout << 1 << endl;
      return 0;
    }
  }
  cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 3572
#include <iostream>

using namespace std;

int main()
{
    int a,b,c,t;
    cin >> a >> b >> c;
    t = a;
    a = b;
    b = t;
    t = a;
    a = c;
    c = t;
    cout << a << ' ' << b << ' ' << c;
    return 0;
}

Measured memory_bytes: 256
word = input()
count = 0
s1 = word[:len(word)//2]
s2 = word[len(word)//2:]
if s1 == reversed(s2):
    print(count)
else:
    for i in range(len(s1)):
        if s1[i] != s2[len(s2)-i-1]:
            count = count + 1
    print(count)

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
const int inf=1<<30;
int main(){
  int a,b,ans;cin>>a>>b;
  ans=a-1;
  if(a<=b)ans++;
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

struct data {
	llong from;
	llong to;
	llong cost;

	data() {};
	data(llong from, llong to, llong cost) :
		from(from),
		to(to),
		cost(cost)
	{}
};

llong N, M, P;
vector<data> all_edge;
vector<vector<llong> > edges;
vector<llong> can_go;

void check_can_go() {
	queue<llong> que;
	can_go.resize(N+1, 0);

	que.push(1);
	can_go[1] = 1;
	while (que.size()) {
		llong now = que.front();
		que.pop();

		for (auto to : edges[now]) {
			if (can_go[to] == 1) continue;
			can_go[to] = 1;
			que.push(to);
		}
	}

	return;
}

pair<set<llong>, llong> bellman_ford() {
	vector<llong> distance(N+1, inf);
	set<llong> ret;
	distance[1] = 0;
	for (int i = 0; i < 2 * N; ++i) {
		for (auto edge : all_edge) {
			if (distance[edge.to] > distance[edge.from] + edge.cost) {
				distance[edge.to] = distance[edge.from] + edge.cost;
				if (i >= N && can_go[edge.to]) {
					ret.insert(edge.to);
				}
			}
		}
	}

	return {ret, -min(0ll, distance[N])};
}

bool including_minus_roop(set<llong> s) {
	queue<llong> que;
	vector<llong> checked(N+1, 0);

	while (s.size()) {
		que.push(*s.begin());
		checked[*s.begin()] = 1;
		s.erase(s.begin());
	}

	while (que.size()) {
		llong now = que.front();
		que.pop();

		for (auto to : edges[now]) {
			if (checked[to] == 1) continue;
			checked[to] = 1;
			que.push(to);
		}
	}

	return checked[N];
}

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

	edges.resize(N+1);
	llong from, to, cost;
	for (int i = 0; i < M; ++i) {
		cin >> from >> to >> cost;
		all_edge.push_back(data(from, to, -cost + P));
		edges[from].push_back(to);
	}

	check_can_go();

	auto ans = bellman_ford();

	cerr << ans.first.size() << endl;
	if (including_minus_roop(ans.first)) {
		cout << -1 << endl;
	} else {
		cout << ans.second << endl;
	}

	return 0;
}

Measured memory_bytes: 896