akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
using namespace std;
int main(){
    int n,m,sum=0;
    int n2[1001]={0},m2[1001]={0},ichi=1;
    cin>>n>>m;
    while(n!=0&&m!=0){
        for(int i=1;i<=n;i++)cin>>n2[i];
        for(int j=1;j<=m;j++)cin>>m2[j];
        for(int i=1;i<=m;i++){
            ichi+=m2[i];
            if(n2[ichi]>=0)ichi+=n2[ichi];
            else if(n2[ichi]<0){
                if(ichi+n2[ichi]>=1){
                    ichi+=n2[ichi];
                }
                else{
                    ichi=1;
                }
            }
            //cout<<ichi<<endl;
            sum++;
            if(ichi>=n){
                cout<<sum<<endl;
                break;
            }
        }
        cin>>n>>m;
        sum=0;
        ichi=1;
    }
}

Measured memory_bytes: 3084
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String[] N = sc.next().split("");
		long res = 0;
		long num = 0;
		for (String s : N) {
			if (s.equals("W")) {
				res += num;
			} else {
				num++;
			}
		}
		System.out.println(res);

	}
}


Measured memory_bytes: 54324
// ABC95-C
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    ll a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    
    ll ans=pow(10,10);
    int num=max(x,y);
    for(int i=0;i<=num;i++){ //abピザで作るa,bピザの数
        ll cur=i*2*c;
        cur+=a*max(ll(0),x-i);
        cur+=b*max(ll(0),y-i);
        ans=min(ans,cur);
    }
    cout<<ans<<endl;
    return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
#define test cout<<"test"<<endl;
#define fi first
#define se second
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
const ll zero=0;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0,sum=0;
  bool judge = true;
  ll n;cin>>n;
  vector<ll>d(n);
  for(i=0;i<n;i++)cin>>d[i];
  sort(ALL(d));
  ll k=n/2;

  cout<<d[k]-d[k-1]<<endl;


  return 0;
}

Measured memory_bytes: 1024
'use strict';

function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _unsupportedIterableToArray(arr, i) || _nonIterableRest(); }

function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method."); }

function _unsupportedIterableToArray(o, minLen) { if (!o) return; if (typeof o === "string") return _arrayLikeToArray(o, minLen); var n = Object.prototype.toString.call(o).slice(8, -1); if (n === "Object" && o.constructor) n = o.constructor.name; if (n === "Map" || n === "Set") return Array.from(o); if (n === "Arguments" || /^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)) return _arrayLikeToArray(o, minLen); }

function _arrayLikeToArray(arr, len) { if (len == null || len > arr.length) len = arr.length; for (var i = 0, arr2 = new Array(len); i < len; i++) { arr2[i] = arr[i]; } return arr2; }

