akhauriyash/Code-Regression huggingface dataset:
import math
import sys
readline = sys.stdin.readline


def main():
    # input
    n = int(readline().rstrip())
    A = list(map(int, readline().rstrip().split()))
    B = [0] * n

    for a in A:
        B[a - 1] += 1

    total = 0
    for b in B:
        if b > 1:
            total += b * (b - 1) // 2

    C = [0] * n
    for i, b in enumerate(B):
        C[i] = total + (b - 1) * (b - 2) // 2 - (b) * (b - 1) // 2

    for a in A:
        print(C[a-1])


if __name__ == '__main__':
    main()


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

int main(){
	int a,b;
	string s[100];
	cin>>a>>b;

	for (int i = 0; i < a; i++){
		cin>>s[i];
	}

	for (int i = 0; i < b+2; i++){
		cout<<'#';
	}
	cout<<endl;

	for (int i = 0; i < a; i++){
		cout<<'#'<<s[i]<<'#'<<endl;
	}

	for (int i = 0; i < b+2; i++){
		cout<<'#';
	}
	cout<<endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    // Your code here!
    int N, K;
    int min=1000000001;
    
    cin >> N >> K;
    
    int h[N];
    for(int i=0;i<N;i++){
        cin >> h[i];
    }
    sort(h,h+N);
    for(int i=0;i<N-K+1;i++){
        if(h[i+K-1]-h[i]<min){
            min = h[i+K-1] - h[i];
        }
    }
    
    cout << min << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>

using namespace std;

int main() {
	string S;
	cin >> S;
	if (S == "Sunny") {
		cout << "Cloudy";
	}
	else if (S == "Cloudy") {
		cout << "Rainy";
	}
	else {
		cout << "Sunny";
	}
	return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let s: String = read().unwrap();

    if &s == "SAT" {
        println!("1");
    } else if &s == "FRI" {
        println!("2");
    } else if &s == "THU" {
        println!("3");
    } else if &s == "WED" {
        println!("4");
    } else if &s == "TUE" {
        println!("5");
    } else if &s == "MON" {
        println!("6");
    } else { println!("7") }
}

Measured memory_bytes: 4352
import scala.io.{StdIn => in}

object Main extends App {
  val Array(n, h) = in.readLine.split(" ").map(_.toInt)
  val k = Iterator.continually(in.readLine)
    .take(n)
    .map(_.split(" ").map(_.toInt))
    .toArray
    .transpose
  
  val ans = {
    val a = k(0).max
    val b = k(1).filter(_ > a).sorted(Ordering[Int].reverse)

    def rec(hp:Int, cnt:Int):(Int,Int) = {
      if(hp <= 0 || cnt >= b.size) (hp,cnt)
      else rec(hp-b(cnt),cnt+1)
    }

    val (hp,cnt) = rec(h,0)
    if(hp <= 0) cnt else cnt + (hp + (a-1)) / a
  }

  println(ans)
}

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

import numpy as np

def EDPC_B_flog():
    """
    5 3
    10 30 40 50 20
    ans 30
    0 20 30 40 30
    
    3 1
    10 20 10
    ans 20
    
    2 100
    10 10
    ans 0
    
    10 4
    40 10 20 70 80 10 20 70 80 60
    ans 40
    0 30 20 30 40 30 20 30 40 40
    """
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    k = min(n-1, k)
    a = np.array(a)
    dp = np.concatenate([np.abs(a - a[0])[:k+1], np.zeros(n-k-1, dtype="int")])
    for i in range(k+1, n):
        dp[i] = np.min(dp[i-k:i] + np.abs(a[i-k:i] - a[i]))
    print(dp[-1])



def EDPC_C_vacation():
    """
    3
    10 40 70
    20 50 80
    30 60 90
    ans 210
    
    1
    100 10 1
    ans 100
    
    7
    6 7 8
    8 8 3
    2 5 2
    7 8 6
    4 6 8
    2 3 4
    7 5 1
    ans 46
    8, 8, 5, 8, 8, 4, 7 -> 48
    8, 8, 5, 7, 8, 3, 7 -> 46
    """
    n = int(input())
    a = np.array([list(map(int, input().split())) for i in range(n)])  
    arr = a
    dp = [[0, 0, 0] for _ in range(n)]
    dp[0] = arr[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
    print (max(dp[-1]))


def EDPC_D_knapsack():
    """
    3 8
    3 30
    4 50
    5 60
    ans 90
    
    5 5
    1 1000000000
    1 1000000000
    1 1000000000
    1 1000000000
    1 1000000000
    ans 5000000000(>int32)
    
    6 15
    6 5
    5 6
    6 4
    6 6
    3 5
    7 2
    ans 17
    """
    N, W = map(int, input().split())
    WV = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype="int64")
    dp = np.zeros(W + 1, dtype="int64")
    for w, v in WV:
        dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    print(dp[-1])


def EDPC_E_knapsack():
    """
    3 8
    3 3
    4 5
    5 6
    ans 9
    
    6 15
    6 5
    5 6
    6 4
    6 6
    3 5
    7 2
    ans 17
    
    N<100, W<10*9
    wi<10**9, vi<10**3 
    """
    N, W = map(int, input().split())
    WV = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype="int64")
    Wsum = np.sum(WV[:, 0])
    Vsum = np.sum(WV[:, 1])
    
    dp = np.full(Vsum+1, Wsum, dtype="int64")
    for w, v in WV:
        dp[:Vsum-v+1] = np.min(np.vstack([dp[:Vsum-v+1], dp[v:] - w]), axis=0)
    
    print(dp[dp < W+1].size - 1) # == np.where(dp < W+1)[0][-1]

    
EDPC_B_flog()


Measured memory_bytes: 22944
#include <stdio.h>

