akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
using namespace std;
typedef long long ll;
const int N = 2 * 1e5 + 5;
const ll mod = 1e9 + 7;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
const double E = 1e-9;
ll dp[55][55];
ll C(ll n,ll r){
    if(r > n)return 0;
    if(r == 0 or n == r)
        return dp[n][r] = 1;
    if(dp[n][r] != -1)
        return dp[n][r];
    return dp[n][r] = dp[n][n - r] = C(n - 1,r - 1) + C(n - 1,r);
}
int main(){/*
    freopen("in","r",stdin);
    freopen("out","w",stdout);*/
    cls(dp,-1);
    int n,a,b;
    //scanf("%d %d %d",&n,&a,&b);
    cin >> n >> a >> b;
    ll v[n + 1];
    for(int i = 0; i < n; i++)
        //scanf("%lld",&v[i]);
        cin >> v[i];
    sort(v,v + n);
    reverse(v,v + n);
    double sm = 0;
    fore(i,0,a)
        sm += (double)v[i];
    sm /= (double)a;
    ll mx = 0;
    ll n1 = 0,r1 = 0;
    fore(i,0,n){
        if(v[i] == v[a - 1]){
            n1++;
            if(i < a)
                r1++;
        }
    }
    if(r1 == a){
        while(r1 <= b){
            mx += C(n1,r1);
            r1++;
        }
    }else
        mx = C(n1,r1);
    cout << fixed << setprecision(6) << sm << '\n';
    cout << mx << '\n';
    //printf("%.6lf\n%lld",sum,mx);
    return 0;
}   

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
  ll n;
  cin>>n;
  ll arr[n];
  ll count[n+1]={0};
  for(ll i=0;i<n;i++)
  {
      cin>>arr[i];
      count[arr[i]]++;
  }
  ll sum=0;
  for(ll i=0;i<n+1;i++)
  {
      if(count[i]>1)
      {
          sum = sum + (count[i]*(count[i]-1))/2;
      }
  }
  for(ll i=0;i<n;i++)
  {
      ll ele = arr[i];
      ll temp= sum;
      temp -= (count[ele]*(count[ele]-1))/2;
      count[ele]--;
      if(count[ele]>1)
      {
          temp+=(count[ele]*(count[ele]-1))/2;
      }
      count[ele]++;
      cout<<temp<<endl;
  }
}


Measured memory_bytes: 5760
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)

	fmt.Printf("%.6f", answer(n))
}

func answer(n int) float32 {
	if n%2 == 0 {
		return float32(0.5)
	} else {
		return float32(n+1)/float32(2*n)
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("function min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func minArray(nums *[]int) int {
	res := (*nums)[0]
	for _, v := range *nums {
		res = int(math.Min(float64(res), float64(v)))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("function max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func maxArray(nums *[]int) int {
	res := (*nums)[0]
	for _, v := range *nums {
		res = int(math.Max(float64(res), float64(v)))
	}
	return res
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N; cin >> N;
    map<string, int> M;
    rep(i, N) {
        string s; cin >> s;
        M[s]++;
    }
    cout << "AC x " << M["AC"] << endl;
    cout << "WA x " << M["WA"] << endl;
    cout << "TLE x " << M["TLE"] << endl;
    cout << "RE x " << M["RE"] << endl;
}


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

void chmin(int& a, int b){
    a = min(a, b);
}

const int Tmax = 10000;
int N, M;
int Dst[Tmax];

int dist[400][400], E[400][400], Nxt[400][400];

void initialize(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        E[a][b] = E[b][a] = c;
    }
    int _; cin >> _;
    for(int i=0; i<Tmax; i++){
        int n; cin >> n;
        if(n) cin >> _ >> Dst[i];
        Dst[i]--;
    }

    for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(i != j) dist[i][j] = (E[i][j] ? E[i][j] : 1e9);
    for(int k=0; k<N; k++) for(int i=0; i<N; i++) for(int j=0; j<N; j++) chmin(dist[i][j], dist[i][k] + dist[k][j]);
    for(int i=0; i<N; i++) for(int j=0; j<N; j++){
        for(int k=0; k<N; k++) if(i != k && E[i][k] && E[i][k] + dist[k][j] == dist[i][j]){
            Nxt[i][j] = k;
            break;
        }
    }
}

vector<int> ans;
int stock[400], have[400], havesum;
int pos, now;
int scorenum = 0;

void addtime(){
    now++;
    if(now < Tmax && Dst[now] >= 0) stock[Dst[now]]++;
}
void visit(int v){
    if(v == 0) for(int i=0; i<N; i++){
        have[i] += stock[i];
        havesum += stock[i];
        stock[i] = 0;
    }
    scorenum += have[v];
    havesum -= have[v];
    have[v] = 0;
}

void moveto(int v){
    if(pos == v){
        addtime();
        ans.push_back(-1);
        visit(pos);
        return;
    }
    while(pos != v){
        int nxt = Nxt[pos][v];
        int d = E[pos][nxt];
        while(d--){
            addtime();
            ans.push_back(nxt);
        }
        pos = nxt;
        visit(nxt);
    }
}

int main(){
    initialize();
    cerr << Nxt[0][3] << endl;
    while(ans.size() < Tmax){
        if(havesum > 0){
            int nxt = -1;
            for(int i=0; i<N; i++) if(have[i]) if(nxt == -1 || dist[pos][nxt] > dist[pos][i]) nxt = i;
            moveto(nxt);
        }else{
            moveto(0);
        }
    }
    ans.resize(Tmax);
    for(int a : ans) cout << (a == -1 ? -1 : a+1) << endl;
}


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

namespace AOJ_ITP_1_4_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int a = int.Parse(s[0]);
            int b = int.Parse(s[1]);
            Console.WriteLine("{0} {1} {2:f5}", a/b, a%b, 1.0*a/b);
        }
    }
}



