akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	vector<int> a = { 1,6,9,36,81,216,729,1296,6561,7776,46656,59049 };
	int n; cin >> n;
	vector<int> dp(1000000, 100000);
	dp[0] = 0;
	rep(i, 0, n - 1)
	{
		rep(j, 0, 11)
		{
			if (i + a[j] <= n)dp[i + a[j]] = min(dp[i] + 1, dp[i + a[j]]);
		}
	}
	cout << dp[n] << endl;
}


Measured memory_bytes: 4096
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
using namespace std;

typedef long long ll;
ll MOD = 1e9+7;

ll x[1000];
ll y[1000];
vector<ll> arm;
char com[36];

int main()
{
	int n;
	int ans=0;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>x[i]>>y[i];
	
	bool f=true;
	//座標の合計の偶奇が一致しているかどうか調べる
	if(((ll)abs(x[0])+(ll)abs(y[0]))%2==0)
	{
		for(int i=0;i<n;i++)
		{
			if(((ll)abs(x[i])+(ll)abs(y[i]))%2!=0)
			{
				f=false;
				break;
			}
		}
	}else{
		for(int i=0;i<n;i++)
		{
			if(((ll)abs(x[i])+(ll)abs(y[i]))%2==0)
			{
				f=false;
				break;
			}
		}
	}
	//一致していなければ構成は無理
	if(!f)
	{
		cout<<-1<<endl;
		return 0;
	}
	//アームは大きい方から40本
	int armcnt=35;
	if(((ll)abs(x[0])+(ll)abs(y[0]))%2==0)
	{
		arm.push_back(1);//偶数なら1を足しておく
		armcnt--;
	}
	ll bit=1;
	for(int i=0;i<armcnt;i++)
	{
		arm.push_back(bit);
		bit*=2;
	}
	sort(arm.begin(),arm.end());
	reverse(arm.begin(),arm.end());

	//ここから答え
	cout<<35<<endl;
	for(int i=0;i<35;i++)
		cout<<arm[i]<<" ";
	cout<<endl;
	for(int i=0;i<n;i++)
	{
		//fill(com,com+36,'0');
		ll nowx=0;
		ll nowy=0;
		for(int j=0;j<35;j++)
		{
			if(abs(x[i]-nowx)<abs(y[i]-nowy))
			{
				if(y[i]<=nowy)
				{
					nowy-=arm[j];
					cout<<"D";
				}else{
					nowy+=arm[j];
					cout<<"U";
				}
			}else{
				if(x[i]<=nowx)
				{
					nowx-=arm[j];
					cout<<"L";
				}else{
					nowx+=arm[j];
					cout<<"R";
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define N 1000000007
typedef long long ll;
#define all(v) (v).begin(),(v).end()
#define sz(x) int(x.size())
#define INF 1000000000
#define MAX 100005


    
int main(){
	int n;
	cin>>n;
	int p=6;
	vector<int> an;
	int dp[MAX];
	rep(i,MAX){
		dp[i]=INF;
	}
	an.push_back(1);
	while(p<=MAX){
		an.push_back(p);
		p*=6;
	}
	p=9;
	while(p<=MAX){
		an.push_back(p);
		p*=9;
	}
	dp[0]=0;
	rep(i,n){
		rep(j,sz(an)){
			if(dp[i]==INF) continue;
			if(i+an[j]<MAX){
				if(dp[i+an[j]]>dp[i]+1) dp[i+an[j]]=dp[i]+1;
			}
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 640
N = int(input())
listClock = [int(input()) for i in range(N)]

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(x, y):
    g = gcd(x, y)
    # / で割ると小数判定になり、答えがイカれる。
    return x // g * y

ans = 1
for i in listClock:
    ans = lcm(ans, i)

print(ans)

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

int main() {
  string s; cin >> s;
  
  vector<int> stones(s.size(), 0);
  for (int i = 0; i < s.size(); i++) if (s.at(i) == 'B') stones.at(i) = 1;
  
  vector<ll> ps_stones(s.size(), 0);
  partial_sum(stones.begin(), stones.end(), ps_stones.begin());
  
  ll answer = 0;
  for (int i = 0; i < s.size(); i++) if (s.at(i) == 'W') answer += ps_stones.at(i);
  
  cout << answer << endl;
}

Measured memory_bytes: 2948
n = gets.to_i
t = []*n
0.upto(n-1) {|i| t[i] = gets.chomp.split(/:/).map(&:to_i)}

0.upto(n-1) do |i|
  a,b = t[i]
  long = b * 6
  short = a * 30 + b.to_f / 2
  r = (long - short).abs
  r = 360 - r if r > 180
  case r
  when 0...30
    puts "alert"
  when 30...90
    puts "warning"
  when 90..180
    puts "safe"
  end
end

Measured memory_bytes: 8904
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


if __name__ == "__main__":
    n = int_in()
    n %= 1000
    n = n if n == 0 else 1000 - n
    out(n)

Measured memory_bytes: 61852
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

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

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  int n; cin >> n;
  for (int k = 1; ; k++) {
    int sum = k * (k + 1) / 2;
    if (sum >= n) {
      for (int i = 1; i <= k; i++) {
        if (i == sum - n) continue;
        outl(i);
      }
      return;
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
// Problem : C - : (Colon)
// Contest : AtCoder - AtCoder Beginner Contest 168
// URL : https://atcoder.jp/contests/abc168/tasks/abc168_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#define int long long
#define db double
#define mod 1000000007
#define pb push_back
#define pp pair<int,int>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=b;i>=a;i--)
#define maxn 100005
#define ss second
#define ff first
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub uppper_bound
using namespace std;
void solve()
{
	db a,b,h,m;
	cin >>a >> b >> h >> m;
	db pi = acos(-1);
	db ang1 = ((pi/6)*h)+((pi/360)*m);
	db ang2 = (pi/30)*m;
	if(ang1 < pi/2)
		ang1=pi/2-ang1;
	else{
		ang1=(5*pi/2)-ang1;
	}
	if(ang2<pi/2)
		ang2=pi/2-ang2;
	else{
		ang2=(5*pi/2)-ang2;
	}
	db x1=a*cos(ang1);
	db y1=a*sin(ang1);
	db x2=b*cos(ang2);
	db y2=b*sin(ang2);
	db ans = (sqrt(pow(x1-x2,2)+ pow(y1-y2,2)));
	cout <<fixed << setprecision(15) << ans;
}
signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

Measured memory_bytes: 4116
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int ll;

ll n;
ll dp[101][100000];
ll find(ll arr[][2], ll curr, ll w, ll i) {
	if (i >= n)
		return 0;

	if (curr > w)
		return 0;

	if (dp[i][curr] != -1)
		return dp[i][curr];

	ll ans = find(arr, curr, w, i + 1);
	if (curr + arr[i][0] <= w)
		ans = max(ans, find(arr, curr + arr[i][0], w, i + 1) + arr[i][1]);

	dp[i][curr] = ans;
	return ans;
}


int main() {
	ll w;
	cin >> n >> w;
	memset(dp, -1, sizeof(dp));
	// vector<vector<ll>> arr(n, vector<ll>(2));
	ll arr[n][2];
	for (ll i = 0; i < n; i++)
		cin >> arr[i][0] >> arr[i][1];
	cout << find(arr, 0, w, 0);
	return 0;
}

Measured memory_bytes: 82516
#include<iostream>
#include<algorithm>
using namespace std;
bool c(int a,int b)
{
	return a>b;
}
int main()
{
	int n,k,q=0;
	cin>>n>>k;
	int l[n];
	for(int i=0;i<n;i++)
	cin>>l[i];
	sort(l,l+n,c);
	for(int i=0;i<k;i++)
	q+=l[i];
	cout<<q<<endl;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<stdio.h>
#include<string.h>

#define ll long long 
#define ull unsigned long long
#define ld long double
#define all(vec) (vec).begin(),(vec).end()
#define allr(vec) (vec).rbegin(),(vec).rend()
#define viewVec(vec) for(auto i:(vec))cout << i << " ";cout << endl
using namespace std;

ll  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;
ll ans = 0, sum = 0, mn = 1e18, mx = 0, cnt = 0;
const ll M = 1000000007;

map<char, int>mp;
vector<int>vec;
vector<int>vec2;
vector<int>res;


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


/*(constructive)*/

vector<int>adj[10];
void dfs(vector<int>visited, int node,int height)
{
	visited[node] = 1;
	for (int i = 0; i < adj[node].size(); i++)
	{
		if (!visited[adj[node][i]])
		{
			dfs(visited, adj[node][i], height + 1);
		}
	}
	if (height == n)ans++;
}

int main()
{
	vector<int>visited(10,0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(visited, 1,1);
	cout << ans << endl;
	return 0;
}

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

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

  int ans = 0;
  rep(_, N) {
    int x;
    cin >> x;
    ans += 2 * min(x, K - x);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
import java.util.*;
class Main{
	public static void main(String[]$){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		long l=1;
		for(int i=0;i<n;++i) {
			l=lcm(l,s.nextLong());
		}
		System.out.println(l);
	}
	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	static long lcm(long a, long b) {
		return a/gcd(a,b)*b;
	}
}

Measured memory_bytes: 23892
#!/usr/bin/env python3
import sys
INF = float("inf")

import math
import collections


def factorial(n):
    # 試し割りによる素因数分解
    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def solve(N: int, P: int):
    counter = factorial(P)
    ans = 1
    for k in counter:
        if counter[k] >= N:
            ans *= k**(counter[k]//N)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    solve(N, P)


if __name__ == '__main__':
    main()


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

int main()
{
	LL N;
	in >> N;

	LL ans = 1145148101919;
	for (LL A = 1; A < N; ++A)
	{
		LL B = N - A;
		LL sumA = 0, sumB = 0;
		auto A_ = A;
		while (A > 0)
		{
			sumA += A % 10;
			A /= 10;
		}
		while (B > 0)
		{
			sumB += B % 10;
			B /= 10;
		}
		A = A_;
		ans = std::min(ans, sumA + sumB);
	}

	out << ans << std::endl;
}


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

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        tx: [f64; 2]
    }
    println!("{}", solve(tx[0], tx[1]));
}

fn solve(t: f64, x: f64) -> f64 {
    t / x
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(){
    int X; cin>>X;
    for(int i=X;;i++){
        bool can=true;
        for(int j=2;j<i;j++){
            if(i%j==0){
                can=false;
                break;
            }
        }
        if(can){
            cout<<i;
            return 0;
        }
    }
    return 0;
}

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

#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

#define Debug(x) cout<<(#x)<<" >> "<<(x)<<endl

using namespace std;

ll fastpow(ll angka,ll pangkat,ll MOD){
	ll res=1;
	while(pangkat){
		if(pangkat&1) res=(res*angka)%MOD;
		angka=(angka*angka)%MOD;
		pangkat=pangkat>>1;
	}
	return res;
}

ll fastpow(ll angka,ll pangkat){
	ll res=1;
	while(pangkat){
		if(pangkat&1) res=(res*angka);
		angka=(angka*angka);
		pangkat=pangkat>>1;
	}
	return res;
}

ll gcd(ll angka1,ll angka2){
	while(angka2){
		swap(angka1,angka2);
		angka2=angka2%angka1;
	}
	return angka1;
}

ll lcm(ll angka1,ll angka2){
	return (angka1/gcd(angka1,angka2))*angka2;
}




void solve(){
	
	int x;
	cin>>x;
	
	if(x>=400 && x<=599) cout<<8<<endl;
	else if(x>=600 && x<=799) cout<<7<<endl;
	else if(x>=800 && x<=999) cout<<6<<endl;
	else if(x>=1000 && x<=1199) cout<<5<<endl;
	else if(x>=1200 && x<=1399) cout<<4<<endl;
	else if(x>=1400 && x<=1599) cout<<3<<endl;
	else if(x>=1600 && x<=1799) cout<<2<<endl;
	else if(x>=1800 && x<=1999) cout<<1<<endl;
	
	
}

int main(){
	
	fastio();

	int t=1;
//	cin>>t;
	
	for(int tt=0;tt<t;tt++){
//		cout<<"Case #"<<tt+1<<": ";solve();
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 3636
import copy     
n,m = map(int,input().split())
count = 0
ab = []
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

for i in range(m):
    root = [[] for i in range(n)]
    done = [False]*n
    cd = copy.copy(ab)
    cd.pop(i)
    for j in range(m-1):
        a, b = cd[j]
        root[b-1].append(a-1)
        root[a-1].append(b-1)
        
    stack=[0]
    while len(stack):
        v = stack.pop()
        for k in root[v]:
            if done[k]: continue
            done[k] = True
            stack.append(k)
    if False in done:
        count += 1

print(count)

Measured memory_bytes: 40560
/* 
 * Created by solzard on 2020-03-05.
 * 
 */
#include <iostream>

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

  int N;
  std::cin >> N;
  std::cout << (N + 1) / 2 << "\n";
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<numeric>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=1e9+7;
const int MOD=998244353;
const int N = 1e6 + 5;
const ll inv2=499122177;
const double pi=acos(-1);
ll k[100005],s[100005];
ll qpmod(ll a,ll n)
{
	ll ret=1;
	while(n)
	{
	   	if(n&1)
	      	ret=(ret*a)%MOD;
	   	a=(a*a)%MOD;
		n>>=1;
	}
	return ret;
}
int main()
{
	ll n;
	int flag=1;
	scanf("%lld",&n);
	memset(k,0,sizeof(k));
	for(ll i=0;i<n;i++)
	{
		scanf("%lld",&s[i]);
		if(s[i]==0&&i!=0)
			flag=0;
		if(s[0]!=0)
			flag=0;
		k[s[i]]++;
	}
	if(flag==0)
		printf("0\n");
	else
	{
		ll ans=1;
		for(ll i=1;i<n;i++)
		{
			ans=(ans*qpmod(k[i],k[i+1]))%MOD;
		}
		printf("%lld\n",ans);
	}
    return 0;
}



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

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

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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

char alpha[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'};

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

int main(){
    vector<ll> lis(2, 0);
    cin >> lis[0] >> lis[1];
    sort(ALL(lis));
    ll k =lis[0] + lis[1];
    if(k % 2 == 0){
        cout << k /2 << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    ll n;
    cin >> n;
    ll ans = 0;
    for ( ll i = 1; i <= n; ++i ) {
        if ( i % (ll)3 == 0LL || i % (ll)5 == 0LL ) {
            continue;
        }
        ans += i;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>

int min(int num[]){
  int tempmin, index;
  tempmin=num[0];
  index=0;

  for(int i=0; i<5;i++){
    if(num[i]<tempmin&&num[i]!=0){
      tempmin=num[i];
      index=i;
    }
  }
  return index;
}

int main(){
  int num[5];
  scanf("%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &num[4]);
  int num_r[5]={num[0]%10,num[1]%10,num[2]%10,num[3]%10,num[4]%10};
  int index_min=min(num_r);
  int sum=0;
  for(int i=0;i<5;i++){
    if(i!=index_min){
      if(num_r[i]==0){
        sum+=num[i];
      }else{
        sum+=((num[i]/10+1)*10);
      }
    }
  }
  sum+=num[index_min];
  printf("%d\n",sum);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <new>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <iomanip>

typedef long long ll;
typedef long double ld;

using namespace std;
using Graph = vector<vector<ll>>;

#define rep(i, N) for (ll i = 0; i < (ll)(N); ++i)
#define ALL(a) (a).begin(),(a).end()

const ll inf = 1e18+7;
const ll mod = 1e9+7;

ll GetDigit(ll num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

int main(){
    double N;
    cin >> N;
    cout << ceil(N/2) << endl;
    return 0;
}


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

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T> p) {
    out << "(" << p.first << "," << p.second << ")";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cout << pow(n, 3) << endl;
    return 0;
}



Measured memory_bytes: 892
n = int(input())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
ans = 0
for i in range(n):
    if sum(a1[:i+1])+sum(a2[i:])-ans>0:
        ans = sum(a1[:i+1])+sum(a2[i:])

print(ans)

Measured memory_bytes: 3060
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        s: String
    };

    let weeks = vec!["SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"];
    let res = 7 - weeks.into_iter().position(|x| x == &s).unwrap();
    println!("{}", res);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 2216
s = input()
q = int(input())

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0

p = ""
while idx < q:
    if t[idx] == 1:
        s, p = p, s
    else:
        if f[idx] == 1:
            p += c[idx]
        else:
            s += c[idx]
    idx += 1

p = p[::-1]
s = p + s
print(s)



Measured memory_bytes: 9076
n, m = list(map(int, input().split()))

E = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    e = E.get(a, None)
    if e is None:
        e = []
    e.append(b)
    E[a] = e
    e = E.get(b, None)
    if e is None:
        e = []
    e.append(a)
    E[b] = e


def foo(E):
    for i in range(1, n):
        if i in E and 1 in E[i] and n in E[i]:
            return True
    return False

if foo(E):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Measured memory_bytes: 61304
package main

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

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatVec(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}

func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

func Count(C [][]int) []int {
  Z, K := 0, 1
  for i := range C[2:] {
    Z = (Z + K * C[i + 1][1] % p) % p
    K = (K + Z * (C[i + 2][0] - C[i + 1][0]) % p) % p
  }
  return []int{Z, K}
}

const p = 1000000007

func Solve() {
  var N int
  NextInt(&N)
  var A []int
  NextIntVec(&A)
  C := make([][][]int, 1 << uint(20))
  for i := range C {
    C[i] = make([][]int, 0)
    C[i] = append(C[i], []int{0, 0})
  }
  Z := 1
  b := 0
  for _, a := range A {
    b ^= a
    if b == 0 {
      Z++
      continue
    }
    n := len(C[b]) - 1
    if C[b][n][0] < Z {
      C[b] = append(C[b], []int{Z, 0})
      n++
    }
    C[b][n][1]++
  }
  if b == 0 {
    for i := 1; i < len(C); i++ {
      C[i] = append(C[i], []int{Z, 0})
    }
  }
  ans := 1
  if b != 0 {
    ans = Count(C[b])[1]
  } else {
    for i := 2; i < Z; i++ {
      ans = 2 * ans % p
    }
    for _, c := range C[1:] {
      ans = (ans + Count(c)[0]) % p
    }
  }
  Write(ans)
}

func main() {
  Solve()
  Output()
}

Measured memory_bytes: 182636
#include <stdio.h>

long exist(long y, long tag){
  while(y != 0){
    if(tag == y % 10)
      return 1;
    else y=y/10;
  }
  return 0;
}

long count753(long x, long y){
  if (x < y)
    return 0;
  else{
    long yes = exist(y,3)&&exist(y,5)&&exist(y,7);
    long ret = yes + count753(x,y*10+3) + count753(x,y*10+5) + count753(x,y*10+7);
    return ret;
  }
}

int main(){
  long x;
  scanf("%ld",&x);
  printf("%ld\n",count753(x,0));

  return 0;
}


Measured memory_bytes: 128
n,k = map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(k)]

mod = 998244353

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    bit = BitImos(len(li))
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)

b = BitImos(n)
b.add(0,1,1)

for i in range(n):
    tmp = b.get(i)
    tmp %= mod
    for l1,r1 in lr:
        if i + l1 < n:
            b.add(i+l1, min(i+r1+1, n), tmp)

print(b.get(n-1) % mod)


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

using namespace std; 

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

int main(){
 long n,a,b;
  cin >> n >> a >> b;
  long v[n];
  rep(i,n) cin >> v[i];
  
  sort(v,v+n);

  long c[n+1][n+1];
    rep(i,n+1){
     rep(j,i+1){
      if(j==0||j==i) c[i][j]=1;
      else c[i][j]=c[i-1][j-1]+c[i-1][j];
     }
  }
  
  double res=0.0;
  rep(i,a) res+=v[n-1-i];
     res/=double(a);
  
  auto x=upper_bound(v,v+n,v[n-a])-lower_bound(v,v+n,v[n-a]);
   
  if(v[n-1]!=v[n-a]) {
    auto y=upper_bound(v+(n-a),v+n,v[n-a])-lower_bound(v+(n-a),v+n,v[n-a]);
    cout << setprecision(24) << res << endl;
    cout << c[x][y] << endl;
  }
  else {
    long com=0;
   rep(i,b-a+1) {
     if(a+i>x) continue;
     com+=c[x][a+i];
   }
   cout << setprecision(24) << res << endl;
   cout << max(long(1),com) << endl;
  }
  
}

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

using namespace std;

int const INF = 1<<28;

int main() {
  int N;
  while(cin >> N && N) {
    vector<vector<int> > vec(N, vector<int>(N+1));
    for(int i=0; i<N; i++)
      for(int j=0; j<N+1; j++)
	cin >> vec[i][j];
    
    vector<int> dp(1<<N, INF);
    dp[0] = 0;
    for(int S=0; S<(1<<N); S++) {
      for(int i=0; i<N; i++) {
	if(S>>i & 1) continue;
	dp[S+(1<<i)] = min(dp[S+(1<<i)], dp[S] + vec[i][0]);
	for(int j=0; j<N; j++) {
	  if(!(S>>j & 1)) continue;
	  dp[S+(1<<i)] = min(dp[S+(1<<i)], dp[S] + vec[i][j+1]);
	}
      }
    }
    
    cout << dp[(1<<N)-1] << endl;
    
  }
  return 0;
}

Measured memory_bytes: 1476
tmp = []
cnt = "0"
while cnt != [0, 0]
  i = gets.chomp.split.map(&:to_i)
  tmp.push(i)
  tmp.flatten!
  cnt = i
end
# p "tmp = #{tmp}"

num_of_element = -1 + tmp.length/2
# tmp.delete(tmp.length)
# p "num_of_element = #{num_of_element}"
# p "tmp = #{tmp}"

i = 0
num_of_element.times do
  x = tmp[i]
  y = tmp[i+1]
  if x <= y
    puts "#{x} #{y}"
  else
    puts "#{y} #{x}"
  end
  i = i + 2
end

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

using namespace std;

int main()
{
    int n,x;cin>>n>>x;
    vector<int> l(n+1);
    for(int i=1;i<=n;i++) cin>>l[i];
    vector<int> d(n+2, 0);
    int ret = 1;
    for(int i=2;i<=n+1;i++)
    {
        d[i] = d[i-1] + l[i-1];
        if(d[i]<=x) ret++;
    }
    cout << ret << endl;
}

Measured memory_bytes: 256
h, w = map(int, input().split())
field = [input() for _ in range(h)]
MOD = 10 ** 9 + 7

dp = [[0] * w for _ in range(h)]
dp[0][0] = 1

for i in range(1, w):
    if field[0][i] == ".":
        dp[0][i] = dp[0][i-1] 

for i in range(1, h):
    if field[i][0] == ".":
        dp[i][0] = dp[i-1][0]

for row in range(1, h):
    for col in range(1, w):
        if field[row][col] == ".":
            dp[row][col] = (dp[row-1][col] + dp[row][col-1]) % MOD
print(dp[-1][-1])



Measured memory_bytes: 51568
import numpy as np
w, h, n = map(int, input().split())
arr = np.zeros((w, h))
for i in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        arr[:x] = np.ones((x, h))
    elif a == 2:
        arr[x:] = np.ones((w - x, h))
    elif a == 3:
        arr[:, :y] = np.ones((w, y))
    elif a == 4:
        arr[:, y:] = np.ones((w, h - y))
print(int(w * h - np.sum(arr)))

Measured memory_bytes: 12504
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define IOS {ios :: sync_with_stdio(false); cin.tie(0);cout.tie(0); }
#define F first
#define S second
#define pb push_back
typedef long double ld;
#define deci(n) cout << fixed << setprecision(n);
typedef long long ll;

#define mem0(x)  memset(x,0,sizeof(x));
#define memm1(x) memset(x,-1,sizeof(x));
#define all(a) a.begin(), a.end()
#define pll pair<ll, ll>
#define bits(x) __builtin_popcount(x)
#define fori(n)  for (ll i = 0; i < n; i++)
#define fori2(n) for(ll i=1;i<=n;i++)
#define forj(n)  for (ll j = 0; j < n; j++)
#define forj2(n) for(ll j=1;j<=n;j++)
#define fork(n)  for (ll k = 0; k < n; k++)
#define fork2(n) for(ll k=1;k<=n;k++)
#define vll vector <ll>
#define mll map <ll, ll>
#define vpll vector <pll>
const ll md = 1e9 + 7;

#define BSET(a, p) ((a) | (1ll << (p)))
#define BCHK(a, p) ((a) & (1ll << (p)))
#define BXOR(a, p) ((a) ^ (1ll << (p)));
#define BREM(a, p) (BCHK(a, p)?(BXOR(a, p)):(a))
#define BSHO(a, N) (bitset<N>(a))
// const ll N = 100005;
// ll fac[N] = {1};
// #define calfac for(ll i=1  ;i<N;i++) fac[i] = (fac[i-1]*i)%md;
// ll C[N+1][M+1]; 
// void  ncr(){
//     ll n = N,k = M; 
//     for (ll i = 0; i <= n; i++) { 
//         for (ll j = 0; j <= min(i, k); j++) { 
//             if (j == 0 || j == i)  C[i][j] = 1; 
//             else C[i][j] = C[i - 1][j - 1] +  C[i - 1][j]; 
//         } 
//     } 
// } 


#define RBTTYPE int
#define ordered_set tree<RBTTYPE, null_type, less<RBTTYPE>, rb_tree_tag,tree_order_statistics_node_update> 
// Ordered set docs:
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
ll modexp(ll x, ll ex) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % md;
        ex >>= 1ll;
        x = (x * x) % md;
    }
    return ans;
}
ll modInv(ll a)
{
    return pow(a,md-2);
}
 
// ll nCr(ll n,ll r)
// {
//     return (fac[n]*modInv((fac[r]*fac[n-r])%md))%md;
// }

 
ll po(ll x,ll n){
    if(n==0) return 1;
    if(n%2==1) return (x*po(x,n-1));
    else {
        ll k=po(x,n/2);
        return (k*k);
    }
}
 
ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
}
 
 ll a[200005];
int32_t main(){
    IOS;
    ll n,sum=0;
    cin >> n;
    fori(n) cin >> a[i];
    fori2(n-1){
        if(a[i] < a[i-1]) {
            sum += (a[i-1]-a[i]);
            a[i]=a[i-1];
        }
    }
    cout << sum <<"\n";
} 

Measured memory_bytes: 5256
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

int main()
{
	int n;
	scanf ("%d", &n );
	while (n-- ){
		string train = "";
		cin >> train;
		int len = train.length();
		set<string> kind;
		kind.clear();
		kind.insert (train );
		for (int j = 1; j < len; j++ ){
			string dv1o = train.substr (0, j ), dv1r = dv1o;
			string dv2o = train.substr (j ), dv2r = dv2o;
			reverse (ALL (dv1r ) );
			reverse (ALL (dv2r ) );
			kind.insert (dv2o+dv1o );
			kind.insert (dv1o+dv2r );
			kind.insert (dv2r+dv1o );
			kind.insert (dv1r+dv2o );
			kind.insert (dv2o+dv1r );
			kind.insert (dv1r+dv2r );
			kind.insert (dv2r+dv1r );
		} // end rep
		printf ("%d\n", kind.size() );
	} // end loop
		
	return 0;
}

Measured memory_bytes: 1028
N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N):
    if (i==0):
        ans.append(0)
        continue
    if (A[i-1] > A[i]):
        m = A[i-1] - A[i]
        A[i] += m
        ans.append(m)
    else:
        ans.append(0)
print(sum(ans))

Measured memory_bytes: 32184
N, L = map(int, input().split())
A = []
B = []
for i in range(N):
  A.append(L+i)
  B.append(abs(L+i))
C = sum(A[0:N])
D = max(A)
if D>0 :
  E=min(B)
else:
  E=D
print(C-E)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
typedef pair<long long , long long> P;
typedef long long ll;
typedef long long lint;
#define REP(i, n) for(long long (i)=0; (i)<(n); ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = static_cast<long long>(1e9) + 7LL;
const long long INF = 1234567891234567890LL;
long long eulerFunc(long long n){
    vector<long long> factors;
    { 
        long long tn = n;
        for(long long i=2; i*i<=n; i++){
            if(tn%i==0) factors.emplace_back(i);
            while(tn%i==0){
                tn/= i;
            }
        }
        if(tn>1) factors.emplace_back(tn);
    }
    int num = factors.size();
    long long res = 0;
    for(long long mask=0; mask<(1LL<<num); mask++){
        long long val = 1LL;
        int cnt = 0;
        for(int i=0; i<num; i++){
            if(mask & (1LL<<i)){
                cnt++;
                val *= factors[i];
            }
        }
        if(cnt==0) continue;
        if(cnt%2==0){
            res -= n/val;
        }
        else{
            res += n/val;
        }
    }
    return n-res;
}
signed main(){
    long long n;
    cin >> n;
    cout << eulerFunc(n) << endl;
    return 0;
}


Measured memory_bytes: 3136
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#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 P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;
const double PI = acos(-1.0);


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * b / g;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

using Graph = vector<VE>;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n; cin >> n;
	VE a(n-1);
	rep(i, n-1)cin >> a[i];
	int ans = 0;
	ans += a[0]; ans += a[n - 2];
	rep(i, n - 2) {
		ans += min(a[i], a[i + 1]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
alphabet_small = [chr(i) for i in range(97, 97+26)] #アルファベッドの小文字
answer =[[] for i in range(26)]
n = int(input())
for i in range(n):
    S = input()
    box = [0]*26
    for s in S:
        box[alphabet_small.index(s)] += 1

    for i in range(26):
        answer[i].append(box[i])

ans = ""
for i in range(26):
    answer[i].sort()
    ans = ans + alphabet_small[i]*answer[i][0]

print(ans)

Measured memory_bytes: 39920
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};


bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int K;
  string S;
  cin >> S;
  cin >> K;
  vector<string> v(0);
  REP(i,S.size()){
    v.push_back(S.substr(i,1));
  }
  if(S.size() >= 2){
  REP(i,S.size()-1){
    v.push_back(S.substr(i,2));
  }
  if(S.size() >= 3){
  REP(i,S.size()-2){
    v.push_back(S.substr(i,3));
  }
  if(S.size() >= 4){
  REP(i,S.size()-3){
    v.push_back(S.substr(i,4));
  }
  if(S.size() >= 5){
  REP(i,S.size()-4){
    v.push_back(S.substr(i,5));
  }
  }
  }
  }
  }
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  
  
  cout << v[K-1] << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


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

for i in range(n):
    v = a[i]
    j = i - 1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = v
    print(*a)


Measured memory_bytes: 5976
// Problem : E - Crested Ibis vs Monster
// Contest : AtCoder - AtCoder Beginner Contest 153
// URL : https://atcoder.jp/contests/abc153/tasks/abc153_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,b,a) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
#define cs(ans) setprecision(10)<<fixed<<ans

 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ld pii=3.14159265359;
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int H,N;
    cin>>H>>N;
    vpi v;
    F0R(x,N)
    {
    	int a,b;
    	cin>>a>>b;
    	v.pb(mp(a,b));
    }
    sort(all(v));
    // int mx=v.back().f,mn=v[0].f;
	vi cst(H+1);
	FOR(x,1,H+1)
	{
		int res=INT_MAX;
		F0R(y,N)
		{
			if(x-v[y].f<0)
				res=min(res,v[y].s);
			else
				res=min(res,v[y].s+cst[x-v[y].f]);
		}
		cst[x]=res;
	}
	cout<<cst[H]<<endl;
	return 0;
	//CHECK CORNER CASES
}
// read the question correctly (ll vs int)
// template by bqi343




Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int dx[]={0,-1,-1,0,1,1};
int dy[]={1,0,-1,-1,0,1};
int obstacle[200][200], visited[200][200];
int q[40000], top, bottom;

int main(void)
{
    int t, n;
    while (scanf("%d%d", &t, &n), t) {
        int x, y, res;
        memset(obstacle, 0, sizeof(obstacle));
        memset(visited, 0, sizeof(visited));
        while (n--) {
            scanf("%d%d", &x, &y);
            obstacle[x+100][y+100]=1;
        }
        scanf("%d%d", &x, &y);

        res=top=bottom=0;
        x+=100, y+=100;
        q[bottom++]=x*1000+y;
        visited[x][y]=1;
        while (top<bottom) {
            int i, k;
            x=q[top]/1000;
            y=q[top]%1000;
            k=visited[x][y];
            ++top;
            for(i=0;i<6;++i) {
                int nx=x+dx[i], ny=y+dy[i];
                if (!visited[nx][ny] && !obstacle[nx][ny] && k<=t) {
                    q[bottom++]=nx*1000+ny;
                    visited[nx][ny]=k+1;
                }
            }
        }
        printf("%d\n", top);
    }
    return 0;
}

Measured memory_bytes: 932
#include<bits/stdc++.h>
using namespace std;
#define max 10005
int d[max];
int p[max];
char clr[max];
int mx;
int node,edge,x,y;
int arr[max];
void  bfs(vector<int>v[],int s,int node)
{
    queue<int>q;
    int u,i;
    for(int i=0; i<node; i++)
    {
        d[i]=0;
        p[i]=-1;
        clr[i]='w';
    }
    clr[s]='g';
    d[s]=0;
    p[s]=-1;
    q.push(s);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            int x=v[u][i];
            if(clr[x]=='w')
            {
                clr[x]='g';
                d[x]=d[u]+1;
                p[x]=u;
                q.push(x);
            }
        }
        clr[u]='b';
    }
}
int main()
{
    int x,y,dis;
    vector<int>v[max];
    cin>>node>>x>>y;
    v[x-1].push_back(y-1);
    v[y-1].push_back(x-1);
    for(int i=0;i<(node-1);i++)
    {
        v[i].push_back(i+1);
        v[i+1].push_back(i);
    }
    for(int i=0;i<node;i++)
    {
       bfs(v,i,node);
       for(int j=i+1;j<node;j++)
       {
           arr[d[j]]++;
       }
    }
    for(int i=1;i<node;i++)
        cout<<arr[i]<<endl;
}


Measured memory_bytes: 640
def test():
    n = int(input())
    s = input()
    result = 0; x = 0
    for i in s:
        if i == "I":
            x += 1
        elif i == "D":
            x -= 1
        result = max(result,x)
    print(result)


if __name__ == "__main__":
    test()


Measured memory_bytes: 2940
from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    H, W = map(int, input().split())
    ls = deque([])
    D = [[True] * (W+2)]
    D += ([[True] + [False]*W + [True] for i in range(H)])
    D.append([True]*(W+2))
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == "#":
                ls.append([i+1, j+1, 0])
                D[i+1][j+1] = True

    while len(ls) > 0:
        h, w, depth = ls.popleft()
        if not D[h+1][w]:
            ls.append([h+1, w, depth+1])
            D[h+1][w] = True
        if not D[h-1][w]:
            ls.append([h-1, w, depth+1])
            D[h-1][w] = True
        if not D[h][w+1]:
            ls.append([h, w+1, depth+1])
            D[h][w+1] = True
        if not D[h][w-1]:
            ls.append([h, w-1, depth+1])
            D[h][w-1] = True

    return depth
    
print(bfs())

Measured memory_bytes: 168460