akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

int N, M, Q;
int a[51], b[51], c[51], d[51];
void dfs(int i, int x, int &res, vector<int> &A) {
    if (i == N) {
        int sum = 0;
        REP(j, Q) {
            if (A[b[j]] - A[a[j]] == c[j]) sum += d[j];
        }
        res = max(res, sum);
        return;
    }
    A[i] = x;
    for (int y = x; y <= M; ++y) { dfs(i + 1, y, res, A); }
}

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

    cin >> N >> M >> Q;
    REP(i, Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i];
        --b[i];
    }
    int res = 0;
    vector<int> A(N);

    FOR(x, 1, M + 1) { dfs(0, x, res, A); }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int MAXN = 2 * 105000;

int n, k;
int p[MAXN];
double e[MAXN];
double sum, ans;

int main() { 

  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &p[i]);
  }

  for (int i = 0; i < n; i++) {
    long long curSum = 1ll * (p[i] + 1) * p[i] / 2;
    e[i] = 1.0 * curSum / p[i];
  }

  for (int i = 0; i < n; i++) {
    sum += e[i];
    if (i - k >= 0) {
      sum -= e[i - k];
    }
    if (i >= k - 1) {
      ans = max(ans, sum);
    }
  }

  printf("%.12lf\n", ans);

  return 0;
}


Measured memory_bytes: 2560
import collections
 
n = int(input())
d = list(map(int, input().split()))
for i in range(len(d)):
    if i == 0 and d[i] != 0:
        print(0)
        exit()
    if i != 0 and d[i] == 0:
        print(0)
        exit()
 
e = collections.Counter(d)
 
e2 = dict(sorted(e.items()))
e3 = list(e2.values())
e4 = list(e2.keys())
# print(e2)
#print(e3)
#print(e4)
 
tmp = 0
for i in e4:
    if i - tmp >= 2:
        print(0)
        exit()
    tmp = i
cntsum = 1
for i in range(1, len(e3)):
    cntsum *= e3[i - 1] ** e3[i]
print(cntsum%998244353)

Measured memory_bytes: 75948
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>
#include<ctype.h>
using namespace std;


