akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int W = stdIn.nextInt();
		int H = stdIn.nextInt();
		int x = stdIn.nextInt();
		int y = stdIn.nextInt();
		int r = stdIn.nextInt();

		if (0 <= x - r && x + r <= W && 0 <= y - r && y + r <= H) {
			System.out.println("Yes");

		}
		else 
			System.out.println("No");
	}
}

Measured memory_bytes: 17328
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;

using namespace std;

int main(void){
    string S;
    ll pat[105];
    ll K;
    cin>>S>>K;
    char th, la=S[0];
    ll index=0;
    MEMSET(pat, 0);
    rep(i, S.length()){
        th = S[i];
        if(th != la) index++;
        pat[index]++;
        la=th;
    }
    //cout <<pat[index]<<endl;
    //cout<<endl;
    ll count=0;
    for(int i = 1; i<index; i++) count+=(pat[i]/2);
    count *=K;
    ll de = (pat[0]/2)+(pat[index]/2);
    if(S[S.length()-1] == S[0]){
        if(index==0){
            cout<< (K*S.length())/2 <<endl;
            return 0;
        }
        ll inner = (pat[0]+pat[index])/2;
        //cout << inner <<endl;
        count+=((K-1)*inner);
    } else de*=K;
    count+=de;
    cout << count <<endl;
    return 0;
}


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

namespace ConsoleApp15
{
    class Class124
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            var ans = Console.ReadLine().Split().Select(x=>int.Parse(x)-1).Sum();
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11328
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();

		for(int i = 0; i < w+2; i++) {
			System.out.print("#");
		}
		sc.nextLine();
		for(int i = 0; i < h; i++) {
			System.out.print("\n#");
			System.out.print(sc.nextLine());
			System.out.print("#");
		}
		System.out.println("");
		for(int i = 0; i < w+2; i++) {
			System.out.print("#");
		}

	}
}


Measured memory_bytes: 23252
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10**7)

ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

import math

a, b, h, m = na()

ah = h * 30 + m * 0.5
am = m * 6
ang = abs(ah - am)
t = abs(360 - ang)
print("{:.10f}".format(math.sqrt(pow(a, 2) + pow(b, 2) - (2 * a * b * math.cos(math.radians(t))))))

Measured memory_bytes: 9540
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("atcoder-problems/arc089_a.txt"); \
  cin.rdbuf(in.rdbuf());
#else
#define INPUT_FILE
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
const int INF = 100100100;
const ll LINF = 1e18+100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;
  
  vector<int> t(N);
  vector<int> x(N);
  vector<int> y(N);
  rep(i, N) { cin >> t[i] >> x[i] >> y[i]; }

  bool ok = true;
  int bx = 0, by = 0, bt = 0;
  rep(i, N) {
    int diff = abs(x[i] - bx) + abs(y[i] - by);
    int diffT = t[i] - bt;
    if (diffT % 2 != diff % 2 || diff > diffT) {
      ok = false;
      break;
    }
    bx = x[i];
    by = y[i];
    bt = t[i];
  }

  cout << (ok ? "Yes" : "No") << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d,e,k;
  cin >> a >> b >> c >> d >> e >> k;
  string ret = ":(";
  if (e - a <= k) {
    ret = "Yay!";
  }
  cout << ret << endl;
}


Measured memory_bytes: 256
import sys
from collections import deque, defaultdict, Counter
# from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()
S = [input() for _ in range(H)]

L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
D = [[0]*W for _ in range(H)]
U = [[0]*W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			L[i][j] = 0
		elif j == 0:
			L[i][j] = 1
		else:
			L[i][j] = L[i][j-1] + 1

for i in range(H):
	for j in range(W-1, -1, -1):
		if S[i][j] == '#':
			R[i][j] = 0
		elif j == W-1:
			R[i][j] = 1
		else:
			R[i][j] = R[i][j+1] + 1

for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			U[i][j] = 0
		elif i == 0:
			U[i][j] = 1
		else:
			U[i][j] = U[i-1][j] + 1

for i in range(H-1, -1, -1):
	for j in range(W):
		if S[i][j] == '#':
			D[i][j] = 0
		elif i == H-1:
			D[i][j] = 1
		else:
			D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(H):
	for j in range(W):
		ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)


Measured memory_bytes: 186204
#include<iostream>
using namespace std;
typedef long long ll;
ll f(ll n) {
	ll ans = 0;
	while (n > 0) {
		ans += n % 10; n /= 10;
	}return ans;
}
int main() {
	ll n; cin >> n;
	cout << ((n%f(n) == 0) ? "Yes\n" : "No\n");
	return 0;
}

Measured memory_bytes: 256
horses = [4, 1, 4, 1, 2, 1, 2, 1]

readlines.each do |passengers|
  ps = passengers.chomp.split.map(&:to_i)
  hs = horses.dup
  h_result = horses.dup
  max = 0
  (0..7).each do |i|
    temp = ps.map.with_index{ |p, j| (p < hs[j] ? p : hs[j])}.inject(&:+)
    if max < temp
      max = temp
      h_result = hs.dup
    elsif max == temp
      h_result = hs.dup if hs.join.to_i < h_result.join.to_i
    end
    hs.rotate!
  end

  puts h_result.join(' ')
end

