akhauriyash/Code-Regression huggingface dataset:
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let k: usize = itr.next().unwrap().parse().unwrap();
    // 任意の2点間の組み合わせ = n * (n - 1) / 2
    // 真ん中の1点と組む組み合わせ = n - 1
    // (n - 2) * (n - 1) / 2
    if k > (n - 2) * (n - 1) / 2 {
        println!("-1");
    } else {
        // まず k = (n - 2) * (n - 1) / 2の場合を作る
        let mut ans = Vec::new();
        for i in 2..n + 1 {
            ans.push((1, i));
        }
        let mut iranai = (n - 2) * (n - 1) / 2 - k;
        for i in 2..n + 1 {
            for j in i + 1..n + 1 {
                if iranai == 0 {
                    break;
                }
                ans.push((i, j));
                iranai -= 1;
            }
            if iranai == 0 {
                break;
            }
        }
        // output
        let mut out = Vec::new();
        writeln!(out, "{}", ans.len()).ok();
        for &(a, b) in ans.iter() {
            writeln!(out, "{} {}", a, b).ok();
        }
        stdout().write_all(&out).unwrap();
    }
}


Measured memory_bytes: 4352
using System;

namespace A___Harmony
{
    class Program
    {
        static void Main (string[] args)
        {
            var input = Console.ReadLine ().Split (' ');
            var a = int.Parse (input[0]);
            var b = int.Parse (input[1]);
            if ((a + b) % 2 == 0)
            {
                Console.WriteLine ((a + b) / 2);
            }
            else
            {
                Console.WriteLine ("IMPOSSIBLE");
            }
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, max_x = -100, min_y = 100;
int tmp;
int main()
{
    cin >> n >> m >> x >> y;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        max_x = max(tmp, max_x);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> tmp;
        min_y = min(tmp, min_y);
    }
    if (max_x < min_y && min_y > x && max_x < y)
        cout << "No War" << endl;
    else
        cout << "War" << endl;

    return 0;
}

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

// #define int long long

signed main(void)
{
  int num; // num
  num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  int n;
  array<int, 10> a;

  cin>> n;
  for(auto it = a.begin(); it < a.begin() + n; ++it){
    cin >> *it;
    num = max(num,*it);
  }

  num = - num/2;

  for (auto it = a.begin(); it < a.begin() + n; ++it)
    num += *it;

  cout << num << endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
int H, W;
string C[200];

int main() {
  cin >> H >> W;
  rep(i, 0, H) { cin >> C[i]; }

  repe(i, 0, 2 * (H - 1) + 1) {
    repe(j, 0, W - 1) { cout << C[i / 2][j]; }
    cout << "\n";
  }
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

ll n,k,ans=0;
int main(){
  cin >> n >> k;
  for(int b=1; b<=n; b++){
    ans += n/b*max(b-k,ll(0))+max(n%b+1-k,ll(0));
  }
  if(k==0){
    ans -= n;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
V = list(map(int, input().split()))
A = [] # 偶数
B = [] # 奇数

import collections

for i in range(n):
  if i % 2 == 0:
    A.append(V[i])
  else:
    B.append(V[i])

A = collections.Counter(A).most_common()[:2]
B = collections.Counter(B).most_common()[:2]
count = 0

if A[0][0] == B[0][0]:
  count += max(A[0][1], B[0][1])
  if A[0][1] == B[0][1]:
    if len(A) > 1 and len(B) > 1:
      count += max(A[1][1], B[1][1])
    elif len(A) > 1:
      count += max(A[1][1])
    elif len(B) > 1:
      count += max(B[1][1])
else:
  count += A[0][1] + B[0][1]

print(n-count)

Measured memory_bytes: 17272
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int INF = 1 << 22;
int main() {
    int n;
    while (cin >> n, n) {
        vector<int> x(n + 1), y(n + 1);
        for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
        x[n] = x[0], y[n] = y[0];
        int xmin = INF, xmax = -INF;
        int ymin = INF, ymax = -INF;
        for (int i = 0; i < 4; i++) {
            int a, b;
            cin >> a >> b;
            xmin = min(xmin, a);
            xmax = max(xmax, a);
            ymin = min(ymin, b);
            ymax = max(ymax, b);
        }
        int r1 = 0, r2 = 0;
        for (int i = 0; i < n; i++) {
            if (y[i] == y[i + 1]) {
                int x1 = x[i];
                int x2 = x[i + 1];
                int y1 = y[i];
                r2 += y1 * (x1 - x2);

                x1 = max(xmin, min(xmax, x1));
                x2 = max(xmin, min(xmax, x2));
                y1 = max(ymin, min(ymax, y1));
                r1 += y1 * (x1 - x2);
            }
        }
        cout << r2 - r1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3008
// DP & Fibonachi

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> oks(N+1, true);

    for(long long i = 0; i < M; ++i) {
        long long a;
        cin >> a;
        oks.at(a) = false;
    }

    vector<long long> dp(N+1);
    dp.at(0) = 1;
    for(long long now = 0; now < N; ++now) {
        for(long long next = now+1; next <= min(N, now+2); ++next) {
            if(oks.at(next)) {
                dp.at(next) += dp.at(now);
                dp.at(next) %= mod;
            }
        }
    }

    cout << dp.at(N) << endl;

}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long int 
using namespace std;
int main()
{
    ll i,j,k,n;
    cin>>n;
    k=n%10;
    if(k==3)
        cout<<"bon"<<endl;
    else if(k==0||k==1||k==6||k==8)
        cout<<"pon"<<endl;
    else
        cout<<"hon"<<endl;
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>

using namespace std;


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

	int n, i, j, k, nn;
	cin >> n;
	nn = 1 << n;

	vector<pair<int, int>> a(nn);
	for (i = 0; i < nn; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}

	vector<set<pair<int, int>>> s(nn);
	vector<int> ans(nn, 0);
	for (i = 0; i < nn; i++) {
		s[i].insert(a[i]);

		for (j = 0; j < n; j++) {
			if ((1 << j) & i) {
				for (auto p : s[i - (1 << j)]) s[i].insert(p);
			}
		}
		while (s[i].size() > 2) s[i].erase(s[i].begin());

		if (i > 0) {
			ans[i] = max(ans[i - 1], s[i].begin()->first + s[i].rbegin()->first);
			cout << ans[i] << "\n";
		}
	}



	return 0;
}


Measured memory_bytes: 37224
#include <iostream>
using namespace std;
long long gcd(long long a,long long b);
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    long long x,y,ans;
    cin>>x>>y;
    cout<<gcd(x,y)<<endl;
    return(0);
}
long long gcd(long long x,long long y){
    while(y!=0){
        long long r=x%y;
        x=y;
        y=r;
    }
    return(x);
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define sigma_size 30
#define max_size (int)(2e5+10)
#define MAX (int)(1e5+7)
int qread()
{
	char c; int s=0,t=1; while ((c=getchar())<'0' || c>'9') (c=='-' && (t=-1));
	do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*t;
}

int L[2005];
int main ()
{
	int n = qread();
	for ( int i = 1 ; i <= n ; i++ )
		cin >> L[i];
	sort ( L+1 , L+1+n );
	int cnt = 0;
	for ( int i = 1 ; i <= n ; i++ )
	{
		for ( int j = i+1 ; j <= n ; j++ )
		{
			int d = L[i] + L[j];
			int tot = lower_bound( L+1 , L+n+1 , d ) - L -1 ;
			cnt += tot-j;
			if ( d == L[tot] )	cnt--;
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,num=1,ans=0;
    cin>>n;
    while(n){
        n/=2;
        ans+=num;
        num*=2;
    }
    cout << ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int side1, side2, diagonal;
	int oblong, rhombus;

	oblong = rhombus = 0;
	while (scanf("%d,%d,%d", &side1, &side2, &diagonal) != EOF){
		if ((side1 * side1) + (side2 * side2) == (diagonal * diagonal)){
			oblong++;
		}
		else if (side1 == side2){
			rhombus++;
		}
	}

	printf("%d\n%d\n", oblong, rhombus);

	return (0);
}

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

int INF = 1001001001;

int main(){
  int n, m;
  cin >> n >> m;
  vvi to(n);
  rep(i,m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    to.at(a).push_back(b);
    to.at(b).push_back(a);
  }
  // rep(i,n){
  //   cout << i << " ";
  //   for (auto u : to.at(i)){
  //     cout << u << " ";
  //   }
  //   cout << endl;
  // }

  queue<int> q;
  vi dist(n, INF);
  vi pre(n, -1);
  dist.at(0) = 0;
  q.push(0);
  while (!q.empty()){
    int v = q.front(); q.pop();
    for (int u : to.at(v)){
      if (dist.at(u) != INF) continue;
      dist.at(u) = dist.at(v) + 1;
      pre.at(u) = v;
      q.push(u);
    }
  }

  cout << "Yes" << endl;
  rep(i,n){
    if (i == 0) continue;
    int ans = pre.at(i);
    ans++;
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 10748
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func stringToInt(ss []string) []int {
	var seq []int
	for _, s := range ss {
		i, _ := strconv.Atoi(s)
		seq = append(seq, i)
	}
	return seq

}

func input() (int, []int) {
	stdin := bufio.NewScanner(os.Stdin)
	stdin.Scan()
	nk := stdin.Text()
	nkSplit := strings.Split(nk, " ")
	k := nkSplit[1]
	kInt, _ := strconv.Atoi(k)
	stdin.Scan()
	p := stdin.Text()
	pSplit := strings.Split(p, " ")
	seq := stringToInt(pSplit)
	return kInt, seq
}

func main() {
	k, p := input()
	output := 0
	sort.Sort(sort.IntSlice(p))
	for i := 0; i < k; i++ {
		output += p[i]
	}
	fmt.Println(output)

}


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

int main(void){
    int n;
    cin>>n;
    vector<pair<int, int> > x(n);
    rep(i, n){
        int a, b;
        cin>>a>>b;
        x[i].first=a;x[i].second=b;
    }
    vector<vector<double> > d(n, vector<double>(n));
    rep(i, n)rep(j, n){
        d[i][j]=sqrt(pow(x[i].first-x[j].first, 2)+pow(x[i].second-x[j].second, 2));
        //cout<<i<<", "<<j<<", "<<d[i][j]<<endl;
    }
    vector<int> a(n);
    rep(i, n) a[i]=i;
    double ans=0;
    do{
        rep(j, n-1){
            //cout<<d[a[j]][a[j+1]]<<endl;
            ans+=d[a[j]][a[j+1]];
        }
        //rep(j, n) cout<<a[j]<<", ";
        //cout<<endl;
    }while(next_permutation(a.begin(), a.end()));
    int nkaijou=1;
    for(int i=1;i<=n;i++) nkaijou*=i;
    //cout<<"kaijou"<<nkaijou<<endl;
    ans/=(double)nkaijou;
    //cout<<ans<<endl;
    printf("%.10f", ans);
}

Measured memory_bytes: 256
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
a = sorted(map(int, input().split()))

factorialNumInverse = [None] * (n + 1)
naturalNumInverse = [None] * (n + 1)
fact = [None] * (n + 1)

def inverseofNumber():
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, n + 1):
        naturalNumInverse[i] = (naturalNumInverse[MOD % i] * (MOD - MOD // i) % MOD)

def inverseofFactorial():
    factorialNumInverse[0] = factorialNumInverse[1] = 1
    for i in range(2, n + 1):
        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % MOD

def factorial():
    fact[0] = 1
    for i in range(1, n + 1):
        fact[i] = (fact[i - 1] * i) % MOD

inverseofNumber()
inverseofFactorial()
factorial()

def nCk(n, k):
    ans = ((fact[n] * factorialNumInverse[k]) % MOD * factorialNumInverse[n - k]) % MOD
    return ans

def calcSum(a):
    ret = 0
    for i in range(k - 1, n):
        ret += (nCk(i, k - 1) * a[i]) % MOD
        ret %= MOD
    return ret

print((calcSum(a) - calcSum(a[::-1])) % MOD)

Measured memory_bytes: 19544
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
last = 0
cnt = 0
for ind,i in enumerate(A):
    lmon = max(i-last,0)
    if(ind<N):
        lpow = B[ind]
    else:
        lpow = 0
    cnt += min(last+lpow,i)
    last = max(lpow-lmon,0)
print(cnt)


Measured memory_bytes: 18468
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int N;
int A[200001];
int E[400001], ne[400001], he[200001];
int kotae[200001];
vector<int> V;

void dfs(int p, int mae) {

	int itr = lower_bound(V.begin(), V.end(), A[p]) - V.begin();
	if (itr == V.size()) {
		V.pb(A[p]);
		kotae[p] = V.size();
		for (auto to = he[p]; to; to = ne[to]) {
			if (E[to] != mae) {
				dfs(E[to], p);
			}
		}
		V.pop_back();
	}
	else {
		swap(V[itr], A[p]);
		kotae[p] = V.size();
		for (auto to = he[p]; to; to = ne[to]) {
			if (E[to] != mae) {
				dfs(E[to], p);
			}
		}
		V[itr] = A[p];
	}
}

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

	cin >> N;
	rep1(i, N) cin >> A[i];
	int k = 1;
	rep(i, N - 1) {
		int u, v;
		cin >> u >> v;
		E[k] = v;
		ne[k] = he[u];
		he[u] = k++;
		E[k] = u;
		ne[k] = he[v];
		he[v] = k++;
	}

	V.pb(2000000000);
	dfs(1, -1);

	rep1(i, N) co(kotae[i]);

	Would you please return 0;
}

Measured memory_bytes: 23340
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define vi vector<int>
#define nl endl
#define tc    \
    ll t;     \
    cin >> t; \
    while (t--)
#define fastio                       \
    ios_base::sync_with_stdio(NULL); \
    cin.tie(NULL);                   \
    cout.tie(NULL);
using namespace std;
int main()
{
    fastio;
    ll n, a, b;
    cin >> n >> a >> b;
    if(n==1&&a==b)
        cout<<"1";
    else if(n!=1&&a<=b)
        cout<<(n-2)*(b-a)+1;
    else cout<<"0";
}

Measured memory_bytes: 3640
import math
a, b, x = map(int, input().split())
h = x/a**2

if b == h:
    print(0)
    exit()
elif h >= b/2:
    tanth = a / (b - h) / 2
else:
    tanth = 2 * a * h / b**2

theta = math.degrees(math.atan(tanth))
print(90 - theta)


Measured memory_bytes: 38384
#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;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

ll ppow(ll a,ll b){
	a%=MOD;
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}
class Fact{
	vector<ll>fact;
	vector<ll>inv;
public:
	Fact(){}
	Fact(int n){
		n=n*2+10;
		fact=inv=vector<ll>(n);
		fact[0]=inv[0]=1;
		for(int i=1;i<n;i++){
			fact[i]=(fact[i-1]*i)%MOD;
		}
		inv[n-1]=ppow(fact[n-1],MOD-2);
		for(int i=n-2;i>=0;i--){
			inv[i]=(inv[i+1]*(i+1))%MOD;
		}
	}
	ll get(int n){
		return fact[n];
	}
	ll get_inv(int n){
		return inv[n];
	}
	ll nPr(int n,int r){
		return fact[n]*inv[n-r]%MOD;
	}
	ll nCr(int n,int r){
		return nPr(n,r)*inv[r]%MOD;
	}
	ll nrP(int n,int r){
		return nPr(n+r,n);
	}
	ll nrC(int n,int r){
		return nCr(n+r,n);
	}
};

ll sum[200000];
ll x[200000];
int main(){
	int n;cin>>n;
	rep(i,n)scanf("%lld",&x[i]);
	rep(i,n+1){
		sum[i+1]=sum[i]+ppow(i+1,MOD-2);
	}
	ll ans=0;
	rep(i,n-1){
		ll X=x[i+1]-x[i];
		(ans+=X*sum[i+1]%MOD)%=MOD;
	}
	Fact fac(n);
	cout<<ans*fac.get(n-1)%MOD<<endl;
}

Measured memory_bytes: 4992
S = input()
first = int(S[0:2])
second = int(S[2:])

if 1 <= first <= 12:
    # MMYY?
    if 1 <= second <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    # YYMM?
    if 1 <= second <= 12:
        print("YYMM")
    else:
        print("NA")


Measured memory_bytes: 2940
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
#define ds(q) scanf("%lld",&q)
ll ans[100];
int main()
{
    double x;
    ll n;
    ds(n);
    x=(n-n/2)/(double)n;
    printf("%.10lf",x);
    return 0;

}


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

typedef long long ll;

int main(){
    int n, res=0;
    ll h, w, a, b;
     scanf("%lld%lld%lld", &n, &h, &w);
     for(int i=1; i<=n; i++){
       scanf("%lld%lld", &a, &b);
       if(a>=h&&b>=w)
        res++;
     }
     printf("%d", res);
     return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

int main()
{ios_base::sync_with_stdio(false);
string s;
cin>>s;
sort(all(s));

if(s[0]==s[1]&&s[2]==s[3]&&s[0]!=s[2])
{
	ol("Yes");
}
else
{
	ol("No");
}

return 0;
}



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

#define INF 1e9
using namespace std;

int main() {

    int N; cin >> N;

    set<string> se;

    char back;

    for (int i = 0; i < N; ++i) {
        string w; cin >> w;

        if (i == 0) {
            back = w.front();
        }

        if (back != w.front()) {
            cout << "No" << endl;
            return 0;
        }

        if (se.count(w) == 1) {
            cout << "No" << endl;
            return 0;
        }

        back = w.back();
        se.insert(w);
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;
	vector<vector<long long>> list(3);
	vector<long long>& x = list[0];
	vector<long long>& y = list[1];
	vector<long long>& z = list[2];
	for (auto i = 0; i < N; ++i)
	{
		long long a, b, c;
		cin >> a >> b >> c;
		x.push_back(a);
		y.push_back(b);
		z.push_back(c);
	}

	auto result = 0ll;
	for (auto i = 0; i < 8; ++i)
	{
		vector<long long> tempList;

		for (auto k = 0; k < N; ++k)
		{
			auto num = 0ll;

			for (auto j = 0; j < 3; ++j)
			{
				if ((i & (1 << j)) != 0)
				{
					num += list[j][k];
				}
				else
				{
					num -= list[j][k];
				}

			}
			tempList.push_back(num);
		}

		sort(tempList.begin(), tempList.end(), greater<long long>());
		auto sum = 0ll;
		for (auto k = 0; k < M; ++k)
		{
			sum += tempList[k];
		}

		result = max(result, sum);
	}

	cout << result << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define PB push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
#define inI(x) scanf("%d",&x)
#define inI2(x,y) scanf("%d %d",&x,&y)
#define inI3(x,y,z) scanf("%d %d %d",&x,&y,&z)
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
int n,l,r,ch[100005];
bool p;
char c[100005];
int main()
{
    scanf("%d",&n);
    scanf("%s",c+1);
    for(ch[1]=0;ch[1]<2;ch[1]++)
    {
        for(ch[2]=0;ch[2]<2;ch[2]++)
        {
            for(int i=3;i<=n;i++)
            {
                if(ch[i-1]==1)
                {
                    if(c[i-1]=='x')
                    {
                        ch[i]=1-ch[i-2];
                    }
                    else
                    {
                        ch[i]=ch[i-2];
                    }
                }
                else
                {
                    if(c[i-1]=='x')
                    {
                        ch[i]=ch[i-2];
                    }
                    else
                    {
                        ch[i]=1-ch[i-2];
                    }
                }
            }
            if(ch[n]==1)
            {
                if(c[n]=='x')
                {
                    if(ch[1]+ch[n-1]==1)p=true;
                    else p=false;
                }
                else
                {
                    if(ch[1]==ch[n-1])p=true;
                    else p=false;
                }
            }
            else
            {
                if(c[n]=='x')
                {
                    if(ch[1]==ch[n-1])p=true;
                    else p=false;
                }
                else
                {
                    if(ch[1]+ch[n-1]==1)p=true;
                    else p=false;
                }
            }
            if(!p)continue;
            if(ch[1]==1)
            {
                if(c[1]=='x')
                {
                    if(ch[n]+ch[2]==1)p=true;
                    else p=false;
                }
                else
                {
                    if(ch[n]==ch[2])p=true;
                    else p=false;
                }
            }
            else
            {
                if(c[1]=='x')
                {
                    if(ch[n]==ch[2])p=true;
                    else p=false;
                }
                else
                {
                    if(ch[n]+ch[2]==1)p=true;
                    else p=false;
                }
            }
            if(!p)continue;
            for(int i=1;i<=n;i++)
            {
                if(ch[i]==1)printf("S");
                else printf("W");
            }
            return 0;
        }
    }
    printf("-1");
}


Measured memory_bytes: 768
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    N,M,K = map(int, readline().split())

    MOD = 998244353

    if M == 1:
        if K == N - 1:
            print(1)
        else:
            print(0)
        exit()
    
    prepare(N + 10, MOD)

    m = pow(M-1, N-1, MOD)
    m_inv = pow(M-1, MOD-2, MOD)
    ans = 0
    for k in range(K+1):
        ans += (cmb(N-1, k, MOD) * m) % MOD
        ans %= MOD

        m *= m_inv
        m %= MOD

    print(ans * M % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 32956
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

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

  ll n, a, b;
	cin >> n >> a >> b;
	if (n == 1) {
		if (a == b) cout << 1 << endl;
		else cout << 0 << endl;
	}
	else {
		if (a == b) cout << 1 << endl;
		else if (a > b) cout << 0 << endl;
		else {
			ll minsum = a * (n - 1) + b, maxsum = a + b * (n - 1);
			cout << maxsum - minsum + 1 << endl;
		}
	}
}


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

const int INF=250000005;

int main(){
  int n,C;
  cin>>n>>C;
  vector<vector<int>> d(C,vector<int>(C));
  rep(i,C)rep(j,C) cin>>d[i][j];
  vector<vector<int>> c(3,vector<int>(C));
  rep(i,n)rep(j,n){
    int x;
    cin>>x;
    x--;
    c[(i+j)%3][x]++;
  }
  int ans=INF;
  rep(i,C){
    rep(j,C){
      if(j==i) continue;
      rep(k,C){
        if(k==i||k==j) continue;
        int res=0;
        rep(p,C){
          res+=c[0][p]*d[p][i];
          res+=c[1][p]*d[p][j];
          res+=c[2][p]*d[p][k];
        }
        ans=min(ans,res);
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define F            first
#define S            second
#define PB           push_back
#define MP           make_pair
#define Fin          freopen("input.txt","r",stdin)
#define Fout         freopen("output.txt","w",stdout)
#define Precision(a) cout << fixed << setprecision(a)
#define FasterIO     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF9 2147483647
#define INF18 9223372036854775806
#define ll long long
#define ull unsigned long long
#define nn printf("\n")
#define no printf("NO\n")
#define yes printf("YES\n")
#define pp pair<int,int>
#define ppp pair<int,pp >
#define mapii map<int,int>
#define mapll map<ll,ll>
#define mapsi map<string,int>
#define mapss map<string,string>

char Uplowch(char ch)
{
    if(ch >= 'A' &&  ch <= 'Z')
        ch += 32;
    return ch;
}
char Lowupch(char ch)
{
    if(ch >= 'a' &&  ch <= 'z')
        ch -= 32;
    return ch;
}

int ara[111];
int ara2[111];
vector<int>v;
int main()
{
    ll t,n,m,a,b,i,j,x,y,mx,mn,sum,k=0,flag,c,d;

    while(scanf("%lld %lld %lld %lld",&a,&b,&c,&d)==4)
    {
        printf("%lld\n",max(a*c,max(a*d,max(b*c,b*d))));
    }

    return 0;
}


Measured memory_bytes: 3824
import java.util.Scanner;

public class Main {
  public static String security(String num){
    char a = num.charAt(0);
    for(int i=1; i<4; i++){
      char b = num.charAt(i);
      if(a == b) return "Bad";
      else{
        if(i != 3) a = b;
        else return "Good";
      }
    }
    return "0";
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    System.out.println(security(a));
  }
}


Measured memory_bytes: 21716
n = int(input())
h = list(map(int,input().split()))
array = [0 for i in range(n)]
for i in range(n):
    if 2 >= i > 0:
        array[i] = abs(h[i]-h[0])
    elif i > 2:
        array[i]= min(array[i-1] + abs(h[i]-h[i-1]),array[i-2] + abs(h[i]-h[i-2]))
print(array[n-1])


Measured memory_bytes: 13928
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int N; cin >> N;
    vector<int> L(N);
    rep(i,N) cin >> L.at(i);
    sort(L.begin(), L.end());
    ll res = 0;
    rep(i,N) {
        for (int j = i + 1; j < N; j++) {
            auto x = lower_bound(begin(L), end(L), L[i] + L[j]);
            size_t k = distance(begin(L), x);
            res += k - 1 - j;
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


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

    int ans = 0;
    rep(i, 1000){
        string str="";
        str += (i/100) + '0';
        str += (i%100)/10 + '0';
        str += (i%10) + '0';
        
        int itr = 0;
        rep(si, s.size()){
            if (s[si] == str[itr]){
                itr++;
            }
            if (itr == 3) {ans++; break;}
        }
    }

    cout << ans << endl;
}



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

int main() {
    int N, M, X, Y;
    cin >> N >> M >> X >> Y;
    vector<int> x(N), y(M);
    for (int i = 0; i < N; i++) {
        cin >> x[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> y[i];
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    for (int z = x[N - 1] + 1; z <= y[0]; z++) {
        if (X < z && z <= Y) {
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
    return 0;
}

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

bool solve(int N) {
    bool exist[21][21] = {};
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        exist[x][y] = true;
    }
    int M;
    cin >> M;
    map<char, pair<int, int>> m;
    m['N'] = make_pair(0, 1);
    m['E'] = make_pair(1, 0);
    m['S'] = make_pair(0, -1);
    m['W'] = make_pair(-1, 0);
    int cx = 10, cy = 10;
    for (int i = 0; i < M; i++) {
        char d;
        int l;
        cin >> d >> l;
        for (int j = 0; j < l; j++) {
            if (exist[cx][cy]) {
                exist[cx][cy] = false;
            }
            cx += m[d].first;
            cy += m[d].second;
        }
        if (exist[cx][cy]) {
            exist[cx][cy] = false;
        }
    }
    bool res = true;
    for (int i = 0; i < 21; i++) {
        for (int j = 0; j < 21; j++) {
            if (exist[i][j]) {
                res = false;
            }
        }
    }
    return res;
}

int main() {
    int N;
    while (true) {
        cin >> N;
        if (!N) return 0;
        cout << (solve(N) ? "Yes" : "No") << endl;
    }
}


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

int main () {
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  
  bool exist = false;
  for (int i = 0; i <= k; i++) {
    if (a >= b) {
      b *= 2;
    } else if (b >= c) {
      c *= 2;
    } else exist = true;
  }
  
  if (exist) {
    cout << "Yes" << endl;
  } else cout << "No" << endl;
}

Measured memory_bytes: 3132
function main(input){
    var line = input.split("\n");
    var line = line[0].split(' ');

    if ( line[0]*line[1]%2 == 0 ) {
        console.log('Even');
    } else {
        console.log('Odd');
    }
}
main(require('fs').readFileSync('/dev/stdin', 'UTF-8'));




Measured memory_bytes: 7496
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

using P = pair<double, double>;

int f(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n * f(n - 1);
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<P> p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i].first >> p[i].second;
    }
    sort(ALL(p));
    double sum = 0;
    do
    {
        double res = 0;
        for (int i = 0; i < n - 1; i++)
        {
            res += sqrt(pow(p[i].first - p[i + 1].first, 2) + pow(p[i].second - p[i + 1].second, 2));
        }
        sum += res;
    } while (next_permutation(ALL(p)));
    double ans = sum / (double)f(n);
    cout << fixed;
    cout << setprecision(15);
    cout << ans << endl;
}

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

typedef long long int ll;
double PI = 3.14159265358979;

bool prime(int x){
    int t = x;
    if(x == 1){
        return false;
    }
    if(t == 2){
        return true;
    }
    for(int i = 2;i < pow(x,0.5)+1;i++){
        if(t % i == 0){
            return false;
        }
        if(i == pow(x,0.5) && t % i != 0){
            return true;
        }
    }
    return true;
}

int main(){
 int Q;
 cin >> Q;
 int L[100010];
 L[1] = 0;
 for(int i = 1;i < 100010;i++){
     if(prime(i) && prime((i+1)/2)){
         L[i+1] = L[i] + 1;
     }else{
         L[i+1] = L[i];
     }
 }
 for(int i = 0;i < Q;i++){
     int l,r;
     cin >> l >> r;
     cout << L[r+1]-L[l] << endl;
 }
 /*for(int i = 2;i < Q;i++){
    if(prime(i)){
        cout << i << endl;
    }
 }*/
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[10010];
int main()
{
         while(1)
         {
                    memset(a,0,sizeof(0));
                    int n;
                    cin >> n;
                    if(n==0)break;
                    for(int i=0;i<n;i++)cin >> a[i];
                    long long ans=0ll;
                    sort(a,a+n);
                    for(int i=0;i<n-1;i++)ans+=a[i]*(n-1-i);
                    cout << ans << endl;
         }
         return 0;
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
using namespace std;
int main (){
    string s,s1;
    cin >> s;
    s1 = "YAKI";
    bool flg = true;
    if(s.size()<4){
        cout<<"No"<<endl;
        return 0;
    }
    for(int i=0;i<4;i++){
        if(s[i]!=s1[i]){
            flg = false;
        }
    }
    if(flg)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<vector>


using namespace std;


typedef long long ll;


int n;
vector<int> a;

int sign(int v)
{
	if(v<0) return -1;
	return v>0;
}


ll solve(int chk_sign)
{
	ll count=0;
	int sum=0, add, prev_sum;

	prev_sum=chk_sign;
	for(int i=0;i<n;i++)
	{
		sum+=a[i];
		if(prev_sum<0 && sum<=0)
		{
			add=-sum+1;
			sum+=add;
			count+=llabs(add);
		}
		if(prev_sum>0 && sum>=0)
		{
			add=-sum-1;
			sum+=add;
			count+=llabs(add);
		}
		prev_sum=sum;
	}
	return count;
}


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


int main(void)
{
	while(scanf("%d", &n)==1)
	{
		a.resize(n);
		for(int i=0;i<n;i++)
		{
			scanf("%d", &a[i]);
		}
		printf("%lld\n", min(solve(1), solve(-1)));
	}
	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>

int cmp(const void * a, const void * b) {
  return *(int*)b - *(int*)a;
}

int main(void) {
  int n, r=0;
  scanf("%d", &n);
  int arr[n];

  // 配列に保存 O(n)
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  
  //ソートする。O(log n)
  qsort(arr,n,sizeof(arr[0]),cmp);

  // 数える O(n)
  for (int j = 1; j <= n; j++) {
    if (arr[j-1] == arr[j]) continue;
    r++;
  }
  printf("%d", r);
}

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

char g[30][30];
bool vis[30][30] = {false};
int h, w;

void reset() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			vis[i][j] = false;
		}
	}
}
void bfs(int x, int y, int& ans) {
	queue<pair<pair<int, int>, int>> q;
	q.push({{x, y}, 0});


	while (!q.empty()) {
		int x = q.front().first.first, y = q.front().first.second;
		int lev = q.front().second;
		q.pop();


		if (vis[x][y]) continue;
		vis[x][y] = true;
		ans = max(ans, lev);

		if (x - 1 >= 0 && g[x-1][y] == '.') {
			q.push({{x-1, y}, lev+1});
		}
		if (x + 1 < h && g[x+1][y] == '.') {
			q.push({{x+1, y}, lev+1});
		}
		if (y - 1 >= 0 && g[x][y-1] == '.') {
			q.push({{x, y-1}, lev+1});
		}
		if (y + 1 < w && g[x][y+1] == '.') {
			q.push({{x, y+1}, lev+1});
		}

	}
}

int main() {
	cin >> h >> w;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> g[i][j];
		}
	}

	int ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (g[i][j] == '#')
				continue;
			reset();
			bfs(i, j, ans);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
def func(n):
  if n==1:return 1
  if n==0:return 1
  if dp[n]!=-1:return dp[n]
  f1=func(n-1) if n-1 not in a else 0
  f2=func(n-2) if n-2 not in a else 0
  tmp=(f1+f2)%1000000007
  dp[n]=tmp
  return tmp
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a={int(input()) for i in range(m)}
dp=[-1]*(n+1)
print(func(n)%1000000007)

Measured memory_bytes: 89668
#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 n,m;
    cin>>n>>m;
    vector<vector<int>> v(m);
    vector<int> p(m);
    for(int i=0; i<m; i++){
        int k;
        cin>>k;
        v[i].resize(k);
        for(int j=0; j<k; j++){
            cin>>v[i][j];
            v[i][j]-=1;
        }
    }
    for(int i=0; i<m; i++) cin>>p[i];

    int answer=0;
    for(int i=0; i<=n; i++){
        vector<int> tmp;
        for(int j=i; j<n; j++) tmp.push_back(0);
        for(int j=0; j<i; j++) tmp.push_back(1);
        do{
            int k=0;
            for(k=0; k<m; k++){
                int cnt=0;
                for(int s : v[k]) cnt+=tmp[s];
                if(cnt%2!=p[k]) break;
            }
            if(k==m) answer+=1;
        }while(next_permutation(tmp.begin(),tmp.end()));
    }
    cout<<answer;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
int n = 200005,q;
vector<vector<int>> tree(n,vector<int>());
vector<int> add(n,0);
vector<int> cumsum(n,0);

void dfs(int i,int before,int sum){
  cumsum.at(i) = sum + add.at(i);
  for(auto p:tree.at(i)){
    if(p == before) continue;
    dfs(p,i,cumsum.at(i));
  }
}
 
int main() {
  cin >> n >> q;
  rep(i,n-1){
    int a,b;
    cin >> a >> b;
    --a;--b;
    tree.at(a).push_back(b);
    tree.at(b).push_back(a);
  }
  rep(i,q){
    int p,x;
    cin >> p >> x;
    --p;
    add.at(p) += x;
  }
  dfs(0,-1,0);
  rep(i,n) cout << cumsum.at(i) <<  " ";
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 27392
#include<bits/stdc++.h>
using namespace std;
#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--)
typedef long long LL;
LL K;
LL A[100001];
int main(){
	cin>>K;
	REP(i,K){
		cin>>A[i];
	}
	
	/*if(A[K-1]>2){
		cout<<-1<<endl;
		return 0;
	}*/
	LL mi=2;
	LL ma=2;
	for(int i=K-1;i>=0;i--){
		LL ubb=ma;
		{
			LL ub=1e18;
			LL lb=-1;
			while(abs(ub-lb)>1){
				LL mid=(ub+lb)/2;
				if(mid>(ubb)/A[i]){
					ub=mid;
				}else{
					lb=mid;
				}
			}
			ma=lb*A[i];
		}
		if(ma==0){
			cout<<-1<<endl;
			return 0;
		}
		ma+=(A[i]-1);
		LL lbb=mi;
		{
			LL ub=1e18;
			LL lb=-1;
			while(abs(ub-lb)>1){
				LL mid=(ub+lb)/2;
				if(mid<(lbb+A[i]-1)/A[i]){
					lb=mid;
				}else{
					ub=mid;
				}
			}
			mi=ub*A[i];
		}
		if(mi<2||ma<2){
			cout<<-1<<endl;
			return 0;
		}
		//cout<<mi<<" "<<ma<<endl;
		if(mi>ma){
			cout<<-1<<endl;
			return 0;
		}
	}
	if(mi>ma){
		cout<<-1<<endl;
	}else{
		cout<<mi<<" "<<ma<<endl;
	}
	return(0);
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <unordered_map>
#include <limits>

int K;
std::vector<int> dp;
std::vector<int> cost;

int sol ( int i ) {
  if ( dp[i] != -1 ) return dp[i];

  int cost_min = std::numeric_limits<int>::max();
  for(int j=1; j<=K && i-j>=0; j++) cost_min = std::min( cost_min, sol(i-j) + std::abs(cost[i]-cost[i-j]) );

  return dp[i] = cost_min;
}

int main (void) {

  int N;
  std::cin >> N;

  std::cin >> K;

  cost.resize(N);
  for(int i=0; i<N; i++) std::cin >> cost[i];

  dp.assign(N,-1);
  dp[0] = 0;

  std::cout << sol(N-1) << std::endl;

  return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
char s[1000007];
int k,n;
int main()
{
    ios::sync_with_stdio(false);
    cin>>(s+1);
    cin>>k;
    if(k==1) 
    {
        cout<<(s+1); 
        return 0; 
    }
    n=strlen(s+1);
    for(int i=1;i<=n;++i)
    {
        if(i%k==1) cout<<s[i];
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };


int main() {
	long long x,t;
	cin>>x>>t;
	if(x>t){
		cout<<x-t<<endl;
	}
	else{
		cout<<0<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
	cin >> n;
	int m = ceil(0.5 * sqrt(8.0 * n + 1) - 0.5), q = m * (m + 1) / 2 - n;
	string s = string(m - q, ')') + "(" + string(q, ')') + string(m - 1, '(');
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 3364
#include <string>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
int main()
{
    int d, t, s;
    cin >> d >> t >> s;
    if(d <= t * s) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

void OutputIntVector(const std::vector<int>& Vector);

int main()
{
	int N;
	std::cin >> N;
	std::vector<int> A;
	A.resize(N);
	for(int i=0;i<N;i++)
	{
		std::cin >> A[i];
	}

	OutputIntVector(A);

	for(int i=1;i<N;i++)
	{
		int key = A[i];
		/* insert A[i] into the sorted sequence A[0,...,j-1] */
		int j = i - 1;
		while(j>=0 && A[j]>key)
		{
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = key;
		OutputIntVector(A);
	}

	return 0;
}

void OutputIntVector(const std::vector<int>& Vector)
{
	for(unsigned int i=0;i<Vector.size();i++)
	{
		std::cout << Vector[i] << std::flush;
		if(i < Vector.size() -1)
		{
			std::cout << " " << std::flush;
		}else{
			std::cout << std::endl;
		}
	}
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define e "\n"
#define MaRiaMa { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
#define fix(n) cout << fixed << setprecision(n);
using namespace std;
int main()
{
	MaRiaMa;
	int n;
	ll fac=1;
	cin >> n;
	for (int i = n; i >= 1; i--)
	{
		fac *= i;
		fac %= (1000000007);
	}
	cout << fac;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<long long, long long>
#define ff first
#define ss second
const int M = 1e9+7;

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W; cin >> H >> W;
    int a[H][W];
    for(int i = 0; i < H; i++){
        string s; cin >> s;
        for(int j = 0; j < W; j++){
            if(s[j] == '.') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    int DP[H][W]; memset(DP, 0, sizeof(DP));
    DP[0][0] = 1;
    for(int i = 1; i < H && a[0][i]; i++)
        DP[0][i] = DP[0][i-1];
    for(int i = 1; i < W && a[i][0]; i++)
        DP[i][0] = DP[i-1][0];
    for(int i = 1; i < H; i++){
        for(int j = 1; j < W; j++){
            if(!a[i][j]) DP[i][j] = 0;
            else DP[i][j] = (DP[i-1][j] + DP[i][j-1]) % M;
        }
    }
    cout << DP[H-1][W-1];
}

Measured memory_bytes: 11376
L,R = map(int,input().split())
flg = 1
for i in range(10**6+1) :
    if 2019*i < L :
        continue
    
    if 2019*i <= R :
        ans = 0
        flg = 0
        break
    
    else :
        break
if flg :
    ans = float("inf")
    
    for i in range(L,R) :
        for j in range(i+1,R+1) :
            calc = (i*j) % 2019
            ans = min(ans,calc)
print(ans)


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

const int maxn=20010;
const int base=8000;
const int maxm=8000;
int n;
int a[maxn];
bool dp[maxn][2], tmp[maxn];
char s[maxn];
int x, y;

int main(){

	scanf("%s",s+1); n=strlen(s+1);
	scanf("%d%d",&x,&y);
	int cnt=0, now=0, first=1;
	dp[base][1]=true;
	for(int i=1;i<=n;i++){
		if(s[i]=='F') cnt++;
		if(s[i]=='T' || i==n){
			if(first){ dp[base+cnt][now]=1,first=0, now^=1, cnt=0; continue; }
			// printf("%d ",cnt);
			memset(tmp,0,sizeof(tmp));
			for(int j=0;j+cnt<=(maxm<<1);j++) if(dp[j][now]) tmp[j+cnt]=1;
			for(int j=cnt;j<=(maxm<<1);j++) if(dp[j][now]) tmp[j-cnt]=1;
			for(int j=0;j<=(maxm<<1);j++) dp[j][now]=tmp[j];
			cnt=0; now^=1;
		}
	}
	int ans=dp[x+base][0] & dp[y+base][1];
	printf("%s\n", ans?"Yes":"No");
	return 0;
}

Measured memory_bytes: 256