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

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

typedef long long ll;

template <class T = ll> T in() { T x; cin >> x; return (x); }

signed main() {
	int n;cin >> n;
	int a[3 * n];
	REP (i,3 * n) cin >> a[i];
	sort(a,a + 3 * n);
	int ans = 0;
	FOR (i,n,3 * n) {
		ans += a[i];
		++i;
	}
	cout << ans << endl;
}

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            string str1 = Console.ReadLine();
            string str2 = Console.ReadLine();

            //for文
            int iMax = str1.Length;

            //判定
            if (str2 == str1)
            {
                Console.WriteLine("Yes");
                return;
            }

            for (int i=1;i< iMax;i++)
            {
                //最後尾の文字格納
                string strLast= str1.Substring(iMax-1);

                //最後尾削除
                str1= str1.Remove(iMax - 1);

                //最後尾を先頭に乗せる
                str1 = strLast+str1 ;

                //判定
                if(str2==str1)
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }

            Console.WriteLine("No");

        }
    }

}

Measured memory_bytes: 25876
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<iterator>
#include<complex>
#include<stack>
#include "stdio.h"
using namespace std;

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

using ll = long long;
using Pii = pair<int, int>;

const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const long long mod_const = 1e9+7;

int dy[] = { 0, 0, 1, -1, 0 };
int dx[] = { 1, -1, 0, 0, 0 };

using MIte = multimap<ll, ll, greater<ll> >::iterator;

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

using pll = pair<long long, long long>;



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

	int N;
	cin >> N;

	set<int> s;

	for (int i = 1; i != 10; ++i) {
		for (int j = 1; j != 10; ++j) {
			s.insert(i * j);
		}
	}

	if (s.find(N) == s.end()) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  string s;
  cin >> s;
  s[3] = '8';
  cout << s << endl;
  return 0;
}


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

int main() {
  int N,Z=0;
  cin>>N;
  vector<vector<int>>p(10,vector<int>(10));
  for(int i=1;i<=N;i++){
    int d=i,a=i%10;
    while(d>=10){
      d/=10;
    }
    p.at(a).at(d)++;
  }
  for(int i=1;i<10;i++){
    Z-=p.at(i).at(i)*p.at(i).at(i);
    for(int j=i;j<10;j++){
      Z+=2*p.at(i).at(j)*p.at(j).at(i);
    }
  }
  cout<<Z<<endl;
    
}

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

int main(){
  string S;
  cin >> S;
  int count = 0;
  int max = 0;
  for (int i = 0; i < S.size(); i++){
    if (S.at(i) == 'R'){
      count += 1;
      if (max < count){
        max = count;
      }
      
    } 
    if (S.at(i) == 'S') count = 0;

  }

  cout << max << endl;
}

Measured memory_bytes: 3620
n,x = map(int,input().split())
lst = []
for _ in range(n):
    p = int(input())
    lst.append(p)
ing = x -(sum(lst))
mini = 10**5
for i in range(n):
    if lst[i] <= mini:
        mini = lst[i]
