akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000
#define SENTINEL 2000000000

struct Card {
	char suit;
	int value;
};

struct Card L[(MAX / 2) + 2], R[(MAX / 2) + 2];

void merge(struct Card A[], int n, int left, int mid, int right) {
	int i, j, k;
	int n1 = mid - left;
	int n2 = right - mid;
	for (i = 0; i < n1; i++)
		L[i] = A[left + i];
	for (i = 0; i < n2; i++)
		R[i] = A[mid + i];
	L[n1].value = R[n2].value = SENTINEL;
	i = j = 0;
	for (k = left; k < right; k++) {
		if (L[i].value <= R[j].value)
			A[k] = L[i++];
		else
			A[k] = R[j++];
	}
}

void mergeSort(struct Card A[], int n, int left, int right) {
	int mid;
	if (left + 1 < right) {
		mid = (left + right) / 2;
		mergeSort(A, n, left, mid);
		mergeSort(A, n, mid, right);
		merge(A, n, left, mid, right);
	}
}

int partition(struct Card A[], int n, int p, int r) {
	int i, j;
	struct Card t, x;

	x = A[r];
	i = p - 1;

	for (j = p; j < r; j++) {
		if (A[j].value <= x.value) {
			i++;
			t = A[i];
			A[i] = A[j];
			A[j] = t;
		}
	}

	t = A[i + 1];
	A[i + 1] = A[r];
	A[r] = t;

	return i + 1;
}

void quickSort(struct Card A[], int n, int p, int r) {
	int q;
	if (p < r) {
		q = partition(A, n, p, r);
		quickSort(A, n, p, q - 1);
		quickSort(A, n, q + 1, r);
	}
}

int main() {
	int n, i, v;
	struct Card A[MAX], B[MAX];
	char S[10];
	int stable = 1;

	scanf("%d", &n);
	if (n < 1 || n > MAX)
		exit(1);

	for (i = 0; i < n; i++) {
		scanf("%s %d", S, &v);
		A[i].suit = B[i].suit = S[0];
		A[i].value = B[i].value = v;
	}

	mergeSort(A, n, 0, n);
	quickSort(B, n, 0, n - 1);

	for (i = 0; i < n; i++) {
		if (A[i].suit != B[i].suit)
			stable = 0;
	}

	if (stable == 1)
		printf("Stable\n");
	else
		printf("Not stable\n");
	for (i = 0; i < n; i++)
		printf("%c %d\n", B[i].suit, B[i].value);

	return 0;
}


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

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

const long long MOD = 1000000007;

int main(){
  int n,m,a;
  cin >> n >> m;
  ll s=0;
  rep(i,m){
  	cin >> a;
  	s+=a;
  }
  ll ans = n - s;
  if(ans >= 0)cout << ans << endl;
  else cout<< "-1" << endl;
}


Measured memory_bytes: 3624
#include <iostream>

int main() {
        int h, w;
        while (1) {
                std::cin >> h >> w;
                if (h == 0 && w == 0) break;
                for (int i = 0; i < h; i++) {
                        for (int j = 0; j < w; j++) {
                                std::cout << "#";
                        }
                        std::cout << std::endl;
                }
                std::cout << std::endl;
        }
        return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2*1e5+10;
const int MOD = 1e9 + 7;
const int INF = 1e18 + 10;
int dp[101][(int)1e5+1];
int weight[101];
int val[(int)1e5 + 1];
int W;
int ans[101];
int n;

void printVector(vector<int> s){
    for(int &x:s){
        cout<<x<<" ";
    }
    cout<<endl;
}

int rec(int i,int w){
    if(i==n){
        return 0;
    }
    if(dp[i][w]!=-1){
        return dp[i][w];
    }
    if(w+weight[i]<=W){
        return dp[i][w] = max(val[i] + rec(i+1,w+weight[i]),rec(i+1,w));
    }
    return dp[i][w] = rec(i+1,w);
}


void solve(){
    cin>>n;
    cin>>W;
    for(int i = 0 ; i <101 ; i++){
        for(int j = 0 ; j < 1e5 + 1; j++) dp[i][j] = -1;
    }
    for(int i = 0 ; i < n ; i++){
        cin>>weight[i];
        cin>>val[i];
    }
    cout<<rec(0,0)<<endl;


}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
//    cin>>t;
    t = 1;
    for(int i = 0 ; i < t ; i++){
        solve();
    }
    return 0;
}

Measured memory_bytes: 82544
#include <cstdio>

int main()
{
  char s[4];
  scanf("%s", s);
  printf("%d\n", 700 + 100 * ((s[0] == 'o' ? 1 : 0) + (s[1] == 'o' ? 1 : 0) + (s[2] == 'o' ? 1 : 0)));
  return 0;
}

Measured memory_bytes: 128
n,x = gets.split.map(&:to_i)

def para(a,b)
  short,long = [a,b].sort
  if short == long
    return short
  elsif long % short == 0
    return long*2 - short
  elsif short < long
    return 2*short*(long/short) + para(short,long%short)
  end
end

puts n + para(x,n-x)


