akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

use std::collections::BinaryHeap;
use std::cmp::Ordering;

// Define custom type to implement a min-heap
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
struct Cost(usize);

impl Ord for Cost {
    fn cmp(&self, other: &Cost) -> Ordering {
        other.0.cmp(&self.0)
    }
}

impl PartialOrd for Cost {
    fn partial_cmp(&self, other: &Cost) -> Option<Ordering> {
        Some(other.0.cmp(&self.0))
    }
}

fn main() {
    input!{
      n: usize,
      abcs: [(usize, usize, usize); n-1],
      qq: usize,
      k: usize,
      xys: [(usize, usize); qq],
    }
    let k = k-1;
    let mut g = vec![vec![]; n];
    for &(a, b, c) in &abcs {
        g[a-1].push((b-1, c));
        g[b-1].push((a-1, c));
    }

    const INF: usize = 1 << 60;
    let mut ds = vec![INF; n];
    ds[k] = 0;

    let mut q = BinaryHeap::new();
    q.push((Cost(0),k));

    while q.len() > 0 {
        let (ttl_cost, v) = q.pop().unwrap();
        if ds[v] < ttl_cost.0 {
            continue;
        }

        for &(n, nc) in &g[v] {
            if ds[v] + nc < ds[n] {
                ds[n] = ds[v] + nc;
                q.push((Cost(ds[v] + nc), n));
            }
        }
    }

    for i in 0..qq {
        let x = xys[i].0 - 1;
        let y = xys[i].1 - 1;
        println!("{}", ds[x] + ds[y]);
    }
}


Measured memory_bytes: 27900
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


int T, n, m, to[10101], f[404];
vector<int> v[404];
vector<P> G[404];
vector<vector<int>> dist(404, vector<int>(404, INF));
vector<int> route[404][404];
int now_t = 0;
int now = 1, next_t = 0;
int have[404] = {0};

i64 para[2] = {180, 16};

void floyd(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= n; k++){
				if(dist[j][k] > dist[j][i] + dist[i][k]){
					//route[j][k] = route[j][i]+route[i][k];
					route[j][k] = route[j][i];
					route[j][k].insert(route[j][k].end(),route[i][k].begin(),route[i][k].end());
					dist[j][k] = dist[j][i] + dist[i][k];
				}
			}
		}
	}
}

void input(){
	int a,b,c;
	cin >> a;
	for(int i = 0; i < a; i++){
		cin >> b >> c;
		v[c].push_back(now_t);
		to[now_t] = c;
	}
	cin >> a;
	for(int i = 0; i < a; i++){
		cin >> b;
	}
	now_t++;
}

void result(){
	string s;
	int a,b;
	cin >> s;
	cin >> a;
	for(int i = 0; i < a; i++){
		cin >> b;
	}
}

P choice_next(int start, int t){
	i64 ma = -1, k = -1;
	for(int i = 2; i <= n; i++){
		if(!have[i]) continue;
		if(dist[start][i] >= T-t) continue;
		int cnt = 0;
		for(int j = 0; j < route[start][i].size(); j++){
			cnt += have[route[start][i][j]];
		}
		if(ma < cnt * para[0] / (dist[start][i])){
			ma = cnt * para[0] / (dist[start][i]);
			k = i;
		}
	}
	return P(ma, k);
}

int Move(int start, int next_t){
	P choice = choice_next(start, next_t);
	int ma = choice.first, k = choice.second;
	if(ma >= para[1]){
		int npos = route[start][k][0];
		have[npos] = 0;
		for(int i = 0; i < dist[now][npos]; i++){
			if(next_t >= T) break;
			next_t++;
			cout << npos << endl;
			result();
			if(next_t != T) input();
		}
		now = npos;
		next_t = Move(now, next_t);
		
		return next_t;
	}
	for(int i = route[1][now].size()-2; i >= -1; i = route[1][now].size()-2){
		int npos;
		if(i == -1) npos = 1;
		else npos = route[1][now][i];
		for(int j = 0; j < dist[now][npos]; j++){
			if(next_t >= T) break;
			next_t++;
			cout << npos << endl;
			result();
			if(next_t != T) input();
		}
		now = npos;
	}
	return next_t;
}

int main(int argc, char** argv){
	
	cin >> n >> m;
	for(int i = 0; i <= n; i++){
		dist[i][i] = 0;
	}
	for(int i = 0; i < m; i++){
		int a,b,c;
		cin >> a >> b >> c;
		G[a].push_back(P(b,c));
		G[b].push_back(P(a,c));
		dist[a][b] = c;
		dist[b][a] = c;
		route[a][b].push_back(b);
		route[b][a].push_back(a);
	}
	for(int i = 1; i <= n; i++){
		cin >> f[i];
	}
	cin >> T;
	
	floyd();
	
	input();
	
	
	for(int t = 0; t < T; t++){
		if(now == 1) have[to[t]]++;
		if(next_t > t) continue;
		next_t = Move(1, t);
		if(next_t == t){
			cout << -1 << endl;
			result();
			if(t != T-1) input();
		}
	}
	
	return 0;
}

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

