akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8
import sys
input = sys.stdin.readline

def f2(n, p):
    dp = [ 0.0 ] * (n + 1)
    dp[0] = 1.0
    # pprint.pprint(dp, width = 50)
    for i in range(n):
        dp_ = list(dp)
        pi_ = 1 - p[i]
        for j in range(n + 1):
            dp[j] = dp_[j - 1] * p[i] + dp_[j] * pi_
        # pprint.pprint(dp, width = 50)
    return(sum(dp[n // 2 + 1:]))

n = int(input()) # n: odd, 1 <= n <= 2999
p = list(map(float, input().split())) # 0 < pi[i] < 1
print(f2(n, p))


Measured memory_bytes: 3316
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include <cctype>
#include<math.h>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a < 10 && b < 10 && a>0 && b>0) {
		cout << a * b << endl;
	}
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 256
n, l = map(int, input().split())
a = 0
ap = []
abp = []
while a <= n-1:
    a += 1
    ap.append(l + a - 1)
    abp.append(abs(l + a - 1))
x = abp.index(min(abp))
ap.remove(ap[x])
print(sum(ap))


Measured memory_bytes: 3060
package main

import (
	"fmt"
)

var debug = false

func main() {
	var n, a, b int
	fmt.Scanf("%d %d %d", &n, &a, &b)
	res := GetAnswer(n, a, b)
	fmt.Printf("%v\n", res)
}

// GetAnswer ...
func GetAnswer(n, a, b int) int {
	prt("inputs: n:%d a:%d, b:%d", n, a, b)
	result := 0
	for i := 1; i <= n; i++ {
		prt("test for %d", i)
		digitList := []int{}
		digitList = parseDigit(i, digitList)
		prt("digitList %v", digitList)
		added := adder(digitList)
		if added >= a && added <= b {
			result += i
		}
	}
	prt("%v\n", result)
	return result
}

func adder(list []int) int {
	result := 0
	for _, i := range list {
		result += i
	}
	return result
}

func parseDigit(i int, list []int) []int {
	if i > 0 {
		return parseDigit(i/10, append(list, i%10))
	}
	return list
}

func prt(format string, inputs ...interface{}) {
	if debug {
		fmt.Printf(format+"\n", inputs...)
	}
}

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

int main()
{
    int a,b,sum=0, i=2;
    cin >> a >> b;
    if(a == b) {
        sum = a+b;
        cout << sum;
        return 0;
    }
    while(i--) {
        sum += max(a--,b--);

    }
    cout << sum;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x " = " << (x) << '\n';
#define P(x) cout << #x << '\n';    
#define int long long
typedef pair<int, int> pii;
const int mod = 1000000007;


int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(9);
	#ifdef LOCAL_DEFINE
		freopen("in.txt", "rt", stdin);
	#endif
	
	char ch;
	cin >> ch;
	cout << (char) (ch + 1) << '\n';
	
	
	return 0;
}






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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;


int main(void){
	string s;
	while(1){
		cin >> s;
		if(s=="#")
			break;
	
		bool dir[20];
		int n=0;
		
		for(int i=0;i<s.size();++i){
			if(s.substr(i,5)=="north")
				dir[n++]=true;
			if(s.substr(i,4)=="west")
				dir[n++]=false;
		}
		
		ll mol=dir[n-1] ? 0: 90*pow(2,n-1);
		ll den=pow(2,n-1);
		
		for(int i=n-2;i>=0;--i){
			if(dir[i])
				mol-=90*pow(2,i);
			else
				mol+=90*pow(2,i);
		}
		
		ll div=__gcd(mol,den);
		mol/=div;
		den/=div;
		
		if(mol==0||den==1)
			cout << mol << endl;
		else
			cout << mol << "/" << den << endl;
	}
	return 0;
}

Measured memory_bytes: 1244
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int N, M, Q;

int main()
{
	in >> N >> M >> Q;
	std::vector<int>L(M), R(M), p(Q), q(Q);
	std::vector<std::pair<int, int>>sec;
	std::vector<std::vector<int>>imos(N + 1, std::vector<int>(N + 1, 0));
	rep(i, M)
	{
		in >> L[i] >> R[i];
		imos[L[i]][R[i]]++;
	}
	rep(i, Q)
	{
		in >> p[i] >> q[i];
		sec.push_back(std::make_pair(p[i], q[i]));
	}
	for (int i = 1; i <= N; ++i) for (int j = 1; j < N; ++j) imos[i][j + 1] += imos[i][j];
	for (int i = 1; i < N; ++i) for (int j = 1; j <= N; ++j) imos[i + 1][j] += imos[i][j];
	for (auto s : sec) out << imos[s.second][s.second] - imos[s.first - 1][s.second] - imos[s.second][s.first - 1] + imos[s.first - 1][s.first - 1] << std::endl;
	return 0;
}


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

int main() {
    int n, m, a, b;
    cin >> n >> m;
    vector<vector<int>> way(n + 1, vector<int>(0));
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        way.at(a).push_back(b);
        way.at(b).push_back(a);
    }

    queue<int> q;
    q.push(1);

    vector<int> dis(n + 1, -1), guide(n + 1);
    dis.at(1) = 0;

    int r;
    while(!q.empty()) {
        r = q.front();
        for (int i = 0; i < way.at(r).size(); i++) {
            if (dis.at(way.at(r).at(i)) == -1) {
                dis.at(way.at(r).at(i)) = dis.at(r) + 1;
                guide.at(way.at(r).at(i)) = r;
                q.push(way.at(r).at(i));
            }
            else {
                if (dis.at(r) + 1 >= dis.at(way.at(r).at(i))) continue;
                else {
                    dis.at(way.at(r).at(i)) = dis.at(r) + 1;
                    guide.at(way.at(r).at(i)) = r;
                    q.push(way.at(r).at(i));
                }
            }
        }
        q.pop();
    }
    bool tf = true;
    for (int i = 2; i <= n; i++) {
        if(dis.at(guide.at(i)) == dis.at(i) - 1) continue;
        else {
            tf = false;
            break;
        }
    }
    if (!tf) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        for (int i = 2; i <= n; i++) cout << guide.at(i) << endl;
    }
}

