akhauriyash/Code-Regression huggingface dataset:
n = gets.chomp.to_i
x = gets.chomp.split.map(&:to_i)
y = gets.chomp.split.map(&:to_i)

manhattan = 0
n.times do |i|
  manhattan += (x[i] - y[i]).abs
end

puts format("%.6f", manhattan)

euclid = 0
n.times do |i|
  euclid +=  ((x[i] - y[i]).abs ** 2)
end
puts format("%.6f", Math.sqrt(euclid))

value = 0
n.times do |i|
  value +=  ((x[i] - y[i]).abs ** 3)
end
puts format("%.6f", Math.cbrt(value))

chebyshev = 0

n.times do |i|
  chebyshev =  [chebyshev, (x[i] - y[i]).abs].max
end
puts format("%.6f", chebyshev)



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

int main()
{
    int n;
    cin>>n;
    vector <int> a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    cout<<a[n/2]-a[n/2-1]<<endl;
    return 0;
}

Measured memory_bytes: 640
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	int a, b;
	cin >> a >> b;
	int ans = a <= 9 && b <= 9 ? a * b : -1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
n=int(input())
b=sorted([int(i) for i in input().split()],reverse=True)
def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
A=groupby(b)
l=len(A)
B=[]
for i in range(l):
    A[i][1]=min(A[i][1]//2,2)
    if A[i][1]!=0:
        B.append(A[i])

l=len(B)
if l==0:
    print(0)
elif l==1:
    if B[0][1]==1:
        print(0)
    else:
        print(B[0][0]**2)
else:
    if B[0][1]==2:
        print(B[0][0]**2)
    else:
        print(B[0][0]*B[1][0])


Measured memory_bytes: 17684
#include <iostream>
#include <math.h>
#include <bits/stdc++.h>
#include <algorithm>
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define N 100005
#define inf 1e18
#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

ll binomialCoeff(ll n,ll k)
{
    ll res = 1;
    if(k >n - k)
        k = n - k;
    for(int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

ll power(ll x,ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}


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

void Sieve(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));
    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";
}

//******************************************************    CHECK CONSTRAINTS   ***************************************************************//

vector <int> g[N];
int dp[N];

int dfs(int n)
{
    if(dp[n]!=-1)
        return dp[n];
    int a = 0;
    for(int i=0;i<g[n].size();i++)
    {
        a = max(a,dfs(g[n][i])+1);
    }
    dp[n] = a;
    return dp[n];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
    int n,m;
    mem(dp,-1);
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].pb(y);
    }
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans = max(ans,dfs(i));
    }
    //for(int i=1;i<=n;i++)
      //  cout << dp[i] << " ";
    cout << ans;
}


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

using namespace std;


void solve() {
    int a, b;
    cin >> a >> b;
    if (abs(a-b)&1) {
        cout << "IMPOSSIBLE";
        return;
    }
    int res = (a+b)/2;
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
def count_div_by_two(n: int):
    c = 0
    while n % 2 == 0:
        n //= 2
        c += 1
    return c


N = int(input())
A = list(map(int, input().split()))
count_A = list(map(count_div_by_two, A))
print(sum(count_A))


Measured memory_bytes: 4148
import java.util.Scanner;

class Main{
    int x, y;
    
    public void solve(){
        int a, b;
        Scanner sc = new Scanner(System.in);
        x = sc.nextInt();
        y = x*x*x;
        
        System.out.println(y);
                
    }
    
    public static void main(String[] args){
        new Main().solve();
    }
    
}

Measured memory_bytes: 17156
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
constexpr int INF = 1 << 28;

int main()
{
    int N, T;
    cin >> N >> T;
    vector<pair<int, int>> ab(N);
    rep(i, N)cin >> ab[i].first >> ab[i].second;
    sort(ab.begin(), ab.end());

    vector<vector<int>> dp(N + 1, vector<int>(T + 1, -INF));
    dp[0][0] = 0;
    rep(i, N) {
        int a, b;
        tie(a, b) = ab[i];
        rep(t, T) {
            // nothing
            dp[i][t + 1] = max(dp[i][t + 1], dp[i][t]);
            dp[i + 1][t] = max(dp[i + 1][t], dp[i][t]);

            // use
            dp[i + 1][min(t + a, T)] = max(dp[i + 1][min(t + a, T)], dp[i][t] + b);
        }
        // left
        dp[i + 1][T] = max(dp[i + 1][T], dp[i][T]);
    }
    cout << *max_element(dp.back().begin(), dp.back().end()) << endl;
    return 0;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
#define long long long
#define read cin >>
#define echo cout <<
#define fin << endl
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)

// for debug macro
bool global_debug_flag = false;
#define DEBUG(val) \
  if (global_debug_flag) cout << #val << " = " << val << endl

double kitaichi(long x) {
  long a = 0;
  REP(i, x + 1) { a += i; }
  double ret = 0;
  ret = a / ((double)x);
  DEBUG(x);
  DEBUG(ret);
  return ret;
}

int main() {
  int n, k;
  read n >> k;
  vector<long> data(n);
  vector<long> syaku(n);
  REP(i, n) {
    int x;
    read x;
    data[i] = x;
    if (i == 0) {
      syaku[i] = x;
    } else {
      syaku[i] = syaku[i - 1] + x;
    }
  }
  long max_range_num = 0;
  int idx = 0;
  REP(i, n - k + 1) {
    long now_range = 0;
    if (i == 0) {
      now_range = syaku[i + k - 1];
    } else {
      now_range = syaku[i + k - 1] - syaku[i - 1];
    }
    DEBUG(now_range);
    if (max_range_num < now_range) {
      max_range_num = now_range;
      idx = i;
    }
  }
  DEBUG(idx);
  double ans = 0;
  FOR(i, idx, idx + k) { ans += kitaichi(data[i]); }
  cout << fixed << setprecision(12) << ans << endl;
}


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

using namespace std;

#define N 120000

int n,ans,fl,a[N],b[N];
map<int,int> fa,cnt,vis;

int gfa(int x){
	return x==fa[x]?x:fa[x]=gfa(fa[x]);
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){scanf("%d",a+i); a[0]^=a[i];}
	for (int i=1;i<=n;++i){scanf("%d",b+i); b[0]^=b[i];}
	for (int i=0;i<=n;++i){++cnt[a[i]]; --cnt[b[i]];}
	for (auto i:cnt) if (i.second){puts("-1"); return 0;}
	for (int i=0;i<=n;++i) fa[a[i]]=a[i];
	vis[a[0]]=1; ans=1;
	for (int i=0;i<=n;++i){
		if (a[i]!=b[i]){
			ans+=(!vis[a[i]])+(!vis[b[i]]);
			vis[a[i]]=vis[b[i]]=1;
			++ans;
			int x=gfa(a[i]),y=gfa(b[i]);
			if (x!=y){
				--ans;
				fa[x]=y;
			}
		}
	}
	printf("%d\n",ans+fl-1-(a[0]!=b[0]));
	
	return 0;
}
			

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