function _iterableToArrayLimit(arr, i) { if (typeof Symbol === "undefined" || !(Symbol.iterator in Object(arr))) return; var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

function main(lines) {
  var _lines$0$split$map = lines[0].split(' ').map(Number),
      _lines$0$split$map2 = _slicedToArray(_lines$0$split$map, 2),
      N = _lines$0$split$map2[0],
      K = _lines$0$split$map2[1];

  var S = lines[1];
  var s = shorten(S); // console.log(s);

  for (var i = 0; i < K; i++) {
    if (s.length === 1) break;
    s = s[0] + s.slice(3); // console.log(s);
  }

  var happiness = N - s.length;
  console.log(happiness);
}

function shorten(s) {
  var len = s.length;

  for (var i = 0; i < len;) {
    if (i !== len - 1 && s[i] === s[i + 1]) {
      s = s.slice(0, i + 1) + s.slice(i + 2);
      len--;
    } else {
      i++;
    }
  }

  return s;
}

function calcHappiness(s) {
  return s.length - shorten(s).length;
}

function runWithStdin() {
  var input = "";
  process.stdin.resume();
  process.stdin.setEncoding("utf8");
  process.stdin.on("data", function (v) {
    input += v;
  });
  process.stdin.on("end", function () {
    main(input.split("\n"));
  });
}

runWithStdin();



Measured memory_bytes: 39224
import math

N = int(input())

digits = int(math.log10(N)) + 1

s = 0
for d in range(1, digits, 2):
    s += 9 * int(math.pow(10, d - 1))

if digits % 2 == 1:
    s += N - int(math.pow(10, digits - 1)) + 1

print(s)


Measured memory_bytes: 3188
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <queue>
using namespace std;
int main()
{
    long long m,i,sum,flag;
    while(~scanf("%lld",&m))
    {
        for(i=1; i<=m; i++)
        {
            sum=i*i;
            if(sum==m)
            {
                flag=i;
                break;
            }
            if(sum>m)
            {
                flag=i-1;
                break;
            }
        }
        flag*=flag;
        printf("%lld\n",flag);
    }
    return 0;
}

Measured memory_bytes: 888
n=int(input())
mons=list(map(int,input().split()))
sold=list(map(int,input().split()))

a=0
for i in range(n):
    if mons[i]<=sold[i]:
        sold[i]-=mons[i]
        a+=mons[i]
        mons[i]=0
        if mons[i+1]<=sold[i]:
            a+=mons[i+1]
            mons[i+1]=0
        else:
            a+=sold[i]
            mons[i+1]-=sold[i]
    else:
        a+=sold[i]

print(a)


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

const int M = 1000000007;
long long a[2001][2001];
int n, k;

int main()
{
	cin >> n >> k;

	for (int i = 0; i <= n; i++) {
		a[i][0] = 1;

		for (int j = 1; j <= i; j++)
			a[i][j] = (a[i - 1][j - 1] + a[i - 1][j]) % M;
	}

	for (int i = 1; i <= k; i++)
		cout << (a[k - 1][i - 1] * a[n - k + 1][i]) % M << endl;

	return 0;
}

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

int main() {
    string s;
    cin >> s;
    string t;
    cin >> t;
    
    vector<vector<int> > memo(s.size()+1, vector<int>(t.size()+1, 0));

    for(int i = 1; i < s.size()+1; i++) {
        for(int j = 1; j < t.size()+1; j++) {
            if(s[i-1] == t[j-1]) {
                memo[i][j] = 1 + memo[i-1][j-1];
            } else {
                memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
            }
        }
    }

    string sequence;
    int i = s.size(), j = t.size();
     while(i && j) {
        if(memo[i][j] == memo[i-1][j]) {
            i--;
        } else if(memo[i][j] == memo[i][j-1]) {
            j--;
        } else {
            i--;
            j--;
            sequence += s[i];
        }
    }
    
	reverse(sequence.begin(), sequence.end());
	cout << sequence;
    return 0;
}

Measured memory_bytes: 38276
#include<iostream>
using namespace std;
int main(){
  int a,i,n,cnt=0;
  cin >> n;
  for(i=0; i<n; i++){
    cin >> a;
    if(a%2==0){
      if(a%3!=0 && a%5!=0){
        cnt++;
      }
    }
  }
  if(cnt>0){
    cout << "DENIED" << endl;
  }
  else{
    cout << "APPROVED" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using ll = long long;
#define ull unsigned ll
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ppi pair<int, pii>
#define mt make_tuple
#define eb emplace_back
using namespace std;

const int N = 10, mod = 1e9 + 7;
const ll inf = 1e18;
int n, m, k, tb, sl, sr;
int a[N], b[N];
string s[N];
int ans;
void solve(){
    cin >> n >> m >> k;
    ans = 0;
    tb = 0;
    //string s;
    //int a[n] = {0}, b[m] = {0};
    for(int i = 0; i < n; i++){
        cin >> s[i];
        for(int j = 0; j < m; j++){
            if(s[i][j] == '#'){
                tb++;
            }
        }
    }
    sl = 1 << n;
    sr = 1 << m;
    for(int i = 0; i < sl; i++){
        for(int j = 0; j < sr; j++){
            int rb = 0;
            for(int l = 0; l < n; l++){
                if(i&(1<<l)){
                    //cout << "i " << l << " ";
                    for(int p = 0; p < m; p++){
                        if(s[l][p] == '#'){
                            rb++;
                            s[l][p] = 'R';
                        }
                    }
                }
            }
            for(int l = 0; l < m; l++){
                if(j&(1<<l)){
                    //cout << "j " << l << " ";
                    for(int p = 0; p < n; p++){
                        if(s[p][l] == '#'){
                            rb++;
                            s[p][l] = 'R';
                        }
                    }
                }
            }
            //cout << rb << endl;
            for(int l = 0; l < n; l++){
                for(int p = 0; p < m; p++){
                    if(s[l][p] == 'R')
                        s[l][p] = '#';
                }
            }
            if(tb - rb == k){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);//cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll t,p;
    t=1;
    //cin>>t;
    for(p=1;p<=t;p++){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 40;

struct Dinic {
public:
	using Flow = ll;
	Dinic(int n_) : n(n_), g(n_) {}
	Flow maximumFlow(int s_, int t_) {
		s = s_;
		t = t_;
		Flow res = 0;
		while(levelize()) {
			prog.assign(n, 0);
			res += augment(s, INF);
		}
		return res;
	}
	void add_edge(int u, int v, Flow c) {
		g[u].push_back({ u, v, c, 0, (int)g[v].size() });
		g[v].push_back({ v, u, c, c, (int)g[u].size() - 1 });
	}

private:
	struct Edge { int s, d; Flow c, f; int r; };
	vector<vector<Edge>> g;
	int n, s, t;
	vector<int> level, prog;

	bool levelize() {
		queue<int> q;
		q.push(s);
		level.assign(n, -1);
		level[s] = 0;
		while(q.size()) {
			int v = q.front();
			q.pop();
			if(v == t) break;
			for(auto &e : g[v]) {
				if(level[e.d] == -1 && residue(e) != 0) {
					level[e.d] = level[v] + 1;
					q.push(e.d);
				}
			}
		}
		return level[t] != -1;
	}
	Flow augment(int v, Flow lim) {
		Flow res = 0;
		if(v == t) return lim;
		for(int &i = prog[v]; i < (int)g[v].size(); ++i) {
			if(lim == 0) break;
			auto &e = g[v][i];
			if(level[v] < level[e.d] && residue(e) != 0) {
				Flow aug = augment(e.d, min(lim, residue(e)));
				e.f += aug;
				reverse(e).f -= aug;
				res += aug;
				lim -= aug;
			}
		}
		return res;
	}
	Flow residue(const Edge& e) { return e.c - e.f; }
	Edge &reverse(const Edge &e) { return g[e.d][e.r]; }
};

int H, W;
char b[110][110];
int in[110][110];
int out[110][110];
int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };


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


	cin >> H >> W;
	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			cin >> b[i + 1][j + 1];
		}
	}

	H += 2, W += 2;

	int cnt = 0;
	for(int i = 0; i < H; i++) {
		for(int j = 0; j < W; j++) {
			in[i][j] = cnt++;
			out[i][j] = cnt++;
		}
	}
	int S = cnt++, T = cnt++;

	Dinic d(cnt);

	for(int y = 0; y < H; y++) {
		for(int x = 0; x < W; x++) {
			if(b[y][x] == 0) {
				d.add_edge(out[y][x], T, INF);
				d.add_edge(in[y][x], out[y][x], INF);
			}
			else if(b[y][x] == 'X') {
				d.add_edge(S, in[y][x], INF);
				d.add_edge(in[y][x], out[y][x], INF);
			}
			else {
				d.add_edge(in[y][x], out[y][x], 1);
			}
			for(int k = 0; k < 4; k++) {
				int nx = x + dx[k], ny = y + dy[k];
				if(0 <= nx && nx < W && 0 <= ny && ny < H) {
					d.add_edge(out[y][x], in[ny][nx], INF);
				}
			}
		}
	}

	ll ans = d.maximumFlow(S, T);
	if(ans >= INF) ans = -1;
	cout << ans << endl;
}

Measured memory_bytes: 6904
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> x(5);
    for(int i = 0; i < 5; i++){
        cin >> x[i];
        if(x[i] == 0){
            cout << i + 1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long int
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define Pb push_back
#define Mp make_pair
#define ff first
#define ss second
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define MOD (ll)1000000007


signed main()
{
    IOS;
    int n,cnt=0;
    cin >> n;
    string s;
    cin >> s;
    for(int i=0;i<s.size()-2;i++)
    {
      if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
      {
        cnt++;
      }
    }
    cout << cnt;
    return 0;
}


Measured memory_bytes: 256
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
from itertools import accumulate
import bisect

import sys
input = sys.stdin.readline

def solve(n,m):
    graph = defaultdict(list)
    for _ in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    connected = []
    unseen = set(range(n))
    while unseen:
        aa = unseen.pop()
        unseen.add(aa)
        stack = [aa]
        cnt = 0
        while stack:
            bb = stack.pop()
            if bb in unseen:
                stack.extend(graph[bb])
                unseen.remove(bb)
                cnt += 1
        connected.append(cnt)
    #print(connected)
    print(max(connected))
            


            

def main():
    n,m = map(int,input().split())
    solve(n,m)


if __name__ == "__main__":
    main()

Measured memory_bytes: 157756
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());

            var w = new List<int>(n);
            foreach (var s in Console.ReadLine().Split(' '))
            {
                w.Add(int.Parse(s));
            }
            var sumA = 0;
            var sumB = w.Sum();
            var min = sumB;

            foreach(var i in w)
            {
                sumA += i;
                sumB -= i;
                var diff = Math.Abs(sumB - sumA);

                if (diff < min) min = diff;

            }

            Console.WriteLine(min);

        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 998244353;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
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; }
const double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
template<typename Monoid>
struct SegmentTree{
    using F = function<Monoid(Monoid, Monoid)>;
 
    int sz;
    vector<Monoid> seg;
 
    const F f;      // モノイドに対して二項演算を行う関数オブジェクト
    const Monoid M1;
 
    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
        sz = 1;
        while(sz < n)   sz <<= 1;
        seg.assign(2 * sz, M1);
    }
 
    void set(int k, const Monoid &x){
        seg[k + sz] = x;
    }
 
    void build(){
        for(int k = sz - 1; k > 0; --k){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }
 
    void update(int k, const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }
 
    Monoid query(int a, int b){
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1)   L = f(L, seg[a++]);
            if(b & 1)   R = f(seg[--b], R);
        }
        return f(L, R);
    }
 
    Monoid operator[](const int &k) const{
        return seg[k + sz];
    }
};
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
 
    int N;
	cin >> N;
	vector<P> p(N);
	SegmentTree<int> seg(N, [](int a, int b){return max(a, b);}, -INF);
	rep(i,N){
		cin >> p[i].first >> p[i].second;
		p[i].first += 1000000010;
		p[i].second += p[i].first;
	}
	sort(p.begin(),p.end());
	int cnt1[N]{}, cnt2[N]{};
	seg.update(N-1, p[N-1].second*MOD+N-1);
	cnt2[N-1] = 2;
	cnt1[N-1] = 1;
	for(int i=N-2;i>=0;i--){
		seg.update(i,p[i].second*MOD+i);
		auto itr = lower_bound(p.begin(), p.end(), P(p[i].second, -INF));
		int j = itr - p.begin();
		// if(itr == p.end()) cnt2[i] = 1;
		if(j == i+1) cnt2[i] = cnt2[i+1];
		else{
			int x = seg.query(i+1, j);
			x %= MOD;
			cnt2[i] = cnt1[x];
		}
		cnt1[i] = cnt2[i];
		cnt2[i] += cnt2[i+1];
		cnt2[i] %= MOD;
	}
	cout << cnt2[0] << endl;
}