Measured memory_bytes: 6128
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for(int i = 0; i < H; ++i) {
        cin >> S[i];
    }
    vector<vector<int>> memo(H, vector<int>(W, -1));
    auto dfs = [&](auto &&dfs, int y, int x) -> int {
        if(y >= H || x >= W) return 0;
        if(S[y][x] == '#') return 0;
        if(y == H - 1 && x == W - 1) return 1;
        if(memo[y][x] != -1) return memo[y][x];
        return memo[y][x] = (dfs(dfs, y + 1, x) + dfs(dfs, y, x + 1)) % MOD;
    };
    cout << dfs(dfs, 0, 0) << '\n';
    return 0;
}


Measured memory_bytes: 5376
#define _CRT_DISABLE_PERFCRIT_LOCKS
#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define fs first
#define sc second

using namespace std;

ll inf=1e18;
ll mod=(ll)10e9+7;
double pi=3.1415926535897932384626433832795;
ll i, j;
ll N=1e5;

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    ll a, b, c, i, j;
    cin>>a>>b>>c;
    vector < ll > v;
//            ll n=a, m=b;
//            for(i = 1; i<=b; i++)
//            {   n=a*i; m=b-i;
//                while(1)
//                {
//                    if(n+m>=a*b) {break;}
//                    cout<<n+m<<endl;
//                    v.pb(n+m);
//                    m+=m;
//                }
//            }
//            for( i=0; i<v.size(); i++)
//            {
//                cout<<v[i]<<" ";
//            }
        for(i=0; i<=a; i++)
        {
            for(j=0; j<=b; j++)
            {
                //cout<<(a*j-i)+(b*i-j)<<endl;
                v.pb((a*j)+(b*i)-(i*j)-(i*j));
            }
        }

            for( i=0; i<v.size(); i++)
            {
                //cout<<v[i]<<" ";
                if(c==v[i]) {cout<<"Yes"<<endl; return 0;}
            }

/*    if(c==0)
    {
        cout<<"Yes"<<endl; return 0;
    }
    if(c==1)
    {
        if(a==1 or b==1)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
        return 0;
    }
    if(a%c==0 or b%c==0 or c%a==0 or b%c==0)
    {
        cout<<"Yes"<<endl; return 0;
    }
    else
    {
        if(a*b%2==1 or a*b%2==0)
        {
            if(c==a*b/2 or c==a*b/2+1)
            {
                cout<<"Yes"<<endl; return 0;
            }
            else
            {
                cout<<"No"<<endl; return 0;
            }
        }
        else
        {

            cout<<"No"<<endl; return 0;
        }
    }*/
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 10220
import java.util.Scanner;

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

		long n = sc.nextLong();

		double d = Math.sqrt(n);

		long ans1 = 0;
		long ans2 = 0;

		for (long i = (long) d; i > 0; i--) {

			double tmp = (double) n / i;
			if (tmp == (long) tmp) {

				ans1 = (long) tmp;
				ans2 = i;
				break;

			}
		}

		long ans = ans1 + ans2 - 2;

		System.out.println(ans);

	}

}