#define MAX 100005
#define NIL -1

typedef struct {int p, l, r;} Node;

Node T[MAX];
int n, D[MAX];

void print(int u) {
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if( T[u].p == NIL ) printf("root, ");
  else if( T[u].l == NIL ) printf("leaf, ");
  else printf("internal node, ");

  printf("[");

  for(i=0, c=T[u].l; c != NIL; i++, c=T[c].r) {
    if(i) printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

void rec(int u, int p) {
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r,p);
  if(T[u].l != NIL) rec(T[u].l,p+1);
}

int main(void) {
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i=0;i<n;i++) {
    scanf("%d %d",&v,&d);
    for(j=0;j<d;j++) {
      scanf("%d",&c);
      if(j==0) T[v].l=c;
      else T[l].r =c;
      l = c;
      T[c].p = v;
    }
  }
  for(i=0;i<n;i++) {
    if(T[i].p == NIL) r = i;
  }
  
  rec(r,0);
  
  for(i=0;i<n;i++) print(i);
  
  return 0;
}



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

B = []

for _ in range(K):
    d = int(input())
    B += list(map(int, input().split()))

B = list(set(B))

cnt = 0
for i in range(1, N + 1):
    if i not in B:
        cnt += 1

print(cnt)


Measured memory_bytes: 9184
#include <bits/stdc++.h>
using  namespace std;
int main(){
  long long n, a, sumCost = 0, ans;
  cin >> n;
  vector<long long> A, cost;
  A.push_back(0);
  for(int i=1;i<n+1;i++){
    cin >> a;
    A.push_back(a);
  }
  A.push_back(0);
  for(int i=0;i<n+1;i++){
    cost.push_back(abs(A[i+1] - A[i]));
    sumCost += cost[i];
  }
  for(int i=1;i<n+1;i++){
    ans = sumCost - (cost[i-1] + cost[i]) + abs(A[i+1] - A[i-1]);
    cout << ans << endl;
  }
  return 0;

}


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

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

int N;
int x[100010];
int y[100010];
int num[210000];

bool ok(int t) {
	ll need = ((ll)(N + 1) * N / 2) / 2 + 1;
	memset(num, 0, sizeof(num));

	const int B = 100010;

	int d = B;
	++num[d];
	int prefix = 0;

	ll cnt = 0;

	rep(i, N) {
		if (x[i] <= t) {
			prefix += num[d];
			++d;
		} else {
			prefix -= num[d-1];
			--d;
		}
		cnt += prefix;
		++num[d];
	}

	return cnt >= need;
}

int main() {
	cin >> N;

	rep(i, N) {
		cin >> x[i];
		y[i] = x[i];
	}
	sort(y, y + N);

	int lo = 0, hi = N;
	if (ok(y[0])) hi = 0;

	while (hi - lo > 1) {
		int t = (lo + hi) / 2;
		if (ok(y[t])) {
			hi = t;
		} else {
			lo = t;
		}
	}

	cout << y[hi] << endl;

	return 0;
}

Measured memory_bytes: 1792
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Monmo momo = new Monmo(n);
        Monmo momo2 = new Monmo(n);
        List<Integer> plist = new ArrayList<Integer>();
        List<Integer> qlist = new ArrayList<Integer>();
        
        for(int i=0;i<n;i++){
            int p = sc.nextInt();
            plist.add(p);
        }
        for(int i=0;i<n;i++){
            int q = sc.nextInt();
            qlist.add(q);
        }
        int psum=0;
        for(int i=0;i<n;i++){
            psum+=momo.check(plist.get(i))*fact(n-1-i);
        }
        int qsum=0;
        for(int i=0;i<n;i++){
            qsum+=momo2.check(qlist.get(i))*fact(n-1-i);
        }
        System.out.println((int)Math.abs((psum+1)-(qsum+1)));
        
    }
    
    static int fact(int n){
        if(n==0)return 1;
        return n*fact(n-1);
    }
}

class Monmo {
    int n;
    List<Integer> list = new ArrayList<Integer>();
    
    Monmo(int n){
        this.n = n;
        for(int i=0;i<n;i++){
            list.add(i+1);
        }
    }
    
    int check(int c){
        for(int i=0;i<list.size();i++){
            if(c==list.get(i)){
                list.remove(i);
                return i;
            }
        }
        System.out.println("ここは通らない");
        System.exit(0);
        return 0;
    }
}



Measured memory_bytes: 35672
use std::io::*;
use std::str::FromStr;
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main(){
    let a:i32 = read();
    let b:i32 = read();
    let c:i32 = read();
    println!("{} {} {}",c,a,b);
}

Measured memory_bytes: 4352
n, m = gets.split.map(&:to_i)
mat = []
(1..n).each do |_x|
  mat << gets.split.map(&:to_i)
end
v = []
(1..m).each do |_x|
  v << gets.to_i
end

ans = [0] * n
(0...n).each do |x|
  (0...m).each do |y|
    ans[x] += mat[x][y] * v[y]
  end
end
puts ans.join("\n") + "\n"

Measured memory_bytes: 8860
n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
broken.sort()
broken += [0] * (n-m)
index = 0
mod = 10**9 + 7
for i in range(1,n+1):
  if i==1:
    if i != broken[index]:
      a=1
      b=1
    else:
      a=1
      b=0
      index += 1
  else:
    if i == broken[index]:
      a,b=b,0
      index += 1
    else:
      a,b=b,(a+b)%mod
print(b)

Measured memory_bytes: 7056
from collections import Counter
from scipy.misc import comb

N, M = map(int, input().split())
A = list(map(int, input().split()))

# mod累積和
X = [0]
for a in A:
    X.append((X[-1] + a) % M)

C = Counter(X)
ans = 0
for v in C.values():
    ans += comb(v, 2, 1)

