akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const double PI=3.14159265358979323846;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  vstring s(n);
  rep(i,n){
    cin>>s[i];
    sort(all(s[i]));
  }
  sort(all(s));
  ll count=0;
  rep(i,n){
    auto low=lower_bound(all(s),s[i]);
    auto up=upper_bound(all(s),s[i]);
    count+=up-low-1;
  }
  cout<<count/2<<'\n';
  return(0);
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K;
  string S;
  cin >> K;
  cin >> S;
  if(S.size()<=K){
  	cout<<S<<endl;
  }else{
  	string dos = S.substr(0,K);
    cout<<dos + "..."<<endl;
  }
}

Measured memory_bytes: 3632
(let((a(read))(b(read))(c(read))(x(read))(s 0))
  (loop for i from 0 to a do(loop for j from 0 to b do(loop for k from 0 to c do
	(if(=(+(* i 500)(* j 100)(* k 50))x)(incf s)))))
  (princ s))


Measured memory_bytes: 11108
import java.util.ArrayList; 
import java.util.List;
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;


class Main {

    public static void main(String[] args) {
        Scanner stdIn=new Scanner(System.in);
        int x=stdIn.nextInt();
        List<String> list=new ArrayList<String>(){
            {
                for(int i=0; i<x; i++){
                    add(stdIn.next());
                }
            }
        };
       
        Map<String,Integer> map=new HashMap<>();
        for(String s:list){
            Integer i=map.get(s);
            map.put(s,i==null?1:i+1);
        }

        System.out.println(map.size());
        
    }

    

}

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

public class Main{
    public static void main(String[] args)throws Exception{
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] ary=new int[n];
        int total=0;
        for(int i=0;i<n;i++){
            ary[i]=sc.nextInt();
            total+=ary[i];
        }
        Arrays.sort(ary);
        if((double)ary[n-m]>=(double)total/(4*m)){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std; 
int main(){
  int N,i,x=1;
  cin>>N;
  vector<int>a(N);
  for(i=0;i<N;i++)cin>>a.at(i);
  for(i=0;i<N;i++){
    x=a.at(x-1);
    if(x==2)break;
  }
  if(x==2)cout<<i+1<<endl;
  else cout<<-1<<endl;
}

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

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

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

int main() {
    double d;
    cin >> d;
    printf("%.10lf", max(sqrt(2)*d, (int)(d)+1.0));
    return 0;
}


Measured memory_bytes: 3268
from math import gcd
import numpy as np


def sum_gcd(k: int) -> int:
    # a > b > c
    sum_p1 = 0
    for h in range(1, k + 1):
        for i in range(1, h):
            for j in range(1, i):
                sum_p1 += gcd(gcd(h, i), j)
                
    # a = b > c and a > b = c
    sum_p2 = 0
    for h in range(1, k + 1):
        for i in range(1, h):
            sum_p2 += gcd(h, i)

    # a = b = c
    sum_p3 = k * (k + 1) //2

    answer = sum_p1 * 6 + sum_p2 * 6 + sum_p3
    
    return answer


def main():
    k = int(input().rstrip())
    print(sum_gcd(k))


if __name__ == '__main__':
    main()



Measured memory_bytes: 26936
#include <stdio.h>
#include <string.h>

#define BUF (100005)

char s[BUF];
void input(void){
	scanf("%s",s);
}

int main(void){
	input();

	char tmp[BUF]="";
	int cnt=0;
	for(int i=0;i<strlen(s);i++){
		if(i%2==0){
			tmp[cnt] = s[i];
			cnt++;
		}
	}
	printf("%s\n",tmp);
	return 0;
}


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

int main(){
  string n;
  cin >> n;
  for(int i = 0 ; i < n.size() ; i++){
    if(n[i] == '1'){
      cout << 9;
    }else if(n[i] == '9'){
      cout << 1;
    }else{
      cout << n[i];
    }
  }
  cout << endl;
  return 0;
}

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

int main()
{
    // 入力
    int a;
    cin >> a;

    string s;
    cin >> s;

    if (a >= 3200) {
        cout << s << endl;
    } else {
        cout << "red" << endl;
    }
    // 出力
    return 0;
}


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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string t, b;
  cin >> t >> b;
  vint dp(b.size()+1);
  dp[0] = 1;
  rep(i, t.size()) {
    for(int j = b.size()-1; j >= 0; --j) {
      if(t[i] == b[j]) (dp[j+1] += dp[j]) %= mod;
    }
  }
  cout << dp[b.size()] << endl;

  return 0;
}



Measured memory_bytes: 3216
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include <cassert>
    #include <cmath>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;
    using Graph = vector<vector<int>>;


    vector<bool> seen;
    void dfs(const Graph &G,int v){
        int cnt = 0;
        seen[v] = true;
        for(auto nv:G[v]){
            if(seen[nv])continue;
            cnt++;
            dfs(G,nv);
        }
    }