Measured memory_bytes: 23892
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void)
{
  int num = 0;
  int n; cin >> n;

  int i = 1;
  while(i <= n) {

    ++num;
    
    if (i == 9) {
      i = 100;
    } else if (i == 999) {
      i = 10000;
    } else if (i == 99999) {
      i = 1000000;
    } else {
      ++i;
    }
    

  }
    cout << num << endl;
  
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long ll;
#define INF 100000000000
#define MAX_V 10001
int main(){
  ll n,w,dp[101][MAX_V],W,v;
  cin >> n >> W;
  for(int i=0;i<101;i++){
    for(int j=0;j<MAX_V;j++){
      if(j==0) dp[i][j]=0;
      else dp[i][j]=INF;
    }
  }
  cin >> v >> w;
  dp[0][v]=w;
  for(int i=1;i<n;i++){
    cin >> v >> w;
    for(int j=0;j<MAX_V;j++){
      if(j<v)dp[i][j]=dp[i-1][j];
      else dp[i][j]=min(dp[i-1][j],dp[i-1][j-v]+w);
    }
  }
  for(int i=MAX_V-1;i>=0;i--){
    if(dp[n-1][i]!=INF&&dp[n-1][i]<=W){
      cout << i<<endl;
      break;
    }
  }
}



Measured memory_bytes: 11012
#include<bits/stdc++.h>
#define INF 2000000000
#define int long long int
#define MOD 1000000007
#define pb push_back
#define cin1(n) (cin >> n)
#define cin2(a,b) (cin >> a >> b)
#define cin3(a,b,c) (cin >> a >> b >> c)
#define cout(n) (cout << n << endl)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define fr first 
#define sc second 
#define EPS (1e-10)

using namespace std;

typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector<pair<int,int>> vpii;
typedef vector<string> vs;
typedef vector<vector<string>> vss;
typedef pair<int,int> pii;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n,m;
int a,b;
int p,q;


signed main() {
	
	cin1(n);

	vector<int> l(2*n);
	for (int i = 0; i < 2*n; i++) {
		cin1(l[i]);
	}

	sort(l.begin(),l.end());
	int ans = 0;
	for (int i = 0; i < 2*n; i+=2) {
		ans += min(l[i],l[i+1]);
	}

	cout(ans);
	return 0;
}





Measured memory_bytes: 256
N=int(input())
W=[int(x) for x in input().split()]

head=1
tail=N-2
sum_s1=W[0]
sum_s2=W[N-1]
while(head<=tail):
    if(sum_s1<=sum_s2):
        sum_s1+=W[head]
        head+=1
    else:
        sum_s2+=W[tail]
        tail-=1
        
print(abs(sum_s1-sum_s2))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int dp[200005];
vector<int> G[200005];
int n;
int a[200005];
int ans[200005];
const int inf = 0x3f3f3f3f;
void dfs(int u,int p){
	
	int ind = (int)(lower_bound(dp,dp+n,a[u]) - dp);
	
	int cnt = dp[ind];
	
	dp[ind] = a[u];
	
	ans[u] = (int)(lower_bound(dp,dp+n,inf) - dp);
	
	for(int i:G[u]){
		if(i!=p){
			dfs(i,u);
		}
	}
	
	//undo
	
	dp[ind] = cnt;
	
	
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++){
		int t1,t2;
		cin>>t1>>t2;
		t1--,t2--;
		G[t1].push_back(t2);
		G[t2].push_back(t1);
	}
	fill(dp,dp+n+2,inf);
	dfs(0,-1);
	for(int i=0;i<n;i++) cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 31188
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<double> v(n);
    rep(i,n) cin >> v[i];
    double sum = 0;
    rep(i,n) sum += v[i];
    sum /= n;
    double sub = inf;
    int ans = 0;
    rep(i,n){
        if( abs(sum - v[i]) < sub){
            sub = abs(sum - v[i]);
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3756
#define _GLIBCXX_DEBUG //提出時に消す
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pull = pair<ull, ll>;
#define INF 1000000
#define LLINF 10000000000000000ll
#define MOD 1000000007LL

bool dbgflag = false;

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

  ull a;
  double b;
  cin >> a >> b;
  ull bint = b * 100.1;
  //cout << bint << endl;
  cout << (a * bint) / 100 << endl;
}


Measured memory_bytes: 3728
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

int main()
{
	char strN[11];
	int N;
	int S=0;
	int len;
	int num[11];

	cin >> strN;

	N=atoi(strN);
	len=strlen(strN);

	for(int i=0;i<len;i++){
		switch(strN[i]){
			case '1':	num[i]=1;
					break;
			case '2':	num[i]=2;
					break;
			case '3':	num[i]=3;
					break;
			case '4':	num[i]=4;
					break;
			case '5':	num[i]=5;
					break;
			case '6':	num[i]=6;
					break;
			case '7':	num[i]=7;
					break;
			case '8':	num[i]=8;
					break;
			case '9':	num[i]=9;
					break;
			default:	num[i]=0;
		}
		S=S+num[i];
	}

	if(N%S==0){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

constexpr long long MOD = 1000000007;

int main()
{
  int N;
  std::cin >> N;
  std::multiset<long long> pos;
  std::multiset<long long> neg;
  for (int i = 0; i < N; ++i)
  {
    int a;
    std::cin >> a;
    if (0 <= a)
      pos.insert(a);
    else
      neg.insert(a);
  }
  std::vector<std::pair<long long, long long>> ans;
  ans.reserve(N - 1);
  long long M;
  while (true)
  {
    if (pos.empty())
    {
      auto x = *neg.rbegin();
      neg.erase(std::prev(neg.end()));
      auto y = *neg.rbegin();
      neg.erase(std::prev(neg.end()));
      ans.push_back({x, y});
      if (neg.empty())
      {
        M = x - y;
        break;
      }
      pos.insert(x - y);
    }
    else
    {
      if (neg.empty())
      {
        auto y = *pos.begin();
        pos.erase(pos.begin());
        auto x = *pos.begin();
        pos.erase(pos.begin());
        ans.push_back({x, y});
        if (pos.empty())
        {
          M = x - y;
          break;
        }
        neg.insert(x - y);
      }
      else
      {
        auto x = *pos.rbegin();
        auto psize = pos.size();
        pos.erase(std::prev(pos.end()));
        auto y = *neg.begin();
        neg.erase(neg.begin());
        if (pos.empty() && neg.empty())
        {
          ans.push_back({x, y});
          M = x - y;
          break;
        }
        if (pos.size() < neg.size())
        {
          pos.insert(x - y);
          ans.push_back({x, y});
        }
        else
        {
          neg.insert(y - x);
          ans.push_back({y, x});
        }
      }
    }
  }

  std::cout << M << "\n";
  for (auto& pair: ans)
    std::cout << pair.first << " " << pair.second << "\n";
  std::cout << std::flush;

  return 0;
}



Measured memory_bytes: 8192
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

#define REP(i,n) for(int i=0;i<(n);i++)

int main(){
    string S;
    cin >> S;
    int N = S.size(), MOD = 1000000007;

    long long dp[100010][4] = {};
    for(int i = N; i >= 0; --i){
        for(int j = 3; j >= 0; --j){
            if(i == N){
                dp[i][j] = (j == 3 ? 1 : 0);
            }else{
                dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3LL : 1LL);
                if(j < 3 && (S[i] == '?' || S[i] == "ABC"[j])){
                    dp[i][j] += dp[i+1][j+1];
                }
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[0][0] << endl;
}


Measured memory_bytes: 3648
def main():
    s = input()
    max_len = 0
    length = 0

    s = list(s)
    s.append('')

    for i in s:
        if i in ['A', 'C', 'G', 'T']:
            length += 1
        else:
            if length > max_len:
                max_len = length
                length = 0

    print(max_len)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import math

n, x = map(int, input().split())
X = sorted(list(map(int, input().split())))
dis = [0] * (n-1)

xdis = 0
for i in range(n-1):
    dis[i] = X[i+1] - X[i]
    if X[i] <= x <= X[i+1]:
        xdis = min(abs(x-X[i]), abs(X[i+1]-x))

if n == 1:
    print(abs(X[0]-x))
    exit()
        
reg = xdis

for i in range(n-1):
    reg = math.gcd(reg, dis[i])

print(reg)

Measured memory_bytes: 20788
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;

int main() {

  long long int n;
  cin >> n;

  long long int ans = 0;
  vector< long long int > v;

  for ( long long int i = 0; i < n; i++ ) {
    long long int in;
    cin >> in;
    v.push_back( in );
  }

  sort( v.begin(), v.end() );

  if ( v[n-1] > n * ( n - 2 ) + n - 2 ) {

    ans += n - 2;
    v[n-1] -= n * ( n - 2 );
    for ( long long int j = 0; j < n - 1; j++ ) {
      v[j] += n-2;
    }

    for ( long long int i = 0; i < n; i++ ) {
      if ( v[i] > ( n + 1 ) * 2 ) {
	long long int cnt = ( v[i] - ( n + 1 ) * 2 ) / ( n + 1 ) + 1;
	ans += cnt * ( n + 1 );
	v[i] -= cnt * ( n + 1 );
      }
    }

  }

  while( true ) {

    bool f = true;
    for ( long long int i = 0; i < n; i++ ) {
      if ( v[i] >= n ) {
	f = false;
	long long int cnt = v[i] / n;
	ans += cnt;
	v[i] %= n;
	for ( long long int j = 0; j < n; j++ ) {
	  if ( j == i ) continue;
	  v[j] += cnt;
	}
	break;
      }
    }
    if ( f == true ) break;

  }

  cout << ans << endl;

  return 0;

}


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



int main(){
    ll N,K;
    string S;
    cin >> N >> K >> S;

    ll ans = 0;
    ll cnt_LR = 0;
    for(int i = 0; i < N - 1; i++){
        if(S[i] != S[i + 1]){
            cnt_LR++;
        }
    }

    ans = N - 1 - max(cnt_LR - 2 * K, ll(0));

    cout << ans << endl;

}


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

namespace ABC095_C
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');

            int A = int.Parse(input[0]);  //それぞれのピザの金額
            int B = int.Parse(input[1]);
            int AB = int.Parse(input[2]);
            int needA = int.Parse(input[3]);  //ピザの必要枚数
            int needB = int.Parse(input[4]);

            int common = Math.Min(needA, needB); //AとBが両方存在しているとき
            int single = Math.Abs(needA - needB); //残りがAとBのどちらかのとき
            int moreNeed = needA > needB ? A : B; //要求数の多いほうをの金額を代入
            int total = Math.Min((A + B) * common, AB * common * 2) + Math.Min(moreNeed * single, AB * single * 2);
            Console.WriteLine(total);
        }
    }
}


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

ll dp[55][2];

int main(){
  int n, p;
  cin >> n >> p;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  dp[0][0] = 1;
  rep(i,n) {
    if (a[i] % 2 == 0) {
      dp[i+1][0] += dp[i][0] * 2;
      dp[i+1][1] += dp[i][1] * 2;
    } else {
      dp[i+1][0] += dp[i][1] + dp[i][0];
      dp[i+1][1] += dp[i][0] + dp[i][1];
    }
  }
  cout << dp[n][p] << endl;
  return 0;
} 

Measured memory_bytes: 256
# ALDS_4_B - 二分探索

import sys

n = int(input())
S = list(map(int, sys.stdin.readline().strip().split()))
q = int(input())
T = list(map(int, sys.stdin.readline().strip().split()))


def search(i, S):  # i は探索対象 S : 探索する数列
    if S[0] > i:
        return False
    if S[-1] == i:
        return True

    left = 0
    right = len(S) - 1

    while right - left != 1:
        mid = int((left + right) / 2)
        if S[mid] <= i:
            left = mid
        else:
            right = mid

    if S[left] == i:
        return True
    else:
        return False


ans = 0
for t in T:
    if search(t, S):
        ans += 1

print(ans)



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

using namespace std;

vector< vector<int> > hyou(17, vector<int>(17, 0));

int count (int a, int b) {
	if (hyou[a][b] == 1 || a < 1 || b < 1) {
		return 0;
	} else if (a == 1 && b == 1) {
		return 1;
	} else {
		return count(a-1, b) + count(a, b-1);
	}
}

int main() {
	int a, b, n;
	int c, d;
	while (cin >> a >> b) {
		if (a == 0 && b == 0) {
			break;
		}
		for (int i = 0; i < 17; i++) {
			for (int j = 0; j < 17; j++) {
				hyou[i][j] = 0;
			}
		}
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> c >> d;
			hyou[c][d] = 1;
		}
		cout << count(a, b) << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #include<cmath>
// #include<cstdio>
// #include<cctype>
// #include<cstring>
// #include<iomanip>
// #include<iostream>
// #include<algorithm>
using namespace std;
#define maxn 600010
#define maxm 2000010
#define ll long long
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define rint register int
#define uint unsigned int
#define pir pair <ll ,ll >
#define ull unsigned long long

#define fir first
#define sec second
#define LS(x) ((x)<<1)
#define RS(x) ((x)<<1|1)
#define lowbit(i) (i&-i)
#define MID(l,r) ((l)+(r)>>1)

const ll INF=4e18;
const int BASE=131;
const double eps=1e-4;
const int mod=1000000007;
const int inf=1061109567;
const double pi=acos(-1);
const int inv2=(mod+1)>>1;

namespace Math{

	inline ll popcount(ll x){
		x = (x&0x55555555) + ((x>>1)&0x55555555);
		x = (x&0x33333333) + ((x>>2)&0x33333333);
		x = (x&0x0F0F0F0F) + ((x>>4)&0x0F0F0F0F);
		x = (x&0x00FF00FF) + ((x>>8)&0x00FF00FF);
		x = (x&0x0000FFFF) + ((x>>16)&0x0000FFFF);
		return x;
	}

	inline ll F(ll x,ll p){return x>=p?x-p:x;}
	inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
	inline ll ksm(ll x,ll t,ll p){
		ll res=1;while(t){
			if(t&1)res=1LL*res*x%p;
			x=1LL*x*x%p;t>>=1;
		}return res;
	}
	
}

// using Math::popcount;
using Math::ksm;
using Math::F;

template < typename tp >
inline void read ( tp & dig ) {
	char ch=getchar();ll flag=0;dig=0;
	while(!isdigit(ch)){ if(ch=='-')flag=1;ch=getchar(); }
	while(isdigit(ch))dig=dig*10+ch-'0',ch=getchar();
	if(flag)dig=-dig;
}

template < typename tp , typename ...Args >
inline void read ( tp & dig , Args & ...args ){
	read(dig);read(args...);
}

int n,sum1,sum2,a[maxn],b[maxn],c[maxn],s[maxn];
int f[610][310][310];

int main()
{

	read(n);int N=n<<1;
	for(int i=1;i<=N;++i)read(a[i]);
	for(int i=1;i<=N;i+=2){
		if(a[i]<0&&a[i+1]<0)++sum1;
		else if(a[i]>0&&a[i+1]>0)b[a[i]]=b[a[i+1]]=1;
		else ++sum2,c[a[i]>0?a[i]:a[i+1]]=1;
	}for(int i=N;i;--i)if(!b[i])s[++s[0]]=i;
	f[0][0][0]=1;
	for(int i=1;i<=s[0];++i)
		for(int j=0;j<=sum1+sum2;++j)
			for(int k=0;k<=sum2;++k){
				if(!f[i-1][j][k])continue;
				if(!c[s[i]]){
					f[i][j+1][k]=F(f[i][j+1][k]+f[i-1][j][k],mod);
					if(j)f[i][j-1][k]=F(f[i][j-1][k]+f[i-1][j][k],mod);
					if(k)f[i][j][k-1]=F(f[i][j][k-1]+1LL*k*f[i-1][j][k]%mod,mod);
				}else {
					f[i][j][k+1]=F(f[i][j][k+1]+f[i-1][j][k],mod);
					if(j)f[i][j-1][k]=F(f[i][j-1][k]+f[i-1][j][k],mod);
				}
			}
	int ans=f[s[0]][0][0];
	for(int i=1;i<=sum1;++i)
		ans=1LL*ans*i%mod;
	printf("%d\n",ans);return 0;

}

Measured memory_bytes: 231680
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int MOD = 1000000007;

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);

    int n,m;
    cin >> n >> m;
    VVI a(n,VI(n)),b(m,VI(m));
    REP(i,n){
        REP(j,n){
            char c;
            cin >> c;
            a[i][j] = (c=='#'?1:0);
        }
    }

    REP(i,m){
        REP(j,m){
            char c;
            cin >> c;
            b[i][j] = (c=='#'?1:0);
        }
    }

    REP(i,n-m+1){
        REP(j,n-m+1){
            bool f = true;
            REP(k,m){
                REP(l,m){
                    if(a[i+k][j+l]!=b[k][l]){
                        f=false;
                        break;
                    }
                }
                if(!f){
                    break;
                }
            }
            if(f){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

int main()
{
    int n, H;
    bool flag;
    flag = true;
    cin >> n;
    vector<int> x, y, h;
    x.resize(n);
    y.resize(n);
    h.resize(n);
    for (int i=0; i<n; ++i){
        cin >> x[i] >> y[i] >> h[i];
    }
    
    for (int cx=0; cx<=100; cx++){
        for (int cy=0; cy<=100; cy++){
            flag = true;
            for (int i=0; i<n; ++i){
                if(h[i] >= 1){
                    H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
                    break;
                }
            }
            for (int i=0; i<n; ++i){
                if(max(0, H - abs(x[i] - cx) - abs(y[i] - cy)) != h[i]){
                    flag = false;
                }
            }
            if(flag){
                cout << cx << " " << cy << " " << H << endl;
            }
        }
    }
}

Measured memory_bytes: 256
N, W = map(int, input().split())
w, v = [], []
for i in range(N):
	x, y = map(int, input().split())
	w.append(x)
	v.append(y)

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j < w[i]:
			dp[i + 1][j] = dp[i][j]
		else:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])

print(dp[N][W])

Measured memory_bytes: 120428
n, k = gets.split.map(&:to_i)
h = Array.new(n){gets.to_i}.sort
l=0
ans = 1<<30

(0..h.length-k).each do |i|
  delta = (h[k+i-1] - h[i]).abs
  if delta < ans
    ans = delta
  end
end

p ans


Measured memory_bytes: 4464
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int C[500], S[500], F[500];
int N, i;

void next_arrive_time(int now_n, int now_t) {
    if (now_n == N-1) cout << now_t << endl;
    else {
        int next_dep_t;
        next_dep_t = max(S[now_n], (now_t + (F[now_n] - 1)) / F[now_n] * F[now_n]);
        next_arrive_time(now_n + 1, next_dep_t + C[now_n]);
    }
}

int main(){
    scanf("%d", &N);
    for (i=0; i<N-1; i++) scanf("%d %d %d", &C[i], &S[i], &F[i]);

    for (i=0; i<N; i++) next_arrive_time(i, 0);

    return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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
from bisect import bisect
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
A = LIST()

def solve(lis):
	lis = lis.copy()
	tmp_sum = lis[0]
	lis = lis[1:]
	cnt = 0
	for x in lis:
		if (tmp_sum + x) * tmp_sum < 0:  # 異符号
			tmp_sum += x
		else:
			 if tmp_sum > 0:
			 	cnt += abs(-tmp_sum-1-x)
			 	tmp_sum = -1
			 else:
			 	cnt += abs(-tmp_sum+1-x)
			 	tmp_sum = 1
	return cnt

if A[0] > 0:
	ans = solve(A)
	B = A.copy()
	B[0] = -1
	ans = min(ans, solve(B)+abs(A[0]+1))
elif A[0] < 0:
	ans = solve(A)
	B = A.copy()
	B[0] = 1
	ans = min(ans, solve(B)+abs(A[0]-1))
else:
	A[0] = 1
	ans = solve(A)+1
	A[0] = -1
	ans = min(ans, solve(A)+1)
print(ans)


Measured memory_bytes: 16348
#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]))
#define LL long long
#define VI vector<int>
#define VL vector<LL>
#define VII vector< vector<int> >
#define VLL vector< vector<LL> >
#define VS  vector<string>
#define VSS vector< vector<string> >
#define PII pair<int,int>
#define PIS pair<int,string>
#define PSI pair<string,int>
#define PLL pair<LL,LL>
const LL MOD = 1000000007;
const LL INF = 1e16;
LL facctorialMethod(int k);
int main(){
    LL n,k,total;
    cin >> n >> k;
    VL l(n);
    for(int i = 0; i < n; i++) {
        cin >> l[i];
    }
    sort(l.begin(),l.end());
    reverse(l.begin(),l.end());

    total = 0;
    for(int i = 0; i < k; i++) {
        total += l[i];
    }
    cout << total << endl;

    return 0;
}

LL facctorialMethod(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i){
        sum *= i;
    }
    return sum;
}


Measured memory_bytes: 3612
S = int(input())
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, S + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans = 0
for r in range(1, S//3+1):
    ans += cmb(S-3*r+r-1, r-1, mod)
    ans %= mod
print(ans)

Measured memory_bytes: 9276
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]

sset = list(set(s))
imax = 0
for i in range(len(sset)):
    if imax < s.count(sset[i]) - t.count(sset[i]):
        imax = s.count(sset[i]) - t.count(sset[i])
print(imax)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long

using namespace std;

int x=0,y=0,a=0,b=0,c=0;
int p[100001];
int q[100001];
int r[100001];
int res=0;
multiset<int> Set1, Set2;

signed main()
{
	scanf("%lld%lld%lld%lld%lld", &x, &y, &a, &b, &c);
	for (int i=0; i<a; i++)
		scanf("%lld", &p[i]);
	for (int i=0; i<b; i++)
		scanf("%lld", &q[i]);
	for (int i=0; i<c; i++)
		scanf("%lld", &r[i]);
	sort(r, r+c);
	reverse(r, r+c);
	for (int i=0; i<a; i++)
	{
		Set1.insert(p[i]);
	}
	for (int i=0; i<b; i++)
		Set2.insert(q[i]);
	while (Set1.size()>x)
		Set1.erase(Set1.begin());
	while (Set2.size()>y)
		Set2.erase(Set2.begin());
	for (auto ss : Set1)
		res+=ss;
	for (auto ss : Set2)
		res+=ss;
	for (int i=0; i<c; i++)	
	{
		int m1 = (*Set1.begin());
		int m2 = (*Set2.begin());
		if (m1<m2)
		{
			Set1.insert(r[i]);
			res+=max(0ll, r[i]-1ll*(*Set1.begin()));
			Set1.erase(Set1.begin());
		}
		else
		{
			Set2.insert(r[i]);
			res+=max(0ll, r[i]-1ll*(*Set2.begin()));
			Set2.erase(Set2.begin());
		}
	}	
	cout << res;
	return 0;
}


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

namespace abc050_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] T = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int M = int.Parse(Console.ReadLine());
            for (int i = 0; i < M; i++)
            {
                int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
                Console.WriteLine(T.Sum() - T[x[0] - 1] + x[1]);
            }
        }
    }
}