using namespace std;

typedef long long llint;

const int MAXN = 200005;
const llint INF = 1000000000000000000LL;

llint n, mn, mx, sol = INF;
llint x[MAXN], y[MAXN];
vector < pair <llint, llint> > v;
multiset <int> ms;
multiset <int> :: iterator it;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> x[i] >> y[i];
        if (x[i] > y[i]) swap(x[i], y[i]);
        v.push_back(make_pair(x[i], y[i]));
    }
    sort(v.begin(), v.end());
    int ind;
    for (int i=0; i<n; i++) {
        x[i] = v[i].first, y[i] = v[i].second;
        if (y[i] > mx) {
            mx = y[i];
            ind = i;
        }
    }
    mn = x[0];
    if (mx == y[0]) {
        llint z = mx;
        for (int i=0; i<n; i++) {
            z = min(z, y[i]);
        }
        llint res = (x[n-1] - mn) * (mx - z);
        sol = min(sol, res);
    } else {
        llint z = mx;
        for (int i=0; i<n; i++) {
            if (i == ind) continue;
            z = min(z, y[i]);
        }
        llint res = (x[n-1] - mn) * (mx - z);
        sol = min(sol, res);
        //dfsdf
        llint a = y[0], b = x[ind], lim = 0, lo = INF;
        if (a > b) swap(a, b);
        for (int i=1; i<n; i++) {
            if (i == ind) continue;
            lim = max(lim, x[i]);
            lo = min(lo, x[i]);
        }
        lim = max(lim, b);
        lo = min(lo, a);
        res = (mx - mn) * (lim - lo);
        sol = min(res, sol);
        for (int i=1; i<n; i++) {
            if (i == ind) continue;
            ms.insert(x[i]);
        }
        for (int i=1; i<n; i++) {
            if (i == ind) continue;
            ms.erase(ms.find(x[i]));
            ms.insert(y[i]);
            lo = *ms.begin();
            it = ms.end(); it--;
            lim = *it;
            lo = min(lo, a);
            lim = max(lim, b);
            res = (mx - mn) * (lim - lo);
            sol = min(sol, res);
        }
    }
    cout << sol;
    return 0;
}


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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int N;
    cin>>N;
    ll ans=0;
    for(int i=1;i<=N;i++){
        ans+=max((N-1)/i,0); 
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = (int)1e7;  
using  p = pair<int,int>;
using  v = vector<ll>;
auto used = v(50,0);   
int n,m;

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

   ll ans4 = 0;
   ll ans2 = 0;
   ll ans = 0;
   for (int i = 0; i < n; i++)
   {
      if(a[i]%4==0) {
        ans4++;
      }else if(a[i]%4==2){
        ans2++;
      }else{
      	ans++;
      }
   }
   if(ans4>=ans+ans2%2-1){
		cout << "Yes"<<endl;
   }else{
   		cout << "No"<<endl;
   }
}
  

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
using pii = pair<int, int>;
int main() {
  ll a, b;
  cin >> a >> b;

  cout << a * b / __gcd(a, b) << endl;
}

Measured memory_bytes: 3616
use proconio::input;

fn main() {
    input! {
        n:usize,
        h:[usize;n],
    }
    let mut max_jump = 0;
    let mut jump = 0;

    for i in 0..n - 1 {
        if h[i] >= h[i + 1] {
            jump += 1;
        } else {
            max_jump = std::cmp::max(max_jump, jump);
            jump = 0;
        }
    }
    max_jump = std::cmp::max(max_jump, jump);

    println!("{}", max_jump);
}


Measured memory_bytes: 3604
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>

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

int N;
deque<int> A;

int main() {
  cin >> N;
  rep (i, N) {
    int a;
    cin >> a;
    if (i%2==0) {
      A.push_back(a);
    } else {
      A.push_front(a);
    }
  }
  rep(i, N) {
    if (N%2 == 0) {
      cout << A.at(i);
    } else {
      cout << A.at(N-1-i);
    }
    if (i != N-1) {
      cout << ' ';
    }
  }
  cout << endl;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    LL a,b,c,k;
    cin >> a >> b >> c >> k;
    LL ans=min(a,k);
    LL rem=max((LL)0, k-a-b);
    cout << ans-rem << '\n';
    return 0;
}

Measured memory_bytes: 3652
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
sum = 0
for i in range(0,N-1):
    sum += B[A[i]-1]
    if A[i] == A[i+1] - 1:
        sum += C[A[i]-1]
sum += B[A[N-1]-1]
print(sum)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

vector< int > z_algorithm(const string &s) {
  vector< int > prefix(s.size());
  for(int i = 1, j = 0; i < s.size(); i++) {
    if(i + prefix[i - j] < j + prefix[j]) {
      prefix[i] = prefix[i - j];
    } else {
      int k = max(0LL, j + prefix[j] - i);
      while(i + k < s.size() && s[k] == s[i + k]) ++k;
      prefix[i] = k;
      j = i;
    }
  }
  prefix[0] = (int) s.size();
  return prefix;
}