    int main(){
      ll h;cin>>h;
      ll cnt = 0;
      while(h>0){
          cnt++;
          h/=2;
      }
      ll ans = pow(2,cnt)-1;
      cout<<ans;
    }


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) {
  v = vector<T>(n, x);
}
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n) {
  v = vector<T>(n); for (lli i=0; i<n; ++i) cin >> v[i];
}
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli N, W;
vector<lli> w, v;
vector<lli> dp;
int main() {
  cin >> N >> W;
  init_n(w, N);
  init_n(v, N);
  for (lli i=0; i<N; ++i) cin >> w[i] >> v[i];
  init_n(dp, 1000 * N + 1, 1e10);
  dp[0] = 0;
  for (lli i=0; i<N; ++i) {
    for (lli j=dp.size()-1; j>0; --j) {
      lli k = j - v[i];
      dp[j] = min(dp[j], (k>=0 ? dp[k] : 0) + w[i]); 
    }
  }
  lli j;
  for (j=dp.size()-1; j>0 && dp[j]>W; --j);
  cout << j << endl;

  return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll n, a, b;
  cin >> n >> a >> b;
  if(a%2==b%2){
    cout << (b-a)/2 << endl;
  }else{
    cout << min(a - 1, n - b) + 1 + (b - a - 1) / 2 << endl;
  }
}

Measured memory_bytes: 256
N, Y = map(int, input().split())

def otoshidama():
    for i in range(N+1):
        for j in range(N+1-i):
            if i * 10000 + j * 5000 + 1000 * (N-i-j) == Y:
                return str(i) + " " + str(j) + " " + str(N-i-j)
    return "-1 -1 -1"

print(otoshidama())

Measured memory_bytes: 3060
attrs = Array.new
while line = $stdin.gets
    attrs << line.chomp.split.map{|v| v.to_i }
end

tmp = attrs.shift
N = tmp[0]
X = tmp[1]
L = attrs.shift

bound = 1
d = 0
L.each{|n|
  d += n
  bound += 1 if d <= X
}
puts bound

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

int n,s;
int dp[350][1024];

int rec(int k,int sum,int u){
  int res = 0;
  if(k==0 && sum==0)return 1;
  if(dp[sum][u] >= 0)return dp[sum][u];
  if(k==0)return 0; 

  for(int i=0;i<10;i++){
    if(u>>i &1){
      if(sum-k*i>=0)res += rec(k-1,sum - k*i,u - (1<<i));
    }
  }
  dp[sum][u] = res;
  return res;
}


int main(){
  for(int i=0;i<350;i++){
    for(int j=0;j<1024;j++)dp[i][j] = -1;
  }
  while(cin >> n >> s){
    if(s>330)cout << 0 << endl;
    else{
      int up = 0;
      for(int i=0;i<n;i++)up += (9-i)*(n-i);
      for(int i=0;i<=up;i++){
	for(int j=0;j<1024;j++)dp[i][j] = -1;
      }
      cout << rec(n,s,1023) << endl;
    }
  }
}

Measured memory_bytes: 0
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int cr, cg, cb;
int cnt;
string s;
int n;

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

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'R') cr++;
		else if (s[i] == 'G') cg++;
		else cb++;

		for (int j = i - 1; j >= 0; j--) {
			int k = 2 * i - j;
			if (k >= s.size()) break;
			if (s[i] != s[j] && s[j] != s[k] && s[i] != s[k]) {
				cnt++;
			}
		}
	}

	cout << cr * 1ll * cg * cb - cnt << endl;

	return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>

int main(){
	int a,b,i;
	long long unsigned ans=1;
	scanf("%d%d",&a,&b);
	ans=ans*b;
	for(i=0;i<a-1;i++)ans=ans*(b-1);
	printf("%llu\n",ans);
	return 0;
}

Measured memory_bytes: 128
import java.io.*;
import java.util.*;
public class Main { // "Main" should be used for most online judges
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s = sc.nextLine();
		//int count = sc.nextInt();
		//int nums[] = new int[count];
		/*int size = nums.length / 2;
		for(int i = 0; i < nums.length; i++) {
		}*/
		int num1 = sc.nextInt();
		int num2 = sc.nextInt();
		int num3 = num1*num2;
		if(num3 % 2 == 0) System.out.println("Even");
		else System.out.println("Odd");
	}
}

Measured memory_bytes: 20948
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;


int main(){
long long N,D,A,X,H;
cin>>N>>D>>A;
vector<pair<long long,long long> > pairs(N);
for(long long i=0;i<N;++i){
  cin>>X>>H;
  pairs[i]=make_pair(X,H);
}
//Xを昇順でsort
sort(pairs.begin(),pairs.end());
long long ans=0;
long long damage=0;
long long target=0;
queue<pair<long long,long long>> que;
long long num=0;
for(int i=0;i<N;++i){
  while(!que.empty() && que.front().first < pairs[i].first){
    num -= que.front().second;
    que.pop();
  }
  pairs[i].second-=num;
  if(pairs[i].second<=0){
    continue;
  }
  ans+=((pairs[i].second-1)/A+1);
  que.push(make_pair(pairs[i].first+D*2,((pairs[i].second-1)/A+1)*A));
  num+=((pairs[i].second-1)/A+1)*A;
}
cout<<ans<<"\n";
return 0;
}

Measured memory_bytes: 4992
#include<stdio.h>
#define MAX 102
#define WHITE 0
#define BLACK 1
#define GRAY 2
#define NIL -1

void init();