Measured memory_bytes: 3032
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
#include <set>
#include <stack>
#include <cstdlib>

bool find(std::vector<int> &m, int goal)
{
    std::set<int> cand, cand_n;
    cand.insert(0);
    for(auto v : m)
    {
        for(auto w : cand)
        {
            cand_n.insert(w+v);
            cand_n.insert(w-v);
        }
        cand.clear();
        cand.swap(cand_n);
    }
    return cand.find(goal) != cand.end();
}

int main(void)
{
    std::string commands;
    int x_goal, y_goal;
    std::cin >> commands >> x_goal >> y_goal;

    std::vector<int> xm;
    std::vector<int> ym;
    bool d_is_x = true;
    int distance = 0;
    bool first_x = true;
    commands += 'T';
    for(int i=0; i<commands.size(); ++i)
    {
        if(commands[i] == 'T')
        {
            if(d_is_x)
            {
                if(first_x)
                {
                    x_goal -= distance;
                    first_x = false;
                }
                else
                    xm.push_back(distance);
            }
            else
                ym.push_back(distance);
            distance = 0;
            d_is_x = !d_is_x;
        }
        else // F
            ++distance;
    }
    bool xf = find(xm, x_goal);
    bool yf = find(ym, y_goal);        
    std::cout << (xf && yf ? "Yes" : "No") << std::endl;
    return 0;
}


