akhauriyash/Code-Regression huggingface dataset:
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

int N, M;

ll X[1010], Y[1010], Z[1010];

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i] >> Z[i];
    }

    ll ans = 0;
    for (int n = 0; n < (1 << 3); ++n) {
        int s[3];
        for (int i = 0; i < 3; ++i) {
            s[i] = (n & (1 << i)) != 0 ? 1 : -1;
        }

        vector<pair<ll, int>> gains;

        for (int i = 0; i < N; ++i) {
            ll gain = 0;
            gain += s[0] * X[i];
            gain += s[1] * Y[i];
            gain += s[2] * Z[i];

            gains.push_back(make_pair(gain, i));
        }
        sort(begin(gains), end(gains));
        reverse(begin(gains), end(gains));

        ll acc[3] = {0, 0, 0};
        for (int i = 0; i < M; ++i) {
            int idx = gains[i].second;
            acc[0] += X[idx];
            acc[1] += Y[idx];
            acc[2] += Z[idx];
        }

        ans = max(ans, abs(acc[0]) + abs(acc[1]) + abs(acc[2]));
    }

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


Measured memory_bytes: 256
program main
    implicit none
    integer*8::a,b,c,x,y,ans=1000000000,i
    read(*,*)a,b,c,x,y
    do i=0,max(x,y)
        ans=min(ans,c*2*i+a*max(0,x-i)+b*max(0,y-i))
    end do
    print*,ans
end program


Measured memory_bytes: 768
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cassert>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
#include <forward_list>
#include <array>
#include <cstring>
#include <cmath>
#include <tuple>
#include <complex>
#include <bitset>
#include <climits>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pld = pair<LD, LD>;


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

    int N;
    cin >> N;

    vector<int> nr_subords(N + 1);
    for (int i = 2; i <= N; ++i)
    {
        int A;
        cin >> A;

        ++nr_subords[A];
    }

    for (int i = 1; i <= N; ++i)
    {
        cout << nr_subords[i] << "\n";
    }
}


Measured memory_bytes: 3980
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main() {
 
  int N; cin >> N;
  int M; cin >> M;
  
  vector<pair<int,int>> v(M);
  for(int i = 0; i < M; i++){
    cin >> v.at(i).first;
    cin >> v.at(i).second;
  }
  
  //矛盾した条件はないか？
  bool mujun = 0;
  for(int i = 0; i < M-1; i++){
    for(int j = i+1; j < M; j++){
      if(v.at(i).first == v.at(j).first
        && v.at(i).second != v.at(j).second){
        mujun = 1;
        break;
      }
    }
  }
  
  //先頭の数字が0と指定されてないか？
  bool top0 = 0;
  for(int i = 0; i < M; i++){
    if(v.at(i).first == 1 && v.at(i).second == 0 && N > 1){
      top0 = 1;
      break;
    }
  }
  
  //上記2条件をクリアしてれば構成する
  if(!mujun && !top0){
    string T = "";
    for(int i = 0; i < N; i++){
      T += '0';
    }

    for(int i = 0; i < M; i++){
      T.replace(v.at(i).first -1,1,to_string(v.at(i).second));
    }
    
    if(T.at(0) == '0' && N > 1){
      T.replace(0,1,"1");
      cout << stoi(T) << endl;
    }
    else if(T.at(0) == '0' && N == 1){
      cout << 0 << endl;
    }else{
      cout << stoi(T) << endl;
    }
  }else{
    cout << -1 << endl;
  }

}

Measured memory_bytes: 256
N = int(input())

c = 10**100

for a in range(2, int(N**0.5)+1):
    if N % a == 0:
        b = N / a
        if (a-1)+(b-1) < c:
            c = (a-1)+(b-1)
        
print(min((N-1), int(c)))

Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
int main(){
  char s[100000];
  int count=0,i,j;
  scanf("%s",s);
  for(i=0;i<strlen(s)-1;i++){
    if(s[i]!=s[i+1]){
      count++;
    }
  }
  printf("%d\n",count);
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> ds(N);
  rep(i, N) cin >> ds.at(i);
  
  sort(ds.begin(), ds.end());
  
  int ans = 0;
  // 1 <= d_i <= 100
  int old = -1;
  for (int d : ds) {
    if (d != old)
      ans++;
    old = d;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int ans = 0;
        ans+=(x/500)*1000;
        x%=500;
        ans+=(x/5)*5;
        System.out.println(ans);
    }
    static long factorial(long num){
        if (num<2)return 1;
        else return num*factorial(num-1);
    }
    static int arraySum(int[] array){
        int ans = 0;
        for (int value : array) ans += value;
        return ans;
    }
    static long combination(long a, long b){
        long data = 1;
        for (int i=0;i<b;i++){
            data*=a-i;
        }
        return data/factorial(b);
    }
    static double log(double base,double antilogarithm){
        return Math.log(antilogarithm)/Math.log(base);
    }

    static long gcd(long x,long y){
        if (y==0)return x;
        else return gcd(y,x%y);
    }
    static long lcm(long x,long y){
        return x/gcd(x,y)*y;
    }

}


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