int n, head = 0, tail = 0, color[MAX];
int d[MAX], edge[MAX], G[MAX][MAX];



void init(){
  int i;

  for(i = 0; i <= n; i++){
      color[i] = WHITE;
      d[i] = 10000000;    
  }
  
}

/*void Enqueue(int x){
  if((head == 1 && tail == length) || head == tail+1){
    return NIL;
  }

  Q[tail] = x;

  if(tail == length){
    tail = 1;
  } else {
    tail = tail+1;
  }

  }*/

void Enqueue(int *Q, int x){
 
  if(tail == n){
    tail = 1;
  } else {
    tail += 1;
  }
 
 Q[tail] = x;
}
 
int Dequeue(int *Q){
  if(head == n){
    head = 1;
  } else {
    head++;
  }
  return Q[head];
}

void BFS(){
  int i, s = 1, u, j = 0;
  int Q[101];
  init();

  color[s] = GRAY;
  d[s] = 0;
  for(i = 0 ; i <= n; i++){
    Q[i] = 0;
  }
  Enqueue(Q, s);

  while(head != tail){
    u = Dequeue(Q);
    
    for(i = 1; i <= n; i++){
      if(color[i] == WHITE && G[u][i] == 10){ 
	color[i] = GRAY;
	d[i] = d[u] + 1;
	Enqueue(Q, i); 
      }
    }
    color[u] = BLACK;
    j++;  
  }
  
  
}


int main(){
  
  int i,j,k = 0,vertex,number;
  
  scanf("%d",&n);

  for(i = 1; i <= n; i++){
    scanf("%d %d",&vertex,&edge[i]);
    for(j = 1; j <= edge[i]; j++){
      scanf("%d",&number);
      G[vertex][number] = 10;
    }

  }

  /*for(i = 1; i <= n; i++){
    for(j = 1; j <= n; j++){
      printf("%d ",G[i][j]);
    }
    printf("\n");
    }*/

    BFS();
  
   for(i = 1; i <= n; i++){
    if(d[i] == 10000000){
      printf("%d %d\n", i, -1);
    } else {
    printf("%d %d\n", i, d[i]);
    }
  }

  return 0;

}

