akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define SORTG(v) sort(v.begin(),v.end(),greater<>())
#define SORT(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/3

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<string> Vs;

template<class T> void chmax(T& a, T b) {if(a<b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a>b){a=b;}}
void YesNo(int a){cout<<((a)?"Yes":"No")<<endl;}
void YESNO(int a){cout<<((a)?"YES":"NO")<<endl;}
void AorB(int a,string b,string c){cout<<((a)?b:c)<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void start(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}

signed main(){start();
    int n,maxw;
    cin>>n>>maxw;
    Vi w(n),v(n);
    REP(i,0,n) cin>>w[i]>>v[i];

    const int nmax=100,wmax=100000;
    VVi dp(nmax+1,Vi(wmax+1,0));
    REP(i,0,n){
        REP(j,0,maxw+1){
            chmax(dp[i+1][j],dp[i][j]);
            if(j+w[i]<=wmax) chmax(dp[i+1][j+w[i]],dp[i][j]+v[i]);
        }
    }
    cout << dp[n][maxw] << endl;
    return 0;
}


Measured memory_bytes: 80256
#!/usr/bin/env python3
import sys


def solve(N: int, H: "List[int]"):

    result = 0
    count = 0
    for i in range(N - 1):
        if H[i] >= H[i + 1]:
            count += 1
        else:
            result = max(result, count)
            count = 0
    result = max(result, count)
    print(result)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    H = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, H)


if __name__ == "__main__":
    main()


Measured memory_bytes: 15288
// Etavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define file(s) freopen(s".in" ,"r",stdin),freopen(s".out","w",stdout)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
	register char ch;int f=1;
	while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
	register int x=ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return f*x;
}

const int mod = 1e9+7;
enum{N=200023};

il ll qpow(ll a,ll b){
	ll ans= 1;
	for(; b; b>>=1,a=a*a%mod) if( b&1 ){
		ans= ans*a%mod;
	} return ans;
}
il ll inv(ll x){ return qpow(x,mod-2); }

ll fac[N],Invf[N];
il void init_fac(int n){
	n= min(n,mod-1);
	fac[0]= 1;
	rep(i,1,n) fac[i]=fac[i-1]*i%mod;
	Invf[n]= inv(fac[n]);
	rev_rep(i,n,1) Invf[i-1]=Invf[i]*i%mod;
}
il ll comp(ll n,ll m){
	if( n<m ) return 0;
	return fac[n]*Invf[m]%mod*Invf[n-m]%mod;
}

int main(){
	int n=ci(), k=ci();
	init_fac(n);
	ll ans = 0;
	k = min(k,n-1);
	rep(i,1,k){
		ans = (ans+comp(n,i)*comp(n-1,n-i-1))%mod;
	}
	printf("%lld\n",(ans+1+mod)%mod);
	return 0;
}


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

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(&mut i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: &mut R, o: &mut W) {
    let mut i = AtRead::from(i);
    let (n, m) = i.read2::<usize, usize>();
    writeln!(o, "{}", solve(n, m)).unwrap();
}
fn solve(n: usize, m: usize) -> usize {
    match (n, m) {
        (1, 1) => 1,
        (1, x) | (x, 1) => x - 2,
        (n, m) => (n - 2) * (m - 2),
    }
}

struct AtRead<'a, R: BufRead + 'a> {
    r: &'a mut R,
    s: String,
}

macro_rules! fn_read {
        {$f:ident($($v:ident: $t:ident),*)} => {
            fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.next().split(' ');
                $(
                    let $v = next(i);
                )*
                ($($v),*)
            }
        };
    }

impl<'a, R: BufRead + 'a> AtRead<'a, R> {
    fn from(r: &'a mut R) -> Self {
        AtRead {
            r: r,
            s: String::new(),
        }
    }
    fn next(&mut self) -> &str {
        self.s.clear();
        self.r.read_line(&mut self.s).unwrap();
        self.s.trim()
    }

    fn_read! { read2(v1: T1, v2: T2) }
}

fn next<'a, T: FromStr, I: std::iter::Iterator<Item = &'a str>>(i: &mut I) -> T {
    i.next().unwrap().parse().ok().unwrap()
}


Measured memory_bytes: 4352
N, M, X = map(int, input().split())
A = list(map(int, input().split()))
A.append(X)

A.sort()

index = A.index(X)

print(len(A[0:index]) if len(A[0:index]) <= len(A[index+1:len(A)]) else len(A[index+1:len(A)]))


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

int main()
{
	int i,s=0,c=0,n;
	cin>>n;
	int a[n+1];
	for(i=1;i<=n;i++)  cin>>a[i];
	sort(a+1,a+n+1);
	for(i=1;i<=n;i+=2)
	s+=a[i];
	for(i=2;i<=n;i+=2)
	c+=a[i];
	cout<<fabs(s-c)<<endl;
	return 0;  
}

Measured memory_bytes: 384
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N;
	cin >> N;
	VI A(N);
	REP(i, N)cin >> A[i];
	//int z[5010] = { 0 };

	int ans = LLINF;
	eREP(t, A[0]) {
		int z[5010] = { 0 };
		int cost = t;
		z[0] = t;
		FOR(i, 1, N) {
			cost += (A[i - 1] - z[i - 1]) * 2;
			z[i] += A[i - 1] - z[i - 1];
			z[i] = min(A[i], z[i]);
			//cout << cost << " ";
		}
		//cout << endl;
		cost += A[N - 1] - z[N - 1];
		ans = min(ans, cost);
		//eREP(i, N)cout << z[i] << " ";
		//cout << endl;
		//cout << cost << endl;
	}
	cout << ans << endl;



	return 0;
}