Measured memory_bytes: 10624
n = gets.to_i
x = gets.split.map(&:to_i)
y = 0
x.each do |i|
    y += i
end
y = (y.to_f)/(x.size)
if y - y.to_i <= 0.5
    y = y.to_i 
else
    y = y.to_i + 1
end
sum = 0
x.each do |j|
    sum += (j-y)**2
end
puts sum

Measured memory_bytes: 3836
import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    List<Double> list = new ArrayList<>();
    Double n = sc.nextDouble();
    for(int i = 0; i < n; i++){
      list.add(sc.nextDouble());
    }
    
    Collections.sort(list);
    System.out.println((int)(list.get(list.size() - 1) - list.get(0)));
    return;
  }
}


Measured memory_bytes: 23124
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5e5 + 7;
//--------head---------
struct Edge {
	int u, v, c;
	void in() {
		cin >> u >> v >> c;	
	}
} E[N];
int n, m, tot;
map<pii, int> R;
map<pii, int>::iterator it;
vector<pii> e[N];
void ins(int u, int c) {
	pii p = mp(u, c);
	if (R.find(p) == R.end())
		R[p] = ++tot;
}
void addEdge(int u, int v, int c) {
	int x = R[mp(u, c)], y = R[mp(v, c)];
	e[x].pb(mp(v, 0)), e[x].pb(mp(y, 0));
}
bool vis[N];
int dis[N];
priority_queue<pii> que;
int solve() {
	rep(i, 0, tot + 1)
		vis[i] = false, dis[i] = -1;
	que.push(mp(0, 1));
	while (!que.empty()) {
		int u = que.top().second, d = -que.top().first;
		que.pop();
		if (vis[u])
			continue;
		dis[u] = d, vis[u] = true;
		rep(i, 0, sz(e[u])) {
			int v = e[u][i].first, w = e[u][i].second;
			if (!vis[v])
				que.push(mp(-(d + w), v));
		}
	}
	int ans = dis[n];
	rep(i, 0, sz(e[n])) {
		int v = e[n][i].first;
		if (~dis[v] && (ans == -1 || dis[v] < ans))
			ans = dis[v];
	}
	return ans;
}
int main() {
	cin >> n >> m;
	tot = n;
	rep(i, 0, m) {
		E[i].in();
		ins(E[i].u, E[i].c), ins(E[i].v, E[i].c);
	}
	for (it = R.begin(); it != R.end(); ++it) {
		pii p = it->first;
		int v = it->second;
		e[p.first].pb(mp(v, 1));
	}
	rep(i, 0, m) {
		int u, v, c;
		u = E[i].u, v = E[i].v, c = E[i].c;
		addEdge(u, v, c), addEdge(v, u, c);
	}
	cout << solve() << endl;
	return 0;
}


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

