akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<long long> A(n);
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += A[i] / 2;
		A[i] %= 2;
		if (A[i] > 0 && i < n-1 && A[i+1] > 0) {
			A[i]--;
			A[i+1]--;
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
n = int(input())
dp = [2]*n
dp[0] = 1
mod = 10**9+7
an = [int(i) for i in input().split()]

if n % 2 == 1:
  for i in an:
    if i % 2 == 1 or dp[i] == 0:
      print(0)
      exit()
    else:
      dp[i] -= 1
  print(2**((n-1)//2)%mod)
else:
  for i in an:
    if i % 2 == 0 or dp[i] == 0:
      print(0)
      exit()
    else:
      dp[i] -= 1
  print(2**(n//2)%mod)

Measured memory_bytes: 14580
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N;
long long int b[100000];
long long int sum[100000];
int ans=1;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)cin >> b[i];
	stable_sort(b, b + N);
	sum[0] = b[0];
	for (int i = 1; i < N; i++) {
		sum[i] = sum[i - 1] + b[i];
	}
	for (int i = N-2; i >= 0; i--) {
		if (sum[i] * 2 >= b[i+1])ans++;
		else break;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = LLONG_MAX;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    string S, x = "keyence";
    cin >> S;
    int N = S.size(), M = x.size();
    int s = 0, e = 0;
    while(s < N && s < M && S[s] == x[s]) s++;
    while(e < N && e < M && S[N-1-e] == x[M-1-e]) e++;
    if(s+e < M) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse4")
#pragma GCC optimize("unroll-loops")
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
using namespace std;
int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
	int n,x=0,y=0,t=0,x2,y2,t2;
	cin>>n;
	while(n--){
		cin>>t2>>x2>>y2;
		int d=abs(x2-x)+abs(y2-y);
		if(d>t2-t or (t2-t-d)%2){
			cout<<"No";
			return 0;
		}
		t=t2,x=x2,y=y2;
	}
	cout<<"Yes";
    return 0;
}

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

#include <algorithm>
#include <queue>
#include <climits>

using namespace std;

int i,j,n;
string str;

#define V 100000

vector<int> edge[V];

int min0[V],mine[V];



void dfs0(int s,int d){
    if(min0[s] != INT_MAX) return;
    min0[s] = d;
    for(int i = 0;i < edge[s].size();i++){
        dfs0(edge[s][i],d+1);
    }
}

void dfse(int s,int d){
    if(mine[s] != INT_MAX) return;
    mine[s] = d;
    for(int i = 0;i < edge[s].size();i++){
        dfse(edge[s][i],d+1);
    }
}

int main(){
    cin >> n;
    for(i = 0;i < n-1;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    for(i = 0;i < n;i++){
        min0[i] = INT_MAX;
        mine[i] = INT_MAX;
    }
    dfs0(0,0);
    dfse(n-1,0);
    int count0 = 0,counte = 0;
    for(i = 0;i < n;i++){
        if(min0[i]>mine[i]){
            counte++;
        }
        else{
            count0++;
        }
    }
    if(count0 > counte){
        cout << "Fennec" << endl;
    }
    else{
        cout << "Snuke" << endl;
    }
}


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

int n;
string s;

int main() {
    cin >> n >> s;
    int red = 0;
    for(auto x: s)
        if(x == 'R') red++;

    int ans = 0;
    for(int i = 0; i < red; i++)
        if(s[i] != 'R') ans++;
    cout << ans;
}


Measured memory_bytes: 3752
#include <cstdio>
#include <algorithm>
int N, M, X, Y, a[100][100], sx[100][100], sy[100][100], f[100][100][100][100];
inline int SY(int x, int l, int r)
{
	int L = std::max(l, r - Y), R = std::min(r, M - 1 - Y + l);
	return L > R ? 0 : sy[x][R] - (L ? sy[x][L - 1] : 0);
}
inline int SX(int y, int l, int r)
{
	int L = std::max(l, r - X), R = std::min(r, N - 1 - X + l);
	return L > R ? 0 : sx[R][y] - (L ? sx[L - 1][y] : 0);
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++)
	{
		static char _i[101];
		scanf("%s", _i);
		for (int j = 0; j < M; j++)
			if (_i[j] == 'E')
				X = i, Y = j;
			else if (_i[j] == 'o')
				a[i][j] = 1;
	}
	for (int i = 0; i < N; i++)
		std::copy(a[i], a[i] + M, sx[i]);
	for (int i = 1; i < N; i++)
		for (int j = 0; j < M; j++)
			sx[i][j] += sx[i - 1][j];
	for (int i = 0; i < N; i++)
		std::copy(a[i], a[i] + M, sy[i]);
	for (int i = 0; i < N; i++)
		for (int j = 1; j < M; j++)
			sy[i][j] += sy[i][j - 1];
	for (int i = 0; i <= X; i++)
		for (int j = N - 1; j >= X; j--)
			for (int k = 0; k <= Y; k++)
				for (int l = M - 1; l >= Y; l--)
				{
					if (i > j - X)
						f[i][j][k][l] = std::max(f[i][j][k][l], f[i - 1][j][k][l] + SY(i - 1, k, l));
					if (j < N - 1 - X + i)
						f[i][j][k][l] = std::max(f[i][j][k][l], f[i][j + 1][k][l] + SY(j + 1, k, l));
					if (k > l - Y)
						f[i][j][k][l] = std::max(f[i][j][k][l], f[i][j][k - 1][l] + SX(k - 1, i, j));
					if (l < M - 1 - Y + k)
						f[i][j][k][l] = std::max(f[i][j][k][l], f[i][j][k][l + 1] + SX(l + 1, i, j));
				}
	printf("%d\n", f[X][X][Y][Y]);
	return 0;
}


Measured memory_bytes: 225536
#include<stdio.h>

int main(){
    int n;
    int a[100000+5], b[100000+5];
    long cnt=0;

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

    for(int i=0; i<n; i++){
        scanf("%d", &b[i]);
    }
    for(int i=0; i<n; i++){
        if(a[i]-b[i]>=0){
            cnt+=b[i];
            a[i]-=b[i];
            b[i]=0;
        }else{
            cnt+=a[i];
            b[i]-=a[i];
            a[i]=0;
            if(a[i+1]-b[i]>=0){
                cnt+=b[i];
                a[i+1]-=b[i];
                b[i]=0;
            }else{
                cnt+=a[i+1];
                b[i]-=a[i+1];
                a[i+1]=0;
            }
        }
    }
    printf("%ld\n", cnt);
    return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using  namespace std;
int main(){
	int n;cin>>n;n--;vector<int>v(n+1);
	for (int x=0;x<n;x++){
		cin>>v[x];
	}
	int a=v[0];
	int sum=a;
	for (int x=1;x<n;x++){
		sum+=min(a,v[x]);
		a=v[x];
	}
	sum+=a;
	cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 10000000000000000
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;

bool check(ll mid, ll arr[], ll n, ll m)
{
    ll cnt = 0;
    for(ll i=n-1;i>-1;i--)
    {
        if(2*arr[i]>=mid)
            cnt++;
        auto ind = lower_bound(arr,arr+i,mid-arr[i]) - arr;
        if(ind == i)
            continue;
        ll siz = i-1-ind+1;
        cnt+=2*siz;
    }
    
    //cout<<"for "<<mid<<" = "<<cnt<<"\n";
    
    return cnt>=m;
}

int main()
{
   FAST/**/
   
   ll n,m;
   cin>>n>>m;
   
   ll arr[n];
   rep(n)
        cin>>arr[i];
   
   sort(arr,arr+n);
   
   ll start = 0;
   ll end = inf;
   
   while(end - start > 1)
   {
       ll mid = (start + end)/2;
       bool temp = check(mid,arr,n,m);
       if(temp)
            start = mid;
       else end = mid - 1;        
   }
   
   ll mid;
   
   bool temp = check(end,arr,n,m);
   if(temp)
        mid = end;
   else mid = start; 
   
   //cout<<"mid = "<<mid<<"\n";
   
   ll ans = 0;
   ll pref[n];
   pref[0] = arr[0];
   rep(n-1)
        pref[i+1] = pref[i] + arr[i+1];
   ll rem = m;        
   for(ll i=n-1;i>-1;i--)
   {
        if(2*arr[i] > mid)
            ans+=2*arr[i], rem--;
        auto ind = lower_bound(arr,arr+i,mid-arr[i]+1) - arr;
        if(ind == i)
            continue;
            
        ll st = ind;
        ll en = i-1;
        
        rem-=(en-st+1)*2;
        
        ans+=(en-st+1)*arr[i]*2;
        
        if(st == 0)
            ans+=2*pref[en];
        else ans+=2*pref[en]-2*pref[st-1];    
   }
   
   //cout<<"till mid = "<<ans<<"\n";
   
   map<ll,ll> ma;
   rep(n)
        ma[arr[i]]++;
   rep(n)
   {
       if(rem == 0)
            break;
       if(2*arr[i] == mid)
       {
           rem--;
           ans+=mid;
       }
       if(rem == 0)
            break;
       ma[arr[i]]--;
       ll siz = min(ma[mid-arr[i]],rem);
       rem-=siz;
       ans+=mid*siz;
       ma[arr[i]]++;
   }
   
   cout<<ans;
   
   return 0;        
}  
   

Measured memory_bytes: 9472
# AtCoDeer君は、赤、緑、青色のカードを持っています。
# それぞれのカードには1以上9以下の整数が書かれており、赤色のカードにはr、緑色のカードにはg、青色のカードにはbが書かれています。
# 3つのカードを左から順に赤、緑、青色の順に並べ、左から整数を読んだときにこれが4の倍数であるか判定しなさい。

r,g,b = map(int,input().split())

if 1 <= r <=9 and 1 <= g <=9 and 1 <= b <=9 and (100 * r + 10 * g + b) %   4 == 0: # rを100倍、gを10倍にして、それぞれ100の位、10の位とする。
    print('YES')

else:
    print('NO')

Measured memory_bytes: 9176
n,k=map(int, input().split())
ans=0
for i in range(k,n+2):
  smax=i*((n-i+1)+n)//2
  smin=i*(0+(i-1))//2
  ans+=(smax-smin+1)%(10**9+7)
print(ans%(10**9+7))

Measured memory_bytes: 9188
// Package main provides
//
// File:  b.go
// Author: ymiyamoto
//
// Created on Sat Jan  5 17:05:02 2019
//
package main

import "fmt"

var dp []int

func lucas(n int) int {
	if dp[n] == 0 {
		dp[n] = lucas(n-1) + lucas(n-2)
	}

	return dp[n]
}

func main() {
	var N int
	fmt.Scan(&N)

	dp = make([]int, 87)
	dp[0] = 2
	dp[1] = 1

	fmt.Println(lucas(N))
}


Measured memory_bytes: 512
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;


void Main(){
    ll N;
    sll(N);
    vector<ll> as(N,0);
    priority_queue<pll, vector<pll>> pq;
    rep(i, N){
        sll(as[i]);
        pq.push(make_pair(as[i], 2));
    }

    auto top = pq.top();pq.pop();
    // cout << top.first <<endl;
    top.second = 1;
    pq.push(top);
    ll ans = 0;
    rep(i, N-1){
        auto top = pq.top();pq.pop();
        -- top.second;
        ans += top.first;
        if(top.second>0){
            pq.push(top);
        }
    }

    cout << ans <<endl;


}

int main(){
    Main();
}

Measured memory_bytes: 8656
import scala.io.StdIn.readLine

object Main extends App {

  val alpha = Array.fill[Int](128)(0)

  def count():Unit = {
    val l = readLine
    if(l != null) {
      l.trim.foreach { s => alpha(s.toLower) += 1 }
      count()
    }
  }

  count()
  for(i <- 'a' to 'z')
    println(i + " : " + alpha(i))
}

Measured memory_bytes: 44752
#include <iostream>

using namespace std;
int main(void) {
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	int res = 0;
	if(a<=b) res += a;
	else res += b;
	if(c<=d) res += c;
	else res += d;
	cout << res << endl;
	return 0;
}

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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    print(min({abs(a+b),abs(a+c),abs(b+c)}));

}

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) cin >> a[i];
  int res = 1;
  int increasing = 0;
  rep(i, N - 1) {
    int s = a[i] - a[i + 1];
    if(increasing == 0) {
      if(s > 0)
        increasing = 1;
      else if(s < 0)
        increasing = -1;
    } else if((increasing == 1 && s < 0) || (increasing == -1 && s > 0)) {
      res++;
      increasing = 0;
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 640
(function(input) {
  var p = input.replace(/\n$/, '').split('\n');
  var n = p.length;
  for (var i = 0; i < n; i++) {
    var a = p.shift().split('');
    console.log(count(a));
  }
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

function count(a) {
  var l = ['I', 'V', 'X', 'L', 'C', 'D', 'M'];
  var c = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000};
  var s = 0;
  for (var i = 0; i < a.length; i++) {
    if (i < a.length - 1 && l.indexOf(a[i]) < l.indexOf(a[i + 1])) {
      s -= c[a[i]];
    } else {
      s += c[a[i]];
    }
  }
  return s;
}

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


using namespace std;

int N;
vector<int>H;


int main()
{

	bool ans = true;

	cin >> N;
	H = vector<int>(N);
	for (int i = 0; i < N; i++) {
		cin >> H.at(i);
	}

	int min = H.at(0)-1;
	if (min < 1) { min = 1; }

	for (int i = 1; i < N; i++) {
		if (H.at(i) < min) {
			ans = false;
			break;
		}

		if (H.at(i) > min) {
			min = H.at(i) - 1;
		}

	}

	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}


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

void Main()
{
  ll n; cin >> n;
  vector<ll> a(n);
  bool oneFound = false;
  rep(i,n) {
    cin >> a[i];
    if (a[i] == (ll)1) oneFound = true;
  }
  ll foundNum = 1;
  rep(i,n) {
    if (a[i] == foundNum) foundNum++;
  }
  if (!oneFound) {cout << -1 << endl; return;}
  else cout << n-(foundNum-1) << endl;
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 4756
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int
#define pb push_back 
#define mp make_pair 
#define pii pair <int , int > 
#define pll pair < ll , ll >
vector < int > adj[200005] ;
ll vis[200005] , val[200005] ;
void dfs(int i , ll v){
    vis[i] = 1 ;
    val[i] = v ;
    for(auto it : adj[i]){
        if(!vis[it]){
            dfs(it , val[it] + v) ;
        }
    }
}
int main(){
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
    int n , tt ;
    cin >> n >> tt ;
    for(int i = 0 ; i < n - 1 ; i++){
        int a , b ;
        cin >> a >> b ;
        adj[a].pb(b) ;
        adj[b].pb(a) ;
    }
    while(tt--){
        ll p , d ;
        cin >> p >> d ;
        val[p] += d ;
    }
    dfs(1 , val[1]) ;
    for(int i = 1 ; i <= n ; i++) cout << val[i] << " " ;
}


Measured memory_bytes: 22784
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	printf("%d",a[n/2+1]-a[n/2]);
}

Measured memory_bytes: 640
(let ((p 1000000007))
  (defun mod+ (a b)
    (mod (+ a b) p))
  (defun mod* (a b)
    (mod (* a b) p))
  (defun mod_expt (a z)
    (loop :with ans := 1
          :with pow := a
          :while (> z 0)
          :do (multiple-value-bind (x y) (floor z 2)
                (setf z x)
                (if (= y 1) (setf ans (mod* ans pow)))
                (setf pow (mod* pow pow)))
          :finally (return ans)))
  (defun mod_inv (a)
    (mod_expt a (- p 2))))


(let ((n (read))
      (a (read))
      (b (read))
      (ac 1)
      (bc 1)
      (ans 0))
  (loop :with x := 1
        :for i :from 1 :to (max a b)
        :do (setf x (mod* x (mod* (mod_inv i) (- n i -1))))
        :if (= a i)
        :do (setf ac x)
        :if (= b i)
        :do (setf bc x))
  (setf ans (mod+ ans (mod_expt 2 n)))
  (setf ans (mod+ ans (- 1)))
  (setf ans (mod+ ans (- ac)))
  (setf ans (mod+ ans (- bc)))
  (format t "~A~%" ans))



Measured memory_bytes: 24488
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int w, h, n;
    cin >> w >> h >> n;
    int x_mn = 0, x_mx = w, y_mn = 0, y_mx = h;
    for (int i = 0; i < n; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        if(a == 1) {
            x_mn = max(x, x_mn);
        } else if (a == 2) {
            x_mx = min(x, x_mx);
        } else if (a == 3) {
            y_mn = max(y_mn, y);
        } else {
            y_mx = min(y_mx, y);
        }
    }
    if (x_mn < x_mx && y_mn < y_mx) {
        cout << (y_mx - y_mn) * (x_mx - x_mn) << "\n";
    } else {
        cout << "0\n";
    }
}

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


int main(){
	int S,h,m,s;
	cin >> S;
	h = S/3600;
	m = (S - h * 3600) / 60;
	s = S - (h * 3600 + m * 60);
	cout << h << ':' << m << ':' << s << endl;
	return 0;
}


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

int main(int argc, const char * argv[]) {



    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    /////////////////////
    char c;

    cin>>c;

    if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
        cout<<"vowel"<<endl;
    }
    else{
        cout<<"consonant"<<endl;
    }
}

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

int main(){
  int N;
  cin >> N;
  vector<int> A(N, 0);
  int M = 0;
  for (int i=0;i<N;i++){
    cin >> A[i];
    M = max(M, A[i]);
  }
  vector<bool> X(M+1, true);
  map<int, int> E;
  for (int i: A){
    if (E.count(i)){
      E[i] += 1;
      X[i] = 0;
    }
    else{
      E[i] = 1;
    }
  }
  set<int> F;
  for (pair<int, int> i: E){
    if (i.second == 1){
      F.insert(i.first);
    }
  }
  for (int i: A){
    for (int j=2;j<=M/i;j++){
      X[i*j] = 0;
    }
  }
  int S = 0;
  for (int i: F){
    S += X[i];
  }
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 22632
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list ?sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list ?sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list ?sep conv);
  arr

let atoi c = Char.code c - Char.code '0'

let rec powerset e =
  match Enum.get e with
  | None -> Enum.singleton @@ Enum.empty ()
  | Some v ->
    let f = powerset e in
    let g = Enum.clone f in
    EnumL.map f ~f:(fun x -> let y = Enum.clone x in push y v; y)
    |>  Enum.append g

let permutations l =
  let rec aux l =
    let rec interleave x = function
      | [] -> [[x]]
      | (hd::tl) as lst ->
        (x::lst) ::
        (ListL.map ~f:(List.cons hd)  @@ interleave x tl)
    in
    match l with
    | [] -> [[]]
    | hd::tl -> List.concat @@ List.map (interleave hd) @@ aux tl in
  let l = List.sort (List.compare Int.compare) @@ aux @@ List.of_enum l in
  List.enum % ListL.map ~f:List.enum @@ l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let n = scan "%d" id

let rec divs n i =
  if n = 1 then []
  else if n mod i = 0 then i :: divs (n/i) i
  else if n < i*i then [n]
  else divs n (succ i)

let rec shrink acc = function
  | [] -> acc
  | a::rest ->
    begin
      match acc with
      | (b,n)::res when b = a -> shrink ((b,succ n)::res) rest
      | _ -> shrink ((a,1)::acc) rest
    end

exception Found of int

let () =
  shrink [] @@ divs n 2
  |> ListL.map ~f:(fun (_,n)->
      try ListL.iter (0 ++^ 50) ~f:(fun i ->
          if i * (i+1)/2 <= n && n < (i+1)*(i+2)/2 then raise (Found i)); 0
      with
      | Found i ->  i)
  |> List.sum
  |> Printf.printf "%d\n"


Measured memory_bytes: 5416
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

typedef long long ll;

int main()
{
  ll n;
  std::cin >> n;

  std::vector< ll > va(n, 0);
  std::vector< ll > vb(n, 0);
  for (ll i = 0; i < n; i++) {
    std::cin >> va[i] >> vb[i];
  }

  std::reverse(va.begin(), va.end());
  std::reverse(vb.begin(), vb.end());

  ll count = 0;
  for (ll i = 0; i < n; i++) {
    va[i] += count;
    if (va[i] % vb[i] != 0) {
      count += vb[i] - (va[i] % vb[i]);
    }
    //std::cout << count << " " << va[i] << " " << vb[i] << std::endl;
  }

  std::cout << count << std::endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = (int)s.size();
    if(s[n-1] != 's'){
        s += 's';
    }
    else{
        s += 'e';
        s += 's';
    }
    cout << s << "\n";
    return 0;
}

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

int main()
{
  int n;
  while (cin >> n, n){
    int cnt = 0;
    while (n != 1){
      if (n % 2 == 0) n /= 2;
      else n = n * 3 + 1;
      cnt++;
    }
    cout << cnt << endl;
  }
  return (0);
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i,ans=0;
	string s;
	cin>>n>>s;
	for(i=1;i<n;++i){
    	if(s.at(i)!=s.at(i-1)){
        	ans++;
        }
    }
	cout<<ans+1<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  long long  n;
  cin >> n;
  long long a[n];
  for (int i =0; i<n; i++) cin >> a[i];
  sort(a,a+n);
  long  max = a[n-1];
  long double  dif = 1000000000;
  long double  target  = max/2.0;
  long  ans = a[0];
  for (int i =0; i<n; i++){
    long double c = abs(a[i]-target);
    if(dif> c)  ans = a[i];
    dif = min(dif,c);
  }
    
  
  cout << max <<" "<< ans  << endl;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

				var inputArray = retreiveLongArray();
			var inputCount = 2;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long N = inputArray[0];
			long M = inputArray[1];

			//エッジケース対応
			if (N==1) {
				Console.WriteLine(M);
				return;
			}
			var saidaikouho = M / N;

			//最大の公約数は(M/N) ※割り切れる場合
			long max = 1;
			for (int i = 1; i <= saidaikouho; i++) {
				if(M %i == 0) {
					max = i;
				}
			}

			//答えの出力
			var ans = max;
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}


Measured memory_bytes: 13396
N,K = map(int,input().split())
d = []
A = []
count = [0]*N
count.insert(0,'X')

for i in range(K):
	d.append(input())
	A.append(list(map(int,input().split())))
	
for s in range(len(A)):
	for t in range(len(A[s])):
		count[A[s][t]] += 1

print(count.count(0))


Measured memory_bytes: 9188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication83
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = new int[2];
            a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine((a[0] - 1) * (a[1] - 1));
        }
    }
}


Measured memory_bytes: 13268
n = int(input())
l = [[0, 0, 0] for _ in range(n)]
for i in range(n):
    at, bt, ct = list(map(int, input().split()))
    l[i] = [at, bt, ct]
m = [[0,0,0] for _ in range(n)]
m[0] = l[0]
for i in range(1,n):
    m[i][0] = l[i][0] + max(m[i-1][1], m[i-1][2])
    m[i][1] = l[i][1] + max(m[i-1][0], m[i-1][2])
    m[i][2] = l[i][2] + max(m[i-1][0], m[i-1][1])
print(max(m[-1]))



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

int main(){
  long N,K;
  long t;
  cin >> N >> K;

 
  if(N > K){
    N %= K;
  }

  while(true){
    t = abs(N-K);
    if(abs(t-K) >= abs(N-K)){
      break;
    }
    N = t;
  }

  cout << t << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

#define MAX_N (200000L)
#define MAX_C (200000L)
#define NUM_MOD (1000000007L)

using namespace std;

int main(int argc, char *argv[]) {
  // read inputs
  long N, cs[MAX_N];
  scanf("%ld", &N);
  for (long i = 0; i < N; i++) {
    scanf("%ld", &cs[i]);
  }

  // create list of positions each color appears
  vector<vector<long>> idxss(MAX_C, vector<long>());
  for (long i = 0; i < N; i++) {
    const long c = cs[i];
    idxss[c].push_back(i);
  }

  // solve dp
  long dps[MAX_N + 1];
  // initialize
  dps[N] = 1;
  // update
  for (long i = N - 1; i >= 0; i--) {
    const long c = cs[i];
    vector<long> &idxs = idxss[c];
    const long j_next = upper_bound(idxs.begin(), idxs.end(), i) - idxs.begin();
    long dp = 0;
    dp = (dp + dps[i + 1]) % NUM_MOD;
    if (j_next < idxs.size()) {
      const long idx_next = idxs[j_next];
      if (idx_next > i + 1 && idx_next < N) {
        // printf("i = %ld, c = %ld, idx_next = %ld\n", i, c, idx_next);
        dp = (dp + dps[idx_next]) % NUM_MOD;
      }
    }
    dps[i] = dp;
  }
  printf("%ld\n", dps[0]);

  return 0;
}


Measured memory_bytes: 14336
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <stdio.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);++i)
#define urep(i,a,n) for(ll i = (a);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define INF 1e18
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N,M,X,Y,A,B,C,D,Q,K,R,W,H,P,L,G;
ll ans;
string S,T;
ll y[101010];
ll a[101010];
ll k[101010];
ll b[101010];
ll t[101010];
ll p[101010];
ll n[101010];
ll l[101010];
ll r[101010];
ll s[1010][1010];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
struct Edge{
	ll to,cost;
	 Edge(ll to, ll cost) : to(to), cost(cost) {}
};
typedef vector<vector<Edge> > AdjList;
AdjList graph;
vector<ll> dist;

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	vector<ll> size;
    UnionFind(ll N) : par(N),size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
		for(ll i = 0; i < N; i++) size[i] = 1;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
	ll GetSize(ll x){
		return size[root(x)];
	}

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		size[ry]+=size[rx];

    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};