Measured memory_bytes: 3256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define out(a) cout << a << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)

int main() {
    int n, k; cin >> n >> k;
    int ans = inf;
    rep(i, (1 << n)) {
        int tmp = 1;
        rep(j, n) {
            if (i & (1 << j)) {
                tmp += k;
            } else tmp *= 2;
        }
        chmin(ans, tmp);
    }
    out(ans);
}


Measured memory_bytes: 256
/*
   Author : BabaYaga42,
   BITS Pilani, Hyderabad.
   Don't give up ;)
   */  
#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define int long long
 
int32_t main()
{
	IOS;	
	int n;
	cin >> n;
	int ans= 0;
	for(int i = 0; i < n; i++)
	{
	 	int x;
	 	cin >> x;
	 	while(x%2 == 0)
	 		x /= 2,ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.Math.*;

class Main{
    
    static int[] mData = new int[100000];
    static int[] dp = new int[100000];

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

        for(int i = 0; i < N; i++){
            mData[i] = sc.nextInt();
        }

        dp[0] = 0;
        dp[1] = Math.abs( mData[0] - mData[1] );

        for(int i = 2; i < N; i++){
            dp[i] = Math.min( dp[i-2] + Math.abs(mData[i] - mData[i-2]), 
                                dp[i-1] + Math.abs(mData[i] - mData[i-1]));
        }


        System.out.println(dp[N-1]);
        sc.close();
    }
}


Measured memory_bytes: 60072
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
typedef pair<ll,int> P;
const int MAX_N=1e5;
const ll MOD=1e9+7,INF=1e18;
struct edge{
	int t;
	ll c;
	edge(int t=-1,ll c=0):t(t),c(c){}
};
int N,M;
vector<edge> G[MAX_N];
ll dist[2][MAX_N],com[2][MAX_N];
int S,T;
void dijkstra(int s){
	int f;
	if (s==S){
		f=0;
	}else{
		f=1;
	}
	fill(dist[f],dist[f]+N,INF);
	dist[f][s]=0;
	priority_queue<P,vector<P> ,greater<P> > pque;
	pque.push(P(0,s));
	while(!pque.empty()){
		P p=pque.top();
		pque.pop();
		int v=p.second;
		if (dist[f][v]<p.first) continue;
		for(auto e:G[v]){
			if (dist[f][e.t]>dist[f][v]+e.c){
				dist[f][e.t]=dist[f][v]+e.c;
				pque.push(P(dist[f][e.t],e.t));
			}
		}
	}
}
void calcom(int s){
	int f;
	if (s==S){
		f=0;
	}else{
		f=1;
	}
	vector<bool> used(N);
	com[f][s]=1;
	priority_queue<P,vector<P> ,greater<P> > pque;
	pque.push(P(0,s));
	while(!pque.empty()){
		P p=pque.top();
		pque.pop();
		int v=p.second;
		if (used[v]) continue;
		used[v]=true;
		for(auto e:G[v]){
			if (dist[f][e.t]==dist[f][v]+e.c){
				com[f][e.t]+=com[f][v];
				com[f][e.t]%=MOD;
				pque.push(P(dist[f][e.t],e.t));
			}
		}
	}
}

int main(){
	cin>>N>>M>>S>>T;
	S--;
	T--;
	REP(i,M){
		int u,v;
		ll d;
		cin>>u>>v>>d;
		u--;
		v--;
		G[u].push_back(edge(v,d));
		G[v].push_back(edge(u,d));
	}
	dijkstra(S);
	calcom(S);
	dijkstra(T);
	calcom(T);
	ll ans=0;
	REP(v,N){
		if (dist[0][v]*2==dist[0][T] && dist[1][v]*2==dist[0][T]){
			ans+=com[0][v]*com[1][v]%MOD*(com[0][T]-com[0][v]*com[1][v]%MOD+MOD)%MOD;
			ans%=MOD;
		}
		for(auto e:G[v]){
			ll d=dist[0][T],c=com[0][T];
			if (dist[0][v]+dist[1][e.t]+e.c==d && dist[0][v]*2<d && d<(dist[0][v]+e.c)*2){
				ans+=com[0][v]*com[1][e.t]%MOD*(c-com[0][v]*com[1][e.t]%MOD+MOD)%MOD;
				ans%=MOD;
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 18792
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
    long long int n,a[10005],i,sum,s,j,flag;
    while(scanf("%lld",&n)==1)
    {
        sum=0,flag=1;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&s);
            flag=0;
            while(s%2==0)
            {
                flag++;
                s=s/2;
            }
            a[i]=flag;
        }
        for(i=0;i<n;i++)
        {
            sum=sum+a[i];
        }
        printf("%lld\n",sum);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace::std;
using ll = long long int;

int main(){
    string s;
    cin >> s;
    for(int i=0; i<(int)s.length()-2; i++){
        if(s[i]==s[i+2] && s[i]!=s[i+1]){
            cout << i+1 << " " << i+3 << "\n";
            return 0;
        }
    }
    for(int i=0; i<(int)s.length()-1; i++){
        if(s[i]==s[i+1]){
            cout << i+1 << " " << i+2 << "\n";
            return 0;
        }
    }
    cout << -1 << " " << -1 << "\n";
}

Measured memory_bytes: 512
#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() {
    int n;
    cin >> n;
    vector<ll> v(n);
    int k = 0;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        if(v[i] < 0) k++, v[i] = -v[i];
    }
    sort(v.begin(),v.end());
    ll ans = k%2 ? -v[0]*2 : 0;
    for (int i = 0; i < n; ++i) {
        ans += v[i];
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int> P;
vector<P> vec;
 
bool check(){
  for(int i = 0 ; i < vec.size() ; i++){
    if(vec[i].first != -1) return true;
  }
 
  vec.clear();
  return false;
}
 
void change(int p, int S, int l){
  vector<P> tmp;
  int Next = vec[p].second - S;
 
  for(int i = 0 ; i < p ; i++){
    tmp.push_back(vec[i]);
  }
 
  tmp.push_back(P(l, S));
  tmp.push_back(P(-1,Next));
 
  for(int i = p+1 ; i < vec.size() ; i++){
    tmp.push_back(vec[i]);
  }
 
  vec = tmp;
}
 
void Wri(){
  int len = vec.size(), l, S;
 
  cin >> l >> S;
 
  if(len == 0 || !check()){
    vec.push_back(P(l,S));
    return;
  }
 
  for(int i = 0 ; i < len ; i++){
    if(vec[i].first == -1){
      if(S - vec[i].second >= 0){
        vec[i].first = l;
        S -= vec[i].second;
      }else{
        change(i, S, l);
        return;
      }
    }
  }
 
  if(S > 0){
    vec.push_back(P(l,S));
  }
}
 
void Del(){
  int len = vec.size(), l;
 
  cin >> l;
  if(len == 0){
    return;
  }
 
  for(int i = 0 ; i < len ; i++){
    if(vec[i].first == l){
      vec[i].first = -1;
    }
  }
}
 
int Ref(){
  long long cnt = 0;
  int len = vec.size(), l, num = vec[0].first;
 
  cin >> l;
  if(len == 0){
    return -1;
  }
 
  for(int i = 0 ; i < len ; i++){
    cnt += vec[i].second;
    num = vec[i].first;
     
    if(cnt > l){
      return num;
    }
  }
 
  if(cnt <= l){
    return -1;
  }else{
    return vec[len-1].first;
  }
}
 
int main(){
  int N;
  char ch;
 
  while(cin >> N, N){
    vec.clear();
    for(int i = 0 ; i < N ; i++){
      cin >> ch;
 
      switch(ch){
      case 'W':
        Wri();
        break;
      case 'D':
        Del();
        break;
      default:
        cout << Ref() << endl;
        break;
      }
    }
 
    cout << endl;
  }
 
  return 0;
}

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

int main(){
	
	string s; cin>>s;
	deque<char> d;
	for(int i=0;i<s.size();i++){
		d.push_back(s[i]);
	}
	int q; cin>>q;
	int cnt=0;
	while(q--){

		int ti,fi;
		char ci;
		cin>>ti;
		if(ti==1){
			cnt++;
		}
		else{
			cin>>fi>>ci;
			if(fi==1){
				if(cnt%2!=0) { d.push_back(ci); }
				else { d.push_front(ci); }
			}
			else{
				if(cnt%2!=0) { d.push_front(ci); }
				else { d.push_back(ci); }
			}	
		}
	}
	if(cnt%2==0) { for(auto x:d) { cout<<x; } }
	else { 
		//deque<char>::iterator it;
		for(auto it=d.rbegin();it!=d.rend();++it) { cout<<*it; } }
		cout<<"\n";
	
	return 0;
} 

Measured memory_bytes: 896
import sys
input = sys.stdin.readline
 
# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

n, u, v = map(int, input().split())
u, v = u-1, v-1
l = [[] for i in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  l[a].append(b)
  l[b].append(a)

def dfs(G, cr, seen, dist):
  seen[cr] = 1
  for i in G[cr]:
    if seen[i] == 0:
      dist[i] = dist[cr] + 1
      dfs(G, i, seen, dist)
  return dist

seen_u = [0]*n
seen_v = [0]*n
dist_u = [0]*n
dist_v = [0]*n

T1 = dfs(l, u, seen_u, dist_u)
T2 = dfs(l, v, seen_v, dist_v)

for i in range(n):
  if dist_u[i] >= dist_v[i]:
    dist_v[i] = -1
    
print(max(dist_v)-1)

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

num = list(range(1, N+1))
num = num[::2]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
ans = []
for n in num:
  ans.append(len(make_divisors(n)))

print(ans.count(8))



Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846
#define __LOCAL

#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int n,m,x;
vector<int> V,W;

int main()
{
    fast_io();
    int A,B;
    cin >> A >> B;
    int sum = 6-A-B;
    cout << sum << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		//List<Integer> amari = new ArrayList<Integer>();
		for(int i=1;;i++) {
			if((a*i)%b==c) {
				System.out.println("YES");
				break;
			}else {
				if((a*i)%b <=0) {
					System.out.println("NO");
					break;
				}

			}
		}
	}

}


Measured memory_bytes: 23636
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cstring>
#include <iomanip>
#include <queue>
#include <deque>
#include <cmath>
using namespace std;
#define inf 280201280201280201
#define mn 100005
#define FLN "test"
#define int long long
typedef pair<int, int> ii;
//constance

//common data structures and templates
template<typename T>
struct SegmentTree{
};
//gb
int n;
bool a[mn];
string s;
//functions here
void input(){
}
void solve(){
}

//#define LOCAL 1

signed main(signed argc, char** argv) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#ifdef LOCAL
	   freopen(FLN".inp", "r", stdin);
	   freopen(FLN".out", "w", stdout);
#endif
  cin >> s;
  n = s.length();
  a[0] = 0;
  int l=1, r = n, ans = 1;
  while(l<= r){
    int mid =  (l+r)>>1;
    for(int i=1; i<= n; ++i) a[i] = s[i-1] -'0';
    for(int i=n; i>=1; --i) a[i] = a[i]^a[i-1];
    for(int i=1; i<= n-mid+1; ++i){
      a[i] ^= a[i-1];
      if(a[i]) a[i]^=1;
    }
    bool check = true;
    for(int i=n-mid+2; i<= n; ++i){
      a[i] ^= a[i-1];
      check &= (a[i]==0 || i-1 >= mid);
    }
    
    if(check){
      ans = mid;
      l = mid+1;
    }
    else r = mid-1;
  }
  cout << ans;
	return 0;
}


Measured memory_bytes: 1208
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n;
    cin >> n;
    vector<ll> a(n);
    set<ll> Set;

    for(ll i=0;i<n;i++){
        cin >> a[i];
        Set.insert(a[i]);
    }

    cout << Set.size() - (n-Set.size())%2 << endl;
    return 0;
}


Measured memory_bytes: 8564
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>
#include <stack>
#include <iterator>
#include <random>
#include <fstream>
#include <chrono>
#include <math.h>
using namespace std;
const int N=1e5+300;
#define int long long
int dp[105][N],a[105],w[105],v[105],mark[N];



int32_t main(){
    int n,k;
    cin >> n >> k;
    for (int i=1 ; i<=n ; i++){
        cin >> w[i] >> v[i];
    }
    int ma=0;
    mark[0]=1;
    for (int i=1 ; i<=k ; i++){
        for (int j=1 ; j<=n ; j++){
            dp[j][i]=dp[j-1][i];
            ma=max(ma,dp[j][i]);
            if (i>=w[j] && mark[i-w[j]]> 0){
                dp[j][i]=max(dp[j][i] , dp[j-1][i-w[j]]+v[j]);
                ma=max(ma,dp[j][i]);
                mark[i]=1;
            }

        }
    }
    cout << ma;
    return 0;
}


Measured memory_bytes: 81408
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e15;

int main() {
  ll n,W;
  ll V=1e5+10;
  cin >> n >> W;
  vec w(n),v(n);
  for(ll i=0;i<n;i++) cin >> w[i] >> v[i];
  vec dp(V+1,inf);
  dp[0]=0;
  for(ll i=0;i<n;i++) {
    for(ll j=V;j>=0;j--) {
      if(j+v[i]<V) {
        dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i]);
      }
    }
  }
  for(ll i=V;i>=0;i--) {
    if(dp[i]<=W) {
      cout << i << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 1024
#include <stdio.h>

#define lln long long int

int main(){
	lln A, B, C, D, E;
	scanf("%lld%lld", &A, &B);
	for(C = 1; ; C <<= 1){
		if(C > B){
			C >>= 1;
			if(C >= A){
				D = B - C;
				break;
			}
			else{
				A -= C;
				B -= C;
				C = 1;
			}
		}
	}
	for(E = 1; ; E <<= 1){
		if(E > D){
			E--;
			break;
		}
	}/*
	printf("C:%lld\n", C);
	printf("D:%lld\n", D);
	printf("E:%lld\n", E);*/
	if(E >= A){
		printf("%lld\n", 2 * C - A);
	}
	else{
		printf("%lld\n", 2 * (C - A) + E + 1);
	}
	return 0;
}

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

using namespace std;

int a, b, c, N;

struct Data {
    int a, b, c;
    Data(int a, int b, int c) : a(a), b(b), c(c) {}
};

int main()
{
    while (cin >> a >> b >> c, a || b || c) {
        cin >> N;
        vector<int> ans(a + b + c, 2);
        vector<Data> data;

        for (int index = 0; index < N; ++index) {
            int i, j, k, r;

            cin >> i >> j >> k >> r;
            i--, j--, k--;
            if (r == 1)
                ans[i] = ans[j] = ans[k] = 1;
            else
                data.push_back(Data(i, j, k));
        }

        for (int i = 0; i < data.size(); ++i) {
            if (ans[data[i].a] == 1 && ans[data[i].b] == 1)
                ans[data[i].c] = 0;
            else if (ans[data[i].a] == 1 && ans[data[i].c] == 1)
                ans[data[i].b] = 0;
            else if (ans[data[i].b] == 1 && ans[data[i].c] == 1)
                ans[data[i].a] = 0;
        }

        for (int i = 0; i < a + b + c; ++i)
            cout << ans[i] << endl;
    }

    return 0;
}

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

using namespace std;
int main()
{
    int k, a, b;
    cin >> k;
    cin >> a >> b;
    bool is = false;
    for (int i = a; i <= b; i++)
    {
        if (i % k == 0)
        {
            cout << "OK"
                 << "\n";
            is = true;
            break;
        }
    }
    if (is == false)
    {
        cout << "NG"
             << "\n";
    }
}

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

int N, A, X[55];
long long dp[55][55][2505];

int main() {
	cin >> N >> A;
	for (int i = 1; i <= N; i++) cin >> X[i];

	dp[0][0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N; j++) {
			for (int k = 0; k <= 2500 - X[i + 1]; k++) {
				dp[i + 1][j][k] += dp[i][j][k];
				dp[i + 1][j + 1][k + X[i + 1]] += dp[i][j][k];
			}
		}
	}

	long long ans = 0;
	for (int i = 1; i <= N; i++) ans += dp[N][i][i * A];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 54528
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
using ll = long long;



int main() {
	string s;
	cin >> s;
	map <char, int> a;
	for (int i = 0; i < s.length(); i++) {
		a[s[i]]++;
	}
	for (int i = 0; i < 26; i++) {
		if (a['a' + i] == 0) {
			char c = 'a' + i;
			cout << c << endl;
			return 0;
		}
	}
	cout << "None" << endl;

	return 0;
}

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

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_p(x) cerr<<#x": "<<x.first<<","<<x.second<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define st first
#define nd second

using namespace std;

// const int N = ;
int n, k;

template<class T>
ostream& operator<<(ostream& out, vector<T> v) {
	out << v.size() << '\n';
	for(auto e : v) out << e << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> p) {
	return out << '(' << p.st << ' ' << p.nd << ')';  
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> k;

	if(k % 2 == 1) {
		int ans = n / k;
		cout << 1LL * ans * ans  * ans << '\n';
		return 0; 
	}

	int ans[5];
	ans[0] = 0;
	ans[1] = 0;

	for(int i = 1; i <= n; i++) {
		if(i % k == 0)
			ans[1]++;
		else if(i % (k / 2) == 0)
			ans[0]++;
	}
	// dbg_v(ans, 3);
	cout << 1LL * ans[0] * ans[0] * ans[0] +  1LL * ans[1] * ans[1] * ans[1]  << '\n';
}	

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long 
#define ld long double
using namespace std;
const int mod = 998244353;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int k, n;
    cin >> k >> n;
    int arr[n + 1];
    vector<int> ans;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    for(int i = 1; i < n; i++){
        ans.push_back(arr[i] - arr[i - 1]);
    }
    ans.push_back(k - arr[n - 1] + arr[0]);
    int sum = 0, mx = 0;
    for(auto v : ans){
        sum += v;
        mx = max(mx, v);
    }
    cout << sum - mx << endl;
    
}

Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
typedef int64_t Int;
typedef pair<Int,Int> P;

const Int Q = 26;

Int D;
vector<Int> C(Q);
vector<vector<Int>> S(400, vector<Int>(Q));

struct ContestInformation{
    vector<set<Int>> held; // held[q] : コンテストqを行った日程の集合
    vector<Int> schedule; // schedule[d]: d日目に実施するコンテストの番号
    Int score = 0; // 最終日の満足度

    ContestInformation(Int D){
        schedule.resize(D);

        held.resize(Q);
        rep(q, Q){
            held[q].insert(-1);
            held[q].insert(D);
        }
    }

    void ReadSchedule(){
        rep(d,D) {
            Int q; cin >> q; q--;
            schedule[d] = q;
            held[q].insert(d);
        }
    }

    // 最終日の満足度を計算する
    void CalcScore(){
        Int ans = 0;

        rep(d,D){
            Int q_now = schedule[d]; // その日に行われるコンテスト

            rep(q, Q){
                if(q == q_now){
                    ans += S[d][q];
                } else {
                    auto last_day_itr = lower_bound(held[q].begin(),held[q].end(),d);
                    ans -= C[q] * (d - *prev(last_day_itr));
                }
            }
            cout << ans << endl;
        }

        score = ans;
    }
};



int main(){
    cin >> D;
    rep(i,Q) cin >> C[i];
    rep(i,D) rep(j,Q) cin >> S[i][j];

    ContestInformation CI(D);
    CI.ReadSchedule();
    CI.CalcScore();
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;

int main()
{
    int x;
    cin >>x;
    if(x<600)cout<<8<<endl;
    else if(x<800)cout<<7<<endl;
    else if(x<1000)cout<<6<<endl;
    else if(x<1200)cout<<5<<endl;
    else if(x<1400)cout<<4<<endl;
    else if(x<1600)cout<<3<<endl;
    else if(x<1800)cout<<2<<endl;
    else cout<<1<<endl;
    return 0;
}


Measured memory_bytes: 3620
#!/usr/bin/env python
# coding: utf-8

# In[8]:


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


# In[11]:


flag = True
for x in S[:A]:
    if x == "-":
        flag = False
        break
if flag:
    for x in S[A+1:]:
        if x == "-":
            flag = False
            break
if flag:
    if S[A] != "-":
        flag = False
if flag:
    print("Yes")
else:
    print("No")


# In[ ]:






Measured memory_bytes: 3060
import collections

n = int(input())
s = []
for i in range(n):
  s.append(input())
count = list(collections.Counter(s).items())
count = sorted(count, key=lambda x: x[1], reverse=True)
result = sorted([i for i in count if i[1] == count[0][1]], key=lambda x:x[0])

for i in result:
  print(i[0])

Measured memory_bytes: 43504
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > > 
#define pq_pair_ts priority_queue <pair<ll,ll> > //第二成分の大きさが関係ない
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll A, B , K;
    cin >> A >> B >> K;
    
    rep(i, (K+1)/2){
        if(A % 2 == 1) A--;
        B+=A/2;
        A/=2;
        
        if((K%2 == 1) && (i == K/2)) break;
            
        if(B % 2 == 1) B--;
        A+=B/2;
        B/=2;
        
        cerr << i << ":" << A << " " << B << endl;
    }
    
    cout << A << " " << B << endl;
    
    
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


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

using namespace std;

int n, k;
int a[100000];
int dp[100000];

int solve(int i)
{
	if (i == n - 1)
		return dp[i] = 0;
	if (dp[i] != -1)
		return dp[i];
	int ans = INT_MAX;
	for (int j = 1; j <= k; j++)
	{
		if (j + i < n)
			ans = min(ans, abs(a[i] - a[i + j]) + solve(i + j));
		else
			break;
	}
	return dp[i] = ans;
}

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	memset(dp, -1, sizeof(dp));
	cout << solve(0) << endl;
	return 0;
}


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


int main(){
    int n;
    cin >> n;
    int ans=0;
    if(n%2==0){
        ans=n/2;
        ans=ans*ans;
    }else{
        ans=n/2;
        ans=ans*(ans+1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#n=int(input())
n,q=map(int,input().split())

s=list(input())
#bl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

count=[0]*n

for i in range(1,n):
    st=s[i-1:i+1]
    if st==["A","C"]:
        count[i]=count[i-1]+1
    else:
        count[i]=count[i-1]

for i in range(q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])


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

using namespace std;

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

    if(s[k - 1] == 'A')
        s[k - 1] = 'a';
    if(s[k - 1] == 'B')
        s[k - 1] = 'b';
    if(s[k - 1] == 'C')
        s[k - 1] = 'c';

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

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1000;

int A[N][N], a[N][N];
int equation, variable;
int n, m, manhaton;

int gauss()
{
    int col=1, row=1;
    for(; row<=equation && col<=variable; row++, col++)
    {
        int max_row=row;

        for(int i=row+1; i<=equation; i++)
            if(abs(A[i][col])>abs(A[max_row][col]))
                max_row=i;

        if(A[max_row][col]==0)
        {
            row--;
            continue;
        }

        if(max_row!=row)
        {
            for(int i=col; i<=variable+1; i++)
                swap(A[max_row][i], A[row][i]);
        }

        for(int i=row+1; i<=equation; i++)
        {
            if(i==row) continue;
            if(A[i][col]==0) continue;
            int GCD=__gcd(abs(A[i][col]), abs(A[row][col]));
            int ta=abs(A[row][col]) / GCD;
            int tb=abs(A[i][col])   / GCD;

            if((A[i][col]>0 && A[row][col]<0) || (A[i][col]<0 && A[row][col]>0)) tb=-tb;

            for(int j=col; j<=variable+1; j++)
                A[i][j]=abs((A[i][j]*ta-A[row][j]*tb))%2;
        }
    }

    for(int i=row; i<=equation; i++)
        if(A[i][variable+1]!=0) return -1;

    return 0;
}

void build(int n, int m)
{
    variable=n*m, equation=n*m;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d", &a[i][j]);

    for(int i=1; i<=equation; i++)
        for(int j=1; j<=variable+1; j++)
            A[i][j]=0;

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            int id=i*m+j+1;
            A[id][id]=1;
            for(int x=0; x<n; x++)
                for(int y=0; y<m; y++)
                {
                    if(abs(y-j)+abs(x-i)==manhaton) A[id][x*m+y+1]=1;
                }
            if(a[i][j]==1) A[id][variable+1]=1;
        }
}

int main()
{
    while(scanf("%d%d%d", &m, &n, &manhaton), m!=0 || n!=0 || manhaton!=0)
    {
        build(n, m);
        int ans=gauss();
        if(ans==-1) printf("0\n"); else printf("1\n");
    }
    return 0;
}

Measured memory_bytes: 5568
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define ABS(x) (x>0?x:-(x))

#define INF 1000000000

int array_min_max(int* p, int n,bool f)  //f: true→min false→max
{
	int tmp;

	if (f)
		tmp = INF;
	else
		tmp = 0;

	for (int i = 0; i < n; i++)
	{
		if (f)
		{
			if (p[i] < tmp)
				tmp = p[i];
		}
		else
		{
			if (p[i] > tmp)
				tmp = p[i];
		}
	}
	return tmp;
}

void swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void bubble_sort(int *p, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (p[j] > p[j + 1])
				swap(&p[j], &p[j + 1]);
		}
	}
}

int det(int p[5][5], int n)
{
	int ans = 0;

	int tmp[25] = { 0 };
	int tmp2[5][5];
	int cnt = 0;

	if (n == 2)
		return p[0][0] * p[1][1] - p[0][1] * p[1][0];
	else
	{
		for(int i = 0; i < n; i++)
		{
			cnt = 0;
			for (int k = 0; k <n; k++)
			{
				for (int l = 0; l < n; l++)
				{
					if (k != 0 && l != i)
					{
						tmp[cnt] = p[k][l];
						cnt++;
					}
				}
			}
			cnt = 0;
			for (int k = 0; k < n-1; k++)
			{
				for (int l = 0; l < n-1; l++)
				{
					tmp2[k][l] = tmp[cnt];
					cnt++;
				}
			}
			ans+=p[0][i]*pow(-1,i)*det(tmp2, n - 1);
		}
	}
	return ans;
}

int main()
{
	char s[2];

	scanf("%s", s);

	switch (s[0])
	{
	case 'A':
		printf("T\n");
		break;
	case 'T':
		printf("A\n");
		break;
	case 'C':
		printf("G\n");
		break;
	case 'G':
		printf("C\n");
		break;
	}
}

Measured memory_bytes: 128
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 100000001;
ll t[100010][50];
const ll mod = 1000000007;
void GoodSequence() {
	
	int n;
	cin >> n;
	map<ll, int> m;
	int res = 0;
	for (size_t i = 0; i < n; i++)
	{
		ll v;
		cin >> v;
		if (m.count(v) == 0) {

		}
		m[v]++;
		if (m[v] < v) res++;
		if (m[v] > v) res++;
		if (m[v] == v) res -= v - 1;
	}
	cout << res << endl;

}

int main() {
	GoodSequence();

	return 0;
}



Measured memory_bytes: 6272
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
const int max_n = 6001;

int s_n, m; int c;
map<string, int> mp;
int n = 2;
int to_id(const string &s) {
	if (mp[s])return mp[s];
	else {
		n++; mp[s] = n; return n;
	}
}
struct edge {
	int to, cost;
};
vector<edge> G[max_n];
vector<edge> trueG[max_n];
int d[max_n];
void init(int s) {
	rep1(i, n) {
		d[i] = mod;
	}
	d[s] = 0;
}
bool needed[max_n];

priority_queue<P,vector<P>,greater<P>> q;
void dijkstra(int sta) {
	init(sta);
	q.push({ 0,sta });
	while (!q.empty()) {
		P p = q.top(); q.pop();
		int v = p.second;
		rep(j, G[v].size()) {
			int to = G[v][j].to;
			if (p.first + G[v][j].cost < d[to]) {
				d[to] = p.first + G[v][j].cost;
				q.push({ d[to],to });
			}
		}
	}
	rep1(i, n) {
		if (i == sta)continue;
		if (!needed[i])continue;
		if (d[i] <= 10 * c) {
			trueG[sta].push_back({ i,d[i] });
		}
	}
}
void all_init() {
	rep1(i, n) {
		G[i].clear();
		trueG[i].clear();
		needed[i] = false;
	}
	mp.clear();
	n = 2;
}
int main() {
	while (cin >> m >> s_n >> c,m) {
		all_init();
		string in1, in2;
		cin >> in1 >> in2;
		mp[in1] = 1; mp[in2] = 2;
		rep(i, m) {
			int z;
			cin >> in1 >> in2 >> z;
			int i1 = to_id(in1), i2 = to_id(in2);
			G[i1].push_back({ i2,z });
			G[i2].push_back({ i1,z });
		}
		needed[1] = needed[2] = true;
		rep(i, s_n) {
			cin >> in1;
			needed[to_id(in1)] = true;
		}
		rep1(i, n)if (needed[i])dijkstra(i);
		init(1);
		q.push({ 0,1 });
		while (!q.empty()) {
			P p = q.top(); q.pop();
			int v = p.second;
			rep(j, trueG[v].size()) {
				int to = trueG[v][j].to;
				int cost = p.first + trueG[v][j].cost;
				if (cost < d[to]) {
					d[to] = cost;
					q.push({ d[to],to });
				}
			}
		}
		if (d[2] == mod)cout << -1 << endl;
		else cout << d[2] << endl;
	}
	return 0;
}



Measured memory_bytes: 6284
#include <stdio.h>

void judge_righttriangle(int a, int b, int c);

int main(void)
{
  int n, a, b, c;

  scanf("%d",&n);
  while(n-- > 0)
  {
    scanf("%d %d %d", &a, &b, &c);
	judge_righttriangle(a,b,c);
  }

  return 0; 		
}

void judge_righttriangle(int a, int b, int c)
{
  int tmp;

  //sort as a<b<c
  if(b > c){tmp=b; b=c; c=tmp;}
  if(a > b){tmp=a; a=b; b=tmp;}
  if(b > c){tmp=b; b=c; c=tmp;}

  if(c*c==a*a+b*b) printf("YES\n");
  else             printf("NO\n");
}

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

int main(){
    int a,b,c,d,e,k;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    cin >> e;
    cin >> k;

    if(e - a <= k)
        cout << "Yay!" << endl;
    else
        cout << ":(" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long n,k,l,ans,s;
    cin>>n>>k;

    s=n%k;
     l=abs(s-k);
    ans=l;
    while(1)
    {
      l=abs(l-k)  ;
      if(l>=ans)
      {
          break;
      }
      else
      {
          ans=l;
      }

    }
    cout<<ans<<endl;

}


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

namespace AtCoder_solve
{
    class Program
    {
        public const ulong mod = 1000000007;

        static void Main(string[] args)
        {
            var xy = Console.ReadLine().Split().Select(long.Parse).ToArray();
            for (int i = 0; i < 250; i++)
            {
                xy[2] -= xy[1];
                if (xy[2] <= 0)
                {
                    Console.WriteLine("Yes");
                    break;
                }

                xy[0] -= xy[3];
               // Console.WriteLine(xy[0]);
                if (xy[0] <= 0)
                {
                    Console.WriteLine("No");
                    break;
                }
            
            }

        }






    





        static public long Input()
        {
            return long.Parse(Console.ReadLine());
        }

        static public string[] Input2()
        {
            return Console.ReadLine().Split();
        }
        
        static public long[] Input3()
        {
            string[] data = Console.ReadLine().Split();
            long[] res = new long[data.LongLength];
            for(long i = 0; i < data.LongLength; i++)
            {
                res[i] = long.Parse(data[i]);
            }
            return res;
        }
        public static long Choose(long n, long a)
        {
            long x = 1;
            long y = 1;
            for (long i = 0; i < a; i++)
            {
                x *= n - i;
                y *= i + 1;
            }
            return x / y;
        }

        public static long Gcd(long a, long b)
        {
            long x = Math.Max(a, b);
            long y = Math.Min(a, b);
            if (x % y == 0) return y;
            else return Gcd(y, x % y);
        }
    }
}


Measured memory_bytes: 28232
x,y,a,b,c = list(map(int,input().split()))
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))