int N,ans;
typedef pair<int,int> P;
P R[100],B[100];
vector<P> C[100];
map<P,int> used;

int main(void){
    cin >> N;
    rep(i,N)cin >> R[i].second >> R[i].first; //firstがy座標
    rep(i,N)cin >> B[i].first >> B[i].second; //firstがx座標
    sort(B,B+N);
    sort(R,R+N,greater<P>());

    rep(i,N){
        rep(j,N){
            if(R[j].second < B[i].first && R[j].first < B[i].second){
                if(used.count(R[j])==0){
                    used[R[j]] = 1;
                    ans++;
                    break;
                }
            }
        }
    }
    /*
    rep(i,N){
        rep(j,C[i].size()){
            if(j)cout << ",";
            cout << "(" << C[i][j].first <<","<<C[i][j].second<<")";
        }
        cout << endl;
    }*/
    cout << ans << endl;
}


Measured memory_bytes: 256
import math
import itertools
from heapq import heapify, heappop, heappush
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))





##### Library ####
#指定値未満の素数
def primes(max_number):
    """
    指定値未満の素数を取得するジェネレータ
    https://qiita.com/Mokkeee/items/93b6b7d59fa256aa1677
    """
    if max_number <= 2:
        raise StopIteration
    yield 2
    is_prime = [1] * max_number
    square_root_of_max = max_number ** 0.5
    for number in range(3, max_number, 2):
        if is_prime[number] is 0:
            continue
        yield number
        if number <= square_root_of_max:
            for multiple in range(number * 2, max_number, number):
                is_prime[multiple] = 0
##### main #####
def main():
	l = LI()
	K = I()
	max_l = max(l)
 
	add_max = max_l * (2 ** K)
	print(sum(l) - max_l + add_max)


if __name__ == '__main__':
	main()

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 100000

int main()
{
    int N;
    cin >> N;
    vector<ll> a(N);
    rep(i,N)cin >> a[i];

    int s=0;
    rep(i,N)s^=a[i];
    rep(i,N)a[i]^=s;
    rep(i,N){
        cout << a[i] << endl;
    }
}

Measured memory_bytes: 4720
D = int(input())
c = [int(_) for _ in input().split()]
s = [[int(_) for _ in input().split()] for _ in range(D)]

sat = 0
last = [0] * 26
for d in range(D):
    v = -1000000
    for x in range(26):
        if v < (d + 1 - last[x]) * c[x]:
            j = x
            v = (d + 1 - last[x]) * c[x]
    last[j] = d + 1
    print(j+1)

    for i in range(26):
        sat -= (d + 1 - last[i]) * c[i]
    sat += s[d][j]
    # print(sat)