Measured memory_bytes: 18004
use std::cmp::{min, max};
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:i64 = read();
    let b:i64 = read();
    let c:i64 = read();
    let d:i64 = read();
    println!("{}", max(0, min(d, b) - max(c, a)));
}

Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int H, W;
  cin >> H >> W;
  string S[50];
  
  for(int i = 0; i < H; i++){
    cin >> S[i];
  }
  
  int x[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
  int y[8] = {  1, 1, 1,  0, 0, -1,-1,-1 };
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(S[i][j] == '#') continue;
      int C = 0;
      
      for(int k = 0; k < 8;k++){
        if(j + x[k] < 0 || j + x[k] >= W) continue;
        if(i + y[k] < 0 || i + y[k] >= H) continue;
        if(S[i + y[k]][j + x[k]] == '#') C++;
      }
      S[i][j] = char(C + '0');
    }
  }
  
  for(int i = 0; i < H; i++) cout << S[i] << endl;
 
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

int N, K;
ll h[100010];
ll dp[100010];

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

  cin>>N;
  K=2;
  rep(i,N)cin>>h[i];
  rep(i,N+1)dp[i]=INF;
  dp[0]=0;
  repl(i,1,N){
    repl(j,max(0LL,i-K),i)minch(dp[i],dp[j]+(ll)abs(h[i]-h[j]));
  }
  cout<<dp[N-1]<<endl;

  return 0;
}


