akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        // 主処理
        char[] array = s.toCharArray();
        int countC = 0;
        boolean judge = true;
        for (int i = 0; i < array.length; i++) {
            if (i == 0) {
                judge = judge && array[i] == 'A';

            } else if (2 <= i && i <= array.length - 2) {
                if (array[i] == 'C') {
                    countC++;
                } else {
                    judge = judge && Character.isLowerCase(array[i]);
                }

            } else {
                judge = judge && Character.isLowerCase(array[i]);
            }
        }
        String result = judge && countC == 1 ? "AC" : "WA";

        // 出力
        System.out.println(result);
        sc.close();
    }
}


Measured memory_bytes: 22228
using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
class P
{
    static void Main()
    {
        int[] abc = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(abc.Sum() >= abc[2] * 2 ? "Yes" : "No");
    }
 
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
int main () {
  int K;
  cin >> K;
  if (K % 2 == 0 || K % 5 == 0) {
    cout << -1 << endl;
    return 0;
  }
  int key = 7;
  int ans = 1;
  int kj = 1;
  while (key % K != 0) {
    ans ++;
    kj *= 10;
    kj %= K;
    key += (kj * 7);
    key %= K;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007
using namespace std;
using ll = long long;

int main() {
    ll N, A, B;
    cin >> N >> A >> B;

    vector<ll> X(N);
    for (int i = 0; i < N; i++) cin >> X[i];

    ll ans = 0;
    for (int i = 1; i <= N - 1; i++) {
        if ((X[i] - X[i - 1]) * A > B) {
            ans += B;
        }
        else {
            ans += A*(X[i] - X[i - 1]);
        }

    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
import fractions
a,b=map(int,input().split())
c=fractions.gcd(a,b)
#print(c)
l=[]
s=int(c**(1/2))+1
for i in range(1,s+1):
    if c%i==0:
        if i!=c//i:
            l.append(i)
            l.append(c//i)
        else:
            l.append(i)
l.sort()
l=l[::-1]
ans=1
#print(l)
for i in range(len(l)-1):
    for j in range(i+1,len(l)-1):
        if fractions.gcd(l[i],l[j])>=2:
            break
    else:
        ans+=1
print(ans)

Measured memory_bytes: 5304
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    s = input()

    # KeyInsight
    # 条件を満たす場合を直接求めるのが難しい場合は、補集合を考える

    # R, G, Bは、それぞれ独立に扱える
    r_count = s.count('R')
    g_count = s.count('G')
    b_count = s.count('B')

    ans = r_count * g_count * b_count

    # i, jを固定して全探索
    # 常にi < jとなるように添字を振るのもポイント
    for j in range(n):
        for i in range(j):
            # kは、i, jから計算
            k = 2 * j - i

            # インデックスエラーを回避
            if k < n:
                if s[i] == s[j]:
                    continue
                elif s[i] == s[k]:
                    continue
                elif s[j] == s[k]:
                    continue

                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9060
S = input()
if not S[0] is "A":
  print("WA")
  exit()

subS = S[2:-1]
if not (("C" in subS) and (subS.count('C') == 1)):
  print("WA")
  exit()

subS = S.replace('A', '').replace('C','')
if not subS.islower():
  print("WA")
  exit()

print("AC")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	map<ll,ll>a;
	for(ll i=0;i<n;i++){
		ll x;
		cin>>x;
		a[x]++;
	}
	ll ans=0;
	ll cnt=0;
	for(auto itr=a.begin();itr!=a.end();itr++){
		ll val=itr->second;
		if(val%2==0){
			cnt++;
		}
		else{
			ans++;
		}
	}
	if(cnt%2!=0){
		cnt=max(ll(0),cnt-1);
	}
	cout <<ans+cnt;
	// your code goes here
	return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    long long sum=0;
    vector<int> v(n);
    for(int&a : v){
        cin>>a;
        sum+=a;
    }
    vector<vector<long long>> dp(n+1,vector<long long>(n+1));
    for(int l=n-1;l>=0;l--){
        for(int r=l;r<n;r++){
            if(l==r) dp[l][r] = v[l];
            else dp[l][r]= max(v[l]-dp[l+1][r],v[r]-dp[l][r-1]);
        }
    }
    cout<<dp[0][n-1]<<endl;
}

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

int main(){
  int H, W;
  while(true){
    cin >> H >> W;
    if (H == 0 && W == 0) {
      break;
    } else {
      for (int i = 0; i < W; i++) {
        cout << "#";
      }
      cout << endl;

      for (int j = 0; j < H-2; j++) {
        cout << "#";
        for (int k = 0; k < W-2; k++) {
          cout << ".";
        }
        cout << "#" << endl;
      }

      for (int i = 0; i < W; i++) {
        cout << "#";
      }
      cout << endl;
      cout << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3044
#include<bits/stdc++.h>
using namespace std;
int cnt[128];
int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); ++i){
        ++cnt[s[i]];
    }
    int m = min(cnt['a'], min(cnt['b'], cnt['c']));
    cnt['a'] -= m; cnt['b'] -= m; cnt['c'] -= m;
    if (abs(cnt['a']) > 1 || abs(cnt['b']) > 1 || abs(cnt['c']) > 1) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 512
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::prelude::BufRead;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Write};
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
	let line = read_vector::<usize>();
	let (l, r) = (line[0], line[1]);
	let mut minimum = 2020;
	if r - l <= 2019 {
		for i in l..(r + 1) {
			for j in (i + 1)..(r + 1) {
				let remainder = ((i % 2019) * (j % 2019)) % 2019;
				minimum = min(remainder, minimum);
			}
		}
	} else {
		minimum = 0;
	}
	println!("{}", minimum);
}


#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .trim()
        .parse()
        .unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    use std::io::prelude::*;
    let stdin = stdin();
    return stdin
        .lock()
        .lines()
        .map(|line| line
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect())
        .collect();
}

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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 110, M = 1010;

int a, b;
char g[N][N];

int main()
{
	cin >> a >> b;
	a -- , b -- ;
	
	for (int i = 0; i < 50; i ++ )
		for (int j = 0; j < 100; j ++ )
			g[i][j] = '#';
	for (int i = 50; i < 100; i ++ )
		for (int j = 0; j < 100; j ++ )
			g[i][j] = '.';
			
	for (int i = 0; i < 50 && a; i += 2)
		for (int j = 0; j < 100 && a; j += 2)
			g[i][j] = '.', a -- ;
			
	for (int i = 51; i < 100 && b; i += 2)
		for (int j = 0; j < 100 && b; j += 2)
			g[i][j] = '#', b -- ;
	
	puts("100 100");
	for (int i = 0; i < 100; i ++ ) puts(g[i]);
	return 0;
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

string s[8];

int latte[6][8]={
{0,1,2,3,4,5,6,7},
{1,5,6,2,0,4,7,3},
{2,6,7,3,1,5,4,0},
{0,3,7,4,1,2,6,5},
{0,4,5,1,3,7,6,2},
{4,7,6,5,0,3,2,1},
};

void solve(){
    vector<string>v;
    rep(i,8)v.pb(s[i]);
    sort(all(v));v.erase(unique(all(v)),v.end());

    vint c(8);
    rep(i,8)c[i]=lower_bound(all(v),s[i])-v.begin();
    sort(all(c));
    set<vint>st;

    do{
        vint mi=c;
        rep(i,6){
            vector<int>cc(8);
            rep(j,8)cc[j]=c[latte[i][j]];
            rep(j,4){
                chmin(mi,cc);
                rotate(cc.begin(),cc.begin()+1,cc.begin()+4);
                rotate(cc.begin()+4,cc.begin()+5,cc.begin()+8);
            }
        }
        st.insert(mi);
    }while(next_permutation(all(c)));


    cout<<st.size()<<endl;
}

signed main(){
    while(cin>>s[0]){
        rep(i,7)cin>>s[i+1];
        solve();
    }
    return 0;
}

Measured memory_bytes: 3332
n,k = map(int,input().split())
X = list(map(int,input().split()))
min_d =10**9

for i in range(n-k+1):
    l,r = X[i],X[i+k-1]
    if l<0 and r <=0:
        d = abs(l)
    elif l <=0 and r>=0:
        d = min(abs(l),abs(r))*2 + max(abs(l),abs(r))
    else:
        d = r
    min_d = min(min_d,d)
print(min_d)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
#define mod 1e9+7
#define pb push_back
#define F first
#define S second

using namespace std;
typedef long long ll;
typedef long double ld;
int dx[4] = {-1, 0, +1, 0}, dy[4] = {0, -1, 0, +1};



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    int a = 0, b = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'A') a++;
        if (s[i] == 'B') b++;
    }
    if (a >= 1 && b >= 1) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    H = i2nn()
    n = 0
    while True:
        l = -1
        r = -1
        for i, h in enumerate(H):
            if l == -1 and h > 0:
                l = i
            if l > -1 and r == -1 and h <= 0:
                r = i
        if l == -1:
            break
        if r == -1:
            r = N
        for i in range(l, r):
            H[i] -= 1
        n += 1
    print(n)

main()


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

using namespace std;

const int size=10e5+2;
int sizeC;
int matrix[size][3];
int state[size][3];

int maxi(int n,int a){

  if(n==0)
    return matrix[n][a];

  if(state[n][a])
    return state[n][a];

  if(a==0)
    return state[n][a]=max(maxi(n-1,1),maxi(n-1,2))+matrix[n][a];
  else if(a==1)
    return state[n][a]=max(maxi(n-1,0),maxi(n-1,2))+matrix[n][a];
  else
    return state[n][a]=max(maxi(n-1,1),maxi(n-1,0))+matrix[n][a];
}

int main(){

  scanf("%d",&sizeC);

  for(int i=0;i<sizeC;i++){
    for(int j=0;j<3;j++){
      scanf("%d",&matrix[i][j]);
    }
  }

  cout<<max(maxi(sizeC-1,0),max(maxi(sizeC-1,1),maxi(sizeC-1,2)))<<endl;

  return 0;
}


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

int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  int res = 0;
  rep(i,m){
    cin>>a[i];
    res += a[i];
  }
  if(res>n){
    cout << -1 << endl;
  }else{
    cout << n - res << endl;
  }
}

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

string str[100];
int len;
int fie[101][101];
int m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
char s[4]={'R','D','L','U'};
int main(void){
	int n=9;
	for(int i=0;i<10;i++)cin >> str[i];
	m=str[0].size();
	for(int i=0;i<n;i++){
		for(int j=0;j<str[i].size();j++){
			if(str[i][j]=='1'){
				if(i%2==0)fie[j*2+2][i+1]=1;
				if(i%2==1)fie[j*2+1][i+1]=1;
			}
		}
	}
	int x=2,y=0,dir=0;
	while(1){
		int nx=x+dx[(dir+1)%4],ny=y+dy[(dir+1)%4];
		if(nx>=0 && nx<=m*2+2 && ny>=0 && ny<=n+1){
			if(fie[nx][ny]==1)printf("%c",s[dir]);
		}
		nx=x+dx[dir],ny=y+dy[dir];
		if(nx>=0 && nx<=m*2+2 && ny>=0 && ny<=n+1){
			if(fie[nx][ny]==0){
				x+=dx[dir]*2;
				y+=dy[dir]*2;
				if(fie[x+dx[(dir+1)%4]][y+dy[(dir+1)%4]]==0){
					dir=(dir+1)%4;
				}
			}else{
				if(fie[x+dx[(dir+1)%4]][y+dy[(dir+1)%4]]==0){
					dir=(dir+1)%4;
					x+=dx[dir]*2;
					y+=dy[dir]*2;
				}else if(fie[x+dx[(dir+3)%4]][y+dy[(dir+3)%4]]==0){
					dir=(dir+3)%4;
					x+=dx[dir]*2;
					y+=dy[dir]*2;
					printf("%c",s[dir]);
				}else{
					dir=(dir+2)%4;
					x+=dx[dir]*2;
					y+=dy[dir]*2;
					printf("%c",s[(dir+1)%4]);
					printf("%c",s[dir]);
				}
			}
		}else dir=(dir+1)%4;
		//printf("%d %d %d %d %d\n",x,y,dir,dx[dir],dy[dir]);
		if(x==0 && y==0)break;
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1160
import sys
n = int(input())
src = [input() for _ in range(n)]
tmp = ''
for i,s in enumerate(src):
    if i == 0:
        tmp = s[-1]
    else:
        if s[0] != tmp:
            print('No')
            sys.exit()
        tmp = s[-1]
if len(src) != len(set(src)):
    print('No')
    sys.exit()
print('Yes')

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

int main() {    
    long long int n;
    cin>>n;
    if(n>=400&&n<=599)
    cout<<"8";
    else if(n>=600&&n<=799)
    cout<<"7";
    else if(n>=800&&n<=999)
    cout<<"6";
    else if(n>=1000&&n<=1199)
    cout<<"5";
    else if(n>=1200&&n<=1399)
    cout<<"4";
    else if(n>=1400&&n<=1599)
    cout<<"3";
    else if(n>=1600&&n<=1799)
    cout<<"2";
    else
    cout<<"1";
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define INF 999999999
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using llong = long long;
using namespace std;

int main(){
    string s;
    cin >> s;
    rep(i,3) if(s[i] == s[i+1]){
        cout << "Bad" << endl;
        return 0;
    }
    cout << "Good" << endl;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };
static const int mod = 1000000007;
static const int MAX_M = 100000;

int dat[MAX_M*3],lazy[MAX_M*3];

class LazySegmentTree{
public:

    int n;
    LazySegmentTree(vector<int> v){
        n=1;
        while(n<v.size())n*=2;
        for(int i=0;i<v.size();++i)dat[n+i-1]=v[i];
        for(int i=0;i<2*n-1;++i)lazy[i]=0;
        for(int i=n-2;i>=0;--i)dat[i]=dat[2*i+1]+dat[2*i+2];
    }

    void eval(int k,int l,int r){
        if(lazy[k]!=0){
            dat[k]+=lazy[k];
            if(r-l>1){
                lazy[2*k+1]+=lazy[k]/2;
                lazy[2*k+2]+=lazy[k]/2;
            }
            lazy[k]=0;
        }
    }

    void add(int a,int b,int x,int k,int l,int r){
        eval(k,l,r);
        if(b<=l||r<=a)return;
        if(a<=l&&r<=b){
            lazy[k]+=(r-l)*x;
            eval(k,l,r);
        }
        else{
            add(a,b,x,2*k+1,l,(l+r)/2);
            add(a,b,x,2*k+2,(l+r)/2,r);
            dat[k]=dat[2*k+1]+dat[2*k+2];
        }
    }

    int query(int a,int b,int k,int l,int r){
        eval(k,l,r);
        if(b<=l||r<=a)return 0;
        if(a<=l&&r<=b)return dat[k];
        int vl = query(a,b,2*k+1,l,(l+r)/2);
        int vr = query(a,b,2*k+2,(l+r)/2,r);
        return vl+vr;
    }
};

int N,M;
int L[MAX_M*3],R[MAX_M*3];
vector<P1> len[MAX_M*3];
vector<int> init(MAX_M,0);
LazySegmentTree seg(init);
int pre;

void solve(int d){
    //cout<<"/////////////////////"<<endl;
    //cout<<d<<endl;
    //res=0;
    int res=N-(pre+len[d].size());
    pre+=len[d].size();
    //cout<<res<<endl;
    for(auto v : len[d]){
        int l = v.first,r = v.second;
        //cout<<l<<" "<<r<<endl;
        seg.add(l,r+1,1,0,0,seg.n);
    }
    int x=0,t=1;
    while(1){
        if(x>M)break;
        res+=seg.query(x,x+1,0,0,seg.n);
        //cout<<x<<" "<<seg.query(x,x+1,0,0,seg.n)<<endl;
        x=d*t;
        t++;
    }
    cout<<res<<endl;
    //cout<<"/////////////////////"<<endl;
    //cout<<res<<endl;
}


signed main(){
    cin>>N>>M;
    for(int i=0;i<N;++i){
        cin>>L[i]>>R[i];
        len[R[i]-L[i]+1].PB(P1(L[i],R[i]));
    }
    //cout<<res<<endl;
    for(int i=1;i<=M;++i){
        solve(i);
    }
}


Measured memory_bytes: 25200
using System;
using System.Collections.Generic;
using System.Linq;

namespace program{
	class Program{
		static void Main(){
			int[] A = Console.ReadLine().Split(' ').Select(x=>int.Parse(x)).ToArray();
if(A[1]>=A[2]) Console.WriteLine("delicious");
else if(A[2]-A[1]<=A[0]) Console.WriteLine("safe");
else Console.WriteLine("dangerous");
return;
		}
	}
}



Measured memory_bytes: 13268
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int x;
    cin >> x;
    int index = 1;
    while (1) {
        if (index * x % 360 == 0) {
            cout << index << endl;
            return 0;
        }
        index++;
    }
}


Measured memory_bytes: 3636
package main
import(
  "fmt"
)
func min(a int, b int) int {
  if a < b {
    return a
  } else {
    return b
  }
}
func main(){
  var a, b, c, x, y, d int
  fmt.Scan(&a, &b, &c, &x, &y)
  c = min(c*2, a+b)
  d = min(x,y)
  fmt.Println(c*d + min(a,c)*(x-d) + min(b,c)*(y-d))
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;i<n;i++)
#define ll long long
#define pii pair < int , int >
#define vi vector < int >
#define pb push_back
#define F first
#define S second
#define clr(x) memset(x, 0, sizeof(x))
#define init(x, a) memset(x, a, sizeof(x))
#define vll vector < long long int >
#define sll set < long long int >
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main()
{
	fastIO;
	ll n,m,i,j,k,a[100001],minIndex,mn=1e9+7,left,right=0;
	cin>>n>>k;
	Fo(i,1,n+1)
	{
		cin>>a[i];
		if(mn>a[i])
		{
			mn = a[i];
			minIndex = i;
		}
	}
	left = (minIndex-1)/(k-1) + ((minIndex-1)%(k-1)!=0);
	minIndex -= (minIndex-left*(k-1)-1);
	if(minIndex<n)right = (n-minIndex)/(k-1) + ((n-minIndex)%(k-1)!=0);
	cout<<left+right;
	return(0);
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

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

// math
//-------------------------------------------
template <class T> inline T sqr(T x) { return x * x; }

// typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

// container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c)                                                             \
  for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

// constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

// clear memory
#define CLR(a) memset((a), 0, sizeof(a))

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                                               \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"                       \
       << " " << __FILE__ << endl;

void solve(long long N, std::vector<long long> B) {
  vector<LL> A;
  A.push_back(B[0]);
  REP(i, N-1){
    A.PB(B[i]);
    if(i != N-2 &&A[i+1]>B[i+1]){
    A[i+1] = min(A[i+1], B[i+1]);
    }
  }
  LL ans =0;
  REP(i,N){
    // debug(A[i]);
    ans+=A[i];
  }
  cout<<ans<<endl;

}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> B(N - 1);
  for (int i = 0; i < N - 1; i++) {
    scanf("%lld", &B[i]);
  }
  solve(N, std::move(B));
  return 0;
}


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

typedef long long LL;
typedef stringstream strstm;
#define PI acos(-1.0)
#define E 2.718281829459
#define pb push_back
#define lowbit(x) (x & (-x))
#define DBG(x) cout << (x) << " ";
#define MST(a,b) memset(a,b,sizeof(a));
#define _for(i,a,b) for(int i = (a); i < (b); ++i)
#define _rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define _ech(x,z) for(auto x = z.begin(); x != z.end(); ++x)

struct FastIO {
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint() {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline LL xlongint() {
        LL s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s) {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c> 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x) {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x) {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s) {
        while (*s) wchar(*s++);
    }
    ~FastIO() {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;


const int maxn = 10011;
set<int> st;
int arr[maxn];

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n; cin >> n;
    _for(i,0,n){
        cin >> arr[i];
        st.insert(arr[i]);
    } 
    cout << st.size() << endl;
}


Measured memory_bytes: 256
from collections import deque

class Dinic:
    class edge:
        def __init__(self,to,cap,rev):
            self.to,self.cap,self.rev=to,cap,rev

    def __init__(self,v):
        self.numv=v
        self.G=[[] for _ in range(self.numv)]

    def add(self,fr,to,cap):
        self.G[fr].append(self.edge(to,cap,len(self.G[to])))
        self.G[to].append(self.edge(fr,0,len(self.G[fr])-1))

    def bfs(self,s):
        self.level=[-1]*self.numv
        self.level[s]=0
        que=deque()
        que.append(s)
        while len(que)!=0:
            v=que.popleft()
            for i in range(len(self.G[v])):
                e=self.G[v][i]
                if e.cap>0 and self.level[e.to]<0:
                    self.level[e.to]=self.level[v]+1
                    que.append(e.to)

    def dfs(self,v,t,f):
        if v==t:return f
        for i in range(self.iter[v],len(self.G[v])):
            self.iter[v]=i
            e=self.G[v][i]
            if e.cap>0 and self.level[v]<self.level[e.to]:
                d=self.dfs(e.to,t,min(f,e.cap))
                if d>0:
                    e.cap-=d
                    self.G[e.to][e.rev].cap+=d
                    return d
        return 0

    def max_flow(self,s,t):
        flow=0
        inf=float('inf')
        while 1:
            self.bfs(s)
            if self.level[t]<0:return flow
            self.iter=[0]*self.numv
            f=self.dfs(s,t,inf)
            while f>0:
                flow+=f
                f=self.dfs(s,t,inf)

V,E=map(int,input().split())
MF=Dinic(V)
for i in range(E):
    u,v,c=map(int,input().split())
    MF.add(u,v,c)
print(MF.max_flow(0,V-1))

Measured memory_bytes: 8340
N, M = map(int, input().split())
KS = [list(map(int, input().split())) for i in range(M)]
P = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    switches = bin(i)[2:].zfill(N)
    for j in range(M):
        _, *S = KS[j]
        on = 0
        for k, s in enumerate(switches, 1):
            if s == '1' and k in S:
                on += 1
        if on % 2 != P[j]:
            all_light_on = False
            break
    else:
        ans += 1
print(ans)

Measured memory_bytes: 74376
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //昇順
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順

int main(){
  string s;
  cin >> s;
  ll sum = stol(s);
  vector<char> hoge(s.length());
  for (int i = 0; i < s.length(); i++){
    hoge[i] = s[i];
  }
  
  // int count = 1;
  // int cut_posi = 0;
  vector<string> fuga;
  string start_s = {s[0]};
  for (int bit = 1; bit < (1 << (s.length() - 1)); bit++){
    start_s = {s[0]};
    // cout << bitset<3>(bit) << endl;
    for (int i = 0; i < s.length() - 1; i++){
      if (bit >> ((s.length() - 2) - i) & 1){
        fuga.push_back(start_s);
        start_s = s[i + 1];
      }else{
        start_s += {s[i+1]};
      }
    }
    fuga.push_back(start_s);
    // copy(fuga.begin(), fuga.end(), ostream_iterator<string>(cout, " "));
    // cout << endl;
    for (int i = 0; i < fuga.size(); i++){
      sum += stol(fuga[i]);
    }
    fuga.clear();
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){

    char a[1000];
    while(scanf("%[^\n]",a) != EOF){
        getchar();
        bool flg = 0;
        for(int i = 0; i < 26; i++){
            unsigned char ans[1000] = {0};
            for(int j = 0; j < strlen(a); j++){
                if(a[j] == ' ' || a[j] == '.') ans[j] = a[j];
                else ans[j] = a[j] + i;
                if(ans[j] > 'z') ans[j] -= 26;
            }
            for(int j = 0; j < strlen(a); j++){
                if(ans[j] == 't' && ans[j+1] == 'h'){
                    if(ans[j+2] == 'e' && ans[j+3] == ' ' || ans[j+3] == 0 || ans[j+3] == '.')flg = 1;
                    if(ans[j+2] == 'i' && ans[j+3] == 's' && ans[j+4] == ' ' || ans[j+4] == 0 || ans[j+4] == '.')flg = 1;
                    if(ans[j+2] == 'a' && ans[j+3] == 't' && ans[j+4] == ' ' || ans[j+4] == 0 || ans[j+4] == '.')flg = 1;
                }
                if(flg){
                    if(j == 0){
                        cout << ans << endl;
                        goto end;
                    }
                    else{
                        if(ans[j-1] == ' '){
                            cout << ans << endl;
                            goto end;
                        }
                    }
                }
            }
        }
        end:;
        for(int i = 0;i < 1000; i++) a[i] = 0;
    }

    return 0;
}

Measured memory_bytes: 1148
import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans
mod = 10**9+7 #出力の制限
N = 10**5 * 2 + 1
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,k = m()

dp = [0 for i in range(n+1)]
dp[0] = n+1
co = 0
if k-1 == 0:
    co += dp[0]
for i in range(1,n+1):
    dp[i] = dp[i-1] + (n - 2*i)
    dp[i] %= mod
    if i >= k-1:
        co += dp[i]
        co %= mod

print(co)





Measured memory_bytes: 123412
#include<bits/stdc++.h>
using namespace std;
const bool DEBUG = true;
#define coutd if(DEBUG) cout 
#define ff first
#define ss second
#define debug(x) cout << "> x:" << x << endl;
#define len(x) int(x.size())
#define all(x) x.begin(), x.end()
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<ll>;
using vii = vector<ii>;
const double PI = acos(-1);
const double EPS = 1e-9;

int main(){
	ios::sync_with_stdio(0);
	int x, y;
	cin >> x >> y;
	int ans = 0;
	if(x==1) ans+=300000;
	if(x==2) ans+=200000;
	if(x==3) ans+=100000;
	
	if(y==1) ans+=300000;
	if(y==2) ans+=200000;
	if(y==3) ans+=100000;
	
	if(x==1 and x==y) ans+=400000;
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int li;
using namespace std;
int main()
{
    fast_io;
  li n;
  double sum=0.0;
  cin>>n;
  li a[n],i;
  for(i=0;i<n;i++)
  {cin>>a[i];
   sum+=(1*1.0/a[i]);
  }
  cout<<1/sum;

    return 0;
}

Measured memory_bytes: 256
#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;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


string to_string(string s) {
	return '"' + s + '"';
}

string to_string(const char* s) {
	return to_string((string) s);
}

string to_string(bool b) {
	return (b ? "true" : "false");
}

string to_string(char ch) {
	return string("'")+ch+string("'");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
	bool start = true;
	string res = "{";
	while (first!=last) {
		if (!start) {
			res += ", ";
		}
		start = false;
		res += to_string(*first);
		++first;
	}
	res += "}";
	return res;
}

template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
	input>>x.F>>x.S;
	return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x){
	for(auto& i:x)
		input>>i;
	return input;
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif



const int mod=1e9+7;

int mul(int a,int b)
{
	return (a*1ll*b)%mod;
	}
	
void add(int &a,int b)
{
	a+=b;
	if(a>=mod)a-=mod;
	}
int powz(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=mul(res,a);
		b/=2;
		a=mul(a,a);
		}
	return res;
	}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=300005;

void solve()
{  
int n;
cin>>n;
vi a(n);
cin>>a;
int preg[n+1]={0},posg[n+2]={0};
int pref=-1;
int ans=0;
for(int i=0;i<n;i++)
{
	if(pref==-1){pref=a[i];}
	else
	{
		pref=__gcd(pref,a[i]);
		}
		preg[i+1]=pref;
	}
	pref=-1;
for(int i=n-1;i>=0;i--)
{
	if(pref==-1){pref=a[i];}
	else
	{
		pref=__gcd(pref,a[i]);
		}
		posg[i+1]=pref;
	}
for(int i=0;i<n;i++)
{
	ans=max(ans,__gcd(preg[i],posg[i+2]));
	}
	cout<<ans;
} 
	
	
   
	
	

signed main()
{   
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tc=1;
	//cin>>tc;
    for(int i=0;i<tc;i++)
	{
		//cout<<"Case #"<<i+1<<": "; 
        solve();
		}
	
	}


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

int n,S;
vector<int> r;

int input(){
  cin>>n>>S;
  if(n==0&&S==0)return false;
  r.clear();r.resize(n);
  for(int i=0;i<n;i++){
    cin>>r[i];
  }
  return true;
}

int solve(){
  int ans = 0;
  sort(r.begin(),r.end());
  for(int i=0;i<r.size();i++){
    const int s = S-r[i];
    for(int j=i+1;j<r.size();j++){
      if(s<r[j]){
        ans += r.size()-j;
        break;
      }
    }
  }
  return ans;
}

int main(){
  while(input())cout<<solve()<<endl;

}

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

n,k = (int(x) for x in input().split())
lst = [0 for _ in range(n)]
for i in range(k):
    d = int(input())
    seq = [int(x) for x in input().split()]
    for val in seq:
        lst[val-1] += 1
print(sum((val==0 for val in lst)))


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

int main () {
  int N;
  cin >> N ;
  long long sum=0;
  for (int i=0;i<=N;i++){
    if (i % 5 == 0) continue;
    if(i % 3 == 0) continue;
    sum+=i;
  }

  cout << sum;
  return 0;
}


Measured memory_bytes: 3600
n = gets.to_i
A = gets.split.map(&:to_i)
B = Array.new(n)
for x in 0..n-1
  B[x] = 0
end
for i in 0..n-1
  while A[i]%2 == 0
    B[i] = B[i] + 1
    A[i] = A[i]/2
  end
end
puts B.min

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() {
  int N;
  cin >> N;
  map<char, int> A{};
  {
    string S;
    cin >> S;
    REP(i, S.size()) { A[S[i]]++; }
  }
  REP(i, N - 1) {
    map<char, int> B{};
    string S;
    cin >> S;
    REP(j, S.size()) { B[S[j]]++; }
    REP(j, 26) {
      char a = j + 'a';
      A[a] = min(A[a], B[a]);
    }
  }
  REP(i, 26) {
    char a = i + 'a';
    REP(j, A[a]) { cout << a; }
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
  string s;
  get(s);
  print(s.substr(0, 4) + " " + s.substr(4, 8));
  return 0;
}

Measured memory_bytes: 256
n = int(input())
a, b = [], []
ans = 0


def solve(x, y):
    n = -(-x//y)
    return (y)*n-x


for _ in range(n):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)

for i in reversed(range(n)):
    ans += solve(a[i]+ans, b[i])

print(ans)


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

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  bool ans=true;
  while(ans){
    c-=b;
    a-=d;
    if(c<=0){
      cout<<"Yes"<<endl;
      ans=false;
      break;
    }
    if(a<=0){
      cout<<"No"<<endl;
      ans=false;
      break;
    }
  }
}


Measured memory_bytes: 3596
#include<iostream>

using namespace std;

int n;
long long m, k, arr[55];

int main() {
	cin >> k; n = 50;
	for(int i = 0; i < n; i++) arr[i] = i;
	m = 1LL * k/n;
	for(int i = 0; i < n; i++) {
		arr[i] += m;
	}
	for(int i = 0; i < k % n; i++) {
		for(int j = 0; j < n; j++) {
			if(j == i) {
				arr[j]+=n;
			} else {
				arr[j]--;
			}
		}
	}
	cout << n << "\n";
	for(int i = 0; i < n; i++) cout << arr[i] << " ";
	cout << "\n";
	return 0;
}

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

int N,cost[10000];
int dp[2][5010][2];
const int INF=1e9;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++)scanf("%d",&cost[i]);

    fill_n(**dp,2*2*5010,INF);
    dp[0][1][0]=dp[0][0][1]=0;

    for(int i=0;i<N-1;i++){
        for(int j=0;j<=N/2;j++){
            dp[(i+1)&1][j+1][0]=min(dp[i&1][j][0],dp[i&1][j][1]+cost[i]);
            dp[(i+1)&1][j][1]=min(dp[i&1][j][0]+cost[i],dp[i&1][j][1]);
        }
    }

    printf("%d\n",min(dp[(N-1)&1][N/2][0],dp[(N-1)&1][N/2][1]));
    return 0;
}

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

using namespace std;

int main() {

	while (1) {
		string s;
		cin >> s;
		if (s == "-") { return 0; }

		string news = s;

		int m;
		cin >> m;

		for (int i = 0; i < m; i++) {

			int h;
			cin >> h;
			h--;
			for (int j = h + 1; j < s.size(); j++) {
				news[j - h - 1] = s[j];
			}
			for (int j = 0; j <= h; j++) {
				news[s.size() - 1 - h + j] = s[j];
			}
			s = news;
		}
		cout << s << endl;
	}
}


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

int main() {
    int N, t, x, y, a = 0, b = 0, c = 0;
    string ans = "Yes\n";
    cin >> N;
    rep(i, N) {
        cin >> t >> x >> y;
        if (abs(x - a) + abs(y - b) > t - a) {
            ans = "No\n";
        }
        if ((abs(x - a) + abs(y - b) + t - a) % 2) {
            ans = "No\n";
        }
    }
    cout << ans;
}

Measured memory_bytes: 256
N = int(input())
dp = [float("inf") for i in range(N+100)]
dp[0] = 0 
for i in range(1,N+50):
    r = 1 
    dp[i] = min(dp[i],dp[i-r]+1)
    p = 6 
    while (i>=p) :
        dp[i] = min(dp[i],dp[i-p]+1)
        p *= 6
    q = 9 
    while (i>=q) :
        dp[i] = min(dp[i],dp[i-q]+1)
        q *= 9
print(dp[N])

Measured memory_bytes: 6296
#include <bits/stdc++.h>
#define int long long int
#define all(v) v.begin(),v.end()
#define ov(v) for(int i=0;i<(v).size();i++)cout<<v[i]<<" ";cout<<endl;
#define N 10000
using namespace std;
void solve()
{
	string s;
	cin>>s;
	int sm = 0;
	for(auto i:s)
		sm+=(i-'0');
	if(sm%9==0)cout<<"Yes";
	else cout<<"No";
}
signed main() 
{
	// int t;
	// cin>>t;
	// while(t--)
	solve();
	return 0; 
}

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

int main(){
  int n;
  cin >> n;
  bool flag = false;
  if(n%10 == 7){
    flag = true;
  }
  n /= 10;
  if(n%10 == 7){
    flag = true;
  }
  n /= 10;
  if(n == 7){
    flag = true;
  }
  if(flag)
     cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 100005;
const int INF = (LL)1e9 + 5;
const LL MOD = 998244353;

int N, K, h[MAXN], dp[MAXN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> h[i];
		dp[i] = i == 0 ? 0 : INF;
		for (int j = i - 1; j >= 0 && i - j <= K; j--) {
			dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
		}
	}
	
	cout << dp[N - 1] << "\n";
}


Measured memory_bytes: 1024
//file_name:ABC53_A.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("ABC");}else{puts("ARC");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


int main() {
    int n;
    scanf("%d",&n);

    if(n<1200)yn;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,A,B,Plan1;
  cin >> N >> A >> B;
  Plan1 = N * A;
  if (Plan1 < B){
    cout << Plan1 << endl;
  }
  else{
    cout << B << endl;
  }
}

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

int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  
  int ans=0;
  for(int i=1;i<n-1;i++){
    if(a[i]<a[i-1]&&a[i]>a[i+1]){
      ans++;
    }else if(a[i]>a[i-1]&&a[i]<a[i+1]){
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>


int main() {
	int n, k, ans;
	ans = 1;
	scanf("%d", &n);
	scanf("%d", &k);
	for (int i = 0; i < n; i++) {
		if (ans < k) {
			ans = ans * 2;
		}
		else {
			ans += k;
		}
	}
	printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;

int n, m;
LL x;
pair<int, PII> E[2005];
int par[1005], siz[1005], dis[1005];

int unite(int u, int v, int w)
{
	int cur = -1;
	while(u != v) {
		if(par[u] == u && par[v] == v) {
			if(siz[u] > siz[v]) swap(u, v);
			par[u] = v;
			dis[u] = w;
			siz[v] += siz[u];
			return -1;
		}
		if(par[u] == u || par[v] != v && siz[u] > siz[v]) {
			cur = max(cur, dis[v]);
			v = par[v];
		} else {
			cur = max(cur, dis[u]);
			u = par[u];
		}
	}
	return cur;
}

int main()
{
	scanf("%d%d%lld", &n, &m, &x);
	if(n == 1) {
		if(x == 0) printf("1\n");
		else printf("0\n");
		return 0;
	}
	rep1(i, n) {
		par[i] = i;
		siz[i] = 1;
	}
	rep(i, m) scanf("%d%d%d", &E[i].second.first, &E[i].second.second, &E[i].first);
	sort(E, E + m);
	rep(i, m) {
		int cur = unite(E[i].second.first, E[i].second.second, E[i].first);
		if(cur == -1) {
			x -= E[i].first;
			E[i].first = 0;
		} else E[i].first -= cur;
	}
	
	sort(E, E + m);
	int cur = 1, ans = 0;
	for(int i = m - 1; i > 0; i --) {
		cur = 2 * cur % MOD;
		if(E[i].first == x) ans = (ans + cur) % MOD;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256