Measured memory_bytes: 9452
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    string s;
    cin >> s;
    vector<int> a(26);
    rep(i,s.length()){
        int num = s[i] - 97;
        a[num]++;
    }
    rep(i,26){
        if(a[i]%2 == 1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



//連想配列を利用する

int main (){
  int n;
  cin >> n;
  map<string, int> mp;
  REP(i,n){
    string s;
    cin >> s;
    mp[s]++;
  }


  cout << "AC" << " x " << mp["AC"]<< endl;
  cout << "WA" << " x " << mp["WA"] << endl;
  cout << "TLE" << " x " << mp["TLE"] << endl;
  cout << "RE" << " x " << mp["RE"] << endl;

  //c++ mapは， 存在しないキーは　０　で返されるので


  return 0;

}

Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

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

    vector<int> bukaNum(num + 1, 0);

    int temp;

    for (int i = 2; i <= num; i++)
    {
        cin >> temp;

        bukaNum[temp] = bukaNum[temp] + 1;
    }

    for (int i = 1; i <= num; i++)
    {
        cout << bukaNum[i] << endl;
    }


}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

vpii v;
int main(){
	int n; scanf("%d", &n);
	int m = n/2*2;
	FOR(i, 1, m+1){
		FOR(j, i+1, m+1){
			if(i+j==m+1) continue;
			v.EB(i, j);
		}
	}
	if(n%2){
		FOR(i, 1, m+1){
			v.EB(i, n);
		}
	}
	printf("%d\n", v.size());
	for(pii &p: v){
		printf("%d %d\n", p.first, p.second);
	}
}


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>0;(i)--)
#define rrep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrepr(i,n,m) for(int (i)=(n);(i)>(m);(i)--)
#define SORT(s) sort((s).begin(),(s).end())
#define SORTR(s,t) sort((s).begin(),(s).end(),greater<t>())

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<vector<int>> vvi;

const int INF = 1000000000;
const ll LINF = 1000000000000000000ll;
const double PI = acos(-1.0);
const double EPS = 1e-10;

const ll MOD = 1000000007ll;
const int MAX=510000;

int N; ll M; vll A;
void input()
{
    cin>>N>>M;
    rep(i,N){
        ll a; cin>>a; A.emplace_back(a);
    }
    return;
}

ll gcd(ll a,ll b)
{
    while(b!=0ll){
        ll tmp=a%b;
        a=b;
        b=tmp;
    }
    return a;
}
ll lcm(ll a, ll b)
{
    return a*b/gcd(a,b);
}

void solve()
{
    // rep(i,N) A[i]/=2ll;
    ll lc=A[0]/2;
    rep(i,N) {
        lc=lcm(lc,A[i]/2);
        if(lc>M) break;
        if ((lc/(A[i]/2)) % 2 == 0){
            printf("0\n");
            return;
        }
    }
    // cout<<lc<<endl;

    // ll ans=(M/lc+1ll)/2ll;
    ll ans=0;
    for(int i=1;lc*i<=M;i+=2){
        ++ans;
    }
    cout<<ans<<endl;
    return;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    solve();
    return 0;
}

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(-1.0);
const int limit = 100010;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())

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

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

    REP(i, a, b + 1) {
        if (i - a <= k - 1 || b - i <= k - 1) cout << i << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main {
    public static void main(String args[] ) throws Exception {
        Scanner ob=new Scanner(System.in);
        int n=ob.nextInt();int k=ob.nextInt();
        int INF = (int)1e9+7;
        int a[]=new int[n];
        for(int i=0;i<n;i++)a[i]=ob.nextInt();
        int dp[]=new int[n];
        for(int i=0;i<n;i++)dp[i]=INF;
        dp[0]=0;
        dp[1]=Math.abs(a[1]-a[0]);
        
        
        //System.out.println(Arrays.toString(a));
        //System.out.println(Arrays.toString(dp));
        
        for(int i=2;i<n;i++)
        {
            for(int j = Math.max(0,i-k);j<i;j++)
            {
                dp[i]=Math.min(dp[i],dp[j]+Math.abs(a[j]-a[i]));
            }
        }
        System.out.println(dp[n-1]);
        
        //System.out.println(Arrays.toString(dp));
        //System.out.println("Hello World!");
    }
}


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

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

  int64_t N, T;
  cin >> N >> T;
  pair<int64_t, int64_t> P[N];
  rep(i,N){
    cin >> P[i].first >> P[i].second;
  }
  int64_t ans = 0;
  int64_t dp1[N+2][T] = {}, dp2[N+2][T] = {};
  for(int i=1;i<=N;i++){
    for(int j=1;j<T;j++){
      if(P[i-1].first > j){
        dp1[i][j] = dp1[i-1][j];
      }
      else{
        dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-P[i-1].first] + P[i-1].second);
      }
    }
  }

  for(int i=N;i>=1;i--){
    for(int j=1;j<T;j++){
      if(P[i-1].first > j){
        dp2[i][j] = dp2[i+1][j];
      }
      else{
        dp2[i][j] = max(dp2[i+1][j], dp2[i+1][j-P[i-1].first] + P[i-1].second);
      }
    }
  }

  for(int i=1;i<=N;i++){
    for(int j=0;j<=T-1;j++){
      ans = max(ans, dp1[i-1][j] + dp2[i+1][T-j-1] + P[i-1].second);
    }
  }


  cout << ans << endl;

}

