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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

ll dp[1001001];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; string s; cin>>n>>s;
  s+='a';
  
  rep(i,n){
    if( (s[i]=='O'&&s[i+1]=='X') || (s[i]=='X'&&s[i+1]=='O') ) chmax(dp[i+2], dp[i]+1);
    chmax(dp[i+1], dp[i]);
  }
  
  ll ans=0;
  irep(i,n,n+3){
    chmax(ans, dp[i]);
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 4152
N=int(input())
lv=list(map(int,input().split()))
lv.sort()
ans=lv[0]
#print(ans)
#print(lv[0],lv[1])
for i in range(1,N):
    ans=(ans+lv[i])/2
    #print("lv[i]",lv[i])
print(ans)
#print((3+4)/2)


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

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=100005;
int n,rt[2];
vector<int>edge[2][maxn],nedge[maxn];
int ans[maxn];
bool vis[maxn];

int dfs(int x,int tp){
	int cur=(int(edge[tp][x].size())&1)?0:x;
	rep(i,int(edge[tp][x].size())){
		int y=edge[tp][x][i];
		int cur2=dfs(y,tp);
		if(cur2){
			if(cur)nedge[cur].pb(cur2),nedge[cur2].pb(cur),cur=0;
			else cur=cur2;
		}
	}
	return cur;
}

void dfs2(int x,int d){
	vis[x]=true;
	ans[x]=d;
	rep(i,int(nedge[x].size())){
		int y=nedge[x][i];
		if(!vis[y])dfs2(y,-d);
	}
}

int main(){
	scanf("%d",&n);
	rep(tp,2){
		REP(i,n){
			int p;scanf("%d",&p);
			if(p<0)rt[tp]=i;
			else edge[tp][p].pb(i);
		}
	}
	REP(i,n)if((int(edge[0][i].size())&1)!=((int(edge[1][i].size()))&1)){
		puts("IMPOSSIBLE");
		return 0;
	}
	dfs(rt[0],0);
	dfs(rt[1],1);
	REP(i,n)if(!vis[i]&&(!(int(edge[0][i].size())&1)))dfs2(i,1);
	puts("POSSIBLE");
	REP(i,n)printf("%d%c",ans[i],i==n?'\n':' ');
	return 0;
}

Measured memory_bytes: 16512
N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)


Measured memory_bytes: 171912
function shcdHash( key )
{
  if( 'S' == key ) {
    return 0;
  } else if( 'H' == key ) {
    return 1;
  } else if( 'C' == key ) {
    return 2;
  } else if( 'D' == key ) {
    return 3;
  } else {
    return 1;
  }
} 
var input = '';
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  input += chunk;
});

readable.on( 'end', function() {
  var cards = { S:[] , H:[], C:[], D:[] };
  var shcd = [ 'S', 'H', 'C', 'D' ];
  var hash = { 'S':0, 'H':1, 'C':2, 'D':3 };
  for( var key in cards ) {
    for( var i=1; i<=13; i++ ) {
      cards[key].push( i );
    }
  }
  var data = input.split( '\n' );
 
  for( var i=1; i<data.length; i++ ) {
    var p = data[i].split( ' ' );
    var k = shcdHash( p[0] );
    var res = cards[ shcd[k] ].indexOf( Number( p[1] ) );
    if( -1 != res ) {
        cards[ shcd[k] ].splice( res, 1 );
    }
  }
  for( var i=0; i<4; i++ ) {
    for( var j = 0; j<cards[ shcd[i] ].length; j++ ) {
      console.log( shcd[i]+" "+cards[ shcd[i] ][j] );
    }
  }
});

Measured memory_bytes: 7640
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;

int A, B, C, D, E, F;
string S, Sa, Sb, Sc;
long long int V[100000];
long long int X[100000];
typedef pair<double,int> Pi;
Pi N[100000] = {};
int main() {
	cin >> A;
for(int i = 0;i < A;i++)cin >> V[i];
sort(V, V + A, greater<int>());
B = 0;
for(int i = 1;i < A;i++)B += V[i];
if(B > V[0])cout << "Yes" << endl;
else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 1792
use std::io;
use std::str::FromStr;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn input_vec() -> Vec<u64> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn main() {
    let n: u64 = input();
    let mut h_vec = input_vec();
    let mut max = 0;
    let mut count = 0;
    // h_vec.reverse();
    for h in h_vec {
        if h >= max {
            max = h;
            count += 1;
        }
    }
    println!("{}", count);
}


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

int main()
{
	int N;
	bool flag=0;
	cin >> N;
	vector<string> data;
	data.assign(N, "");
	for (int i = 0; i < N; i++) {
		cin >> data[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) { continue; }
			if (data[i] == data[j]) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) { break; }
	}
	if (flag) {
		cout << "No" << endl;
		return 0;
	}

	flag = 0;
	for (int i = 1; i < N; i++) {
		if (!(data[i - 1].back() == data[i].front())) {
			flag = 1;
			break;

		}
	}
	if (flag) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}



	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<utility>
#include<set>
using namespace std;

vector<long int>r;
vector<long int>a;
vector<long int>b;
vector<long int>size;
vector<long int>ans;