Measured memory_bytes: 3836
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL a[30010],dp[30010];
int main(){
	LL n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j+i-1<=n;j++)
			dp[j]=max(a[j]-dp[j+1],a[j+i-1]-dp[j]);
	cout<<dp[1]<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A, B, C, D; cin >> N>>A>>B>>C>>D;
  string s; cin >> s;
  bool flg=true;
  if(D>C) {
    for (int i=A-1; i<C-1; i++) {
      if(!flg) break;
      if(s[i]=='#'&&s[i+1]=='#') flg = false;
    }
    for (int i=B-1; i<D-1; i++) {
      if(!flg) break;
      if(s[i]=='#'&&s[i+1]=='#') flg = false;
    }
  }
  if(D<C) {
    flg=false;
    for (int i=B-2; i<D-1; i++) {
      if(flg) break;
      if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.') flg = true;
    }
    for (int i=A-1; i<C-1; i++) {
      if(!flg) break;
      if(s[i]=='#'&&s[i+1]=='#') flg = false;
    }
    for (int i=B-1; i<D-1; i++) {
      if(!flg) break;
      if(s[i]=='#'&&s[i+1]=='#') flg = false;
    }
  }
  if(flg) cout << "Yes" << "\n";
  else cout << "No" << "\n";
}

Measured memory_bytes: 640
{-# LANGUAGE PartialTypeSignatures #-}
module Main (main) where

import qualified Data.ByteString.Char8 as C8
import qualified Data.Char as C
import qualified Data.List as L

main :: IO ()
main = readInts >>= output . solve

solve :: [Int] -> Int
solve [n] = if r == 0 then 0 else 1000 - r
  where
    r = n `mod` 1000

output :: Int -> IO ()
output = print

-- utils
readInts :: IO [Int]
readInts = L.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine

Measured memory_bytes: 3776
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 1; i < n + 1; i++)
#define PI 3.14159265359
#define EPS 0.0000000001
#define MOD 1000000007
//cout << std::fixed << std::setprecision(15) << y << endl;


int main(){
    ll N;
    cin >> N;

    string W[N];
    bool success = true;
    char lastChar;
    rep(i, N){
        cin >> W[i];
        if(!success){
            continue;
        }
        rep(j, i){
            if(W[j] == W[i]){
                success = false;
                break;
            }
        }
        if(i != 0){
            if(lastChar != W[i][0]){
                success = false;
            }
        }
        lastChar = W[i][W[i].size() - 1];
    }

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

    return 0;
}

Measured memory_bytes: 3564
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
typedef long long ll;

string lltos(ll x){
  stringstream ss;
  ss << x;
  return ss.str();
}

ll len(ll x){
  x--;
  ll k=9,lim=10,res=0,l=1;
  while(x>=lim){
    res += k*l;
    k*=10; lim*=10; l++;
  }
  res += (x-lim/10+1)*l;
  return res;
}

int main(){
  ll n,k;

  while(cin >> n >> k,n||k){
    ll l = 1, r = n+1;

    while(r-l>1){
      ll mid = (l+r)/2;
      if(len(mid)<n)l = mid;
      else r = mid;
    }
    int dif = n-1-len(l);

    string res = "";
    while(res.size()<2*k){
      res += lltos(l++);
    }

    cout << res.substr(dif,k) << endl;
  }
}
    

Measured memory_bytes: 1224
import heapq

if __name__ == "__main__":
    n, m = list(map(int, input().split(" ")))
    a = list(map(lambda x: (-1) * int(x), input().split(" ")))

    heapq.heapify(a)

    for i in range(m):
        maxValue = heapq.heappop(a) * (-1)
        heapq.heappush(a, (-1) * (int(maxValue / 2)))

    print((-1) * sum(a))


Measured memory_bytes: 14180
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=input.split("\n");
var A=Arr[1].split(" ").map(Number);
var N=Arr[0]-0;
console.log(A.join(" "));
for(var i=1;i<=N-1;i++){
   var v=A[i];
   var j=i-1;
   while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
   }
A[j+1]=v;
console.log(A.join(" "));
}


Measured memory_bytes: 16532
//arc062_c.cpp
//Sun Jun 10 18:12:34 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;

int main(){
	string s;
	cin >> s;

	int num=0;

	for (int i=0;i<s.size();i++){
		if (s[i] == 'g'){
			num++;
		}else {
			num--;
		}
	}



	cout << num/2 << endl;
}

Measured memory_bytes: 512
EPS = 1e-5

include Math