Measured memory_bytes: 141056
s = input()

dic = ['dreameraser', 'dreamerase', 'dreamer', 'dream', 'eraser', 'erase']

def check():
    i = 0
    while i < len(s):
        found = False
        for k in dic:
            if s[i:i+len(k)] == k:
                found = True
                break
        if not found:
            return False
        i += len(k)
    return True


print('YES' if check() else 'NO')

Measured memory_bytes: 39920
#include<iostream>
using ll=long long;
using namespace std;
int main(){
ll x,k,d;
  cin>>x>>k>>d;
  x=abs(x);
  ll ans;
  if(x/d>k){
    ans=x-d*k;
  }
else{
  ll e=x/d;
  k-=e;
  x-=e*d;
  if(k%2==1) x=abs(x-d);
  ans=x;
}
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3632
//
//  main.cpp
//  zero
//
//  Created by 叶金炜 on 2019/4/2.
//  Copyright © 2019 okstal. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string.h>
#define pi acos(-1)
using namespace std;
int main()
{
    int n,m,l;
    int a[107][107];
    int b[107][107];
    long long c[107][107];
    memset(c, 0, sizeof(c));
    cin>>n>>m>>l;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=l;j++)
            cin>>b[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=l;j++)
            for(int k=1;k<=m;k++)
                c[i][j]+=a[i][k]*b[k][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=l;j++)
        {
            if(j==l)cout<<c[i][j]<<endl;
            else cout<<c[i][j]<<" ";
        }
    return 0;
}



Measured memory_bytes: 3272
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
//    return *(long long*)a - *(long long*)b;
}
//  qsort(A, b, sizeof(int), compare_int);

long long  factorial(long long n) {
    if (n > 0) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}

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

int distance(int a, int b) {
  return abs(a-b)*abs(a-b);
}

//int ()



int main()
{
  int a ,b, c, d, e, X, Y;
//  long long  a, b, c, d, e, X, Y;
  //  double  c;
//  int  A[200003]={};
  int  A[100003]={};
  int  B[100003]={};
  int  C[100003][11]={};

  int  flg=0;

//  long long  a, b, c, d, X, Y;
  char s[101][101]={};
  char t[101]={};
//  int N, M;
//  int A[1000000001]={};
//  long long  C[101]={};
  int i,j,k;
  long long p,q;
//  int flag=0;
//  int tmp=0;
//  char tmp[101]={};
//  long long min=10000000000;
//  long long min=100000001;
  int len=0;
  int l=0;
  int r=1000001;
  int cnt=0;
  int num=0;
  int num1=0;
  int num2=0;
  int ans=0;
  int max=0;
  int sum=0;
  int addr=0;
  int ptn=0;
  long long  tmp=0;
//  bool on_off[100]={};
  
//  char alp[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

  //  a=0;
//  scanf("%lld %lld", &a, &b);
  scanf("%d", &a);
  scanf("%d", &B[0]);
  A[0]=B[0];
  A[1]=B[0];
  //  printf("%d ", A[0]);

  for(i=1;i<a-1;i++){
  scanf("%d", &B[i]);
    if(B[i]<A[i]) A[i]=B[i];
    A[i+1]=B[i];
 //   printf("%d ", A[i]);
  }
 //     printf("%d ", A[i+1]);
  for(i=0;i<a;i++){
    cnt=cnt+A[i];
 //   printf("%d ", cnt);
  }
 
  

    
//    printf("%s %d %d\n", s[i],C[i][0],C[i][1]);
   // printf("%d\n", C[i][1]);
/*  for(i=0;i<addr;i++){
//  scanf("%lld%lld", &B[0][i],&B[1][i]);
//    ans=ans+A[i];
    printf("%lld ", A[i]);
  }
*/
    printf("%d\n", cnt);
   

return 0;
}


Measured memory_bytes: 896
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int LL;
typedef long double dd;
//#define i_7 (ll)(1E9+7)
#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

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

struct A{
    string s;
    ll kaz;
    ll mi=0;
    ll ma=0;
};
bool comp(l_l a,l_l b){
    ll disa=a.se-a.fi;
    ll disb=b.se-b.fi;
    if(disa>0){
        if(disb<=0)return true;
        return a.fi<b.fi;
    }
    if(disa<0){
        if(disb>=0)return false;
        return a.fi>b.fi;
    }
    if(disb<0)return true;
    else return false;
}