using namespace std;

using ll = long long;

int main() {
   ios_base::sync_with_stdio(false);
   int N;
   cin >> N;
   vector<tuple<int, int, int>> edges;
   for (int i = 0; i < N - 1; ++i) {
      int v, u, w;
      cin >> v >> u >> w;
      --v, --u;
      edges.emplace_back(w, v, u);
   }
   sort(edges.begin(), edges.end());
   reverse(edges.begin(), edges.end());
   vector<int> par(N);
   vector<int> sz(N);
   vector<ll> add(N);
   iota(par.begin(), par.end(), 0);
   fill(sz.begin(), sz.end(), 1);
   auto getPar = [&](int v) {
      while (v != par[v]) {
         v = par[v];
      }
      return v;
   };
   auto getSum = [&](int v) {
      ll ans = add[v];
      while (v != par[v]) {
         ans += add[par[v]];
         v = par[v];
      }
      return ans;
   };
   for (auto e : edges) {
      int w, v, u;
      tie(w, v, u) = e;
      v = getPar(v), u = getPar(u);
      add[v] += ll(sz[u]) * w;
      add[u] += ll(sz[v]) * w;
      if (sz[v] < sz[u]) swap(v, u);
      par[u] = v;
      sz[v] += sz[u];
      add[u] -= add[v];
   }
   for (int i = 0; i < N; ++i) {
      cout << getSum(i) << "\n";
   }
}