Measured memory_bytes: 10676
import * as fs from "fs";
const lines = fs.readFileSync("/dev/stdin", "utf8").split("\n");
const [X, N] = lines[0].split(" ").map(Number);
const p = lines[1].split(" ").map(Number);
//console.log(X);
//console.log(N);
const allowed = [];
for (let i = 0; i <= 101; i++) {
    if (!p.includes(i)) {
        allowed.push(i);
    }
}

const allowed_diffs: number[][] = allowed.map(i => [i, Math.abs(X - i)])
let min = allowed_diffs[0];
//console.log(min);
for (let diff of allowed_diffs) {
    if (diff[1] < min[1]) {
        min = diff;
    }
}
console.log(min[0]);


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

#pragma GCC diagnostic warning "-Wconversion"

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(a) begin(a), end(a)
#define has(a, b) (a.find(b) != a.end())
#define fora(i, n) for(int i = 0; i < n; i++)
#define forb(i, n) for(int i = 1; i <= n; i++)
#define forc(a, b) for(const auto &a : b)
#define ford(i, n) for(int i = n; i >= 0; i--)
#define maxval(t) numeric_limits<t>::max()
#define minval(t) numeric_limits<t>::min()
#define imin(a, b) a = min(a, b)
#define imax(a, b) a = max(a, b)

#define dbgs(x) #x << " = " << x
#define dbgs2(x, y) dbgs(x) << ", " << dbgs(y)
#define dbgs3(x, y, z) dbgs2(x, y) << ", " << dbgs(z)
#define dbgs4(w, x, y, z) dbgs3(w, x, y) << ", " << dbgs(z)

using ll = long long;

vector<int> succ[200007];

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

        int n, M;
        cin >> n >> M;

        fora(i, M)
        {
                int a, b;
                cin >> a >> b;
                --a; --b;
                if (a == 0 || b == n - 1)
                        succ[a].pb(b);
        }

        forc(q, succ[0])
        {
                if (succ[q].size() == 1)
                {
                        cout << "POSSIBLE\n";
                        return 0;
                }
        }
        cout << "IMPOSSIBLE\n";
}


Measured memory_bytes: 8440
R, G, B, N = map(int, input().split())