int main(){fastio
    ll n;cin>>n;
    A a[n];
    rep(i,0,n-1)cin>>a[i].s;
    rep(i,0,n-1){
        ll cnt=0;
        rep(j,0,a[i].s.size()-1){
            if(a[i].s[j]=='(')cnt++;
            else cnt--;
            chmin(a[i].mi,cnt);
            chmax(a[i].ma,cnt);
        }
        a[i].kaz=cnt;
    }
    
    vector<ll>l,r;
    vector<l_l>m;
    rep(i,0,n-1){
        if(a[i].mi<0){
            if(a[i].kaz==a[i].mi){
                r.pb(-a[i].mi);
            }else{
                m.pb({-a[i].mi,a[i].kaz-a[i].mi});
            }
        }else{
            if(a[i].kaz>0){
                l.pb(a[i].kaz);
            }
        }
    }
    ll L=0,R=0;
    for(auto x:l)L+=x;
    for(auto x:r)R+=x;
    sort(m.begin(),m.end(),comp);
    
    for(auto x:m){
        L-=x.fi;
        if(L<0){
            cout<<"No"<<endl;
            return 0;
        }
        L+=x.se;
    }
    if(L-R==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    
    
    return 0;
}




Measured memory_bytes: 65920
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int MOD = (int)1e9 + 7;
const int INF = 1LL << 60;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end() //コンテナじゃないと使えない!!
#define debug(x) cerr << #x << ": " << x << "\n";
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    string boin = "aeiou";
    if (boin.find(S)!=string::npos){
        cout << "vowel\n";
    }else{
        cout << "consonant\n";
    }
}

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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long
#define MAX_V 10000

typedef pair<ll, ll> P;
set<int> st;

int main(){
    int h, a;
    cin >> h >> a;
    if(h % a == 0) cout << h/a << endl;
    else cout << h/a + 1 << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> S(N);
  int ans = 0;
  for (int& s : S) {
    cin >> s;
    ans += s;
  }
  if (ans % 10) {
    cout << ans << endl;
    return 0;
  }
  sort(S.begin(), S.end());
  for (int i = 0; i < N; i++) {
    ans = 0;
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      ans += S[j];
    }
    if (ans % 10) {
      cout << ans << endl;
      return 0;
    }
  }
  cout << 0 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define PI 3.14159265358979323846
const int MOD = 1e9 + 7 ;
const int EPS = 1e-9;
const int N=1e5+2;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool vis[1000][1000];
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);

      int h,w;
      cin>>h>>w;
      string a[h];
      for(int i=0;i<h;i++) cin>>a[i];
      queue<pair<int,int>> q;
      for(int i=0;i<h;i++)
      {
        for(int j=0;j<w;j++)
        {
            if(a[i][j]=='#') 
            {
                  q.push({i,j});
            }
        }
      }
      q.push({-1,-1});
      int ans=0;
      while(!q.empty())
      {
            auto curr=q.front();
            q.pop();
            if(curr.fi==-1)
            {
                  if((int)q.size()==0) {break;}
                  else q.push({-1,-1}),ans++;
                  continue;
            }
            if(vis[curr.fi][curr.se]) continue;
            vis[curr.fi][curr.se]=true;
            for(int i=0;i<4;i++)
            {
                  int xx=curr.fi+dx[i];
                  int yy=curr.se+dy[i];
                  if(xx<h&&xx>=0&&yy>=0&&yy<w&&a[curr.fi+dx[i]][curr.se+dy[i]]=='.')
                  {
                        q.push({curr.fi+dx[i],curr.se+dy[i]});
                        a[xx][yy]='#';
                  }
            }
      }
      cout<<ans;
} 

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

public class Main {
    static MyReader in = new MyReader();

    public static void main(String[] args) {
        int N = in.i();
        char[][] S = new char[2][];
        S[0] = in.s(N);
        S[1] = in.s(N);

        int[][] numOfCase = {{2, 2}, {1, 3}, {3, 6}};
        int state = 2;
        long ans = 1;
        int MOD = 1_000_000_007;
        for (int i = 0; i < N; i += 1 + state) {
            int input = S[0][i] == S[1][i] ? 0 : 1;
            ans = ans * numOfCase[state][input] % MOD;
            state = input;
        }
        System.out.println(ans);
    }
}

class MyReader extends BufferedReader {
    char[] cbuf = new char[1024];
    int head = 0;
    int tail = 0;

    MyReader() {
        super(new InputStreamReader(System.in));
    }

    char next() {
        if (head == tail) {
            try {
                tail = super.read(cbuf, 0, cbuf.length);
            } catch (IOException e) {
                e.printStackTrace();
            }
            head = 0;
        }
        return cbuf[head++];
    }

    int i() {
        int k = next() - '0';
        boolean minus = k == -3;
        int n = minus ? 0 : k;
        while (0 <= (k = next() - '0') && k <= 9) n = 10 * n + k;
        return minus ? -n : n;
    }

    int[] ii(final int N) {
        int[] a = new int[N];
        for (int j = 0; j < a.length; j++) a[j] = i();
        return a;
    }

    long l() {
        int k = next() - '0';
        boolean minus = k == -3;
        long n = minus ? 0 : k;
        while (0 <= (k = next() - '0') && k <= 9) n = 10 * n + k;
        return minus ? -n : n;
    }