Measured memory_bytes: 4468
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

inline void read(int &T) {
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	T=f?-x:x;
}

int a,b;

int main() {
	std::cin>>a>>b;
	std::cout<<a*b<<'\n';
	return 0;
}

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

int main()
{
    int n;
    while (cin >> n, n)
    {
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }

        sort(a, a + n);

        int sum = 0;
        for (int i = 1; i < n - 1; i++)
        {
            sum += a[i];
        }

        cout << sum / (n - 2) << "\n";
    }
}


Measured memory_bytes: 3164
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]
#CW = [list(map(int, list(input()))) for _ in range(H)]


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

bd = b*d
ca = c*a
ad = a*d
bc = b*c

print(max(bd,ca, bc,ad))





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

int main() {
    ll N,M;
    cin >> N >> M;
    vector<ll> H(N);
    for (ll i=0; i<N; i++) {
        cin >> H[i];
    }
    vector<ll> A(M);
    vector<ll> B(M);
    for (ll i=0; i<M; i++) {
        cin >> A[i] >> B[i];
    }

    //
    vector<ll> good(N,1);
    for (ll i=0; i<M; i++) {
        if (H[A[i]-1] > H[B[i]-1]) {
            good[B[i]-1] = 0;
        }
        else if (H[A[i]-1] == H[B[i]-1]) {
            good[A[i]-1] = 0;
            good[B[i]-1] = 0;
        }
        else {
            good[A[i]-1] = 0;
        }
    }
    ll ans = 0;
    for (ll i=0; i<N; i++) {
        ans += good[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 6412
N = int(input())

cnt = 0
for i in range(1,N+1):
    if i % 2 == 0:
        continue
    c = 0
    for j in range(1,i+1):
        if i % j == 0:
            c += 1
    if c == 8:
        cnt += 1

print(cnt)


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////


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

	vector<ll> X(N + 1);
	repn(i, N) cin >> X[i];

	vector<ll> c(N + 1,0), lc(N + 1,0);

	repn(i, N) c[i] = c[i - 1] + X[i] * 2;
	repn(i, N) lc[i] = lc[i - 1] + (L - X[i]) * 2;

	//repn(i, N) cout << c[i] <<" "<< lc[i] << endl;
	
	ll ans = 0;

	repn(i, N) {
		ll d = min(i - 1, N - i);
		ll v = c[i - 1] - c[i - 1 - d] + lc[i + d] - lc[i];
		v += max(X[i], L - X[i]);

		ll w = 0;
		if (i - 1 < N - i) {
			w = c[i - 1] - c[i - 1 - d] + lc[i + d + 1] - lc[i];
			w += X[i];
		}
		if (i - 1 > N - i) {
			w = c[i - 1] - c[i - 1 - d - 1] + lc[i + d] - lc[i];
			w += L - X[i];
		}

		v = max(v, w);

		//cout << i << " " << v << endl;

		ans = max(ans, v);
	}
	
	cout << ans;

	system("PAUSE");
}


Measured memory_bytes: 5120
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PI 3.1415926535897932384626433832795
#define endl "\n"
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
long long MOD = 1e9+7;
pair<int,int> dx[4] = {{1,0},{-1,0},{0,1},{0,-1}};
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct chash {int operator()(int x) const { return x ^ RANDOM; }};
string toString(long long x){stringstream ss;ss << x;string str = ss.str();return str;}
long long fastpow(long long x,long long k){if(!k)return 1;if(k & 1)return ((x * fastpow(x,k-1) % MOD) % MOD) % MOD;
long long ans = fastpow(x,k/2);ans %= MOD;ans *= ans;ans %= MOD;return ans;}
long long sumF(long long x){int s = 0;while(x)s += x%10,x /= 10;return s;}
bool isS(char c){return (c >= 'a' && c <= 'z');}
bool isB(char c){return (c >= 'A' && c <= 'Z');}
bool isD(char c){return (c >= '0' && c <= '9');}
bool isSqrt(long long x){ long long f = sqrt((long double)x + 0.5); return f*f == x;}
bool isCubic(long long x) {long long f = cbrt((long double)x + 0.5); return f*f*f == x;}
long long lcm(long long a,long long b){return a * (b / __gcd(a,b));}
vector<long long> divVec(long long x){vector<long long> tmp;for(long long i = 1;1LL*i*i <= x;i++){if(x % i == 0){tmp.push_back(i);if(x / i != i)
tmp.push_back(x / i);}}return tmp;}
long long invMod(long long x){return fastpow(x,MOD - 2) % MOD;}
int main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    IO;
    string s;
    cin >> s;
    int wins = 0;
    for(int i = 0;i < s.length();i++)
        wins += (s[i] == 'o');
    wins += 15-s.length();
    if(wins >= 8)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}


Measured memory_bytes: 256
from math import sqrt


def is_prime(n: int) -> bool:
    sq = int(sqrt(n))
    if sq * sq == n:
        return False

    for i in range(2, sq+1):
        if n % i == 0:
            return False
    return True


def primes(n: int) -> list:
    res = []

    if n < 2:
        return res
    res.append(2)

    if n < 3:
        return res
    res.append(3)

    for i in range(6, n+1, 6):
        if is_prime(i-1):
            res.append(i-1)

        if i + 1 > n:
            break

        if is_prime(i+1):
            res.append(i+1)

    return res


def five_five_everywhere(N: int) -> list:
    res = []
    count = 0
    for p in primes(55555):
        if p % 5 != 1:
            continue

        res.append(p)
        count += 1
        if count == N:
            return res

    return None


if __name__ == "__main__":
    N = int(input())
    ans = five_five_everywhere(N)
    print(' '.join(map(str, ans)))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);