print(ans)


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

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


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

int main() {
    int n, m, x;
    cin >> n >> m >> x;

    int min = 0, max = 0, tmp;
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        if (tmp < x) {
            min++;
        } else {
            max++;
        }
    }

    cout << (min < max ? min : max) << endl;

    return 0;
}


Measured memory_bytes: 3584
#include<stdio.h>
int main(){
int a,b,c,d,e,f,g,h,x,y;
scanf("%d %d\n%d %d\n%d %d %d %d %d",&a,&b,&c,&d,&e,&f,&g,&h);
x=a*e+b*f;
y=c*e+d*f;
if(a>=10){
x=x+a/10*g;
}
if(b>=20){
x=x+b/20*h;
}
if(c>=10){
y=y+c/10*g;
}
if(d>=20){
y=y+d/20*h;
}
if(x>y){
printf("hiroshi\n");
}
else if(x<y){
printf("kenjiro\n");
}
else{
printf("even\n");
}
return 0;
}


Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i > n; --i)
const int MOD = 1000000007;

int main() {
    int a; cin >> a;
    cout << 3 * a * a << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;

int main() {
	//freopen("in","r",stdin);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n;
	std::cin >> n;
	int a[n];
	for (int i = 0; i < n; ++i) std::cin >> a[i];
	LL r = 0;
	for (int i = 1; i < n; ++i) if (a[i] < a[i - 1]) {
		r += a[i - 1] - a[i];
		a[i] = a[i - 1];
	}
	std::cout << r << std::endl;
	return 0;
}

Measured memory_bytes: 4424
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
#include <cassert>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 62;
//const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll conbinationMemo[100][100];

void cmemoInit(){
    rep(i, 100){
        rep(j, 100){
            conbinationMemo[i][j] = -1;
        }
    }
}
 
ll nCr(ll n, ll r){
    if(conbinationMemo[n][r] != -1) return conbinationMemo[n][r];
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return conbinationMemo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
//-----------------------ここから-----------
vector<vector<ll>> gx;
vector<vector<ll>> gy;
vector<int> visitedx;
vector<int> visitedy;
void dfs(ll now, ll xy, ll &cntx, ll &cnty){
    if(xy == 0){
        visitedx[now] = 1;
        cntx++;
    } else {
        visitedy[now] = 1;
        cnty++;
    }

    if(xy == 0){
        rep(i, gx[now].size()){
            ll next = gx[now][i];
            if(visitedy[next]) continue;
            visitedy[next] = 1;
            dfs(next, !xy, cntx, cnty);
        }
    } else {
        rep(i, gy[now].size()){
            ll next = gy[now][i];
            if(visitedx[next]) continue;
            visitedx[next] = 1;
            dfs(next, !xy, cntx, cnty);
        }
    }
}
int main(void){
    ll n;
    cin >> n;
    gx.resize(100100);
    gy.resize(100100);
    rep(i, n){
        ll x, y;
        cin >> x >> y;
        x--, y--;
        gx[x].push_back(y);
        gy[y].push_back(x);
    }

    visitedx.resize(100100, 0);
    visitedy.resize(100100, 0);
    ll ans = 0;
    for(int i = 0; i < 100100; i++){
        if(visitedx[i]) continue;
        ll cntx = 0;
        ll cnty = 0;
        dfs(i, 0, cntx, cnty);
        ans += cntx * cnty;
    }

    cout << ans - n << endl;
    
}


Measured memory_bytes: 11776
import itertools
N,M=map(int,input().split())
ks=list(list(map(int,input().split())) for _ in range(M))
P=list(map(int,input().split()))
L=[0,1]
LL=list(itertools.product(L,repeat=N))
ans=0
sum=[]
msum=0
for I in LL:
    sum=[]
    for J in ks:
        msum=0
        for k in range(1,J[0]+1):
            msum+=I[J[k]-1]
        sum.append(msum)
    if all(sum[i]%2==P[i] for i in range(M)):
        ans+=1
print(ans)

Measured memory_bytes: 3188
import numpy as np

N = int(input())
r = input().split()
H = np.array(r, dtype='int')[::-1]

out = 'Yes'

h = H[0]
for i in range(N):
  h_next = H[i]
  if h_next > h + 1:
    out = 'No'
    break
  elif h_next == h + 1:
    h_next -= 1
    h = h_next
  else:
    h = h_next

print(out)




Measured memory_bytes: 24624
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

int div_up(int a, int b)
{
    return (a + b - 1) / b;
}

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

    int n, m;
    cin >> n >> m;

    ll res = 0;

    if (n == 1)
    {
        if (m == 1)
            res = 1;
        else
            res = m - 2;

        cout << res << endl;
        return 0;
    }

    if (m == 1)
    {
        if (n == 1)
            res = 1;
        else
            res = n - 2;

        cout << res << endl;
        return 0;
    }

    res += (ll)max(0, n - 2) * (ll)max(0, m - 2);

    res += 4 * (((ll)min(2, n) * min(2, m)) % 2);
    res += (ll)max(0, n - 2) * 2 * (2 * min(3, n)) % 2;
    res += (ll)max(0, m - 2) * 2 * (2 * min(3, m)) % 2;

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

// Manages Union-Find Forest.
class UnionFindForest {
  std::vector<int> parent_;
  std::vector<int> rank_;
  std::vector<int> size_;

public:
  // Initialize forest.
  // parent_[i]=i, rank_[i]=0, size_[i]=1.
  UnionFindForest(const int &n);
  // Get the number of the root of the node q.
  int Root(const int &q);
  // Return true if the roots of x and y is same.
  bool IsSame(const int &x, const int &y);
  // Unite the tree x and tree y.
  void Unite(int x, int y);
  // Get the number of nodes which are the same group as node q.
  int Size(const int &q);
};
UnionFindForest::UnionFindForest(const int &n) {
  parent_.resize(n);
  rank_.resize(n);
  size_.resize(n);
  for (int i = 0; i < n; i++) {
    parent_[i] = i;
    rank_[i]   = 0;
    size_[i]   = 1;
  }
}
int UnionFindForest::Size(const int &q) {
  return size_[Root(q)];
}

int UnionFindForest::Root(const int &q) {
  if (parent_[q] == q) {
    return q;
  } else {
    return parent_[q] = Root(parent_[q]);
  }
}

bool UnionFindForest::IsSame(const int &x, const int &y) {
  return Root(x) == Root(y);
}

void UnionFindForest::Unite(int x, int y) {
  x = Root(x);
  y = Root(y);
  if (x == y) return;
  if (rank_[x] < rank_[y]) {
    parent_[x] = y;
    size_[y] += size_[x];
    size_[x] = 0;

  } else {
    parent_[y] = x;
    size_[x] += size_[y];
    size_[y] = 0;
    if (rank_[x] == rank_[y]) rank_[x]++;
  }
}

struct Edge{
  int x,y,w;
  Edge(int ix,int iy,int iw):x(ix),y(iy),w(iw){};
  bool operator<(const Edge& a)const{
    return w<a.w;
  }
};

int Solve(int n,int m){
  if(m==0)
    return  -1;
  std::vector<Edge> edgevec;
  for(int i=0;i<m;i++){
    int a, b, w;
    cin >> a >> b >> w;
    edgevec.push_back(Edge(a-1, b-1, w));
  }
  std::sort(edgevec.begin(), edgevec.end());

  std::unordered_map<int,int> itr_map;
  itr_map[edgevec.front().w]=0;
  for(int i=1;i<m;i++){
    if(edgevec[i-1].w!=edgevec[i].w){
      itr_map[edgevec[i].w]=i;
    }
  }
  const int INF=INT32_MAX/3;
  int result=INF;
  for(int v=1;v<=10000;v++){
    if(itr_map.find(v)==itr_map.end()) continue;
    UnionFindForest uf(n);
    for(int ei=itr_map[v];ei<m;ei++){
      uf.Unite(edgevec[ei].x,edgevec[ei].y);
      if(uf.Size(0)==n){
        result=std::min(result,edgevec[ei].w-v);
        break;
      }
    }
  }
  if(result==INF) return -1;
  else return result;
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  while(true){
    int n,m;
    cin>>n>>m;
    if(n==0) break;
    cout<<Solve(n,m)<<endl;
  }





  return 0;
}


Measured memory_bytes: 3164
#include <iostream>

using namespace std;

int main() {
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	
	if (a > k) cout << k;
	else if (a <= k && (a + b) > k) cout << a;
	else if ((a + b) <= k && (a + b + c) > k) cout << a - (k - a - b);
	else cout << a - c;
	return 0;
}


Measured memory_bytes: 3636
unittest
{
	assert( [ "010" ].parse.expand.solve == 2 );
	assert( [ "100000000" ].parse.expand.solve == 8 );
	assert( [ "00001111" ].parse.expand.solve == 4 );
	
	assert( [ "11111111" ].parse.expand.solve == 8 );		// 追加ケース
}

import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto s = input.front.to!( dchar[] );
	return tuple( s );
}

auto solve( dchar[] s )
{
	auto ans = s.length.signed;
	for( auto i = 1L; i < s.length; i++ )
	{
		if( s[ i - 1 ] != s[ i ] ) ans = min( ans, max( i, s.length.signed - i ) );
	}
	return ans;
}


Measured memory_bytes: 2968
# https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    result = float('inf')
    for bit in range(1 << N):
        use = []
        for i in range(N):
            if bit & (1 << i):
                use.append(i)
        if len(use) != K:
            continue

        cost = 0
        eye_height = A[0]

        for i in range(1, N):
            a = A[i]
            if a > eye_height:
                eye_height = a
                continue
            elif i in use:
                eye_height = eye_height + 1
                cost += eye_height - a

        # print(bin(bit))
        # print(use)
        # print('cost {}'.format(cost))

        result = min(result, cost)

    print(result)


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

#define jougen 393
int dp[jougen+1][jougen+1];

int main(){
    int n;
    cin >> n;
    int s[n+1],l[n+1],p[n+1];
    int i,j,k;
    for(i=1; i<=n; i++){
        cin >> s[i] >> l[i] >> p[i];
    }
    for(j=0; j<=jougen; j++){
        for(k=0; k<=jougen; k++){
            dp[j][k]=0;
        }
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=jougen; j++){
            for(k=0; k<=jougen; k++){
                if(j-s[i]<0){
                    dp[j][k]=dp[j][k];
                }else if(k-l[i]<0){
                    dp[j][k]=max(dp[j][k],dp[j-s[i]][0]+p[i]);
                }else{
                    dp[j][k]=max(dp[j][k],dp[j-s[i]][k-l[i]]+p[i]);
                }
            }
        }
    }
    int m;
    cin >> m;
    bool nonzero=1;
    int w[m+1];
    for(i=1; i<=m; i++){
        cin >> w[i];
        if(dp[w[i]][w[i]]<=0){
            nonzero=0;
        }
    }
    if(nonzero==1){
        for(i=1; i<=m; i++){
            cout << dp[w[i]][w[i]] << endl;
        }
    }else{
        cout << -1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3720
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        int[] sizes = new int[n];
        
        for(int i = 0 ; i < n ; i++){
            sizes[i] = scan.nextInt();
        }

        // now we play the game in DP.
        boolean[] dp = new boolean[k+1];
        dp[0] = false;
        for(int i = 1 ; i <= k ; i++) {
            // we have to collect all statuses from sizes.
            boolean result = true;
            for(int j = 0 ; j < n ; j++) {
                if(i - sizes[j] >= 0) {
                    result = result && dp[i-sizes[j]]; // if all are false - we would have result = false.
                }
            }
            dp[i] = !result; // if all are false - we would win for sure.
        }
        System.out.println(dp[k] ? "First" : "Second");
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
double ac;
double TLE(){return (double)(clock() - ac) / CLOCKS_PER_SEC;}
void debug_out() { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main(){
 ios::sync_with_stdio(0),cin.tie(0);
 int x,y;
 cin>>x>>y;
 ll m1 = x*2;
 ll mu = x*4;
 if(y<m1||y>mu)cout<<"No\n";
 else {
  if(y%2==0)cout<<"Yes\n";
  else cout<<"No\n";
 }
}

Measured memory_bytes: 3616
_N, _M = [int(_) for _ in input().split()]


def calc(N, M):
    ans = 0

    def hashicco(n, m):
        tmp = 1
        if n > 1:
            tmp += 1
        if m > 1:
            tmp += 1
            if n > 1:
                tmp += 1
        res = tmp % 2
        if n > 1:
            res *= 2
        if n > 1:
            res *= 2
        return res

    # ans += hashicco(N, M)

    v = 0
    if M > 2 and N == 1:
        v += M - 2
    h = 0
    if N > 2 and M == 1:
        h += N - 2

    return hashicco(N,M)+v+h


res = calc(_N, _M)

if _N >= 3 and _M >= 3:
    res += (_N - 2) * (_M - 2)
print(res)

Measured memory_bytes: 3064
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >>n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++)
        cin >>arr[i];
    int start = 0, ans = 0;
    for(int i = 1; i < n; i++){
        if(arr[i] > arr[i-1])
            // we can move forward
            start = i;
        // keep on updating the maximum number of moves till ith index
        ans = max(ans, i - start);
    }
    cout <<ans;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <iomanip>
#include <math.h>
#include <vector>

int main(int argc, char **argv){
	int n = 0;
	std::vector<int> x;
	std::vector<int> y;
	double d = 0;

	std::cin >> n;

	x.resize(n, 0);
	y.resize(n, 0);

	for(int i = 0; i < n; i++){
		std::cin >> x[i];
	}
	for(int i = 0; i < n; i++){
		std::cin >> y[i];
	}

	//p = 1
	d = 0;
	for(int i = 0; i < n; i++){
		d += abs(x[i] - y[i]);	
	}
	std::cout << std::fixed << std::setprecision(6) << d << std::endl;

	//p = 2
	d = 0;
	for(int i = 0; i < n; i++){
		d += pow(x[i] - y[i], 2.0);	
	}
	std::cout << std::fixed << std::setprecision(6) << sqrt(d) << std::endl;

	//p = 3
	d = 0;
	for(int i = 0; i < n; i++){
		d += pow(abs(x[i] - y[i]), 3.0);	
	}
	std::cout << std::fixed << std::setprecision(6) << cbrtl(d) << std::endl;


	//p = ??? 
	d = 0;
	for(int i = 0; i < n; i++){
		d = std::max<double>(abs(x[i] - y[i]), d);	
	}
	std::cout << std::fixed << std::setprecision(6) << d << std::endl;
	return 0;
}

Measured memory_bytes: 3488
n = int(input())
s = list(input())
e, w = [0] * (n + 1), [0] * (n + 1)
for i in range(n):
    if s[i] == "E":
        e[i + 1] = e[i] + 1
        w[i + 1] = w[i]
    else:
        e[i + 1] = e[i]
        w[i + 1] = w[i] + 1
ans = 364364
for i in range(2, n - 1):
    if ans > e[n] - e[i] + w[i] - w[0]:
        ans = e[n] - e[i] + w[i] - w[0]
if ans > min(w[n - 1], e[n] - e[1]):
    ans = min(w[n - 1], e[n] - e[1])
print(ans)

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

int main(){
  int64_t N; cin >> N;
  vector<int64_t> B(N-1);
  for(int64_t i =0; i<N-1; i++){
    cin >> B.at(i);
  }
  int64_t ans = 0;
  ans = B.at(0) + B.at(N-2);
  for(int64_t i=0; i<N-2; i++){
    ans += min(B.at(i),B.at(i+1));
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
typedef long long ll;
int N, cnt;
map<string, int>m;
int main(){
	cin.tie(0);
	cin.sync_with_stdio(0);
	cin >> N;
	for(int i = 1;i<=N;i++){
		string s; cin >> s;
		if(m[s]==0)m[s] = ++cnt;
	}
	cout << cnt << nl;
	return 0;
}


Measured memory_bytes: 19204
#include <iostream>

int main(){
   long long N, M;
   std::cin >> N >> M;
   
   if(N>=3 && M>=3){
      std::cout << (N-2) * (M-2) << std::endl;
   }else if(N==1 || M==1){
      if(N==1 && M==1) std::cout << 1 << std::endl;
      else std::cout << std::max(N,M)-2 << std::endl;
   }else{
      std::cout << 0 << std::endl;
   }

   return 0;
   
}


Measured memory_bytes: 256
import { count } from 'console';

process.stdin.resume();
process.stdin.setEncoding('utf8');

// 標準入力取込
let gInput = '';
process.stdin.on('data', (chunk) => (gInput += chunk));
process.stdin.on('end', () => main(gInput.split(/\r?\n/)));

// 解答
function main(inputs: string[]): void {
  const [n, m, q] = inputs[0].split(' ').map(Number);
  const list = setArgList(inputs, q);
  // 全パターンの数列Aを取得
  const numListA = initNumList(1, 0, n, m, []);
  let max = 0;

  for (let i = 0; i < numListA.length; i++) {
    let numList = numListA[i];
    let totalScore = 0;
    for (let j = 0; j < q; j++) {
      if (numList[list[j][1] - 1] - numList[list[j][0] - 1] == list[j][2]) {
        totalScore += list[j][3];
      }
    }

    max = Math.max(max, totalScore);
  }

  console.log(max);
}

// 2行目以降の引数を取得
function setArgList(inputs: string[], q: number): number[][] {
  let list: number[][] = [];

  for (let i = 1; i <= q; i++) {
    list.push(inputs[i].split(' ').map(Number));
  }

  return list;
}

// 数列Aの初期化
function initNumList(j: number, k: number, n: number, m: number, list: number[]): number[][] {
  let numList: number[][] = [];

  if (k === n) {
    return [list];
  }

  for (let i = j; i <= m; i++) {
    numList = numList.concat(initNumList(i, k + 1, n, m, list.concat([i])));
  }
  return numList;
}


Measured memory_bytes: 72796
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool ispal(string a)
{
    long long int n=a.length();
    if(n==1)
        return true;
    else{
    int i=0,j;
    j=n-1;
    while(1)
    {
        if(a[i]!=a[j])
        {
            cout<<i<<" "<<j;
           return false;
        }
        i++,j--;
        if(i==j)
         {
        //     cout<<i<<" ";
             break;
        }
    }
    return true;
}}
ll nof(ll n){
    if(n==2)
    {
        return 2;
    }
    ll c=1;
if(n%2==0)
{
    while(n%2==0)
    {
             c++;
        n/=2;
      //  cout<<c<<"--->"<<n<<" ";
    }
    //cout<<endl;
}
for(int i=3;i<=sqrt(n);i++)
{
    if(n%i==0)
    {
        c+=2;
    }
}
if(n>1)
{
    c++;
}
return c;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n;
  cin>>n;
 ll a[n];
 for(int i=0;i<n;i++)
 {
     cin>>a[i];
 }
 ll m=1e18;
 vector<ll>ans(n,m);
ans[0]=0;
for(int i=0;i<n;i++)
{
    for(int j=i+1;j<=i+2;j++)
    {
      if(j<n)
        ans[j]= min(ans[j], ans[i] + abs(a[i]-a[j]));
    }
}
          cout<<ans[n-1];
  }


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

int main() {
  long n, d;
  cin >> n >> d;
  int ans = 0;
  while (n > 0) {
    long x, y;
    cin >> x >> y;
    if (x*x + y*y <= d*d) ans++;
    n--;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3184
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define MOD 1000000007
using namespace std;

int main(void){
	long long n,res=0,welth=0,count=0;
	cin >> n;
	vector<long long> a(n),b(n),c;
	for(int i=0; i<n; i++){
		cin >> a[i];
	}	
	for(int i=0; i<n; i++){
		cin >> b[i];
		if(a[i]<b[i]){
			res+=b[i]-a[i];
			count++;
		}
		else {
			welth+=a[i]-b[i];
			c.push_back(a[i]-b[i]);
		}
	}
	if(welth<res){
		cout << -1 << endl;
		return 0;
	}
	sort(c.begin(),c.end());
	reverse(c.begin(),c.end());
	for(int i=0; i<c.size(); i++){
		if(res<=0)break;
		res-=c[i];count++;
		
	}
	cout << count << endl;
    return 0;
}

Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cerr << #x " = " << (x) << endl;
#define P(x) cerr << #x << endl;    
#define int long long
typedef pair<int, int> pii;
const int mod = 1000000007;


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(9);
    
    
    int n, k;
	cin >> n >> k;
	vector<int> h(n + 10);
	vector<int> dp(n + 10, 1e18);
	
	for(int i = 1; i <= n; ++ i)
	{
		cin >> h[i];
	}
	
	dp[1] = 0;
	for(int i = 2; i <= n; ++ i)
	{
		for(int j = 1; j <= k; ++ j)
		{
			if(i - j <= 0) break;
			dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
		}
	}
	cout << dp[n] << endl;
    
    return 0;
}






Measured memory_bytes: 1792
n=int(input())
vote={}
for i in range(n):
    si=input()
    vi=vote.get(si, 0)
    vote[si]=vi+1

max_v=max(vote.values())

ans=[]
for k,v in vote.items():
    if(v==max_v):
        ans.append(k)
ans.sort()
for i in range(len(ans)):
    print(ans[i])

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

using ll = long long;

#define for_(i,a,b) for(int i = (a);i < (b);i++)
#define rfor_(i,a,b) for(int i = (b)-1;i >= (a);i--)
#define rep(i,n) for_(i,0,(n))
#define rrep(i,n) rfor_(i,0,(n))

int H, W;

int main(){
	cin.tie(0);
	
	while(cin>>H>>W,H||W) {
    	rep(i, H) {
	        rep(j, W)cout<<'#';
	        cout<<endl;
	    }
	    cout<<endl;
	}

	return 0;
}



Measured memory_bytes: 3072
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

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

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

template<typename T>
void inputVector(vector<T> * p, int a){
    rep(i, a){
        T input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

#define Max 110000
int X[Max];
int Xdiff[Max];
int N, M;

int main(int argc, const char * argv[]) {
    N = inputValue();
    M = inputValue();
    inputArray(X, M);
    sort(X, X+M);
    rep(i, M-1) {
        Xdiff[i] = X[i+1] - X[i];
    }
    sort(Xdiff, Xdiff+M-1, greater<int>());

    if (N >= M) {
        output(0);
        return 0;
    }

    int sum = 0;
    repd(i, 0, N-1) {
        sum += Xdiff[i];
    }

    output((X[M-1] - X[0]) - sum);
    return 0;
}

Measured memory_bytes: 1024
import math
a, b, x = map(int, input().split())

if x/a >= (a*b)/2:
    ans = math.degrees(math.atan((2/a)*(b-(x/a**2))))
else:
    ans = math.degrees(math.atan((a*b*b)/(2*x)))
print('{:.10f}'.format(ans))

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

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    vector<int> xs = {a, b, c};
    sort(xs.begin(), xs.end());
    if (xs[0] == 5 && xs[1] == 5 && xs[2] == 7) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){
    int N;
    string S;
    cin >> N >> S;
    vector <int> alpha(26,0); 
    vector <int> beta(26,0);//アルファベット記憶
    int count = 0;
    int maxi = 0;
    REP(i,N){
        alpha[S.at(i) - 'a']++;
    }
    /*REP(i,alpha.size()){
        cout << alpha[i] << " ";
        cout << endl;
    }*/
    REP(i,N){
        alpha[S.at(i) - 'a']--;
        beta[S.at(i) -'a']++;
        if(alpha[S.at(i) - 'a'] == 0 && beta[S.at(i) -'a'] == 1){continue;}
        else if(alpha[S.at(i) - 'a'] == 0 && beta[S.at(i) -'a'] > 1){count--;}
        if(alpha[S.at(i) - 'a'] > 0 && beta[S.at(i) -'a'] == 1){count++;}
        else{continue;}
        maxi = max(maxi,count);
    }

    cout << maxi << endl;

    return 0;

}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INFI = 1000000007;
const int mod = 1000000007;

int main(){
int n;
int alice=0,bob=0;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++){
    cin>>a.at(i);
}
sort(a.begin(),a.end(),greater<int>());
for(int i=0;i<n;i++){
    if(i%2==0){
        alice+=a.at(i);
    }else{
        bob+=a.at(i);
    }
}
cout<<alice-bob<<endl;
}













Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF (1e10)

double dist[1080][1080];
double d[1080][1080];
int cnt[1080];
int q[1080];
int main(){
	int n, s, t;
	while(cin >> n >> s >> t, n | s | t){
		s--,t--;
		for(int i = 0;i < n;i++)cin >> q[i];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				cin >> dist[i][j];
				if(dist[i][j] == 0)dist[i][j] = INF;
				d[i][j] = dist[i][j];
			}
			dist[i][i] = 0;
		}
		for(int i = 0;i < n;i++)
			for(int j  = 0;j < n;j++)
				for(int k = 0;k < n;k++)
					dist[j][k] = min(dist[j][i] + dist[i][k], dist[j][k]);
		if(dist[s][t] == INF){
			cout << "impossible" << endl;
			continue;
		}
		double mat[n][n];
		double ans[n];			
		memset(mat, 0, sizeof(mat));		
		memset(ans, 0, sizeof(ans));
		memset(cnt, 0, sizeof(cnt));
		for(int i = 0;i < n;i++){
			if(i == t){
				mat[t][t] = 1;
				continue;
			}
			for(int j = 0;j < n;j++){
				if(i == j)continue;
				if(dist[i][t] == d[i][j] + dist[j][t] || q[i] == 0 && d[i][j] != INF){
					cnt[i]++;
				}
			}
			for(int j = 0;j < n;j++){
				if(i == j){
					mat[i][j] = 1;
				}
				else if(dist[i][t] == d[i][j] + dist[j][t] || q[i] == 0 && d[i][j] != INF){
					mat[i][j] = -1.0 / cnt[i];
					ans[i] += d[i][j] / cnt[i];
				}
			}
		}                    
		for(int i = 0;i < n;i++){
			double tmp = mat[i][i];
			for(int j = 0;j < n;j++)mat[i][j] /= tmp;
			ans[i] /= tmp;
			for(int j = 0;j < n;j++){
				if(i == j)continue;
				tmp = mat[j][i];
				for(int k = 0;k < n;k++){
					mat[j][k] -= tmp * mat[i][k];
				}
				ans[j] -= tmp * ans[i];
			}
			
		}
		printf("%.10lf\n", ans[s]);
	}
	return 0;
}

Measured memory_bytes: 3848
/*
* Welcome to my code!
*---------------------------------------------*
* author : lynmisakura(twitter : @andoreiji11)
*/

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define repn for(int i = 0;i < n;i++)
#define ain(a) for(auto& i : a)cin >> i;
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size()) 
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define cont continue

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using pi = pair<int,int>;
using vpi = vector<pi>;
using pl = pair<ll,ll>;
using vpl = vector<pl>;

template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;}
template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;}
template<class T> void print(std::vector<T> a){ int sz = a.size();
for(int i=0;i<a.size();i++)cout << a[i] << (i < sz-1 ? ' ' : '\n'); }
void ioboost(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}
///////////////////////////////////////////////////////////