Measured memory_bytes: 640
n,k = map(int,input().split())

if k > (n-1)*(n-2)/2:
    print(-1)
else:
    l = [[1,_] for _ in range(2,n+1)]
    next = [2,3]
    d = int((n-1)*(n-2)/2) - k
    for i in range(d):
        l.append(next[:])
        if next[1] != n:
            next[1] += 1
        else:
            next[0] += 1
            next[1] = next[0] + 1
    print(len(l))
    for ll in l:
        print(ll[0],ll[1])


Measured memory_bytes: 4120
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
// const int MOD = 1e9 + 7;

int main() {
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        if (S[i] == '+')
            ans++;
        else if (S[i] == '-')
            ans--;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
alist = list(map(lambda x:int(x) - 1,input().split()))
count = [0]*n
count[0] += 1
now = 0
order = [0]
for i in range(k):
    now = alist[now]
    count[now] += 1
    if count[now] == 2:
        start = order.index(now)
        loop = len(order[start:])
        syoki = len(order[:start])
        break
    order.append(now)
else:
    print(now+1)
    exit()
k -= syoki
k %= loop
print(order[k+syoki] + 1)

Measured memory_bytes: 103616
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;

typedef long double lld;

#define REP(i,n) for(int i=0;i<n;i++)
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))