Measured memory_bytes: 0
// clang-format off
	#include <bits/stdc++.h>
	using namespace std; using ll = long long; using uint = unsigned int;
	#define SFINAE(x, ...)	template <class, class = void> struct x : false_type {}; template <class T> struct x<T, void_t<__VA_ARGS__>> : true_type {};
	SFINAE(DefaultIO, decltype(cout << declval<T &>()))
	SFINAE(IsTuple, typename tuple_size<T>::type)
	SFINAE(Iterable, decltype(begin(declval<T>())))
	template <class T> constexpr char Space(const T &) { return (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' '; }
	template <auto &os> struct Writer {
		template <class T> void Impl(T const &t) const {
			if constexpr (DefaultIO<T>::value) os << t;
			else if constexpr (Iterable<T>::value) { int i = 0; for (auto &&x : t) ((i++) ? (os << Space(x), Impl(x)) : Impl(x)); }
			else if constexpr (IsTuple<T>::value) apply([this](auto const &... args) { int i = 0; (((i++) ? (os << ' ', Impl(args)) : Impl(args)), ...);}, t);
			else static_assert(IsTuple<T>::value, "No matching type for print");
		}
		template <class F, class... Ts> auto &operator()(F const &f, Ts const &... ts) const { return Impl(f), ((os << ' ', Impl(ts)), ...), os << '\n', *this; }
	};
	template <auto &is> struct Reader {
		template <class T> auto& operator()(T &t) const {
			if constexpr (DefaultIO<T>::value) is >> t;
			else if constexpr (Iterable<T>::value) for (auto &x : t) (*this)(x);
			else if constexpr (IsTuple<T>::value) apply([this](auto &... args) { ((*this)(args), ...); }, t);
			else static_assert(IsTuple<T>::value, "No matching type for read");
			return *this;
		}
	};
	#ifdef NARUT_LOCAL
	#define Debug(...) cerr << "\033[0;31m", Writer<cerr>{}(__VA_ARGS__), cerr << "\033[0m\n"
	#else
	#define Debug(...) 0
	#endif
	[[maybe_unused]] constexpr Reader<cin> Cin; [[maybe_unused]] constexpr Writer<cout> Cout;
	#define FOR(i, j, n) for (int i = int(j); i < int(n); ++i)
	#define ROF(i, j, n) for (int i = int(n) - 1; i >= int(j); --i)
// clang-format on





auto Main() {
	ll a;
	cin>>a;
	cout<<a+a*a+a*a*a;	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
#ifdef NARUT_LOCAL
	assert(freopen("io/test.in", "r", stdin));
	cin.exceptions(cin.badbit | cin.failbit);
	cerr << fixed << setprecision(10);
#endif

	Main();
}


Measured memory_bytes: 3644
using System;
using System.Collections.Generic;
class Program
{

    static void Main()
    {
        string N = Console.ReadLine();
        int n = int.Parse(N);
        string[] Ai = Console.ReadLine().Split(' ');
        long[] a = new long[n];
        long o1 = 0;
        long o2 = 0;
        long o3 = 0;

        for(int i=0;i<n;i++)
        {
            a[i] = long.Parse(Ai[i]);
        }

        for(int i=0;i<n;i++)
        {
            if(a[i]<o1)
            {
                o2 = o1 - a[i];
            }

            o3 += o2;

            if (a[i] > o1)
            {
                o1 = a[i];
            }
            o2 = 0;
        }

        Console.WriteLine(o3);

    }

}



Measured memory_bytes: 46620
n = gets.to_i
p = Array.new(n-1)
p = gets.split(" ").map(&:to_i);
count = 0
for i in 1..n-2 do
    if p[i] > p[i-1] && p[i] <= p[i+1]
        count += 1
    else
        if p[i] >= p[i-1] && p[i] < p[i+1]
            count += 1
        else
            if p[i] < p[i-1] && p[i] >= p[i+1]
                count += 1
            else
                if p[i] <= p[i-1] && p[i] > p[i+1]
                    count += 1
                end
            end
        end
    end
end
puts count


Measured memory_bytes: 1788
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
using namespace std;
namespace adaptor = boost::adaptors;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define cy cout << "Yes" << endl
#define cn cout << "No" << endl
typedef long long ll;


bool CheckIfContra(int N, vector<int> S, vector<vector<int>> table){
  	// 正直者は 1, 不親切は -1 にする
  	vector<int> v(N,-1);
	for(auto i : S){
      	v[i] = 1;
    }
	/*  
  	cout << "v[i] = ";
  	rep(i,N){
		cout << v[i] << ", ";
    }
  	cout << endl;
  	*/
	
  	rep(j,N){
     	for(auto i : S){
			//cout << i << "," << j << ": ";
          	if(table[i][j] == 0){
              ;
            	//cout << "case1" << endl;
            }
          	else if(table[i][j] != v[j]){ 
				// 矛盾する
              	// cout << "(i, j) = (" << i << ", " << j <<"), v[j] = " << v[j] << endl;
              	return true;
            }
        } 
    }
    // 矛盾しない
	return false;
}

void Main()
{
	int N;
  	cin >> N;
  	vector<vector<int>> table(N, vector<int>(N));
  	
  	rep(i,N){
      	int A; 
      	cin >> A;
      	rep(j,A){
          	int x, y;
      		cin >> x >> y;
          	x--;
			table[i][x] = y*2-1; // 1 -> 1, 0 -> -1
        }
    }
  	
  /*
  	cout << "table[i][j] = " << endl;
  	rep(i,N){
      rep(j,N){
		cout << table[i][j] << " " ;
      }
      cout << endl;
    }
	cout << endl;
  */
  
  /*
	vector<int>S = {};
  	if(CheckIfContra(N, S, table)){
      	cout << "Contradict" << endl;
    }
  	else{
  		cout << "No Contradict" << endl;
  	}
    */
  	
  	// bit 全探索
  	int temp = 0;
  	for(int bit = 0; bit < (1<<N); bit++){
        vector<int> S;
        for (int i = 0; i < N; ++i) {
            if (bit & (1<<i)) { // i が bit に入るかどうか
                S.push_back(i);
            }
        }
      	// S に入っている i を正直者, そうでない番号を不親切と仮定
      	// 矛盾しなかったらそのときの正直者の総数を記憶しておく
      	int sz = S.size();
      	//cout << "bit = " << bit << ", CheckIFContra = " << CheckIfContra(N,S,table) << endl;
    	if(!CheckIfContra(N, S, table)){ temp = max(temp, sz); }
    }
  	cout << temp << endl;
  
    return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 256
n, t = map(int, input().split())
t_list = list(map(int, input().split()))

ans = 0

if n != 1:
	
	for i in range(n-1):
		diff = t_list[i+1] - t_list[i]
		if t >= diff:
			ans += diff
		else:
			ans += t
			
	ans += t
	
	
else:
	ans = t
	
print(ans)

Measured memory_bytes: 26708
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[3],k;
	cin>>a[0]>>a[1]>>a[2]>>k;
	sort(a,a+3);
	for(int i=0;i<k;i++)
		a[2]*=2;
	cout<<a[0]+a[1]+a[2];
	return 0;
}

Measured memory_bytes: 256
/* ALDS1_3_C: Stable Sort */

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define N 36

typedef struct {
	char suit;
	int value;
} Card;

void bubbleSort(Card *A, int n);
void selectionSort(Card *A, int n);
void swap(Card *A, int x, int y);
void isStable(Card *A, Card* B, int n);
void print(Card *A, int n);

int main(void){
	int n, i = 0;
	Card c1[N], c2[N];

	scanf("%d", &n);
	getchar();
	while(i < n){

		scanf("%c%d", &(c1[i].suit), &(c1[i].value));
		getchar();
		/*c1[i].suit = getchar();
		c1[i].value = getchar();*/
		c2[i] = c1[i];
		i++;
	}

	bubbleSort(c1, n);
	print(c1, n);
	printf("Stable\n");
	selectionSort(c2, n);
	print(c2, n);
	isStable(c1, c2, n);

	return 0;
}

void bubbleSort(Card *A, int n){
	int sw = 0, i, j;

	for(i = 0; i < n-1; i++){
		for(j = n-1; j > i; j--){
			if(A[j].value < A[j - 1].value) swap(A, j, j-1);
		}
	}
}


void selectionSort(Card *A, int n){
	int min_id, i, j, sw = 0;

	for(i = 0; i < n - 1; i++){
		min_id = i;
		for(j = i+1; j < n; j++){
			if(A[j].value < A[min_id].value){
				min_id = j;
			}
		}

		if(min_id != i) 	swap(A, i, min_id);
	}

}

void swap(Card *A, int x, int y){
	Card temp = A[x];
	A[x] =  A[y];
	A[y] = temp;
}

void isStable(Card *A, Card* B, int n){
	int i = 0;
	while(i < n){
		if(A[i].suit != B[i].suit){
			printf("Not stable\n");
			return;
		}
		i++;
	}

	printf("Stable\n");
}

void print(Card *A, int n){
	int i = 0;
	while(i < n){
		if(i > 0)  printf(" ");
		printf("%c%d", A[i].suit, A[i].value);
		i++;
	}
	putchar('\n');
}


Measured memory_bytes: 1984
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    int k,n;
    cin>>k>>n;
    vector<int> a(n+1);
    for(int i=0; i<n; i++) cin>>a[i];
    a[n]=a[0];
    int sa=1e9;
    for(int i=1; i<n; i++){
        sa=min(sa,k-abs(a[i]-a[i-1]));
    }
    sa=min(sa,a[n-1]-a[0]);
    cout<<sa<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

vector<set<string>> s(11);

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

    ll N;
    cin >> N;

    s[1].insert("a");

    for (int i = 2; i <= N; i++) {
        // cout << i << endl;
        for (string b : s[i-1]) {
            // cout << "b:" << b << "\n";
            set<char> cnt;
            for (char c : b) {
                cnt.insert(c);
            }
            Rep (j, cnt.size() + 1) {
                string c = b;
                c += 'a' + j;
                s[i].insert(c);
            }
        }
    }

    set<string> ans;

    for (auto e : s[N]) {
        cout << e << "\n";
    }


}

