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

int main(void){
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i = 0 ; i<n ; ++i){
    cin >> a.at(i);
  }

  for(int i = 0 ; i<n-k ; ++i){
    if(a.at(i) < a.at(i+k)){
      cout << "Yes" << endl;
    }   
    else{
      cout << "No" << endl;
    }   
  }

  return 0;
}


Measured memory_bytes: 4048
from bisect import bisect_left

S = input()
T = input()
a = 97

grid = [[] for _ in range(26)]
for idx, s in enumerate(S):
    s = ord(s) - a
    grid[s].append(idx)

glen = [0] * 26
for idx, g in enumerate(grid):
    glen[idx] = len(g)

cnt = 0
cur = 0
for t in T:
    t = ord(t) - a
    if glen[t]:
        idx = bisect_left(grid[t], cur)
        if idx == glen[t]:
            cnt += 1
            ncur = grid[t][0] + 1
        else:
            ncur = grid[t][idx] + 1
            cnt = cnt + (ncur <= idx)
        cur = ncur
    else:
        cnt = 0
        cur = -1
        break

print(cur + len(S) * cnt)


Measured memory_bytes: 45808
#![allow(non_snake_case)]
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use whiteread::parse_line;
use std::collections::*;
use num::*;

use itertools::Itertools;
use itertools_num::ItertoolsNum;

#[fastout]
fn main() {
    input!{
        n: usize, m: usize,
        ab_vec: [(usize, usize); m],
    }

    let mut map: BTreeMap<usize, usize> = BTreeMap::new();
    

    for (a, b) in ab_vec.iter() {
        *map.entry(*a).or_insert(0) += 1;
        *map.entry(*b).or_insert(0) += 1;
    }
    
    for i in 1..=n {
        match map.get(&i) {
            Some(x) => println!("{}", x),
            None => println!("0"),
        }
    }
}


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

int main(){
  int N;cin>>N;
  int A[210];for(int i=0;i<N;i++)cin>>A[i];
  int t=1,cnt=0;
while(t==1){
    for(int j=0;j<N;j++){
      if(A[j]%2!=0){
        t=0;
      }else{
        A[j]/=2;
      }
    }
    if(t==1)cnt++;
  }
  cout<<cnt<<endl;
  }



Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int D;
  cin>>D;
  if(D==25)
    cout<<"Christmas";
  if(D==24)
    cout<<"Christmas Eve";
  if(D==23)
    cout<<"Christmas Eve Eve";
  if(D==22)
    cout<<"Christmas Eve Eve Eve";
  return 0;
}

Measured memory_bytes: 256
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug "<< i << std::endl

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll n;
  std::cin>>n;

  std::cout<<n*n*n;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int N,A,B,c;
  cin >> N >> A >> B;
  if(A<=B) cout << A <<endl;
  else cout << B << endl;
  
  c = N-(A+B); 
  if(c>=0) cout << 0 << endl;
  else cout << -c << endl;
}

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

x = a[0]
y = sum(a) - a[0]
score = abs(x-y)
for i in range(1, n-1):
  x += a[i]
  y -= a[i]
  score = min(score, abs(x-y))

print(score)

Measured memory_bytes: 24812
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <cmath>
#include <cstdio>

using namespace std;

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

using ll = long long;
using ull = unsigned long long;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif




void solve() {
    string s;
    cin >> s;
    int n = 700;
    for (auto c: s) {
        if (c == 'o') {
            n += 100;
        }
    }
    cout << n << '\n';
}


int main() {
    solve();
    return 0;
}


Measured memory_bytes: 256
def main():
    cnt = 0
    yes = False
    N = int(input())
    for _ in range(N):
        d1, d2 = list(map(int, input().split()))
        if d1 == d2:
            cnt += 1
        else:
            cnt = 0
        if cnt >= 3:
            yes = True
            break
    if yes:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Measured memory_bytes: 9120
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <time.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef LL ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=5+3*1e+4;
const ut INF=1<<30;
const ld eps=1e-6;
const LL mod=1e+9 + 7;

int N, A[128], B[128];