signed main(){

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

  int ans = 0;
  for(int i = 0; i < n; i++){
    auto v = z_algorithm(s.substr(i,n));
    for(int j = 1; j < v.size(); j++){
      int res = min(v[j], j);
      ans = max(ans, res);
    }
  }
  cout << ans << endl;

  return 0;
}


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


def check(op):  # 最初の数の正負を引数とする
    total = 0
    ans = 0
    for i in range(0, n):
        if (total+a[i]) > 0 and op == "+":
            ans += abs(-1 - (total + a[i]))
            total = -1
            op = "-"
        elif (total+a[i]) < 0 and op == "-":
            ans += abs(1 - (total + a[i]))
            total = 1
            op = "+"
        elif total+a[i] == 0:
            ans += 1
            if op == "+":
                total = -1
                op = "-"
            else:
                total = 1
                op = "+"
        else:
            total += a[i]
            if op == "+":
                op = "-"
            else:
                op = "+"
    return ans


print(min(check("+"), check("-")))


Measured memory_bytes: 14648
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int a[n];
    rep(i,n)cin>>a[i];
    vector<pair<int,int>> pairs(m);
    int b,c;
    rep(i,m){
        cin>>b>>c;
        pairs[i] = make_pair(c,b);
    }

    sort(a,a+n);
    sort(pairs.begin(),pairs.end(),greater<pair<int,int>>());

    int work=0;
    rep(i,m){
        rep(j,pairs[i].second){
            if(j+work >= n)break;
            if(a[j+work] <= pairs[i].first)a[j+work] = pairs[i].first;
        }
        work += pairs[i].second;
        if(work >= n)break;
    }

    long long sum=0;
    rep(i,n)sum += a[i];

    cout<<sum;
}

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

const ll INF = 1e15;
ll n, W, dp[100001], c[101], w[101], ans;

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

	for(int i = 0; i <= 100000; ++i)
		dp[i] = INF;

	for(int i = 0; i < n; ++i)
		cin >> w[i] >> c[i];

	dp[0] = 0;
	for(int pos = 0; pos < n; ++pos) {
		if(w[pos] > W) continue;
		for(int cst = 100000; cst >= 0; --cst)
			if(cst + c[pos] <= 100000)
				dp[cst + c[pos]] = min(dp[cst + c[pos]], dp[cst] + w[pos]);
	}

	for(int i = 100000; i >= 0; --i)
		if(dp[i] <= W) {
			cout << i << endl;
			return 0;
		}
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int A, B, C, D;
    string ans;
    cin >> A >> B >> C >> D;

    int t = (C - 1) / B + 1;
    int a = (A - 1) / D + 1;

    if (t > a)
    {
        ans = "No";
    }
    else
    {
        ans = "Yes";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3588
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
ll t[5];
signed main()
{
	ll n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='R')t[1]++;
		if(s[i]=='G')t[2]++;
		if(s[i]=='B')t[3]++;
	}
	ll ss=t[1]*t[2]*t[3];
	for(int i=0;i<n;i++)
	{
		for(int k=1;k<=n;k++)
		{
			if(i+2*k>=n)break;
			if(s[i]!=s[i+k]&&s[i+k]!=s[i+k*2]&&s[i]!=s[i+k*2])ss--;
		}
	}
	cout<<ss;
	return 0;
}




Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int inf=1e18;
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,m;
    cin >> n >> m;
    if(n%2){
    	int i=1;
    	while(m--){
    		cout << i << " " << n+1-i << '\n';
    		i++;
    	}
    }
    else{
    	int k=n/2,i=1,c=0;
    	while(c<k/2 and c<m){
    		cout << i << " " << k+1-i << "\n";
    		c++,i++;
    	}
    	i=1;
    	int x=n/2-1;
    	while(c<m){
    		cout << i+n/2 << " " << x+1-i+n/2 << "\n";
    		c++,i++; 
    	}
    }
}

Measured memory_bytes: 3556
#include <iostream>
#include <stack>
#include <deque>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define mp make_pair
#define fname ""
#define fi first
#define se second
#define sz(a) (int)a.size()
#define pb push_back
#define fo(i,k,n) for(int i=k; (int)i<n; ++i)
#define rep(i,n,k) for(int i=n; (int)i>=k; --i)
#define all(v) v.begin(), v.end()
#define it ::iterator
#define forit(it,v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)


const int inf = (int)1e9;
const ll INF = (ll)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int N = 100100;

int n, a[1111],cnt, ans;
bool u[10];
int cr[8] = {400, 800, 1200, 1600, 2000, 2400, 2800, 3200};

int main(){
    
//freopen(fname"in", "r", stdin);
//freopen(fname"out", "w", stdout);

	cin>>n;

	fo(i,0,n)
		cin>>a[i];

	fo(i,0,n){
		fo(j,0,8){
			if(a[i] < cr[j]){
				u[j] = 1;
				break;
			}
			else if(a[i] >= 3200){
				cnt++;
				break;
			}
			
		}

	}

	fo(i,0,8)
		ans+=u[i];
    if(ans == 0){
        ans++;
        cnt--;
    }
        
	cout<<ans<<" "<<cnt+ans;



    return 0;
}









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