Measured memory_bytes: 17024
n=int(input())
h=list(map(int,input().split()))
dp=[float("inf")]*100010
dp[0]=0

for i in range(1,n):
    dp[i]=min(dp[i],dp[i-1]+abs(h[i]-h[i-1]))
    if i > 1:
        dp[i]=min(dp[i],dp[i-2]+abs(h[i]-h[i-2]))

print(dp[n-1])



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

#if DEBUG
template <typename T>
void debug(const T& value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                        \
  do {                                  \
    cerr << #__VA_ARGS__ << ": ";       \
    debug(__VA_ARGS__);                 \
    cerr << " (L" << __LINE__ << ")\n"; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define rd(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << '\n';
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define wt(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

using namespace std;

class RollingHash {
 public:
  void Add(char c) {
    const unsigned long long base = 100000007;
    hash_ = hash_ * base + c;
  }
  unsigned long long hash() const { return hash_; }
  bool operator==(const RollingHash &h) const { return hash_ == h.hash_; }

 private:
  unsigned long long hash_ = 0;
};

namespace std {
template <>
class hash<RollingHash> {
 public:
  size_t operator()(const RollingHash &h) const {
    return hash<unsigned long long>()(h.hash());
  }
};
}  // namespace std

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  rd(int, n);

  V<string> s(n);
  rep(i, n) {
    cin >> s[i];
    reverse(all(s[i]));
  }
  sort(all(s),
       [](const string &a, const string &b) { return a.size() > b.size(); });

  ll ans = 0;
  unordered_map<RollingHash, array<int, 26>> m;
  for (const auto &si : s) {
    vector<bitset<26>> cum(si.size() + 1);
    for (int i = si.size() - 1; i >= 0; --i) {
      cum[i] = cum[i + 1];
      cum[i].set(si[i] - 'a');
    }
    RollingHash h;
    rep(i, si.size() - 1) {
      rep(j, 26) {
        if (cum[i][j]) {
          m[h][j]++;
        }
      }
      h.Add(si[i]);
    }
    ans += m[h][si.back() - 'a'];
  }
  wt(ans);
}


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

namespace ABC082_D
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();
            string s2 = string.Concat(s.OrderBy(a => a));
            string t2 = string.Concat(t.OrderByDescending(a => a));
            if(string.Compare(s2,t2) < 0)
            {
                Console.WriteLine("Yes");
                return;
            }
            else
            {
                Console.WriteLine("No");
                return;
            }
        }
    }
}