struct UnionFind{
    vector<int> d;
    UnionFind(int n=0):d(n,-1){}
    int root(int x){
        if(d[x]<0)return x;
        return d[x]=root(d[x]);
    }
    bool unite(int x,int y){
        x=root(x);y=root(y);
        if(x==y)return false;
        if(d[x]>d[y])swap(x,y);
        d[x]+=d[y];
        d[y]=x;
        return true;
    }
    bool same(int x,int y){return root(x)==root(y);}
    int usize(int x){return -d[root(x)];}
};

int main(){
    ll n,m;cin >>n>>m;
    vector<ll>a(m);
    vector<ll>b(m);
    for (int i = 0; i < m; ++i) {
        cin >>a[i]>>b[i];
        a[i]--;b[i]--;
    }
    reverse(all(a));
    reverse(all(b));
    UnionFind uni(n);
    vector<ll>ans;
    ll U=n*(n-1)/2;
    for (int i = 0; i < m; ++i) {
        ans.push_back(U);
        if(!uni.same(a[i],b[i])) {
            U -= uni.usize(a[i]) * uni.usize(b[i]);
            uni.unite(a[i], b[i]);
        }
    }
    reverse(all(ans));
    for (int i = 0; i < m; ++i) {
        cout <<ans[i]<<endl;
    }
    return 0;
}


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

int F[45];

int fib(int n){
  if (F[n]) return F[n];
  if (n==0||n==1) F[n]=1;
  else F[n]=fib(n-1)+fib(n-2);
  return F[n];
}

int main(){
  int n;
  cin >>n;
  cout << fib(n)<<endl;
  return 0;
}

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <cmath>
#include <bitset>
#define REP(i,n) for(int i=0;i<n;i++)
using Int = long long;
using namespace std;
const int MOD = 1000000007;
int main()
{
    int N; cin >> N;
    Int power = 1;
    for (int i = 1; i <= N; i++) {
        power = (power * i) % MOD;
    }
    cout << power << endl;
    return 0;
}

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

import sys

def merge(A, left, mid, right):
    n1 = mid-left
    n2 = right-mid
    L = [0]*(n1+1)
    R = [0]*(n2+1)
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = R[n2] = sys.maxint
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left+right)/2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

A = map(int, raw_input().split())
mergeSort(A, 0, 5)
print " ".join(map(str, A[::-1]))

Measured memory_bytes: 6424
//include
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

// conversion
inline int
toInt(string s)
{
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}
template <class T>
inline string toString(T x)
{
    ostringstream sout;
    sout << x;
    return sout.str();
}

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

//math
template <class T>
inline T sqr(T x) { return x * x; }

template <class T>
inline T nCr(T n, T r)
{
    T num = 1;
    for (int i = 1; i <= r; ++i)
    {
        num *= (n - i + 1) / i;
    }
    return num;
}
template <class T>
inline T nPr(T n, T r)
{
    r = n - r;
    T sum = 1;
    int i;
    for (i = n; i >= r + 1; --i)
        sum *= i;
    return sum;
}