long int n,m;

long int root(long int x){
  if(r.at(x)==x)return x;
  else{
    long int p=root(r.at(x));
    r.at(x)=p;
    return p;
  }
}

long int getsize(long int x){
  return size.at(root(x));
}

void conect(long int x, long int y){
  long int p=root(x);
  long int q=root(y);
  if(p==q)return;
  size.at(q)+=size.at(p);
  r.at(p)=q;
  size.at(p)=0;
  return;
}

bool notsame(long int x,long int y){
  if(root(x)!=root(y))return true;
  else return false;
}

int main(void){
  int i;
  cin >> n >> m;
  r=vector<long int>(n);
  a=vector<long int>(m);
  b=vector<long int>(m);
  size=vector<long int>(n,1);
  ans=vector<long int>(m+1,0);
  ans.at(m)=n*(n-1)/2;
  for(i=0;i<m;i++)cin >> a.at(i) >> b.at(i);
  for(i=0;i<n;i++)r.at(i)=i;
  for(i=m-1;i>-1;i--){
    if(notsame(a.at(i)-1,b.at(i)-1)){
      ans.at(i)=ans.at(i+1)-getsize(a.at(i)-1)*getsize(b.at(i)-1);
      conect(a.at(i)-1,b.at(i)-1);
    }else{
      ans.at(i)=ans.at(i+1);
    }
  }
  for(i=1;i<=m;i++)cout << ans.at(i) << endl;
}


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

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

    vector<string> s(n);
    rep (i, n)
        cin >> s[i];

    int ans = 1;
    sort(s.begin(), s.end());
    rep (i, n - 1)
        if (s[i] == s[i + 1])
            continue;
        else
            ans++;

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

Measured memory_bytes: 9560
#include <bits/stdc++.h>    //super header :標準ライブラリ,STLを全てインクルード
using namespace std;

struct Data {
    long long a;
    long long b;
};

int main(){
    int N,M;
    cin >> N >> M;
    vector<Data> v = {};
    for(int i = 0; i < N; i++)
    {
        int a;cin >> a;
        int b;cin >> b;
        v.push_back({a,b});
    }

    sort(v.begin(),v.end(), [](const auto& x, const auto& y){
        return x.a < y.a;
    });
    
    int sum = 0;
    long long ans = 0;
    for(int i = 0; i < N; i++)
    {
        sum += v[i].b;
        ans += v[i].a * v[i].b;
        if(sum >= M){
            ans -= v[i].a * (sum-M);
            break;
        }
    }
    cout << ans << "\n";
}


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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t r, d, x;
  std::cin >> r >> d >> x;
  for (int64_t i = 0; i < 10; i++) {
    x = r * x - d;
    std::cout << x << std::endl;
  }
  return 0;
}

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