Measured memory_bytes: 13536
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  string a, b, c; cin >> a >> b >> c;
  int ans = 0;
  REP(i, n) {
    set<char> st;
    st.insert(a[i]);
    st.insert(b[i]);
    st.insert(c[i]);
    if (st.size() == 3) ans += 2;
    else if (st.size() == 2) ++ans;
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if x == y:
            return
        else:
            if self.rnk[x] > self.rnk[y]:
                x, y = y, x
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Size(self, x):
        return -self.root[self.Find_Root(x)]

n,m=map(int,input().split())
l=list(reversed([list(map(int,input().split())) for _ in [0]*m]))
uf=UnionFind(n)
ans=[0]*m
ans[0]=n*(n-1)//2
for i in range(m-1):
    if uf.isSameGroup(l[i][0],l[i][1]):
        ans[i+1]=ans[i]
    else:
        ans[i+1]=ans[i]-uf.Size(l[i][0])*uf.Size(l[i][1])
        uf.Unite(l[i][0],l[i][1])
for i in range(m):
    print(ans[~i])

Measured memory_bytes: 34180
import sys
input = sys.stdin.readline


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    N, M = map(int, input().split())
    A = []
    B = []
    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    
    T = UnionFind(N)
    ans = [0]*M
    ans[M-1] = N*(N-1)//2
    for i in reversed(range(M-1)):
        a = A[i+1]
        b = B[i+1]
        if T.isSameGroup(a, b):
            ans[i] = ans[i+1]
        else:
            ans[i] = ans[i+1] - T.Count(a) * T.Count(b)
        T.Unite(a, b)

    for i in range(M):
        print(ans[i])


if __name__ == '__main__':
    main()

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

int dfs(vector<int> graph[], int vertex, int N);
// template<class T>
void printvector(vector<int> &toprint)
{   
    for(int i = 0; i < toprint.size(); i++) cout << toprint[i] << " ";
    cout << endl;
}
// USING ADJENCY LIST TO STORE vertices 
int N, M; // Vertices, Edges
map<int, int>m;
int main()
{
    cin >> N >> M;
    vector<int>graph[N+1];
    int x1, y1;
    for(int i = 1; i <= M; i++)
    {
        cin >> x1 >> y1;
        graph[x1].push_back(y1);
    }
    // cout << endl;
    
    // for(int v = 1; v <= N; v++)
    // {
    //     printvector(graph[v]);
    // }
    int finalmax = INT_MIN;
    for(int i = 1; i <= N; i++)
    {
        if(m.find(i) != m.end())
        {
            finalmax = max(finalmax, m[i]);
        }
        else
        {
            finalmax = max(finalmax, dfs(graph, i, N));
        }
    }

    cout << finalmax << endl;

    return 0;

}

int dfs(vector<int> graph[], int vertex, int N)
{
    if(m.find(vertex) != m.end())
    {
        return m[vertex];
    }
    if (graph[vertex].size() == 0)
    {
        return 0;
    }
    int maximum = INT_MIN;
    for(auto v : graph[vertex])
    {
        maximum = max(maximum , 1 + dfs(graph, v, N));
    }
    m[vertex] = maximum; 

    return maximum;
}

Measured memory_bytes: 14464
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct UnionFind {
    vector<int> id;
    vector<vector<int> > groups;
    int gn; //number of groups
    UnionFind(int n){
        id = vector<int>(n);
        groups = vector<vector<int> >(n);
        gn = n;
        for(int i=0;i<n;++i){
            id[i]=i;
            groups[i]={i};
        }
    }
    void unite(int a, int b) {
        if(same(a,b)) return;
        gn--;
        int x = id[a];
        int y = id[b];
        if(groups[x].size()<groups[y].size()) swap(x,y);
        for(int j : groups[y]){
            id[j] = x;
            groups[x].push_back(j);
        }
        groups[y].clear();        
    }
    bool same(int a, int b) {
        return id[a] == id[b];
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vvll nei(n);
    vector<pair<ll,ll> >  p(n-1);
    REP(i,n-1){
        ll a,b;
        cin >> a >> b;
        a--;
        b--;
        nei[a].pb(b);
        nei[b].pb(a);
        p[i] = make_pair(a,b);
    }
    vll par(n,0);
    par[0]=-1;
    vll dep(n,INF);
    dep[0]=0;
    stack<ll> st;
    st.push(0);
    while(!st.empty()){
        ll now = st.top();
        st.pop();
        for(ll i : nei[now]){
            if(i!=par[now]){
                dep[i]=dep[now]+1;
                par[i]=now;
                st.push(i);
            }
        }
    }
    ll ca,cb;
    ll x = n-1;
    while(true){
        ll now = par[x];
        if(dep[now]==(dep[n-1]/2)){
            ca = x;
            cb = now;
            break;
        }
        x = now;
    }
    UnionFind uf(n);
    REP(i,n-1){
        if((p[i].fi==ca&&p[i].se==cb)||(p[i].fi==cb&&p[i].se==ca)){
            continue;
        }
        uf.unite(p[i].fi,p[i].se);
    }
    int bl = (int)uf.groups[uf.id[0]].size();
    int wh = (int)uf.groups[uf.id[n-1]].size();
    if(bl>wh){
        cout << "Fennec" << endl;
    }else{
        cout << "Snuke" << endl;
    }
    return 0;
}

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

def median(num):
    row=[0]*N
    for i in range(N):
        if A[i]>num:
            row[i]=1
        else:
            row[i]=-1
    m=0
    data=[0]
    for i in range(0,N):
        data.append(data[-1]+row[i])
        m=min(m,data[i+1])
    data=[data[i]-m+1 for i in range(N+1)]
    ans=0
    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**9
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)

Measured memory_bytes: 121432
[N,M]=list(map(int, input().split()))
hlist=list(map(int, input().split()))
ablist=[list(map(int, input().split())) for m in range(M)]
mylist=[1 for n in range(1,N+1)]
for abpair in ablist:
    if hlist[abpair[0]-1]>hlist[abpair[1]-1]:
        mylist[abpair[1]-1]=0
    elif hlist[abpair[0]-1]==hlist[abpair[1]-1]:
        mylist[abpair[1]-1]=0
        mylist[abpair[0]-1]=0
    else:
        mylist[abpair[0]-1]=0
print(mylist.count(1))


Measured memory_bytes: 31968
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <math.h>
using namespace std;

double total = 0;
int sum = 0;
std::vector<std::pair<int, int> > p;
void ret(const int N, const int now, std::set<int> count, double d) {
    for (int i = 0; i < N; i ++) {
        if (count.find(i) == count.end()) {
            double a = sqrt(pow((p[now].first - p[i].first), 2) + pow((p[now].second - p[i].second), 2));
            std::set<int> c = count;
            c.insert(i);
            ret(N, i, c, d + a);
        }
    }
    if (count.size() == N) {
        sum += 1;
        total += d;
    }
}

int main() {
    int N;
    cin >> N;
    int a,b;
    for (int i = 0; i < N; ++i) {
        cin >> a >> b;
        p.push_back(std::pair<int, int>(a, b));
    }

    for (int i = 0; i < N; ++i) {
        double d = 0;
        std::set<int> count;
        count.insert(i);
        ret(N, i, count, d);
    }

    printf("%.10lf\n", total / sum);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i, s, e) for (int i = s; i < e; i++)
#define endl '\n'
int main()
{
    string S, T;
    cin >> S >> T;
    string res = "Yes";
    if (S.size() != T.size() - 1)
        res = "No";
    rep(i, 0, S.size())
    {
        if (S[i] != T[i])
            res = "No";
    }
    cout << res << endl;
}

Measured memory_bytes: 3632
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
//#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 900000;
const int K = 60;
const int mod = 1e9 + 7;
map < int, int > mp;
int a[N], cnt[N];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    set < int > s;
    for (int i = 0; i < (1 << n); i++){
        cin >> a[i];
        s.insert(-a[i]);
    }
    int c = 0;
    for (auto i: s){
        mp[-i] = c;
        c++;
    }
    for (int i = 0; i < (1 << n); i++){
        a[i] = mp[a[i]];
        cnt[a[i]]++;
    }
    multiset < int > q;
    if (cnt[0] != 1){
        cout << "No";
        return 0;
    }
    q.insert(-n);
    for (int i = 1; i < c; i++){
        int x = cnt[i];
        vector < int > b;
        b.clear();
        while(!q.empty() && x > 0){
            int y = -(*q.begin());
            q.erase(q.begin());
            if (y > 1) b.pb(y - 1);
            x--;
            y--;
            if (y != 0) q.insert(-y);
        }
        if (x != 0 && q.size() == 0){
            cout << "No";
            return 0;
        }
        for (auto j: b) q.insert(-j);
    }
    cout << "Yes";
}