//ios::sync_with_stdio(false);



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

    sort(all(d));
    ans=d[0];

    for(int i=0;i < n;i++)
    {
        if(i%2==0){
            d[i]=24-d[i];
        }
    }

    sort(all(d));
    
    

    for(int i=0;i < n-1;i++)
    {
        ans=min(ans,d[i+1]-d[i]);
    }

    cout<<ans<<endl;;


}

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

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

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	char s[16]="URDLLURDRDLU";
	int sx,sy,tx,ty,a,b,i;
	scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
	a = tx-sx;
	b = ty-sy;
	for(i = 1;i <= b;i++){printf("%c",s[0]);}
	for(i = 1;i <= a;i++){printf("%c",s[1]);}
	for(i = 1;i <= b;i++){printf("%c",s[2]);}
	for(i = 1;i <= a;i++){printf("%c",s[3]);}
	for(i = 1;i <= 1;i++){printf("%c",s[4]);}
	for(i = 1;i <= b+1;i++){printf("%c",s[5]);}
	for(i = 1;i <= a+1;i++){printf("%c",s[6]);}
	for(i = 1;i <= 1;i++){printf("%c",s[7]);}
	for(i = 1;i <= 1;i++){printf("%c",s[8]);}
	for(i = 1;i <= b+1;i++){printf("%c",s[9]);}
	for(i = 1;i <= a+1;i++){printf("%c",s[10]);}
	for(i = 1;i <= 1;i++){printf("%c",s[11]);}
	printf("\n");
	return 0;
}

Measured memory_bytes: 128
def main():
    vertex, edge_num = map(int, input().split())
    edge = [[] for _ in range(vertex)]
    all_edge = []
    for _ in range(edge_num):
        all_edge.append(tuple(map(lambda x: int(x) - 1, input().split())))
        edge[all_edge[-1][0]].append(all_edge[-1][1])
        edge[all_edge[-1][1]].append(all_edge[-1][0])

    def search(exception):
        next_search = [0]
        has_searched = []
        result = 0
        while not next_search == []:
            now = next_search.pop(0)
            for d in edge[now]:
                if d in exception and now in exception:
                    continue
                elif d not in has_searched:
                    has_searched.append(d)
                    next_search.append(d)
                    result += 1
        return result == vertex

    answer = 0
    for ex in all_edge:
        if not search(ex):
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()



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

a=list(map(int,input().split()))

if n==2:
    print(max(a)-min(a))

    print(max(a),min(a))
    exit()

#+ -が最低一つ必要
#あとはどちらの符号にもできる？

a_p=[]
#a_zero=[]
a_m=[]

for aa in a:
    if aa>=0:
        a_p.append(aa)
    else:
        a_m.append(aa)

#どっちもある

ans=[]