ll A, P;

int main()
{
	cin >> A >> P;
	ll B = A * 3;
	cout << (B + P) / 2 << endl;

}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  int max_h = -1;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (h[i] >= max_h) {
      max_h = h[i];
      ans++;
    }
  }
  cout << ans << endl;

}

    
    
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<int>(1000,10000)(rng)

ll binpow(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
        return res * a;
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    cout<<(10000-n)%1000;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;

const ll INF = 10010010010;

void warshall_floyd(int n, vector<vector<ll> > &D) {
  rep(k,n) rep(i,n) rep(j,n) D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n, m, r;
  cin >> n >> m >> r;
  vector<int> R(r);
  rep(i,r) {
    cin >> R[i];
    R[i]--;
  }
  sort(R.begin(), R.end());
  vector<vector<ll> > dist(n, vector<ll>(n, INF));
  rep(i,m) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--; b--;
    dist[a][b] = c;
    dist[b][a] = c;
  }
  warshall_floyd(n, dist);
  ll ans = INF;
  do {
    ll temp = 0;
    rep(i,r-1) {
      temp += dist[R[i]][R[i+1]];
    }
    ans = min(ans, temp);
  } while (next_permutation(R.begin(), R.end()));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cnt = 0
for i in range(N):
  if i != N-1:
#    cnt += min(A[i], B[i])
    if A[i] >= B[i]:
      cnt += B[i]
    else:
      cnt += A[i]
      kantuu = B[i] - A[i]
      # A[i+1]のうち、倒す数
      taosu = min(A[i+1], kantuu)
      cnt += taosu
      A[i+1] -= taosu
  else:
    cnt += min((A[i]+A[i+1]), B[i])
print(cnt)

Measured memory_bytes: 19156
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int n, a[500000];
long long MOD = 1e9 + 7;
long long ans = 1;
set<pair<int, int> > ss;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    long long before = 0;
    for (int i = 0; i < n; i++)
    {
        before++;
        ss.insert({a[i], 1});
        while (ss.size() > 1)
        {
            auto it1 = ss.end(), it2 = ss.end();
            it1--, it2--, it2--;
            pair<int, int> a = *it1, b = *it2;
            int firo = a.first - (a.second - 1) * 2;
            if (firo > b.first + 2)
                break;
            if (firo == b.first + 2)
            {
                ss.erase(a);
                ss.erase(b);
                ss.insert({a.first, a.second + b.second});
                break;
            }
            if (firo == b.first + 1)
            {
                ss.erase(a);
                ss.erase(b);
                ss.insert({a.first, a.second + b.second});
            }
        }
        int t = 0;
        while (ss.size())
        {
            auto it = ss.begin();
            pair<int, int> a = *it;
            if (a.first - (a.second - 1) * 2 <= 0)
            {
                ss.erase(a);
                ss.insert({a.first, a.second - 1});
                before--;
                t = 1;
            }
            else
            {
                break;
            }
        }
        //cout << before + t << " ";
        ans = ans * (before + t) % MOD;
    }
    cout << ans;
}