count = 0
tmp1 = N + R
for i in range(N // R + 1):
    tmp1 -= R
    tmp2 = tmp1 + G
    for j in range(N // G + 1):
        tmp2 -= G
        if tmp2 < 0:
            continue
        if tmp2 % B == 0:
            count += 1

print(count)

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


int main(void){
  ll n; cin >> n;
  ll x = 1;
  while(x*x < n){
    x++;
  }
  ll y=1;
  ll mx;
  while(y <= x){
    if(n%y == 0){
      mx = y;
    }
    y++;
  }
  ll mx2 = n/mx;
  cout << mx + mx2 -2<< endl;
  return 0;
}


Measured memory_bytes: 256
//============================================================================
// Name        : AOJ.cpp
// Author      : Akari Fujii
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>
#include<algorithm>

using namespace std;
typedef long long ll;
int main(){

	ll n,e=0;

	cin>>n;

	if(n%10==0){
		n=n/2;
		for(int j=1; j<6; ++j){
			e+=n%10;
			n=n/10;
		}
		e=e*2;

	}else{
		for(int j=1; j<6; ++j){
			e+=n%10;
			n=n/10;
		}
	}


	cout<<e<<endl;


	return 0;
}


Measured memory_bytes: 256
A = list(input())
B = list(input())
C = list(input())

def turn(L,N):
    if len(L) > 0:
        temp = L.pop(0)
        if temp == 'a':
            turn (A,'A')
        elif temp == 'b':
            turn (B,'B')
        else:
            turn (C,'C')
    else:
        print(N)

turn(A,'A')


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=998244353;
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)

int main(void){
    int n,m;
    cin>>n>>m;
    Graph G(m);
    rep(i,m){
        int k;
        cin>>k;
        rep(j,k){
            int s;
            cin>>s;
            s--;
            G[i].push_back(s);
        }
    }
    vector<int> P(m);
    rep(i,m) cin>>P[i];
    int ans=0;
    rep(bit,(1<<n)){
        int sum=0;
        rep(i,m){
            int temp=0;
            for(auto j:G[i]){
                if(bit&(1<<j)) temp++;
            }
            if(temp%2==P[i]) sum++;
        }
        //cout<<bit<<" "<<sum<<endl;
        if(sum==m) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)

int main(void){
    #define int long long
    int n, a, b;
    cin >> n >> a >> b;
    const int ab = a + b;
    const int t = n / ab;
    int m = n % ab;
    int ans = t * a;
    ans += min(a, m);
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class program{

  static void Main(){
    string[] s=Console.ReadLine().Split(' ');
    int A = int.Parse(s[0]);
    int B = int.Parse(s[1]);
    
    if(B%A==0){
      Console.WriteLine(A+B);
    }else{
      Console.WriteLine(B-A);
    }
  }
}


Measured memory_bytes: 11092
s = input()

a = -1
b = -1

for i in range(len(s)-2):
    if s[i]==s[i+1]:
        a = i+1
        b = i+2
        break
    elif s[i]==s[i+2]:
        a = i+1
        b = i+3
        break
if s[-2]==s[-1]:
    a = len(s)-1
    b = len(s)
        
print(str(a)+" "+str(b))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int N;cin>>N;
    cout<<N/2+N%2<<endl;
}

Measured memory_bytes: 3552
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
class ans
{
public:
    int a,i;
};
vector<int> cn[10001];
int chk[10001],now=1;
ans num[10001];
int dfs(int n)
{
    if(chk[n]>0) return 0;
    int tmp=cn[n].size();
    for(int i=0;i<tmp;i++)
    {
        dfs(cn[n][i]);
    }
    chk[n]=now++;
    return 0;
}
bool cmp(ans a,ans b)
{
    return a.i>b.i;
}
int main()
{
    int v,e,x,y;
    scanf("%d%d",&v,&e);
    for(int i=0; i<=v; i++)
    {
        num[i].a=i;
    }
    for(int i=0; i<e; i++)
    {
        scanf("%d%d",&x,&y);
        cn[x].push_back(y);
    }
    for(int i=0; i<v; i++)
    {
        if(chk[i]==0)
        {
            dfs(i);
        }
    }
    for(int i=0; i<v; i++) num[i].i=chk[i];
    sort(num,num+v,cmp);
    for(int i=0; i<v; i++) printf("%d\n",num[i].a);
    return 0;
}

Measured memory_bytes: 1800
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v(20);
vector<int> c(20);
int dfs(int num, int score){
  if(num==n)return score;
  return max(dfs(num+1, score + v.at(num) - c.at(num)), dfs(num+1, score));
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>v.at(i);
  for(int i=0;i<n;i++)cin>>c.at(i);
  cout << dfs(0, 0) << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
main(){
	int f=1,i;
	string s;
	for(cin>>s;f;)for(f=0,i=1;i<s.size()-3;i++)if(s.substr(i,3)=="mew")s.replace(i,3,""),f=1;
	cout<<(s=="mew"?"Cat":"Rabbit")<<endl;
}

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

namespace TYC
{
	const int N = 2e5 + 5;

	int n, M, A[N], B[N], now;

	bool check(const int mid)
	{
		now = 0;
		memcpy(B, A, sizeof(int[n + 1]));
		for (int i = n - mid + 1; i <= n; i++)
			B[i] = A[i] - M;
		sort(B + 1, B + 1 + n);
		for (int i = 1; i <= (n >> 1); i++)
			if (B[i] + B[n - i + 1] < 0)
				return false;
			else
				now = max(now, B[i] + B[n - i + 1]);
		return true;
	}

	void work()
	{
		scanf("%d%d", &n, &M);
		n <<= 1;
		for (int i = 1; i <= n; i++)
			scanf("%d", &A[i]);
		sort(A + 1, A + 1 + n);
		int l = 0, r = n, mid, ans = 0;
		while (l <= r)
		{
			mid = (l + r) >> 1;
			if (check(mid))
				ans = mid, l = mid + 1;
			else
				r = mid - 1;
		}
		check(ans);
		printf("%d\n", now);
	}
}

int main()
{
	TYC::work();
	return 0;
}

Measured memory_bytes: 1792
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;

#define MP make_pair
#define fastIO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//for gcc (未test)
// #define FOREACH_IT(it,c) for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
int INPUT_INT() {int d;cin>>d;return d;} // 入力をpush_back(d)やarray[d]に使う時に無駄な変数を使わない

// ------------------- include, typedef, define END. -------------------

void solveAndOutput(MuMAPIC &result){
	foreach_it(MuMAPIC, it, result){
		cout << (*it).second << endl;
	}
}

int main(){
	/* 方針
	 * A:381 , B:370 , C:40 , ...
	 * 百の位は勝ち数, 十の位は(9-負け数), 一の位は引き分け数.
	 * 入力チーム数が10以下（= 繰り上がり繰り下がりがないこと）を前提としている.
	 *
	 * また, 勝ち, 負け以外に引き分けしかない(無効試合とかない)ことを前提に, 引き分け数も計算に入れた.
	 */
	// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1167731
	// このコードは、↑のコードを、ビット演算使用してみたversionに書き換えたものである.

	int n = 0;
	char in_char;
	while (cin >> n, n){
		MuMAPIC result;

		// 各team入力
		FOR(teamSum, 0, n){
			// seisekiCount[0] = win, [1]=lose, [2]=hikiwake
			VI seisekiCount(3, 0);
			int temp_mapin = 0;

			cin >> in_char;
			FOR(i, 0, n - 1)
				seisekiCount[INPUT_INT()]++;

			//temp_mapin = seisekiCount[0] * 100 + (9 - seisekiCount[1]) * 10 + seisekiCount[2];
			FOR(i, 0, seisekiCount.size()){
				if (i == 1)
					temp_mapin += 9 - seisekiCount[i];
				else
					temp_mapin += seisekiCount[i];
				// 最大で+9される.つまり+1001される.よってずらす分は4bit以上.
				temp_mapin <<= 4;
			}
			result.insert(MP(temp_mapin, in_char));
		}
		// all teams input END.
		solveAndOutput(result);
	}
	return 0;
}

Measured memory_bytes: 1188
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

  int ans = 0;
  for (int i = 0; i < q; i++) {
    auto it = lower_bound(s.begin(), s.end(), t[i]);
    if (it != s.end() && *it == t[i]) {
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}



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

//#define int long long
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
//const int MOD = 1e9 + 7;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))

vector<vector<int>> graph;
vector<int> d(100, -1), f(100,-1);
vector<bool> visited(100, false);

int dfs(int n, int t){
    d[n] = ++t;
    visited[n] = true;
    for(int to : graph[n]){
        if(visited[to]) continue;
        t = dfs(to, t);
    }
    f[n] = ++t;
    return t;
}

signed main(){
    int n; cin >> n;
    graph.resize(n);
    
    rep(i,n){
        int u, k;
        cin >> u >> k;
        graph[u-1] = vector<int>(k);
        rep(j,k){
            cin >> graph[u-1][j];
            graph[u-1][j]--;
        }
    }
    
    int t = 0;
    rep(i,n){
        if(!visited[i]) t = dfs(i,t);
    }
    rep(i,n){
        printf("%d %d %d\n", i+1, d[i], f[i]);
    }
}


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

from collections import deque

def getNeighbor(A, i):
    a = len(A)
    for k in range(2, a):
        M[i][A[k]-1] = 1

def bfs():
    u = q.popleft()
    c[u] = 1

    for v in range(n):
        if M[u][v] and c[v] == 0:
            q.append(v)
            d[v] = d[u] + 1
            c[v] = 1

    if q:
        bfs()

    return

    bfs()

q = deque([0])

n = int(input())
#color
c = [0] * n
d = [0] + [-1] * (n-1) #depth

M = [[0] * n for _ in range(n)]
t = 0

for i in range(n):
    A = list(map(int, input().split()))
    getNeighbor(A,i)

bfs()

for i in range(n):
    print(str(i+1), str(d[i]))




Measured memory_bytes: 6112
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

int a[1010][1010];
int toid(int i, int j) {
	if (i > j)return a[j][i];
	return a[i][j];
}

int len = -1;
vector<int>TopologicalSort(int n, vector<int>in, vector<int>e[]) {
	queue<pair<int, int>>q;
	for (int i = 0; i < n; i++)if (!in[i])q.push({ i,1 });
	vector<int>ret;
	while (q.size()) {
		auto p = q.front();
		len = max(len, p.second);
		q.pop();
		ret.pb(p.first);
		fore(x, e[p.first]) {
			in[x]--;
			if (!in[x])q.push({ x,p.second + 1 });
		}
	}
	return ret;
}

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

	int N;
	cin >> N;
	vector<int>edge[505050];
	int cnt = 0;
	for (int i = 0; i < N; i++)for (int j = i + 1; j < N; j++) {
		a[i][j] = cnt;
		cnt++;
	}
	int sz = N * (N - 1) / 2;

	vector<int>in(sz);
	for (int i = 0; i < N; i++) {
		int pre;
		for (int j = 0; j < N - 1; j++) {
			if (j == 0) {
				cin >> pre;
				pre--;
			}
			else {
				int temp;
				cin >> temp;
				temp--;
				edge[toid(i, pre)].pb(toid(i, temp));
				in[toid(i, temp)]++;
				pre = temp;
			}
		}
	}


	vector<int>ord = TopologicalSort(sz, in, edge);
	if (ord.size() != sz) {
		puts(-1);
		return 0;
	}
	puts(len);

	return 0;
}

Measured memory_bytes: 37752
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
using namespace std;

using ll = long long;

ll chart[234][234];
ll INF = 1234567890123456;
ll memo[456][234][234];
ll h, w;
ll dp(int d, int i, int j)
{
	if (i < 0 || i > d || j < 0 || j > d || d - i >= w || d - j >= w || i >= h || j >= h)return -INF;
	if (memo[d][i][j] != -1)return memo[d][i][j];
	ll score = chart[i][d - i];
	if (i != j)
	{
		score += chart[j][d - j];
	}
	ll ans = 0;
	for (int bit = 0; bit < 4; ++bit)
	{
		ans = max(ans, dp(d - 1, i - (bit % 2), j - (bit / 2)));
	}
	return memo[d][i][j] = ans + score;
}

int main(void)
{
	memset(memo, 0xff, sizeof(memo));
	scanf("%lld %lld", &h, &w);
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			scanf("%lld", &chart[i][j]);
		}
	}
	memo[0][0][0] = chart[0][0];
	printf("%lld\n", dp(h + w - 2, h - 1, h - 1));
	return 0;
}


Measured memory_bytes: 195840
#include<bits/stdc++.h>
using namespace std;
#define N 1111116

int n,a[3][N],f[2][N],ans[2];

void modify(int f[],int x){
	if (x>n) return;
	f[x]^=1;modify(f,x+(x&-x));
}

int query(int f[],int x){
	if (!x) return 0;
	return f[x]^query(f,x-(x&-x));
}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();
	for (int i=1;i<=n;i++) a[0][i]=read();
	for (int i=1;i<=n;i++) a[1][i]=read();
	for (int i=1;i<=n;i++) a[2][i]=read();
	for (int i=n;i>=1;i--)
		if (abs(a[1][i]-a[0][i])+abs(a[1][i]-a[2][i])!=2||i%2!=(a[1][i]+1)/3%2)
		{printf("No\n");return 0;}
		else {
			ans[i%2]^=query(f[i%2],(a[1][i]+1)/3);
			modify(f[i%2],(a[1][i]+1)/3);
			ans[(i%2)^1]^=(a[0][i]>a[2][i]);
		}
	printf((ans[0]%2==0&&ans[1]%2==0)?"Yes\n":"No\n");
	return 0;
}