k = 0
loop do
  n = gets.to_i
  break if n == 0
  points = (1..n).map { gets.split.map(&:to_i) }
  best = 0

  points.combination(2).each do |p1, p2|
    x1, y1 = p1
    x2, y2 = p2
    # p [x1, y1, x2, y2]
    t = atan2(y2 - y1, x2 - x1)
    shifted = points.map {|x, y| [x - x1, y - y1] }
    normalized = shifted.map {|x, y| [cos(-t) * x - sin(-t) * y, sin(-t) * x + cos(-t) * y] }

    zero_point_type = {}

    (normalized + [normalized[0]]).each_cons(2) do |p1, p2|
      x1, y1 = p1
      x2, y2 = p2
      next if y1.abs < EPS || y2.abs < EPS
      next if y1 * y2 > 0
      if (x1 - x2).abs < EPS
        x = x1
      else
        x = (y2 * x1 - y1 * x2) / (y2 - y1)
      end
      zero_point_type[x] = :VERTICAL
    end

    (normalized + normalized[0..1]).each_cons(3) do |p0, p1, p2|
      x0, y0 = p0
      x1, y1 = p1
      x2, y2 = p2
      # p [p0, p1, p2]
      if y1.abs >= EPS
        next
      end
      if y0.abs < EPS && y2.abs < EPS
        next
      end

      if y0.abs < EPS
        if x0 < x1
          if y2 > EPS
            zero_point_type[x1] = :RIGHT_UP
          else
            zero_point_type[x1] = :RIGHT_DOWN
          end
        else
          if y2 > EPS
            zero_point_type[x1] = :DOWN_RIGHT
          else
            zero_point_type[x1] = :UP_RIGHT
          end
        end
      elsif y2.abs < EPS
        if x2 < x1
          if y0 > EPS
            zero_point_type[x1] = :RIGHT_UP
          else
            zero_point_type[x1] = :RIGHT_DOWN
          end
        else
          if y0 > EPS
            zero_point_type[x1] = :DOWN_RIGHT
          else
            zero_point_type[x1] = :UP_RIGHT
          end
        end
      elsif y0 * y2 < EPS
        zero_point_type[x1] = :VERTICAL
      end
    end

    # p zero_point_type
    
    state = :OUT
    from = nil
    prev_state = nil
    prev_type = nil

    zero_point_type.keys.sort.each do |x|
      type = zero_point_type[x]

      enter = proc do
        state = :IN
        from = x
      end

      leave = proc do
        state = :OUT
        len = x - from
        best = len if len > best
      end

      case type
      when :VERTICAL
        state == :OUT ? enter[] : leave[]
      when :UP_RIGHT
        prev_state = state
        enter [] if state == :OUT
        prev_type = type
      when :DOWN_RIGHT
        prev_state = state
        enter [] if state == :OUT
        prev_type = type
      when :RIGHT_UP
        if prev_type == :UP_RIGHT
          leave[] if prev_state == :IN
        else
          leave[] if prev_state == :OUT
        end
      when :RIGHT_DOWN
        if prev_type == :DOWN_RIGHT
          leave[] if prev_state == :IN
        else
          leave[] if prev_state == :OUT
        end
      end

    end

    # p best
    # puts
  end

  puts "Case #{k += 1}: #{best}"
end



Measured memory_bytes: 7372
#/usr/bin/env python3

# import sys
# input = lambda: sys.stdin.readline().strip()

S = input()
N = len(S)
V = N // 2

L1 = S[:V]
L2 = S[V:]

count = 0
for i in range(V):
    if L1[i] != L2[-1-i]:
        count += 1
    
print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define arep(a,i,n) for(ll i=(a);i<(n);i++)
#define rep(i,n) for(ll i=0;i<(n);i++)
#define cinf(x,n) for(ll i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(ll i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

