akhauriyash/Code-Regression huggingface dataset:
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

void dfs(int v, const vector<vector<int> > &G, vector<bool> &used, vector<int> &vs) {
	used[v] = true;
	for(const auto &to : G[v]) {
		if(!used[to]) dfs(to, G, used, vs);
	}
	vs.push_back(v);
}

void rdfs(int v, int k, const vector<vector<int> > &rG, vector<bool> &used, vector<int> &cmp) {
	used[v] = true;
	cmp[v] = k;
	for(const auto &to : rG[v]) {
		if(!used[to]) rdfs(to, k, rG, used, cmp);
	}
}

int scc(const vector<vector<int> > &G, vector<int> &cmp) {
	const int n = G.size();
	vector<bool> used(n, false);
	vector<int> vs;
	vs.reserve(n);

	for(int v = 0; v < n; ++v) {
		if(!used[v]) dfs(v, G, used, vs);
	}

	vector<vector<int> > rG(n);
	for(int v = 0; v < n; ++v) {
		for(const auto &to : G[v]) {
			rG[to].emplace_back(v);
		}
	}

	fill(used.begin(), used.end(), false);
	int k = 0;
	for(int i = n - 1; i >= 0; --i) {
		if(!used[vs[i]]) rdfs(vs[i], k++, rG, used, cmp);
	}
	return k;
}

typedef int weight;
constexpr weight INF = (1 << 28);
constexpr weight EPS = 1e-8;

struct edge {
	int to;
	weight cost;
	edge(int to_, weight cost_):to(to_), cost(cost_){}
};

weight minimum_spanning_arborescence(int r, const vector<vector<edge> > &G, weight sum = 0) {
	const int n = G.size();

	vector<int> rev(n, -1);
	vector<weight> minimum_weight(n, INF);
	for(int v = 0; v < n; ++v) {
		for(const auto &e : G[v]) {
			if(minimum_weight[e.to] > e.cost + EPS) {
				minimum_weight[e.to] = e.cost;
				rev[e.to] = v;
			}
		}
	}

	vector<vector<int> > tG(n);
	for(int v = 0; v < n; ++v) {
		if(v == r) continue;
		if(rev[v] == -1) return INF;
		tG[rev[v]].emplace_back(v);
		sum += minimum_weight[v];
	}

	vector<int> cmp(n);
	const int num = scc(tG, cmp);
	if(num == n) return sum;

	vector<vector<edge> > next_G(num);
	for(int v = 0; v < n; ++v) {
		const int from = cmp[v];
		for(const auto &e : G[v]) {
			const int to = cmp[e.to];
			if(from == to) continue;

			const int cost = e.cost - minimum_weight[e.to];
			next_G[from].push_back({to, cost});
		}
	}

	return minimum_spanning_arborescence(cmp[r], next_G, sum);
}

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

	int n, m, r;
	cin >> n >> m >> r;

	vector<vector<edge>> G(n);
	for(int i = 0; i < m; ++i) {
		int from, to, w;
		cin >> from >> to >> w;
		G[from].emplace_back(to, w);
	}

	cout << minimum_spanning_arborescence(r, G) << endl;

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1664
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll N, M;
	cin >> N >> M;
	ll d = M / N;
	ll r = M % N;

	for (ll i = d; i > 0; i--) {
		if (r % i == 0) {
			cout << i << endl;
			return 0;
		}

		r += N;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << ", "
template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){ \
 if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;}
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef unsigned int uint;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unsigned char uchar;
struct secure_hash {
 static uint64_t splitmix64(uint64_t x) {
  x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); }
 size_t operator()(uint64_t x) const {
  static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } };
template<typename T> using V = vector<T>;
template<typename T, typename U> using umap = unordered_map<T,U,secure_hash>;
template<typename T> using uset = unordered_set<T,secure_hash>;
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using max_heap = priority_queue<T>;

template <typename T>
struct SegmentTree {
    int n;
    T* t;
    T zero_val;

    inline T operation(T a, T b)
    {
        return max(a, b);
    }
    void setup(int n_, T zero_val_)
    {
        n = n_;
        zero_val = zero_val_;
        t = new T[2*n];
        memset(t, 0, 2*n*sizeof(T));
    }
    void build()
    {
        for (int i = n-1; i > 0; --i) {
            t[i] = operation(t[2*i], t[2*i+1]);
        }
    }
    void update(int p, T v)
    {
        t[p+n] = v;
        for (int i = p+n; i > 1; i /= 2) {
            t[i/2] = operation(t[i], t[i^1]);
        }
    }
    T query(int l, int r)
    {
        T res = zero_val;
        ++r; // make range inclusive
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l&1) res = operation(res, t[l++]);
            if (r&1) res = operation(res, t[--r]);
        }
        return res;
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    V<int> h(n), a(n);
    rep(i,0,n) cin >> h[i];
    rep(i,0,n) cin >> a[i];
    SegmentTree<ll> st;
    st.setup(n+1, 0);
    st.build();
    for (int i = 0; i < n; ++i) {
        // for (int k = 0; k < h[i]; ++k) {
        //     dp[h[i]] = max(dp[h[i]], dp[k] + a[i]);
        // }
        // CODE ABOVE OPTIMIZED:
        st.update(h[i], max(st.query(h[i], h[i]), st.query(1, h[i]) + a[i]));
    }
    cout << st.query(1, n) << endl;
}