    char[] s(final int N) {
        char[] s = new char[N];
        for (int i = 0; i < N; i++) {
            s[i] = next();
        }
        next();
        return s;
    }

    public int read(char[] cbuf) {
        int i;
        char c;
        for (i = 0; (c = next()) != ' ' && c != '\n'; i++) cbuf[i] = c;
        return i;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }
}


Measured memory_bytes: 32308
V=int(input())
 
G=[[] for i in range(V)]
d=[1001001001 for i in range(V)]
used=[False for i in range(V)]
 
import heapq
 
def dijkstra(s):
    q=[]
    d[s]=0
    heapq.heappush(q,(0, s))
     
    while(len(q)):
         
        p=heapq.heappop(q)
        v=p[1]
        used[v]=True
        if d[v]<p[0]:
            continue
        for e in G[v]:
            if (not used[e[0]]) and d[e[0]]>d[v]+e[1]:
                d[e[0]]=d[v]+e[1]
                 
                heapq.heappush(q, (d[e[0]], e[0]))
 
import sys
for l in sys.stdin:
    l=list(map(int,l.split()))
    u=l[0]
    k=l[1]
    G[u]=zip(*[iter(l[2:])]*2)
     
dijkstra(0)
for i, c in enumerate(d):
    print(i, d[i])

Measured memory_bytes: 41600
N = int(input())
P = list(map(int, input().split()))
cnt = 0
curr_min = 0
for i in range(N):
    if not curr_min:
        curr_min = P[i]
        cnt += 1
    else:
        if P[i] <= curr_min:
            curr_min = P[i]
            cnt += 1

print(cnt)

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

int main() {

  int n,a,b;
  cin>>n>>a>>b;
  cout<<(abs(a-n)<abs(b-n) ? "A" : "B")<<endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int a = sc.nextInt();
    int b = sc.nextInt();
    int t = sc.nextInt();
    int n = 0;
    
    for(int i=a; i<=t+0.5; i += a){
      n += b;
    }
    
    System.out.println(n);
  }
}

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

int main(){
  long long sum = 9;
  while(1){
    char x;
    cin >> x;
    if(cin.eof()) break;
    int num = x-'0';
    sum += num;
  }
  if(sum%9 == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdbl vector<double>
#define vstr vector<string>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	int n;
	string s;
	cin >> n >> s;

	int l = 0;
	int r = 0;
	int cnt = 0;
	rep(i,n){
		char c = s[i];
		if(cnt == 0 && c == ')'){
			l++;
		}else{
			cnt += c == '(' ? 1 : -1;
		}
	}

	r = cnt;

	rep(i,l) cout << '(';
	cout << s;
	rep(i,r) cout << ')';
	cout << endl;
}

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

#define EPS 1e-10
bool eq(double a, double b) {return fabs(a - b) < EPS;}

struct Point {
    double x, y;
    Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
    Point operator + (Point &p);
    Point operator - (Point &p);
    Point operator * (double k);
    Point operator / (double k);
    bool operator == (const Point &p) const;
    double norm();
    double abs();
    void print();
} typedef Vec;

struct Segment {
    Point p1, p2;
    Segment(Point p1, Point p2) : p1(p1), p2(p2) {}
    Segment(double x1, double y1, double x2, double y2) : p1(Point(x1, y1)), p2(Point(x2, y2)) {}
} typedef Line;

struct Circle {
    Point o; double r;
    Circle(Point o, double r) : o(o), r(r) {}
    Circle(double x, double y, double r) : o(Point(x, y)), r(r) {}
};

double norm(Vec a);
double abs(Vec a);

double dot(Vec a, Vec b);
double cross(Vec a, Vec b);

bool isOrthogonal(Vec a, Vec b);
bool isOrthogonal(Point a1, Point a2, Point b1, Point b2);
bool isOrthogonal(Segment s1, Segment s2);

bool isParallel(Vec a, Vec b);
bool isParallel(Point a1, Point a2, Point b1, Point b2);
bool isParallel(Segment s1, Segment s2);

Point project(Segment s, Point p);

int main() {
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    Line l(x1, y1, x2, y2);
    int q; cin >> q;
    while(q--) {
        double x, y;
        cin >> x >> y;
        auto p = project(l, Point(x, y));
        p.print();
    }
    return 0;
}

Point Point::operator + (Point &p) {return Point(x + p.x, y + p.y);}
Point Point::operator - (Point &p) {return Point(x - p.x, y - p.y);}
Point Point::operator * (double k) {return Point(x * k, y * k);}
Point Point::operator / (double k) {return Point(x / k, y / k);}
bool Point::operator == (const Point &p) const {return eq(x, p.x) && eq(y, p.y);}
double Point::norm() {return x * x + y * y;}
double Point::abs() {return sqrt(norm());}
void Point::print() {printf("%.10lf %.10lf\n", x, y);}

double norm(Vec a) {return a.x * a.x + a.y * a.y;}
double abs(Vec a) {return sqrt(norm(a));}

double dot(Vec a, Vec b) {return a.x * b.x + a.y * b.y;}
double cross(Vec a, Vec b) {return a.x * b.y - a.y * b.x;}

bool isOrthogonal(Vec a, Vec b) {return eq(dot(a, b), 0.0);}
bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) {return isOrthogonal(a1 - a2, b1 - b2);}
bool isOrthogonal(Segment s1, Segment s2) {return eq(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);}