template <class T>
inline T facctorial(T k)
{
    T sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

//numeric
template <class T>
inline T gcd(T a, T b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

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

template <class T>
inline T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())

//repetition
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
constexpr double EPS = 1e-10;
const double PI = acos(-1.0);
constexpr LL INF = 1e10;

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

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

int main()
{
    string s;
    cin >> s;
    int n = s.length();
    for (int i = 0; i < n; ++i)
    {
        if (i % 2 != 0)
        {
            if (s[i] == 'R')
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else
        {
            if (s[i] == 'L')
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string str;
  while(cin>>str){
    bool flg=true;
    for(int i=0;i+1<(int)str.size();i++){
      char f=str[i];
      char s=str[i+1];
      if(f>s)swap(f,s);
      if(f=='A'){
        if(s!='B'&&s!='D')flg=false;
      }
      if(f=='B'){
        if(s!='C'&&s!='E')flg=false;
      }
      if(f=='C'){
        if(s!='F')flg=false;
      }
      if(f=='D'){
        if(s!='E'&&s!='G')flg=false;
      }
      if(f=='E'){
        if(s!='F'&&s!='H')flg=false;
      }
      if(f=='F'){
        if(s!='I')flg=false;
      }
      if(f=='G'){
        if(s!='H')flg=false;
      }
      if(f=='H'){
        if(s!='I')flg=false;
      }
      if(f=='I')flg=false;

    }
    if(flg)cout<<str<<endl;
  }
  return 0;
}

Measured memory_bytes: 1172
n = int(input())
a = list(map(int, input().split()))


flag = 1
i = 0
count = 0

while flag:
    flag = 0
    for j in reversed(range(i+1, n)):
        if a[j] < a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
            flag = 1
            count += 1
    i += 1
for k in range(len(a)):
    if k == n - 1:
        print(a[k])
    else:
        print(a[k], end=' ')
print(count)



Measured memory_bytes: 5608
#include<bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
    int A,B,C;
    cin >> A >> B >> C;
    if (A == 5 || A == 7) {
        if (B == 5 || B == 7) {
            if (C == 5 || C == 7) {
                if (A+B+C==5+7+5) {
                    cout << "YES" << endl;
                }else{
                    cout << "NO" << endl;

                }

            } else {
                cout << "NO" << endl;

            }

        } else {
            cout << "NO" << endl;

        }
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;


struct edge{int to; long long int cap; int rev;};

class Edmonds_Karp{
    int source;
    int sink;
    int v;
    long long int maxflow = 10000000000;
    std::vector<std::vector<edge>> g;
    std::vector<std::pair<int,int>> back_v;
    std::vector<bool> used;
    std::stack<std::pair<int,int>> minimum_route;

    bool BFS(){
        std::queue<int> que;

        que.push(source);

        while(!que.empty()){
            int t = que.front();
            que.pop();

            if(t == sink)return true;

            if(used[t])continue;

            used[t] = true;

            for(int i = 0; i < g[t].size(); i++){
                if(!used[g[t][i].to] && g[t][i].cap > 0){
                    que.push(g[t][i].to);
                    back_v[g[t][i].to] = std::make_pair(t,i);
                }
            }
        }

        return false;
    }

    void backtrack(){
        minimum_route.push(back_v[sink]);
        std::pair<int,int> t = back_v[sink];
        while(t.second >= 0){
            minimum_route.push(t);
            t = back_v[t.first];
        }
    }

    long long int DFS(int s,long long int f){
        if(s == sink) return f;

        std::pair<int,int> t = minimum_route.top();
        minimum_route.pop();

        edge &e = g[s][t.second];
        
        int ret = DFS(e.to,std::min(f,e.cap));
        if(ret < 0) return ret;

        e.cap -= ret;
        g[e.to][e.rev].cap += ret;

        return ret;
    }
    
    public:
    Edmonds_Karp(int s,int t,int n):source(s),sink(t),v(n){
        g = std::vector<std::vector<edge>>(v+1);
        back_v = std::vector<std::pair<int,int>>(v+1,std::make_pair(-1,-1));
        used = std::vector<bool>(v+1,false);
    }

    void add_edge(int f,int t,long long int c){
        g[f].push_back(edge{t,c,(int)g[t].size()});
        g[t].push_back(edge{f,0,(int)g[f].size()-1});
    }

    long long int solve(){
        long long int ans = 0;

        while(BFS()){
            backtrack();
            ans += DFS(source,maxflow);
            fill(used.begin(),used.end(),false);
            fill(back_v.begin(),back_v.end(),std::make_pair(-1,-1));
        }

        return ans;
    }
};


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

    LL v,e;
    cin >> v >> e;

    Edmonds_Karp ek = Edmonds_Karp(0,v-1,v);

    for(int i = 0; i < e; i++){
        LL a,b,c;
        cin >> a >> b >> c;
        ek.add_edge(a,b,c);
    }

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


Measured memory_bytes: 3236
n = int(input())
h = list(map(int, input().split()))

ind = 0
prev = h[0] - 1
no = False

for i in range(1, n):
  if prev < h[i]:
    prev = h[i] - 1
  elif prev == h[i]:
    prev = h[i]
  else:
    print('No')
    no = True
    break

if not no:
  print('Yes')

Measured memory_bytes: 63856
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <bitset>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b){
  if(a<b) swap(a, b);
  ll r = -1;
  while(r!=0){
    r = a % b,a = b,b = r;
  }
  return a;
}
int main(int argc, char const *argv[]) {
  ll N, K, flag=1;
  std::cin >> N >> K;
  std::vector<int> A(N);
  range(i, N) {
    std::cin >> A[i];
    if(A[i]%2==1) flag = 0;
  }
  sort(A.begin(), A.end());
  if(A[N-1] < K) std::cout << "IMPOSSIBLE" << '\n';
  else {
    ll gc = A[0];
    range(i, N) gc = gcd(gc, A[i]);
    std::cout << (K%gc==0?"POSSIBLE":"IMPOSSIBLE") << '\n';
  }
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    int ans=1;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 1; i < n; i++)
    {
        if(a[i]!=a[i-1]) ans++;
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  int n;
  cin >> n;
  cout << n / 3 << endl;
  return 0;
}


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

using namespace std;

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

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

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

vector<vector<int> > g;
vector<vector<P> > edge; //vertex,cost
vector<int> dist,used;
bool flag;

void dfs(int x){
	if(used[x]) return;
	used[x]++;
	for(auto p : edge[x]){
		int to = p.first;
		int cost = p.second;
		if(!used[to]){
			dist[to] = dist[x] + cost;
			dfs(to);
		}else if(dist[to] - dist[x] != cost){
			flag = false;
			return;
		}
	}
}

int main()
{
	int n,m;
	cin>>n>>m;
	g.resize(n,vector<int>());
	edge.resize(n,vector<P>());
	dist.resize(n,-1);
	used.resize(n,0);
	flag=true;
	for (int i = 0; i < m; i++)
	{
		int l,r,d;
		cin>>l>>r>>d;
		l--;
		r--;
		g[l].push_back(r);
		g[r].push_back(l);
		edge[l].push_back(P(r,d));
		edge[r].push_back(P(l,-d));
	}
	for (int i = 0; i < n; i++){
		if(!flag)break;
		if(dist[i] < 0){
			dist[i] = 0;
			dfs(i);
		}
	}
	cout<<(flag?"Yes":"No")<<endl;


	return 0;
}

Measured memory_bytes: 17920
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n ,w;
    cin >> n >> w;
    vector<pair<long ,long>>c;
    for(int i=0;i<n;i++){
        long a,b;
        cin >> a >> b;
        c.push_back(make_pair(a,b));
    }
   // sort(c.begin(),c.end());
    long long dp[w+1][n+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=w;i++){
        for(int j=0;j<n;j++){
            if(i >= c[j].first){
                dp[i][j+1] = max(dp[i][j], dp[i - c[j].first][j] + c[j].second) ;
            }
            else
            {
                dp[i][j+1] = dp[i][j];
            }
            
        }
    }
    cout<<dp[w][n]<<endl;
}

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

using namespace std;

int main(){
    int a;
    cin >> a;
    string re;
    re = to_string(a);
    for(int i = 0; i < 3; ++i){
        if(re[i] == re[i + 1]){
            cout << "Bad";
            return 0;
        }
    }
    cout << "Good";

    return 0;
}

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

int main(){
    ll N; cin >> N;
    ll ans=0;
    ans=N*(N-1)/2;
    cout << ans;
}

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

int main(){

    double N, X;
    const double TAXRATE = 1.08;

    cin >> N;

    X = ceil( N / TAXRATE );

    if ( floor(X*1.08) == N ){
        cout << (int)X << endl;
    }else{
        cout << ":(" << endl;
    } 
    

    return 0;
}

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

int main() {
  int x; cin >> x;
  
  int r = 1;
  for(int b=2;b<sqrt(x)+1;b++){
    for(int p=2;p<x;p++){
      int temp = pow(b,p);
      if(temp<x+1){
        r = max(temp,r);
      } else{
        break;
      }
    }    
  }
  cout << r << endl;
  
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
using ll = int64_t;
#define rep(i, j, n) for (int i = j; i < (int)n; ++i)
#define rrep(i, j, n) for (int i = (int)n - 1; j <= i; --i)

int cnt[1000010];

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int& x : a) cin >> x;

  // pairwise coprimeは左からgcdやればよい。
  int g = 0;
  rep(i, 0, n) g = gcd(g, a[i]);

  if (g != 1) {
    cout << "not coprime" << endl;
    return 0;
  }
  // pairwise coprime 普通にやるO(N^2 * logN)
  // 何かを素因数分解していって
  // aiとajが互いに素とは？ 共通の素因数を持たない。

  rep(i, 0, n) {
    int x = a[i];
    int j = 2;
    while (j * j <= x) {
      if (x % j == 0) {
        if (cnt[j] != 0) {
          cout << "setwise coprime" << endl;
          return 0;
        }
        while (x % j == 0) ++cnt[j], x /= j;
      }
      ++j;
    }
    if (x != 1) {
      if (cnt[x] != 0) {
        cout << "setwise coprime" << endl;
        return 0;
      }
      ++cnt[x];
    }
  }
  cout << "pairwise coprime" << endl;
  return 0;
}

Measured memory_bytes: 7576
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define LL long long
#define N 5011 
int n,a,b;
LL ans,f[N][N][2],p[N][2],g[N],t0,t1;
typedef struct{
	int to,nxt;
}edge;
edge e[N<<1];
int head[N<<1],cnt,siz[N];
void add(int a,int b){
	cnt++;
	e[cnt].to=b;
	e[cnt].nxt=head[a];
	head[a]=cnt;
}
void dfs(int u,int fa){
	f[u][1][0]=1;siz[u]=1;
	for(int i=head[u];i!=-1;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		memset(p,0,sizeof(p));
		for(int j=1;j<=siz[u];j++)
		  for(int k=1;k<=siz[v];k++){
		  	t0=(f[u][j][0]*f[v][k][0]%MOD+f[u][j][1]*f[v][k][1]%MOD)%MOD;
		  	t1=(f[u][j][0]*f[v][k][1]%MOD+f[u][j][1]*f[v][k][0]%MOD)%MOD;
		  	p[j+k][0]=(p[j+k][0]+t0)%MOD;
		  	p[j+k][1]=(p[j+k][1]+t1)%MOD;
		  	p[j][0]=(p[j][0]+t1*g[k]%MOD)%MOD;
		  	p[j][1]=(p[j][1]+t0*g[k]%MOD)%MOD;
		  }
		memcpy(f[u],p,sizeof(p));
		siz[u]+=siz[v];
	}
}
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		scanf("%d%d",&a,&b);
		add(a,b);add(b,a);
	}
	g[0]=1;
	for(int i=2;i<=n;i+=2)
	  g[i]=g[i-2]*(i-1)%MOD;
	dfs(1,0);
	ans=0;
	for(int i=1;i<=n;i++)
	  ans=(ans+(f[1][i][0]-f[1][i][1])%MOD*g[i]%MOD)%MOD;
	if(ans<0) ans+=MOD;
	printf("%lld\n",ans%MOD);
}