int main(){
	int N;
	cin >> N;
	
	unsigned long long Lucas = 0;
	unsigned long long Lucasi2 = 2;
	unsigned long long Lucasi1 = 1;
	
	if(N == 1){
		cout << 1 << endl;
	}
	else if(N > 1){
		for(int i = 1; i < N; i++) {
			Lucas = Lucasi1 + Lucasi2;
			Lucasi2 = Lucasi1;
			Lucasi1 = Lucas;
		}
		cout << Lucas << endl;
	}
}

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

void bubbleSort(int *, int);

int main(){
  int A[100];
  int i, N;

  scanf("%d",&N);
  if(N < 1 || 100 < N) exit(1);

  for(i=0; i<N; i++){
    scanf("%d",&A[i]);
    if(A[i] < 0 || 100 < A[i]) exit(2);
  }

  bubbleSort(A, N);

  return 0;
}

void bubbleSort(int *A, int N){
  int i, j, tem, num=0, flag=1;

  while(flag == 1){
    flag=0;
    for(j=N-1; j>=1; j--){
      if(A[j] < A[j-1]){
	tem=A[j];
	A[j]=A[j-1];
	A[j-1]=tem;
	flag=1;
	num++;
      }
    }
  }
  for(i=0; i<N; i++){
    if(i) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n%d\n", num);
}



Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

string s;
int cnt[26];
int xcnt;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    int n =  s.size();
    if (n == 1) {
      cout << 0 << endl;
      return 0;
    }
    int l = 0;
    int r = n - 1;
    int ans = 0;
    bool ok = true;
    while (l < r) {
      if (s[l] == s[r]) {
        l++;
        r--;
      }
      else if (s[l] == 'x' || s[r] == 'x'){
        if (s[r] == 'x') {
          int cnt = 0;
          while (r >= l && s[l] != s[r]) {
            if (s[r] != 'x') {
              ok = false;
              break;
            }
            cnt++;
            r--;
          }
          if (!ok) {
            break;
          }
          ans += cnt;
        }
        else {
          int cnt = 0;
          while (l <= r  && s[l] != s[r]) {
            if (s[l] != 'x') {
              ok = false;
              break;
            }
            cnt++;
            l++;
          }
          if (!ok) {
            break;
          }
          ans += cnt;
        }
      }
      else {
        ok = false;
        break;
      }
    }
    if (ok) cout << ans << endl;
    else cout << -1 << endl;
}