Measured memory_bytes: 36096
import sys

if __name__ == "__main__":
    X, Y = [int(x) for x in input().split(" ")]
    # i tul
    for i in range(0, X + 1):
        if i * 2 + (X - i) * 4 == Y:
            print("Yes")
            sys.exit(0)
    print("No")


Measured memory_bytes: 9164
n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]
ans = 0
for i in range(n):
    ans1 = 0
    for j in range(n):
        if s[i] == s[j]:
            ans1 += 1
    for k in range(m):
        if s[i] == t[k]:
            ans1 -= 1
    ans = max(ans, ans1)
print(ans)

Measured memory_bytes: 39408
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<14)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> P;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct Edge{
  int to,d;
  Edge(int to, int d):to(to),d(d){}
};

int N,M,C, V;
vector<Edge>G[6001];
string city[6001];
char gs[6001];
short dist[2001][6001];
map<string,int>recity;

void dijkstra(int s){
  rep(i,C+1) fill(dist[i], dist[i]+V, INF);
  dist[C][s] = 0;
  priority_queue<P, vector<P>, greater<P> >q;
  q.push(MP(0, MP(C, s)));

  while(!q.empty()){
    P p = q.top(); q.pop();
    short cap = p.second.first, v = p.second.second, cost = p.first;

    if(dist[cap][v] < cost) continue;
    rep(i, G[v].size()){
      Edge e = G[v][i];
      if(e.d > cap) continue;
      short tar = max(cap-e.d, gs[e.to]*C);
      if(dist[tar][e.to] > dist[cap][v] + e.d){
	dist[tar][e.to] = dist[cap][v] + e.d;
	q.push(MP(dist[tar][e.to], MP(tar, e.to)));
      }
    }
  }
}

int main(){
  while(cin>>N>>M>>C, N||M||C){

    rep(i,3005) G[i].clear();
    memset(gs, 0, sizeof gs);
    recity.clear();
    C *= 10;
    V = 0;
    string src, dest;
    cin >> src >> dest;

    rep(i,N){
      string s1, s2; short d,u,v;
      cin >> s1 >> s2 >> d;
      if(recity.find(s1) == recity.end()){ recity[s1] = V; city[V++] = s1;}
      if(recity.find(s2) == recity.end()){ recity[s2] = V; city[V++] = s2;}
      u = recity[s1];
      v = recity[s2];
      G[u].push_back(Edge(v,d));
      G[v].push_back(Edge(u,d));
    }

    rep(i,M){
      string s;  cin >> s;
      gs[recity[s]] = 1;
    }

    dijkstra(recity[src]);

    short res = INF;
    rep(i, C+1) res = min(res, dist[i][recity[dest]]);
    cout <<(res==INF?-1:res)  << endl;
  }
  return 0;
}