Measured memory_bytes: 1792
def upper_cnt(a, b):
    upper_cnt = n-b + 1
    a += upper_cnt
    upper_cnt += ((n-a) // 2)    
    return upper_cnt

def lower_cnt(a, b):
    lower_cnt = a-1 + 1
    b -= lower_cnt
    lower_cnt += ((b-1) // 2)
    return lower_cnt

n, a, b = map(int, input().split())

if 0 == (b-a) % 2:
    print((b-a) // 2)

else:
    up = upper_cnt(a, b)
    low = lower_cnt(a, b)
    print(min(up, low))


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

int main(){
    int n;
    cin >> n;
    int sum=0, minodd=111;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        sum += a;
        if(a<minodd and a%2==1){
            minodd = a;
        }
    }
    if(sum%2 == 0){
        cout << sum/2 << endl;
    }else{
        cout << (sum-minodd)/2 << endl;
    }
    return 0;
}



Measured memory_bytes: 3100
N, X = map(int, input().split())
m = []
for _ in range(N):
    m.append(int(input()))

SUM = sum(m)
MIN = min(m)


if SUM < X:
    REST = X - (SUM)
    ans = REST//MIN
    print(ans + N)
    
else:
    print(N)

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

int main() {
	int midt, endt, ret;
	while (1){
		cin >> midt >> endt >> ret;
		if (midt == -1 && endt == -1 && ret == -1) break; 
		else if (midt == -1 || endt == -1) cout << "F" << endl;
		else if (midt + endt >= 80) cout << "A" << endl;
		else if (midt + endt >= 65) cout << "B" << endl;
		else if (midt + endt >= 50 || (midt + endt >= 30 &&ret >= 50)) cout << "C" << endl;
		else if (midt + endt >= 30) cout << "D" << endl;
		else if (midt + endt < 30) cout << "F" << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <stdlib.h>

#define N 2000001
#define k 10000

void countingSort(unsigned short *, unsigned short *);

int n;

int main(){
  unsigned short *a, *b;
  int c;
  scanf("%d",&n);

  a = malloc(sizeof(short)*n+1);
  b = malloc(sizeof(short)*n+1);
  
  for(c = 0; c < n; c++) scanf("%d",&a[c]);

  countingSort(a,b);

  for(c = 1; c < n; c++) printf("%d ",b[c]);
  printf("%d\n",b[c]);

  return 0;
}

void countingSort(unsigned short *x, unsigned short *y){
  int a;
  int z[k+1];
  for(a = 0; a < k+1; a++) z[a] = 0;
  for(a = 0; a < n; a++) z[x[a]]++;
  for(a = 1; a < k+1; a++) z[a] = z[a] + z[a-1];
  for(a = n-1; a >= 0; a--){
    y[z[x[a]]] = x[a];
    z[x[a]]--;
  }
}



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

int main() {
  int N;
  cin >> N;
  set<int> S;
  rep(i,N){
    int x = 0;
    cin >> x;
    S.insert(x);
  }
  if(N == S.size()){
    cout << "YES";
  }
  else{
    cout << "NO";
  }
}

Measured memory_bytes: 12964
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const double PI=3.14159265358979323846;

int main(){

int n;
  string b;
  cin>>n>>b;
  vector<char> c(n);
  vector<char> d(0);
  rep(i,n) c.at(i) = b.at(i);
 int ans =0;
  
  for(int i =0;i<n-1;i++){
    if(c.at(i)!= c.at(i+1)){
       d.push_back(c.at(i));
    }
  }
  cout<<d.size()+1<<endl;
}

Measured memory_bytes: 640
#include<iostream>

using namespace std;

typedef unsigned long long ull;

ull gcd(ull a, ull b) {	// 最大公約数
	//while ((a = a % b) != 0) swap(a, b);
	ull r;

	while ((r = a % b) != 0) {
		//if (r > b - r) r = b - r;
		a = b;
		b = r;
	}

	return b;
}

ull lcm(ull a, ull b) {	// 最小公倍数
	return a * b / gcd(a, b);
}

int main() {
	ull a, b;

	while (cin >> a >> b) {
		cout << gcd(a, b) << " " << lcm(a, b) << endl;
	}

	return 0;
}

Measured memory_bytes: 0
package main

import "fmt"

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

	ans := 0
	p := 0
	var a int
	for i := 0; i < n; i++ {
		fmt.Scan(&a)
		if p == a {
			ans++
			p = 0
		} else {
			p = a
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 512
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
x = LIST()
ans = inf
for p in range(1, 101):
    tmp2 = 0
    for xx in x:
        tmp2 += (xx - p) ** 2
    if ans > tmp2:
        ans = tmp2
print(ans)

Measured memory_bytes: 59884
(* O(n) *)
let n, k = Scanf.scanf " %d %d" @@ fun a b -> a, b
let s = Scanf.scanf " %s" @@ fun s -> s
let rec f acc i c m =
  if i >= n then List.rev @@ (if c = '1' then m :: acc else 0 :: m :: acc)
  else if s.[i] <> c then f (m :: acc) (i + 1) s.[i] 1
  else f acc (i + 1) s.[i] (m + 1)
let base = f [] 0 '1' 0 |> Array.of_list
let m = Array.length base
let sums = Array.make (m + 1) 0
let ans = ref 0
let _ =
  if (m - 1) / 2 <= k then (Printf.printf "%d\n" n; exit 0);
  Array.iteri (fun i c -> sums.(i + 1) <- sums.(i) + c) base;
  for i = 0 to (m - 2 * k - 1) / 2 do
    ans := max !ans @@ sums.(2 * (i + k) + 1) - sums.(2 * i)
  done;
  Printf.printf "%d\n" !ans

Measured memory_bytes: 8448
n = int(raw_input())
a = []

total = 0
for i in range(n):
    ai = raw_input()
    ai = map(lambda x: x == '#', ai)
    a.append(ai)
    total += sum(ai)

if total == 0:
    print -1
    exit()

b = [0] * n
for i in range(n):
    flag = 0
    for j in range(n):
        flag |= a[j][i]
    b[i] = flag^1

col = 0
for j in range(n):
    flag = 1
    for i in range(n):
        flag &= a[i][j]
    col += flag

ans = float('inf')
for i in range(n):
    total = 0
    flag = 0
    for j in range(n):
        if a[i][j] == 0:
            total += 1
            flag |= 1
    ans = min(ans, total + (flag&b[i]) + n-col)

print ans

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define GET_ARRAY_SIZE(a)   (sizeof(a)/sizeof(a[0]))
int main(){
    int64_t h,w;
    cin >> h >> w;
    if(h == 1 || w == 1){
        cout << 1 << endl;
    }else{
        cout << (h*w/2)+(h*w%2) << endl;        
    }


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;
typedef long long llong;
typedef long double ldouble;

int main()
{
  string ans = "No";
  vector<int> A1(3);
  vector<int> A2(3);
  vector<int> A3(3);
  int N;
  for(int i=0; i<3; ++i) cin >> A1.at(i);
  for(int i=0; i<3; ++i) cin >> A2.at(i);
  for(int i=0; i<3; ++i) cin >> A3.at(i);
  cin >> N;
  vector<int> b(N);
  vector<int> a1(3,0);
  vector<int> a2(3,0);
  vector<int> a3(3,0);
  for(int j=0; j<N; ++j) {
    int hoge;
    cin >> hoge;
    for(int i=0; i<3; ++i){
      if(A1.at(i)==hoge) a1.at(i) = 1;
      if(A2.at(i)==hoge) a2.at(i) = 1;
      if(A3.at(i)==hoge) a3.at(i) = 1;
    }
  }
  for(int i=0; i<3; ++i){
    if(a1.at(i) == 1) {
      if(a2.at(i)==1) {
        if(a3.at(i)==1) ans="Yes";
      }
    }
  }
  if(a1.at(0) == 1) {
    if(a1.at(1)==1) {
      if(a1.at(2)==1) ans="Yes";
    }
  }
  if(a2.at(0) == 1) {
    if(a2.at(1)==1) {
      if(a2.at(2)==1) ans="Yes";
    }
  }
  if(a3.at(0) == 1) {
    if(a3.at(1)==1) {
      if(a3.at(2)==1) ans="Yes";
    }
  }
  if(a1.at(0) == 1) {
    if(a2.at(1)==1) {
      if(a3.at(2)==1) ans="Yes";
    }
  }
  if(a1.at(2) == 1) {
    if(a2.at(1)==1) {
      if(a3.at(0)==1) ans="Yes";
    }
  }
  cout << ans << endl;
}




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

using namespace std;

int main() {

	int s;
	cin >> s  ;

	vector<int> a;
	a.push_back(s);

	int counter = 0;
	while (1) {
		if (a[counter] % 2 == 0) {
			a.push_back(a[counter]/ 2);
		}
		else {
			a.push_back(3 * a[counter] + 1);
		}
		for (int i = 0; i < counter + 1; i++) {
			if (a[counter + 1] == a[i]) {
				cout << counter + 1 + 1 << endl;
				return 0;
			}
		}
		counter++;
	}

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> h(n), dp(n + k, INF);
  for (int i = 0; i < n; i++) cin >> h[i];
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= k; j++) {
      dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
    }
  }
  cout << dp[n - 1] << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
struct cube{
  int x,y,z;
  cube(){}
  cube(int x,int y,int z):x(x),y(y),z(z){}
};
#define MAX 3000
bool used[MAX];
int c[MAX][MAX];
vector<cube> vc;
vector<int> vi;
vector<vector<int> > G;
bool dfs(int v,int p){
  bool f=false;
  if(used[v]) return true;
  vi.push_back(v);used[v]=1;
  for(int i=0;i<G[v].size();i++) {
    if(i&&!~p) reverse(vi.begin(),vi.end());
    if(G[v][i]!=p) f|=dfs(G[v][i],v);
  }
  return f;
}
int main(){
  int n,k,s,i,j,l,t;
  while(cin>>n>>k>>s,n||k||s){
    int ans=-1;
    memset(c,0,sizeof(c));
    G.clear();G.resize(n);
    vc.clear();vc.resize(n);
    for(i=0;i<n;i++) cin>>vc[i].x>>vc[i].y>>vc[i].z;
    for(i=0;i<n;i++){
      for(j=i+1;j<n;j++){
        int xx=s-abs(vc[i].x-vc[j].x),
          yy=s-abs(vc[i].y-vc[j].y),
          zz=s-abs(vc[i].z-vc[j].z);
        if(xx>0&&yy>0&&zz>0){
          G[i].push_back(j);
          G[j].push_back(i);
          c[i][j]=c[j][i]=(xx*yy+yy*zz+zz*xx)*2;
        }
      }
    }
    memset(used,0,sizeof(used));
    for(i=0;i<n;i++){
      if(used[i]) continue;
      vi.clear();
      bool f=dfs(i,-1);
      if(vi.size()<k) continue;
      t=0;
      if(f){
        if(vi.size()==k){
          for(j=0;j<k;j++) t+=c[vi[j]][vi[(j+1)%k]];
          ans=max(ans,t);
        }else{
          for(j=0;j<k-1;j++) t+=c[vi[j]][vi[j+1]];
          ans=max(ans,t);
          int si=vi.size();
          for(j=0;j<si;j++){
            t+=c[vi[(k-1+j)%si]][vi[(k+j)%si]]-c[vi[j%si]][vi[(j+1)%si]];
            ans=max(ans,t);
          } 
        }
      }else{
        for(j=0;j<k-1;j++) t+=c[vi[j]][vi[j+1]];
        ans=max(ans,t);
        for(j=0;j<vi.size()-k;j++){
          t+=c[vi[k-1+j]][vi[k+j]]-c[vi[j]][vi[j+1]];
          ans=max(ans,t);
        } 
      }
    }
    if(~ans) cout << s*s*6*k-ans << endl;
    else cout << -1 << endl;
  }
  return 0;
}

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

public class Main {
    public static void main(String[] args) throws IOException {

        int[] count = new int['z' - 'a' + 1];

        int c;
        while ((c = System.in.read()) != -1) {
            if (Character.isLetter(c)) {
                if (Character.isUpperCase(c))
                    c = Character.toLowerCase(c);
                count[c - 'a']++;
            }
        }

        for (int i = 0; i < count.length; i++)
            System.out.printf("%c : %d\n", 'a' + i, count[i]);
    }
}



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

int main(){
string S;
cin >> S;
sort(S.begin(),S.end());
if(S.at(0) == S.at(1)&&S.at(2) ==S.at(3)&&S.at(1) !=S.at(2)){
cout << "Yes" <<endl;
}

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin >>a>>b;
	if(b==1) cout <<" 0" <<endl;
	else{
		int i,sum=1;
		for( i=1;sum<b;i++)
		{
			sum = sum+a-1;
		}
		cout << i-1 <<endl;
	}
	
}

Measured memory_bytes: 384
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
 
using ll = long long;
using P = std::pair<ll, ll>;
 
#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << i << std::endl
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
ll pow_mod(ll a, ll b, ll mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  ll x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
 
 
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  ll n;
  std::cin>>n;

  ll ans=LLONG_MAX;

  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      chmin(ans,i+n/i-2);
    }
  }

  std::cout<<ans;
 
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;

bool ok(string s)
{
        rep(i, 0, len(s)) {
                if (s[i] != s[0]) return false;
        }
        return true;
}

int main()
{
        ll N;
        cin >> N;
        rep(i, N, inf) {
                string tmp = to_string(i);
                if (ok(tmp)) {
                        cout << i << endl;
                        return 0;
                }
        }
}

Measured memory_bytes: 3596
//Date: 28/12/19
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PI acos(-1)
#define pi 3.1415926535897932384
#define INF 2147483647
#define EPS 1e-8
#define MOD 1000000007
#define MAX 200005
using namespace std;

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

int Set(int mask, int pos){return mask = mask | (1<<pos);}
bool check(int mask, int pos){return (bool)(mask & (1<<pos));}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, a, b;

    cin>>n>>a>>b;

    if((b - a) % 2 == 0){
        ll ans = (b - a) / 2;
        ans = min(ans, min(b - 1, n - a));
        cout<<ans<<endl;
    }
    else{
        ll ans, res;
        ll ta = a, tb = b;
        ans += (n - tb);
        ta += (n - tb) + 1;
        ans++;
        ans += (n - ta) / 2;
        res = ans;
        ans = 0;
        ta = a, tb = b;
        ans += (ta - 1);
        tb -= (ta - 1) + 1;
        ans++;
        ans += (tb - 1) / 2;
        res = min(res, ans);
        cout<<res<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int n,s[400],l[400],p[400];
	int i,j,k;
	int m,w[400],dp[400],ans[400];
	int mx,flg,x;
	
	scanf("%d",&n);
	for(i=0;i<n;i++)	{
		scanf("%d %d %d",&s[i],&l[i],&p[i]);
	}
	scanf("%d",&m);
	mx=-1;
	for(i=0;i<m;i++)	{
		scanf("%d",&w[i]);
		if(mx<w[i])	mx=w[i];
	}
	for(i=0;i<=mx;i++)	{
		dp[i]=-1;
	}
	dp[0]=0;
	for(i=0;i<n;i++)	{
		for(j=0;j<mx;j++)	{
			if(dp[j]!=-1)	{
				for(k=s[i];k<=l[i];k++)	{
					if(j+k<=mx)	{
						dp[j+k]=max(dp[j+k],dp[j]+p[i]);
					}
				}
			}
		}
	}
	flg=1;
	for(i=0;i<m;i++)	{
		if(dp[w[i]]==-1)	{
			flg=0;	break;
		}
	}
	if(flg==0)	{
		printf("-1\n");
	}
	else {
		for(i=0;i<m;i++)	{
			printf("%d\n",dp[w[i]]);
		}
	}
	return 0;
}


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

int main(){
  ll n,k;
  int count=0;
  cin >> n >> k;
  while(n!=0){
    n/=k;
    count +=1;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import javax.lang.model.util.ElementScanner6;
//import java.lang.Math;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 入力
        int k = sc.nextInt();
        int n = sc.nextInt();

        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }

        // 処理
        int out = k;

        //時計回り
        int work = 0;
        for(int i = 0; i < n; i++){
            int dist = a[(i + 1 + n) % n] - a[i];
            if (dist < 0) {
                dist += k;
            }
            work = dist > work ? dist : work;
        }
        out = k - work;
        
        // 出力
        System.out.println(out);
    }
}

Measured memory_bytes: 82752
#include <iostream>
#include <string>
#include <queue>
#include <cstdlib>
#include <vector>
#include <map>
#define T 0
#define R 1
#define F 2
#define L 3
#define B 4
#define Bt 5
using namespace std;

vector<int> dice;

void No()
{
  int tmp = dice[T];
  dice[T] = dice[F];
  dice[F] = dice[Bt];
  dice[Bt] = dice[B];
  dice[B] = tmp;
}

void Ea()
{
 int tmp = dice[T];
  dice[T] = dice[L];
  dice[L] = dice[Bt];
  dice[Bt] = dice[R];
  dice[R] = tmp;
}

void We()
{
  int tmp = dice[T];
  dice[T] = dice[R];
  dice[R] = dice[Bt];
  dice[Bt] = dice[L];
  dice[L] = tmp;
}

void Sou()
{
 int tmp = dice[T];
  dice[T] = dice[B];
  dice[B] = dice[Bt];
  dice[Bt] = dice[F];
  dice[F] = tmp;
}

void Rig()
{
  int tmp = dice[R];
  dice[R] = dice[B];
  dice[B] = dice[L];
  dice[L] = dice[F];
  dice[F] = tmp;
}

void Lef()
{
  int tmp = dice[R];
  dice[R] = dice[F];
  dice[F] = dice[L];
  dice[L] = dice[B];
  dice[B] = tmp;
}

int main()
{
  int n;
  dice.resize(6);
  

  while(cin >> n,n)
    {
      int sum = 1;
      dice[0] = 1,dice[1] = 3,dice[2] = 2,dice[3] =4,dice[4] = 5,dice[5] = 6;
      string ope;
      for(int i=0;i<n;i++)
	{
	  cin >> ope;
	  if(ope == "North")
	    No();
	  else if(ope == "East")
	    Ea();
	  else if(ope == "West")
	    We();
	  else if(ope == "South")
	    Sou();
	  else if(ope == "Right")
	    Rig();
	  else if(ope == "Left")
	    Lef();
	
	  sum += dice[T];
	}
      cout << sum << endl;
    }
  return 0;
}

Measured memory_bytes: 1216
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long a,b,L,G,cnt1,cnt2,cnt3,c,d;
int main() {

  cin >> a >> b >> c >> d;
  G=__gcd(c,d);
  L=c*d/G;
  cnt1=b/c-(a-1)/c;
  cnt2=b/d-(a-1)/d;
  cnt3=b/L-(a-1)/L;
  cout << b-a+1-cnt1-cnt2+cnt3 << endl;
}

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

const int MAX_N = 201;
const int MAX_H = 1001;
const int MAX_R = MAX_H;
int N;
int H[MAX_N], R[MAX_N];
int T[MAX_H][MAX_R];

int solve() {
  int ans = 0;
  fill(T[0],T[MAX_H],0);
  for(int j = 0; j < MAX_H; ++j) {
    for(int k = 0; k < MAX_R; ++k) {
      for(int i = 0; i < N; ++i) {
	if(H[i] > j && R[i] > k) {
	  T[H[i]][R[i]] = max(T[H[i]][R[i]], T[j][k] + 1);
	  ans = max(ans, T[H[i]][R[i]]);
	}
      }
    }
  }
  return ans;
}

int main() {
  while(cin >> N && N) {
    for(int i = 0; i < N; ++i) cin >> H[i] >> R[i];
    int m;
    cin >> m;
    for(int i = 0; i < m; ++i) cin >> H[N+i] >> R[N+i];
    N += m;
    cout << solve() << endl;
  }
  return 0;
}

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

void solve() {
  int N;
  string s;
  cin >> N >> s;
  int ans = 0;
  rep(i, 0, 1000) {
    string t = to_string(1000 + i).substr(1);
    int start = 0;
    int cnt = 0;
    for (char c : t) {
      rep(i, start, N) {
        if (s[i] == c) {
          start = i + 1;
          cnt++;
          break;
        }
      }
    }
    if(cnt==3)ans++;
  }
  cout << ans << endl;
}

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

Measured memory_bytes: 3752
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n){
    if(n==1||n==1){
        return false;
    }
    for(int i=2;i<n;++i){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
int fact(int n){
    int ans = 1;
    for(int i = 1; i<= n; ++i){
        ans *= i;
    }
    return ans;
}


int main()
{
    double n;
    cin>>n;
    printf("%.12f",(n/3)*(n/3)*(n/3));

}

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

using namespace std;

int main()
{
	string a_deck = "";
	string b_deck = "";
	string c_deck = "";
	string result = "";

	cin >> a_deck >> b_deck >> c_deck;

	string *current_player = &a_deck;

	while (current_player->length() > 0)
	{
		if(current_player->at(0) == 'a')
		{
			*current_player = current_player->substr(1);
			current_player = &a_deck;
			result = "A";
			continue;
		}
		if(current_player->at(0) == 'b')
		{
			*current_player = current_player->substr(1);
			current_player = &b_deck;
			result = "B";
			continue;
		}
		if(current_player->at(0) == 'c')
		{
			*current_player = current_player->substr(1);
			current_player = &c_deck;
			result = "C";
			continue;
		}
	}

	cout << result << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i <= 6; i++){
        if(pow(2,i) <= n && n < pow(2,i + 1)){
            cout << pow(2,i) << endl;
            break;
        }
    }
}

Measured memory_bytes: 512
/*betaでやろう*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <iterator>
#include <cstring>

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define PB push_back
#define rep(i, a) for(ll i = 0; i < a; i++)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define mp make_pair
#define INT int_64
const ll INF = 1e17;
const ll NEGA=-INF; 

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

int x[200000];
int dis[200000];
int main() 
{ 
    int n,X;
    cin>>n>>X;
    for(int i=0;i<n;++i) cin>>x[i];
    x[n]=X;
    sort(x,x+n+1);
    for(int i=0;i<n;++i){
        dis[i]=x[i+1]-x[i];
    }

    ll ans=dis[0];
    for(int i=1;i<n;++i){
        ans=gcd(ans,dis[i]);
    }
   cout<<ans<<endl;
}



Measured memory_bytes: 1024
#import<atcoder/all>
using std::cin;int N,Q,i,a;main(){cin>>N>>Q;atcoder::fenwick_tree<long>b(N);for(;i<N;b.add(i++,a))cin>>a;for(;cin>>i>>a>>N;Q--){i&&std::cout<<b.sum(a,N)<<'\n';if(!i)b.add(a,N);}}

Measured memory_bytes: 8216
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,x = map(int,input().split())
data = [tuple(map(int,input().split())) for i in range(n)]
for bit in range(2**n):
  cost = 0
  tmp = [0] * m
  for i in range(n):
    if bit >> i & 1:
      for j in range(m):
        tmp[j] += data[i][j+1]
      cost += data[i][0]
  ok = 1
  for j in range(m):
    if tmp[j] < x: ok = 0
  if ok:
    mans = min(mans,cost)
  # print(cost,ok)
  # if cost == 1067:
  #   print(tmp)
print(mans if not mans == inf else -1)


Measured memory_bytes: 68736
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const vi d8x = {1, 0, -1, 0, 1, -1, -1, 1};
const vi d8y = {0, 1, 0, -1, 1, 1, -1, -1};
const vi d4x = {1, 0, -1, 0};
const vi d4y = {0, 1, 0, -1};

//----------------ここからだよ-------------------

int main(){
    int a,b; cin>>a>>b;
    cout<< (a<10&&b<10 ? a*b : -1)<<endl;
}

Measured memory_bytes: 256
def examA():
    N, i = LI()
    ans = N - i + 1
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI() for _ in range(H)]
    h = [[]for _ in range(H)]
    for i in range(W):
        flag = False
        for j in range(H):
            if A[j][i]=="#":
                flag = True
                break
        if flag:
            for j in range(H):
                h[j].append(A[j][i])
    #print(h)
    ans = []
    for i,a in enumerate(h):
        if "#" in a:
            ans.append(i)
    for v in ans:
        print("".join(map(str,h[v])))
    return

def examC():
    N, K = LI()
    X = LI()
    ans = inf
    for i in range(N-K+1):
        if X[i]<0 and X[i+K-1]>0:
            cur = (-X[i] + X[i+K-1]) + min(-X[i], X[i+K-1])
        else:
            cur = max(-X[i], X[i+K-1])
        ans = min(ans,cur)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Measured memory_bytes: 15836
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vs vector<string>
#define all(v) (v).begin(),(v).end()
#define ll long long
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ld long double
#define mod 1000000007
#define PI 3.141592653589793238
#define phi 1.638
#define eps 1e-7
//#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 

int main() 
{
    fastio
    int n, m;
    cin>>n>>m;
    vector<ll> v(m);
    for(auto& it : v) cin>>it;
    ll sum = accumulate(all(v), 0);
    if(n<sum) {
        cout<<-1<<endl;
    }
    else {
        cout<<n-sum<<endl;
    }
}   

Measured memory_bytes: 3724
#include <stdio.h>
#include <string.h>
int main(){
  int len,k,n;
  char s[11],c;
  scanf("%d\n%s\n%d",&n,s,&k);
  c=s[k-1];
  len=strlen(s);
  for (int i=0;i<len;i++){
    if (s[i]!=c) s[i]='*';
  }
  printf("%s\n",s);
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

int main(){
    int A, B, H, M;
    read(A, B, H, M);
    long double dth = abs(H * 30 - (long double)M * 11 / 2);
    long double ans = A * A + B * B - 2 * A * B * cos((long double)(M_PI) * dth / 180);
    ans = sqrt(ans);
    cout << fixed << setprecision(10) << ans;
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

Measured memory_bytes: 4168
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int MAX=10000;
const int INFTY=1<<30;

class edge
{
public:
	int target,cost,len;
	edge(int intarget=0,int incost=0,int inlen=0):
	target(intarget),cost(incost),len(inlen){}
};


int n,col[MAX],d[MAX],l[MAX];
vector<edge> Q[MAX];

int dijkstra(int s)
{
	priority_queue<pair<int,int>> PQ;//weight,id
	for(int i=0;i<n;i++)
	{
		d[i]=l[i]=INFTY;
		col[i]=0;
	}
	d[s]=0;l[s]=0;
	PQ.push(make_pair(0,s));
	col[s]=1;
	pair<int,int> parent[MAX];//vertex,edgenum
	parent[s]=make_pair(-1,0);
	
	while(!PQ.empty())
	{
		pair<int,int> f=PQ.top();PQ.pop();
		int u=f.second;
		col[u]=2;
		if(d[u]<f.first*(-1))continue;
		for(int j=0;j<Q[u].size();j++)
		{
			int v=Q[u][j].target;
			if(col[v]==2)continue;
			if((d[u]+Q[u][j].cost<d[v])||(d[u]+Q[u][j].cost<=d[v]
			&&Q[parent[v].first][parent[v].second].len>Q[u][j].len))
			{
				parent[v]=make_pair(u,j);
				d[v]=d[u]+Q[u][j].cost;
				PQ.push(make_pair(d[v]*(-1),v));
				col[v]=1;
			}
		}
	}
	
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(parent[i].first!=-1)
		{
			ans+=Q[parent[i].first][parent[i].second].len;
		}
	}
	
	return ans;
}

int main()
{
	int m;
	while(cin>>n>>m,n){
	for(int i=0;i<MAX;i++)Q[i].clear();
	int u,v,d,c;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v>>d>>c;
		u--;v--;
		Q[u].push_back(edge(v,d,c));
		Q[v].push_back(edge(u,d,c));
	}
	
	cout<<dijkstra(0)<<endl;
	}
	return 0;
}

Measured memory_bytes: 5132
#include<iostream>

const int MOD = 1e9 + 7;
const int N = 5030;

using namespace std;

long long dp[N][N];

int main()
{
  int n, m;
  cin >> n >> m;
  dp[1][0] = 1;
  for (int j = 1; j <= m; j++)
  {
    dp[1][j] = dp[1][j - 1] * 2 % MOD;
  }
  for (int i = 2; i <= n; i++)
  {
    long long w = 0;
    for (int j = 0; j <= m; j++)
    {
      dp[i][j] = (dp[i - 1][j] * (j + 1) + w) % MOD;
      w = 2 * w % MOD;
      w = (w + dp[i - 1][j] * j) % MOD;
    }
  }
  cout << dp[n][m];
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    LL n, a, b;
    cin >> n >> a >> b;
    LL t = n / (a + b) * a;
    if( n % (a + b) <= a ) t += n % (a + b);
    else t += a;
    cout << t << endl;
    return 0;
}



Measured memory_bytes: 256
/**   Created by: Marcos Portales
          Codeforces User: marcosportales
          Country: Cuba
          Copyright                    */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
#define vi vector<int>
#define sz(a) int((a).size())
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,x,y) for(int i=(x);i<=(y);i++)
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 400010;
const int mod = 1000000007;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 2000000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return (pwur * pwur) % mod;
}
int modinv(int x){
    return qpow(x,mod-2);
}
/// My Code -------------------------------------------------

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));
    //freopen("a.in","r",stdin);
    //freopen("a.in","w",stdout);
    string s;
    cin>>s;
    set<char>st;
    for(char c:s)st.insert(c);
    if(st.size()==s.size())cout<<"yes";
    else cout<<"no";
    return 0;
}


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