int main(int argc, char const *argv[])
{
	ioboost();
	int k,a,b;cin >> k >> a >> b;
	for(int i =a;i <= b;i++){
		if(i % k == 0){
			cout << "OK" << '\n';
			return 0;
		}
	}	
	cout << "NG" << '\n';
	return 0;
}

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

int main(){
    int m, A, B, C, D; cin >> m;
    A = m/1000; B = (m-1000*A)/100; C = (m - 1000*A - 100*B)/10; D = m - 1000*A - 100*B - 10*C;
    int p = 0;
    for(int i=0; i<2; i++){
      for(int j=0; j<2; j++){
        for(int k=0; k<2; k++){
            if(p > 0){
                break;
            }
            int s, t, u;
            char c_1, c_2, c_3;
            if(i == 0){
                s = A + B;
                c_1 = '+';
            }
            else{
                s = A - B;
                c_1 = '-';
            }
            if(j == 0){
                t = s + C;
                c_2 = '+';
            }
            else{
                t = s - C;
                c_2 = '-';
            }
            if(k == 0){
                u = t + D;
                c_3 = '+';
            }
            else{
                u = t - D;
                c_3 = '-';
            }
            if(u == 7){
                cout << A << c_1 << B << c_2 << C << c_3 << D << '=' << 7 << endl;
                p++;
            }
        }
      }
    }
}