print(ing//mini+n)

Measured memory_bytes: 3060
#include <iostream>

 

using namespace std;

 

int main()
{
    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if(x-r>=0 && y-r>=0 && x+r<=w && y+r<=h)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 3116
n=int(input())
L=[['nd']*n for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        L[i][x-1]=y
r=0
for bit in range(1<<n):
    flag=0
    for k in range(n):
        if bit&(1<<k):
            for l in range(n):
                if l!=k:
                    if L[k][l]==1:
                        if bit&(1<<l):
                            pass
                        else:
                            flag=1
                            break
                    elif L[k][l]==0:
                        if bit&(1<<l):
                            flag=1
                            break
                        else:
                            pass
            
        if flag==1:
            break
        if k==n-1:
            r=max(r,str(bin(bit)).count('1'))
print(r)

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

typedef int64_t i64;
typedef uint64_t ui64;

const int inf=1073741823;
const i64 llinf=4611686018427387903LL;

int main(void){
    int s;
    scanf("%i",&s);
    printf("%i:%i:%i\n",s/3600,(s%3600)/60,s%60);
    return 0;
}



Measured memory_bytes: 3192
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<deque>
using namespace std;

using ll = long long;
const int INF = 1001001001;
const ll LLINF = 1001001001001001001;
const int MOD = 1000000007;

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

int main(void)
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if ((c / b + ((c % b) ? 1 : 0)) <= (a / d + ((a % d) ? 1 : 0))) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}





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

int main() {
  string S;
  cin >> S;
  string ans = "";
  for (int b = 0; b < (1 << 3); b++) {
    int res = S.at(0) - '0';
    string formula = to_string(res);
    for (int i = 0; i < S.size() - 1; i++) {
      if (b & (1 << i)) {
        formula += '+';
        res += S.at(i + 1) - '0';
      } else {
        formula += '-';
        res -= S.at(i + 1) - '0';
      }
      formula += S.at(i + 1);
    }

    if (res == 7) {
      cout << formula + "=7" << endl;
      break;
    }
  }
}


Measured memory_bytes: 3672
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)

using namespace std;
typedef pair<int, int> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

int N, K;
vector<ipair> res;
bool solve() {
    int MAX = (N - 1) * (N - 2) / 2;
    if(K > MAX) return false;

    //ウニ状態を作る
    for(int i = 1; i < N; ++i) {
        res.push_back(make_pair(i, N));
    }
    
    int add_cnt = MAX - K;
    if(add_cnt > 0) {
        for(int i = 1; i < N; ++i)
            for(int j = i + 1; j < N; ++j) {
                res.push_back(make_pair(i, j));
                if(--add_cnt == 0)
                    goto finish;
            }
    }
    
    finish:;
    
    return true;
}
int main(int argc, char **argv) {
    cin >> N >> K;
    if(solve()) {
        cout << res.size() << endl;
        for(int i = 0; i < res.size(); ++i)
            cout << res[i].first << " " << res[i].second << endl;
    } else {
        cout << "-1" << endl;
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define N 100005
#define ll long long
#define ull unsigned long long
#define loop1(i, j, k, step) for (int i = j; i < k; i += step)
#define loop(i, j, k) for (int i = j; i < k; i++)
#define rloop1(i, j, k, step) for (int i = j; i >= k; i -= step)
#define rloop(i, j, k) for (int i = j; i >= k; i--)
#define rep(i, k) for (int i = (0); i < (k); i++)
#define rrep(i, k) for (int i = k - 1; i >= 0; i--)

#define forall(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define mp make_pair
#define pb push_back
#define pop pop_back
#define F first
#define S second
#define sz(x) (int)(x).size()
#define endl "\n"
#define Max (int)INT_MAX
#define Min (int)INT_MIN
#define MEM(a, b) memset(a, (b), sizeof(a))
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define lin puts("");
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
//char ch[101][101];
char c;
int arr[10000], brr[105];

void solve()
{
    string s;
    cin >> s;
    if (s.size() < 6 || s.size() > 6)
    {
        cout << "No" << endl;
        return;
    }
    if (s[2] == s[3] && s[4] == s[5])
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}
int main()
{
    auto start = clock();
    fast_io;
    //freopen("test.txt", "r", stdin);
    int t;
    t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    auto stop = clock();
    cerr << "time taken:" << double(stop - start) / double(CLOCKS_PER_SEC) << " s" << endl;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
int main(void){
    char moji;
    int i;

    for(i=1;1<=200;i++){
    scanf("%c",&moji);
    if(moji=='a'){
        printf("A");
    }else if(moji=='b'){
        printf("B");
    }else if(moji=='c'){
        printf("C");
    }else if(moji=='d'){
        printf("D");
    }else if(moji=='e'){
        printf("E");
    }else if(moji=='f'){
        printf("F");
    }else if(moji=='g'){
        printf("G");
    }else if(moji=='h'){
        printf("H");
    }else if(moji=='i'){
        printf("I");
    }else if(moji=='j'){
        printf("J");
    }else if(moji=='k'){
        printf("K");
    }else if(moji=='l'){
        printf("L");
    }else if(moji=='m'){
        printf("M");
    }else if(moji=='n'){
        printf("N");
    }else if(moji=='o'){
        printf("O");
    }else if(moji=='p'){
        printf("P");
    }else if(moji=='q'){
        printf("Q");
    }else if(moji=='r'){
        printf("R");
    }else if(moji=='s'){
        printf("S");
    }else if(moji=='t'){
        printf("T");
    }else if(moji=='u'){
        printf("U");
    }else if(moji=='v'){
        printf("V");
    }else if(moji=='w'){
        printf("W");
    }else if(moji=='x'){
        printf("X");
    }else if(moji=='y'){
        printf("Y");
    }else if(moji=='z'){
        printf("Z");
    }else if(moji==' '){
        printf(" ");
    }else if(moji=='.'){
        printf(".");
    }else{
        printf("\n");
        break;
    }
    }
    return 0;
    }



Measured memory_bytes: 2036
x, y = map(int,input().split())
if x >= 0 and y > 0:
    if x <= y:
        ans = abs(x - y)
    else:
        ans = abs(x - y) + 2
if x >= 0 and y == 0:
    if x <= y:
        ans = abs(x - y)
    else:
        ans = abs(x - y) + 1
elif x >= 0 and y < 0:
    ans = abs(abs(x) - abs(y)) + 1
elif x < 0 and y >= 0:
    ans = min((abs(abs(x) - abs(y)) + 1), y - x)
else:
    if x <= y:
        ans = abs(x - y)
    else:
        ans = abs(x - y) + 2
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };

int R,C,N;
vector<P2> pos_x1,pos_x2,pos_y1,pos_y2;
vector<P2> edge;
stack<int> st;
bool flag[100005];

bool isOnEdge(int x,int y){
    if(x==0||x==R||y==0||y==C)return true;
    else return false;
}

void pushEdge(int x,int y,int n){
    if(x==0)pos_x1.PB(P2(x,P1(y,n)));
    else if(x==R)pos_x2.PB(P2(x,P1(y,n)));
    else if(y==0)pos_y1.PB(P2(x,P1(y,n)));
    else if(y==C)pos_y2.PB(P2(x,P1(y,n)));
}

signed main(){
    cin>>R>>C;
    cin>>N;
    for(int i=0;i<N;++i){
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        if(isOnEdge(x1,y1)&&isOnEdge(x2,y2)){
            pushEdge(x1,y1,i+1);
            pushEdge(x2,y2,i+1);
        }
    }
    sort(pos_x1.begin(),pos_x1.end(),greater<P2>());
    sort(pos_x2.begin(),pos_x2.end());
    sort(pos_y1.begin(),pos_y1.end());
    sort(pos_y2.begin(),pos_y2.end(),greater<P2>());
    for(auto v:pos_y1)edge.PB(v);
    for(auto v:pos_x2)edge.PB(v);
    for(auto v:pos_y2)edge.PB(v);
    for(auto v:pos_x1)edge.PB(v);
    if(edge.size()<=2){
        printf("YES\n");
        return 0;
    }
    st.push(edge[0].se.se);
    flag[edge[0].se.se]=true;
    for(int i=1;i<edge.size();++i){
        int it = i%edge.size();
        int v = edge[it].se.se;
        if(flag[v]==false){
            flag[v]=true;
            st.push(v);
        }
        else if(st.top()==v)st.pop();
        else {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
}


Measured memory_bytes: 17308
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,dp[100000],cost[100000],weight[100];

void func(int a)
{
    dp[1]=0;
    dp[2]=abs(cost[1]-cost[2]);
    for(int i=3; i<=a; i++)
    {
        dp[i]=min(dp[i-1]+abs(cost[i]-cost[i-1]),dp[i-2]+abs(cost[i]-cost[i-2]));
    }
}

int main()
{
    memset(dp,-1,sizeof(dp));
    cin>>a;
    for(int i=1; i<=a; i++)
    {
        cin>>cost[i];
    }
    func(a);
    cout<<dp[a]<<endl;
    //cout<<nCr(a,b)<<endl;

}


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var sc = NewScanner(os.Stdin, 1000000)

func main() {
	N := sc.readInt()
	M := sc.readInt()
	C := sc.readInt()
	B := []int{}
	A := [][]int{}
	for i := 0; i < M; i++ {
		B = append(B, sc.readInt())
	}
	for j := 0; j < N; j++ {
		tmp := []int{}
		for i := 0; i < M; i++ {
			tmp = append(tmp, sc.readInt())
		}
		A = append(A, tmp)
	}

	res := 0
	for j := 0; j < N; j++ {
		sumtmp := 0
		for i := 0; i < M; i++ {
			sumtmp += A[j][i] * B[i]
		}
		sumtmp += C
		if sumtmp > 0 {
			res++
		}
	}
	fmt.Println(res)
}

type Scanner struct {
	*bufio.Scanner
}

func (scn *Scanner) readInt() int {
	scn.Scanner.Scan()
	i, _ := strconv.Atoi(scn.Scanner.Text())
	return i
}

func NewScanner(r io.Reader, bufSize int) *Scanner {
	buf := make([]byte, bufSize)
	scn := bufio.NewScanner(r)
	scn.Buffer(buf, bufSize)
	scn.Split(bufio.ScanWords)
	return &Scanner{scn}
}


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

double a,b;
int ans;

int main() {
  cin >> a >> b;
  ans = ceil((b-1)/(a-1));
  cout << ans << endl;
  return 0;
}


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

int main(){
  int m, f, r;
  while(true){
    cin >> m >> f >> r;
    if(m == -1 && f == -1 && r == -1) return 0;
    if(m == -1 || f == -1) cout << "F" << endl;
    else if(m + f >= 80) cout << "A" << endl;
    else if(m + f >= 65 && m + f < 80) cout << "B" << endl;
    else if(m + f >= 50 && m + f < 65) cout << "C" << endl;
    else if(m + f >= 30 && m + f < 50){
      if(r >= 50) cout << "C" << endl;
      else cout << "D" << endl;
    }
    else if(m + f < 30) cout << "F" << endl;
  }
}


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

void solve()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if (a[i] == a[j] || a[j] == a[k])
                    continue;
                if (a[i] + a[j] >= a[k] && a[k] - a[i] < a[j])
                {
                    // cout << a[i] << " " << a[j] << " " << a[k] << endl;
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    long long t = 1;
    // cin >> t;
    for (long long i = 1; i <= t; i++)
    {
        //cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <map>
using namespace std;
int main() {
    int n,d,k;
    cin>>n;
    cin>>d>>k;
    int a[105];
    int cnt=0;
	for(int i=0;i<n;i++){
    	cin>>a[i];
    	cnt+=d/a[i]+1;
    	if(d%a[i]==0){
    		cnt-=1;
		}
	}
	cnt+=k;
	cout<<cnt<<endl;
	return 0;
}

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

int main(){
 int a,b,s;
 char op;
 while(1){
  cin >> a >> op >> b;
  if (op=='?') break;
  
  if (op=='+'){
   s=a+b;
  }
  else if (op=='-'){
   s=a-b;
  }
  else if (op=='*'){
   s=a*b;
  }
  else{
   s=a/b;
  }
  cout << s << endl;
 }
return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
ll N;
int main(){
    cin>>N;
    ll w=0;
    for(ll h=0;h<=3500;h++){
        for(ll n=0;n<=3500;n++){
            if(h==0||n==0||N==0) continue;
            if(4*h*n-N*n-N*h==0) continue;
            if((N*h*n)%(4*h*n-N*n-N*h)==0){
                w=(N*h*n)/(4*h*n-N*n-N*h);
                if(w<=0) continue;
                cout<<h<<" "<<n<<" "<<w<<endl;
                return 0;
            } 
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>

using namespace std;
using pii=pair<int,int>;
using ll=long long;

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

    int h,w;
    cin>>h>>w;
    vector<string> a(h);
    vector<vector<pair<pii,pii>>> b(h,vector<pair<pii,pii>>(w));
    for(int i=0; i<h; i++) cin>>a[i];
    for(int i=0; i<h; i++){
        int now=-1;
        for(int j=0; j<w; j++){
            b[i][j].first.first=now;
            if(a[i][j]=='#') now=j;
        }
        now=w;
        for(int j=w-1; j>=0; j--){
            b[i][j].first.second=now;
            if(a[i][j]=='#') now=j;
        }
    }

    for(int j=0; j<w; j++){
        int now=-1;
        for(int i=0; i<h; i++){
            b[i][j].second.first=now;
            if(a[i][j]=='#') now=i;
        }
        now=h;
        for(int i=h-1; i>=0; i--){
            b[i][j].second.second=now;
            if(a[i][j]=='#') now=i;
        }
    }

    int answer=0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(a[i][j]=='.'){
                answer=max(answer,b[i][j].first.second-b[i][j].first.first+b[i][j].second.second-b[i][j].second.first-3);
            }
        }
    }
    cout<<answer;

    return 0;
}


Measured memory_bytes: 67072
def main():
    n = int(input())
    ans = 10000000000000
    for i in range(1, int(n ** 0.5 + 0.5) + 1):
        if n % i == 0:
            ans = min(ans, i + n // i - 2)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9396
N = gets.to_i
A = gets.split.map(&:to_i)

last_index = 0
n_ = (1 .. N + 1).find do |n|
  found = (last_index ... N).find{|i| A[i] == n }
  last_index = found if found
  !found
end
puts n_ == 1 ? -1 : N - (n_ - 1)


Measured memory_bytes: 19204
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#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())

ll N, M, R;
vector<ll> r;
ll road[201][201];

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

  cin >> N >> M >> R;
  rep(i,R){ll inp; cin >> inp; r.pb(inp);}

  rep(i,201)rep(j,201)
    road[i][j]=1e9;

  rep(i,M){
    ll a,b,c; cin >> a >> b >> c;
    road[a][b]=c;
    road[b][a]=c;
  }

  rep(k,N+1)rep(i,N+1)rep(j,N+1)
    road[i][j]=min(road[i][j], road[i][k]+road[k][j]);


  
  ll ans = 1e9;
  sort(all(r));
  
  //ll times = 1;FOR(i,1,R+1)times*=i;
  do{
    ll sum=0;
    rep(j,r.size()-1){
      sum+=road[r[j]][r[j+1]];
    }
    ans = min(ans,sum);
  }while( next_permutation(all(r)) );
  

  cout << ans << endl;
  
  
  return 0;
}


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

int check(int num);

int main() {
  // ここにプログラムを追記
  int a, b;
  int result = 0;

  cin >> a >> b;
  for(int i = a; i<b+1;i++){
    result +=check(i);
  }


  cout << result << endl;
}

int check(int num){
  string str, rev = "";
  str = to_string(num);
  for(int i = str.size()-1; i>=0;i--){
    rev+=str[i];
  }

  return str == rev;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define f(i,a,b) for(int i=(a); i<(b);++i)
const unsigned int M = 1000003;
int main()
{
    int n;
    string s;
    set <string> situ;
    cin>>n;
    while(n--){
        cin>>s;
        situ.insert(s);
    }
    cout<<situ.size()<<endl;
    return 0;
}


Measured memory_bytes: 19176
# -*- coding: utf-8 -*-
"""
Created on Mon Aug  1 00:00:01 2016

@author: dotha
"""

def h(a):
    if a[0]*a[1] <= 0:
        return 'Zero'
    elif a[0] < 0:
        if (a[1]-a[0])%2 == 0:
            return 'Negative'
        else:
            return 'Positive'
    else:
        return 'Positive'
        
print(h(list(map(int,input().split(' ')))))

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

int main() {
    long long n, c, k;
    long long t[100010];
    cin >> n >> c >> k;
    for (long long i=0; i<n; i++) {
        cin >> t[i];
    }
    sort(t, t+n);
    long long bn = 0;
    for (long long i=0; i<n;){
        long long temp = 0;
        for (int j=1; j<=c;){
            if (j == c){
                temp += j;
                bn++;
                break;
            }
            else if (t[i+j]<=t[i]+k){
                j++;
            }
            else if (t[i+j]>t[i]+k){
                temp += j;
                bn++;
                break;
            }
        }
        i += temp;
        if (i>=n) break;
    }
    cout << bn << endl;
    return 0;
}

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

#define fi first
#define se second

using namespace std;

using ll=long long;
using ld=long double;

int main()
{
    int n;
    scanf("%d",&n);
    vector<ld> x(n);
    for(auto &i:x)
        scanf("%Lf",&i);
    vector<vector<ld>> dp(n+1,vector<ld>(n+1));
    dp[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        dp[i][0]=dp[i-1][0]*(1-x[i-1]);
        for(int j=1;j<=n;++j)
            dp[i][j]=dp[i-1][j]*(1-x[i-1])+dp[i-1][j-1]*x[i-1];
    }
    int m=(n+1)>>1;
    ld res=0;
    for(int i=m;i<=n;++i)
        res+=dp[n][i];
    printf("%.10Lf\n",res);
}



Measured memory_bytes: 141056
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[] w, v;
	static int N, W;
	static long[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] line = sc.nextLine().split(" ");
		N = Integer.parseInt(line[0]);
		W = Integer.parseInt(line[1]);

		w = new int[N];
		v = new int[N];
		for (int i = 0; i < N; i++) {
			line = sc.nextLine().split(" ");
			w[i] = Integer.parseInt(line[0]);
			v[i] = Integer.parseInt(line[1]);
		}

		dp = new long[N + 1][W + 1];
		for (long[] row : dp)
			Arrays.fill(row, -1);
		System.out.println(dfs(0, W));
	}

	static long dfs(int i, int j) {
		long res;

		if (dp[i][j] > -1) return dp[i][j];
		if (i == N) res = 0;
		else if (j < w[i]) res = dfs(i + 1, j);
		else res = Math.max(dfs(i + 1, j), dfs(i + 1, j - w[i]) + v[i]);

		return dp[i][j] = res;
	}
}

Measured memory_bytes: 129620
from collections import Counter
import sys
import math
from functools import cmp_to_key

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)


def main():
    n = int(input())
    a = list([tuple(map(int, input().split())) for i in range(n)])
    a = list(map(lambda x: x[0] == x[1], a))
    for i in range(n-2):
        if a[i] and a[i+1] and a[i+2]:
            print("Yes")
            return
    print("No")
main()


Measured memory_bytes: 9568
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    string s;
    cin >> s;
    bool b[4] = {};
    for(int i = 0;i < s.size();i++)
    {
        if(s[i] == 'N')
        {
            b[0] = true;
        }
        else if(s[i] == 'S')
        {
            b[1] = true;
        }
        else if(s[i] == 'E')
        {
            b[2] = true;
        }
        else
        {
            b[3] = true;
        }
    }
    if(b[0] == b[1] && b[2] == b[3])
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
s = gets.chomp.chars
ans = 0
(0..s.size-1).each do |i|
  (i..s.size-1).each do |j|
    size = s[i..j].size if s[i..j].all? { |k| ['A', 'G', 'C', 'T'].include?(k) }
    size = 0 if size.nil?
    ans = size if size > ans
  end
end
p ans


Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(), v.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;

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

  if(S[S.size()-1]=='s')
  {
    S = S + "es";
  }
  else
  {
    S = S + "s";
  }

  cout << S << endl;
  return 0;
}


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

double rec_exp(vector<vector<vector<double> > > &dp, int i, int j, int k, int n) {
    if (dp.at(i).at(j).at(k) >= 0.0) {
        return dp.at(i).at(j).at(k);
    }
    if (i == 0 && j == 0 && k == 0) {
        return 0.0;
    }
    double expectancy = 0.0;
    if (i > 0) {
        expectancy += rec_exp(dp, i-1, j, k, n) * (double)i;
    }
    if (j > 0) {
        expectancy += rec_exp(dp, i+1, j-1, k, n) * (double)j;
    }
    if (k > 0) {
        expectancy += rec_exp(dp, i, j+1, k-1, n) * (double)k;
    }
    expectancy += (double)n;
    expectancy /= (double)(i + j + k);
    dp.at(i).at(j).at(k) = expectancy;
    return expectancy;
}

int main() {
    int n; cin >> n;
    vector<int> num(3, 0);
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        num.at(a-1)++;
    }
    vector<vector<vector<double> > > dp(301, vector<vector<double> >(301, vector<double>(301, -1)));
    cout << fixed << setprecision(10) << rec_exp(dp, num.at(0), num.at(1), num.at(2), n) << endl;
}

Measured memory_bytes: 217088
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
N, W = map(int, input().split())
v = [0]*101
w = [0]*10001
for i in range(N):
	v[i], w[i] = map(int, input().split())

### solve
dp = [[0 for j in range(10001)] for i in range(101)]

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

print(dp[N][W])


Measured memory_bytes: 25960
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define inf 500000000
#define IOS ios_base::sync_with_stdio(0)
#define meM(y,a) memset(y,a,sizeof y)
#define sC(a) scanf("%d",&a)
#define alL(a) a.begin(),a.end()
#define prinT(a,sz)  cout<<a[0];for(int i=1;i<sz;i++)cout<<" "<<a[i];cout<<endl
#define ranD srand(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int>pi;
typedef pair<ll,ll>pll;
//int fx[]={0,0,1,-1};
//int fy[]={1,-1,0,0};
//int gx[]={0,0,1,1,1,-1,-1,-1};
//int gy[]={1,-1,0,1,-1,0,1,-1};
bool check(int n,int p){return (1<<p)&n;}

int main()
{
    IOS;
    ll a,b,x;
    cin>>a>>b>>x;
    ll res=b/x-(a+x-1)/x+1;
    cout<<res<<endl;
}








Measured memory_bytes: 256
n = int(input())
A1 = [int(i) for i in input().split()]
A2 = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    ans = max(ans, sum(A1[0 : i + 1]) + sum(A2[i : n]))
    
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1e9
#define MOD 1e9+7
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef tuple<ll, ll, ll> T;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    map<ll,ll> mp;
    REP(i,n){
        ll a,b;
        cin>>a>>b;
        mp[a]+=b;
    }
    ll cnt=0;
    for(auto p:mp){
        cnt+=p.second;
        if(cnt>=k){
            cout<<p.first<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 4224
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string>
#include <string.h>

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

using namespace std;
int dp[1001][1001];
//?????????????????????
int n;
string x,y;
void solve(){
	cin >> n;
	REP(j,n){
	cin >> x >> y;
	memset(dp,0,1001*1001);
	int xn = x.size();
	int yn = y.size();
	REP(jj,xn+1){
		 REP(ii,yn+1){
			 if(jj <= 0 || ii <= 0){
				 dp[jj][ii] = 0 ;
			 }
			 else if(x[jj-1]==y[ii-1]) {
				 dp[jj][ii] = 1 + dp[jj-1][ii-1];
			 }
			 else{
				 dp[jj][ii] = max ( dp[jj-1][ii], dp[jj][ii-1] );
		   }
			 //cout << '('<<ii<<','<<jj<<')'<<dp[jj][ii]<<endl;
		 }

	}
	cout << dp[xn][yn]<<endl;
	}


}


int main(){
solve();
}

Measured memory_bytes: 5124
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> P;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef __gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;
string str;
int n,k;
vector<string> v;
int main()
{
    cin>>str;
    n=str.size();
    scanf("%d",&k);
    for(int i=0;i<n;i++)
        for(int j=1;i+j-1<n&&j<=k;j++)
            v.push_back(str.substr(i,j));
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    cout<<v[k-1]<<endl;
    return 0;
}



Measured memory_bytes: 1660
package main

import (
	"fmt"
)

func main() {
	var A, B, C, D int
	fmt.Scanf("%d", &A)
	fmt.Scanf("%d", &B)
	fmt.Scanf("%d", &C)
	fmt.Scanf("%d", &D)
	fmt.Printf("%d\n", map[bool]int{true: A, false: B}[A < B] + map[bool]int{true: C, false: D}[C < D])
	return
}


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

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

using namespace std;
using ll = long long;
using P = pair<int, int>;

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 = 1e9;
const ll LINF = 1e18;
const int MOD = 998244353;

ll modpow( ll x, ll n ){
    if( n == 0 ){
        return 1;
    }else if( n % 2 == 0 ){
        ll h = modpow( x, n / 2 );
        return h * h % MOD;
    }else{
        return x * modpow( x, n - 1 ) % MOD;
    }
}

int cnt[100010];

int main(){
    int N; cin >> N;
    vector<int> d( N );
    REP( i, N ){
        cin >> d[i];
        cnt[d[i]]++;
    }

    if( d[0] != 0 ){
        cout << 0 << endl;
        return 0;
    }

    if( N == 1 ){
        cout << 1 << endl;
        return 0;
    }

    

    int t1 = -1, t2;
    for( int i = 1; i < 100010; i++ ){
        if( cnt[i] == 0 && t1 == -1 ) t1 = i - 1;
        if( cnt[i] >= 1 ) t2 = i;

        if( i < N && d[i] == 0 ){
            cout << 0 << endl;
            return 0;
        }
    }

    if( t1 != t2 ){
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;
    for( int i = 2; i < 100010; i++ ){
        ans *= modpow( cnt[i - 1], cnt[i] );
        ans %= MOD;
    }

    cout << ans << endl;
}

/*


*/


Measured memory_bytes: 1024
package main

import "fmt"

func main() {
	var n, m, l int
	fmt.Scan(&n, &m, &l)
	a := make([]int, n*m)
	b := make([]int, m*l)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scan(&a[i*m+j])
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < l; j++ {
			fmt.Scan(&b[i*l+j])
		}
	}
	c := make([]int, n*l)
	for i := 0; i < n; i++ {
		for j := 0; j < l; j++ {
			cij := 0
			for k := 0; k < m; k++ {
				cij += a[i*m+k] * b[k*l+j]
			}
			c[i*l+j] = cij
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < l; j++ {
			if j > 0 {
				fmt.Printf(" ")
			}
			fmt.Printf("%d", c[i*l+j])
		}
		fmt.Printf("\n")
	}
}



Measured memory_bytes: 2516
#include <cstdio>
#include <vector>
#include <cmath>
#include <complex>
#include <algorithm>
using namespace std;

const double EPS = 1e-9;

typedef struct
{
  double x, y;
}Point;

int main()
{
  int N;
  while (~scanf("%d", &N)) {
    if (N == 0)
      break;

    Point c;
    vector<Point> p(N);
    for (int i = 0; i < N; ++i)
      scanf("%lf %lf", &p[i].x, &p[i].y);

    int ans = 1;
    for (int i = 0; i < N; ++i) {
      for (int j = i+1; j < N; ++j) {
	double H = hypot(p[i].x-p[j].x, p[i].y-p[j].y);
	if (H - 2.0 > EPS)
	  continue;
	double D = sqrt(1.0 - (H*H)/4.0);
	for (int pm = 0; pm < 2; ++pm) {
	  c.x = (p[i].x+p[j].x)/2.0 + (p[j].y-p[i].y)*D/H;
	  c.y = (p[i].y+p[j].y)/2.0 - (p[j].x-p[i].x)*D/H;
	  int cnt = 2;
	  for (int k = 0; k < N; ++k) {
	    if (k == i || k == j)
	      continue;
	    if ((c.x-p[k].x)*(c.x-p[k].x)+(c.y-p[k].y)*(c.y-p[k].y)-1.0 <= EPS)
	      ++cnt;
	  }
	  ans = max(ans, cnt);
	  D *= -1.0;
	}
     }
    }
    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
 
int main() {
	int n;
	cin >> n;
	string a,b;
	cin >> a;
  	a+=a[0];
	for ( int j = 0 ; j < 4 ; j++ ) {
		b.clear();
		if ( j == 0 ) b += 'S', b += 'S';
		if ( j == 1 ) b += 'S', b += 'W';
		if ( j == 2 ) b += 'W', b += 'S';
		if ( j == 3 ) b += 'W', b += 'W';  
		for ( int i = 2 ; i <= n + 1 ; i++ ) {
			if ( a[i-1] == 'o' ) {
				if ( b[i-1] == 'S') {
					if ( b[i-2] == 'W') b += 'W';
					else b += 'S';
				} 
				else {
					if (b[i-2] == 'W') b += 'S';
					else b += 'W'; 
				}
			}
			else {
				if ( b[i-1] == 'W') {
					if ( b[i-2] == 'W') b += 'W';
					else b += 'S';
				} 
				else {
					if (b[i-2] == 'W') b += 'S';
					else b += 'W'; 
				}
			}
		}
		if ( b[n] == b[0] && b[n+1] == b[1]) {
				cout << b.substr(0,n);
				return 0;
        }
	}
	cout << -1;
}

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

int main(){
  int r,g,b;
  cin >> r >> g >> b;
  
  int x = 100*r+10*g+b;
  
  if(x % 4 == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
using namespace std;
main(){
  int n,m,a,b,c,d;;
  cin>>n>>m;
  int di[n][n];
  r(i,n)r(j,n)di[i][j]=(i==j)?0:INF;
  while(m--){
    scanf("%d,%d,%d,%d",&a,&b,&c,&d);
    a--;b--;
    di[a][b]=c;
    di[b][a]=d;
  }
  r(k,n)r(i,n)r(j,n)di[i][j]=min(di[i][j],di[i][k]+di[k][j]);
  scanf("%d,%d,%d,%d",&a,&b,&c,&d);a--;b--;
  cout<<c-d-di[a][b]-di[b][a]<<endl;
}

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

using namespace std;

const int N = 1e5 + 10;

int n , x;
int num[N];

int main ( void ) {
	scanf ( "%d%d" , &n , &x );
	for ( int i = 1 ; i <= n ; i++ )  {
		scanf ( "%d" , &num[i] );
		num[i] -= x;
	}
	int ans = abs ( num[1] );
	for ( int i = 1 ; i <= n ; i++ ) 
		ans = __gcd ( ans , abs ( num[i] ) );
	printf ( "%d\n" , ans );
	return 0;
}

Measured memory_bytes: 640
// Author : Sarthak Kapoor
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define pi pair<int,int> 
#define pii pair<pi,int>
#define ull unsigned long long
#define vi vector<int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll fastexp(ll x,ll a){
    ll res = 1;
    while(a>0){
        if(a&1){
            res = (res*x)%mod;
        }
        a=a>>1;
        x=(x*x)%mod;
    }
    return res;
}
ll inverse(ll n){
    return fastexp(n,mod-2);
}
template <typename T>
void add(T &a, T b){
	a += b;
	if(a >= mod)a -= mod;
}
template <typename T>
void sub(T &a, T b){
	a -= b;
	if(a < 0)a += mod;
}
template <typename T>
void mul(T &a, T b){
	a *= b;
	if(a >= mod)a %= mod;
}
const int maxn =  1001;
vi v[maxn];
vi g[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	rep(i,m){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		g[b].pb(a);
		// v[b].pb(a);
	}
	int ans = 1e9;
	int pos = -1;
	repa(i,1,n+1){
		queue<int> q;
		q.push(i);
		int inf = 1e9;
		vi d(n+1,inf);
		d[i] = 0;
		std::vector<bool> vis(n+1,0);
		while(!q.empty()){
			int u = q.front();
			q.pop();
			vis[u] = 1;
			for(auto x:v[u]){
				if(!vis[x]){
					vis[x] = 1;
					q.push(x);
					d[x] = d[u]+1;
				}
			}
		}
		int temp = 1e9;
		for(auto x:g[i]){
			temp = min(temp,1+d[x]);
		}
		// cout<<temp<<"\n";
		if(temp < ans){
			ans = temp;
			pos = i;
		}
	}
	if(pos == -1){
		cout<<-1;
		return 0;
	}
	queue<int> q;
	q.push(pos);
	int inf = 1e9;
	vi d(n+1,inf);
	d[pos] = 0;
	std::vector<bool> vis(n+1,0);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 1;
		for(auto x:v[u]){
			if(!vis[x]){
				vis[x] = 1;
				q.push(x);
				d[x] = d[u]+1;
			}
		}
	}
	cout<<ans<<"\n";
	for(auto x:g[pos]){
		if(d[x] + 1 == ans){
			while(x != pos){
				cout<<x<<"\n";
				for(auto y:g[x]){
					if(d[y] == d[x] - 1){
						x = y;
						break;
					}
				}
			}
			cout<<pos<<"\n";
			return 0;
		}
	}
	return 0;
}

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

int main() {
  string S, T;
  cin >> S >> T;
  int N, M;
  N = S.size();
  M = T.size();
  int P = 1;
  if (N != M - 1)
    cout << "No" << endl;
  for (int i = 0; i < N; i++) {
    if (S.at(i) != T.at(i))
      P *= 0;
    else if (S.at(i) == T.at(i)) 
      P *= 1;
  }
    if (P == 1)
      cout << "Yes" << endl;
    else if (P == 0)
      cout << "No" << endl;
}


Measured memory_bytes: 3596
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int l, a, b, c, d;
	cin >> l >> a >> b >> c >> d;
	int m, n;
	m = a / c;
	n = b / d;
	if (a%c != 0){
		m += 1;
	}
	if (b%d != 0) {
		n += 1;
	}
	cout << l - max(m, n) << endl;
	char k;
	cin >> k;
}

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

int main(){
    int N;cin >> N;
    vector<double> p(N+1);
    rep(i,N)cin >> p[i];
    vector<vector<double>> dp(N+1,vector<double>(N+1,0));
    dp[0][0] = 1.0;

    rep(i,N) rep(j,N){
        dp[i+1][j+1] += dp[i][j] * p[i];
        dp[i+1][j] += dp[i][j] * (1.0-p[i]);
    }

    double ans = 0.0;
    for(int j = (N+1)/2;j<=N;++j)ans += dp[N][j];
    cout << fixed << setprecision(10) << ans << endl;
}



Measured memory_bytes: 70784
#include<cstdio>

typedef long long int lli;

lli dp[1<<17][5];

lli sq(lli x) {
    return x*x;
}

int main(void) {
    dp[0][0]=1;
    for(lli x=1; sq(x)<1<<16; x++)
        for(int i=0; i+sq(x)<1<<16; i++)
            for(int j=0; j<4; j++)
                dp[sq(x)+i][j+1] += dp[i][j];

    while(1) {
        int n;
        scanf("%d",&n);
        if(!n) break;
        printf("%lld\n",dp[n][1]+dp[n][2]+dp[n][3]+dp[n][4]);
    }
    return 0;
}

Measured memory_bytes: 5120
n = int(input())
xyh = []
for i in range(n):
    x, y, h = [int(i) for i in input().split()]
    xyh.append((x, y, h))

xyh.sort(key=lambda x: x[2], reverse=True)

for i in range(101):
    for j in range(101):
        x, y, h = xyh[0]
        H = h + abs(i - x) + abs(j - y)
        for x, y, h in xyh[1:]:
            if h != max(H - abs(i - x) - abs(j - y), 0):
                break
        else:
            ans = i, j, H
print(*ans)


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A, B, C):
    A.sort()
    B.sort()
    C.sort()

    ans = 0
    for b in B:
        i = bisect.bisect_left(A, b)
        j = N - bisect.bisect_right(C, b)
        ans += i * j
    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    C = read_int_n()
    print(slv(N, A, B, C))


if __name__ == '__main__':
    main()


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

int main()
{
int n,k,q;
cin>>n>>k>>q;
int a[n+2];
memset(a,0,sizeof(a));
for(int i=0;i<q;i++)
{
    int x;
    cin>>x;
    a[x]++;

}
for(int i=1;i<=n;i++)
{
    if(a[i]-q+k>0)
    cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
return 0;
}
 


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

int main() {
  string s;
  cin >> s;
  int A=200001;
  int Z;
  int N=s.size();
  for(int i=0;i<N;i++){
    if(s.at(i)=='A'&& i<A) A=i;
    if(s.at(i)=='Z') Z=i;
  }
  cout << Z-A+1 << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>

using namespace std;

/********** TEMPLATE STARTS HERE ***********/

#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define PI 3.1415926535897932384626433832795
#define gcd __gcd 

typedef unsigned long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pll> vll;
typedef vector <pii> vii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

/*********** TEMPLATE ENDS HERE *************/

const int DIM = 120;

int v[DIM];

main()
{
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		cin >> v[i];
	
	sort(v + 1, v + 1 + n);
	
	int sum = 0;
	
	int k = 1;
	
	for(int i = n; i >= 1; i--, k *= -1)
		sum += v[i] * k;
	
	cout << sum;
}

Measured memory_bytes: 256