Measured memory_bytes: 8832
nn, dd = list(map(int,input().split()))
arr = [list(map(int,input().split())) for l in range(nn)]

mycount = 0

for i in range(nn):
    mydist = (arr[i][0]**2+arr[i][1]**2)**0.5
    if mydist <= dd:
        mycount += 1

print(mycount)

Measured memory_bytes: 102976
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    int n, k; cin >> n >> k;
    vector<int> h(n);
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }

    vector<int> dp(n, INT_MAX);
 
    dp[0] = 0;

    dp[1] = abs(h[1] - h[0]);
    

    for(int i = 2; i < n; i++){
      for(int j = i - 1, jump = 0; j  >= 0 && jump < k; j--, jump++){
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
      }
    }
    cout << dp[n - 1];
    return 0;
}

Measured memory_bytes: 3980
import math
a,b,h,m=map(int,input().split(" "))

def angle(hour,mini):
	 h = (hour * 360) / 12 + (mini * 360) / (12 * 60)
	 m = (mini * 360) / (60)
	 angle = abs(h - m)
	 if (angle > 180):
	     angle=360-angle
	 return (angle*math.pi)/180
an=angle(h,m)
print(math.sqrt((a*a)+(b*b)-(2*a*b*(math.cos(an)))))

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

using namespace std;