Measured memory_bytes: 256
/**
*   @Author : MeGaCrazy
*   @InitTime : Wed Jan 02 21:25:15 2019
*   @Idea :
*
*
*
*
*
*  Happy Solving :)
**/
#include <bits/stdc++.h>
using namespace std;


long long  solve(long long n){
    stringstream f;
    f<<n;
    long long ans=(f.str().size());
    for(long long i=2;i*i<=n;i++){
        if(n%i==0){
        	long long a=i;
        	long long b=n/i;
    	        stringstream in;
	   in<<a;
	   long long ret=in.str().size();
	   stringstream inn; 
	
	   inn<<b;
	
	   ret=max((long long )inn.str().size(),ret);
           ans=min(ans,ret);

        }

     }
     return ans;	
}
int main(){
#ifndef ONLINE_JUDGE
  // freopen("in","r",stdin);
   //freopen("out","w",stdout);
#endif
   long long n;
   cin>>n;
   cout<<solve(n)<<endl;





}

Measured memory_bytes: 256
s=input()
cnt=0
if s[0]=="<":
    cnt=1
else:
    cnt=-1
l=[]
for i in range(len(s)-1):
    if s[i]=="<":
        if s[i+1]=="<":
            cnt+=1
        else:
            l.append(cnt)
            cnt=-1
    else:
        if s[i+1]==">":
            cnt-=1
        else:
            l.append(cnt)
            cnt=1