Measured memory_bytes: 4992
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    map<int,int>pos;
    rep(i,n){
        cin >> a[i];
        pos[a[i]] = i;
    }
    set<int>st;
    st.insert(-1);
    st.insert(n);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        auto it = st.lower_bound(pos[i]);
        int r = *it;
        it--;
        int l = *it;
        ans += (ll)i * (l-pos[i])*(pos[i]-r);
        st.insert(pos[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 19840
n=int(input())
l=[]
for i in range(1,n+1):
    l.append(i)
#print(l)
count=[]
keta=1
#print(keta)
for i in range(n):
    if l[i]//10==0:
        count.append(keta)
    elif 1<=l[i]//10<=9:
        keta+=1
        count.append(keta)
        keta=1
    elif 10<=l[i]//10<=99:
        keta+=2
        count.append(keta)
        keta=1
    elif 100<=l[i]//10<=999:
        keta+=3
        count.append(keta)
        keta=1
    elif 1000<=l[i]//10<=9999:
        keta+=4
        count.append(keta)
        keta=1
    elif 10000<=l[i]//10<=99999:
        keta+=5
        count.append(keta)
        keta=1
#print(count)
c=0
for i in count:
    if i==1 or i==3 or i==5:
        c+=1
print(c)

Measured memory_bytes: 7860
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
int a[3],n;
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
scanf("%d",&a[j]);
}
sort(a,a+3);
if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2])printf("YES\n");
else printf("NO\n");
}
}

Measured memory_bytes: 2756
const main = (input) => {
  const [A, B, N] = input.trim().split(' ').map(Number)
  let x = B - 1 <= N ? B - 1 : N

  return console.log(Math.floor(A*x/B) - A * Math.floor(x/B))
}

process.env.MYTEST ? test() : main(require('fs').readFileSync('/dev/stdin', 'utf8'))

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