int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a==b&&a!=c) {
		cout << "Yes" << endl;
	}
	else if(c == b && a != c) {
		cout << "Yes" << endl;
	}
	else if (c == a && a != b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
import math

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

hk=(h*60+m)*0.5
mk=6*m

f=a**2+b**2-2*a*b*math.cos(math.radians(min(abs(hk-mk),360-abs(hk-mk))))
print(math.sqrt(f))

Measured memory_bytes: 9512
n = int(input())
p = list(map(int,input().split()))
count = 0
for i in range(1, n-1):
    p_max = max(p[i-1],p[i], p[i+1])
    p_min = min(p[i-1], p[i], p[i+1])
    if p_max != p[i] and p_min != p[i]:
        count += 1
print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	int A;
	long long B, N;
	int ans = 0;
	cin >> A >> B >> N;

	//余りがB-1で
	long long x_max = ((N / B) - 1)*B + (B - 1);
	long long test;
	test = A * x_max / B;
	test -= A * (long long)(x_max / B);

	ans = max(ans, (int)test);

	test = A * N / B;
	test -= A * (long long)(N / B);

	ans = max(ans, (int)test);

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

Measured memory_bytes: 3136
n = int(input())

def make_divisors(nnn):
    masu = []
    for i in range(1, int(nnn**0.5)+1):
        if nnn % i == 0:
            masu.append(i + nnn//i)
    return masu

masu_min = min(make_divisors(n))

print(masu_min - 2)

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

int main() {
int a,b,c,d;
cin >> a >> b >> c >> d;
int x = (a+d-1)/d;
int y = (c+b-1)/b;
cout << (x>=y?"Yes":"No") << "\n";
return 0;
}

Measured memory_bytes: 3640
import copy
n = int(input())
l = list(map(int, input().split()))
m = sorted(copy.copy(l))
check = [True] * n
for i in range(n):
    if not (l[i] == m[i]):
        check[i] = False
if check.count(False) <= 2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3444
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct node
{
    int k,l,r;
    node(int k=0,int l=0,int r=0):k(k),l(l),r(r){}
};
struct haha
{
    int id,v,k;
    haha(int id=0,int v=0,int k=0):id(id),v(v),k(k){}
    bool operator<(const haha&o)const
    {
        if(v==o.v) return k<o.k;
        return v<o.v;
    }
};
vector<node>vl,vr;
int n,t[N<<2],lz[N<<2],ss[N];
ll ans=0;
ll s[2][N];
void update(int l,int r,int k)
{
    assert(t[k]>=0);
    if(l!=r)
    {
        t[k<<1]-=lz[k];t[k<<1|1]-=lz[k];
        lz[k<<1]+=lz[k];lz[k<<1|1]+=lz[k];
        t[k]=min(t[k<<1],t[k<<1|1]);
    }
    lz[k]=0;
}
int query(int l,int r,int k)
{
    if(lz[k]) update(l,r,k);
    if(t[k]>0) return 0;
    if(l==r) return l;
    int m=l+r>>1;
    if(t[k<<1|1]<=0) return query(m+1,r,k<<1|1);
    return query(l,m,k<<1);
}
void fix(int l,int r,int k,int x,int y)
{
    if(lz[k]) update(l,r,k);
    if(r<x||l>y) return;
    if(l>=x&&r<=y)
    {
        lz[k]++;t[k]--;update(l,r,k);return;
    }
    int m=l+r>>1;
    fix(l,m,k<<1,x,y);fix(m+1,r,k<<1|1,x,y);
    t[k]=min(t[k<<1],t[k<<1|1]);
}
void build(int l,int r,int k)
{
    t[k]=l;lz[k]=0;
    if(l==r) return;
    int m=l+r>>1;
    build(l,m,k<<1);build(m+1,r,k<<1|1);
    t[k]=l;
}
void solve(vector<node>v,int p)
{
    build(1,n,1);
    priority_queue<haha>q;
    ll sum=0;
    for(int i=0;i<v.size();i++) sum+=v[i].r,q.push(haha(i,v[i].l-v[i].r,v[i].k));
    s[p][0]=sum;
    for(int i=1;i<=n;i++)
    {
        int pos=query(1,n,1);
        //cout<<pos<<' '<<t[1]<<endl;
        while(!q.empty())
        {
            int id=q.top().id;q.pop();
            if(v[id].k==0) continue;
            if(v[id].k>pos)
            {
                //cout<<v[id].l<<' '<<v[id].r<<' '<<v[id].k<<endl;
                sum=sum-v[id].r+v[id].l;
                fix(1,n,1,v[id].k,n);
                break;
            }
        }
        s[p][i]=max(sum,s[p][i-1]);
    }
}
fstream in,out;
void getts()
{
    int t=50;
    in.open("1.txt");
    in<<t<<endl;
    while(t--)
    {
        int n=5;
        in<<n<<endl;
        for(int i=1;i<=n;i++)
        {
            int k=rand()%n+1,l=rand()%100+1,r=rand()%100+1;
            in<<k<<' '<<l<<' '<<r<<endl;
        }
    }
    in.close();
}
bool de=false;
int main()
{
    srand(time(0));
    //getts();freopen("1.txt","r",stdin);out.open("out.txt");de=true;
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        vl.clear();vr.clear();ans=0;
        for(int i=1;i<=n;i++)
        {
            int k,l,r;
            scanf("%d%d%d",&k,&l,&r);
            if(l==r) ans+=l;
            else if(l>r) vl.push_back({k,l,r});
            else vr.push_back({n-k,r,l});
        }
        for(int i=0;i<=n;i++) s[0][i]=s[1][i]=0;
        solve(vl,0);
        solve(vr,1);
        ll res=0;
        for(int i=0;i<=n;i++)
            res=max(res,s[0][i]+s[1][n-i]);
        if(!de) printf("%lld\n",ans+res);
        if(de) out<<ans+res<<endl;
    }
}


Measured memory_bytes: 16796
program kadai
implicit none
integer(8)  ::  a,b
integer(8) ::  c,d
integer(8)  ::  sa,sb,i,g
integer(8)  ::  aac,aad,bbc,bbd,alpha1,alpha2
integer(8)  ::  unta,untb,ans

read(*,*) a,b,c,d
a=a-1
aac=a/c
aad=a/d
bbc=b/c
bbd=b/d

sa=dble(c*d)
g=gcd(c,d)
alpha1=a/(sa/g)
alpha2=b/(sa/g)

untb=b-(bbc+bbd-alpha2)
unta=a-(aac+aad-alpha1)
ans=untb-unta

write(*,*) ans

stop
contains
integer function gcd(a,b)
    implicit none
    integer(8),intent(in)  ::  a,b
    integer(8)  ::  l,m,n
    m=a
    n=b
    do
        l=mod(m,n)
        if (l==0) then
            exit
        end if
        m=n
        n=l
    end do
    gcd=n
    return
end function gcd




end program kadai


Measured memory_bytes: 256
// Aizu Vol-6 0619: Selecting Subjects
// 2017.9.5 bal4u@uu

#include <stdio.h>

int main()
{
	int i, a, ans, min;

	for (ans = 0, min = 100, i = 0; i < 4; i++) {
		scanf("%d", &a), ans += a;
		if (a < min) min = a;
	}
	ans -= min;
	for (min = 100, i = 0; i < 2; i++) {
		scanf("%d", &a), ans += a;
		if (a < min) min = a;
	}
	ans -= min;
	printf("%d\n", ans);
	return 0;
}

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

int main() {
 ll x,y;
 cin >> x >> y;
 ll ans = 0;
 if(x == y) ans = 0;
 else if(abs(x) == abs(y)) ans = 1;
 else if(x < y && x*y > 0) ans = y-x;
 else if(x > y && x*y > 0) ans = 1 + x-y + 1;
 else if(x*y < 0) ans = abs(abs(x) - abs(y)) + 1;
 //else if(x > 0 && y < 0) ans = 1 + abs(abs(x) - abs(y));
 else if(x == 0 && y < 0) ans = -y + 1;
 else if(x == 0 && y >0) ans = y;
 else if(x < 0 && y == 0) ans = -x;
 else if(x > 0 && y == 0) ans = x + 1;
 cout << ans << endl;
 
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
int main()
{
    int n,s;
    cin>>n>>s;
    if(s>=n)cout<<"unsafe"<<endl;
    else cout<<"safe"<<endl;
}


Measured memory_bytes: 3632
using System;
using System.Collections.Generic;

class CardEater
{
	static public void Main(string[] args)
	{
		int N;
		Dictionary<int, int> ADic = new Dictionary<int, int>();
		string[] vals;
		int a;
		N = int.Parse(Console.ReadLine());
		vals = Console.ReadLine().Split(' ');
		for(int i=0; i<N; i++)
		{
			a = int.Parse(vals[i]);	
			if(ADic.ContainsKey(a))
			{
				ADic[a]++;
			}
			else
			{
				ADic[a] = 1;
			}
		}
		int evenCards = 0;
		foreach(int v in ADic.Values)
		{
			if(v % 2 == 0)
				evenCards++;
		}

		if(evenCards % 2 == 0)
		{
			Console.WriteLine(ADic.Count);
		}
		else
		{
			Console.WriteLine(ADic.Count - 1);
		}
	}
}


Measured memory_bytes: 22624
n=int(input())
a=list(map(int,input().split( )))
q=int(input())
for i in range(q):
    com,b,e=map(int,input().split( ))
    if com==0:
        mn=min(a[b:e])
        print(mn)
    else:
        mx=max(a[b:e])
        print(mx)



Measured memory_bytes: 5632
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    i64 a,b,x;
    cin>>a>>b>>x;
    i64 start = ceil(a/(long double)x);
    i64 end = floor(b/(long double)x);
    //cout<<start<<" "<<end<<endl;
    if(start>end)   cout<<0<<endl;
    else            cout<<end-start+1<<endl;
    return 0;
}



Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
using namespace std;
int N, M, A, B, C, D, x1, x2, y1, y2;
int K[32][32];

int mini(int s,int t){
  if(s>t){
    return t;
  }
  return s;
}

int main(){
  for (int i = 0; i < 32; ++i)
  {
    for (int j = 0; j < 32; ++j)
    {
      K[i][j]=100100100;
    }
  }

  scanf("%d%d", &N, &M);
  for (int i=0; i<M;++i){
    scanf("%d,%d,%d,%d", &A, &B, &C, &D);
    K[A][B]=C;
    K[B][A]=D;
    // cerr << "read " <<A<<" " << B << " " << C <<" "<< D <<endl;
  }
  for (int i = 1; i < N+1 ; ++i)
  {
    for (int j = 0; j < N+1; ++j)
    {
      for(int k=0;k<N+1;++k)
      {
        K[j][k]=mini(K[j][i]+K[i][k],K[j][k]);
      }
    }
  }
  scanf("%d,%d,%d,%d", &x1, &x2, &y1, &y2);
  // cout << K[x1][x2];
  cout << y1-y2-K[x1][x2]-K[x2][x1] << endl;

}

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

import sys
if K > ((N-1)*(N-2)//2):
    print(-1)
    sys.exit()
    
edge = []
for i in range(N-1):
    edge.append([i+1,N])

nums = (N-1)*(N-2)//2 - K
for i in range(N-1):
    for j in range(i+1,N-1):
        if nums==0:break
        edge.append([i+1,j+1])
        nums-=1
    if nums==0:break

print(len(edge))
for u,v in edge:
    print(u,v)


Measured memory_bytes: 4128
#include <bits/stdc++.h>
#include <cstring>
#include <limits>
using namespace std;
#define ll long long int
#define lli long long int
#define fw(i, s, e) for (ll i = s; i < e; ++i)
#define fe(i, s, e) for (ll i = s; i <= e; ++i)
#define fb(i, e, s) for (ll i = e; i >= s; --i)
#define L(T)  \
    ll T;     \
    cin >> T; \
    while (T--)
#define FASTIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define mem(a, i) memset(a, i, sizeof(a))
#define ld long double
#define endl "\n"
#define in(P) \
    ll P;     \
    cin >> P;
int main()
{
    FASTIO
    in(n);
    ll fi[100000];
    mem(fi, 0);
    ll ans = 0;
    fw(i, 1, n + 1)
    {
        ll tmp = n / i;
        ans += i * (tmp * (tmp + 1)) / 2;
    }
    cout << ans << " ";
    return 0;
}

Measured memory_bytes: 3580
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val c = sc.nextInt()
    println(problem110(a, b, c))
}

fun problem110(a: Int, b: Int, c: Int): Int {
    val abc = listOf(a, b, c).sorted()
    return Integer.parseInt(abc[2].toString() + abc[1].toString()) + abc[0]
}

Measured memory_bytes: 35840
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    string s;cin>>s;
    int k;cin>>k;
    int ss=s.size();
    string copy=s;
    sort(all(copy));
    vch t(ss);
    t[0]=copy[0];
    int h=1;
    rep(i,ss-1){
        if(copy[i+1]!=copy[i]){
            t[h]=copy[i+1];
            h++;
        }
    }
    vstr tmp;
    int j=0;
    int sum=0;
    set<string> p;
    while(1){
        int l=0;
        rep(i,ss){
            if(s[i]==t[j]){
                tmp.push_back(s.substr(i));
                l++;
            }
        }
        sort(all(tmp));
        for(auto u:tmp){
            rep(i,u.size()){
                if(!(p.count(u.substr(0,i+1)))&&sum<k){
                    sum++;
                    p.insert(u.substr(0,i+1));
                }
                if(sum==k){
                    cout<<u.substr(0,i+1)<<endl;
                    return 0;
                }
            }
        }
        tmp.clear();
        j++;
    }
}