const int INF = 1e9 + 5;

int main(){
    int n;
    scanf("%d",&n);
    vector<int> v(n);
    for(int& x: v) scanf("%d",&x);
    vector<int> dp(n,INF);
    dp[0] = 0;
    for(int i=0;i<n;++i){
        for(int j=i+1;j<=i+2;++j) {
            if(j < n) dp[j] = min(dp[j],dp[i]+abs(v[i]-v[j]));
        }
    }
    cout << dp[n-1] << '\n';
    return 0; 
}

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

typedef long long ll;

int main()
{
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);
    auto k = X / D;
    if(K <= k) cout << (X - K * D) << endl;
    else{
        if((K-k)%2 == 0) cout << abs(X - k * D) << endl;
        else             cout << abs(X - (k+1) * D) << endl;
    }

    return 0;
}

Measured memory_bytes: 3612
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

X,t = MI()
print(max(0,X-t))


Measured memory_bytes: 61456
#include "bits/stdc++.h"

typedef long long ll;
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n-2; ++i) {
        if (s[i]== 'A'&&s[i+1]== 'B'&&s[i+2]== 'C') ans++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto K = readln.chomp.to!long;
    long s;
    foreach (a; 1..K+1) foreach (b; 1..K+1) {
        auto x = gcd(a, b);
        foreach (c; 1..K+1) s += gcd(c, x);
    }
    writeln(s);
}

Measured memory_bytes: 2680
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
use std::collections::HashMap;
fn main() {
    input!{
        n: usize,
        s: [chars; n],
    }
    let mut s = s;
    let mut h = HashMap::new();
    for i in &mut s {
        i.sort();
        *h.entry(i).or_insert(0) += 1;
    }
    println!("{}", h.into_iter().fold(0i64, |sum, (_, x)| sum + x * (x - 1) / 2));
}


Measured memory_bytes: 24828
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define REP(type,i,n) for(type i=0;i<(n);++i)
#define MP(a,b) make_pair((a),(b))
#define F_ first
#define S_ second

typedef long long int lli;
typedef pair<int,int> Pi;

const int INF=100000000;
const long long int INF_=1000000000000000000;