if len(a_m)>0 and len(a_p)>0:
    if len(a_p)==1:
        tmp=a_p[0]
        for v in a_m:
            ans.append([tmp,v])
            tmp=tmp-v
    else:
        tmp=a_m[0]
        for v in a_p[1:]:
            ans.append([tmp,v])
            tmp=tmp-v
        ans.append([a_p[0],tmp])
        tmp=a_p[0]-tmp
        for v in a_m[1:]:
            ans.append([tmp,v])
            tmp=tmp-v

elif len(a_p)>0:
    a_p.sort()

    tmp=a_p[0]
    for v in a_p[2:]:
        ans.append([tmp,v])
        tmp=tmp-v
    ans.append([a_p[1],tmp])

else:
    a_m.sort(reverse=True)

    tmp=a_m[0]
    for v in a_m[1:]:
        ans.append([tmp,v])
        tmp=tmp-v


print(ans[-1][0]-ans[-1][1])
for item in ans:
    print(item[0],item[1])





Measured memory_bytes: 105244
#include<bits/stdc++.h>
using namespace std;
char x[100005],y;
int g,z;
int main()
{
	while(x[z]=getchar(),x[z]!='\n')
	{
		
		if(z==0)y=x[z];
		if(x[z]!=y)g++,y=x[z];
		
		z++;
	}
	
	cout<<g;
	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h> 
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<int>>;

int main(){
    ll n,k,q;
    cin>>n>>k>>q;
    vector<ll> a(q);
    rep(i,q)cin>>a[i];

    vector<ll> b(n,-q);
    rep(i,q)b[a[i]-1]++;
    rep(i,n){
        if(b[i]+k>0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}


Measured memory_bytes: 4820
using System;
using System.Linq;

class Amondai
{
    static void Main()
    {
        Console.ReadLine();
        var line = Console.ReadLine().Split(' ').Select(x=>Int32.Parse(x)).ToArray();
        var average = line.Average();
        var min = -1;
        var distance = double.MaxValue;
        var index = 0;
        foreach (var l in line)
        {
            var difference = Math.Abs(l-average);
            if (difference < distance)
            {
                distance = difference;
                min = index;
            }
            index++;
        }
        Console.WriteLine(min);
    }
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int a;
  string s;
  cin >> a >> s;

  if (a >= 3200) {
    cout << s << endl;
  } else {
    cout << "red" << endl;
  }
}


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

int main() {
	int n, query_num;

	std::cin >> n >> query_num;

	std::vector<std::pair<int, int> > v;
	for (int i = 0; i < n; i++) {
		v.push_back(std::make_pair(i, i));
	}

	for (int i = 0; i < query_num; i++) {
		int query, a, b;
		std::cin >> query >> a >> b;
		if (query == 0) {//unite
			int num = v[b].second;
			for (size_t j = 0; j < v.size(); j++) {
				if (v[j].second == num) {
					v[j].second = v[a].second;
				}
			}
		} else {//same
			if (v[a].second == v[b].second) {
				std::cout << 1 << std::endl;
			} else {
				std::cout << 0 << std::endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1328
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define setbits(x) __builtin_popcount(x)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define in insert
#define pb push_back
#define IOS                           \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define endl "\n"
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
inline ll power(ll a, ll n, ll m)
{
    if (n == 0)
        return 1;
    ll p = power(a, n / 2, m);
    p = (p * p) % m;
    if (n % 2)
        return (p * a) % m;
    else
        return p;
}
const ll MOD = 1000000007;
const int N = int(3e5) + 999;
#define int long long int

int32_t main(){
    IOS;
    int n,m;
    cin>>n>>m;
    int arr[n+1]={0},pen[n+1]={0};

    for(int i=0;i<m;i++){
    	int p;string s;
    	cin>>p>>s;
    	if(arr[p]==1)
    		continue;
    	if(s=="AC")
    		arr[p]=1;
    	else
    		pen[p]++;
    }
    int peni = 0,ans=0;
    for(int i=1;i<=n;i++){
    	if(arr[i]==1)
    		ans++;
    	if(arr[i])
    	peni+=pen[i];
    }

    cout<<ans<<" "<<peni<<endl;

    return 0;
}

Measured memory_bytes: 1792
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n){
        cin >> a[i];
    }
    int dp[25][2010];
    rep(i, n+1){
        rep(j, 2001){
            dp[i][j] = (j == 0);
        }
    }
    REP(i, 1, n+1){
        REP(j, 1, 2001){
            if(j >= a[i-1]){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i-1]];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    int q;
    cin >> q;
    rep(i, q){
        int m;
        cin >> m;
        if(dp[n][m] > 0){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3236
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

A = map(int, input().split())

if sum(A) >= 22:
    print("bust")
else:
    print("win")


Measured memory_bytes: 77540
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
#define showm(m) for(auto i: m){cout << m.x << " ";}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


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


    int ans = 0;
    vector<int> dp(2, 0);
    vector<int> old_dp(2, 0);
 
    rep(i, s.size()){
        int num = s[i] - '0';
        if (i == 0) {old_dp[0] = (10-num)+1; old_dp[1] = num; continue;}
        dp[0] = min(old_dp[0] + (10-num)-1, old_dp[1]+(10-num)+1);
        dp[1] = min(old_dp[0], old_dp[1]) + num;
        old_dp = dp;
    }
    cout << min(old_dp[0],old_dp[1]) << endl;
}



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

#define ll long long
#define mod 1000000007
#define pll pair<long long,long long>
#define pdd pair<long double,long double>
#define vll vector<ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define mp make_pair
#define pb push_back
#define pf push_front
priority_queue<pll,vector<pll>,greater<pll> >pq;
priority_queue<ll,vector<ll>,greater<ll> >pq1;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    double n,m,t,p;
    cin>>n;
    ll x=n/1.08;
    if((x*108)/100==n){
        cout<<x;
    }
    else if(((x+1)*108)/100==n){
        cout<<x+1;
    }
    else if(((x-1)*108)/100==n){
        cout<<x-1;
    }
    else{
        cout<<":(";
    }
    return 0;
}


Measured memory_bytes: 256
<?php
[$A, $B, $N] = ints();
    $i = min($N, $B-1);
    echo floor($A*$i/$B) - $A*floor($i/$B),"\n";

function str(){return trim(fgets(STDIN));}
function ints(){return array_map('intval',explode(' ',trim(fgets(STDIN))));}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function o(...$val){
    if(count($val)==1)$val=array_shift($val);
    echo debug_backtrace()[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0)echo "empty array";
        elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
        else{
            echo "array:array\n";
            if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
            else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
        }
    }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

function dfs($current, $from = -1, $d = 0){
  global $G, $distance;
  $distance[$current] = $d;
  foreach($G[$current] as $to){
    if($from != $to){
      dfs($to, $current, $d + 1);
    }
  }
}

function loadTree($N = false){
  if($N === false)$N = $GLOBALS['N'];
  return loadGraph($N, $N-1);
}
function loadGraph($N = false, $M = false, $both = true){
  if($N === false)$N = $GLOBALS['N'];
  if($M === false)$M = $GLOBALS['M'];
  $G = array_fill(1, $N, []);
  for($i = 0; $i < $M; $i++){
    $values = ints();
    if(count($values) == 2){
      list($a, $b) = $values;
      $G[$a][] = $b;
      if($both)$G[$b][] = $a;
    }else{
      list($a, $b, $d) = $values;
      $G[$a][] = [$b, $d];
      if($both)$G[$b][] = [$a, $d];
    }
  }
  return $G;
}


Measured memory_bytes: 16208
/*
2020-04-25
atcoder ABC
C - Rally
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;

int main() {
    int N;
    cin >> N;
    set<ll> S;
    for(int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        S.insert(a);
    }
    if(S.size() == N) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}


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

using namespace std;

const int kMaxN = 1e5+10;
const int kInf = 1e9+10;

int n;
long long ans;
vector<pair<int,int>> T[kMaxN];
int sub[kMaxN], maxsub[kMaxN];

void dfs(int x, int f, int c) {
	sub[x] = 1;

	for (auto edge : T[x]) {
		if (edge.first != f) {
			dfs(edge.first, x, edge.second);
			sub[x] += sub[edge.first];
			maxsub[x] = max(maxsub[x], sub[edge.first]);
		}
	}

	ans += 2LL * min(sub[x], n - sub[x]) * c;
	maxsub[x] = max(maxsub[x], n - sub[x]);
}

int main() {
	cin >> n;

	for (int i = 1; i < n; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		T[x].push_back(make_pair(y, c));
		T[y].push_back(make_pair(x, c));
	}

	dfs(1, 0, 0);

	vector<int> centroids;
	centroids.push_back(1);
	for (int i = 2; i <= n; ++i) {
		if (maxsub[i] < maxsub[centroids[0]]) {
			centroids = vector<int>{i};
		} else if (maxsub[i] == maxsub[centroids[0]]) {
			centroids.push_back(i);
		}
	}

	if (centroids.size() == 2) {
		int x = centroids[0];
		int y = centroids[1];
		for (auto edge : T[x]) {
			if (edge.first == y)
				ans -= edge.second;
		}
	} else {
		int x = centroids[0];
		int minc = kInf;	
		for (auto edge : T[x]) {
			minc = min(minc, edge.second);
		}
		ans -= minc;
	}

	cout << ans << "\n";
}

Measured memory_bytes: 13184