Measured memory_bytes: 51772
#include <iostream>

using namespace std;

int main() {
	int K, X;
	cin >> K >> X;

	cout << (X - (K - 1));
	for(int d = -(K - 2); d <= (K - 1); d++) {
		const auto x = X + d;
		cout << " " << x;
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define MAX(a,b) a=a>b?a:b
#define MIN(a,b) a=a<b?a:b
#define REP(i,x,n) for(int i=x;i<n;i++)
#define REPR(i,x,n) for(int i=n-1;i>=x;i--)
#define pb  push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLr(obj) (obj).rbegin(), (obj).rend()
#define endl "\n"
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;

ll dp[2][21010]={};

int main(){
    ll sum=0,n,m,a[101010];
    cin>>n>>m;rep(i,n){
        cin>>a[i];sum+=a[i];
    }
    ll aa=0;
    rep(i,n){
        if(a[i]>=((double)sum/4/m))aa++;
    }
    if(aa>=m){
        cout<<"Yes";
    }else{
        cout<<"No";
    }cout<<endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long lli;
const int maxn = 5e5 + 50;
typedef pair<int, int> P;

int arr[maxn];
int a, b, c, d, e, f, g;
void solve();
int main()
{
	int t = 1;
//	cin >> t;
	for(int i=0; i<t; i++)
	{
		solve();
	}
	return 0;
}

// type below

void solve()
{
	cin >> a;
	lli ans = 0;
	for(lli i=1; i<=a; i++)
		if(i % 3 && i % 5) ans += i;
	cout << ans << '\n';
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <queue>

using namespace std;



int main(){
  int n,k;
  cin >> n >> k;
  int i;
  int a[n];
  int count = 0;
  for(i=0;i<n;i++){
    cin >> a[i];
    if(a[i]>=k) count++;
  }
  cout << count << endl;
}

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

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

        for(i = 0; i < 100; i++) {
            if (find(p.begin(), p.end(), x-i) == p.end()) {
                cout << x-i << endl;
                break;
            }
            if (find(p.begin(), p.end(), x+i) == p.end()) {
                cout << x+i << endl;
                break;
            }
        }
}


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

int main()
{
    string s;
    cin >> s;
    if(s[2] == s[3]){
        if(s[4] == s[5]){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const double Pi=acos(-1);
double a,b,x;
int main()
{
	scanf("%lf%lf%lf",&a,&b,&x);
	x/=a;
	if(x<=a*b/2)
	{
		double ans=atan(b*b/2/x)/Pi*180;
		printf("%.8lf",ans);
		return 0;
	}
	else
	{
		double ans=atan(2*(a*b-x)/a/a)/Pi*180;
		printf("%.8lf",ans);
	}
	return 0;
}

Measured memory_bytes: 256
using System;

class Greatest_Common_Divisor {
	public static void Main() {

		string a = Console.ReadLine();
		string[] input = a.Split();
		int r;

		int n = int.Parse(input[0]);
		int m = int.Parse(input[1]);

		while(m != 0) {
		r = n % m;
		n = m;
		m = r;	
		}
		Console.WriteLine(n);
	}
}

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

char s[100010];
int n, a[100010];

int main(){
	scanf("%d%s", &n, s);
	for(int i = 0; i < 4; i++){
		a[0] = i & 1;
		a[1] = (i >> 1) & 1;
		for(int j = 2; j < n; j++){
			int c = (s[j - 1] == 'x');
            c ^= a[j - 1];
            a[j] = c ^ a[j - 2];
		}
		if(a[1] ^ a[n - 1] ^ (s[0] == 'x') ^ a[0]) continue;
		if(a[0] ^ a[n - 2] ^ (s[n - 1] == 'x') ^ a[n - 1]) continue;
		for(int j = 0; j < n; j++) putchar(a[j] ? 'W' : 'S');
		puts("");
		return 0;
	}
	puts("-1");
	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int n, k; cin >> n >> k;
    string s; cin >> s;

    vector<ll> num;

    //ランレングス圧縮
    int now = 1;
    int cnt = 0;
    for(int i= 0; i<n; i++){
        if(s[i] == (char)(now + '0')) cnt++;
        else{
            num.push_back(cnt);
            cnt = 1;
            now ^= 1;
        }
    }

    if(cnt != 0) num.push_back(cnt);
    if(num.size() %2 == 0) num.push_back(0);

    vector<ll> sum(num.size() + 1);
    rep(i,num.size()) sum[i+1] = sum[i] + num[i];

    ll K = 2*k + 1;
    ll ans = 0;
    if(K > sum.size()){
        cout << n << endl;
        return 0;
    }
    for(int i = 0; i+K < sum.size(); i+=2){
        ans = max(ans,ll(sum[i+K] - sum[i]));
    }

    cout << ans << endl;

}

Measured memory_bytes: 2164