int main(){
	int D,X,Y;
	cin >> D >> X;
	vector<int> w,v;
	REP(int,i,X){
		char a;
		int p;
		cin >> a >> p;
		if(a=='D'){
			w.push_back(1);
			v.push_back(p);
		}
	}
	cin >> Y;
	REP(int,i,Y){
		string str;
		int p;
		cin >> str >> p;
		if(str[0]=='D'&&str[1]=='D'){
			w.push_back(2);
			v.push_back(p);
		}
	}
	vector<vector<int> > dp(v.size(),vector<int>(D+1));
	if(v.size()!=0) for(int i=w[0]; i<=D; ++i) dp[0][i]=v[0];
	REP(int,i,v.size()){
		REP(int,j,D+1){
			if(i==0) continue;
			if(j<w[i]) dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]));
		}
	}
	int ans=0;
	if(v.size()!=0) REP(int,i,D+1) ans=max(ans,dp[v.size()-1][i]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1228
#include <stdio.h>
int main(){
	int c1,c5,c10,c50,c100,c500;
	scanf("%d%d%d%d%d%d",&c1,&c5,&c10,&c50,&c100,&c500);
	if(1*c1+5*c5+10*c10+c50*50+c100*100+c500*500<1000){
		printf("0\n");
	}
	else printf("1\n");
        return 0;

}

Measured memory_bytes: 1804
package main

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

const (
	initialBufSize = 10000
	maxBufSize     = 1000000
)

var (
	sc *bufio.Scanner = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
		sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
	mod int = 1e9 + 7
)

func main() {
	C := getString()
	fmt.Println(string(C[0] + 1))
}

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func pow(p, q int) int {
	return int(math.Pow(float64(p), float64(q)))
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func strSearch(a []string, b string) bool {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func printIntArray(array []int) {
	strArray := fmt.Sprint(array)
	fmt.Println(strArray[1 : len(strArray) - 1])
}

func calcMod(x int) int {
	return x % mod
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    int n; cin >> n;
    vector<P> blue(n), red(n);
    rep(i,n){
    int a,b; cin >> a >> b;
    red[i] = P(a,b);
    }
    rep(i,n){
        int c,d; cin >> c >> d;
        blue[i] = P(c,d);
    }
    sort(blue.begin(), blue.end());
    sort(red.begin(), red.end(),
    [](auto const &a, auto const &b) -> bool{
        return a.second > b.second;
    });
    int res = 0;
    vector<bool> red_use(n, true);
    rep(i,n){
        rep(j,n){
            if(blue[i].first > red[j].first && blue[i].second > red[j].second && red_use[j]){
                res++;
                red_use[j] = false;
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <cmath>
#include <cstring>

using namespace std;

#define REPI(x) for(int i=0;i<x;i++)
#define REPJ(x) for(int j=0;j<x;j++)
#define SCANFD(x) scanf("%d",&x)

int main(){
    int A,B,K,i=0;
    
    scanf("%d %d %d",&A,&B,&K);
    int res =  A<B  ? A : B;
    
    while(1)
    {
        if(A%res==0 && B%res==0){
            i++;
            if(i==K)
                break;                
        }
        res--;
    }

    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define ll long long

using namespace std;

ll calc(string& s, int l, int r) {
	int now = l - 1;
	char c = s[l];
	int coun = 0;
	ll ans = 0;
	for (int i = l; i <= r; i++) {
		if (s[i] == c) {
			coun++;
			continue;
		}
		ans += coun / 2;
		coun = 1;
		c = s[i];
	}
	ans += coun / 2;
	return ans;
}

int main() {
	string s;
	cin >> s;
	ll k;
	cin >> k;
	int n = s.size();
	int L = 0, R = n - 1;
	while (L < n && s[L] == s[0])
		L++;
	L--;
	while (R >= 0 && s[R] == s[n - 1])
		R--;
	R++;
	if (L == n - 1) {
		ll val = k * n;
		val /= 2;
		cout << val << endl;
		return 0;
	}
	if (s[0] != s[n - 1] || k == 1) {
		ll val = calc(s, 0, n - 1);
		val *= k;
		cout << val << endl;
		return 0;
	}
	ll A = calc(s, 0, R - 1);
	ll B = calc(s, L + 1, n - 1);
	ll C = calc(s, L + 1, R - 1);
	ll D = ((n - R) + (L + 1)) / 2;
	C *= (k - 2);
	D *= (k - 1);
	cout << A + B + C + D << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}

int main (){
    int a,b,c;
    cin >> a >> b >>c;
    swap(a,b);
    swap(a,c);
    cout << a <<" "<< b <<" "<< c << endl;
    return 0;
}



Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

//Long Distance Taxi
public class Main{

	class E{
		int t, c;
		public E(int t, int c) {
			this.t = t;
			this.c = c;
		}
	}
	
	Map<String, Integer> ref;
	int ID, INF = 1<<29, M = 2001;
	int reg(String s){
		if(ref.containsKey(s))return ref.get(s);
		ref.put(s, ID);
		return ID++;
	}

	Set<E>[] adj;
	int[] d;
	boolean[] gas;
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		d = new int[6000*2001];
		adj = new Set[6000];
		gas = new boolean[6000];
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt(), cap = sc.nextInt();
			if((n|m|cap)==0)break;
			ref = new HashMap<String, Integer>();
			ID = 0;
			int S = reg(sc.next()), T = reg(sc.next());
			for(int i=0;i<6000;i++)adj[i]=new HashSet<E>();
			while(n--!=0){
				int s = reg(sc.next()), t = reg(sc.next()), D = sc.nextInt();
				adj[s].add(new E(t, D)); adj[t].add(new E(s, D));
			}
			Arrays.fill(gas, false);
			while(m--!=0)gas[reg(sc.next())]=true;
			for(int i=0;i<ID;i++)for(int j=0;j<=10*cap;j++)d[i*M+j]=INF;
			PriorityQueue<Integer> q = new PriorityQueue<Integer>(ID, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return d[o1]-d[o2];
				}
			});
			d[S*M+10*cap] = 0;
			q.add(S*M+10*cap);
			int res = -1;
			while(!q.isEmpty()){
				int v = q.poll();
				int p = v/M, c = v%M;
				if(p==T){
					res = d[v]; break;
				}
				for(E e:adj[p]){
					if(c-e.c<0)continue;
					int w = d[v]+e.c;
					if(gas[e.t]){
						if(w < d[e.t*M+10*cap]){
							d[e.t*M+10*cap] = w; q.add(e.t*M+10*cap);
						}
					}
					else{
						if(w < d[e.t*M+c-e.c]){
							d[e.t*M+c-e.c] = w; q.add(e.t*M+c-e.c);
						}
					}
				}
			}
			System.out.println(res==INF?-1:res);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int main(){

	double N,T,A,h[1010];
	double ondo;

	cin >> N;
	cin >>T>>A;

	int temp;

	double ans=100000;
	for(int i=0; i<N; i++){
		
		cin >> h[i];
		ondo = T-0.006*h[i];


		if(ans > abs(A-ondo)){

			ans=abs(A-ondo);
			temp=i;
		}
		

	}

	cout <<temp+1<<endl;


}

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

int main()
{
  unsigned long long int n,a,b;
  cin>>n>>a>>b;
  
  unsigned long long int m = n/(a+b) *a;
  n%=(a+b);
  
  m+=min(n,a);
  cout<<m;
  
  
  
  return 0;
}

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

#define ll long long



int main() {
    int  n ;
    char a[150] ;
    cin>>n;
    cin.get();
     cin>>a;
     if(n<strlen(a))
     {a[n]=0;

        strcat(a,"...");
        cout<<a;

     }
     else cout<<a;


}


Measured memory_bytes: 3616
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

// 累積演算 (0-indexed・prefix, suffix, 任意連続部分列)
// 任意連続部分列は逆演算があるときのみできる？

template <typename MonoidType>
struct Accumulation {
    int n;
    vector<MonoidType> val_array, pre, suf;
    MonoidType E;
    
    using MMtoM = function< MonoidType(MonoidType, MonoidType) >;
    MMtoM op, rop;

    void build(int m, vector<MonoidType> vec) {
        pre = suf = vector<MonoidType>(m+1, E);
        for(int i=0; i<m; i++) {
            pre[i+1] = op(pre[i], vec[i]);
        }
        for(int i=m-1; i>=0; i--) {
            suf[i] = op(suf[i+1], vec[i]);
        }
    }

    Accumulation() {}
    Accumulation(vector<MonoidType> val_array_, MonoidType E_,
                 MMtoM op_, MMtoM rop_ = MMtoM()) :
        val_array(val_array_), E(E_), op(op_), rop(rop_) {
        n = val_array_.size();
        build(n, val_array);
    }

    // [0, k)
    inline MonoidType get_prefix(int k) { return pre[k]; }
    // [k, n)
    inline MonoidType get_suffix(int k) { return suf[k]; }
    // [l, r) (rop が定義されてるときのみ)
    inline MonoidType get_subseq(int l, int r) {
        return rop(pre[r], pre[l]);
    }
};


int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

// Verified on Apr 28, 2019 (prefix, suffix のみ)
// Judge: https://atcoder.jp/contests/abc125/tasks/abc125_c
void ABC125_C() {
    int N; cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }
    
    Accumulation<int> acc(A, 0,
                          [](int a, int b) { return gcd(a, b); });

    int ans = 0;
    for(int i=0; i<N; i++) {
        int vl = acc.get_prefix(i), vr = acc.get_suffix(i+1);
        ans = max(ans, gcd(vl, vr));
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  
  bool a = S.at(0) == S.at(1);
  bool b = S.at(1) == S.at(2);
  bool c = S.at(2) == S.at(0);
  
  if(a && b && c){
    cout << "No" << endl;
  }
  
  else{
    cout << "Yes" << endl;
  }
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;


int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n,k;
  cin >> n >> k;
  int arr [n];
  for(int i = 0; i<n ;i++)
  {
    cin>> arr[i];
  }
  int ans[n];
  fill(ans , ans + n , INT_MAX);
  ans [0] = 0;
  ans [1] = abs(arr[0]-arr[1]);
  for(int i = 2;i<n;i++)
  {
     for(int j = i-1  ; j >= max(0,i-k) ; j--)
        ans[i]=min(ans[i],ans[j]+abs(arr[j]-arr[i]));
  }
  cout<< ans[n-1];


  return 0;
}


Measured memory_bytes: 1024
n = int(input())
x_lis = list(map(int, input().split()))
ans = 0
avg = sum(x_lis)/n
if avg - int(avg) >= 0.5:
    avg = int(avg) + 1
else:
    avg = int(avg)
for x in x_lis:
    ans += (x - avg)**2
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>

using namespace std;

#define N_MAX 20
#define M_MAX 100
#define INF 10000

struct Edge{

  Edge(int t,int c)
    :to_(t),cost_(c) {};

  int to_;
  int cost_;

};

vector<int> d(N_MAX);
vector<Edge> edge[M_MAX];

int s,g,V,P;

int dijkstra(int start,int goal){
  typedef pair<int,int> PII;
  priority_queue<PII,vector<PII>,greater<PII>> que;

  fill(d.begin(),d.end(),INF);
  d[start]=0;
  que.push(PII(start,0));

  while(!que.empty()){
    PII p=que.top();
    que.pop();
    int v=p.first;

    if(d[v]<p.second) continue;

    for(int i=0;i<edge[v].size();++i){
      Edge e=edge[v][i];
      if(d[e.to_]>d[v]+e.cost_){
	d[e.to_]=d[v]+e.cost_;
	que.push(PII(e.to_,d[e.to_]));
      }
    }
  }
  return d[goal];
}

int main(){
  int n,m,a,b,c,d;
  cin>>n;
  cin>>m;

  for(int i=0;i<m;++i){
    scanf("%d,%d,%d,%d",&a,&b,&c,&d);
    edge[a].push_back(Edge(b,c));
    edge[b].push_back(Edge(a,d));
  }

  scanf("%d,%d,%d,%d",&s,&g,&V,&P);

  V-=dijkstra(s,g);
  V-=dijkstra(g,s);

  cout<<V-P<<endl;

}

Measured memory_bytes: 3152
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> t(n);
    std::vector<int> x(n);
    std::vector<int> y(n);
    for(int i = 0; i < n; i++){
        std::cin >> t[i] >> x[i] >> y[i];
    }

    int cnt = 0;
    for(int i = 0; i < n; i++){
        int dist;
        int k;
        if(i == 0){
            dist = abs(x[0] + y[0]);
            k = t[0];
        }else{
            dist = abs((x[i] - x[i - 1]) + (y[i] - y[i - 1]));
            k = t[i] - t[i - 1];
        }
        //std::cout << "dist:" << dist << " k:"<< k << std::endl;
        if(k < dist){
            break;
        }else{
            if(k % 2 == 0 && dist % 2 == 0 || k % 2 == 1 && dist % 2 == 1){
                ++cnt;
            }else{
                break;
            }
        }
    }

    std::cout << (cnt == n ? "Yes" : "No") << std::endl;
    return 0;
}


Measured memory_bytes: 1408
N,D = gets.split.map(&:to_i)
X = readlines.map {|s| s.split.map(&:to_i) }
c = 0
X.combination(2) do |x|
  n = Math.sqrt(x.transpose.inject(0) {|r,(y,z)| r + (y-z)**2 })
  c += 1 if n.to_s.match(/\.0$/)
end
puts c

Measured memory_bytes: 1788
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [-1 for i in range(2**n)]
    dp[0] = 0

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [-1 for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==-1:
                continue
            new = dp[j]
            
            update = int(curk,2)|j
            
            #print(i,j,update,new,curc,curk,s)
            target = temp[update]
            if target==-1:
                temp[update] = new+curc
            elif target>new+curc:
                temp[update] = new+curc                
            if new<temp[j] or temp[j]==-1:
                temp[j] = dp[j]
        dp = temp
        #print(dp)
    print(dp[-1])
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Measured memory_bytes: 76512
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;

void solve(long long K, vector<long long> A){
    if (A.back() != 2) {
        std::cout << -1 << std::endl;
        return;
    }
    pair<long long, long long> ret = make_pair(2, 3);
    pair<long long, long long> tmp;
    for (int i = A.size() - 2; i >= 0; i--) {
        if (A[i] > ret.second) {
            std::cout << -1 << std::endl;
            return;
        }
        tmp.first = ((ret.first-1)/A[i] + 1)*A[i];
        tmp.second = (ret.second/A[i] + 1)*A[i] - 1;
        if (tmp.first > ret.second) {
            std::cout << -1 << std::endl;
            return;
        }
        if (tmp.second+1-A[i] < ret.first) {
            std::cout << -1 << std::endl;
            return;
        }
        ret.first = tmp.first;
        ret.second = tmp.second;
        if (ret.first > ret.second) {
            std::cout << -1 << std::endl;
            return;
        }
    }
    if (ret.first > ret.second) {
        std::cout << -1 << std::endl;
        return;
    }
    std::cout << ret.first << " " << ret.second << std::endl;
}

int main(){	
    struct timeval start,end;
    long long span;
    gettimeofday(&start,NULL);

    long long K;
    scanf("%lld",&K);
    vector<long long> A(K-1+1);
    for(int i = 0 ; i <= K-1 ; i++){
    	scanf("%lld",&A[i]);
    }
    solve(K, A);

    gettimeofday(&end,NULL);
    span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
    std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iostream>
using namespace std;

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

	string input;
	cin >> input;

	const int pos = input.find('i');
	string s = input.substr(0, pos);
	string t = input.substr(pos + 3);
	reverse(t.begin(), t.end());

	int mx = 0;

	function<bool(char, char)> match = [](char c1, char c2)
		{
			return c1 != c2 && abs(c1 - c2) <= 2;
		};

	function<void(int, int, int)> dfs = [&](int s_idx, int t_idx, int sum)
		{
			if(sum + min(s.size() - s_idx, t.size() - t_idx) <= mx) return;
			if(s_idx == s.size() || t_idx == t.size()) {
				mx = sum;
				return;
			}

			for(unsigned i = t_idx; i < t.size(); ++i) {
				if(match(s[s_idx], t[i])) {
					dfs(s_idx + 1, i + 1, sum + 1);
					break;
				}
			}
			dfs(s_idx + 1, t_idx, sum);
		};

	dfs(0, 0, 0);
	cout << 2 * mx + 3 << endl;

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1196
Q = int(input())
AB = [[int(i) for i in input().split()] for _ in range(Q)]
for a, b in AB :
    ret = 0
    sqrt = int((a * b) ** 0.5)
    ret += sqrt - 1
    ret += (a * b - 1) // sqrt - 1
    if a == b :
        ret += 1
    print(ret)

Measured memory_bytes: 38384
#include<stdio.h>

int main(){

        int n,x[100],sum1,sum2;

        sum1 = 0;
        sum2 = 0;

        scanf("%d",&n);


        for(int i = 0 ; i < n ; i++){
                scanf("%d",&x[i]);
                sum1 += x[i];
                sum2 += x[i]*x[i];
        }


        if( sum1%n == 0 )
                printf("%d\n",sum2-sum1*sum1/n);
        else {
                double p,diff;
                int P,ansP;

                p = (double)sum1/(double)n ;
                P = sum1/n ;
                diff = p - (double)P;

                if(diff > 0.5)
                        ansP = P+1;
                else
                        ansP = P;

                printf("%d\n",n*ansP*ansP-2*sum1*ansP+sum2);

        }


        return 0;
}


Measured memory_bytes: 1732
n,m = map(int,input().split())
s = input()
cnt = [0]*(n+1)
r = n
for i in range(n-1,-1,-1):
    if s[i] == '1':
        cnt[i] = -1
        continue
    while r > i+m:r -=1
    while cnt[r] == -1:r -= 1
    if i == r:
        print(-1)
        exit(0)
    cnt[i] =cnt[r]+1
now = 0
ans = []
for i in range(n+1):
    if cnt[i] == -1:continue
    if cnt[i] == cnt[now]-1:
        ans.append(i-now)
        now = i
print(*ans)
    
        
        
        
        
    

Measured memory_bytes: 50672