int main(){
    int N, M, X, Y, tmp;
    cin >> N >> M >> X >> Y;
    vector<int> Xs;
    vector<int> Ys;
    for(int i = 0; i < N; i++){
        cin >> tmp;
        Xs.push_back(tmp);
    }
    for(int i = 0; i < M; i++){
        cin >> tmp;
        Ys.push_back(tmp);
    }
    sort(Xs.begin(), Xs.end());
    sort(Ys.begin(), Ys.end());
    int Xback = Xs.back();
    int Yfront = Ys.front();
    if(Xback >= Yfront || X >= Y || Y <= Xback || X >= Yfront) cout << "War" << endl;
    else cout << "No War" << endl;

    return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for (int i = 0; i < N; ++i) cin >> p[i];

  int ans = 0;
  for (int i = 1; i < N - 1; ++i) {
    if ((p[i - 1] < p[i]) && (p[i] < p[i + 1])) ans++;
    else if ((p[i - 1] > p[i]) && (p[i] > p[i + 1])) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main(void) {
  int R[MAX], n;
  cin >> n;
  for (int i=0;i<n;i++) cin >>R[i];
  int maxv = -2000000000; // ???????°??????????????????????????¨????
  int minv = R[0];

  for(int i=1;i<n;i++) {
    maxv = max(maxv, R[i] - minv);
    minv = min(minv, R[i]);
  }
  cout << maxv << endl;
  return 0;
}

Measured memory_bytes: 3860
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using vi = vector<int>;

#define in(v) v; cin >> v;
void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rrep(i,n) for(long long i=(n);i>=0;--i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

// ========== debug ==========
template<class T>ostream& operator<<(ostream& os,const vector<T>& vec){os<<"{";for(size_t i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
ostream& operator<<(ostream& os,const vector<char>&v){for(size_t i=0;i<v.size();++i)os<<v[i];return os;}
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>& rhs){os<<"("<<rhs.first<<", "<<rhs.second<<")";return os;}

#ifdef LOCAL
void debug() {cerr << "\n";}
template<class First> void debug(const First& first) {cerr<<first<<"\n";}
template<class First, class... Rest> void debug(const First& first, const Rest&... rest) {cerr<<first<<",";debug(rest...);}
void debug2() {cerr << "\n";}
template<class First> void debug2(const First& first) {cerr<<first<<" ";}
template<class First, class... Rest> void debug2(const First& first, const Rest&... rest) {cerr<<first<<" ";debug2(rest...);}
#else
#define debug(...) 42
#define debug2(...) 42
#endif
// ===========================

int main() {
  int N;
  ins(N);
  vi ans(10001, 0);
  rep(_x, 100) {
    rep(_y, 100) {
      rep(_z, 100) {
        int x = _x + 1, y = _y + 1, z = _z + 1;
        if (x * x + y * y + z * z + x * y + y * z + z * x > 10000)
          continue;
        ++ans[x * x + y * y + z * z + x * y + y * z + z * x];
      }
    }
  }
  rep(i, N) {
    cout << ans[i+1] << endl;
  }

  return 0;
}


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

using namespace std;
typedef long long LL;

class UnionFind {
public:
    vector <LL> par;
    vector <LL> siz;

    UnionFind(LL sz_): par(sz_), siz(sz_, 1LL) {
        for (LL i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(LL sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (LL i = 0; i < sz_; ++i) par[i] = i;
    }

    LL root(LL x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    bool unite(LL x, LL y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool same(LL x, LL y) {
        return root(x) == root(y);
    }

    LL size(LL x) {
        return siz[root(x)];
    }
};

int main(){
  int N, M, K;
  cin >> N >> M >> K;
  vector<int> ans(N);
  vector<int> fr(N);
  UnionFind tree(N);
  rep(i,M){
    int a, b;
    cin >> a >> b;
    a--; b--;
    fr[a]++; fr[b]++;
    tree.unite(a,b);
  }
  rep(i,N) ans[i]=tree.size(i)-fr[i]-1;
  rep(i,K){
    int c, d;
    cin >> c >> d;
    c--; d--;
    if(tree.same(c,d)){
      ans[c]--;
      ans[d]--;
    }
  }
  rep(i,N-1) cout << ans[i] << " ";
  cout << ans[N-1] << endl;

  return 0;
}


Measured memory_bytes: 3200
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define _for(i,a,b) for(int i = (a);i<(b);i++)
#define endl  '\n'
using namespace std;
const int mod=1e9+7;
const int MAX=1e6+7;
 int a[1005];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
   int n,k;cin>>n>>k;
   for(int i=0;i<n;i++)
   {
   		cin>>a[i];
   }
   sort(a,a+n);
   ll ans=0;
   for(int i=0;i<k;i++)
   ans+=a[i];
   cout<<ans;
    return 0;
}


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

using namespace std;

#define int long long

signed main(){
  vector<int> X, Y;
  int N;

  cin>>N;

  X.resize(N);
  Y.resize(N);

  for(int i = 0; i < N; i++){
    cin>>X[i];
    Y[i] = X[i];
  }

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

  int a = N/2-1, b = N/2;

  for(int i = 0; i < N; i++){
    if(Y[i] <= X[a]) {
      cout<<X[b]<<endl;
    } else {
      cout<<X[a]<<endl;
    }
  }
  return 0;
}


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

namespace _171A
{
    class Program
    {
        static void Main(string[] args)
        {
            string readLine = Console.ReadLine();
            if(Char.IsUpper(Convert.ToChar(readLine)))
            {
                Console.WriteLine('A');
                return;
            }
            Console.WriteLine('a');


        }
    }
}


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

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

int main() {
    ll a, b;
    cin >> a >> b;
    ll n = gcd(a, b);
    ll cnt = 1;

    for (ll i = 2; i <= sqrt(n); i++) {
        if (n % i != 0) continue;
        cnt++;
        while (n % i == 0) {
            n = n / i;
        }
    }
    if (n != 1) cnt++;
    cout << cnt << endl;
    return 0;
}

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

S = input().rstrip()
l = [0]*2
y = S[:2]
m = S[2:]
l[0] = 0 if "01" <= y <= "12" else 1
l[1] = 1 if "01" <= m <= "12" else 0

if l[0] == 0 and l[1] == 1:
  print("AMBIGUOUS")
elif l[0] == 1 and l[1] == 1:
  print("YYMM")
elif l[0] == 0 and l[1] == 0:
  print("MMYY")  
else:
  print("NA")  

Measured memory_bytes: 3064
use text_io::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;

fn main() {
    let mut n:String = read!();
    let v:Vec<char> = n.chars().collect();
    let mut a:usize = 0;
    for i in 0..v.len() {
        if v[i]=='0' {a+=0; }
        if v[i]=='1' {a+=1; }
        if v[i]=='2' {a+=2; }
        if v[i]=='3' {a+=3; }
        if v[i]=='4' {a+=4; }
        if v[i]=='5' {a+=5; }
        if v[i]=='6' {a+=6; }
        if v[i]=='7' {a+=7; }
        if v[i]=='8' {a+=8; }
        if v[i]=='9' {a+=9; }
    }
    if a%9==0 {
        println!("Yes");
    }
    else {
        println!("No");
    }
}

Measured memory_bytes: 3172
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    let mut v2 = Vec::new();
    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        let v = s.trim().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect();
        v2.push(v);
    }
    v2
}

fn abc_a(){

    let k:usize = read();
    let result : String = (0..k).map(|v| "ACL").collect();
    println!("{}",result);
}

fn main() {

   abc_a();

}


Measured memory_bytes: 2128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> PI;
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};


typedef struct _state{
  int from,vis;
  double cost;
  bool operator<(const _state&r)const{
    return cost>r.cost;
  };
}state;

vector<PI> V[30];

main(){
  int n,m,p,a,b;
  while(cin>>n>>m>>p>>a>>b,n){
    --a,--b;
    int ti[n];
    rep(i,n)cin>>ti[i];

    rep(i,m)V[i].clear();

    rep(i,p){
      int x,y,z;
      cin>>x>>y>>z;
      --x,--y;
      V[x].pb(mp(y,z));
      V[y].pb(mp(x,z));
    }

    priority_queue<state> Q;
    state st;
    st.cost=0;
    st.vis=0;
    st.from=a;
    Q.push(st);

    double cost[1<<n][m];
    rep(i,1<<n)rep(j,m)cost[i][j]=1<<26;
    double ans=-1;

    while(!Q.empty()){
      int from=Q.top().from,cti=Q.top().vis;
      double ccost=Q.top().cost;
      Q.pop();
      if(cost[cti][from]<=ccost)continue;
      cost[cti][from]=ccost;
      if(from==b){
	ans=ccost;
	break;
      }

      rep(i,n){
	if(cti>>i&1)continue;
	rep(j,V[from].size()){
	  int to=V[from][j].first;
	  int cc=V[from][j].second;
	  double ncost=ccost+1.0*cc/ti[i];
	  st.from=to;
	  st.vis=cti|1<<i;
	  st.cost=ncost;
	  Q.push(st);
	}
      }
    }
    if(ans<0)cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
  }
}

Measured memory_bytes: 8380
// Why do we fall ? So we can learn to pick ourselves up.
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        long k = sc.nextLong();
        long n = s.length;
        if (n == 1) {
            if (k == 1) {
                System.out.println(0);
            } else {
                System.out.println(k/2);
            }
        } else {
                ArrayList<Long> aa = new ArrayList<>();
                long i = 0;
                long ss = 0L;
                while (true) {
                    if (i == n) {
                        break;
                    }
                    char curr = s[(int)i];
                    long temp = 1L;
                    i += 1;
                    if (i == n) {
                        break;
                    }
                    while (s[(int) i] == curr) {
                        temp += 1;
                        i += 1;
                        if (i == n) {
                            break;
                        }
                    }
                    aa.add(temp);

                }
                if(aa.size() > 1){
                    for (Long aLong : aa) {
                        ss += (aLong / 2L) * k;
                    }
                    if(s[0] == (s[(int) (n-1)]) && aa.get(0) %2 == 1 && aa.get(aa.size()-1)%2 == 1){
                        ss += k-1;
                    }
                } else {
                    ss += (n*k)/2L;
                }
                System.out.println(ss);
        }
    }
}


Measured memory_bytes: 23252
#include<cstdio>
#include<cstdlib>
#include<cstring>

struct Node{
    int key;
    Node *prev, *next;
};
Node *nil;
void init(){
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil;
    nil->prev = nil;
}
void insert(int key){
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
}
Node* listSearch(int key){
    Node *cur = nil->next;
    while(cur != nil && cur->key != key){
        cur = cur->next;
    }
    return cur;
}
void deleteNode(Node *t){
    if(t ==nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}
void deleteFirst(){
    deleteNode(nil->next);
}
void deleteLast(){
    deleteNode(nil->prev);
}
void deleteKey(int key){
    deleteNode(listSearch(key));
}
void printList(){
    Node *cur = nil->next;
    int isf = 0;
    while(1){
        if(cur == nil) break;
        if(isf++ > 0) printf(" ");
        printf("%d" , cur->key);
        cur = cur->next;
    }
    printf("\n");
}
int main(){
    int key ,n, i;
    int size=0;
    char com[20];
    int np=0, nd=0;
    scanf("%d", &n);
    init();
    for(i=0; i<n; i++){
        scanf("%s%d", com, &key);
        if(com[0] =='i'){insert(key); np++; size++;}
        else if(com[0] =='d'){
            if(strlen(com) > 6){
                if(com[6] =='F') deleteFirst();
                else if(com[6] =='L') deleteLast();
            }else{
                deleteKey(key); nd++;
            }
            size--;
        }
    }

    printList();
    return 0;
}



Measured memory_bytes: 33828
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)


def feel(x, a, b):
    if b <= a:
        return "delicious"
    elif b - a <= x:
        return "safe"
    else:
        return "dangerous"

def main():
    x, a, b = map(int, input().split())

    print(feel(x, a, b))

if __name__ == "__main__": main()


Measured memory_bytes: 3828
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main(){
	char a;
	string ans="";
	while (true){
		scanf("%c", &a);
		if (a=='\n'){
			break;
		}
		//a = ('a' <= a <= 'z') ? a - 32 : (('A' <= a <= 'Z') ? a + 32 : a);
		if ('a' <= a&&a<= 'z'){
			a -= 32;
		}
		else if ('A' <= a&&a <= 'Z'){
			a +=32;
		}
		else{
			
		}
		ans += a;
		//printf("%c\n", a);
	}
	//cout<<ans<<endl;
cout<<ans<<endl;
}


Measured memory_bytes: 3296
N,K=map(int,input().split())
S=str(input())
def change(A):
  if S[A]=="A":
    sub="a"
  elif S[A]=="B":
    sub="b"
  else:
    sub="c"
  return sub

if K==1:
  print(change(0)+S[1:])
elif K==N:
  print(S[:N-1]+change(K-1))
else:
  print(S[:K-1]+change(K-1)+S[K:])
  

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define ALL(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
const int MAX = (int)1e5 + 5;

template<typename T>
T gcd(T a, T b)
{
	T c;
	while (a != 0) {
		c = a; a = b%a;  b = c;
	}
	return b;
}

template<typename T>
T lcm(T m, T n)
{
	return ((m / gcd(m, n)) * n);
}

signed main() {
	ll a, b;
	while (cin >> a >> b) {
		cout << gcd(a, b) << " " << lcm(a, b) << endl;
	}
	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
  
using namespace std;
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
 
//Appropriately Changed
using edge=struct{int to,cost;};
using G=vector<vector<edge>>;
 
//Appropriately Changed
void add_edge(G &graph,int from,int to,int cost){ 
    graph[from].push_back({to,cost});
}
 
auto chuliu(const G &graph,int root){
    using W=int; const W inf=1<<28;
     
    const int n=graph.size();
    vector<int> cost(n,inf),pv(n,-1);
    rep(v,n) for(auto &e:graph[v]) if(chmin(cost[e.to],e.cost)) pv[e.to]=v;
 
    int led=-1,unuse=-1;
    vector<int> comp(n),used(n,-1);
    iota(begin(comp),end(comp),0);
     
    rep(v,n){
        if(used[v]!= -1 or cost[v]==inf or v==root) continue;
 
        int cur=used[v]=v;
        for(cur=pv[cur]; cur!=root && used[cur] == -1; cur=pv[cur]) used[cur]=v;
 
        if(used[cur]!=v) continue;
    	led=cur,comp[cur]=cur,v=n; 
    	for(int w=pv[cur]; w != cur; w=pv[w]) comp[w]=cur;
    }
 
    G ngraph(n),ret(n);
    using E=tuple<int,int,int>; map<E,E> dict;

    if(led==-1){
        rep(v,n) if(v!=root and pv[v]!=-1)add_edge(ret,pv[v],v,cost[v]);
        return ret;
    }

	rep(v,n) for(auto &e:graph[v]){
		int a=comp[v],b=comp[e.to],c=e.cost;
		if(comp[e.to]==led) c-=cost[e.to];
		if(a==b) continue;
		dict[E(a,b,c)]=E(v,e.to,e.cost);
		add_edge(ngraph,a,b,c);
	}
	
	auto ntree=chuliu(ngraph,comp[root]);

	rep(v,n) for(auto &e:ntree[v]){
		int a,b,c;
		tie(a,b,c)=dict[E(v,e.to,e.cost)];
		if(comp[b]==led) unuse=b;
		add_edge(ret,a,b,c);
	}

	rep(v,n) if(comp[v]==led and v!=unuse) add_edge(ret,pv[v],v,cost[v]);
    return ret;
}
 
int main(void){
    int v,e,r;
    cin >> v >> e >> r;
    G graph(v);
    rep(i,e){
        int a,b,w;
        cin >> a >> b >> w;
        add_edge(graph,a,b,w);
    }
 
    auto tree=chuliu(graph,r);
    int ans=0;
    rep(i,v) for(auto &e:tree[i]) ans+=e.cost;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5084
#include <iostream>
using namespace std;
int main(){
  int n, m;
  cin >> n >> m;
  double a[n];
  double sum=0;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    sum+=a[i];
  }
  double count=0;
  for(int i = 0; i < n; i++){
    if(a[i]>=sum/(m*4))count++;
  }
  if(count>=m)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define nil -1

typedef struct{
  int p;
  int left;
  int right;
  int sibling;
  int depth;
  int height;
  int degree;
  
}Node;
Node N[100000];

void CalcDepth(int,int);

int main(){

  int i,j,n,c,left,right,degree,tmp,root;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    N[i].p=N[i].left=N[i].right=N[i].sibling=nil;
    N[i].depth=N[i].height=N[i].degree=0;
  }
  
  for(i=0;i<n;i++){
    scanf("%d %d %d",&tmp,&left,&right);
    N[tmp].left=left;
    N[tmp].right=right;
    if(left!=-1&&right!=-1){
      N[right].p=tmp;
      N[right].sibling=left;
      N[left].sibling=right;
      N[left].p=tmp;
      N[tmp].degree=2;
    }
    else if(left!=-1&&right==-1){
      N[left].p=tmp;
      N[tmp].degree=1;
    }
    else if(left==-1&&right!=-1){
      N[right].p=tmp;
      N[tmp].degree=1;
    }
  }

  for(i=0;i<n;i++)if(N[i].p==nil)root=i;
  CalcDepth(n,root);
 
  for(i=0;i<n;i++){
   printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, "
	  ,i,N[i].p,N[i].sibling,N[i].degree,N[i].depth,N[i].height);
   if(N[i].p==nil)printf("root\n");
   else if(N[i].left==nil&&N[i].right==nil)printf("leaf\n");
   else printf("internal node\n");
 }
  return 0;
}


void CalcDepth(int n ,int p){

 int i,j,k,d,h;

  for(i=0;i<n;i++){
    if(i==p)N[i].depth=0;
    else if(N[i].depth==0) {
      for(j=N[i].p,d=1;j!=p;j=N[j].p){
	d++;
      }
      N[i].depth=N[N[i].sibling].depth=d;
      if(N[i].left==nil&&N[i].right==nil){
	h=0;
	j=i;
	while(1){
	  j=N[j].p;
	  h++;
	  if(N[j].height<=h)N[j].height=h;
	  if(j==p) break;
	}
      }
      }
    }
  }

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//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();}
VI l(8);
ll N;
VI target(3);

ll dfs(int n, VI len, int margeTime){

  if(n == N){
    rep(i,3){
      if(len[i] == 0) return 1e9;
    }

    ll ans = 0;
    rep(i,3) ans += abs(len[i] - target[i]);
    ans += (margeTime-3) * 10;
    return ans;

  }else{
    VI res(4);
    //そのまま
    res[3] = dfs(n+1,len,margeTime);
    // marge
    rep(i,3){
      len[i] += l[n];
      res[i] = dfs(n+1,len,margeTime+1);
      len[i] -= l[n];
    }
    int min_res = 1e9;
    rep(i,4) min_res = min(min_res,res[i]);

    return min_res;
  }
}
int main(){
  cin >> N;
  rep(i,3) cin >> target[i];
  rep(i,N) cin >> l[i];
  VI len(3,0);
  cout << dfs(0,len,0) << endl;

  return 0;
}


Measured memory_bytes: 256
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N, K = map(int, input().split())
A = list(map(int, input().split()))
# print('A', A)

def func(A):
    # print('start')
    # print(A)
    all_N = True
    aA = [0]*(2*N+10)
    for i, a in enu(A):
        if a != N:
            all_N = False
        st = max(0, 2*i-2*a-1)
        en = min(2*N, 2*i+2*a+1)
        aA[st] += 1
        aA[en] -= 1

    # print(aA)
    for i in range(2*N):
        aA[i+1] += aA[i]

    # print(aA)

    res = [val for i, val in enu(aA) if i%2==0]
    res = res[:N]
    # print(res)
    return res, all_N

for _ in range(K):
    A, all_N = func(A)
    if all_N:
        break
    # print(*A)

print(*A)

Measured memory_bytes: 180180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=b-1; (ll)(a)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


int main(){
    ll n, m;    cin >> n >> m;
    vector<ll> a(m, 0);
    vector<pair<ll, ll>> v(n);
    rep(i, n)  cin >> v[i].second >> v[i].first;
    sort(ALL(v), greater<pair<ll, ll>>());
    
    ll cnt=0;
    rep(i, n){
        ll d=m-(v[i].second-1);
        //cout << d << ' ' << v[i].first << endl;
        repd(k, d){
            if(a[k]<v[i].first){
                a[k] = max(a[k], v[i].first);
                break;
            }
        }
    }
    ll res=0;
    rep(i, m) res += a[i];
    cout << res << endl;
}


Measured memory_bytes: 5632
package main

import(
    "fmt"
    "sort"
    "strings"
)



func main() {
    var a,b,c,d int
    fmt.Scan(&a,&b,&c,&d)
    fmt.Println(max32(0,min32(b,d)-max32(a,c)))
}





// Pairsort
type Pair struct {
    first,second int64
}

type By func(p1, p2 *Pair) bool

func (by By) Sort(pairs []Pair) {
    ps := &pairSorter{
            pairs : pairs,
            by: by,
    }
    sort.Sort(ps)
}

type pairSorter struct {
    pairs []Pair
    by func(p1, p2 *Pair) bool
}

func (s *pairSorter) Len() int {
    return len(s.pairs)
}

func (s *pairSorter) Swap(i, j int) {
    s.pairs[i], s.pairs[j] = s.pairs[j], s.pairs[i]
}

func (s *pairSorter) Less(i, j int) bool {
    return s.by(&s.pairs[i], &s.pairs[j])
}

func first (p1, p2 *Pair) bool {
        return p1.first < p2.first
}

func second (p1, p2 *Pair) bool {
        return p1.second < p2.second
}
// end



func abs32(a int) int {
    if a<0{
        return -a
    }
    return a
}

func abs64(a int64) int64 {
    if a<0{
        return -a
    }
    return a
}

func min32(a, b int) int {
    if a >= b {
        return b
    }
    return a
}

func max32(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func min64(a, b int64) int64 {
    if a >= b {
        return b
    }
    return a
}

func max64(a, b int64) int64 {
    if a >= b {
        return a
    }
    return b
}

func gcd(a, b int64) int64 {
    if a % b == 0 {
        return b
    } else {
        return gcd(b, a%b)
    }
}

func lcm(a, b int64) int64 {
    return a / gcd(a, b) * b
}

func scanNums(len int) (nums []int){
    var num int
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanNums64(len int) (nums []int64){
    var num int64
    for i:=0; i<len; i++{
        fmt.Scan(&num)
        nums = append(nums,num)
    }
    return
}

func scanString(len int) (str []string){
    var s string
    for i:=0; i<len; i++{
        fmt.Scan(&s)
        str = append(str,s)
    }
    return
}

func makeTwoNums(n,m int) ([][]int){
    Nums := make([][]int, n)
    for i:=0; i<n; i++{
        Nums[i] = make([]int, m)
    }
    return Nums
}

func sortString(s string) string{
    t := strings.Split(s, "")
    sort.Strings(t)
    return strings.Join(t, "")
}

func reverseString(s string) string{
    t := []rune(s)
    for i,j := 0, len(s)-1 ; i < j ; i, j = i+1, j-1 {
        t[i], t[j] = t[j], t[i]
    }
    return string(t)
}

func inside(h,w,H,W int) bool{
    if h>=0 && h<H && w>=0 && w<W{
        return true
    }
    return false
}


Measured memory_bytes: 640
import java.util.*;
import java.util.List;
import java.util.ArrayList;

class Main{
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] arr = new int[m];
        for (int i=0; i<m; i++){
            arr[i] = scan.nextInt();
        }
        scan.close();
        if (n>=m){
            System.out.println(0);
            System.exit(0);
        }
        Arrays.sort(arr);
        List<Integer> score = new ArrayList<>();
        for (int i=0; i<m-1; i++){
            score.add(arr[i+1] - arr[i]);
        }
        Collections.sort(score);
        int ans = 0;
        for (int i=0; i<m-n; i++){
            ans += score.get(i);
        }
        System.out.println(ans);
    }
}

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


bool isEvenString(string S){
  if(S.size() % 2 == 1){
    return false;
  }

  string left,right;
  left   = S.substr(0,S.size()/2);
  right  = S.substr(S.size()/2,S.size()/2);

  if(left != right){
    return false;
  }
  return true;
}

int main(void){
  string S;cin >> S;

  while(S.size() != 0){
    S = S.substr(0,S.size()-1);
    bool rslt;

    if(true == isEvenString(S)){
      cout << S.size() << endl;
      return 0;
    }
  }
  cout << "0" << endl;
  return 0;
}



Measured memory_bytes: 256
import sys
import numpy as np

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

if len(s) == 1:
    print(s[0][0])
    exit()

X, N = s[0]
P = s[1]

x_upper = X
x_lower = X
while 1:
    if P.count(x_lower) == 0:
        print(x_lower)
        exit()
    elif P.count(x_upper) == 0:
        print(x_upper)
        exit()
    x_upper += 1
    x_lower -= 1


Measured memory_bytes: 27136
n=int(input())
x=[]
y=[]
for i in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
ans=0
for i in range(n):
  for j in range(n):
    ans+=((x[i]-x[j])**2+(y[i]-y[j])**2)**.5
print(ans/n)

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

int main() {
	long N, A, B; cin >> N >> A >> B;
	if(A>B) cout << 0 << endl;
	else if(N==1){
	    if(A==B) cout << 1 << endl;
	    else cout << 0 << endl;
	}
	else{
	    long S = ((N-1)*B+A) - ((N-1)*A+B) + 1;
	    cout << S << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define endl '\n'
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x, y) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << (y) << "\n"
#define watch3(x, y, z) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << (y) << " and " << (#z) << " is " << (z) << "\n"
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define rep(i, a, b) for (ll i = a; i < (b); ++i)
#define reb(i, a, b) for (ll i = a; i >= (b); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
int main()
{
fast;
	int t;
	//cin>>t;
	t=1;
	while(t--)
	{
		ll n,m,s,u,v;
		cin>>n>>m>>s;
		ll row[n]={},col[m]={};
		map<pii,ll> mp;
		ll ans=0,maxx=0,maxr,maxc,mar=0,mac=0;
		vi r,c;
		rep(i,0,s)
		{
			cin>>u>>v;
			u--;v--;
			row[u]+=1;
			col[v]+=1;
			mp[{u,v}]=1;
			if(mar<=row[u])
			{
				if(mar<row[u])
				{
					r.clear();
				}
				mar=row[u];
				r.pb(u);
				maxr=u;
			}
			if(mac<=col[v])
			{
				if(mac<col[v])
				{
					c.clear();
				}
				c.pb(v);
				mac=col[v];
				maxc=v;
			}
		}
		ll lol=0;
		rep(i,0,sz(r))
		{
			rep(j,0,sz(c))
			{
				if(mp[{r[i],c[j]}]==0)
				{
					lol=1;
					break;
				}
			}
			if(lol==1)
			break;
		}
		maxx=mac+mar+(lol==1?0:-1);
		cout<<maxx<<endl;
	}
	return 0;
}

Measured memory_bytes: 31380
ans=1
n=int(input())
s=input()
t=input()
m=False
if s[0]==t[0]:
    ans*=3
    flag=True
else:
    ans*=6
    flag=False
    m=True
for i in range(1,n):
    if m==True:
        m=False
        continue
    if flag==True and s[i]==t[i]:
        ans*=2
        continue
    if flag==True and s[i]!=t[i]:
        ans*=2
        m=True
        flag=False
        continue
    if flag==False and s[i]==t[i]:
        flag=True
        continue
    if flag==False and s[i]!=t[i]:
        ans*=3
        m=True
        continue
print(ans%(10**9+7))

Measured memory_bytes: 3064
n = int(input())
A = list(map(int, input().split()))

#偶数項を正とする場合
even_ans = 0
tot = 0

for i in range(n):
    tot += A[i]
    #偶数項では累積和を正とする
    if i % 2 == 1:
        if tot > 0:
            pass
        else:
            even_ans += abs(1 - tot)
            tot = 1
    #奇数項では累積和を負とする
    else:
        if tot < 0:
            pass
        else:
            even_ans += abs(-1-tot)
            tot = -1

#奇数項を正とする場合
odd_ans = 0
tot = 0

for i in range(n):
    tot += A[i]
    #偶数項では累積和を正とする
    if i % 2 == 1:
        if tot < 0:
            pass
        else:
            odd_ans += abs(-1 - tot)
            tot = -1
    #奇数項では累積和を負とする
    else:
        if tot > 0:
            pass
        else:
            odd_ans += abs(1-tot)
            tot = 1

ans = min(even_ans, odd_ans)
print(ans)

    


Measured memory_bytes: 14468
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
ll A[200001],zero[200001],even[200001],odd[200001];
ll dp[200001][5];
int main(){
	int L;
	scan(L);
	rep(i,L){
		scan(A[i]);
		zero[i]=A[i];
		even[i]=(A[i]==0 ? 2 : A[i]%2);
		odd[i]=(A[i]%2==0);
	}
	fill(dp[0],dp[200001],INFl);
	rep(j,5) dp[0][j]=0;
	rep(i,L){
		rep(j,5){
			rep(k,j+1){
				if(j==0||j==4) dp[i+1][j]=min(dp[i+1][j],dp[i][k]+zero[i]);
				else if(j==1||j==3) dp[i+1][j]=min(dp[i+1][j],dp[i][k]+even[i]);
				else dp[i+1][j]=min(dp[i+1][j],dp[i][k]+odd[i]);
			}
		}
	}
	ll ans=INFl;
	rep(j,5) ans=min(ans,dp[L][j]);
	prin(ans);
	return 0;
}


Measured memory_bytes: 14336
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
#define INF 1000000000
ll h,w;
ll e[50][50];
int main(){
	while(true) {
		cin >> h >> w;

		if(h == 0)
			break;

		REP(i,h) {
			REP(j,w) {
				cin >> e[i][j];
			}
		}

		ll ans = 0;
		REP(i,h) {
			FOR(j,i + 2,h) {
				REP(k,w) {
					FOR(l,k + 2,w) {
						ll miniw = INF;

						FOR(p,i,j + 1) {
							miniw = min(e[p][k],miniw);
							miniw = min(e[p][l],miniw);
						}

						FOR(p,k,l + 1) {
							miniw = min(e[i][p],miniw);
							miniw = min(e[j][p],miniw);
						}

						bool f = false;
						ll cou = 0;
						FOR(p,i + 1,j) {
							FOR(q,k + 1,l) {
								if(miniw <= e[p][q])
									f = true;
								cou += miniw - e[p][q];
							}
						}
						if(f) 
							continue;
						ans = max(cou,ans);

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



Measured memory_bytes: 3080
#import<bits/stdc++.h>
using namespace std;main(){int x1,y1,x2,y2,n,xf=1,yf=1,x,y;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);if(x1>x2)swap(x1,x2),xf=-1;if(y1>y2)swap(y1,y2),yf=-1;vector<pair<int,int>>v;for(;n--;)if(scanf("%d%d",&x,&y),x1<=x&&x<=x2&&y1<=y&&y<=y2)v.emplace_back(x*xf,y*yf);sort(v.begin(),v.end());vector<int>d(v.size(),1<<30);for(auto &e:v)n=e.second,*lower_bound(d.begin(),d.end(),n)=n;n=lower_bound(d.begin(),d.end(),1<<30)-d.begin();printf("%.9f\n",100.0*(x2-x1+y2-y1)-20*n+5*(n+(n>min(x2-x1,y2-y1)))*3.1415926536);}

Measured memory_bytes: 2544
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<char> >ar(n,vector<char>(m));
    vector<vector<long long int> >dp(n,vector<long long int>(m));

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>ar[i][j];
        }
    }
    bool flag=true;
    for(int i=0;i<n;i++)
    {
        dp[i][0]=1;
        if(ar[i][0]=='#')
            flag=false;
        if(flag==false)
            dp[i][0]=0;
    }
    flag=true;
    for(int i=0;i<m;i++)
    {
        dp[0][i]=1;
        if(ar[0][i]=='#')
            flag=false;
        if(flag==false)
            dp[0][i]=0;
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(ar[i][j]=='#')
                dp[i][j]=0;
            else
            {
                dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
            }
        }
    }
    cout<<dp[n-1][m-1];
    return 0;
}



Measured memory_bytes: 11996
a= list(input().split())
for i in range(len(a)):
    if a[i] !="+" and a[i] !="-"and a[i] !="*":
        a[i]=int(a[i])
i= 0
while len(a)>1:
    if a[i] =="+":
        temp= a[i-2]+ a[i-1]
        a.pop(i-2)
        a.pop(i-2)
        a[i-2]= temp
        i= i- 1
    elif a[i] =="-":
        temp= a[i-2]- a[i-1]
        a.pop(i-2)
        a.pop(i-2)
        a[i-2]= temp
        i= i- 1
    elif a[i] =="*":
        temp= a[i-2]* a[i-1]
        a.pop(i-2)
        a.pop(i-2)
        a[i-2]= temp
        i= i- 1
    else:
        i= i+ 1
print(a[0])



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

int main()
{
  int n, k, c;
  scanf("%d %d %d", &n, &k, &c);
  string s;
  cin >> s;

  vector<bool> l(n), r(n);
  int m = 0, lp = 0, rp = n;
  for (int i = 0; i < n; i++)
    if (i >= lp && s[i] == 'o') {
      l[i] = true;
      lp = i + c + 1;
      m++;
    }
  for (int i = n - 1; i >= 0; i--)
    if (i < rp && s[i] == 'o') {
      r[i] = true;
      rp = i - c;
    }

  if (m == k) {
    for (int i = 0; i < n; i++)
      if (l[i] && r[i])
        printf("%d\n", i + 1);
  }

  return 0;
}

Measured memory_bytes: 1796
n = gets.to_i

a = Array.new(n).map{ [] }

def calc(x,y,z)
  return x*x + y*y + z*z + x*y + y*z + z*x
end

1.upto(100) do |x|
  1.upto(100) do |y|
    1.upto(100) do |z|
      result = calc(x,y,z)
      if result <= n
        a[result-1] << [x,y,z]
      end
    end
  end
end

a.each do |aa|
  puts aa.size
end


Measured memory_bytes: 29028
#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N;
	cin >> N;
	int i, j, k;
	vector <int> V;
	for (i = 0; i < N; i++) {
		int v;
		cin >> v;
		V.push_back(v);
		cout << V.at(i);
		if (i != N - 1) {
			cout << " ";
		}
	}
	cout << endl;
	for (i = 1; i < N; i++) {
		int j = i;
		while (V.at(j-1) > V.at(j)&&j>0) {
			swap(V.at(j-1), V.at(j));
			j--;
			if (j < 1) {
				break;
			}
		}
		for (k = 0; k < N; k++) {
			cout << V.at(k);
			if (k != N - 1) {
				cout << " ";
			}
		}
		cout << endl;
	}
	
}


Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
int n,a[101101],ans;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
	{
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
	{
        if(a[i]==a[i-1])ans++;
    }
    if(ans&1)ans++;
    cout<<n-ans<<"\n";
    exit(0);
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;

namespace ALDS1_2_D
{
	class Program
	{
		static void Main(string[] args)
		{
			var n = int.Parse(Console.ReadLine());
			var a = new int[n];

			for (var i = 0; i < n; i++)
			{
				a[i] = int.Parse(Console.ReadLine());
			}

			var g = new List<int>();
			var cnt = 0;
			for(var i = n / 2; 1 < i; i = i / 3 - 1)
			{
				g.Add(i);
				cnt += InsertSort(a, n, i);
			}
			g.Add(1);
			cnt += InsertSort(a, n, 1);

			Console.WriteLine(g.Count);
			Console.WriteLine(string.Join(" ", g));
			Console.WriteLine(cnt);
			foreach(var v in a)
			{
				Console.WriteLine(v);
			}
		}

		static int InsertSort(int[] a, int n, int g)
		{
			var cnt = 0;
			for (var i = g; i < n; i++)
			{
				var v = a[i];
				var j = i - g;
				while(0 <= j && v < a[j])
				{
					a[j + g] = a[j];
					j -= g;
					cnt++;
				}
				a[j + g] = v;
			}
			return cnt;
		}
	}
}



Measured memory_bytes: 23516