bool isParallel(Vec a, Vec b) {return eq(cross(a, b), 0.0);}
bool isParallel(Point a1, Point a2, Point b1, Point b2) {return isParallel(a1 - a2, b1 - b2);}
bool isParallel(Segment s1, Segment s2) {return eq(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);}

Point project(Segment s, Point p) {
    Vec base = s.p2 - s.p1;
    double r = dot(p - s.p1, base) / norm(base);
    return base * r + s.p1;
};



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


def read():
    N, M = map(int, input().strip().split())
    AB = []
    for i in range(M):
        a, b = map(int, input().strip().split())
        AB.append((a, b))
    return N, M, AB


def solve(N, M, AB):
    S = [False for i in range(N+1)]
    T = [False for i in range(N+1)]
    for a, b in AB:
        if a > b:
            a, b = b, a
        if a == 1:
            S[b] = True
        elif b == N:
            T[a] = True
    for s, t in zip(S, T):
        if s and t:
            return "POSSIBLE"
    return "IMPOSSIBLE"


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Measured memory_bytes: 38892
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

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

  if (abs(x - a) < abs(x - b)) {
    cout << "A";
  } else {
    cout << "B";
  }
  cout << endl;
  return 0;
}


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

def ans(n):
    a=[1,3,5,7,8,10,12]
    b=[4,6,9,11]
    c=[2]
    
    if n in a:
        return 0
    if n in b:
        return 1
    if n in c:
        return 2
if ans(a)==ans(b):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
	char ch; bool ok;
	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=3010,mod=1e9+7;
char ch[maxn];
int n,m,f[maxn][maxn],tot,sum[maxn],las[maxn];
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int main()
{
	read(n),read(m);scanf("%s",ch+1);
	for(rg int i=1;i<=n+1;i++){
		sum[i]=sum[i-1],las[i]=i;
		if(ch[i]=='1')tot++,sum[i]++;
	}
	for(rg int i=1,x,y;i<=m;i++)read(x),read(y),las[x]=max(las[x],y);
	for(rg int i=1;i<=n+1;i++)las[i]=max(las[i],las[i-1]);
	f[1][sum[las[1]]]=1;
	for(rg int i=1;i<=n;i++)
		for(rg int j=0;j<=tot;j++)
			if(f[i][j]){
				int a=las[i],b=las[i+1];
				if(j)f[i+1][j+sum[b]-sum[a]-1]=add(f[i+1][j+sum[b]-sum[a]-1],f[i][j]);
				if(las[i]+1-i-j)f[i+1][j+sum[b]-sum[a]]=(f[i+1][j+sum[b]-sum[a]],f[i][j]);
		}
	printf("%d\n",f[n+1][0]);
}

Measured memory_bytes: 33920
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long ll;

#define cout (cout << setprecision(12))

bool isPalindrome(string s) {
    if (s.size() <= 1) return true;
    else if (s.front() != s.back()) return false;
    else return isPalindrome(s.substr(1, s.size() - 2));
}