Measured memory_bytes: 512
//#include <algorithm>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
//#include <math.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vector<T>>;

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

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

    string S; cin >> S;
    int N = S.size();

    REP(i, 0, N / 2)
    {
        if (S[i] != S[N - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    int N2 = (N - 1) / 2;
    REP(i, 0, N2 / 2)
    {
        if (S[i] != S[N2 - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    int N3 = N - ((N + 3) / 2) + 1;
    REP(i, 0, N3 / 2)
    {
        if (S[N - N3 + i] != S[N - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


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


int main()
{
	int h, w;
	char c = 48;
	cin >> h >> w;
	char masu[h][w];
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> masu[i][j];
	
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (masu[i][j] == '.')	
			{
				for (int y = -1; y < 2; y++)
					for (int x = -1; x < 2; x++)
						if (i+y >=0 && i+y < h && j+x >= 0 && j+x < w)
							if (masu[i+y][j+x] == '#')
								c++;
				masu[i][j] = c;
				c = 48;
			}
		}
	}
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
			cout << masu[i][j];
		cout << endl;
	}
}



Measured memory_bytes: 3636
import java.util.*;

public class Main {
	final int INF = 1 << 24;
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n == 0 && m == 0) break;
			int [][] land = new int[n][n];
			int [][] sea = new int[n][n];
			for(int i=0; i < n; i++){
				Arrays.fill(land[i], INF);
				Arrays.fill(sea[i], INF);
				land[i][i] = 0;
				sea[i][i] = 0;
			}
			for(int i=0; i < m; i++){
				int from = sc.nextInt() -1;
				int to = sc.nextInt() -1;
				int dis = sc.nextInt();
				String mark = sc.next();
				if(mark.equals("L")){
					land[from][to] = dis;
					land[to][from] = dis;
				}
				else{
					sea[from][to] = dis;
					sea[to][from] = dis;
				}
			}
			int r = sc.nextInt();
			int [] route = new int[r];
			for(int i=0; i < r; i++){
				route[i] = sc.nextInt() -1;
			}
			
			for(int j = 0; j < n; j++){
				for(int i = 0; i < n; i++){
					for(int k = 0; k < n; k++){
						land[i][k] = Math.min(land[i][k], land[i][j] + land[j][k]);
						sea[i][k] = Math.min(sea[i][k], sea[i][j] + sea[j][k]);
					}
				}
			}
			
			int [][]dp = new int[n][r];
			for(int i = 0; i < n; i++){
				Arrays.fill(dp[i], INF);
			}
			dp[route[0]][0] = 0;
			for(int i=0; i < r-1; i++){
				int from = route[i];
				int to = route[i+1];
				for(int untilL = 0; untilL  < n; untilL++){
					for(int untilS = 0; untilS < n; untilS++){
						int currentDis;
						if(untilL == untilS){
							currentDis = land[from][to];
						}
						else{
							currentDis = land[from][untilL] + sea[untilL][untilS] + land[untilS][to];
						}
						dp[untilS][i+1] = Math.min(dp[untilS][i+1], dp[untilL][i] + currentDis);
					}
				}
			}
			
//			for(int i = 0; i < n;i ++){
//				for(int j = 0; j < r; j++ ){
//					if(dp[i][j] == INF){
//						System.out.print("INF ");
//					}
//					else{
//						System.out.print(dp[i][j] + " ");
//					}
//					
//				}
//				System.out.println();
//			}
			
			int ans = INF;
			for(int i = 0; i < n; i++){
				ans = Math.min(ans, dp[i][r-1]);
			}
			System.out.println(ans);
			
		}
	}
	public static void main(String[] args) {
		Main obj = new Main();
		obj.doit();
	}
}

Measured memory_bytes: 16000
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 
        int idx = 1;
        String str;
 
        StringBuilder output = new StringBuilder();
        try {
 
            while(true){
                str = br.readLine();
                if (str.equals("0")) {
                    break;
                } else {
                    output.append("Case ").append(String.valueOf(idx))
                            .append(": ").append(str).append("\n");
                }
                if (idx % 100 == 0) {
                    System.out.print(output.toString());
                    output.setLength(0);
                }
                idx++;
            }
            if (output.length() > 0) {
                System.out.print(output.toString());
            }
 
        } catch (IOException e) {
            e.printStackTrace();
        }
		
	}

}

Measured memory_bytes: 28348
// https://atcoder.jp/contests/agc041/tasks/agc041_b
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m, v, p;
	scanf("%d%d%d%d", &n, &m, &v, &p);
	vector<int> a(n);
	for(int& x : a) {
		scanf("%d", &x);
	}
	sort(a.begin(), a.end());
	
	// m = 1
	// v = 5
	// p = 2
	// 0 1 1 2 2 3
	
	auto can = [&](int i) {
		int me = a[i] + m; // 2
		long long can_distribute = 0;
		for(int j = 0; j < n; j++) {
			if(j == i) {
				continue;
			}
			if(j > n - min(v, p)) { // j > 4
				can_distribute += m; // 1
			}
			else if(j > n - p) {
				continue;
			}
			else if(a[j] > me) {
				return false;
			}
			else {
				can_distribute += min(m, me - a[j]);
			}
		}
		return can_distribute >= (long long) m * (v - 1);
		/*
		// n-1, n-2, ..., n-min(v,p) can all make for sure
		if(i >= n - min(v, p)) {
			return true;
		}
		// a[i] will receive M votes
		// top min(p,v)-1 will receive M votes each
		int me = a[i] + m;
		long long can_distribute = 0;
		for(int j = 0; j < n - min(v, p); ++j) {
			if(j != i) {
				can_distribute += min(m, me - a[j]);
			}
		}
		return can_distribute >= m * v;*/
	};
	
	int low = 0, high = n - 1;
	int answer_index = -1;
	while(low <= high) {
		int i = (high + low) / 2;
		if(can(i)) {
			answer_index = i;
			high = i - 1;
		}
		else {
			low = i + 1;
		}
	}
	assert(answer_index != -1);
	printf("%d\n", n - answer_index);
}


// 2 1 1 3 0 2
  // ^


Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,s,f) for(int i=s;i<f;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define endl "\n"
#define fcout cout<<fixed<<setprecision(15)
typedef pair<int, int> P;
//struct edge { int to, cost; };

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

bool prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)return false;
    }
    return n != 1;
}
int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}
int lcm(int x, int y) {
return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int t = mod_pow(n, p / 2, m);
        return (t * t) % m;
    }
    return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int modinv(int a, int m) {
    int 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;
}
int modinv2(int a, int mod) {
    return mod_pow(a, mod - 2, mod);
}
int digit(int x) {
    int cnt = 0;
    while (x > 0) {
        cnt += x % 10;
        x /= 10;
    }
    return cnt;
}
int read() {
    int tmp;
    cin >> tmp;
    return tmp;
}
int xor128() {
    static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    int t = (x xor (x << 11));
    x = y; y = z; z = w;
    return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}
map<int, int> factaring(int x) {
    map<int, int>ans;
    int now = 2;
    while (now * now <= x) {
        if (x % now == 0) {
            x /= now;
            ans[now]++;
        }
        else now++;
    }
    if (x != 1) ans[x]++;
    return ans;
}
int comb(int n, int k, int mod) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    k = min(k, n - k);
    int x = 1, y = 1;
    rep(i, k) {
        y *= i + 1;
        y %= mod;
    }
    for (int i = n - k + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }
    return x * modinv(y, mod) % mod;
}