Measured memory_bytes: 392576
// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <set>
#include <queue>
#include <cstdio>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define irep(i, n) for(int i=n-1;i>=0;i--)
#define lrep(i, n) for(long long i=0;i<n;i++)
typedef long long ll;
typedef vector<long long> llv;
typedef vector<vector<long long> > llvv;

int N = 100;

int main(){
    int n, p[N+1], m[N+1][N+1];
    cin >> n;
    for (int i=1 ;i<=n;i++){
        cin >> p[i-1] >> p[i];
    }
    for (int i=1;i<N;i++) m[i][i] = 0;
    for (int l=2;l<=n;l++){
        for (int i=1;i<=n-l+1;i++){
            int j = i + l - 1;
            m[i][j] = (1 << 21);
            for (int k=i;k<=j-1;k++){
                m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);
            }
        }
    }
    cout << m[1][n] << endl;
}


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

int main(){
    int N, ans = 0;
    bool pre = false;
    cin >> N;
    for(int i = 0;i<N;i++){
        int in;
        cin >> in;
        if(in == i + 1){
            if(pre) {
                pre = false;
                continue;
            }
            ans++;
            pre = true;
            continue;
        }
        if(pre) pre = false;
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 256
N, K = map(int, raw_input().split())
W = [i for i in xrange(N)]
D = [i for i in xrange(N)]
for i in xrange(N):
    W[i], D[i] = map(int, raw_input().split())

hi = 10**20
lo = 0

while hi - lo > 1:
    mid = (hi + lo) / 2
    cnt = 0
    for i in xrange(N):
        if mid >= W[i]:
            cnt += (mid-W[i])/D[i]+1
    if cnt >= K:
        hi = mid
    else:
        lo = mid
print hi

Measured memory_bytes: 35560
#include <cstdio>
#include <math.h>

int Q;
unsigned int bit;
char ch[9];
double ans;

unsigned cnv(char c){
	if(c >= '0' && c <= '9'){
		return c - '0';
	}
	else{
		return (c - 'a') + 10;
	}
}

int main(){
	scanf("%d",&Q);
	for(int I = 0; I < Q; I++){
		scanf("%s",ch);
		bit = 0;
		ans = 0;
		for(int i = 0; i < 8; i++){
			unsigned k = cnv(ch[i]);
			bit |= (k << (4*(7-i)));
		}
		for(int i = 0; i < 31; i++){
			if(bit & (1<<i)){
				ans += pow(2,i-7);
			}
		}
		if(bit & (1<<31)){
			printf("-");
		}
		if(bit & ((1<<7)-1)){
			char msg[8] = "%.1f\n";
			for(int i = 0; i < 7; i++){
				if(bit & (1<<i)){
					msg[2] = '0' + (7-i);
					printf(msg,ans);
					break;
				}
			}

		}
		else{
			printf("%.1f\n",ans);
		}
	}
	return 0;
}

Measured memory_bytes: 2856
#include <iostream>
#include <queue>

using namespace std;

int main() {
  std::ios::sync_with_stdio(false);

  int N;
  cin >> N;

  priority_queue<int> Q;
  for (int i = 0; i < 2 * N; ++i) {
    int l;
    cin >> l;
    Q.push(l);
  }

  int ans = 0;
  while (!Q.empty()) {
    int l1 = Q.top();
    Q.pop();

    if (Q.empty()) break;
    int l2 = Q.top();
    Q.pop();

    ans += l2;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
/*input
6
30 10 60 10 60 50
*/

//sometimes it's the people who no one imagines anything of 
//who do the things that no one can imagine.

//code author: iamxlr8

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

#define ll long long
#define N 300005
#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main() 
{
    off;
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
        cin>>a[i];
    ll dp[n];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(ll i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n-1];
    return 0;
}

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

int main() {
  int H1, M1, H2, M2, K;
  cin >> H1 >> M1 >> H2 >> M2 >> K;
  int L = H2*60 + M2 - H1*60 - M1;
  cout << L - K << endl;
}

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

int num;
int N=1e5+4;
vector<int>size(N);
vector<int>comp(N,-1);
vector<vector<int>>g(N);
int dfs(int u)
{
    if(comp[u]!=-1)
    return 0;
    
    comp[u]=num;
    int res=1;
    for(int i=0;i<g[u].size();i++)
    res+=dfs(g[u][i]);
    
    return res;
    
}
int main() {
	// your code goes here
	int n,m,k;
	cin>>n>>m>>k;
	g.resize(n);
	for(int i=0;i<m;i++)
	{
	    int a,b;
	    cin>>a>>b;
	    a--;
	    b--;
	    g[a].push_back(b);
	    g[b].push_back(a);
	    
	}
	
	size.resize(n);
	comp.resize(n,-1);
	num=0;
	for(int i=0;i<n;i++)
	{
	    if(comp[i]!=-1)
	    continue;
	    
	    size[num]=dfs(i);
	    num++;
	    
	}
	vector<int>ans(n,0);
	for(int i=0;i<n;i++)
	{
	    ans[i]=size[comp[i]]-g[i].size()-1;
	}
	for(int i=0;i<k;i++)
	{
	    int c,d;
	    cin>>c>>d;
	    c--;
	    d--;
	    if(comp[c]==comp[d])
	    {
	        ans[c]--;
	        ans[d]--;
	    }
	}
	for(int i=0;i<n;i++)
	cout<<ans[i]<<" ";
	

	
	return 0;
}


Measured memory_bytes: 7936
n, m, d = input().split()
n = int(n)
m = int(m)
d = int(d)

if d == 0:
    x = n
    if n == 1:
        result = m - 1
    else:
        result = x*(m-1)/n**2


else:
    x = 2*(n - d)

    result = x*(m-1)/n**2

print(result)

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

int gcd(int x, int y) {
    if (x < y) swap(x, y);
    int r = x%y;
    if (r == 0) {
        return y;
    }
    return gcd(y, r);
}

int main(){
    int K;
    cin >> K;
    ll sum = 0;
    for (int a=1; a<=K; a++) {
        for (int b=1; b<=K; b++) {
            for (int c=1; c<=K; c++) {
                sum += gcd(a, gcd(b, c));
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int N, T, A;
	int i, B;
	double U = 1000000;
	int H[1000];
	double M[1000];
	double K[1000];
	cin >> N >> T >> A;
	for (i = 0; i < N; ++i)cin >> H[i];
	for (i = 0; i < N; ++i)M[i] = T - H[i] * 0.006;
	for (i = 0; i < N; ++i) {
		K[i] = M[i] - A;
		if (K[i] < 0)K[i] = -1 * K[i];
	}
	for (i = 0; i < N; ++i) {
		if (K[i] <= U) {
			U = K[i];
			B = i;
		}
	}
	cout << B + 1;
	return 0;
}

Measured memory_bytes: 256
import math
n,m=map(int,input().split())
gcd=math.gcd(m,n)
i=1
ans=[]
max=int(math.sqrt(gcd))
for i in range(2,max+2):
    while gcd%i==0:
        ans.append(i)
        gcd//=i
if gcd>1:
  ans.append(n)

print(len(set(ans))+1)

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> p(N);
  int min = 0;
  for (int i = 0; i < N; i++){
    cin >> p[i];
  }
  sort(p.begin(), p.end());
  for (int i = 0; i < K; i++){
    min += p[i];
  }
  cout << min;
}


Measured memory_bytes: 3624
#include <iostream>

using namespace std;

int main(void)
{
    int x, y, a, b;

    cin >> x >> y;

    if(x==4 || x==6 || x==9 || x==11){
        a = 1;
    }
    else if(x==2){
        a = 2;
    }
    else{
        a = 3;
    }
    if(y==4 || y==6 || y==9 || y==11){
        b = 1;
    }
    else if(y==2){
        b = 2;
    }
    else{
        b = 3;
    }

    if(a==b){
        cout << "Yes" << endl;
    }

    else{
        cout << "No" << endl;
    }

    return 0;
}

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

int main(){
    cin.tie(0)->sync_with_stdio(false);

	int n;
	cin >> n;
	ll x;
	cin >> x;
	vector<ll> a(n);
	REP(i, n) cin >> a[i];

	ll res = 0;
	REP(i, n - 1) {
		ll tmp = (a[i] + a[i + 1]) - x;
		if (tmp > 0) {
			res += tmp;
			ll diff = tmp - a[i + 1];
			if (diff > 0) {
				a[i + 1] = 0;
				a[i] -= diff - a[i + 1];
			} else a[i + 1] -= tmp;
		}
	}

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


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

namespace diverta20192_B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var x = new long[N];
            var y = new long[N];
            for (int i = 0; i < N; i++)
            {
                var xy = Console.ReadLine().Split().Select(long.Parse).ToArray();
                x[i] = xy[0];
                y[i] = xy[1];
            }

            var difDic = new Dictionary<Tuple<long, long>, long>();
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    if (i == j) continue;

                    var dif = new Tuple<long, long>(x[i] - x[j], y[i] - y[j]);
                    if (difDic.ContainsKey(dif))
                    {
                        difDic[dif]++;
                    }
                    else
                    {
                        difDic.Add(dif, 1);
                    }
                }
            }

            long max = 0;
            foreach (var d in difDic)
            {
                max = Math.Max(max, d.Value);
            }
            Console.WriteLine(N - max);
        }
    }
}


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
    }
    vector<int>  t(n);
    rep(i,n){
        t[i]=a[i];
    }
    sort(t.rbegin(),t.rend());
    rep(i,n){
        if(a[i]==t[0]) cout << t[1] <<endl;
        else cout << t[0]<<endl;
    }
    
    
    
    
    return 0;
}