l.append(cnt)
ans=0
for i in range(len(l)-1):
    if l[i]>0 and l[i+1]<0:
        a=abs(l[i])
        b=abs(l[i+1])
        ans+=max(a,b)
        ans+=(a-1)*a//2+(b-1)*b//2

if l[0]<0:
    ans+=(abs(l[0])+1)*abs(l[0])//2

if l[-1]>0:
    ans+=(l[-1]+1)*l[-1]//2
print(ans)

Measured memory_bytes: 6300
using System;

namespace ABC160B
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            int b = a / 500;
            int c = (a - b * 500) / 5;
            int x = b * 1000 + c * 5;
            Console.WriteLine(x);
            
        }
    }
}

Measured memory_bytes: 13140
#include<stdio.h>

int main(){
  int N, M, i, j, k = 0, S[10000], T[500];
  
  scanf("%d", &N);
  for(i = 0; i < N; i++){
    scanf("%d", &S[i]);
  }
  
  scanf("%d", &M);
  for(i = 0; i < M; i++){
    scanf("%d", &T[i]);
  }
  
  /*N(S)??§?????????M(T)??¨??????*/
  if(N >= M){
    for(i = 0; i < M; i++){
      for(j = 0; j < N; j++){
        if(T[i] == S[j]){
          k += 1; 
          break;
        }
      }
    }
  }
  
  else{/*M(T)??§?????????N(S)??¨??????*/
    for(i = 0; i < N; i++){
      for(j = 0; j < M; j++){
        if(S[i] == T[j]){
          k += 1;
          break;
        }
      }
    }
  }
  
  printf("%d\n",k);
  
  return 0;
}