Measured memory_bytes: 15964
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	a := nextInt()
	b := nextInt()
	_, dl := getDivlistSlow(gcd(a, b))

	cnt := 1
	for _, v := range dl {
		if v == 1 {
			continue
		}
		if isPrime(v) == true {
			cnt++
		}
	}
	fmt.Println(cnt)

}

// 素数判定
func isPrime(a int) bool {
	for i := 2; i*i <= a; i++ {
		if a%i == 0 {
			return false
		}
	}
	return true
}
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

// 約数列挙リストを作成(愚直)
func getDivlistSlow(a int) (cnt int, divlist []int) {
	for i := 1; i*i <= a; i++ {
		if a%i == 0 {
			cnt++
			divlist = append(divlist, i)
			if i*i != a { // 6*6=36 などを重複カウントしない
				cnt++
				divlist = append(divlist, a/i)
			}
		}
	}
	sort.Ints(divlist) // 昇順ソート
	return cnt, divlist
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 2052
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
#define int ll

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int M = 1e9 + 7, N = 2e5 + 7;
int ans;

int qpow(int a, int b) {
	if(b == 0) return 1;
	int t = qpow(a, b/2);
	if(b & 1) return t * t % M * a % M;
	else return t * t % M;
}

int inv(int a) {
	return qpow(a, M-2);
}

vi G[N];
int sum[N], cnt[N];

void dfs(int u, int p = -1) {
	if(G[u].size() == 1 && p != -1) {
		sum[u] = 0;
		cnt[u] = 2;
		return;
	}
	cnt[u] = 1;
	for(int v:G[u])if(v != p) {
		dfs(v, u);
		cnt[u] = cnt[u] * cnt[v] % M;
	}
	for(int v:G[u]) if(v != p) {
		sum[u] = (sum[u] + cnt[u] * inv(cnt[v]) % M * 2 % M * sum[v] % M) % M;
		ans -= sum[v] + (cnt[v] - 1);
		ans = (ans % M + M) % M;
	}
	sum[u] += (cnt[u] - 1);
	sum[u] %= M;
	ans += sum[u];
	ans %= M;
	cnt[u] = cnt[u] * 2 % M;
}

signed main()
{
	IO_OP;
	
	int n;
	cin >> n;
	for(int i=0;i<n-1;i++) {
		int u, v;
		cin >> u >> v;
		G[u].PB(v);
		G[v].PB(u);
	}
	dfs(1);
	cout << ans * inv(qpow(2, n)) % M << endl;
}





Measured memory_bytes: 28032
///Code Forces - DP Educational Contest


#include <iostream>
#include <string.h>
#include <algorithm>


const int NMAX = 100001;

int h[NMAX];
int DP[NMAX];

int main() 
{
	int N, K;
	std::cin >> N >> K;

	for (int i = 1; i <= N; ++i) {
		std::cin >> h[i];
	}

	DP[N] = 0;
	DP[N - 1] = std::abs(h[N] - h[N - 1]);

	for (int i = N - 2; i >= 1; --i) {
		DP[i] = DP[i + 1] + std::abs(h[i] - h[i + 1]);
		for (int j = i + 2; j <= N && j <= i + K; ++j) {
			DP[i] = std::min(DP[i], DP[j] + std::abs(h[i] - h[j]));
		}
	
	}

	std::cout << DP[1];

	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	private Scanner sc;
	
	public static void main(String[] args) {
		new Main();
	}
	
	public Main() {
		sc = new Scanner(System.in);
		
		int num = 0;
		while (sc.hasNextLine() == true) {
			String line = sc.nextLine();

			int state = 0;
			int tmp = 0;
			for (int i = 0; i < line.length(); i++) {
				if (Character.isDigit(line.charAt(i)) == true) {
					tmp = tmp * 10 + (line.charAt(i) - '0');
					state++;
				} else {
					if (state > 0) {
						num = num + tmp;

						state = 0;
						tmp = 0;
					}
				}
			}
			num = num + tmp;
		}
		
		System.out.println(num);
	}
}

Measured memory_bytes: 26040
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll sum = 0;
	vector<ll> a(n), rui(n+1, 0);
	rep(i,n){
		cin >> a[i];
		rui[i+1] = rui[i] + a[i];
		sum += a[i];
	}
	ll ans = 1e18;
	for(int i = 0; i <= n; ++i){
		ll x = rui[i];
		ll y = sum - rui[i];
		ll cost = llabs(x - y);
		chmin(ans, cost);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6352
N, M = map(int, input().split())

def kaijo(n):
    res = 1
    for i in range(n):
        res *= (n-i)
        res = res%(10**9+7)
    return res
    
if abs(N - M) >= 2:
    print(0)
elif N == M:
    print(((kaijo(N)*kaijo(M))*2)%(10**9+7))
else:
    print(((kaijo(N)*kaijo(M)))%(10**9+7))

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<cmath>

int size[3],n,radius;
int d[10000];

int main(){
	while(std::cin>>size[0]>>size[1]>>size[2] ,(size[0]||size[1]||size[2]) ){
		std::sort(size,size+3);
		std::cin>>n;
		while( n-- ){
			std::cin>>radius;
			if( pow(radius*2,2) <= pow((float)size[0],2) + pow((float)size[1],2) )
				std::cout<<"NA"<<std::endl;
			else std::cout<<"OK"<<std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1172
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
typedef long long ll;
int K, A, B;
ll ans = 0;

int main(){
	scanf("%d%d%d", &K, &A, &B);
	if(B-A<=2){
		printf("%d", K+1);
		return 0;
	}else{
		if(K+1<=A){
			printf("%d", K+1);
			return 0;
		}
		K-=(A-1);
		ans = A;
		int t = K/2;
		if(K%2==1){
			ans++;
		}
		ans+=(ll)t * (ll)(B-A);
		printf("%lld", ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;

typedef long double lld;

#define REP(i,n) for(int i=0;i<n;i++)
#define EPS (1e-9)
#define INF (1e9 + 1)
#define PI (acos(-1))

double W, H;
double x, y;

int main()
{
	cin >> W >> H >> x >> y;
	cout << (W * H) / 2 << " ";
	if (W / 2 <= x + EPS && W / 2 >= x - EPS && H / 2 <= y + EPS && H / 2 >= y - EPS) {
		cout << 1 << endl;
	}
	else cout << 0 << endl;

}

Measured memory_bytes: 256
import sys
import collections

x = [1, 1, 0, -1, -1, -1, 0, 1]
y = [0, 1, 1, 1, 0, -1, -1, -1]
while True:
    W, H = map(int, sys.stdin.readline().split())
    if W == 0:
        break
    
    tile = [[-1 for i in xrange(W + 2)] for j in xrange(H + 2)]
    
    
    for i in xrange(H):
        line = raw_input().strip().split()
        for j in xrange(W):
            if line[j] == '1':
                tile[i + 1][j + 1] = 1
            elif line[j] == '0':
                tile[i + 1][j + 1] = 0
    result = 0
    for h in xrange(1, H + 1):
        for w in xrange(1, W + 1):
            if tile[h][w] == 1:
                result += 1
                next = set([(h, w)])
                while len(next) > 0:
                    temp_next = set()
                    for n_h, n_w in next:
                        tile[n_h][n_w] = -1
                        for i in xrange(len(x)):
                            temp = (n_h + x[i], n_w + y[i])
                            if tile[temp[0]][temp[1]] == 1:
                                temp_next.add(temp)
                    next = temp_next
    print result

Measured memory_bytes: 4680
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
string S;
int main(){
	cin>>S;
	string aki="AKIHABARA";
	int i=0,j=0;
	while(i<(int)S.size() && j<(int)aki.size()){
		if(S[i]==aki[j]){
			i++;
			j++;
		}else if(aki[j]=='A'){
			j++;
		}else{
			break;
		}
	}
	while(j<(int)aki.size() && aki[j]=='A'){j++;}
		
	cout<<(i==(int)S.size() && j==(int)aki.size() ? "YES" : "NO")<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvl = vector<vector<long>>;
using pii = pair<int, int>;
using pil = pair<int, long>;
using pll = pair<long, long>;
using vc = vector<char>;
#define fix20 cout << fixed << setprecision(20)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,s,t) for(int i=s; i<t; i++)
#define RNG(i,s,t,u) for(int i=s; i<t; i+=u)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
  int n;
  string s;
  cin >> n >> s;
  vector<long> cnt(26,0);
  rep(i,n){
    cnt.at(s.at(i)-'a')++;
  }
  long ans = 1;
  rep(i,26){
    ans *= cnt.at(i)+1;
    ans %= MOD;
  }
  cout << (ans + MOD - 1) % MOD << endl;
}

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

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

    string s;
    cin >> s;
    if (s[0] == s[1] && s[0] == s[2]) {
        cout << "No";
    } else {
        cout << "Yes";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;

int main(void){
    int h, w, d[1000][1000], dy[4]={0, 1, 0, -1},dx[4]={1, 0, -1, 0}, m=0;
    string a[1000];
    queue<P> q;
    cin>>h>>w;
    for(int i=0;i<h;i++){
        cin>>a[i];
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(a[i][j]=='#'){
                q.push(P(i, j));
                d[i][j]=0;
            }else{
                d[i][j]=-1;
            }
        }
    }
    while(!q.empty()){
        P p=q.front();
        q.pop();
        int y=p.first, x=p.second;
        for(int i=0;i<4;i++){
            int py=y+dy[i], px=x+dx[i];
            if(py>=0&&py<h&&px>=0&&px<w){
                if(d[py][px]==-1){
                    d[py][px]=d[y][x]+1;
                    q.push(P(py, px));
                    m=max(m, d[py][px]);
                }
            }
        }
    }
    cout<<m<<endl;
}


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

using namespace std;

typedef long long ll;

#define MOD 1000000007

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

Measured memory_bytes: 3188
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(abs(a - b), min(a, b));
}
ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
int main() {
	int a1, m1, a2, m2, a3, m3;
	while (cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3, a1 || a2 || a3 || m1 || m2 || m3) {
		ll cnt1 = 0, cnt2 = 0, cnt3 = 0;
		int x = 1, y = 1, z = 1;
		do{
			x = (a1 * x) % m1;
			cnt1++;
		} while (x != 1);
		do {
			y = (a2 * y) % m2;
			cnt2++;
		} while (y != 1);
		do {
			z = (a3 * z) % m3;
			cnt3++;
		} while (z != 1);
		cout << lcm(lcm(cnt1, cnt2), cnt3) << endl;
	}
}

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

signed main()
{
    int n , cnt[4] = {};
    string s;

    cin >> n;
    for(int i=0 ;i<n ;i++ ){
        cin >> s;

        if(s == "AC"){
            cnt[0]++;
        } else if (s == "WA"){
            cnt[1]++;
        } else if (s == "TLE"){
            cnt[2]++; 
        } else {
            cnt[3]++;
        }
    }

    printf("AC x %d\n" ,cnt[0]);
    printf("WA x %d\n" ,cnt[1]);
    printf("TLE x %d\n" ,cnt[2]);
    printf("RE x %d\n" ,cnt[3]);

    return (0);
}

Measured memory_bytes: 3696
// AUTHOR: ROSHAN SRIVASTAVA
// WEBSITE: https://www.youtube.com/channel/UC6uQdd7kLLOdlHSVklhV7Cw

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

int n, k; 


int main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	cin>>n>>k;
	vector<int> arr(n + 1);

	for(int i = 0; i < n; i++) {
		cin>>arr[i];
		if(i < k) continue;
		else if (arr[i] > arr[i - k]) cout<<"Yes\n";
		else cout<<"No\n";
	}

	return 0;
}

Measured memory_bytes: 4032
n = int(input())
p = list(map(int,input().split()))

minp =[p[0]]

for i in range(1,n):
    minp.append(min(minp[i-1],p[i]))


cnt = 0
for i in range(n):
    if minp[i] == p[i]:
        cnt += 1
print(cnt)

Measured memory_bytes: 32184
/*
AizuOnline A2418
Title Problem B War II
*/
#include <stdio.h>
// Select Below
//#include <stdlib.h>
//#include <string.h>
//#include <float.h>
//#include <math.h>
//#include <limits.h>
//Global data section
int N,T,L,H;
int ten[101];
int hund[101];
int stor_ten;
int stor_hund;
int zan;
int player;
int change;
//
void juice()
{
#ifdef DEBUG
        printf("juice\n");
#endif
}

void init()
{
        stor_ten=T;
        stor_hund=H;
}
int ins_coin(int p)
{
        if(ten[p])
        {
#ifdef DEBUG
                printf("PLAYER PAYS 10 YES\n");
#endif
                ten[p]--;
                stor_ten++;
                zan += 10;
        }
        else if(hund[p])
        {
#ifdef DEBUG
                printf("PLAYER PAYS 100 YES\n");
#endif
                hund[p]--;
                stor_hund++;
                zan += 100;
        }
        else
        {
#ifdef DEBUG
                printf("PLAYER HAS NO COIN\n");
#endif                
                return(-1);  //NO coin >> WIN
        }
        if(stor_ten > L) // 10 YES UPPER LIMIT
        {
#ifdef DEBUG
                printf("MORE THAN 10 YEN STORAGE\n");
#endif                
                return(-1);
        }
        if(zan >= 90) //eq or more than juice price
        {
                juice();
                change = (zan - 90)/10;
                if(change > stor_ten)    // cannot return change
                {
#ifdef DEBUG
                        printf("CHANGE (%d)SHORTAGE \n",change);
#endif
                        return(-1);
                }
                stor_ten -= change;
                ten[p] += change;
                zan=0;
        }
        return(0);
}
main()
{
        int i,ret;

        scanf("%d %d %d %d",&N,&T,&H,&L);
        for(i=1;i<=N;i++)
                scanf("%d %d",&ten[i],&hund[i]);
        init();
        player=1;
        while(1)
        {
#ifdef DEBUG
                printf("PLAYER %d TURN\n",player);
#endif
                ret=ins_coin(player);

                if(ret)
                        break;
                player++;
                if(player>N)player=1;
        }

        printf("%d\n",player);




return(0);
}

Measured memory_bytes: 600
from collections import defaultdict,deque,Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a-= 1 ; b-=1
    lines[a].add(b)
    lines[b].add(a)


depths = [set() for _ in range(N)]
Ev = 0
Od = 0

def dfs(s,b,d):
    global depths
    global Ev
    global Od
    depths[d].add(s)

    if d%2 == 0:
        Ev += 1
    else:
        Od += 1

    for t in lines[s]:
        if t == b:
            continue
        else:
            dfs(t,s,d+1)


dfs(0,-1,0)

# print(depths)

n1 = (N+2)//3
n2 = (N+1)//3
n0 = (N+0)//3

# print(n0,n1,n2)
ansl = [-1]*N


if Ev <= n0 or Od <= n0:
    if Ev <= n0: fl = 0
    else: fl = 1

    for d, ps in enumerate(depths):
        if d%2 == fl:
            for p in ps:
                ansl[p] = n0*3
                n0 -= 1
        else:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                elif n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
else:
    for d, ps in enumerate(depths):
        if d%2 == 0:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
        else:
            for p in ps:
                if n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1

print(" ".join(map(str,ansl)))


Measured memory_bytes: 232220
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100005;
const int mod = 1e9 + 7;
LL a[maxn], b[maxn], aa[maxn], bb[maxn];
map<LL, int> mp;
vector<int> p;
#define N 2333
bool vis[N];
void pre() {
    for (int i=2; i<N; i++) {
        if (!vis[i]) {
            p.push_back(i);
            for (int j=i+i; j<N; j+=i) {
                vis[j] = 1;
            }
        }
    }
}
int main() {
    int n,ans=0;
    pre();
    cin>>n;
    for (int i=0; i<n; i++) {
        cin>>a[i];b[i]=a[i];
    }
    for (int i=0; i<n; i++) {
        aa[i] = 1, bb[i] = 1;
        for (int j=0; j<p.size(); j++) {
            int cnt = 0;
            while (a[i] % p[j] == 0) {
                a[i] /= p[j];
                cnt++;
            }
            if (cnt % 3 == 1) {
                aa[i] *= p[j]; bb[i] *= p[j] * p[j];
            } else if (cnt % 3 == 2) {
                bb[i] *= p[j]; aa[i] *= p[j] * p[j];
            }
        }
        aa[i] *= a[i];
        LL t = floor(sqrt(a[i]*1.0));
        if (t * t == a[i]) bb[i] *= t;
        else {
            if (bb[i]*a[i]>0 && bb[i]*a[i]*a[i]>0) bb[i] *= a[i] * a[i];
            else bb[i] = 0;
        }
        mp[aa[i]]++;
    }
    //for (int i=0; i<n; i++) {
    //    cout<<b[i]<<": "<<aa[i]<<" "<<bb[i]<<endl;
    //}
    int flag = 0;
    for (int i=0; i<n; i++) {
        if (aa[i] == 1) {
            if (flag == 0) {ans++; flag=1;}
        } else {
            ans += max(mp[aa[i]], mp[bb[i]]);
            mp[aa[i]] = mp[bb[i]] = 0;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 14464
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
 
	public static void main(String[] args) { 
		Scanner input = new Scanner(System.in);
		long H = input.nextLong();
		long A = input.nextLong();
		long ans = H/A;
		if (H%A!=0) ans++;
		System.out.println(ans);
	}	
}

Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll n,s;
  cin>>n>>s;
  ll q=sqrt(n);
  if(n==s){
    cout<<n+1<<endl;
    return 0;
  }

  if(n<s){
    cout<<-1<<endl;
    return 0;
  }
  for(int i=2;i<=q;i++){
    ll dis=0,tmp=n;
    while(tmp!=0){
      dis+=(tmp%i);
      tmp/=i;
    }
    if(dis==s){
      cout<<i<<endl;
      return 0;
    }
  }

  for(int p=(ll)q;p>0;p--){
    ll b=(n-s)/p+1;
    ll dis=0,tmp=n;
    if(b<2) continue;
    while(tmp!=0){
      dis+=(tmp%b);
      tmp/=b;
    }
    if(dis==s){
      cout<<b<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int s, h[200005], i, dp[200005] = {}, J, mnJ, k, j;
int main(){
	cin >> s >> k;
	for (i = 0; i < s; ++i)cin >> h[i];
	for (i = 1; i <= k; ++i){
		for (j = 1, mnJ = 10e9; j <= i; ++j)J = abs(h[i] - h[i - j]) + dp[i - j], mnJ = min(mnJ, J);
		dp[i] = mnJ;
	}
	for (i = k; i < s; ++i){
		for (j = 1, mnJ = 10e9; j <= k; ++j)J = abs(h[i] - h[i - j]) + dp[i - j], mnJ = min(mnJ, J);
		dp[i] = mnJ;
	}
	cout << dp[s - 1];
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <numeric>
#define REP(i, n) for(LL i = 0;i < n;i++)
#define REPR(i, n) for(LL i = n;i >= 0;i--)
#define FOR(i, m, n) for(LL i = m;i < n;i++)
#define FORR(i, m, n) for(LL i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define INF (LL)1e15
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;
typedef pair<int, P> PP;
typedef pair<LL, LP> LPP;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

struct Edge{
    int to;
    long long cost;
    Edge(int to, long long cost) : to(to), cost(cost) {}
};

class BellmanFord{
    private:
        long long INFl = (long long)1e15;
        int array_size_of_cost;
        int node_num;
        vector<vector<Edge>> adj; // adj[始点][動的配列で始点から伸びる枝]
        vector<bool> negative; // negative[n] := nに到達するまでに負閉路があるか

    public:
        BellmanFord(int n);
        vector<long long> dist; // 最短経路
        void add_edge(int f, int t, long long c);
        void run(int f);
        bool get_negative(int n);
};

BellmanFord::BellmanFord(int n):
    array_size_of_cost(n + 1),
    node_num(n),
    adj(vector<vector<Edge>>(array_size_of_cost)),
    negative(array_size_of_cost),
    dist(vector<long long>(array_size_of_cost))
{
    fill(dist.begin(), dist.end(), INFl);
    fill(negative.begin(), negative.end(), false);
}

void BellmanFord::add_edge(int f, int t, long long c){
    adj[f].push_back(Edge(t, c));
}

void BellmanFord::run(int first_node){
    dist[first_node] = 0;
    for(int loop = 0; loop < node_num - 1; loop++){
        for(int i = 0; i < node_num; i++){
            for(const Edge& e : adj[i]){
                if(dist[i] == INFl) continue;
                if(dist[e.to] > dist[i] + e.cost){
                    dist[e.to] = dist[i] + e.cost;
                }
            }
        }
    }

    for(int loop = 0; loop < node_num; loop++){
        for(int i = 0; i < node_num; i++){
            for(const Edge& e : adj[i]){
                if(dist[i] == INFl) continue;
                if(dist[e.to] > dist[i] + e.cost){
                    dist[e.to] = dist[i] + e.cost;
                    negative[e.to] = true;
                }
                if(negative[i] == true){
                    negative[e.to] = true;
                }
            }
        }
    }
}

bool BellmanFord::get_negative(int n){
    return negative[n];
}

/*************** using variables ***************/
int n, m;
vector<LL> a, b, c;
/**********************************************/

signed main(){
    cin >> n >> m;
    a.resize(m);
    b.resize(m);
    c.resize(m);
    
    BellmanFord bel(n);
    REP(i, m){
        cin >> a[i] >> b[i] >> c[i];
        bel.add_edge(a[i]-1, b[i]-1, -c[i]);
    }

    bel.run(0);
    if(bel.get_negative(n-1)){
        cout << "inf" << endl;    
    }
    else cout << -bel.dist[n-1] << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;


class Graph {
    int n;
    vector<vector<pair<int, double>>> adj;
    vector<double> d;
    
public:
    Graph(int n) {
        this->n = n;
        adj = vector<vector<pair<int, double>>>(n, vector<pair<int, double>>());
    }
    void addArc(int a, int b, double w) {
        adj[a].push_back(make_pair(b, w));
    }
    
    void addEdge(int a, int b, double w) {
        adj[a].push_back(make_pair(b, w));
        adj[b].push_back(make_pair(a, w));
    }
    
    void dijkstra(int a) {
        d = vector<double>(n, INF);
        d[a] = 0;
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
        q.push(make_pair(0, a));
        
        while (!q.empty()) {
            int u = q.top().second;
            q.pop();
            
            for (auto i: adj[u]) {
                if (d[i.first] > d[u] + i.second) {
                    d[i.first] = d[u] + i.second;
                    q.push(make_pair(d[i.first], i.first));
                }
            }
        }
    }
    
    double dist(int a) {
        return d[a];
    }
};

bool hoge(int k) {
    while (k % 2 == 0) {
        k /= 2;
    }
    while (k % 5 == 0) {
        k /= 5;
    }
    return k == 1;
}

int main() {
    int k;
    cin >> k;
    if (hoge(k)) {
        cout << 1 << endl;
        return 0;
    }
    
    Graph g(k);
    long l = 1;
    for (int i = 1; i < k; i++) {
        g.addArc(i, (i + 1) % k, 1);
        g.addArc(i, (i * 10) % k, 0);
    }
    g.dijkstra(1);
    cout << int(g.dist(0)) + 1 << endl;
}


Measured memory_bytes: 9208
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010


int solve(){
  int N, M, L, K, A, H;
  bool freezer[SIZE] = {};
  int x, y, t;
  vector<pair<int,int> > way[SIZE];

  scanf("%d%d%d%d%d%d", &N, &M, &L, &K, &A, &H);
  freezer[A] = freezer[H] = true;

  if(N == 0) return false;
  
  for(int i=0;i<L;i++){
    scanf("%d", &x);
    freezer[x] = true;
  }
  
  for(int i=0;i<K;i++){
    scanf("%d%d%d", &x, &y, &t);
    way[x].push_back({y, t});
    way[y].push_back({x, t});
  }

  bool visited[101][101] = {};
  int costMemo[101][101] = {};

  priority_queue<pair<int,pair<int,int> > > pq;
  pq.push({0, {A, M}});

  while(pq.size()){
    auto p = pq.top(); pq.pop();

    int cost = p.first;
    int pos = p.second.first;
    int rest = p.second.second;
    
    if(visited[pos][rest]) continue;
    visited[pos][rest] = true;
    costMemo[pos][rest] = -cost;
    
    if(pos == H){
      printf("%d\n", -cost);
      return true;
    }

    if(freezer[pos] && rest < M)
      pq.push({cost - 1, {pos, rest+1}});

    for(int i=0;i<way[pos].size();i++){
      if(way[pos][i].second <= rest && !visited[way[pos][i].first][rest - way[pos][i].second])
        pq.push({cost - way[pos][i].second, {way[pos][i].first, rest - way[pos][i].second}});
    }
  }

  puts("Help!");
  
  return true;
}

int main(){
  while(solve());
  return 0;
}



Measured memory_bytes: 6448
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>
#include <iterator>
#include <functional>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin>>N;
  vector<ll>H(N);
  REP(i,N)cin>>H[i];
  H[0]--;
  bool ans=true;
  FOR(i,1,N){
    if(H[i-1]>H[i]){
      ans=false;
    }else if(H[i-1]<H[i]){
      H[i]--;
    }
  }
  cout<<(ans?"Yes":"No")<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main(){
int w, h, x, y, r;
int flg = 0;
scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);
if(x - r < 0)flg = 1;
if(x + r > w)flg = 1;
if(y - r < 0)flg = 1;
if(y + r > h)flg = 1;
if(flg == 0)printf("Yes\n");
else printf("No\n");
return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <cctype>

int main() {
  const int N = 26; // number of alphabetical
  int a[N] = {};
  std::string str;

  while(std::getline(std::cin, str)) {
    for(int i = 0; str[i] != '\0'; ++i) {
      if(isupper(str[i])) str[i] = tolower(str[i]);
      int ch = str[i] - 'a';
      if(0 <= ch && ch < N) {
        a[ch]++;
      }
    }
  }

  for(int i = 0; i < N; ++i) {
    char c = i + 'a';
    std::cout << c << " : " << a[i] << std::endl;
  }

  return 0;
}

Measured memory_bytes: 3152
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll n,k;

int main(){
	cin >> n >> k;
	ll ans = 0;
	FOR(i,1,n+1){
		ans += max((ll)0,(n/i)*(i-k)) + max((ll)0,(n%i+1)-k);
	}
	if(k == 0)ans-=n;
	cout << ans << endl;
}

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

int main(){
    string s = "abcdefghijklmnopqrstuvwxyz";
    string t;
    cin>>t;
    if(t[0]=='z'){cout<<'a'; return 0;}
    for(int i=0;i<32;i++){
        if(t[0]==s[i]){cout<<s[i+1]; return 0;}
    }
    return 0;
}


Measured memory_bytes: 3532
#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 H, W;
	cin >> H >> W;
    vector<string> S(H);
    rep(i, H) cin >> S[i];
    vector<vector<int>> cnt(H, vector<int>(W));
    rep(i, H) {
        vector<int> done(W);
        rep(j, W) {
            if (S[i][j] == '#') continue;
            if (done[j]) continue;
            int l = 0;
            while (j+l < W) {
                if (S[i][j+l] == '#') break;
                ++l;
            } 
            rep(k,l) {
                cnt[i][j+k] += l;
                done[j+k] = 1;
            }
        }
    }
    rep(j, W) {
        vector<int> done(H);
        rep(i, H) {
            if (S[i][j] == '#') continue;
            if (done[i]) continue;
            int l = 0;
            while (i+l < H) {
                if (S[i+l][j] == '#') break;
                ++l;
            } 
            rep(k,l) {
                cnt[i+k][j] += l;
                done[i+k] = 1;
            }
        }
    }
    int ans = 0;
    rep(i,H)rep(j,W) ans = max(ans, cnt[i][j]-1);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 20096
/* author: Tarek */ 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int n;
cin>>n;
string s,t;
cin>>s>>t;
for(int i=0;i<n;i++){
   cout<<s[i]<<t[i];
}
cout<<endl;
return 0;
}



Measured memory_bytes: 256