Measured memory_bytes: 3200
h,m = map(int,input().split())
s = [input() for i in range(h)]
ans = [[] for i in range(h)]

for i in range(h):
    for j in range(m):
        if s[i][j] == "#":
            ans[i].append("#")
        else:
            count = 0
            s1=[[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
            s2=[[i-1,j+1],[i+1,j+1],[i+1,j-1],[i-1,j-1]]
            for temp in s1 :
                i2=temp[0];j2=temp[1]
                if i2<0 or h-1<i2 or j2<0 or m-1<j2:
                    continue

                if s[i2][j2]=="#":
                    count+=1

            for temp in s2 :
                i2=temp[0];j2=temp[1]
                if i2<0 or h-1<i2 or j2 <0 or m-1<j2 :
                    continue

                if s[i2][j2]=="#":
                    count+=1
            ans[i].append(count)

for i in range(h):
    print(*ans[i],sep="")

Measured memory_bytes: 3572
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str, " ");
			int H = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());

			if(H == 0 && W == 0){
				break;
			}

			for ( int i = 0; i < H; i++ ){
				for ( int j = 0; j < W; j++ ){
					System.out.print("#");
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}



Measured memory_bytes: 31524
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<stack>
using namespace std;
int main()
{
    int n,l;
    while(cin>>n>>l)
    {
        string mapp[105];
        int a[105];
        for(int i=0; i<n; i++)
        {
            cin>>mapp[i];
        }
        sort(mapp, mapp+n);
        for(int j=0; j<n; j++)
            cout<<mapp[j];
        }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = 100100100;
const double PI = 3.14159265358979323846;
typedef long long ll;
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) for (ll i = 0; i < (n); ++i)

int main() {
  ll n;
  bool exist = false;
  cin >> n;
  for (ll i = 1; i <= 9; ++i) {
    if (n % i == 0 && n / i <= 9) {
      exist = true;
      break;
    }
  }
  cout << (exist ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(int argc, const char * argv[]) {
    long long money=100,X,i,c=0;
    std::cin >> X;
    
    for(i=1;money<X;i++){
        money=money*1.01;
        c++;
    }
    
    // insert code here...
    std::cout << c;
    
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
    }
} fast;

/* define */
#define FOR(I, X, Y) for (long long(I) = (X); (I) < (Y); (I)++)
#define REP(I, X, Y) for (long long(I) = (Y)-1; (I) >= (X); (I)--)
#define ALL(X) (X).begin(), (X).end()
#define pb push_back
#define COUNT(V, X)                           \
    (upper_bound((V).begin(), (V).end(), X) - \
     lower_bound((V).begin(), (V).end(), X))
#define debug(x) cerr << #x << ':' << x << endl;
#define DEBUG(v)                             \
    {                                        \
        cerr << #v << ':';                   \
        for (auto xv : v) cerr << xv << ' '; \
        cerr << endl;                        \
    }
#define Yes(X) cout << (X ? "Yes" : "No") << endl;
#define YES(X) cout << (X ? "YES" : "NO") << endl;
#define ctoi(C) (C - '0')
#define pow2(x) ((long long)((long long)1 << x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1, 0, -1, 0};
const long long dy[] = {0, 1, 0, -1};
const long long dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
const long long dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long dx9[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
const long long dy9[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) a = b;
    return a < b;
}
long long max(long long x, int y) {
    return max(x, (long long)y);
}
long long max(int x, long long y) {
    return max((long long)x, y);
}
long long min(long long x, int y) {
    return min(x, (long long)y);
}
long long min(int x, long long y) {
    return min((long long)x, y);
}

/* library */

/* main */

signed main() {
    string S;
    cin >> S;
    bool good = true;
    for (int i = 0; i < 3; i++) {
        good &= S[i] != S[i + 1];
    }
    cout << (good ? "Good" : "Bad") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"

using namespace std;
typedef long long ll ;
typedef pair <int,int>  pii;

int main() {
    ll x;
    cin >> x;
    cout << 1LL * (x / 500) * 1000 + 1LL * ((x % 500) / 5) * 5;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define len(X) ((int)(X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000, MAX_M = 100000;
int N, M;
int u[MAX_M], v[MAX_M];
int S, T;

                            
struct edge { int to, cost; };
const int MAX_V = MAX_N*3, INF = 1e9;

// Vの初期化を忘れない。
int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
  fill(d, d+V, INF);
  priority_queue<Pii, vector<Pii>, greater<Pii> > pque;
  d[s] = 0;
  pque.push(Pii(0, s));


  while (!pque.empty()) {
    Pii p = pque.top(); pque.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (int i = 0; i < (int)G[v].size(); ++i) {
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost; 
        pque.push(Pii(d[v]+ e.cost, e.to));
      }
    }
  }
}

int main() {

  cin >> N >> M;
  rep(i, M) cin >> u[i] >> v[i];
  cin >> S >> T;
  V = N*3;
  rep(i, M) { --u[i]; --v[i]; }
  --S; --T;

  for (int i = 0; i < M; ++i) {
    G[u[i]*3].push_back((edge){v[i]*3 + 1, 1});
    G[u[i]*3 + 1].push_back((edge){v[i]*3 +2, 1});
    G[u[i]*3 + 2].push_back((edge){v[i]*3, 1});
  }

  dijkstra(S*3);

  if (d[T*3] == INF) {
    cout << -1 << endl;
  } else {
    cout << d[T*3]/3 << endl;
  }

  return 0;
}


Measured memory_bytes: 18560
#include<stdio.h>

int main()
{
  int n,i,x,y,z;
  int a;
  int cnt=0;
  scanf("%d",&n);
  
  for(i=1;i<=n;i++)
  {
     for(x=1;x<=100;x++)
     {
       if((x+1)*(x+1)>=i)
         break;
       else
       for(y=x;y<=100;y++)
       {
         if((y+1)*(y+1)>=i)
          break;
         else
           for(z=y;z<=100;z++)
           {
             if((x+y)*(x+y)+(x+z)*(x+z)+(y+z)*(y+z)==2*i)
             {
               if(x==y&&y==z)
                 cnt+=1;
               else if(x!=y&&y!=z&&z!=x)
                 cnt+=6;
               else
                 cnt+=3;
             }
             if((z+1)*(z+1)>=i)
               break;
           } 
       }
     }
    printf("%d\n",cnt); 
    cnt=0;
  }
  return 0;
}

Measured memory_bytes: 1676
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define ll long long
#define coYes cout << "Yes" << endl
#define coYES cout << "YES" << endl
#define coyes cout << "yes" << endl
#define coNo cout << "No" << endl
#define coNO cout << "NO" << endl
#define cono cout << "no" << endl
#define BIT_FLAG_0 (1<<0) // 0000 0000 0000 0001
int gcd(int a, int b){ //最大公約数
    if(a%b == 0){
        return b;
    }else{
    return gcd(b, a%b);
    }
}

int main(){
    int a,b,c,x,q=0;
    cin >> a >> b >> c >> x;
    rep0(i,a+1){
        rep0(j,b+1){
            rep0(k,c+1){
                if(500*i+100*j+50*k==x) q++;
            }
        }
    }
    cout << q << endl;
    return 0;
}

Measured memory_bytes: 3632
N,*uvws=$<.read.split.map(&:to_i)

h = {}
uvws.each_slice(3) do |u,v,w|
    h[u] ||= []
    h[u] << [u,v,w%2]
    h[v] ||= []
    h[v] << [v,u,w%2]
end

arr = Array.new(N+1,-1)
arr[1] = 0

q = h[1]
until q.empty?
    u,v,w = q.shift
    next if arr[v] != -1
    if w == 0
        arr[v] = arr[u]
    else
        arr[v] = 1-arr[u]
    end
    if arr[v] != -1
        h[v].each do |x|
            q << x
        end
    end
end

puts arr[1..-1]

Measured memory_bytes: 55080
import std.stdio;
import std.typecons;
import std.algorithm;
import std.conv;

alias Tuple!(long,long) coord;

void main() {
	int K, N;
	coord [] pts;
	long [] xs;
	readf("%d %d\n", &N, &K);
	for(int i = 0; i < N; i++) {
		long x, y;
		readf("%d %d\n", &x, &y);
		pts ~= coord(x,y);
		xs ~= x;
	}

	sort(xs);
	long res = 5_000_000_000_000_000_000L;
	for(int i = 0; i < xs.length; i++) {
		for(int j = i; j < xs.length; j++) {
			long [] ys;
			for(int k = 0; k < pts.length; k++) {
				if(xs[i] <= pts[k][0] && pts[k][0] <= xs[j])
					ys ~= pts[k][1];
			}
			sort(ys);
			for(int k = 0; k+K-1 < ys.length; k++)
				res = min(res, (xs[j]-xs[i])*(ys[k+K-1]-ys[k]));
		}
	}
	writeln(res);
}



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

#define int long long

signed main() {
	int N, W;
	cin >> N >> W;

	const int BEAM = 100000;

	vector<int> w(N), v(N);
	pair<double, pair<double ,double>> p[100000];
	for (int i = 0; i < N; ++i){
		double a, b;
		cin >> b >> a;
		p[i] = make_pair(a / b, make_pair(a,b));
	}
	sort(p, p + N, greater<pair<double, pair<double, double>>>());
	for (int i = 0; i < N; i++){
		w[i] = p[i].second.second;
		v[i] = p[i].second.first;
	}

	// 現在の状態（価値・重さ）
	vector<pair<long long, int>> curr;
	curr.emplace_back(0, 0);

	// ビームサーチ
	for (int i = 0; i < N; ++i) {
		// 次の状態（価値・重さ）
		vector<pair<long long, int>> next;

		for (const auto& s : curr) {
			next.emplace_back(s);
			if (s.second + w[i] <= W) {
				next.emplace_back(s.first + v[i], s.second + w[i]);
			}
		}
		// 価値が大きい順に並び替え
		sort(next.rbegin(), next.rend());
		// 状態をビーム幅に減らす
		if (next.size() > BEAM) next.resize(BEAM);
		curr = move(next);
	}

	// 結果
	cout << curr[0].first << endl;
}


Measured memory_bytes: 14848
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define hi cout<<'h'<<'i'<<'\n' 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    map<string,int> mp;
    mp["Sunny"]=1;
    mp["Cloudy"]=2;
    mp["Rainy"]=0;
    string arr[3]={"Sunny","Cloudy","Rainy"};
    string s;
    cin>>s;
    cout<<arr[mp[s]];

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;
class Main{


	static char[][] map;

	static long[][] c;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		int[] p = new int[n];
		for(int i = 0;i < n;i++){
			p[i] = sc.nextInt();
			
		}
		if(check(p)){
			System.out.println("YES");
			return;
		}
		for(int i= 0;i < n;i++){
			
			for(int j = i + 1;j < n;j++){
				int[] cc = p.clone();
				cc[i] = p[j];
				cc[j] = p[i];
				if(check(cc)){
					System.out.println("YES");
					return;
				}
			}
		}
		System.out.println("NO");


		
	}
	static boolean check(int[] cc){
		for(int i = 0;i < cc.length-1;i++){
			if(cc[i] > cc[i+1]){
				return false;
			}
		}
		return true;
	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}



class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return   end- otherpair.end;
	}








}






Measured memory_bytes: 23508
y,n1 = map(int,input().split())
k10=-1
k5=-1
k1=-1
n=n1
for i in range(n//10000+1):
    n=n1
    if(n//10000==y and n%10000==0):
        k10=n//10000
        k5=0
        k1=0
        break
    elif(n//10000>y):
        break
    else:
        i=n//10000-i
        n-=i*10000
        for j in range(n//5000+1):
            n=n1-i*10000
            if(n//5000==(y-i) and n%5000==0):
                k10=i
                k5=n//5000
                k1=0
                break
            elif(n//5000>y-i):
                break
            else:
                n=n1-i*10000
                j=n//5000-j
                n-=j*5000
                if(n//1000==(y-i-j) and n%1000==0):
                    k10=i
                    k5=j
                    k1=n//1000
                    break
    if(k1!=-1):
        break
    
print(k10,k5,k1)

Measured memory_bytes: 3064