Measured memory_bytes: 5248
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var c = int.Parse(line[2]);
        var d = int.Parse(line[3]);
        if (Math.Abs(a - c) <= d) { Console.WriteLine("Yes"); goto end; }
        if (Math.Abs(a-b)  <= d && Math.Abs(b - c) <= d) { Console.WriteLine("Yes"); goto end; }
        Console.WriteLine("No");
    end:;
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=a;i<=2999;i+=a)
	{
		if(i%b==c)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 256
N, M=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]

def DFS(ab):
    S=ab[0][0]
    graph=[[0 for i in range(N)] for j in range(N)]
    for i in range(len(ab)):
        graph[(ab[i][0]-1)][(ab[i][1]-1)]=1
        graph[(ab[i][1]-1)][(ab[i][0]-1)]=1
    reached=[0 for _ in range(N)]
    Stack=[S]
    reached[S-1]=1
    while Stack:
        h=Stack.pop()
        for i in range(N):
            if graph[h][i]==1:
                if not(reached[i-1]):
                    Stack.append(i)
                    reached[i-1]=1
    return(sum(reached))

ans=0
for i in range(M):
    a=ab[:i]+ab[i+1:]
    if DFS(a)!=N:
        ans+=1
print(ans)


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

template <class T>
struct BIT {
  vector<T> lst;
  int treesize;
  // constructor
  BIT(int newn = 0) {
    treesize = newn;
    lst.resize(treesize + 1);
    for(int i = 0; i <= treesize; ++i) lst[i] = 0;
  }
  // a_place += num
  bool add(int place, T num) {
    while(place <= treesize) {
      lst[place] += num;
      place += place & -place;
    }
    return 1;
  }
  // add wide ver.(add num between l and r)
  bool addw(int left, int right, T num) {
    while(left <= right && left >= 1 && right <= treesize)
      add(left++, num);
    return 1;
  }
  // sum between [0,place]
  T calcsum(int place) {
    T answer = 0;
    while(place > 0) {
      answer += lst[place];
      place -= place & -place;
    }
    return answer;
  }
  // sum [l,r]
  T calcsumw(int left, int right) {
    return calcsum(right) - calcsum(left - 1);
  }
};