const int MOD = 1e9 + 7;

template < typename T >
void printVector (const vector < T > & vec) {
	for (const T x : vec) {
		cout << x << " ";
	}
	cout << endl;
}

template < typename T >
void printMatrix (const vector < vector < T > > & mat) {
	for (const vector < T > vec : mat) {
		printVector (vec);
	}
	cout << endl;
}

const ll INF = 1e18L + 5;

template < typename T >
void min_self (T& a, T b) {
	a = min (a, b);
}

template < typename T >
void max_self (T& a, T b) {
	a = max (a, b);
}

template < typename T >
void add_self (T & a, T b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

template < typename T >
void sub_self (T & a, T b) {
	a -= b;
	if (a < 0) {
		a += MOD;
	}
}

int mul (int a, int b) {
	return ((ll) a * b) % MOD;
}

struct Matrix {
	vector < vector < int > > t;
	Matrix (int m, int n) {
		t.resize (m, vector < int > (n));
	}

	Matrix operator * (const Matrix & b) const {
		Matrix c = Matrix(t.size(), b.t[0].size());
		for (int i = 0; i < c.t.size(); i++) {
			for (int j = 0; j < c.t[0].size(); j++) {
				for (int k = 0; k < t[0].size(); k++) {
					add_self (c.t[i][j], mul (t[i][k], b.t[k][j]));
				}
			}
		}
		return c;
	}
};

int main() {
	int n; ll K;
	scanf ("%d %lld", &n, &K);
	vector < vector < int > > g (n, vector < int > (n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf ("%d", &g[i][j]);
		}
	}

	Matrix m = Matrix (n, n);
	Matrix answer = Matrix (n, n);
	m.t = g;
	for (int i = 0; i < n; i++) answer.t[i][i] = 1;
	while (K >= 1) {
		if (K % 2) {
			answer = answer * m;
		}
		m = m * m;
		K /= 2;
	}

	int total = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			add_self (total, answer.t[i][j]);
		}
	}

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

	// vector < ll > dp (n, 1);

	// for (ll k = 1; k <= K; k++) {
	// 	vector < ll > new_dp (n);
	// 	for (int i = 0; i < n; i++) {
	// 		for (int j = 0; j < n; j++) {
	// 			if (g[i][j]) {
	// 				add_self (new_dp[j], dp[i]);
	// 			}
	// 		}
	// 	}
	// 	dp = new_dp;
	// }

	// ll answer = 0;
	// for (int i = 0; i < n; i++) {
	// 	add_self (answer, dp[i]);
	// }

	// printf ("%lld\n", answer);
	
	return 0;
}

Measured memory_bytes: 256