int main() {
    string s;
    cin >> s;
    int N = s.size();

    if (isPalindrome(s) &&
        isPalindrome(s.substr(0, (N - 1) / 2)) &&
        isPalindrome(s.substr((N + 3) / 2 - 1, (N - 1) / 2))) {

        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int main(){
    long long n,t,a,maxi=1;
    cin>>n;
    cin>>t>>a;
    float h[n];
    f(i,0,n){
        cin>>h[i];
        h[i]=t-h[i]*0.006;
    }
    f(i,1,n){
        if(abs(a-h[i])<abs(a-h[maxi-1])){
            maxi=i+1;
        }
    }
    cout<<maxi<<endl;
    return 0;
}


Measured memory_bytes: 3596
S=input()
for i in range(len(S)//2):
    if S[i]!=S[-i-1]:
        print("No")
        exit()
for i in range(len(S)//4):
    if not S[i]==S[-i-len(S)//2-2]==S[i+len(S)//2+1]==S[-i-1]:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
 if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
}
// Union Find

template<typename T>
struct UnionFind
{
	vector<T> par;
	vector<T> rank;
	vector<T> sizes;
	UnionFind(T n):par(n),rank(n,0),sizes(n,1){
	   for(T i=0;i<n;i++){
	     par[i]=i;
	   }
	}
	T root(T x){
	  return par[x]==x?x:par[x]=root(par[x]);
	}

	bool unite(T x,T y){
	  if(x==y) return false;
	  x=root(x); y=root(y);
	  if(x==y) return false;
	  if(rank[x]<rank[y]) swap(x,y);
	  if(rank[x]==rank[y]) rank[x]++;
	  par[y]=x;
	  sizes[x]=sizes[x]+sizes[y];
	  return true;
	}
	bool same(T x,T y){
	  return root(x)==root(y);
	}
	T size(T x){
	  return sizes[root(x)];
	}
};

ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
int main(){
  ll n,m;
  cin>>n>>m;
  vll p(n);
  rep(i,n) cin>>p[i];
  UnionFind<ll> uf(2*n);
  rep(i,n){
    uf.unite(i,p[i]+n-1);
  }
  rep(i,m){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    uf.unite(a+n,b+n);
  }
  ll ans=0;
  rep(i,n){
    if(uf.same(i,i+n)) ans++;
  }
  COUT(ans);
}

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

using namespace std;
const int maxn = 400 + 5, mod = 1e9 + 7, M = (1 << 21);

int f[22][M], a[22][22], n;

int getbit(int state, int j)
{
    return ((state >> j) & 1);
}

int on(int state, int j)
{
    return (state | (1 << j));
}

int dp(int i, int state)
{
    if (i > n) return 1;
    if (f[i][state] != -1) return f[i][state];
    int &res = f[i][state] = 0;
    for(int j=1; j<=n; ++j) if (!getbit(state, j-1) && a[i][j]) 
    res = (res + dp(i + 1, on(state, j-1))) % mod;
    return res;
}

int main()
{
    #ifdef NTMA 
        freopen("abc.inp", "r", stdin);
    #endif
    memset(f, 255, sizeof(f));
    cin >> n;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j) cin >> a[i][j];
    cout << dp(1, 0);    
    return 0;
}

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

A = [[0] * N for _ in range(N)]
Al = [[0] * (N+1) for _ in range(N+1)]
Ar = [[0] * (N+1) for _ in range(N+1)]

for i in range(N) :
    a = [int(i) for i in input().split()]
    for j in range(N) :
        if i < j :
            A[i][j] = a[j-1]
        elif i > j :
            A[i][j] = a[j]

for i in range(N) :
    for j in range(i+1, N) :
        Al[j][i+1] = Al[j][i] + A[j][i]
        Ar[i][j] = Ar[i-1][j] + A[i][j]

dp = [[float('inf')] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
        
for i in range(N+1) :
    for j in range(i, N+1) :
        if dp[i][j] == float('inf') :
            continue
        l, r = 0, 0
        for k in range(j+1, N+1) :
            l += Al[k-1][i]
            r += Ar[k-2][k-1] - Ar[j-1][k-1]
            dp[j][k] = min(dp[j][k], dp[i][j] + l + r)
print(min(dp[i][N] for i in range(N+1)))

Measured memory_bytes: 127112
n = int(input())

csf = [list(map(int, input().split())) for _ in range(n-1)]

# start ~ 最終駅行くまでにかかる時間
#   timeで合算の時間を扱う
def reach(start, time):
    if start == n-1:
        return time

    # 電車が開通していない場合は開通まで待つ
    if time <= csf[start][1]:
        time = csf[start][1]
    else:
        while time % csf[start][2] != 0:
            time += 1
    return reach(start+1, time + csf[start][0])

for i in range(n-1):
    print(reach(i, 0))
print(reach(n-1, 0))

Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, a[114514], b[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n) {
		b[i + 1] = a[i] * 2 - b[i];
	}
	int memo = b[n] / 2;
	rep(i, n) {
		if (i % 2)cout << b[i] - memo << " ";
		else cout << b[i] + memo << " ";
	}
	cout << endl;
}

Measured memory_bytes: 2944
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long lng;
#define UP(i,a,b) for(int i=(a); i<=(b); ++i)
#define DOWN(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) UP(i,0,n-1)
#define ALL(a) (a).begin(), (a).end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) //NOTE: <a> must be sorted in advance

lng power(lng b, int n) {lng sol=1; while(n>0) {if(n&1) {sol=sol*b;} n>>=1; b*= b;} return sol;} //calculate b^n

const int MOD = 1000000007; //10^9+7
const double PI = 3.1415926535897932384626;

/*********** variables ************/
int N;
int coount[51][30];
vector<char> sol;
/**********************************/


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    REP(i, N) {
        string s;
        cin >> s;
        REP(k, (int)s.size()) {
            coount[i][s[k]-'a']++;
        }
    }
    REP(i, 'z'-'a'+1) {
        int cnt = MOD;
        REP(j, N) {
            cnt = min(cnt, coount[j][i]);
        }
        REP(c, cnt) {
            sol.push_back('a'+i);
        }
    }
    sort(ALL(sol));
    REP(i, (int)sol.size()) cout << sol[i];
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    int K; cin >> K;
    string S; cin >> S;
    if(SZ(S) <= K) cout << S << endl;
    else {
        string sub = S.substr(0, K);
        cout << sub << "..." << endl;
    }
    return 0;
}


Measured memory_bytes: 3632