ll sr,sc;
int main() {
    ans=0;
    cin>>N>>M;
    rep(i,0,M){
        cin>>k[i];
        rep(j,0,k[i]){
            cin>>s[i][j];
        }
    }
    rep(i,0,M){
        cin>>p[i];
    }
    rep(i,0,pow(2,N)){
        bitset<10> bs(i);
        bool flag = true;
        rep(j,0,M){
            ll count=0;
            rep(l,0,k[j]){
                if(bs[s[j][l]-1]){
                    count++;
                }
            }
            if(count%2!=p[j]){
                flag=false;
                break;
            }
        }
        if(flag){
            ans++;
        }
    }
    cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4352
//code by lynmisakura.wish to be accepted
/****************************/
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
#include<set>
#include<bitset>
using namespace std;
/***************************/
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<pair<int,int>> vpi;
 
//const long long Mod = 998244353;
const long long mod = 1000000007;
const long long INF = 10000000000000;
 
#define itn int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define all(x) (x).begin(),(x).end()
#define Rep(n) for(int i = 0;i < n;i++)
#define rep(i,n) for(int i = 0;i < n;i++)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
 
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll qp(ll a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
ll qp(ll a, ll b, int mo) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
 
#define _GLIBCXX_DEBUG
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//素因数分解 O(√n)
map<int,int>prime_factor(int n){
    map<int,int> res;
    for(int i = 2;i * i <= n;i++){
        while(n % i == 0){
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}

#define MAX_P 200010
class combination{
public:
    ll fact[MAX_P]; // n! mod pのテーブル(O(p))
    ll p;
    // factテーブルを初期化する
    combination(ll x = 1000000007){  // x : 余り(1e9 + 7など)
        p = x;
        fact[0] = 1;
        for(ll i = 1;i < MAX_P;i++){
            fact[i] = fact[i - 1] * i % p;  
        }
    }
    //拡張ユークリッドの互除法
    ll extgcd(ll a,ll b,ll& x,ll& y){
        ll d = a;
        if(b != 0){
            d = extgcd(b,a%b,y,x);
            y -= (a / b) * x;
        }else{
            x = 1; y = 0;
        }
        return d;
    }
    //mod上の逆元
    ll mod_inverse(ll a,ll m){
        ll x,y;
        extgcd(a,m,x,y); //extgcdが必要
        return (m + x % m) % m;
    }
    //n! = a p^eとしたときの a mod pを求める O(log_p a)
    ll mod_fact(ll n,ll p,ll& e){
        e = 0;
        if(n == 0) return 1;

        //pの倍数の部分を計算
        ll res = mod_fact(n / p,p,e);
        e += n / p;

        //(p - 1)!≡-1なので、(p-1)!^(n/p)はn/pの偶奇だけで計算できる
        if(n / p % 2 != 0) return res * (p - fact[n % p]) % p;
        return res * fact[n % p] % p;
    }

    //mod p 上の二項係数
    ll mod_comb(ll n,ll k){
        if(n < 0 || k < 0|| n < k) return 0;
        ll e1,e2,e3;
        ll a1 = mod_fact(n,p,e1),a2 = mod_fact(k,p,e2),a3 = mod_fact(n - k,p,e3);
        if(e1 > e2 + e3) return 0;
        return a1 * mod_inverse(a2 * a3 % p,p) % p;
    }
};
int main(void){
	combination c(mod);
	ll n,m;cin >> n >> m;
	
	auto mp = prime_factor(m);
	ll ans = 1;
	
	for(auto i : mp){
		ans *= c.mod_comb(n+i.second-1,i.second);
		ans %= mod;
	}
	
	cout << ans << endl;
	return 0;
}

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



Measured memory_bytes: 2044
#include <set>
#include <cassert>
#include <cmath>
#include <iostream>
using namespace std;

void bruteforce(int N, int D, int *d, bool *ans) {
    int p[N+1];
    p[0] = D;
    for (int i = 0, pos = D; i < N; i++) {
        pos = min(pos, abs(pos - d[i]));
        p[i+1] = pos;
    }
    if (p[N] != 0) {
        fill(ans, ans+N, true);
        return;
    }
    fill(ans, ans+N, false);
    set<int> S;
    S.insert(0);
    for (int i = N-1; i >= 0; i--) {
        for (int x = p[i]; x > 0; x--)
            if (S.find(x) == S.end()) {
                ans[i] = true;
                break;
            }
        set<int> temp;
        for (int p = 0; p <= d[i]; p++)
            if (S.find(min(p, d[i] - p)) != S.end()) temp.insert(p);
        for (int x : S) temp.insert(x + d[i]);
        S.swap(temp);
        // cerr << "i = " << i << "; "; for (int x : S) cerr << x << " "; cerr << endl;
    }
}

int main() {
    int N, D; cin >> N >> D;
    int d[N]; for (int i = 0; i < N; i++) cin >> d[i];
    bool ans[N];
    int p[N+1], s[N+1];
    p[0] = D;
    for (int i = 0, pos = D; i < N; i++) {
        pos = min(pos, abs(pos - d[i]));
        p[i+1] = pos;
    }
    // for (int i = 0; i <= N; i++) cerr << p[i] << endl;
    if (p[N] == 0) {
        s[N] = 0;
        for (int i = N-1; i >= 0; i--) {
            ans[i] = p[i] > s[i+1];
            s[i] = max((d[i] + 1) / 2, d[i] - s[i+1]) - min(d[i] / 2, s[i+1]) <= 1 ? d[i] + s[i+1] : min(d[i] / 2, s[i+1]);
            // cerr << i << " " << s[i] << endl;
        }
    } else {
        fill(ans, ans+N, true);
    }

    // bool ans2[N];
    // bruteforce(N, D, d, ans2);
    // for (int i = 0; i < N; i++)
    //     if (ans[i] != ans2[i]) {
    //         cerr << "wrong answer on i = " << i << "; " << ans[i] << " != " << ans2[i] << endl;
    //     }

    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << (ans[x-1] ? "YES\n" : "NO\n");
    }
}


Measured memory_bytes: 9392
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<deque>
#include<cctype>
#include<cstring>
using namespace std;
int v,p,n,ans;
long long m,a[100050],a1;
int main()
{
	scanf("%d %lld %d %d",&n,&m,&v,&p);
	ans=p;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);a[i]=-a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=-a[i];
	}
	for(int i=p+1;i<=n;i++)
	{
		if(a[i]+m<a[p])break;
		if(v<=p+n-i)++ans;
		else if(((v-p-n+i)*m-a1-1)/(i-p)+1+a[p]<=a[i]+m)++ans;
		a1+=a[p]-a[i];
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 4660
#include<stdio.h>
int main(void){
	int i;
	int n,sum=0;
//	printf("aa%d\n",sum);
	for(i=0;i<4;i++){
		scanf("%d",&n);
		sum=sum+n;
	//	printf("aa%d\n",sum);
	}
	printf("%d\n",sum/60);
	sum-=sum/60*60;
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)

long long gcd(long long int a,long long int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

long long  lcm(long long int a,long long int b)
{
   return a * b / gcd(a, b);
}
int main(){
  long long int a,b,c,d;cin>>a>>b>>c;
  if(fabs(a-b)>fabs(a-c))cout<<"B";
  else cout<<"A";
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main(){
    int n; cin >> n;
    vector<int> data(n); rep(i,n) cin >> data[i];

    vector<int> ans(1,-data[0]);

    for(int i = 1; i < n; i++){
        int k = upper_bound(all(ans),-data[i]) - ans.begin();
        if(k == ans.size()) ans.push_back(-data[i]);
        else ans[k] = -data[i];
    }
    cout << ans.size() << endl;
}

Measured memory_bytes: 4204
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
const ll INF = 1LL<<60;
const int INT_INF = 1e9;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
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; }
using namespace std;

struct Edge{
    int u;
    int v;
    int cost;

    Edge(int _u, int _v, int c) {
        u = _u;
        v = _v;
        cost = c;
    }
};

vector<Edge> adj;
int dist[110];

int main() {
    int n; cin >> n;
    rep(i, n) {
        int u, k; cin >> u >> k;
        rep(j, k) {
            int v, c; cin >> v >> c;
            adj.emplace_back(Edge(u, v, c));
        }
    }

    // 初期化
    rep(i, n) {
        dist[i] = (i == 0) ? 0 : INT_INF;
    }

    for (int i = 1; i < n; i++) {
        for (auto edge: adj) {
            int u = edge.u;
            int v = edge.v;
            int c = edge.cost;
            // cout << '(' << u << ',' << v << ',' << c << ')' << endl;
            if (dist[u] != INT_INF && dist[v] > dist[u] + c) {
                dist[v] = dist[u] + c;
            }
        }
    }

    rep(i, n) {
        cout << i << ' ' << dist[i] << endl;
    }
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1001001001;
const int MOD = 1000000007;
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 (b<a) {a=b; return 1;} return 0;}

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...)
#define print(...)
#endif

int main() {
    int n, c; cin >> n >> c;
    vector<vector<int>> vec(c, vector<int>(c));
    rep(i, c) rep(j, c) cin >> vec[i][j];
    vector<vector<int>> mat(n, vector<int>(n));
    rep(i, n) rep(j, n) {cin >> mat[i][j]; mat[i][j]--;}
    vector<map<int, int>> mp(3);
    rep(i, n) rep(j, n) {
        mp[(i+j)%3][mat[i][j]]++;
    }

    ll ans = LLONG_MAX;
    rep(i, c) rep(j, c) rep(k, c) {
        if (i==j || j==k || i==k) continue;
        ll tot = 0;
        for(const auto& m: mp[0]) tot += vec[m.fi][i]*m.se;
        for(const auto& m: mp[1]) tot += vec[m.fi][j]*m.se;
        for(const auto& m: mp[2]) tot += vec[m.fi][k]*m.se;
        debug(i, j, k, tot);
        chmin(ans, tot);
    }

    cout << ans << endl;
}

Measured memory_bytes: 1280
#define _USE_MATH_DEFINES // for C++  
#include "bits/stdc++.h"
using LL = long long;
using ULL = unsigned long long;
#define NUM 1000000007

using namespace std;

int main()
{
    int a = 10000;
    int b = 5000;
    int c = 1000;
    int n, y;
    cin >> n >> y;
    for (size_t i = 0; i <= n; i++)
    {
        for (size_t j = 0; j <= n - i; j++)
        {
            if (i * 10000 + j * 5000 + (n - i - j) * 1000 == y)
            {
                cout << i << " " << j << " " << (n - i - j) << endl;
                return 0;
            }
        }
    }
    cout << -1 << " " << -1 << " " << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	double min_v;
	
	while (cin >> min_v) {
		double crack_height = (min_v * min_v) / 19.6;
		int N = ceil( (crack_height)/5.0 ) + 1;
		cout << N << endl;
	}
		
	return 0;
}

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

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	ll N;
    cin>>N;
    ll ans = 0;
    ll a;
    rep(i,N){
        a = i+1;
        ans += (N-1)/a;
    }
    cout<<ans<<"\n";
	
	return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int k,n,ans = 987654321; cin>>k>>n;
	vector<int> val(n);
	for(int i=0;i<n;i++) cin>>val[i];
	sort(val.begin(),val.end());
	ans = min(ans,val.back() - val[0]);
	for(int i=0;i<n-1;i++){
		ans = min(ans,k - val[i+1] + val[i]);
	}
	cout<<ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>

using namespace std;

int main(){
    unsigned long long n;
    cin >> n;

    if(n == 1){
        cout << 1 << endl;
        return 0;
    }

    unsigned long long tmp = 2;
    long long ans = 1;

    while(tmp * 2 <= n){
        tmp = tmp * 2;
        ans += 1;
    }

    unsigned long long out = pow(double(2), double(ans + 1)) - 1;

    cout <<  out << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>

#define INC(i, a, b) for(int i = a; i < b; ++i)
#define DEC(i, a, b) for(int i = a; i > b; --i)
#define REP(i, n) INC(i, 0, n)

typedef unsigned int uint;
typedef unsigned long ul;
typedef long long  ll;
typedef unsigned long long ull;

void TFprint(bool b, std::string T, std::string F){
    if(b){
        std::cout << T << std::endl;
    }else{
        std::cout << F << std::endl;
    }
}

int simulation(std::string str, char c, int min){
    bool isSingleChar = true;
    uint len = str.length();
    int ret = 0;
    while(true){

        isSingleChar = true;

        REP(i, len){
            if(str.at(i) != c){
                isSingleChar = false;
                break;
            }
        }
        if(isSingleChar){
            break;
        }

        len--;
        REP(i, len){
            if(str.at(i + 1) == c){
                str.at(i) = c;
            }
        }
        //std::cout << str.substr(0, len) << std::endl;
        ret++;
        if(ret > min){
            ret = INT32_MAX;
            break;
        }
    }
    return ret;
}

int main(){
    std::string str;
    std::cin >> str;
    bool atoz[26] = {false};
    REP(i, str.length()){
        atoz[str.at(i) - 'a'] = true;
    }
    int min = INT32_MAX;
    char c;
    REP(i, 26){
        if(atoz[i]){
            int temp = simulation(str, i + 'a', min);
            if(min > temp){
                min = temp;
            }
        }
    }
    std::cout << min << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long int n;
   cin>>n;
   long long int a[n];
   long long int ans=0,ans1=pow(10,18);
   for(long int i=0;i<n;i++)
   {
      cin>>a[i];
      ans+=a[i];
   }
   long long int aa=0;
   for(long int i=0;i<n;i++)
   {
       aa+=a[i];
       ans-=a[i];
       ans1=min(ans1,abs(ans-aa));
   }
   cout<<ans1;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<map>

int main(){
    std::string S;
    std::cin >> S;
    std::map<char, int> mp;
    for(int i = 0; i < S.size(); i++){
        mp[S[i]]++;
    }
    for(auto i : mp){
        if(i.second != 2){
            std::cout << "No" << std::endl;
            return 0;
        }
    }
    std::cout << "Yes" << std::endl;
    return 0;
}


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

int main() {
  int a,b;
  cin >> a >> b;
  if ((a + b) % 2 == 0)
  {
    cout << (a + b) / 2 << endl;
  } 
  else
  {
    cout << (a + b) / 2 + 1 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b,n;
    cin>>a>>b;
    n=-1;

    for(int i=13; i<=1251; i++){
        if(i*2/25==a and i/10==b){
            n=i;
            break;
        }
    }
    cout<<n<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

typedef pair<int, int> P_;
typedef pair<double, P_> P;

const double PI = 3.1415926535897932384526;

vector<P> p;



int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        double x, y;
        cin >> x >> y;
        double t = atan2(y, x);
        p.push_back(P(t, P_(x, y)));
    }

    double ans = 0.0;
    sort(p.begin(), p.end());
    for(int i = 0; i < N; i++){
        double sx = 0.0, sy = 0.0;
        for(int j = 0; j < N; j++){
            int k = (i+j)%N;
            sx += p[k].second.first;
            sy += p[k].second.second;
            ans = max(ans, sqrt(sx*sx+sy*sy));
        }
    }
    cout << fixed << setprecision(10);
    cout << ans << endl;
}


Measured memory_bytes: 256
n=int(input())
if n==3:
  print(22,3,5)
  exit()
if n==4:
  print(2,3,4,9)
  exit()
if n==5:
  print(2,3,4,6,9)
  exit()
a=n//4
b=n%4
ans=[]
for i in range(a):
  ans.extend((6*i+2,6*i+3,6*i+4,6*i+6))
if a%2==0:
  if b==1:
    ans.append(6*a+6)
  if b==2:
    ans.extend((6*a+2,6*a+4))
  if b==3:
    ans.extend((6*a+2,6*a+4,6*a+6))
else:
  if b==0:
    del ans[-1]
    ans.append(6*a+3)
  if b==1:
    ans.append(6*a+3)
  if b==2:
    ans.extend((6*a+3,6*a+6))
  if b==3:
    ans.extend((6*a+2,6*a+3,6*a+4))
print(*ans)


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



int calc(char s, int a, int b){
  if(s == '+') return a+b;
  else return a-b;
}


int main() {
  int N; cin >> N;
  int a=N/1000%10;
  int b=N/100%10;
  int c=N/10%10;
  int d=N%10;
  string pm = "+-";


  for(int i=0; i<2; i++){
    for(int j=0; j<2; j++){
      for(int k=0; k<2; k++){
        if(calc(pm[k], calc(pm[j], calc(pm[i], a, b), c), d) == 7){
          cout << a << pm[i] << b << pm[j] << c << pm[k] << d << "=7" <<endl;
          return 0;
        }
      }
    }
  }

  return 0;
}


Measured memory_bytes: 256