signed main() {
    //srand((unsigned)time(NULL));

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;
    int h[100005];

    cin >> n;
    rep(i, n) cin >> h[i];

    for (int i = 1; i < n; i++) {
        if (h[i - 1] > h[i]) {
            cout << "No" << endl;
            return 0;
        }
        if (h[i - 1] < h[i]) h[i]--;
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var x = ReadInt();
            int ans = 0;
            if (x >= 1800) ans = 1;
            else if (x >= 1600) ans = 2;
            else if (x >= 1400) ans = 3;
            else if (x >= 1200) ans = 4;
            else if (x >= 1000) ans = 5;
            else if (x >= 800) ans = 6;
            else if (x >= 600) ans = 7;
            else if (x >= 400) ans = 8;
            WriteLine(ans);
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 27536
a = [int(i) for i in input().split()]
dir = input()

class Dise:
    def __init__(self,a):
        self.dise = [0 for i in range(len(a))]
        for i in range(len(a)):
            self.dise[i] = a[i]

    def roll(self,dir):
        for self.pop_str in dir:
            if self.pop_str == "N":
                self.dise[0],self.dise[1],self.dise[4],self.dise[5] = self.dise[1],self.dise[5],self.dise[0],self.dise[4]
            elif self.pop_str == "S":
                self.dise[0],self.dise[1],self.dise[4],self.dise[5] = self.dise[4],self.dise[0],self.dise[5],self.dise[1]
            elif self.pop_str == "E":
                self.dise[0],self.dise[2],self.dise[3],self.dise[5] = self.dise[3],self.dise[0],self.dise[5],self.dise[2]
            elif self.pop_str == "W":
                self.dise[0],self.dise[2],self.dise[3],self.dise[5] = self.dise[2],self.dise[5],self.dise[0],self.dise[3]

    #確認用
    def output(self):
        print(self.dise[0])

dise = Dise(a)
dise.roll(dir)
dise.output()



Measured memory_bytes: 5620
if __name__ == "__main__":
    n, m, c = map(int, input().split())
    b = list(map(int, input().split()))
    a = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n):
        tmp = c
        for j in range(m):
            tmp += a[i][j] * b[j]
        if tmp > 0:
            ans += 1

    print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
#define rep(i,N) for(int i=0;i<(int)N;++i)
//cout << fixed << setprecision(20) << *** << endl;
typedef long long ll;
using namespace std;
int main()
{
	ll N,X=0,Y=0,T=0;
	string ANS="Yes";
	cin>>N;
	rep(i,N){
		ll t,x,y;
		cin>>t>>x>>y;
		if(abs(X-x)+abs(Y-y)<=t-T){
			//cout<<abs(X-x)+abs(Y-y)<<":"<<t-T<<endl;
			if((abs(X-x)+abs(Y-y))%2==0&&(t-T)%2==1){
				//cout<<"!"<<endl;
				ANS="No";
			}
			if((abs(X-x)+abs(Y-y))%2==1&&(t-T)%2==0){
				//cout<<"!!"<<endl;
				ANS="No";
			}
		}
		else{
			ANS="No";
		}
		X=x;
		Y=y;
		T=t;
	}
	cout<<ANS<<endl;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void){
  int N;
  int V[N];
  int C[N];
  int sum = 0;
  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    scanf("%d", &V[i]);
  }
  for(int i = 0; i < N; i++){
    scanf("%d", &C[i]);
  }
  for(int i = 0; i < N; i++){
    int value = V[i]-C[i];
    if(value > 0){
      sum += value;
    }
  }
  printf("%d", sum);
	return 0;
}


Measured memory_bytes: 128
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
		Long[] A = new Long[N];
		Long first = sc.nextLong();
		A[0] = first;
		A[1] = first;
		Long second = 0L;
		for(int i=1;i<N-1;i++){
			second = sc.nextLong();
			if(A[i] > second){A[i]=second;}
			A[i+1] = second;
		}
		A[N-1] = (N==2)?first:second;
		Long Ans =0L;
		for(int i=0;i<N;i++){
			Ans += A[i];
		}
		System.out.println(Ans);
		sc.close();
	}
}

Measured memory_bytes: 23124
import numpy as np
X = np.array([list(map(int, input().split())) for _ in range(3)])
T = True
if X[0][0]-X[0][1]==X[1][0]-X[1][1]==X[2][0]-X[2][1]\
   and X[0][1]-X[0][2]==X[1][1]-X[1][2]==X[2][1]-X[2][2]:
    pass
else:
  T = False

X = X.T
if X[0][0]-X[0][1]==X[1][0]-X[1][1]==X[2][0]-X[2][1]\
   and X[0][1]-X[0][2]==X[1][1]-X[1][2]==X[2][1]-X[2][2]:
    pass
else:
  T = False
print("Yes" if T else "No")