Measured memory_bytes: 1804
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
l=[list(map(int,input().split())) for i in range(m)]
l.sort(key=lambda x:x[1])
for i in range(n):
    if a[i]<l[-1][1]:
        a[i]=l[-1][1]
        l[-1][0]-=1
        if l[-1][0]==0:
            l.pop(-1)
            if len(l)==0:break
    else:break
print(sum(a))

Measured memory_bytes: 32840
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<fstream>
#include<sstream>
#include<queue>
#include<iterator>
#include<stack>

using namespace std;

#define st first
#define nd second
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REV(a) reverse(a.begin(),a.end())
#define SORT(a) sort(a.begin(),a.end())
#define inf (int)1e9
#define linf (long long)1e18

typedef long long ll;
typedef short int si;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;

int n,a[100000],mx=0,mm;
long int ans=0;

int main() {
		cin>>n;
		FOR(i,0,n)cin>>a[i],mx=max(mx,a[i]),mm=min(mm,a[i]);
		sort(a,a+n);
		FOR(i,mm-1,mx+1){
				ans=max(ans,upper_bound(a,a+n,i+1)-lower_bound(a,a+n,i-1));
		}
		cout<<ans<<endl;




  return 0;
}


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

using namespace std;

int main(){
	vector<int> check(10, 0);
	for (int i=0; i<4; i++){
		int a;
		cin >> a;
		check[a] = 1;
	}

	if ((check[1] > 0) && (check[7] > 0) && (check[9] > 0) && (check[4] > 0)){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<map>
#include<cmath>
int main() {
    long long int N,P,sub,ans;
    std::cin>>N>>P;
    ans=1;
    sub=P;
    std::map <long long int ,long long int>yaku;
    if(N==1){
        std::cout<<P<<std::endl;
        return 0;
    }
    yaku[1]=N;
    for(long long int i=2;i*i<=P;i++){
        while(sub%i==0){
            yaku[i]++;
            sub=sub/i;
        }
        if(sub==1)break;
    }
    for(auto i:yaku){
        auto key=i.first;
        auto y=i.second;
        if(y>=N){
            for(int j=1;j<=y/N;j++){
                ans*=key;
            }
        }
    }
    std::cout<<ans<<std::endl;
    return 0;
}

Measured memory_bytes: 3608