#for i in range(c):
#    maze[a + b + i] = ["n",r[i]]

#maze.sort(reverse=True,key = lambda x:x[1])
r.sort(reverse=True)
p.sort(reverse=True)
q.sort(reverse=True)
maze = p[:x] + q[:y]
ans = sum(maze)
dpc = [0]*(c+1)
dpa = [0]*(a+b+1)
maze.sort()
for i in range(c):
    dpc[i+1] = dpc[i] + r[i] 
for i in range(x+y):
    dpa[i+1] = dpa[i]+maze[i]
maxans = ans
for i in range(min(x+y,c)):
    ans = max(ans,maxans - dpa[i+1] + dpc[i+1])
print(ans)

Measured memory_bytes: 107108
#include <iostream>
#include <algorithm>

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

using namespace std;

int main()
{
    int N,K,p[1010];
    cin>>N>>K;
    rep(i,N){
        cin>>p[i];
    }

    sort(p,p+N);

    int ans=0;
    rep(i,K){
        ans+=p[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

int main(){
    int n, m, i, c, s;
    cin >> n >> m;
    int a[n] = {};
    for(i=0; i<n; i++){
        a[i] = -1;
    }
    for(i=0; i<m; i++){
        cin >> s >> c;
        if(a[s-1] != -1 && a[s-1] != c){
            cout << -1;
            return 0;
        }else if(n > 1 && s == 1 && c == 0){
            cout << -1;
            return 0;
        }else{
            a[s-1] = c;
        }
    }
    for(i=0; i<n; i++){
        if(a[i] == -1 && i == 0 && n > 1){
            cout << 1;
        }else if(a[i] == -1){
            cout << 0;
        }else{
            cout << a[i];
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int x = 0;
		int ans = 0;
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		String S = scan.next();
		String[] str = S.split("");
		for(int i = 0; i < N; i++) {
			if(str[i].equals("I")) x++;
			else x--;
			if(ans < x) ans = x;
	    }
		System.out.println(ans);
		scan.close();
	}

}


Measured memory_bytes: 21844
#include <stdio.h>

int main(void)
{
    int N;
    int a, b, c;
    int i;
    scanf("%d", &N);
    for (i = 0; i < N; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        if (a * a + b * b == c * c) {
            printf("YES\n");
        } else if (b * b + c * c == a * a) {
            printf("YES\n");
        } else if (c * c + a * a == b * b) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

Measured memory_bytes: 1008
import java.util.Scanner;

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


		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();
		int rank = 0;

		if (x >= 400 && x <= 599){
			rank = 8;
		} else if (x >= 600 && x <= 799){
			rank = 7;
		} else if (x >= 800 && x <= 999){
			rank = 6;
		} else if (x >= 1000 && x <= 1199){
			rank = 5;
		} else if (x >= 1200 && x <= 1399){
			rank = 4;
		} else if (x >= 1400 && x <= 1599){
			rank = 3;
		} else if (x >= 1600 && x <= 1799){
			rank = 2;
		} else if (x >= 1800 && x <= 1999){
			rank = 1;
		}
		System.out.println(rank);
	}


}

Measured memory_bytes: 35676
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(int i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;

int main(void){
  int n;
  double t, a;
  cin >> n >> t >> a;
  int ans;
  double d = INF;
  REP(i, n){
    double h;
    cin >> h;
    double b = t - h * 0.006;
    double c = fabs(b-a);
    if(c < d){
      ans = i+1;
      d = c;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    int a, b, x;
    cin >> a >> b >> x;

    if(a > x){
        cout << "NO" << endl;
    }else if(a+b < x){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
}

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

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

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

int N;
vi g[110];

int deg[110];
int mx;

void calc(int v, int p, int d) {
	mx = max(mx, d);

	int md = 0;

	for (int to : g[v]) if (to != p) {
		++md;
		calc(to, v, d + 1);
	}
	deg[d] = max(deg[d], md);
}

int main() {
	cin >> N;

	vector<pii> es;

	rep(i, N-1) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].pb(b); g[b].pb(a);
		es.eb(a, b);
	}

	int col = 1e5;
	ll num = LLONG_MAX;

	rep(i, N) { //node
		rep(j, 110) deg[j] = 0;

		ll t = 1;
		mx = -1;
		calc(i, -1, 1);

		rep(j, 110) if (deg[j]) {
			t *= deg[j];
		}

		if (col > mx) {
			col = mx;
			num = t;
		} else if (col == mx) {
			num = min(num, t);
		}
	}

	for (auto e : es) {
		rep(j, 110) deg[j] = 0;

		mx = -1;
		calc(e.fi, e.se, 1);
		calc(e.se, e.fi, 1);

		ll t = 2;
		rep(j, 110) if (deg[j]) {
			t *= deg[j];
		}

		if (col > mx) {
			col = mx;
			num = t;
		} else if (col == mx) {
			num = min(num, t);
		}
	}

	cout << col << " " << num << endl;

	return 0;
}

Measured memory_bytes: 256