Measured memory_bytes: 27140
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

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

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

const double PI = acos(-1);

bool reach(int x, int y, int w, int a, int d)
{
    if(x*x + y*y > a*a) return false;
    double arg = atan2(y, x)*180/PI - w;
    if(arg < -180) arg += 360;
    return abs(arg)*2 < d;
}

void func(int H, int R)
{
    vector<pii> house(H);
    rep(i, H){
        cin >> house[i].first >> house[i].second;
    }
    
    int N[3], d[3];
    rep(i, 3) cin >> N[i];
    rep(i, 3) cin >> d[i];
    
    vector<pii> tree[3];
    
    rep(i, 3){
        tree[i].resize(N[i]);
        rep(j, N[i]){
            cin >> tree[i][j].first >> tree[i][j].second;
        }
    }
    
    vi cnt(H);
    
    rep(i, R){
        int w, a;
        cin >> w >> a;
        
        rep(j, H){
            bool ok = reach(house[j].first, house[j].second, w, a, d[0]);
            
            rep(k, 3) rep(l, N[k]){
                ok &= !reach(house[j].first - tree[k][l].first, house[j].second - tree[k][l].second, w, a, d[k]);
            }
            
            if(ok) cnt[j]++;
        }
    }
    
    int maxi = *max_element(cnt.begin(), cnt.end());
    if(maxi == 0){
        cout << "NA" << endl;
        return;
    }
    
    bool first = true;
    rep(i, H){
        if(cnt[i] == maxi){
            cout << (first ? "" : " ") << i+1;
            first = false;
        }
    }
    
    cout << endl;
}

int main()
{
    int H, R;
    while(cin >> H >> R, H){
        func(H, R);
    }
}

Measured memory_bytes: 1268
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <cstring>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define vi vector < int >
#define vll vector < long long >
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))
#define fname "searching"

const int inf = (int)1e9;
const ll INF = (ll)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int mod = (int)1e9 + 7;

string s;
ll ans;

void go(int p, ll sum){
    if(p >= s.size()) return;
    ll n = 0;
    for(int i = p; i < s.size(); ++i){
        n *= 10;
        n += s[i] - '0';
        go(i + 1, sum + n);
    }
    ans += sum + n;
}

ll solve(){
    cin >> s;

    go(0, 0);

    return ans;
}

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

    cout << solve() << "\n";
    
    return 0;
}


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

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	if (A + B > C + D) cout << "Left";
	else if (A + B == C + D) cout << "Balanced";
	else cout << "Right";
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

if文見れば分かるように、A+BとC+Dを比較すればおｋ
*/

Measured memory_bytes: 256
#include<stdio.h>
#define SIZE10 100000

typedef long long int ll;
typedef unsigned char u8;

int i = 0, j = 0;

int main(void){
    int N = 0;
    double odd = 0;

    scanf("%d", &N);

    if(N%2 == 0){
        printf("0.5");
    }else{
        printf("%f", (((double)N+1)/2)/(double)N);
    }
    return 0;
}

Measured memory_bytes: 128
N,M = map(int,input().split())

AC = [False] * (N+1)
WA_cnt = [0] * (N+1)

penal = 0
for _ in range(M):
    p,s = map(str,input().split())
    p = int(p)
    if AC[p]:
        continue
    if s == "WA":
        WA_cnt[p] += 1
    else:
        AC[p] = True
        penal += WA_cnt[p]

ac = sum(AC)
print(ac, penal)

Measured memory_bytes: 4596
// 問題の URL を書いておく
// https://atcoder.jp/contests/abc167/tasks/abc167_f

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <numeric>
using namespace std;

//#define ENABLE_PRINT

template<typename T>
T Input()
{
    T v;
    cin >> v;
    return v;
}