int main(){
	string s;
	cin >> s;
	int i=0;
	while(true){
		if(i==s.length())
			break;
		else if(s[i]==',')
			cout << " ";
		else
			cout << s[i];
		i++;
	}
	cout << endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int t; cin >> t; cin.ignore(); while(t--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
ll xpow(ll n, ll m){if(m==0){return 1;}else{ll x = xpow(n, m/2);if(m&1){return x*x*n;}else{return x*x;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}

int main(){
    fast();

/* you get what you work for not what you wish for */

    inp(n);
    ll ans = 1e18;
    for(ll i=1; i*i<=n; i++){
        if(n%i==0){
            ll a = i;
            ll b = n/i;
            ans = min(ans, a-1+b-1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
typedef pair<pll, pll> P;
const ll INF = 1ll<<30;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

int g[500][500];

void dfs(vector<int> &v, int level) {
	vector<int> v1, v2;
	REP(i, v.size() / 2) v1.push_back(v[i]);
	FOR(i, v.size() / 2, v.size()) v2.push_back(v[i]);
	
	if (v1.size() == 0 || v2.size() == 0) return;
	
	REP(i, v1.size()) REP(j, v2.size()) g[v1[i]][v2[j]] = g[v2[j]][v1[i]] = level;
	
	dfs(v1, level + 1);
	dfs(v2, level + 1);
}

int main() {
	int N; cin >> N;
	
	memset(g, -1, sizeof(g));
	
	vector<int> v;
	REP(i, N) v.push_back(i);
	
	dfs(v, 1);
	
	REP(i, N) FOR(j, i + 1, N) {
		printf("%d%c", g[i][j], j == N - 1 ? '\n' : ' ');
	}
}


Measured memory_bytes: 1408
function Main(input) {
	input = input.trim().split("\n").map(function(x) { return x.split(" ")});
	let A = parseInt(input[0][0], 10);
	let B = parseInt(input[0][1], 10);
	let K = parseInt(input[0][2], 10);
	let ans;
	if (K <= A) {
		ans = [A - K, B];
	} else {
		ans = [0, Math.max(0, B - (K - A))];
	}
	
	console.log(ans.join(" "));

}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main() {
	int n,d;
	cin >> n >> d ;
	int h = 2 * d + 1;
	int am =0,sh = n/h;
	if(n % h > 0)
	{
		am = 1;
	}
  cout << sh + am  << endl;
}


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

// 1 3 5 1 8
int main(){
    int n;
    scanf("%d",&n);
    int h[n],dp[n];
    for (int i=0;i<n;i++) scanf("%d",&h[i]);
    for (int i=1;i<n;i++) dp[i]=-1;
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for (int i=2;i<n;i++) dp[i]=min(abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2]);
    printf("%d\n",dp[n-1]);
    return 0;
}


Measured memory_bytes: 1024
// 2020-08-15 21:02:55
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  int ans = 0;
  rep(i, n-2) REP(j, i+1, n-1) REP(k, j+1, n) {
    int x = a[i];
    int y = a[j];
    int z = a[k];
    if(x == y) continue;
    if(x == z) continue;
    if(y == z) continue;
    if(x + y > z && x + z > y && y + z > x) {
      ans++;
    }
  }
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
using namespace std;
#define REP(i,n) for(int i = 0;i < (int)(n);i++)

int main() {
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
	cout << min(a,b) + min(c,d);
	return(0);
}

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

//#define int int64_t

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)

#define all(c) begin(c), end(c)
#define maxup(ans, x) (ans = (ans < x ? x : ans))
#define minup(ans, x) (ans = (ans > x ? x : ans))

#define breakif(cond) if(cond) break; else

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

const int INF = 1 << 29;

signed main() {
	int n, k; cin >> n >> k;
	set<int> set;
	rep(i, k) {
		int x; cin >> x;
		set.insert(x);
	}
	rep(i, n, 1 << 29) {
		bool ok = true;
		for (int t = i; t != 0; t /= 10) {
			if (set.count(t % 10)) {
				ok = false;
				break;
			}
		}
		if (ok) {
			cout << i << endl;
			break;
		}
	}
	system("pause");
}

Measured memory_bytes: 504
#include <iostream>
#include <string>
#include <iomanip>
#include <ios>
using namespace std;
int main(void){
  int N;
  cin >> N;
  string s;
  cin >> s;
  
  int n = s.length();
  
  if(n <= N)cout << s << endl;
  else{
    for(int i=0;i<N;i++){
      cout << s[i];
    }
    cout << "..." << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3596
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111;
using namespace std;
typedef long long lint;

int main() {

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

	int N, M, X, Y;
	cin >> N >> M >> X >> Y;

	int x_max = -INF, y_min = INF, input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		x_max = max(input, x_max);
	}
	for (int j = 0; j < M; j++) {
		cin >> input;
		y_min = min(input, y_min);
	}

	if (max(X, x_max) < min(Y, y_min)) cout << "No War" << "\n";
	else cout << "War" << "\n";

	return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nline cout<<"\n"
#define fast ios_base::sync_with_stdio(false)cin.tie(0)
#define ain(A, B, C) assert(IN(A, B, C))
#define ull unsigned long long int
#define ll long long int
#define pii pair<int,int>
#define MAXX 100009
#define fr(a,b,i) for(int i=a;i<b;i++)
#define dbg(x) cout<<"Here we are "<<x<<"\n"
vector<pair<int,int> >G[MAXX];
const int N=100010;
const int LGN=22;
#pragma comment(linker, "/STACK:1000000000")
ll parent[LGN][N],depth[MAXX],vis[MAXX],weight[MAXX];


int uplift(int u,int k){
	for(int i=0;i<LGN;i++){
		if(k&1)u=parent[i][u];
		k>>=1;
	}
	return u;
}
void dfs(int src){
	vis[src]=1;
	for(int i=0;i<G[src].size();i++){
		int v=G[src][i].first;
		int w=G[src][i].second;
		if(vis[v])continue;
		parent[0][v]=src;
		weight[v]=weight[src]+w;
		depth[v]=depth[src]+1;
		dfs(v);
	}
}
void init(int k)
{
	dfs(k);
	for(int i=1;i<LGN;i++){
		for(int j=0;j<N;j++){
			if(parent[i-1][j]!=-1){
				parent[i][j]=parent[i-1][parent[i-1][j]];
			}
		}
	}
}
int lca(int u,int v){
	int diff=abs(depth[u]-depth[v]);
	if(depth[u]>depth[v]){
		u=uplift(u,diff);
	}
	else if(depth[v]>depth[u]){
		v=uplift(v,diff);
	}
	if(u==v)return u;
	for(int i=LGN-1;i>=0;i--){
		if(parent[i][u]!=parent[i][v]){
			u=parent[i][u];
			v=parent[i][v];
		}
	}

	return parent[0][u];
}
int main()
{

	memset(parent,-1,sizeof parent);
	memset(vis,0,sizeof vis);
	memset(weight,0,sizeof weight);
	int n;
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u--; v--;
		G[u].pb({v,w});
		G[v].pb({u,w});
	}
	int q, k;
	cin>>q >> k;
	k--;
	init(k);
	for(int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		a--, b--;
		int lc=lca(a,b);
		if(lc == k){
		ll ans=weight[a]+weight[b]-2*weight[lc];
		   cout << ans << endl;
		}
		else{
           ll ans1 = weight[a]+weight[k]-2*weight[k];
           ll ans2 = weight[k]+weight[b]-2*weight[k];
           ll ans = min(ans1, ans2);
           ll diff = abs(ans1-ans2);
           cout << 2*ans+diff << endl;
		}

	}
	return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll INF=(ll)1e19;
//const int INF=(1<<30);

int main(){
  int n,m;
  cin >> n >> m;
  VI s(m,0);

  REP(i,n){
    int k;
    cin >> k;
    REP(j,k){
      int a;
      cin >> a;
      s[--a]++;
    }
  }
  int ans=0;
  REP(i,m){
    if(s[i]==n)ans++;
  }
  cout << ans << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
#define N 200010
namespace seg{
  ll dat[2*N];
  void init(){
      for(int i=0;i<2*N;i++)dat[i]=0;
  }
  void upd(ll l,ll r){
      l+=N,r+=N+1;
      for(ll a=l,b=r;a<b;a>>=1,b>>=1){
	  if(a&1)dat[a++]--;
	  if(b&1)dat[--b]--;
      }
  }
  ll val(ll i){
      ll res=0;
      for(i+=N;i;i>>=1){
	  res+=dat[i];
      }
      return res;
  }
};
#define X 26
queue<ll> Q[X];
int main(){
    string s; ll k;
    cin>>s>>k;
    for(int i=0;i<s.size();i++){
	Q[s[i]-'a'].push(i);
    }
    for(int i=0;i<s.size();i++){
	ll di[X];
	for(int j=0;j<X;j++){
	    if(Q[j].empty())di[j]=1e17;
	    else{
		di[j]=seg::val(Q[j].front())+Q[j].front();
	    }
	}
	ll p;
	for(p=0;p<X;p++)if(di[p]<=k)break;
	if(p==X)break;
	k-=di[p];
	seg::upd(Q[p].front()+1,s.size()-1);
	Q[p].pop();
	char z='a'+p; cout<<z;
    }
    while(1){
	ll mi=1e17,pnt=-1;
	for(int i=0;i<X;i++){
	    if(Q[i].empty())continue;
	    if(mi>Q[i].front()){
		mi=Q[i].front();
		pnt=i;
	    }
	}
	if(pnt==-1)break;
	char z='a'+pnt; cout<<z;
    }
    cout<<endl;
    return 0;
}



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

int minimumChar(string S1, string S2) 
{ 

	int n = S1.size(), m = S2.size(); 

	int ans = INT_MAX;  
	for (int i = 0; i < m - n + 1; i++) { 
		int minRemovedChar = 0; 
		for (int j = 0; j < n; j++) { 
			if (S1[j] != S2[i + j]) { 
				minRemovedChar++; 
			} 
		} 

		ans = min(minRemovedChar, ans); 
	} 

	return ans; 
} 
 
int main() 
{ 
	string s;
	string t ; 
    cin>>s>>t;
	cout << minimumChar(t,s)<<endl; 
	return 0; 
} 



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

double per(double n){
    if(n == 1) return n;
    return n*per(n-1);
}

int main(){
    int n;
    cin >> n;
    vector<int>p(n), q(n);
    for(int i=0;i<n;i++) cin >> p[i];
    for(int i=0;i<n;i++) cin >> q[i];

    vector<int>t(n);
    for(int i=0;i<n;i++) t[i] = i+1;


    vector<vector<int>>vec;
    do{
        vec.push_back(t);
    }while(next_permutation(t.begin(), t.end()));

    int a = -1, b = -1;
    for(int i=0;i<vec.size();i++){
        if(a < 0){
            bool end = true;
            for(int j=0;j<n;j++)if(vec[i][j] != p[j]) end = false;
            if(end) a = i;
        }if(b < 0){
            bool end = true;
            for(int j=0;j<n;j++)if(vec[i][j] != q[j]) end = false;
            if(end) b = i;
        }
    }

    cout << abs(a-b) << endl;
}


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

int main() {
  int h,w;
  cin >> h >> w;
  vector<string> a(h);

  rep(i,h) cin >> a[i];
  

  rep(i,h+1) {
    if (i == 0) {
      rep(j,w+2) cout << '#';
      cout << endl;
    } else {
      cout << '#' << a[i-1] << '#' << endl;
    }
  }


  rep(i,w+2) cout << '#';
  cout << endl;

  return 0;
}

Measured memory_bytes: 3616
# AOJ 1009: Greatest Common Divisor
# Python3 2018.7.4 bal4u

def gcd(a, b):
	while b != 0:
		r = a % b
		a, b = b, r
	return a

while True:
	try: a, b = map(int, input().split())
	except: break
	print(gcd(a, b))


Measured memory_bytes: 5596
N,M = map(int,input().split())
a = list(int(input())for i in range(M))
a= [-1]+a+[N+1]
r = []
for i in range(M+1):
    r.append(a[i+1]-a[i]-1)
fi = [0,1,1]
for i in range(max(r)):
    fi.append(fi[-1]+fi[-2])
ans = 1
for i in r:
    ans = (ans*fi[i])%(10**9+7)
print(ans)

Measured memory_bytes: 460020
#include<bits/stdc++.h>
#define ull unsigned long long
# define ll long long
# define mod 1000000007LL 
using namespace std;
int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a,b;
    ll flag=0;
    ll count=0;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        if(a==b)
        count++;
        else if(a!=b)
        count=0;
        if(count==3)
        flag=1;

    }
    if(flag==0)
    cout<<"No";
    else
    {
        cout<<"Yes";
    }
    
    
    
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

ll a[125252],b[125252];

int main(){
  int w,h;
  scanf("%d%d",&w,&h);
  REP(i,w)scanf("%lld",a+i);
  REP(i,h)scanf("%lld",b+i);
  sort(a,a+w);
  sort(b,b+h);
  int j=0,k=0;
  ll ans = 0;
  REP(i,w+h){
    if((j<w&&k<h&&a[j]<b[k]) || (j<w&&k==h)){
      ans += (ll)(h+1-k)*a[j];
      j++;
    }else{
      ans += (ll)(w+1-j)*b[k];
      k++;
    }
    // DEBUG(ans);
    // DEBUG(j);
    // DEBUG(k);
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
long long x,k,d;
int main()
{
    cin>>x>>k>>d;
    if(abs(x/d)>k)
    {
        if(x>0) cout<<abs(x-k*d)<<endl;
        else cout<<abs(x+k*d)<<endl;
        return 0;
    }
    k-=abs(x/d);
    x%=d;
    if(k&1) cout<<(x<=0? abs(x+d):abs(x-d))<<endl;
    else cout<<abs(x)<<endl;
	return 0;
}


Measured memory_bytes: 3628
t1 = x1 = y1 = 0

num = int(input())

for i in range(num):
    t2,x2,y2 = map(int, input().split())

    if (x2-x1 + y2-y1) > (t2-t1):
        print('No')
        exit()
    elif ((t2-t1)-(x2-x1 + y2-y1) ) % 2 == 0:
        t1=t2
        x1=x2
        y1=y2
    else:
        print('No')
        exit()

print('Yes')


Measured memory_bytes: 44904
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int X[] = new int[M];
    int Y[] = new int[M - 1];
    for (int i = 0; i < M; i++) {
      X[i] = sc.nextInt();
    }
    Arrays.sort(X);
    for (int i = 0; i < M - 1; i++) {
      Y[i] = X[i + 1] - X[i];
    }
    Arrays.sort(Y);
    int ans = 0;
    for (int i = 0; i < M - N; i++) {
      ans += Y[i];
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 58320
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

que = deque()
que.append((1, 0))
ok = False
seen = [[False] * (N + 1), [False] * (N + 1)]
while que:
    v, d = que.popleft()
    if v == N and d == 2:
        ok = True
        break
    if d >= 2:
        continue
    for u in graph[v]:
        if not seen[d][u]:
            seen[d][u] = True
            que.append((u, d + 1))
if ok:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 84700
import java.util.*;
import static java.lang.Math.*;

public class Main {
    
    static int[] a;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int k = sc.nextInt();
		boolean[] bool = new boolean[n];
		for(int i = 0; i < k; i++){
		    int d = sc.nextInt();
		    for(int j = 0; j < d; j++){
		        bool[sc.nextInt()-1] = true;
		    }
		}
		
		// 計算
		int result = 0;
		for(int i = 0; i < n; i++){
		    if(!bool[i]) result++;
		}
		
		
		// 出力
		System.out.println(result);
	}
}


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

int64_t sum_i(int i, vector<string> &si) {
  if (i == 0) {
    return 0;
  }
  if (i == 1) {
    int64_t a = stoll(si.at(0));
    return a;
  }
  else {
    int64_t total = 0;
    for (int j = 0; j < i; j++) { 
      string b = si.at(i - 1).substr(i - j -1);
      int64_t a = stoll(b);
      int c = 1;
      for (int k = 0; k < i - j - 2; k++) {
        c*=2;
      }
      total += sum_i(i - j - 1, si) + a * c;
    }
    return total;
  }
}  

int main() {
  string S;
  cin >> S;
  vector<string> si(S.size());
  string a = S;
  for (int i = 0; i < S.size(); i++) {
    si.at(S.size() - i - 1) = a;
    a.pop_back();
  }
  cout << sum_i(S.size(), si) << endl;    
}


Measured memory_bytes: 256
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
        Scanner sn = new Scanner(System.in);
        
        int n = Integer.parseInt(sn.next());
        int list[] = {0,0,0,0};
        String str;

        for (int i = 0; i < n; i++){
            str = sn.next();
            switch(str){
                case "AC":
                    list[0] = list[0] + 1;
                    break;
                case "WA":
                    list[1] = list[1] + 1;
                    break;
                case "TLE":
                    list[2] = list[2] + 1;
                    break;
                case "RE":
                    list[3] = list[3] + 1;
                    break;
            }
        }
        System.out.println("AC x " + list[0]);
        System.out.println("WA x " + list[1]);
        System.out.println("TLE x " + list[2]);
        System.out.println("RE x " + list[3]);
    }
}




Measured memory_bytes: 58180
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    vector<int> ans;
    int v[3] = {2, 3, 5};
    auto f = [&](int val, int cur, auto &&f){
        if(val > 1000000) return;
        ans.emplace_back(val);
        f(val*v[cur], cur, f);
        if(cur != 2) f(val, cur+1, f);
    };
    f(1, 0, f);
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    int l;
    while(cin >> l, l){
        int r;
        cin >> r;
        cout << upper_bound(ans.begin(),ans.end(), r) - lower_bound(ans.begin(),ans.end(), l) << "\n";
    }
    return 0;
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define light ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ld long double
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i,a,b) for(ll i = a; i < b; i++)
#define REPE(i,a,b) for(ll i = a; i <= b; i++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define bins(v, x) binary_search(v.begin(), v.end(), x)
const double pi = 2*acos(0.0);
const int INF = 1e9+1;
const int mod = 1e9+7;
const int mod1 = 998244353;
 
ll modExp(ll base, ll exp, ll mod) {
   ll res = 1;
   while (exp > 0) {
    	if (exp % 2 == 1) {
        	res= (res * base) % mod;
		}
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}

ll inverse(ll base, ll exp, ll mod) {
   return modExp(base, exp - 2, mod);
}

bool compare(const pair<int, int>&i, const pair<int, int>&j) {
   return (i.S > j.S || (i.S == j.S && i.F > j.F));
}

void test() {
   int n;
   cin >> n;

   map<string,int> m;
   while(n--) {
      string s;
      cin >> s;
      m[s]++;
   }

   cout << "AC x " << m["AC"] << "\n" << "WA x " << m["WA"] << "\n" << "TLE x " << m["TLE"] << "\n" << "RE x " << m["RE"];
}

int main() {
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   light;
   cout.precision(15);
   cout << fixed;

   int t = 1;
   //cin >> t;
   while(t--) {
      test();
   }
   return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>
#define N 250

int Pa(int);
int Le(int);
int Ri(int);


int main(){

 
  int i,num,A[N],le,ri;

 scanf("%d",&num);

  for( i =1; i<=num;i++)scanf("%d",&A[i]);

  for(i =1; i<=num;i++){

    printf("node %d: key = %d, ",i,A[i]);

    if(i>1)printf("parent key = %d, ",A[Pa(i)]);

    le=Le(i);
    ri=Ri(i);

    if(le<=num)printf("left key = %d, ",A[Le(i)]);
    if(ri<=num)printf("right key = %d, ",A[Ri(i)]);
    puts("");
  }
  


  return 0;
}
  int Pa(int i){
    return i/2;
  }

  int Le(int i){
    return 2*i;
  }


  int Ri(int i){
    return 2*i+1;
  }

Measured memory_bytes: 608
from fractions import gcd

a, b, c, d = map(int, input().split())

cnt = int(0)

for i in [c, d]:
    t4 = a // i
    if a % i == 0:
        t1 = t4
    else:
        t1 = t4+1
    t2 = b // i

    cnt += int(t2 - t1 + 1)

lcm = c * d // int(gcd(c, d))

i = lcm
t4 = a // i
if a % i == 0:
    t1 = t4
else:
    t1 = t4 + 1
t2 = b // i

cnt -= int(t2 - t1 + 1)

print(b - a + 1 - cnt)

Measured memory_bytes: 5308
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i >= n; --i)
typedef long long ll;
#define mod 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

int main() {
  string S;
  cin >> S;
  vector<bool> c(26);
  rep(i, 0, S.size()) {
    c[S[i] - 'a'] = 1;
  }
  rep(i, 0, 26) {
    if(!c[i]) {
      cout << (char)('a' + i) << endl;
      return 0;
    }
  }
  cout << "None" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Path{
    int w,s,t;
    
    bool operator < (const Path &a) const{
        return w < a.w;
    }
};

struct UnionFind{
    vector<int> par;
    
    UnionFind(int n)
        :par(n)
    {
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    
    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry)return;
        else{
            par[rx]=ry;
            return;
        }
    }
    
    int root(int x){
        if(x==par[x])return x;
        else return par[x]=root(par[x]);
    }
};

int main(void){
    int i,j,n,w;
    vector<Path> path;
    Path tmp;
    
    cin>>n;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            cin>>w;
            if(i>j)continue;
            else if(w!=-1){
                tmp.w=w,tmp.s=i,tmp.t=j;
                path.push_back(tmp);
            }
        }
    }
    
    sort(path.begin(),path.end());
    
    UnionFind tree(n);
    int sum=0;

    for(i=0;i<path.size();i++){
        tmp=path[i];
        if(tree.root(tmp.s)!=tree.root(tmp.t)){
            tree.unite(tmp.s,tmp.t);
            sum+=tmp.w;
        }
    }

    cout<<sum<<endl;
    return 0;
}



Measured memory_bytes: 3184
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

s = ns()
t = ns()
S, T = len(s), len(t)
dp = [[0] * (T+1) for _ in range(S+1)]

for i in range(0,S):
    for j in range(0,T):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
#print(dp)
i, j = S, T
ans = ""
while i > 0 and j > 0:
    if dp[i][j] ==dp[i-1][j]:
        # (i-1, j) -> (i, j)
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        # (i, j-1) -> (i, j)
        j -= 1
    else:
        # (i-1, j-1) -> (i, j)
        ans = s[i-1] + ans
        i -= 1; j -= 1

print(ans)


Measured memory_bytes: 113756
if __name__ == '__main__':
    h, w = map(int, input().split())
    n = int(input())
    a = list(map(int, input().split()))

    c = [0] * (h*w)
    
    focus = 0
    for i in range(n):
        for j in range(a[i]):
            c[focus] = i+1
            focus += 1

    for i in range(h):
        for j in range(w):
            if(i%2 == 0):
                if(j + 1 != w):
                    print(c[i*w+j],end=" ")
                else:
                    print(c[i*w+j])
            else:
                if(j + 1 != w):
                    print(c[(i+1)*w-1-j],end=" ")
                else:
                    print(c[(i+1)*w-1-j])


Measured memory_bytes: 3884
#include <bits/stdc++.h>
#include <random>
//-------------------------------------------------------------------------
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define prv(v) for (auto i : v) { cout << i << " ";}
#define prmat(v) for (auto i : v) { prv(i); cout << "\n";}
#define cout(x) cout << fixed << setprecision(x)
#define read(v) for (int i_ = 0; i_ < v.size(); i_++) { cin >> v[i_];}
#define fast_io ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(v) (v.begin()), (v.end())
#define rall(v) (v.rbegin()), (v.rend())
#define pii pair<int, int>
//-------------------------------------------------------------------------
int main() {
    fast_io;
#ifdef LOCALKA
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ll n, p;
    cin >> n >> p;
    map<ll, ll> divs;
    ll i = 2;
    while(i * i <= p){
        while(p % i == 0){
            divs[i]++;
            p /= i;
        }
        i++;
    }
    if(p != 1){
        divs[p]++;
    }
    ll answ = 1;
    for(auto i : divs){
        if(i.second >= n){
            ll k = i.second / n;
            for(int x = 0; x < k; x++){
                answ *= i.first;
            }
        }
    }
    cout << answ;
}


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

int main(){
  int N;
  cin >> N;
  vector<int> h(N);
  int64_t ans=0;
  cin >> h.at(0);
  int x=h.at(0);
  ans+=x;
  for(int i=1;i<N;i++){
    cin >> h.at(i);
    if(x<=h.at(i)){
      ans+=h.at(i)-x;
    }
      x=h.at(i);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def iin(): return int(input())
def nl(): return list(map(int, input().split()))

n, k = nl()

ans = 0
for b in range(1, n + 1):
    ans += (n // b) * max(0, b - k)
    if k == 0:
        ans -= 1
    ans += max(0, (n % b) - k + 1)
print(ans)

Measured memory_bytes: 3060
def div(num):
  ret=[]
  for i in range(1,int(num**0.5)+1):
    if num%i==0:
      ret.append(i)
      if i!=num//i:
        ret.append(num//i)
  return ret

n,m=map(int,input().split())
div_list=div(m)
div_list=sorted(div_list,reverse=True)
ans=0
for i in div_list:
  if (m-i*n)%i==0 and m>=i*n:
    ans=i
    break
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;




int main(){
  int n, m;
  cin >> n >> m;
  vector<int> s(m);
  vector<char> c(m);
  rep(i, m) cin >> s[i] >> c[i];

  int nmin = pow(10, n-1);
  if (nmin == 1) nmin = 0;
  int nmax = pow(10, n);
  for (int i = nmin; i < nmax; i++){
    bool ok = true;
    string tmp = to_string(i);
    rep(j, m){
      if(tmp[s[j] - 1] != c[j]) ok = false;
    }
    if (ok){
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
def factorization(n):
    """
    nを素因数分解
    2以上の整数n => [[素因数, 指数], ...]の2次元リスト
    """
    arr = []
    temp = n
    for i in range(2, int(-(-(n ** 0.5) // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


N = int(input())
fact_li = factorization(N)
ans = 0
for t in fact_li:
    if t[0] == 1:
        continue
    tmp = t[1]
    for i in range(1, tmp + 1):
        if tmp >= i:
            ans += 1
            tmp -= i
        else:
            break

print(ans)


Measured memory_bytes: 63252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=200005;
int n;
ll a[N],ans=1e18;
int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read()+a[i-1];
	for(int i=2;i+2<=n;i++){
		int pos=lower_bound(&a[1],&a[i],a[i]/2)-a;
		if(abs(a[pos]-(a[i]-a[pos]))>abs(a[pos-1]-(a[i]-a[pos-1])))pos--;
		int ppp=lower_bound(&a[i+1],&a[n+1],(a[n]-a[i])/2+a[i])-a;
		if(abs(a[ppp]-a[i]-(a[n]-a[ppp]))>abs(a[ppp-1]-a[i]-(a[n]-a[ppp-1])))ppp--;
		ans=min(ans,max(max(a[pos],a[i]-a[pos]),max(a[ppp]-a[i],a[n]-a[ppp]))-min(min(a[pos],a[i]-a[pos]),min(a[ppp]-a[i],a[n]-a[ppp])));
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1792
// Medha's code  :


#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fastio ios_base:: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define INF 0x3f3f3f3f3f

int main() {

    fastio;

    ll n,k, mini=INF;
    vector<ll> height(100005);
    vector<ll> dp(100005);

    cin >> n ;

    k=2;

    for( ll i = 1 ; i <= n ; i++)
    {
        cin >> height[i];
    }

    dp[1] = 0;

    for( ll i = 2; i <= min(k,n) ; i++)
    {
        for( ll j = 1 ; j <= i-1 ; j++)
        {
            mini = min ( mini , abs(height[j]-height[i]) + dp[j] ) ;
        }

        dp[i]= mini;
        mini = INF;
    }

    for( ll i = k+1; i<= n ; i++)
    {
        for( ll j = i-1 ; j >= i-k ; j--)
        {
            mini = min( mini,  abs(height[j] - height[i]) + dp[j] );
        }
        dp[i] = mini;
        mini = INF;
    }

    cout << dp[n];

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main()
{
    string s1="Sunny",s2="Cloudy",s3="Rainy",s;
    cin>>s;
    if(s==s1){
        cout<<s2<<endl;
    }else if(s==s2){
        cout<<s3<<endl;
    }else{
        cout<<s1<<endl;
    }
    return 0;
}


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

bool IsOneBit(int bits, int i) {
	return (bits & (1 << i)) > 0;
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int>> S(M);
	for (int i = 0; i < M; i++) {
		int k;
		cin >> k;
		S[i] = vector<int>(k);
		for (int j = 0; j < k; j++) cin >> S[i][j];
	}
	vector<int> P(M);
	for (int i = 0; i < M; i++) cin >> P[i];

	int ans = 0;
	for (int bit = 0; bit < (1 << N); bit++) {
		bool AreAllOK = true;
		for (int i = 0; i < M; i++) {
			int Sum = 0;
			for (int s : S[i]) Sum += IsOneBit(bit, s - 1);
			if (Sum % 2 != P[i]) AreAllOK=false;
		}
		if (AreAllOK) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256