int main() {
//int a,b,c;
string s;
char ca='0',cb='0';
cin >> s;
int ia=0,ib=0;
ca=s.at(0);
for(int i=0; i<4; i++){
if(s.at(i)==ca){
ia++;
  }if(i==ia&&s.at(i)!=ca){
         cb=s.at(i);
  } if(s.at(i)==cb){
    ib++;
  }
}
if(ia==2&&ib==2){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string u, d;
    cin >> u >> d;
    for(int i = 0;i < 3;i++) {
        if(u[i]!=d[2-i]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define ll long long
#define endl "\n"
#define print_array(name,n) for(ll o=0;o<n;o++) cout<<name[o]<<" "
#define fr(i,f,t) for(ll i=(f);i<t;i++)
#define fb(i,f,t) for(ll i=(f);i>=t;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 2e18
bool sortbysecond(const pair<int,int> &a,const pair<int,int> &b){
	return (a.ss>b.ss);
}
template <typename T>
string NumberTostring(T Number )
{
	ostringstream ss;
	ss<<Number;
	return ss.str();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,k;
    cin>>n>>k;
    vector<ll> vec(n,0);
    vector<ll> visit(n,0);
    for(int i=0;i<n;i++){
    	cin>>vec[i];
    	vec[i]--;
    }
    vector<ll> steps;
    vector<ll> data(n,0);
    ll stp = 0;
    ll cp;
    ll cur = 0;
    while(visit[cur]==0){
    	// cout<<cur<<endl;
    	steps.pb(cur);
    	visit[cur]=1;
    	data[cur] = stp;
    	cur = vec[cur];
    	stp++;
    }
    
    ll sc = stp-data[cur];
    cp = cur;
    ll trch = data[cur];
    // cout<<sc<<" size of cycle"<<endl;
    // cout<<trch<<endl;
    // cout<<cur<<endl;
    if(k<trch){
    	cout<<steps[k]+1<<endl;
    }
    else{
    	// cout<<"hello"<<endl;
    	int temp_k = (k-trch)%sc;
    	// cout<<temp_k<<endl;
    	cout<<steps[trch+temp_k]+1<<endl;
    }
    return 0;
}

Measured memory_bytes: 10020
#include<iostream>

using namespace std;

int n, a[109];

void bubbleSort(){
  int cnt=0;
  for(int i=0;i<n;i++){
    for(int j=n-1;j>=i+1;j--){
      if(a[j]<a[j-1]){
        cnt++;
        int tmp=a[j];
        a[j]=a[j-1];
        a[j-1]=tmp;
      }
    }
  }
  for(int i=0;i<n;i++)cout << a[i] << (i<n-1?' ': '\n');
  cout << cnt << endl;
}

int main(){
  cin >> n;
  for(int i=0;i<n;i++)cin >> a[i];
  bubbleSort();
}


Measured memory_bytes: 3092
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		long ans = 0;

		Scanner sc = new Scanner(System.in);
		int  m = sc.nextInt();
		int  d = sc.nextInt();
//		longd = sc.nextInt();
//
//		boolean f = false;
//		int[] array = new int [n+1];
//		int[] array2 = new int[n];
//		for (int i = 0; i < n+1; i++) {
//			array[i] = sc.nextInt();
//		}
//		for (int i = 0; i < n; i++) {
//			array2[i] = sc.nextInt();
//		}


		for(int i = 1; i <= m; i++) {
			if(i < 4) {
				continue;
			}
			for(int j = 1; j <= d; j++) {
				int d10 = j/10;
				int d1 = j%10;
				if(d10 < 2 || d1 < 2) {
					continue;
				}
				if(d10 * d1 == i) {
					ans++;
				}
			}
		}


		System.out.println(ans);

		sc.close();
	}
}

Measured memory_bytes: 23636
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}
vector<vector<ll>> v(100001,vector<ll>(0));
vector<int> col(100001,-1);
map<pair<ll,ll>,ll> st;


void dfs(int t){
    int co = col[t];
    for(int i=0;i<v[t].size();i++){
        ll tt = v[t][i];
        if(col[tt]==-1){
            ll ww = (t>tt?st[{tt,t}]:st[{t,tt}]);
            if(ww%2){
                col[v[t][i]] = !co;
                dfs(tt);
            }else{
                col[v[t][i]] = co;
                dfs(tt);
            }
        }
    }

}
int main(){

    ll n;
    cin>>n;

    rep(i,n-1){
        ll u1,v1,w1;
        cin>>u1>>v1>>w1;
        u1--;
        v1--;
        v[u1].push_back(v1);
        v[v1].push_back(u1);
        if(u1<v1){
            st[{u1,v1}] = w1;
        }else{
            st[{v1,u1}] = w1;
        }
    }

    col[0] = 0;
    dfs(0);
    rep(i,n){
        cout<<col[i]<<endl;
    }





return 0;
}


Measured memory_bytes: 17280
N, T = map(int, input().split())
coti = [input().split() for i in range(N)]
#print(coti)
mincost = 1001
for pair in coti:
    #print(int(pair[1]))
    if int(pair[1]) <= T:
        if int(pair[0]) < mincost:
            mincost = int(pair[0])
        continue
if mincost == 1001:
    print('TLE')
else:
    print(mincost)

Measured memory_bytes: 3064
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


def main():
    n, a, b = get_li()
    print(min(n * a, b))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()


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


int main(){

    int X;
    cin >> X;
    // 2000円以上なら全て作れる
    if (X >= 2000){
        cout << '1' << endl;
    }
    else{
        for (int i = 0; i < 20; i++){
            for (int j =0; j <20-i; j++){
                for (int k = 0; k < 20-i-j; k++){
                    for (int l =0; l < 20-i-j-k; l++){
                        for (int m = 0; m < 20-i-j-k-l; m++){
                            for (int n = 0; n < 20-i-j-k-l-m; n++){
                                if ( i*100 + j*101 + k*102 + l*103 + m*104 + n*105 == X){
                                    cout << "1" << endl;
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
        cout << '0' << 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;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;

vector<int> s[2];
vector<ull> u[2];
const int N=500;
int n;
int val[2][N];
int d[N][N];

void flip(){
  rep(i,n)rep(j,i){
    swap(d[i][j],d[j][i]);
  }
}
bool solve(){
  rep(i,n)rep(j,n) d[i][j]=-1;
  rep(k,2){
    rep(i,n){
      int x =val[k][i];
      if(s[k][i] != x){
        rep(j,n){
          if(d[i][j] == !x) return false;
          d[i][j]=x;
        }
      }
    }
    flip();
  }
  rep(_,2){
    rep(k,2){
      rep(i,n){
        int x=val[k][i];
        if(s[k][i]==x){
          vector<int> p;
          bool ok=false;
          rep(j,n){
            if(d[i][j]==-1) p.push_back(j);
            if(d[i][j]== x) ok =true;
          }
          if (ok) continue;
          if(p.size()==0) return false;
          if(p.size()== 1){
            d[i][p[0]]=x;
          }
        }
      }
      flip();
    }
  }
  vector<int> is,js;
  rep(i,n){
    bool filled=true;
    rep(j,n) if (d[i][j]==-1) filled =false;
    if(!filled) is.push_back(i);
  }
  rep(j,n){
    bool filled=true;
    rep(i,n) if (d[i][j]==-1) filled =false;
    if(!filled) js.push_back(j);
  }
  rep(i,is.size())rep(j,js.size()){
    d[is[i]][js[j]]=(i+j)%2;
  }
  return true;
}


ull ans[N][N];

int main(){
  cin >>n;
  rep(i,2){
    s[i]=vector<int>(n);
    rep(j,n) cin >>s[i][j];
  }
  rep(i,2){
    u[i]=vector<ull>(n);
    rep(j,n) cin >> u[i][j];
  }
  rep(b,64){
    rep(i,2)rep(j,n) val[i][j]= u[i][j]>>b&1;
    if(!solve()){
      cout <<"-1"<<endl;
      return 0;
    }
    rep(i,n)rep(j,n) ans[i][j]|= ull(d[i][j])<<b;
  }
  rep(i,n){
    rep(j,n){
      cout << ans[i][j]<<(j==n-1? '\n': ' ');
    }
  }
  return 0;

}


Measured memory_bytes: 8440
class Solver(object):
    def __init__(self):
        self.valids = self._generate_valid_list()
        self.n = int(input())

    def solve(self):
        if self.n in self.valids:
            print("Yes")
        else:
            print("No")

    def _generate_valid_list(self):
        valids = set()
        for cake in range(26): # 0 .. 25
            for donut in range(16):  # 0 .. 15
                valids.add( (donut*7) + (cake*4) )
        return valids


if __name__ == "__main__":
    s = Solver()
    s.solve()

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

int main(void){
    int n;
    vector <int> l, r;
    int i, x;
    int cnt = 0;

    cin >> n;
    for(i = 0; i < n; i++){
        cin >> x;
        l.push_back(x);
        cin >> x;
        r.push_back(x);
    }
    
    for(i = 0; i < n; i++){
        cnt += r[i] - l[i] + 1;
    }
    
    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll l[100000], r[100000];
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> l[i] >> r[i];
	}
	multiset<ll> L, R;
	ll offL = 0, offR = 0, m = 0;
	L.insert(-(1LL << 60));
	R.insert(1LL << 60);
	for (int i = 0; i < N; i++) {
		if (i > 0) {
			offR += (r[i - 1] - l[i - 1]);
			offL -= (r[i] - l[i]);
		}
		if (l[i] < *L.rbegin() + offL) m += *L.rbegin() + offL - l[i];
		else if (*R.begin() + offR < l[i]) m += l[i] - (*R.begin() + offR);
		if (l[i] < *L.rbegin() + offL) {
			R.insert(*L.rbegin() + offL - offR);
			L.insert(l[i] - offL);
			L.insert(l[i] - offL);
			L.erase(L.find(*L.rbegin()));
		}
		else if (*R.begin() + offR < l[i]) {
			L.insert(*R.begin() + offR - offL);
			R.insert(l[i] - offR);
			R.insert(l[i] - offR);
			R.erase(R.find(*R.begin()));
		}
		else {
			L.insert(l[i] - offL);
			R.insert(l[i] - offR);
		}
	}
	cout << m << endl;
}

Measured memory_bytes: 11136
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cstdlib>
#define NMAX 10000
#define MMAX 10000
using namespace std;
int main(){
	int A,B,C;
	cin >> A >> B >> C;
	if(A == B+C || B == A+C || C == A+B){
		cout << "Yes" << "\n";
	}else{
		cout << "No" << "\n";
	}
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
	int n;
	int count;
	while (1)
	{
		cin >> n;
		if (cin.fail()) break;

		bool *isPrime;
		isPrime = new bool[n + 1];
		memset(isPrime, true, sizeof(bool) * (n + 1));
		isPrime[0] = isPrime[1] = false;
		
		count = 0;
		for (int i = 2; i <= n; ++i)
		{
			for (int j = i + i; j <= n; j += i)
			{
				isPrime[j] = false;
			}
		}
		for (int i = 0; i <= n; ++i)
		{
			if (isPrime[i] == true)
				++count;
		}
		cout << count << endl;
		delete[] isPrime;
	}
	return 0;
}

Measured memory_bytes: 3976
def main():
    def sweep(arr):
        col = max(arr).bit_length()
        row = len(arr)

        rank = 0
        for c in range(col-1, -1, -1):
            piv = -1
            for r in range(rank, row):
                if arr[r] >> c & 1:
                    piv = r
            if piv == -1:
                continue

            arr[piv], arr[rank] = arr[rank], arr[piv]

            for r in range(row):
                if r == rank:
                    continue
                if arr[r] >> c & 1:
                    arr[r] ^= arr[rank]

            rank += 1

        return sorted(arr[:rank], reverse=True)

    def solve():
        N = int(input())
        A = list(map(int, input().split()))[::-1]
        S = input()[::-1]
        B0 = []

        for a, s in zip(A, S):
            if s == '1':
                for b0 in B0:
                    if a >> b0.bit_length()-1 & 1:
                        a ^= b0
                if a:
                    return 1
            else:
                B0 = sweep(B0+[a])

        return 0

    for _ in [0]*int(input()):
        print(solve())


if __name__ == '__main__':
    main()


Measured memory_bytes: 69636
#include<stdio.h>
#define INFINITO 1000000000
  
long long int min(long long a, long long b) { return (a < b)? a : b; }
long long int max2(long long a, long long b) { return (a > b)? a : b; } 
long long int max3(long long a, long long b, long long c) {
	if(a>=b && b>=c) return a;
	else if(b>=a && b>=c) return b;
	else if(c>=a && c>=b) return c;
}

int main() {
	long long n, i, j;
	scanf("%lld", &n);
	long long vet[n+10][3], dp[n+10][3];
		
	for(i = 1; i <= n; i++) {
		scanf("%lld", &vet[i][0]);
		scanf("%lld", &vet[i][1]);
		scanf("%lld", &vet[i][2]);
	}
	dp[1][0] = vet[1][0];
	dp[1][1] = vet[1][1];
	dp[1][2] = vet[1][2];

	for(i = 2; i <= n; i++)
		for(j = 0; j < 3; j++)
			dp[i][j] = max2( dp[i-1][(j+2)%3] + vet[i][j] , dp[i-1][(j+1)%3] + vet[i][j] );

	printf("%lld\n", max3(dp[n][0], dp[n][1], dp[n][2]));

	return 0;
}

Measured memory_bytes: 4864
s=input()
s1 = int(s[0:2])
s2 = int(s[2:4])
if s1 > 12 or s1 == 0 :
    if s2 > 12 or s2 == 0 :
        print('NA')
    else:
        print('YYMM')
elif s2 > 12 or s2 == 0 :
    print('MMYY')
else :
    print('AMBIGUOUS')
    

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

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void run(){
		Scanner sc=new Scanner(System.in);
		while(true){
			int n=sc.nextInt();
			if(n==0) break;
			int r[]=new int[n];
			int w[]=new int[n];
			int sumr=0,sumw=0,rmax=0,maxindex=-1;
			for(int i=0; i<n; i++){
				r[i]=sc.nextInt();
				w[i]=sc.nextInt();
				sumr+=r[i];
				sumw+=w[i];
				if(rmax<r[i]){
					rmax=r[i];
					maxindex=i;
				}
			}
//			Arrays.sort(r);
//			System.out.println("読むのが長い奴="+rmax+" sumr="+sumr+" 待ち時間!"+(rmax-(sumr-rmax)));
//			System.out.println("sumw="+sumw);
			if(rmax <= (sumr-rmax)){
				System.out.println(sumr+sumw);
			}
			else{
				boolean dp[][]=new boolean[n+1][sumw+1];//dp[i][j]は1-iから本を選んで感想文の合計をjにできる 
				for(int i=0; i<n+1; i++){
					Arrays.fill(dp[i],false);
				}
				dp[0][0]=true;
				for(int i=0; i<n; i++){
					for(int j=0; j<=sumw; j++){
						if(dp[i][j]){
							dp[i+1][j]=true;
							if(i!=maxindex)dp[i+1][j+w[i]]=true;
						}
					} 
				}
//				for(int i=0; i<n-1; i++){
//					for(int j=0; j<sumw; j++){
//						System.out.print(" "+dp[i][j]);
//					} 
//					System.out.println();
//				}
				int max=0;
				int wait=rmax-(sumr-rmax);
				for(int i=0; i<=n; i++){
					for(int j=0; j<=sumw; j++){
						if(dp[i][j]){
							if(j <= wait && max < j){
								max=j;
							}
						}
					} 
				}
//				System.out.println(max);
				System.out.println(2*rmax+(sumw-max));
			}
		}//while
	}//run		
}

Measured memory_bytes: 62420
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#define ll long long

using namespace std;


int main(void){
    int n, m;
    int ans = 0;
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    vector<pair<int ,int>> p;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        p.emplace_back(a, b);
    }

    for(int i = 0; i < p.size(); i++){
        vector<int> dist(n+1, -1);
        queue<int> que;
        dist[1] = 0;
        que.push(1);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (int nv : g[v]) {
                if(p[i].first==v && p[i].second==nv) continue;
                if(p[i].second==v && p[i].first==nv) continue;
                if (dist[nv] != -1) continue;
                dist[nv] = dist[v] + 1;
                que.push(nv);
            }
        }
        for(ll j = 1; j <= n; j++){
            if(dist[j]==-1){
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
N = int(input())
h = list(map(int, input().split()))
h.append(0)
cnt = 0
for i in range(max(h),0,-1):
    for j in range(N):
        if h[j] == i and h[j+1] == i:
            h[j] -= 1
        elif h[j] == i:
            cnt += 1
            h[j] -= 1
print(cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
#define rev(x) reverse((x).begin(),(x).end())
{
    string a;
    cin>>a;
    string b=a;
    rev(b);
    if(a!=b)
        cout<<"No\n";
    else
    {
        int x=(a.size()-1)/2;
        string c=a.substr(0,x);
        string d=c;
        rev(d);

        int y=a.size()-((a.size()+3)/2-1);
        string e=a.substr((a.size()+3)/2-1,y);
        string f=e;
        rev(f);

        if(c==d && e==f)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
}


Measured memory_bytes: 3568
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 100000;
int ans = 1, dyee[maxn], dyee2[maxn], n;
vector<int> v[maxn];

struct ids {
  int from, to, id;
  bool operator<(const ids dd) const {
    if (from == dd.from) return to < dd.to;
    else return from < dd.from;
  }
} idd[2*maxn];

void dye(int from, int now) {
  int val = 1;
  
  if (from != -1) {
    auto lw = lower_bound(idd, idd+2*n, ids{from, now, 0});
    int id1 = (*lw).id;
    dyee2[id1] = dyee[now];
  }
  //cout << id1 << endl;
  //dyee2[id1] = val;
  //cout << "(" << from << " " << now << ")" << endl;
  //if (dyee[from] != 0 && dyee[now] != 0) return;
  for(int x:v[now]) {
    if (x == from) continue;
    if (dyee[now] == val) val++;
    dyee[x] = val; ans = max(ans, val);
    
    //auto lw = lower_bound(idd, idd+2*n, ids{now, x, 0});
    //int id1 = (*lw).id;
    //cout << id1 << endl;
    //dyee2[id1] = val;
    
    //cout << "#" << now << " " << x << ") ";
    val++; dye(now, x);
  }
}

int main() {
  cin >> n;
  fill(dyee, dyee+n, 0); dyee[0]=1234567;
  fill(dyee2, dyee2+n-1, 0);
  
  for(int i=0; i<n-1; i++) {
    int a, b;
    cin >> a >> b; a--; b--; //cout << a << " " << b << endl;
    v[a].push_back(b);
    v[b].push_back(a);
    idd[2*i].from = a; idd[2*i+1].from = b;
    idd[2*i].to = b; idd[2*i+1].to = a;
    idd[2*i].id = i; idd[2*i+1].id = i;
  }
  
  sort(idd, idd+2*n);
  dye(-1, 0);
  
  int aaaa = 0;
  for(int i=0; i<n-1; i++) {
    aaaa = max(aaaa, dyee2[i]);
  }
  cout << aaaa << endl;
  for(int i=0; i<n-1; i++) {
    cout << dyee2[i] << endl;
  }
}

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

int main() {
  int D;
  cin>>D;
  vector<int> sage(26);
  for(int i=0;i<26;i++){
    cin>>sage.at(i);
  }
  vector<vector<int>> man(D,vector<int>(26));
  for(int i=0;i<D;i++){
    for(int j=0;j<26;j++){
      cin>>man.at(i).at(j);
    }
  }
  vector<int> hini(D);
  vector<vector<int>> rkai(D+1,vector<int>(26,1));
  for(int i=0;i<D;i++){
    int A=0,W=man.at(i).at(0)-(1+rkai.at(i).at(0))*sage.at(0);
    for(int j=1;j<26;j++){
      int Y=man.at(i).at(j)-(1+rkai.at(i).at(j))*sage.at(j);
      if(Y>W){
        W=Y,A=j;
      }
      rkai.at(i+1).at(j)=rkai.at(i).at(j)+1;
    }
    hini.at(i)=A;
    rkai.at(i).at(A)=0;
    rkai.at(i+1).at(A)=1;
  }
  /*for(int i=0;i<D;i++){
    Z+=man.at(i).at(hini.at(i));
    for(int j=0;j<26;j++){
      Z-=rkai.at(i).at(j)*sage.at(j);
    }
    cout<<Z<<endl;
  }*/
  for(int i=0;i<D;i++){
    cout<<hini.at(i)+1<<endl;
  }
}

Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

int main(){
	
	int N;
	cin>>N;
	
	vector<string> s(N);
	vector<int> t(N);
	
	for(int i=0;i<N;i++){
		cin>>s[i]>>t[i];
	}
	
	string X;
	cin>>X;
	
	for(int i=0;i<N;i++){
		if(s[i]!=X)continue;
		int ans = 0;
		
		for(int j=i+1;j<N;j++){
			ans += t[j];
		}
		
		cout<<ans<<endl;
		return 0;
	}
	
    return 0;
}


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



int main(){
	int n, m;
	cin>>n;
	m=0;
	int sum=0;
	while(n--){
		int tmp;
		cin>>tmp;
		m=max(m,tmp);
		sum+=tmp;
	}
	if(2*m<sum){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	
}

Measured memory_bytes: 384
// 最       悪      行列が逆だった 横が行ね...
// 1<=p<=N 1<=q<=Mとして p*(M-q)+q*(N-p)=黒
package main

import "fmt"

func main() {
	var N, M, K int
	fmt.Scan(&N, &M, &K)
	if N == 1 || M == 1 {
		fmt.Println("Yes")
		return
	}
	flag := false
	for p := 0; p <= N; p++ {
		for q := 0; q <= M; q++ {
			if p*(M-q)+q*(N-p) == K {
				flag = true
			}
		}
	}
	if flag {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template <typename A, typename B>
using unordered_map2 = __gnu_pbds::gp_hash_table<A, B>;
using namespace __gnu_pbds;
template <typename T> using ordered_set =
  __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag,
                   __gnu_pbds::tree_order_statistics_node_update>;
// ordered_set<int> s; s.insert(1); s.insert(2);
// s.order_of_key(1);    // Out: 0.
// *s.find_by_order(1);  // Out: 2.

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

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, ll b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  string a, b;
  cin >> a >> b;
  const ll len = ll(n) * m / __gcd(n, m);

  map<int, char> mapa;
  auto Ustaw = [&mapa](int i, char c) -> void {
    char& d = mapa[i];
    if (d and d != c) {
      cout << -1 << endl;
      exit(0);
    }
    d = c;
  };

  for (int i = 0; i < n; i++) {
    Ustaw(i * (len / n) + 1, a[i]);
  }

  for (int i = 0; i < m; i++) {
    Ustaw(i * (len / m) + 1, b[i]);
  }

  cout << len << endl;
  return 0;
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[100002];

int main(){
        
    ll n, k; cin >> n >> k;
    //memset(dp,-1, sizeof(dp)/sizeof(dp[0]));
    std::vector<ll> v(n);
    for(auto &x : v)cin >> x;
    dp[0] = 0;
    for(int i = 1;i <= k; i++){
    //dp[0] = 0;
        dp[i] = abs(v[i] - v[0]);
        for(int j = 0;j < i; j++)
            if(dp[i] > (abs(v[i] - v[j]) + dp[j]))
                dp[i] = abs(v[i] - v[j]) + dp[j];

    }

    for(int i = k+1;i <= n - 1;i++){

        dp[i] = dp[i - 1] + abs(v[i] - v[i - 1]);
        for(int j = 1; j <= k; j++){

            if(dp[i] > (abs(v[i] - v[i - j]) + dp[i - j])){
                dp[i] = abs(v[i] - v[i - j]) + dp[i - j];

            }
        }
    }

    cout<< dp[n - 1];
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int n, m, a, b;;
	ll pos = 0, cnt = 0, ans = 0;
	cin >> n >> m;
	vector<vector<int>>fri(n);
	set<pi>se;
	rep(i, m) {
		cin >> a >> b;
		--a; --b;
		if (!se.count(pi(a, b))) {
			se.insert(pi(a, b));
			se.insert(pi(b, a));
			fri[a].push_back(b);
			fri[b].push_back(a);
		}
	}
	queue<int>q;
	set<int>s;
	rep(i, n) {
		cnt = 0;
		q.push(i);
		while (!q.empty()) {
			pos = q.front(); q.pop(); cnt++;
			s.insert(pos);
			for (auto v : fri[pos]) {
				if (!s.count(v)) { q.push(v); s.insert(v); }
			}
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}



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

int gcd(int m, int n){
   while (n != 0){
      int t = n;
      n = m % n;
      m = t;
   }
   return m;
}

int main(){
   int K;
   cin >> K;
   vector<int> gcd_ab;
   for (int m = K; m>0; m--){
      for (int n = K; n>0; n--){
         if (m > n){
            gcd_ab.push_back(gcd(m, n));
         } else{
            gcd_ab.push_back(gcd(n, m));
         }
      }
   }

   int sum = 0;
   for (int x : gcd_ab){
      for (int i=K; i>0; i--){
         int m, n;
         if (i > x){
            m = i;
            n = x;
         }else{
            m = x;
            n = i;
         }
         sum += gcd(m, n);
      }
   }

   cout << sum << endl;

   //for (int i=0; i<gcd_ab.size(); i++)
   //   cout << gcd_ab.at(i) << " " << endl;
}



Measured memory_bytes: 3752
/* vim:set foldmethod=marker: */
#include <bits/stdc++.h>
using namespace std;

//{{{
#define all(x) (x).begin(),(x).end()
#define REP(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define RREP(i,a,b) for(int i=(int)(a); i>=b; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,n,0)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;

#define dump(x) (cerr << #x << "=" << x << endl)
template<class T> ostream& osContainer(ostream& os,T c) { os<<'[';for(decltype(c.begin()) it=c.begin();it!=c.end();it++)os<<*it<<',';os<<']';return os; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { return osContainer(os,v); }
template<class T> ostream& operator<<(ostream& os,const set<T>& s) { return osContainer(os,s); }
template<class T> ostream& operator<<(ostream& os,const multiset<T>& s) { return osContainer(os,s); }
template<class T,class S> ostream& operator<<(ostream& os,const map<T,S>& m) { return osContainer(os,m); }
template<class T,class S> ostream& operator<<(ostream& os,const multimap<T,S>& m) { return osContainer(os,m); }
template<class T1,class T2>
ostream& operator<<(ostream& os, const pair<T1,T2>& p){ os << '(' << p.first << ',' << p.second << ')'; return os; }

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

void solve()
{
    int n, m, p;

    while (cin >> n >> m >> p, n || m || p)
    {
        int s = 0;
        int x[101];
        REP(i, 1, n + 1) {
            cin >> x[i];
            s += 100 * x[i];
        }

        cout << (x[m] ? s * (100 - p) / 100 / x[m] : 0) << endl;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(12);
    solve();
}

Measured memory_bytes: 3188
#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <regex>
#include <sstream>
#include <string>
#include <thread>
#include <tuple>
#include <type_traits>
#include <vector>

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    int x, y;
    cin >> x >> y;
    if (y >= 2 * x && y <= 4 * x && y % 2 == 0) {
        cout << "Yes" << endl;

        return 0;
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using VI = vector<int>;
using VVI = vector<vector<int>>;

int main(){
  int n;
  cin >> n;
  VI b(n+1);
  b[0] = 100005;
  b[n] = 100005;
  rep(i,n-1) cin >> b[i+1];
  
  int sum = 0;
  rep(i,n){
    sum += min(b[i], b[i+1]);
  }
  
  cout << sum << endl;
  
  return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

ll A[2][110];
ll dp[2][110];

int main2() {
  CLR(dp, 0);
  int N = nextInt();
  REP(i, 2) REP(j, N) {
    A[i][j] = nextInt();
  }

  dp[0][0] = A[0][0];
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < N; j++) {
      if (i + 1 < 2) chmax(dp[i+1][j], dp[i][j] + A[i+1][j]);
      if (j + 1 < N) chmax(dp[i][j+1], dp[i][j] + A[i][j+1]);
    }
  }

  ll ans = dp[1][N-1];
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


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

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

    ll N;
    cin >> N;
    vector<ll> cnt(N, 0);
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        ll A;
        cin >> A;
        if (i >= A) {
            ans += cnt.at(i - A);
        }
        if (i + A < N) {
            cnt.at(i + A)++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4784
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    cout << fixed << setprecision(10);
    
    int N; cin >> N;
    vector<ll> X(N), L(N);
    rep(i, N) cin >> X[i] >> L[i];

    vector<P> lr(N);
    rep(i, N) {
        lr[i] = make_pair(X[i]+L[i], X[i]-L[i]);
    }

    sort(lr.begin(), lr.end());

    ll ans = N, xn = -1e+9 -1;
    rep(i, N) {
        if (xn <= lr[i].second) {
            xn = lr[i].first;
        } else {
            ans -= 1;
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main(){
    int A;
    //Aを定義
    int B;
    //Bを定義
    cin >> A >> B;
    if(A % 2 != B % 2){
        cout << "IMPOSSIBLE" << endl;
        //条件を満たす整数が存在しなければ、代わりにIMPOSSIBLEと出力
    } else {
        cout << (A + B) / 2 << endl;
        //
    }
}

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

namespace abc160_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            char c3 = S[2];
            char c4 = S[3];
            char c5 = S[4];
            char c6 = S[5];
            if (S[2] == S[3] && S[4] == S[5])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
            Console.Read();
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a;
	int l=a.size();
	b=a;
	for(int i=0;i<l;i++)
		switch(b[i])
		{
			case 'b':
				b[i]='d';
				break;
			case 'd':
				b[i]='b';
				break;
			case 'q':
				b[i]='p';
				break;
			case 'p':
				b[i]='q';
				break;
		}
	
	for(int i=0;i<l;i++)
		if(a[i]!=b[l-1-i])
		{
			cout<<"No";
			return 0;
		}
	
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <array>

int main(){
	std::array<u_int, 4> a,b;
	int hit,blow;

	while(std::cin >> a[0] >> a[1] >> a[2] >> a[3]){
		std::cin >> b[0] >> b[1] >> b[2] >> b[3];
		hit=0;
		blow=0;
		for(int i=0;i<4;i++){
			if(a[i]==b[i]) hit++;
			for(int j=0;j<4;j++){
				if(a[i]==b[j]) blow++;
			}
		}
		std::cout << hit << " " << blow-hit << std::endl;
	}

    return 0;
}


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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pairInt;
typedef tuple<int, int, int> tuple3Int;
#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define FOR1(i, m, n) for (int i = int(m); i < int(n); i++)
#define MAX(a, b) ((a) >= (b) ? (a) : (b))
#define MIN(a, b) ((a) <= (b) ? (a) : (b))

int main(int argc, char *argv[])
{
  int N, K;
  vector<int> a;

  scanf("%d%d", &N, &K);
  a.resize(N);

  FOR(i, N) scanf("%d", &a[i]);

  map<int, int> m;
  int sum(0), l(0), r(0), ans(INT_MAX);
  while (r < N) {
    while (r < N && m.size() < K) {
      if (a[r] > K) {
        r++;
        continue;
      }
      m[a[r++]]++;
    }
    if (m.size() < K) break;
    while (m.size() >= K){
      if (a[l] > K) {
        l++;
        continue;
      }
      auto it = m.find(a[l]);
      if (it->second == 1)
        m.erase(it);
      else
        it->second--;
      l++;
    }
    if (r - l + 1 < ans) ans = r - l + 1;
  }

  printf("%d\n", ans == INT_MAX ? 0 : ans);
  
  return 0;
}

Measured memory_bytes: 7900
import java.util.Scanner;

public class Main {

    private static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
	int A = Integer.parseInt(scan.next());
	int B = Integer.parseInt(scan.next());
	
	System.out.println(A % 3 == 0 || B % 3 == 0 || (A+B) % 3 == 0 ? "Possible" : "Impossible");
	scan.close();
    }
}


Measured memory_bytes: 21716