template<typename T>
vector<T> InputVector(int n)
{
    vector<T> v(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    return v;
}

template<typename T>
void InputArray(T* begin, int n)
{
    for(int i = 0; i < n; ++i)
    {
        cin >> begin[i];
    }
}

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

struct Pair
{
    int lower;
    int end;
};

int Test(vector<Pair>& ps)
{
    sort(ps.begin(), ps.end(), [](const auto& a, const auto& b) -> bool {
        return b.lower < a.lower;
    });
    int end = 0;
    for(auto p : ps)
    {
        if(end + p.lower < 0)
        {
            return -1;
        }
        end += p.end;
    }
    return end;
}

int main(int argc, const char* argv[])
{
    int n = Input<int>();
    auto ss = InputVector<string>(n);
    
    vector<Pair> left(n), right(n);
    left.resize(0);
    right.resize(0);

    int li = 0, ri = 0;
    for(auto& s : ss)
    {
        int lower = 0;
        int end = 0;
        for(auto& c : s)
        {
            if(c == '(')
            {
                end++;
            }
            else if(c == ')')
            {
                end--;
                lower = min(end, lower);
            }
            else
            {
                abort();
            }
        }
        if(end < 0)
        {
            right.push_back({lower, end});
        }
        else
        {
            left.push_back({lower, end});
        }
    }

    transform(right.begin(), right.end(), right.begin(), [](const auto& p) -> Pair{
        return {p.lower - p.end, 0 - p.end};
    });

    int l = Test(left);
    int r = Test(right);

    cout << (l == r && l >= 0 ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 50256
N=int(input())
A=list(map(int,input().split()))

mod=10**9+7

inv = pow(2,mod-2,mod)

tmp1=0
for i in range(N):
    tmp1+=A[i]
    tmp1%=mod

tmp2=0
for i in range(N):
    tmp2+=A[i]**2
    tmp2%=mod

res = tmp1**2-tmp2
res %= mod
res *= inv
res %= mod

print(res)


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

int main()
{
	int n, m, k, x, a[30]={0}, cnt=0;
	cin>>n>>m;
	for(int i =0;i<n;++i){
		cin>>k;
		while(k--){
			cin>>x;
			a[x-1]++;
		}
	}
	for(int i=0;i<m;i++){
		if(a[i]==n)cnt++;
	}
	cout << cnt << endl;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    int M;
    Scd2(N,M);

    int a;
    Rep(i,M) Scd(a), N-=a;
    if( N<0 ) N = -1;
    printf ("%d\n", N );

    return 0;
}



Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

int N, M;
vector< vector<int> > G;
vector<P> hen;
vector<int> H;
int itrNum[100001];
stack<int> S;

void dfs(int u){
    S.push(u);
    H[u] = 0;

    while(!S.empty()){
        u = S.top();  // 訪問中の頂点
        auto itr_v = next(G[u].begin(), itrNum[u]);
        if(itr_v != G[u].end()){
            itrNum[u]++;
            int v = *itr_v;
            if(H[v] == -1){
                H[v] = 0;
                S.push(v);
            }
        }else{
            S.pop();
            H[u] = 1;
        }
    }
}

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

    cin >> N >> M;
    G = vector<vector<int> >(N);
    H = vector<int>(N, -1);
    memset(itrNum, 0, sizeof(itrNum));
    REP(i, M){
        int a,b;
        cin >> a >> b;
        a--; b--;

        hen.pb(mp(a,b));
        G[a].pb(b);
        G[b].pb(a);
    }
    int ans = 0;
    REP(i,M){
        int x = hen[i].first, y = hen[i].second;
        auto itr = find(All(G[x]), y);
        G[x].erase(itr);
        itr = find(All(G[y]), x);
        G[y].erase(itr);

        dfs(x);
        if(H[y] == -1) ans++;
        G[x].pb(y);
        G[y].pb(x);
        H = vector<int>(N, -1);
        memset(itrNum, 0, sizeof(itrNum));
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 640
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

def solve(N):
    if N == 2:
        print(1)
        return
    Ans = [N, N-1]
    for base in range(2, N):
        if base * base > N:
            break
        n = N
        while n % base == 0:
            n //= base
        if n % base == 1:
            Ans.append(base)
        if (N-1) % base == 0:
            Ans.append(base)
            Ans.append((N-1)//base)
    if int(N**0.5)**2 == N:
        Ans.append(int(N**0.5))
    print(len(set(Ans)))

numba_compile([
    [solve, "void(i8)"],
])

N = int(input())
solve(N)


Measured memory_bytes: 27264
(set! *unchecked-math* true)

(def ^:const D-Y-X
  [[-1 -1] [-1 0] [-1 1] [0 -1] [0 1] [1 -1] [1 0] [1 1]])
(def ^:const one (unchecked-int \0))

(defn get_H_W []
  (->> (clojure.string/split (read-line) #"\s")
    (map #(Integer/parseInt %))))

(defn set_Array [[H W ^"[[C" Array]]
  (loop [h 0]
    (when (< h H)
      (do (->> (read-line)
            (char-array W)
            (aset ^"[[C" Array h))
          (recur (unchecked-inc-int h))))))


(defn Minesweeper [[H W ^"[[C" Array]]
  (let [X (range W)
        Y (range H)]
    (dorun
      (for [x X
            y Y
            :let [v (aget ^"[C" (aget ^"[[C" Array y) x)]
            :when (not= \# v)]
        (->> (for [d-y-x D-Y-X
                   :let [[dy dx] (map + (list y x) d-y-x)]
                   :when (and
                           (<= 0 dx)
                           (< dx W)
                           (<= 0 dy)
                           (< dy H)
                           (= \# (aget ^"[C"(aget ^"[[C"Array dy) dx)))]
               true)
          count
          (unchecked-add-int one)
          unchecked-char
          (aset ^"[C"(aget^"[[C" Array y) x))))))

(defn output [[H W ^"[[C" Array]]
  (loop [h 0]
    (when (< h H)
      (do (->> (aget ^"[[C" Array h)
            (apply str)
            println)
          (recur (unchecked-inc-int h))))))

(let [[H W] (get_H_W)]
  (doto [H W (make-array Character/TYPE H W)]
    (set_Array)
    (Minesweeper)
    (output)))


Measured memory_bytes: 71980