long long n, q;

int main() {
  cin >> n >> q;
  BIT<long long> bit(n);
  for(int i = 0; i < q; ++i) {
    long long c, x, y, z;
    cin >> c >> x >> y;
    if(c) { cout << bit.calcsumw(x, y) << endl; }
    else {
      bit.add(x, y);
    }
  }
  return 0;
}



Measured memory_bytes: 3508
#include<stdio.h>
int main(void){
  int N;
  scanf("%d",&N);
  int i,judge,two=1;
  for(i=0;i<7;i++){
    if(N>=two){
      judge=two;
      two*=2;
    }
    else break; 
  }
  printf("%d",judge);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define INFTY 10000000000
typedef long long int ll;
const int MOD=1000000007;
using Graph = vector<vector<int>>;
using ipair = pair<ll,ll>;
bool operator< (const ipair a, const ipair b){return a.first < b.first;};
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int main(){
  int x,y,a,b,c;
  cin>>x>>y>>a>>b>>c;
  priority_queue<ll,vector<ll>,greater<ll>> p,q,r;
  priority_queue<ll,vector<ll>,less<ll>> apple;
  rep(i,a){int num;cin>>num;p.push(num);}
  rep(i,b){int num;cin>>num;q.push(num);}
  rep(i,c){int num;cin>>num;r.push(num);}

  int ok = 1;
  int cnx=0,cny=0;
  ll ans = 0;
  rep(i,a-x)p.pop();
  rep(i,b-y)q.pop();
  rep(i,x){
    ll ap = p.top();p.pop();
    apple.push(ap);
  }
  rep(i,y){
    ll ap = q.top();q.pop();
    apple.push(ap);
  }
  rep(i,c){
    ll ap = r.top();r.pop();
    apple.push(ap);
  }
  rep(i,x+y){
    ll cal = apple.top();apple.pop();
    ans += cal;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 8048
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    int K,T;cin >> K >> T;
    vector<int> a(T);rep(i,T)cin >> a[i];
    sort(rall(a));
    int ma = a[0];
    int sum = -1 * a[0];
    rep(i,T)sum += a[i];

    if(ma-1 <= sum)cout << 0 << endl;
    else{
        cout << ma-1-sum << endl;
    }
}

Measured memory_bytes: 256