int main() {
	cin >> N;
	REP(i,N){
		cin >> A[i] >> B[i];
	}
	bool check[128] = {0};
	int ans = 0;
	FFOR(d,1,31){
		int after = 32, wsee = 128;
		bool ok = false;
		REP(j,N){
			if(A[j] <= d && d <= B[j])
				ok = true;
			if(check[j])
				continue;
			if(A[j] <= d && d <= B[j]){
				if(after > B[j]){
					after = B[j];
					wsee = j;
				}
			}
		}
		if(wsee != 128){
			check[wsee] = true;
			ans += 100;
		}
		else{
			if(ok)
				ans += 50;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

vector<pair<ll, ll> > a[111111];
ll ans[111111], visit[111111];

void dfs(ll node, ll dist)
{
    ll i;

    if (visit[node])
		return;

    visit[node] = 1;
    ans[node] = dist % 2;

    for (i = 0; i < a[node].size(); i++)
		dfs(a[node][i].first, dist + a[node][i].second);
}

int main(void)
{
    ll n, i;

    scanf("%lld" ,&n);
    for (i = 1; i < n; i++)
	{
		ll x, y, z;
		scanf("%lld %lld %lld" ,&x, &y, &z);
        a[x].push_back(make_pair(y, z));
        a[y].push_back(make_pair(x, z));
	}

    dfs(1, 0);

    for (i = 1; i <= n; i++)
		printf("%lld\n" ,ans[i]);
	return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>

using namespace std;

vector<int> list;
vector<int> goal;
//vector<int> try_list;
//vector<int> sum;
int min_s;
int N,A,B,C;

int try_take(vector<int> try_list, int ni)
{
	int ans;

	if (ni > N) return -1;

	int sum[4] = { 0 };
	int cnt[4] = { 0 }; 
	for(int ti = 0; ti < try_list.size(); ti++){
		sum[try_list[ti]] += list[ti];
		cnt[try_list[ti]]++;
		//printf("%d,",list[try_list[ti]]);
	}
	//printf("\n");

	if (sum[1] > 0 && sum[2] > 0 && sum[3] > 0){
		ans = abs(sum[1] - goal[1]) + abs(sum[2] - goal[2])  + abs(sum[3] - goal[3]);
		ans += (cnt[1] + cnt[2] + cnt[3] -3) * 10;
		//if (ans > min_s) return -1;
		if (ans < min_s) min_s = ans;
	}

	for (int ti = 0; ti < 4; ti++){
		vector<int> new_try_list = try_list;
		new_try_list.push_back(ti);
		try_take(new_try_list,ni+1);
	}

	return 0;
}


int main()
{
	int l;

	cin >> N >> A >> B >> C;
	goal.push_back(0);
	goal.push_back(A);
	goal.push_back(B);
	goal.push_back(C);

	for (int ni = 0; ni < N; ni++){
		cin >> l;
		list.push_back(l);
	}
	sort(list.begin(),list.end());

	/*
	for(int si = 0; si < 4; si++){
		sum.push_back(0);
	}
	*/

	min_s = 1e9;

	vector<int> try_zero;
	try_take(try_zero,0);

	printf("%d",min_s);


	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n;
bool compatible[24][24];
int dp[2][1<<21];

int main() {
	cin>>n;
	int x, y;
	for(int i = 0 ; i<n;i++)
		for(int j = 0 ;j<n;j++)
			cin>>compatible[i][j];
	memset(dp,0,sizeof(dp));
	dp[1][0] = 1;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			for(int k = 0;k<(1<<n);k++){
				if(!dp[(i+1)%2][k] || (k&(1<<j)))	continue;
				if(compatible[i][j])
					dp[i%2][k|(1<<j)] = (dp[i%2][k|(1<<j)]+dp[(i+1)%2][k])%mod;
			}
		}
	}
	cout<<dp[(n-1)%2][(1<<n)-1];
	return 0;
}

Measured memory_bytes: 16640
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include<iomanip>

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout<<setprecision(10);
  int a,b,c;
  cin>>a>>b>>c;
  if(a+b+1>=c){cout<<b+c<<endl;return 0;}
  else cout<<b+a+b+1<<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;

/*vector<int> p(n);
cin >> p[i]*/

int main(){

    string s;
    cin >> s;

    if(s[0] != s[1] || s[1] != s[2]) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
int a,b,c,d,e,f,i,n;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
b=5*b;
c=10*c;
d=50*d;
e=100*e;
f=500*f;
a=a+b+c+d+e+f;
if(1000<=a){
printf("1\n");
}else{
printf("0\n");
}
return(0);
}


Measured memory_bytes: 2104
const double = Float64
const int = Int64

parseint(x) = parse(int, x)
readint() = map(parseint, split(readline()))

function main()
  X,Y = readint()

  flag = false

  for x in 0:X
    if X*2 + x*2 ==Y
      println("Yes")
      return
    end
  end
  println("No")
end

main()

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


int main() {
    int r,c,n;
    int val1 = 0;
    int total_sum = 0;
    int table[101][101];
    cin >> r >> c;
    
    for (int i=0; i<r; ++i) {
        for (int j=0; j<c; ++j) {
            cin >> n;
            table[i][j] = n;
            val1 += n;
            total_sum += n;
            if (j == c-1) 
                table[i][j+1] = val1;
            if (i == r-1 && j == c-1) 
                table[i+1][j+1] = total_sum;
        }
        val1 = 0;
    }
    
    for (int j=0; j<c; ++j) {
        for (int i=0; i<r; ++i) {
            val1 += table[i][j];
            if (i == r-1) 
                table[i+1][j] = val1;
        }
        val1 = 0;
    }
    
    for (int i=0; i<r+1; ++i) {
        for (int j=0; j<c+1; ++j) {
            cout << table[i][j];
            if (j != c) cout << ' ';
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define INF      (int)1e9
#define MOD      (int)1e9+7
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;

int main(){
	int n;
	cin>>n;
	
	vector<string> s(n);
	REP(i,n){
		cin>>s[i];
		sort(ALL(s[i]));
	}
	
	map<string,int> mp;
	REP(i,n){
		mp[s[i]]++;
	}
	
	llong ans=0;
	for(auto elem:mp){
		llong tmp=elem.second;
		ans+=(tmp*(tmp-1))/2;
	}
	
	cout<<ans<<endl;
}//解答解説参考.

Measured memory_bytes: 18176
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      if(a>0)System.out.println("Positive");
      else if(b>=0)System.out.println("Zero");
      else{
      	if(a==0)System.out.println("Zero");
        else if((b-a+1)%2==0)System.out.println("Positive");
        else System.out.println("Negative");
      }
    }
}

Measured memory_bytes: 22732
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map { it.toLong() }
    val a = readLine()!!.split(' ').map { it.toLong() }

    val k1 = k + 1

    var res = 0L

    for (i in 0..39) {

        if (k1 and (1L shl i) > 0) {
            var x = 0L

            for (j in 0..39) {

                if (j < i) {
                    val c = a.filter { it and (1L shl j) == 0L }.count()
                    if (c > n / 2) {
                        x += 1L shl j
                    }
                    continue
                }

                if (j > i) {
                    x += k1 and (1L shl j)
                    continue
                }

            }

            res = Math.max(res, a.map { it xor x }.sum())
        }

    }

    println(res)
}


Measured memory_bytes: 139048
#include<iostream>
#include<sstream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdlib>
using namespace std;

int main(){
	int k;
	while(scanf("%d",&k)==1,k){
		int sum = 0;
		for(int x=0;x<k*(k-1)/2;++x){
			int j;scanf("%d",&j);
			sum += j;
		}
		cout<<sum/(k-1)<<endl;
	}
	return 0;
}

Measured memory_bytes: 1208
import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False
# cython: cdivision=True
# False:Cython はCの型に対する除算・剰余演算子に関する仕様を、(被演算子間の符号が異なる場合の振る舞いが異なる)Pythonのintの仕様に合わせ、除算する数が0の場合にZeroDivisionErrorを送出します。この処理を行わせると、速度に 35% ぐらいのペナルティが生じます。 True:チェックを行いません。

ctypedef long long LL
from libc.stdio cimport scanf
from libcpp.vector cimport vector as vec

ctypedef vec[vec[LL]] Graph
cdef LL i,j,k,_

cdef LL N,M
scanf('%lld %lld',&N,&M)

cdef Graph graph=Graph(N)

cdef LL a,b

# この問題をあえてグラフの構造を持つことで解く
for _ in range(M):
    scanf('%lld %lld',&a, &b)
    graph[a-1].push_back(b-1)
    graph[b-1].push_back(a-1)

cdef vec[LL] ans
for i in range(N):
    ans.push_back(graph[i].size())

print(*ans, sep='\n')

'''
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode


Measured memory_bytes: 10180
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  int N;
  cin>>N;
  VI A(N);
  rep(i,N) cin>>A[i];
  VL L(N+1),R(N+1);
  rep(i,N) L[i+1]=L[i]+A[i];
  reverse(all(A));
  rep(i,N) R[i+1]=R[i]+A[i];
  ll ans=LLONG_MAX;
  rep(i,N-3){
    int tmp=i+1;
    ll sumL=L[tmp+1];
    ll sumR=R[N-1-tmp];
    ll D,S;
    auto itr=lb(all(L),sumL/2);
    D=max(*itr,sumL-*itr);
    S=min(*itr,sumL-*itr);
    itr--;
    if(abs(*itr-(sumL-*itr))<D-S){
      D=max(*itr,sumL-*itr);
      S=min(*itr,sumL-*itr);
    }
    ll D2,S2;
    itr=lb(all(R),sumR/2);
    D2=max(*itr,sumR-*itr);
    S2=min(*itr,sumR-*itr);
    itr--;
    if(abs(*itr-(sumR-*itr))<D2-S2){
      D2=max(*itr,sumR-*itr);
      S2=min(*itr,sumR-*itr);
    }
    ans=min(ans,max(D,D2)-min(S,S2));
  }
  cout<<ans<<endl;
}


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

int main() {
  string s;
  cin >> s;
  bool ans  = true;
  int cnt = 0;
  if(s.front() != 'A') ans = false;
  else {
    for(int i = 2; i <= s.size()-2; i++){
      if(s.at(i) == 'C')cnt++;
    }
    if(cnt != 1) ans = false;
  }
  cnt = 0 ;
  rep(i,s.size()){
    if(isupper(s.at(i))) cnt++;
  }
  if(cnt != 2) ans = false;
  puts(ans?"AC":"WA");
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,ans=0;
cin>>n;
int a[n],b[n],c[n-1];
for(int i=0;i<n;i++)
  cin>>a[i];
  for(int i=0;i<n;i++)
    {
    cin>>b[i];
    }
    for(int i=0;i<n-1;i++)
      {
      cin>>c[i];
      }

    for(int i=0;i<n;i++)
      {
      ans+=b[a[i]-1];
      if(i>0 && a[i]==a[i-1]+1)
      {
        ans+=c[a[i-1]-1];
      }


      }
      cout<<ans;

}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define yorn(f) puts((f)?"Yes":"No")
ll x;
//ld ;
//string s;

int main() {
  cin >> x;
  ll ans = (x/500)*1000 + ((x%500)/5)*5;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
def ok(board, x, y, dx, dy, w, h)
  0 <= x + dx && x + dx < w && 0 <= y + dy && y + dy < h &&
    case [dx, dy]
      when [-1, 0]
        board[y * 2][x - 1] != '1'
      when [0, 1]
        board[y * 2 + 1][x] != '1'
      when [1, 0]
        board[y * 2][x] != '1'
      when [0, -1]
        board[y * 2 - 1][x] != '1'
    end
end

def solve(board, w, h)
  q = []
  q << [0, 0, 1]
  score = h.times.map{ [w * h] * w }
  score[0][0] = 1
  ans = 0
  until q.empty?
    x, y, n  = q.shift
    if x == w - 1 && y == h - 1
      ans = n
      break
    end
    [[-1, 0], [0, 1], [1, 0], [0, -1]].each do |dx, dy|
      xx = x + dx; yy = y + dy
      if ok(board, x, y, dx, dy, w, h) && score[yy][xx] > n + 1
        score[yy][xx] = n + 1
        q << [xx, yy, n + 1]
      end
    end
  end
  p ans
end

loop do
  w, h = gets.split.map(&:to_i)
  break if w == 0 && h == 0
  board = (2 * h - 1).times.map{ gets.chomp.split }
  solve(board, w, h)
end

Measured memory_bytes: 8808
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>

#define INF 1000000007
#define LINF 1000000000000000007

using namespace std;

typedef long long Int;
typedef pair<Int, Int> P;

Int gcd(Int x, Int y){
	if(y == 0)
		return x;
	return gcd(y, x % y);
}

Int lcm(Int x, Int y){
	return x * y / gcd(x, y);
}

bool sosuu(int x){
	bool b = 1;
	if(x == 1) b = 0;
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0) {
			b = 0;
			break;
		}
	}
	return b;
}

string s;

int main(){
	cin >> s;
	cout << "2018";
	for(int i = 4; i < 10; i++){
		cout << s[i];
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    S = input().rstrip()
    T = input().rstrip()

    # dp[i][j] = sのi番目とtのj番目まででえられる最長部分列の長さ
    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

    # 最長部分列の長さを探索
    for i, s in enumerate(S, 1):
        for j, t in enumerate(T, 1):
            # 一致するとき
            if s == t:
                # 一致する文字の一つ左側までの最大部分列に一致した文字を加える
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
            # 一致しない場合も、一つ手前の文字までの最大文字列を引き継ぐ
            dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

    # 最長だった場合の具体例を復元する
    i, j = len(S), len(T)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans = S[i-1] + ans
            i -= 1
            j -= 1
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 112348
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:>
問題文============================================================

=================================================================

解説=============================================================

================================================================
*/

ll N,Q;
vector<pll> s;
vector<ll> idx;
set<ll> leaders;

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> Q;
    s.resize(N);
    for(int i = 0; i < N;i++){
        cin >> s[i].first; s[i].second = i;
    }
    sort(s.begin(),s.end());
    idx.resize(N);
    for(int i = 0; i < N;i++){
        idx[s[i].second] = i;
    }
    
    for(int _ = 0; _ < Q;_++){
        string query; ll x; cin >> query >> x;
        if(query == "ADD"){
            x--;
            leaders.insert(idx[x]);
        }
        if(query == "REMOVE"){
            x--;
            leaders.erase(idx[x]);
        }
        if(query == "CHECK"){
            if(leaders.empty()){
                if(x < N) cout << "NA" << endl;
                else cout << 0 << endl;
                continue;
            }
            vector<ll> sec;
            for(auto leader : leaders) sec.push_back(s[leader].first);
            sort(sec.begin(),sec.end());
            
            ll l = -1, r = INF + 1000;
            while(r - l>1){
                ll m = (l + r)/2;
                
                ll pre = 0, sum = 0;
                for(auto v:sec){
                    ll l = lower_bound(s.begin(),s.end(),pll(v - m,-1)) - s.begin();
                    ll r = lower_bound(s.begin(),s.end(),pll(v + 1,-1)) - s.begin();
                    sum += r - max(pre,l);
                    pre = r;
                }
                
                if(N - sum <= x) r = m;
                else l = m;
            }
            
            if(r == INF + 1000){
                cout << "NA" << endl;
            }else{
                cout << r << endl;
            }
        }
    }
	return 0;
}



Measured memory_bytes: 26240
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

struct UnionFind {
    vector<int> par;
    UnionFind(int n) : par(n, -1) {}
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    void merge(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return;
        if(-par[x] < -par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<ll> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    using pint = pair<int, int>;
    using Edge = pair<ll, pint>;
    vector<Edge> edges;

    vector<int> ids(n);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) {return x[i] < x[j];});
    rep(i, ids.size()-1) {
        int u = ids[i], v = ids[i+1];
        edges.push_back(Edge(x[v] - x[u], pint(u, v)));
    }

    sort(ids.begin(), ids.end(), [&](int i, int j) {return y[i] < y[j];});
    rep(i, ids.size()-1) {
        int u = ids[i], v = ids[i+1];
        edges.push_back(Edge(y[v] - y[u], pint(u, v)));
    }

    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    ll res = 0;
    for (auto e : edges) {
        int u = e.second.first, v = e.second.second;
        ll cost = e.first;
        if (uf.issame(u, v)) continue;
        uf.merge(u, v);
        res += cost;
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 8304
n = gets.chomp.to_i
arr = gets.chomp.split.map(&:to_i)
sum = arr.inject(:+)
ahash = {}
arr.each do |a|
	if ahash.has_key?(a)
		ahash[a] += 1
	else
		ahash[a] = 1
	end
end

q = gets.chomp.to_i
hash = {}
q.times do |i|
	b, c = gets.chomp.split.map(&:to_i)
	if ahash.has_key?(b)
		sum += (c-b) * ahash[b]
		if ahash.has_key?(c)
			ahash[c] += ahash[b]
			ahash[b] = 0
		else
			ahash[c] = ahash[b]
			ahash[b] = 0 
		end
	end
	puts sum
end


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

A = [0] * N
for i in range(N):
    if i == 0:
        A[i] = B[i]
    elif i == N - 1:
        A[i] = B[i - 1]
    else:
        A[i] = min(B[i - 1], B[i])

answer = sum(A)

print(answer)


Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

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

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

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using uInt = long long unsigned int;
using Double = long double;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int N, M;
        cin >> N >> M;
        vector<Int> A, B, C;
        rep(i, 0, N) {
            Int tmp;
            cin >> tmp;
            A.push_back(tmp);
        }

        rep(i, 0, M) {
            Int tmp;
            cin >> tmp;
            rep(_, 0, tmp) {
                B.push_back(i % 2);
                C.push_back(!(i % 2));
            }
        }

        auto cnt = [&](vector<Int> X, vector<Int> Y) {
            vector<Int> xi, yi;
            rep(i, 0, X.size()) {
                if (X[i] == 1) xi.push_back(i);
            }
            rep(i, 0, Y.size()) {
                if (Y[i] == 1) yi.push_back(i);
            }

            if (xi.size() != yi.size()) return INFl;
            Int ret = 0;
            rep(i, 0, xi.size()) {
                Int tmp = abs(xi[i] - yi[i]);
                ret += tmp;
            }
            return ret;
        };

        Int ans = min(cnt(A, B), cnt(A, C));
        cout << ans << endl;

    }
};


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

    Solve().solve();


    return 0;
}



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

int main(){
  int r, c;
  cin >> r >> c;

  int vec[r+1][c+1];
  for(int i=0;i<r+1;i++){
    for(int j=0;j<c+1;j++){
      vec[i][j] = 0;
    }
  }

  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      cin >> vec[i][j];
    }
  }

  //行の集計
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      vec[i][c] += vec[i][j];
    }
  }

  //列の集計
  for(int i=0;i<r;i++){
    for(int j=0;j<c+1;j++){
      vec[r][j] += vec[i][j];
    }
  }

  for(int i=0;i<r+1;i++){
    for(int j=0;j<c+1;j++){
      if(j==c){
        cout << vec[i][j];
      } else {
        cout << vec[i][j] << " ";
      }
    }
    cout << endl;
  }
}



Measured memory_bytes: 3100
#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 FOR(i, m, n) for(int i = m; i < n; i++)
using namespace std;

int main(){
  int n, k, q;
  cin >> n;
  cin >> k;
  cin >> q;
  int a[q], b[n];
  REP(i,q) cin >> a[i];
  REP(i,n) b[i] = 0;
  
  REP(i,q){
    b[a[i]-1] += 1;
  }
  
  REP(i,n){
    if(k > q - b[i]) cout << "Yes" << '\n';
    else cout << "No" << '\n';
  }
  
  return 0;
}

Measured memory_bytes: 1408
fn main() {
    let n = read::<usize>();
    let w = read_vec::<i32>();

    let mut mi = i32::max_value();
    for i in 0..n-1 {
        let mut s1 = 0;
        for j in 0..i+1 {
            s1 += w[j];
        }
        let mut s2 = 0;
        for j in i+1..n {
            s2 += w[j];
        }

        if mi > (s1 - s2).abs() {
            mi = (s1 - s2).abs();
        }
    }
    println!("{}", mi);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


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

#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define int long long
using namespace std;
const int INF = 2e16;
const int MOD = 1e9 + 7;
const int MB = 20;


void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (i * j == n) {
				cout << "Yes";
				return;
			}
		}
	}
	cout << "No";
}
	

signed main() {
	/*
	freopen("search.in", "r", stdin);
	freopen("search.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define INF 0x3f3f3f3f
#define maxn 1000005
using namespace std;
typedef long long LL;
typedef pair <int,int> PP;
LL n,k;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> n >> k){
        LL ans=0;
        if(k==0){cout << n*n << endl;continue;}
        for(LL i=k+1;i<=n;i++){
            ans+=n/i*(i-k)+max(1ll*0,n%i-k+1);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
def solve(n, k):
    mod = n % k
    if mod == 0:
        print(0)
    elif abs(mod - k) < mod:
        print(abs(mod - k))
    else:
        print(mod)

if __name__ == "__main__":
    n, k = map(int, input().split(' '))
    solve(n, k)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
  int K,S,counter=0;
  cin>>K>>S;
  for(int x=0;x<=K;x++){
    for(int y=0;y<=K;y++){
     int z=S-(x+y);
      if(z<=K&&z>=0){
        counter++;
      }
    }
  }
  cout<<counter<<endl;
}

Measured memory_bytes: 256
n,k = map(int,raw_input().split())
boats = [map(int,raw_input().split())[1:] for i in range(k)]
r = input()
hate = [map(int,raw_input().split()) for i in range(r)]
blue = [0]*51
for i,j in hate:
	for boat in boats:
		if i in boat and j in boat:
			blue[i] = 1
			blue[j] = 1
print sum(blue)

Measured memory_bytes: 4336
from collections import defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
for a,b in AB:
    g[a].append(b)
    g[b].append(a)

cnt = 0
visited = [False] * (N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    cnt += 1
    l = [i]
    while l:
        v = l.pop()
        visited[v] = True
        for nv in g[v]:
            if not visited[nv]:
                l.append(nv)

print(cnt-1)




Measured memory_bytes: 101464
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 210
#define ll long long
#define mod 1000000007
using namespace std;

struct edge{int x, y, f, z, next;}a[N];
int jc[N], inv[N], ans, n, m, k, l, p[N], x, y, d[N], size[N], f[N], flag[N], cl, sum[N], now;

inline int gcd(int a, int b){return b?gcd(b, a%b):a;}
inline int pow(int y, int x){
	int s=1, t=y;
	while(x){if(x&1)s=(ll)s*t%mod; t=(ll)t*t%mod; x>>=1;}
	return s;
}
inline int C(int n, int m){return (ll)jc[n]*inv[m]%mod*inv[n-m]%mod;}

inline int gether(int x){return f[x]?f[x]=gether(f[x]):x;}

inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].f=a[l].z=0; a[l].next=p[x]; p[x]=l;}
inline void dfs(int x){
	flag[x]=1;
	for(int i=p[x]; i; i=a[i].next)if(!a[i].f){
		a[i].f=a[i^1].f=1;
		if(!flag[a[i].y]){
			d[++cl]=i; dfs(a[i].y); cl--;
		}else{
			d[++cl]=i;
			l++; int now=cl, x1, y1;
			while(a[d[now]].x!=a[i].y){
				if(a[d[now]].z){x1=gether(a[d[now]].z); y1=gether(l); if(x1!=y1){f[y1]=x1; size[x1]+=size[y1];}}
				a[d[now]].z=a[d[now]^1].z=l; now--;
			}
			if(a[d[now]].z){x1=gether(a[d[now]].z); y1=gether(l); if(x1!=y1){f[y1]=x1; size[x1]+=size[y1];}}
			a[d[now]].z=a[d[now]^1].z=l; now--;
			cl--;
		}
	}
}

int main(){
	jc[0]=1; for(int i=1; i<=200; i++)jc[i]=(ll)jc[i-1]*i%mod;
	inv[0]=inv[1]=1; for(int i=2; i<=200; i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1; i<=200; i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
	scanf("%d%d%d", &n, &m, &k);
	l=1; memset(p, 0, sizeof(p));
	for(int i=1; i<=m; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x);}
	l=cl=0; memset(f, 0, sizeof(f)); memset(flag, 0, sizeof(flag));
	for(int i=1; i<=m; i++)size[i]=1;
	for(int i=1; i<=n; i++)if(!flag[i])dfs(i);
	memset(sum, 0, sizeof(sum));
	ans=1;
	for(int i=1; i<=m; i++){
		x=a[i*2].z;
		if(x)sum[gether(x)]++; else ans=(ll)ans*k%mod;
	}
	for(int i=1; i<=l; i++)if(!f[i]){
		if(size[i]==1){
			x=sum[i]; now=0;
			for(int j=0; j<=x-1; j++)now=(now+pow(k, gcd(x, j)))%mod;
			ans=(ll)ans*now%mod*pow(x, mod-2)%mod;
		}else ans=(ll)ans*C(k+sum[i]-1, k-1)%mod;
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 128
"use strict";

var main = function main(input) {
  var A = parseInt(input.split("\n")[0], 10);
  var B = parseInt(input.split("\n")[1], 10);
  var C = parseInt(input.split("\n")[2], 10);
  var X = parseInt(input.split("\n")[3], 10);
  var startNum50 = X / 50 > C ? C : X / 50;
  var count = 0;

  for (var i = startNum50; i >= 0; i--) {
    var Xminus50 = X - 50 * i;

    if (Xminus50 == 0) {
      count++;
      continue;
    }

    if (Xminus50 % 100 == 0) {
      var startNum100 = Xminus50 / 100 > B ? B : Xminus50 / 100;

      for (var j = startNum100; j >= 0; j--) {
        var Xminus50minus100 = Xminus50 - 100 * j;

        if (Xminus50minus100 == 0) {
          count++;
          continue;
        }

        if (Xminus50minus100 % 500 == 0 && Xminus50minus100 / 500 <= A) {
          count++;
        }
      }
    }
  }

  console.log(count);
};

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 9420
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
//map<ll,bool>mp;
main()
{
    ll n,i,ans=-1,s;
    cin>>n;
    ll n1=n;
    if(n==1 || n==7)
    {
        printf("1\n");return 0;
    }
    if(n%7==0)n=n/7;
    s=1;ll d=10%n;ll p=1;
    //mp[1]=1;
    for(i=2;i<=n1;i++)
    {
        p=(p*d)%n;
        s=(s+p)%n;
        if(s==0)
        {
            ans=i;break;
        }

    }
    cout<<ans<<endl;
}


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

int main()
{
  int n, l;
  cin >> n >> l;
  valarray<int> va(n);
  iota(begin(va), end(va), l);
  sort(begin(va), end(va), [](auto a, auto b){return abs(a) < abs(b);});
  cout << va.sum() - va[0] << endl;
}


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

typedef long long ll;

int main()
{
  int r, g, b, n;
  cin >> r >> g >> b >> n;

  int res = 0;
  for (int i = 0; i <= floor(n / r); i++)
  {
    for (int j = 0; j <= floor((n - r * i) / g); j++)
    {
      if ((n - r * i - g * j) % b == 0)
      {
        res++;
      }
    }
  }

  cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	string S_,T;
	int slen,tlen,i,j;
	bool flag = false;
	cin >> S_ >> T;
	slen = S_.length();
	tlen = T.length();
	if(slen < tlen){
		cout << "UNRESTORABLE" <<endl;
		return 0;
	}
	for(i=slen-tlen;i>=0;i--){
		for(j=0;j<tlen;j++){
			if(S_[i+j] != '?' && S_[i+j] != T[j]) break;
		}
		if(j == tlen){
			flag = true;
			for(j=0;j<tlen;j++){
				S_[i+j] = T[j];
			}
			break;
		}
	}
	if(!flag){
		cout << "UNRESTORABLE" <<endl;
	}
	else{
		for(i=0;i<slen;i++){
			if(S_[i]=='?') S_[i] = 'a';
		}
		cout << S_ <<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 100005
using namespace std;
int n,in[M];
int main()
{
    while (~scanf("%d", &n)) {
        REP(i,1,n) scanf("%d", &in[i]);
        int ans = 0;
        REP(i,1,n) ans = __gcd(ans, in[i]);
        printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef vector<int> v;
int h,w,k;
v x(v a,v b){
	if(a.size()==b.size())return max(a,b);
	return (a.size()>b.size())?a:b;
}
int main(){
	while(cin>>w>>h&&h){
	v d[75][75],s;r(i,h)r(j,w){
		char z;cin>>z;z-='0';
		if(!(z/10)&&(z||d[i][j].size())){
			d[i][j].push_back(z);
			d[i+1][j]=x(d[i+1][j],d[i][j]);
			d[i][j+1]=x(d[i][j+1],d[i][j]);
		}s=x(s,d[i][j]);
	}r(i,s.size())cout<<s[i];cout<<endl;
	}return 0;
}

Measured memory_bytes: 3392
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>

const int MX=1000000;
const ll inf=1e9;
const ll mod=998244353;


int a[MX];

int main()
{

    FasterIO;


    int n;

    cin>>n;
    for(int i=1; i<=3*n; i++) cin>>a[i];

    sort(a+1, a+3*n+1);

    ll sm=0;

    for(int i=1, j=3*n; i<j; i++, j-=2)
    {
        sm+=a[j-1];
    }

    cout<<sm<<endl;

    return 0;
}


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

namespace _0361
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int i;
            for (i = 1000; !(x[0] % i == 0 && x[1] % i == 0); i--) ;
            Console.WriteLine(x.Sum() - i + 1);
        }
    }
}

Measured memory_bytes: 9632
#include <iostream>
using namespace std;
int sea[51][51], w, h;
const int di[8] = {-1, 1, 0, 0, 1, -1, -1, 1};
const int dj[8] = {0, 0, -1, 1, 1, 1, -1, -1};

void dfs(int i, int j) {
  sea[i][j] = 0;
  for (int z = 0; z < 8; z++) {
    int ti = i + di[z], tj = j+ dj[z];
    if (ti < 0 || tj < 0 || ti >= h || tj >=w) continue;
    if (sea[ti][tj]) dfs(ti, tj);
  }
}

void solve() {
  for(int i=0;i<h;i++)
  for(int j=0;j<w;j++)
  cin>>sea[i][j];
  
  int res = 0;
  for(int i=0;i<h;i++)
  for(int j=0;j<w;j++)
  if (sea[i][j] == 1) {
    dfs(i, j); res++;
  }
  
  cout<<res<<endl;
}

int main (int argc, char const* argv[]) {
  while (cin>>w>>h, w||h) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

const int INF=1e18;

void solve(int N,int M)
{
    int s,g1,g2; cin>>s>>g1>>g2;
    s--; g1--; g2--;
    vector<vector<int>> dist(N,vector<int>(N,INF));
    for(int i=0;i<N;i++) dist[i][i]=0;
    for(int i=0;i<M;i++){
        int a,b,c; cin>>a>>b>>c;
        a--; b--;
        dist[a][b]=c;
    }

    for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++){
        chmin(dist[i][j],dist[i][k]+dist[k][j]);
    }
    
    int ans=INF;
    for(int t=0;t<N;t++){
        chmin(ans,dist[s][t]+dist[t][g1]+dist[t][g2]);
    }
    cout<<ans<<endl;
}

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

    while(true){
        int N,M; cin>>N>>M;
        if(N==0) break;
        solve(N,M);
    }
    return 0;
}


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


int main(){long W, A, B;
cin >> W >> A >> B;
long tmp;
           long zero = 0;
tmp = max(zero, max(A, B) - (min(A, B) + W));
cout << tmp << endl;
return 0;
}




Measured memory_bytes: 256
//gcc listsirkuler.c map.c player.c mesinkata.c mesinkar.c matriks.c pcolor.c point.c queue.c unit.c main.c -o main
#include <bits/stdc++.h>
#define Semangat using
#define World namespace
#define Final std;
#define WF {ios_base::sync_with_stdio(0);cin.tie(0);}
 
Semangat World Final

string x;
int a,b,c,d;

int main(){
	WF
	cin>>x;
	a=x[0]-48;
	b=x[1]-48;
	c=x[2]-48;
	d=x[3]-48;
	if(a+b+c+d==7){
		cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7\n";
	}
	else if(a+b+c-d==7){
		cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7\n";
	}
	else if(a+b-c+d==7){
		cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7\n";
	}
	else if(a-b+c+d==7){
		cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7\n";
	}
	else if(a-b+c-d==7){
		cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7\n";
	}
	else if(a-b-c+d==7){
		cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7\n";
	}
	else if(a+b-c-d==7){
		cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7\n";
	}
	else if(a-b-c-d==7){
		cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7\n";
	}
	return 0;
}

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

public class Main {
    public static void main(String[] args) throws Exception {
        FastReader sc = new FastReader();
        if(sc.nextInt()<=sc.nextInt()){
            System.out.println("unsafe");
        }else System.out.println("safe");
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 25292
test=[]
while True:
  m,r,f=map(int,input().split(' '))
  if m==-1 and r==-1 and f== -1:
    break
  else:
    test.append([m,r,f])



for m,r,f in test:
  if m== -1 or r==-1:
    print('F')
  elif m+r >= 80:
    print('A')
  elif 65 <= m+r < 80:
    print('B')
  elif 50 <= m+r < 65:
    print('C')
  elif  30 <= m+r < 50:
    if f >= 50:
      print('C')
    else:
      print('D')
  else:
      print('F')


Measured memory_bytes: 5600
#include <cmath>
#include <map>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
const int MaxN = 1e5 + 4;
typedef long long LL;
map<int,int>mp;
pair<int,int> PLL;
int main(){
	int a,b,c,x,y;
	int ans = 1e9+5;
	cin>>a>>b>>c>>x>>y;
	if(2*c < a+b){
		int t = min(x,y);
		int v = max(x,y);
		int u = abs(x-y);
		if(x > y)
			ans = min(v*c*2,min(t*c*2+(x-y)*a,ans));
		else ans = min(v*c*2,min(t*c*2+(y-x)*b,ans));
	}
	else {
		ans = a*x+b*y;
	}
	cout<<ans<<endl;
	return 0;
}

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

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

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

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

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

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

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

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

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

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

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

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

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

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



int main() {
	string S, T;
	cin >> S >> T;
	ll ans = INF;
	rep(i, S.size() - T.size()+1) {
		string U = S.substr(i, T.size());
		ll cnt = 0;
		rep(j, T.size()) {
			if (T[j] != U[j]) { cnt++; }
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <vector>
#include <math.h>
#include <typeinfo>
#include <numeric>
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

int main()
{
	int N;
	cin >> N;

	cout << N / 3 << endl;

	return 0;
 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	string S;
	cin >> S;
	int rec = 0;
	if (S[0] == 'A' && S[S.length()-1] > 96) {
		if (S[1] < 96) {
			rec += 2;
		}
		else {
			for (int i = 2; i < S.length() - 1; i++) {
				if (S[i] == 'C') {
					rec++;
				}
				if (S[i] < 96) {
					rec += 2;
				}
			}
		}
	}
	else {
		rec += 2;
	}
	if (rec == 3) {
		cout << "AC" << endl;
	}
	else {
		cout << "WA" << endl;
	}
	return 0;
}

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

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

  int m;
  cin >> m;
  string t;
  bool flag = false;
  for(int i=0; i<m; i++){
    cin >> t;
    bool known = false;
    for(int j=0; j<n; j++){
      if(t == u[j]){
        if(flag){
          cout << "Closed by " << t << endl;;
        }else{
          cout << "Opened by " << t << endl;
        }
        known = true;
        flag = !flag;
        break;
      }
    }
    if(!known)
      cout << "Unknown " << t << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3152