akhauriyash/Code-Regression huggingface dataset:
// D - Equal Cut

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

ll A[200000];
ll cum_A[200001];

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

	for (int i=0; i<N; i++) {
		cin >> A[i];
		cum_A[i+1] = cum_A[i] + A[i];
	}

	ll ans = INF;

	ll P, Q, R, S;
	ll max_sub;
	ll min_sub;
	for (int m=2; m<=N-1; m++) {
		int l = lower_bound(cum_A, cum_A+m, cum_A[m] / 2) - cum_A;
		int r = lower_bound(cum_A+m, cum_A+N, cum_A[m] + (cum_A[N] - cum_A[m]) / 2) - cum_A;

		P = cum_A[l];
		Q = cum_A[m] - cum_A[l];
		R = cum_A[r] - cum_A[m];
		S = cum_A[N] - cum_A[r];
		max_sub = max(P, max(Q, max(R, S)));
		min_sub = min(P, min(Q, min(R, S)));
		ans = min(ans, max_sub - min_sub);

		P = cum_A[l-1];
		Q = cum_A[m] - cum_A[l-1];
		R = cum_A[r] - cum_A[m];
		S = cum_A[N] - cum_A[r];
		max_sub = max(P, max(Q, max(R, S)));
		min_sub = min(P, min(Q, min(R, S)));
		ans = min(ans, max_sub - min_sub);

		P = cum_A[l];
		Q = cum_A[m] - cum_A[l];
		R = cum_A[r-1] - cum_A[m];
		S = cum_A[N] - cum_A[r-1];
		max_sub = max(P, max(Q, max(R, S)));
		min_sub = min(P, min(Q, min(R, S)));
		ans = min(ans, max_sub - min_sub);

		P = cum_A[l-1];
		Q = cum_A[m] - cum_A[l-1];
		R = cum_A[r-1] - cum_A[m];
		S = cum_A[N] - cum_A[r-1];
		max_sub = max(P, max(Q, max(R, S)));
		min_sub = min(P, min(Q, min(R, S)));
		ans = min(ans, max_sub - min_sub);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6740
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(true){
            String s;
            s = scan.nextLine();
            if(s.charAt(0) == '0')break;
            int ans = 0;
            for(int i = 0; i < s.length(); i++){
                ans += s.charAt(i) - '0';
            }
            System.out.println(ans);
        }
    }
}



Measured memory_bytes: 26428
n=gets.to_i
a=gets.split.map &:to_i
sea=[true]+a.map{|e|e<=0}+[true]
cur=0
1.upto(n){|i|cur+=1 if !sea[i]&&sea[i-1]}
r=cur
o=n.times.select{|i|a[i]>0}.map{|i|[a[i],i+1]}.sort
o.each_with_index{|(x,y),i|
    sea[y]=true
    if sea[y-1]&&sea[y+1]
        cur-=1
    elsif !sea[y-1]&&!sea[y+1]
        cur+=1
    end
    if i+1==o.size||x<o[i+1][0]
        r=[r,cur].max
    end
}
p r


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

void insertionsort(vector<int>v, int n) {
		for (int i = 0; i < n; ++i) {
			if (i)cout << " ";
			cout << v[i];
		}
		cout << endl;
	for (int i = 1; i < n; ++i) {//nが1なら条件式が偽になり、実行されない
		int m = v[i];
		for (int j = i-1; j>=0; --j) {
			if (v[j] > m) {
				v[j + 1] = v[j];
			}
			else if (v[j] <= m) {
				v[j + 1] = m;
				break;
			}
			if (j == 0)v[0] = m;
		}
		for (int i = 0; i < n; ++i) {
			if (i)cout << " ";
			cout << v[i];
		}
		cout << endl;
	}
}

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


Measured memory_bytes: 3132
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int,int> P;
int main(void){
  int n,t,i,a[100010],amax=0,dmax=0,ans=0;
  map<int,int> m;
  map<int,int>::iterator ite;
  cin >> n >> t;
  for (i=0;i<n;i++){
    cin >> a[i];
    m.insert(P(a[i],i));
  }
  for (i=n-1;i>=0;i--){
    if (amax-a[i]>dmax) dmax=amax-a[i];
    if (amax<a[i]) amax=a[i];
  }
  for (i=0;i<n;i++){
    ite=m.find(a[i]+dmax);
    if (ite!=m.end() && ite->second > i) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5376
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>
 
#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;
 


int main(){
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n)cin >> a[i];
  sort(ALL(a));
  ll sum = 0;
  rep(i, k)sum += a[i];
  cout << sum << endl;
}
 

Measured memory_bytes: 3164
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

const ll MOD = 1e9 + 7;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}

const int MX = 410000;

ll fc[MX];
ll bfc[MX];
ll bpw[MX];
ll b2;

void init() {
	fc[0] = 1;
	for (int i = 1; i < MX; ++i)
		fc[i] = (fc[i - 1] * i) % MOD;
	bpw[0] = 1;
	b2 = pw(2, MOD - 2);
	for (int i = 1; i < MX; ++i)
		bpw[i] = (bpw[i - 1] * b2) % MOD;
	bfc[MX - 1] = pw(fc[MX - 1], MOD - 2);
	for (int i = MX - 2; i >= 0; --i)
		bfc[i] = (bfc[i + 1] * (i + 1)) % MOD;
}

ll cnk(int n, int k) {
	if (k > n)
		return 0;
	return fc[n] * bfc[k] % MOD * bfc[n - k] % MOD;
}


int b, w;


int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	init();
	cin >> b >> w;
	ll pw = 0, pb = 0;
	for (int i = 0; i < b + w; ++i) {
		if (i > 0) {
			pw = (pw + cnk(i - 1, b - 1) * bpw[i]) % MOD;
			pb = (pb + cnk(i - 1, w - 1) * bpw[i]) % MOD;
		}
		ll oth = 1 - pw - pb + 2 * MOD;
		oth %= MOD;
		cout << (pb + oth * b2) % MOD << "\n";
	}
	return 0;
}




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


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


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    N, M = readnums()
    ab = [tuple(readnums()) for _ in range(M)]
    
    al = {x[1] for x in ab if x[0] == 1}
    bl = {x[0] for x in ab if x[1] == N}
    print('POSSIBLE' if al & bl else 'IMPOSSIBLE')


if __name__ == "__main__":
    main()


Measured memory_bytes: 37724
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
#define vl vector<ll>
#define vi vector<int>
 
#define ff first
#define ss second
 
#define pb push_back
#define MOD 1000000007
//const int nax = 1e6+5;
#define inf 4e18
 
#define display(v) for(int i =0;i<v.size();++i)cout << v[i] << " "
#define all(v) v.begin(),v.end()
ll sqr(ll x){return x*x;}
inline ll add(ll a, ll b){ ll c = a + b; if(c >= MOD) c -= MOD; return c; }
inline ll mul(ll a, ll b){ return (a * 1ll * b) % MOD; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += MOD; return c; }
const int nax = 1000*1000 + 10;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    ll n; cin>>n;
    ll ans = 0;
    for(int i = 1;i<=n;++i){
        ans += (i*(n-i+1));
    }
    // singles , doubles .
    for(int i= 0;i<n-1;++i){
        ll a,b; cin>>a>>b;
        ll mn = min(a,b);
        ll mx = max(a,b);
        ans -= (mn*(n - mx + 1));
    }
    cout << ans;
  


    return 0;
}
    

// Химаншу


Measured memory_bytes: 3652
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let p: usize = iter.next().unwrap().parse().unwrap();
    let q: usize = iter.next().unwrap().parse().unwrap();
    let r: usize = iter.next().unwrap().parse().unwrap();

    println!("{}", std::cmp::min(p+q, std::cmp::min(q+r, r+p)));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0;i < n;i++)
#define rev(i, n) for(int i = n;i >= 0;i--)
#define repeat(i, m, n) for(int i = m;i < n;i++)
#define repeatrev(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define itn int

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
typedef priority_queue<int> Pr;

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

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

    string str;
    cin >> str;


    int S[1000000];
    char a;
    int zero = 0, one = 0;
    for ( char ch : str ) {
        int number = isdigit(ch) ? atoi(string(1,ch).c_str()) : -1;
        //cout << ch << " : " << number << endl;


        //cin >> a;
       // cout << a << endl;
        if(number == 0){
            zero ++;

        }else one ++;
   }
    cout << 2 * min(one, zero) << endl;

}

Measured memory_bytes: 512
from itertools import permutations

N, M = map(int, input().split())
edges = set()
for _ in range(M):
    a, b = map(int, input().split())
    edges.add((a, b))
    edges.add((b, a))

cnt = 0
for p in permutations(range(2, N + 1)):
    cnt += all(move in edges for move in zip((1,) + p, p))
print(cnt)

Measured memory_bytes: 3064
fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    val AArr = readInputLine().split(" ").map { it.toLong() }.toLongArray()
    
    var ans = 0L
    var tmp = AArr[0]

    var l = 0
    var r = 0
    
    while (l < N) {
        while (r < N - 1) {
            if (tmp + AArr[r + 1] != tmp xor AArr[r + 1]) {
                break
            }
            r++
            tmp += AArr[r]
        }
        ans += (r - l + 1).toLong()
        tmp -= AArr[l]
        l++
    }
    
    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

  int h, n;
  cin >> h >> n;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
  }
  cout << ((sum >= h) ? "Yes" : "No") << endl;
}


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

int main()
{
  int n, ans=0;
  cin >> n;
  vector<int> v(n);
  for(int i=0; i<n; i++){
    cin >> v[i];
  }
  for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) ans += v[i]*v[j];
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();
		long Y = sc.nextLong();
		sc.close();
		if(X%Y == 0) {
			System.out.println(-1);
		}else {
			System.out.println(X);
		}
	}
}

Measured memory_bytes: 23764
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<climits>
using namespace std;
typedef vector<string>vs;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<double>vd;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll>pll;
typedef vector<ll>vl;
typedef pair<int,pii>piii;
#define rrep(i,x,n) for(int i=(x);i<(n);++i)
#define rep(i,x) rrep(i,0,(x))
#define fi first
#define se second
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define maxs(a,b) (a)=max(a,b)
#define mins(a,b) (a)=min(a,b)
///#include<sstream>
///#include<cstring>
///#include<stack>
///#include<complex>

typedef pair<int,char>pic;

pic hand[9];

bool check(pic a,pic b,pic c){
    if(a.se!=b.se||b.se!=c.se||c.se!=a.se)return false;
    vector<pic>V;
    V.pb(a);V.pb(b);V.pb(c);
    sort(all(V));
    if(a.fi==b.fi&&b.fi==c.fi)return true;
    if(V[0].fi+1==V[1].fi&&V[1].fi+1==V[2].fi)return true;

    return false;
}

bool solve(){
    sort(hand,hand+9);
    do{
        bool flag=true;
        rep(i,3){
            if(!check(hand[i*3],hand[i*3+1],hand[i*3+2])){
                flag=false;
                break;
            }
        }
        if(flag)return true;

    }while(next_permutation(hand,hand+9));
    return false;
}

int main(){
    int N;
    scanf("%d",&N);
    while(N--){
        rep(i,9)scanf("%d",&hand[i].fi);
        rep(i,9)scanf(" %c",&hand[i].se);
        puts((solve()?"1":"0"));
    }
    return 0;
}

Measured memory_bytes: 1172
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>

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

using namespace std;
int main() {

	int n, d, x;
	cin >> n >> d >> x;
	vector<int>a(n);
	rep(i, n) cin >> a[i];

	int ans = x;

	rep(i, n)
		if (d%a[i] == 0)
			ans += d / a[i];
		else
			ans += d / a[i] + 1;

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

double CalcCapacity(int a, int b, double rad)
{
	if (rad >= M_PI * 0.5)
		return 0.0;

	if (rad == 0.0)
		return a * a * b;

	double ha = sin(rad) * a;
	double hb = sin(M_PI*0.5 - rad) * b;

	if (ha < hb)
	{
		double lo = a * a * tan(rad) * a * 0.5;
		double up = (hb - ha) * (a / cos(rad)) * a;
		return lo + up;
	}
	else
	{
		double t = hb / sin(rad);
		return t * a * b * 0.5;
	}
}

bool IsOverflow(int a, int b, int x, double rad)
{
	return CalcCapacity(a, b, rad) < x;
}

int main()
{
	int a, b, x;
	cin >> a >> b >> x;

	double low = 0;
	double up = M_PI * 0.5;
	double ans = low;

	for (int loop = 0; loop < 1024; ++loop)
	{
		double rad = (low + up) * 0.5;

		if (IsOverflow(a, b, x, rad))
		{
			up = rad;
		}
		else
		{
			ans = std::min(rad,ans);
			low = rad;
		}
	}

	cout << setprecision(10) << (low * 180 / M_PI) << endl;

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define reps(i,x) for(ll i=1;i<=(ll)(x);i++)
#define rrep(i,x) for(ll i=((ll)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(ll)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  if((a*b)%2) cout << "Yes" << endl;
  else cout << "No " << endl; 
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int N,M;
using pp = pair<int,int>;

int main(void) {
    cin>>N>>M;
    vector<pp> P;
    if(N%2 == 1) {
        for(int l = 1,r = N-1;l < r;l++,r--) {
            P.push_back({l,r});
        }
    } else {
        bool flag = false;
        for(int l = 1,r = N-1;l < r;l++,r--) {
            if(!flag && r-l <= N/2) {
                r--;
                flag = true;
            }
            P.push_back({l,r});
        }

    }

    for(int i = 0;i < M;i++) {
        cout<<P[i].first<<" "<<P[i].second<<endl;
    }

    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){
  
  int n,A;
  cin >> n >> A;
  vector<int> v(n);
  rep(i,n)cin >> v[i];
  vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>> (3000,vector<ll>(60,0)));
  dp[0][0][0] = 1;
  rep(i,n)rep(j,3000)rep(k,60){
    int ni = i+1,nj = j+v[i],nk = k+1;
    dp[ni][j][k] += dp[i][j][k];
    if(nj >= 3000)continue;
    dp[ni][nj][nk] += dp[i][j][k];
  }
  ll res = 0;
  rep(i,3000)rep(j,60){
    if(i == A*j)res+= dp[n][i][j];
  }
  res--;
  cout << res << endl;
  


  return 0;
}

Measured memory_bytes: 82464
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long a[100005],mn,mx;
int main()
{
	scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	if(a[n]!=2) {printf("-1");return 0;}mn=2;mx=3;
	for(int i=n-1;i;--i) {
		mn=((mn-1)/a[i]+1)*a[i];
		mx=(mx/a[i])*a[i]+a[i]-1;
		if(mn>mx) {printf("-1");return 0;}
	}
	printf("%lld %lld",mn,mx);
	return 0;
}
/*
mx=2 a[i]=3 at most 0
mn=17 a[i]=9 at most 1
mn=18 a[i]=9 at most 2
mx=
*/

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;
using Tiles = vector<string>;

struct Point {
	int x;
	int y;

	Point() :
		x{0}, y{0}
	{}

	Point(int _x, int _y) :
		x{_x}, y{_y}
	{}

	const Point operator+ (const Point& rhs) const
	{
		Point temp{x + rhs.x, y + rhs.y};
		return temp;
	}
};

const Point Arround[4] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int dfs(const Tiles& tiles, const Point& start, int W, int H)
{
	int count{0};
	queue<Point> Q;

	// ????????¨????????????????????????????????????
	vector<vector<bool>> done(H, vector<bool>(W, false));

	Q.push(start);
	done[start.y][start.x] = true;

	while(true) {
		if(Q.empty()) break;

		const auto& pos = Q.front();
		Q.pop();

		if(tiles[pos.y][pos.x] == '#') continue;

		++count;

		for(const auto& a : Arround) {
			const auto& p = pos + a;

			if(p.x < 0 || W <= p.x) continue;
			if(p.y < 0 || H <= p.y) continue;
			if(done[p.y][p.x]) continue;

			done[p.y][p.x] = true;
			Q.push(p);
		}
	}

	return count;
}

int main()
{
	int W, H;

	while(true) {
		cin >> W >> H;
		if(W == 0 && H == 0) break;

		Tiles tiles(H);
		Point start;

		for(int i = 0; i < H; ++i) {
			cin >> tiles[i];

			for(int j = 0; j < tiles[i].size(); ++j) {
				if(tiles[i][j] == '@') {
					start = Point{j, i};
					break;
				}
			}
		}

		cout << dfs(tiles, start, W, H) << endl;
	}

	return 0;
}

Measured memory_bytes: 3024
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vP p(N);
    rep(i,N){
        cin >> p[i].first;
        p[i].second=i;
    }
    sort(p.begin(),p.end());
    vl a(N);
    rep(i,N){
        a[i]=20000*(i+1);
        a[i]+=p[i].second;
    }
    vl b(N);
    rep(i,N){
        b[i]=20000*(N-i);
    }
    rep(i,N){
        cout << a[i] << (i==N-1? '\n':' ');
    }
    rep(i,N){
        cout << b[i] << (i==N-1? '\n':' ');
    }
}

Measured memory_bytes: 3956
# coding: utf-8
# Your code here!
w,h,x,y,r=map(int, input().split())
if r<=x:
    if x<=w-r:
        if r<=y:
            if y<=h-r:
                print("Yes")
            else:
                print("No")
        else:
            print("No")
    else:
        print("No")
else:
    print("No")
        



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

int main(){
	ios::sync_with_stdio(false);

	string s; cin>>s;
	int ans=0;
	int c=0;
	for(int i=0; i<s.size(); i++){
		if(s[i]=='R'){
			c++;
		}else{
			c=0;
		}
		ans = max(ans,c);
	}
	cout << ans << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<long long int,long long int>
#define vi vector<long long int >
#define vvi vector<vector< long long int>>
#define MP make_pair
#define PB push_back 
#define pb pop_back
#define PF push_front
#define pf pop_front
#define MOD 1000000007
#define MT make_tuple

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans=a*c;
	
	ans=max(ans,a*d);
	ans=max(ans,a*c);
	ans=max(ans,b*d);
	ans=max(ans,b*c);
	cout<<ans<<endl;

    return 0;
}
			

Measured memory_bytes: 3644
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <string>
#include <locale>

static bool input(int &sec)
{
	std::string s;
	std::locale loc;

	if (0x00 == &sec) {
		return false;
	}

	std::cin >> s;
	if (std::isdigit(s[0], loc)) {
		sec = std::atoi(s.c_str());
		if (sec < 86400) {
			return true;
		}
	}

	return false;
}

static bool calcWatch(int sec, int &h, int &m, int &s)
{
	if (0x00 == &h || 0x00 == &m || 0x00 == &s) {
		return false;
	}

	h = m = s = 0;

	if (3600 <= sec) {
		h = sec / 3600;
		sec -= h * 3600;
	}

	if (60 <= sec) {
		m = sec / 60;
		sec -= m * 60;
	}

	s = sec;

	return true;
}

int main()
{
	int sec;
	int h, m, s;

	if (true == input(sec)) {
		calcWatch(sec, h, m, s);
		std::cout << h << ":" << m << ":" << s << std::endl;
	}

	return (0);
}

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

typedef long long int ll;
#define T int t,q; scanf("%d",&t); for(q=1;q<=t;q++)
ll mark[1000006];
int main(){
	ll n,i;
	cin >> n;
	ll ar[n+5];
	
	for(i=0;i<n;i++){
		cin >> ar[i];
	}
	sort(ar,ar+n);
	
	for(i=0;i<=ar[n-1];i++){
		mark[i]=0;
	}
	ll c=0;
	for(i=0;i<n;i++){
		if(i<n-1 and ar[i]==ar[i+1] and i<n-1){
			mark[ar[i]]=1;
			for(ll j=ar[i]*2;j<=ar[n-1]  ;j+=ar[i]){
			  mark[j]=1;
			   }
		}
		else{
			if(mark[ar[i]]==0){c++;
			for(ll j=ar[i]*2;j<=ar[n-1]  ;j+=ar[i]){
			  mark[j]=1;
			   }
		}}
	}
	cout << c << endl;
	
	return 0;
}

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

const int N = 1e5;

int n,x,y;

vector<int> adj[N+5];

int dep[N+5];
int atas[N+5];
int most_dep[N+5];

void dfs(int now, int par){
	atas[now] = par;
	most_dep[now] = dep[now];
	for(int i=0;i<adj[now].size();i++){
		int cur = adj[now][i];
		if(cur == par) continue;
		dep[cur] = dep[now] + 1;
		dfs(cur,now);
		most_dep[now] = max(most_dep[now],most_dep[cur]);
	}
}

int main(){
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dep[y] = 0;
	dfs(y,-1);
	int skrg = x;
	int ans = 0;
	for(int i=0;i<dep[x];i++){
		if(dep[skrg]*2 <= dep[x]) break;
		int nambah = most_dep[skrg] - dep[skrg];
		int tmp = dep[x] - dep[skrg];
		int pos = dep[skrg];
		tmp += nambah;
		pos += nambah;
		int dif = pos - tmp;
		tmp+=dif-1;
		ans = max(ans,tmp);
		skrg = atas[skrg];
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 13312
import java.util.*;
public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
        String s = sc.next();
		String ans = "";
		for (int i = 0; i < s.length(); i++) {
			char key = s.charAt(i);
			if (key=='B') {
				int rightmost = ans.length() - 1;
				if (rightmost<=0) {
					ans = "";
				} else {
					ans = ans.substring(0, rightmost);
				}
			} else{
				ans += key;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 22740
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
string s,t,u;
int a,b; 
int main(){
	ios::sync_with_stdio(0);
	cin>>s>>t>>a>>b>>u;
	if(s==u){
		a--;
	}else
	b--;
	cout<<a<<" "<<b;
	re 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
c = 0
l = [ [0]*w for _ in range(h) ]
for i in range(n):
  for j in range(a[i]):
    l[c//w][c%w] = i+1
    c += 1

for i in range(h):
  if i%2 == 0:
    for j in range(w):
      print(l[i][j], end=" ")
  else:
    for j in range(w-1, -1, -1):
      print(l[i][j], end=" ")
  print("")

Measured memory_bytes: 3908
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(2e5+5); // TODO : change value as per problem
const ll MOD = 1e9+7;

pair<int,int> a[N];
void solve(){
    int n;
    cin >> n;
    for(int i =1;i<=n;i++){
        cin >> a[i].f >> a[i].s;
    }
    sort(a+1,a+n+1);
    int x=-INF,y=INF,z=-INF,z2 = INF;
    for(int i =1;i<=n;i++){
        x = max(x,a[i].f +a[i].s);
        y = min(y,a[i].f + a[i].s);
        z= max(z,a[i].f -a[i].s);
        z2 = min(z2,a[i].f - a[i].s);
    }
    cout << max(x-y,z-z2) << endl;

       
}
signed main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}

Measured memory_bytes: 6772
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<60)
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define dbgp(x) cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define maxn 200000

using namespace std;

struct yes { int l, r; ll scor; };

yes v[maxn+5], u[maxn+5];
ll d[maxn+5];///d[i]=scor maxim daca i este ultima pozitie cu 1 de la st la dr

void umax (ll &a, ll b) { a = max(a,b); }

struct sgtreel {
  sgtreel () {}
  ll yy[4*(maxn+1)+5], lazy[4*(maxn+1)+5];
  void updatel (int p, pii itv, pii ok, ll val) {
    if (lazy[p] != 0) {
      yy[p] += lazy[p];
      if (itv.fi < itv.se) {
        lazy[p*2] += lazy[p];
        lazy[p*2+1] += lazy[p];
      }
      lazy[p] = 0;
    }
    if (itv.fi > ok.se || ok.fi > itv.se) return;
    if (itv.fi >= ok.fi && itv.se <= ok.se) {
      yy[p] += val;
      if (itv.fi < itv.se) {
        lazy[p*2] += val;
        lazy[p*2+1] += val;
      }
      return;
    }
    int mid = (itv.fi + itv.se) / 2;
    updatel(p*2, {itv.fi, mid}, ok, val);
    updatel(p*2+1, {mid+1, itv.se}, ok, val);
    yy[p] = max(yy[p*2], yy[p*2+1]);
  }
  void preupdatel (pii ok, ll val) {///trb inclus si 0
    updatel(1, {1,maxn+1}, {ok.fi+1, ok.se+1}, val);
  }
  ll q_query;
  void queryl (int p, pii itv, pii ok) {
    if (lazy[p] != 0) {
      yy[p] += lazy[p];
      if (itv.fi < itv.se) {
        lazy[p*2] += lazy[p];
        lazy[p*2+1] += lazy[p];
      }
      lazy[p] = 0;
    }
    if (itv.fi > ok.se || ok.fi > itv.se) return;
    if (itv.fi >= ok.fi && itv.se <= ok.se) {
      umax(q_query, yy[p]);
      return;
    }
    int mid = (itv.fi + itv.se) / 2;
    queryl (p*2, {itv.fi, mid}, ok);
    queryl (p*2+1, {mid+1, itv.se}, ok);
  }
  ll prequeryl (pii ok) {
    if (ok.fi > ok.se) return 0;
    q_query = -infl;
    queryl (1, {1, maxn+1}, {ok.fi+1, ok.se+1});
    return q_query;
  }
};

sgtreel aint;

int main () {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n, m; cin >> n >> m;
  int i, j, z;
  for (i = 1; i <= m; i++) cin >> v[i].l >> v[i].r >> v[i].scor;
  for (i = 1; i <= m; i++) u[i] = v[i];
  sort (v+1, v+m+1, [](yes a, yes b){ return a.l < b.l; });
  sort (u+1, u+m+1, [](yes a, yes b){ return a.r < b.r; });
  int st = 1, dr = 1;
  fill(all(d), -infl); d[0] = 0;
  for (z = 1; z <= n; z++) {
    while (dr <= m && v[dr].l == z) {
      aint.preupdatel({0,v[dr].l-1}, v[dr].scor);
      dr++;
    }
    d[z] = aint.prequeryl({0, z-1});
    aint.preupdatel({z,z}, d[z]);
    while (st <= m && u[st].r == z) {
      aint.preupdatel({0,u[st].l-1}, -u[st].scor);
      st++;
    }
  }
  cout << (*max_element(all(d)));
  return 0;
}


Measured memory_bytes: 20608
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <iomanip>
using namespace std;
#define Would
#define you
const int INF = 999999999;
const int MOD = 1e9 + 7;
const double pi = 3.141592653589793238;

int main() {
	while (1) {
		int a, b;
		cin >> a >> b;
		if (a == 0 && b == 0) { break; }
		for (int i = 0; i < a; ++i) {
			for (int j = 0; j < b; ++j) {
				if ((i + j) % 2 == 0) { cout << "#"; }
				else { cout << "."; }
			}
			cout << endl;
		}
		cout << endl;
	}
}


Measured memory_bytes: 3096
#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
map<string,int> ma;
set<pair<string,int> > se;
vector<string> ve;
int main()
{
	int n;
	cin >> n;
	int ans=0;
	for(int i = 1; i <= n; ++i){
		string s;cin >> s;
		ma[s]++;
		pair<string,int> pa=make_pair(s,ma[s]);
		se.insert(make_pair(s,ma[s]));
		if(ma[s]>ans)ans=ma[s];
	}
	for(auto it:se){
		if(it.second==ans){
			ve.push_back(it.first);
		}
	}
	sort(ve.begin(),ve.end());
	for(int i = 0; i < ve.size();++i){
		cout << ve[i] <<endl;
	}
	return 0;
}

Measured memory_bytes: 39920
from collections import deque
import sys

N, M = map(int, input().split())

G = [deque([]) for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

time = 0

for i in range(len(G[0])):
    if (N-1) in G[G[0][i]]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

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

int mp[11][11][11],p,n,m;
int dx[13]={ 0, 1, 0, 1, 1, 0, 1,-1, 0, 1, 1, 1,-1};
int dy[13]={ 0, 0, 1, 1, 0, 1,-1, 0, 1, 1, 1,-1, 1};
int dz[13]={ 1, 0, 0, 0, 1, 1, 0, 1,-1, 1,-1, 1, 1};


int check(int x,int y,int z){
    for(int i=0;i<13;i++){
        int nex,ney,nez,cnt=1;
      nex=x+dx[i],ney=y+dy[i],nez=z+dz[i];
      while(1){
	if(nex>n || nex<=0 || ney>n || ney<=0 || nez>n || nez<=0)break;
	if(mp[nex][ney][nez]!=mp[x][y][z])break;
	cnt++,nex+=dx[i],ney+=dy[i],nez+=dz[i];
      }
      nex=x-dx[i],ney=y-dy[i],nez=z-dz[i];
      while(1){
	if(nex>n || nex<=0 || ney>n || ney<=0 || nez>n || nez<=0)break;
	if(mp[nex][ney][nez]!=mp[x][y][z])break;
	cnt++,nex-=dx[i],ney-=dy[i],nez-=dz[i];
      }
        if(cnt>=m) return mp[x][y][z];
    }
    return -1;
}
      
int main(){
  while(1){
    int x,y,win=-1,turn;
  cin>>n>>m>>p;
  if(n+m+p==0) break;
  memset(mp,-1,sizeof(mp));
  for(int i=1;i<=p;i++){
    cin>>x>>y;
      int z=1;
      while(mp[x][y][z]!=-1)z++;
      mp[x][y][z]=i%2;
      if(win==-1){win=check(x,y,z);if(win>=0) turn=i;}
   }
   if(win==-1) cout<<"Draw"<<endl;
  else if(win==1) cout<<"Black "<<turn<<endl;
  else cout<<"White "<<turn<<endl;
  }
  
  return 0;
}

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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
int main()
{
    LL a,b,c,d;

    cin>>a>>b>>c>>d;

    LL z = (c*d)/__gcd(c,d);
    a--;

    LL cnt = b/d-a/d + b/c-a/c -b/z+a/z;
//    cout<<cnt<<" ... \n";

    cnt=(b-a)-cnt;

    cout<<cnt;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
    using namespace std;
    #define lmax LLONG_MAX
    #define lmin LLONG_MIN
    #define imax INT_MAX
    #define imin INT_MIN
    #define f(i,a,b) for(long long i=a;i<b;i++)
    #define tc long long t;cin>>t;while(t--)
    #define pb push_back
    #define mp make_pair
    #define gcd __gcd
    #define F first
    #define S second
    #define input(a,n) for(ll i=0;i<n;i++) cin>>a[i];
    #define output(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" ";
    #define up upper_bound
    #define lo lower_bound
    #define endl "\n"
    #define mem(a) memset(a,-1,sizeof(a))
    #define ll long long
    #define umap unordered_map


    int main(){
        #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        #endif
        
        string s;
        cin>>s;
        ll n=s.size();
        ll sum=0;
        f(i,0,n){
            sum+=s[i]-'0';
        }

        if(sum%9==0) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

        return 0;
    }

Measured memory_bytes: 3720
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <stack>
#include <bitset>
using namespace std;

typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;

#define rep(i,n) for(int i=0;i<n;i++)
#define repf(i,f,n) for(int i=f;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define INT_MAX 2147483647
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())



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


int main() {

  string a = "AGCT";

  string S;
  cin >> S;

  int ans = 0;
  bool flag =false;
  int anss = 0;


  rep(i,S.size()){
    rep(j,4){
      if(S[i]==a[j]){
        flag = true;
        ans++;
      }
    }
    anss = max(anss,ans);
    if(!flag) ans = 0;
    flag = false;
  }



  cout << anss << endl;


}

















//


Measured memory_bytes: 256
import sys
H,W,h,w=map(int,input().split())
rh=H%h
rw=W%w
qh=H//h
qw=W//w
if rh==0 and rw==0:
    print('No')
    sys.exit()
print('Yes')
dp=[[0]*W for i in range(H)]
for i in range(0,H,h):
    for j in range(0,W,w):
        dp[i][j]=10**9-1
for i in range(h-1,H,h):
    for j in range(w-1,W,w):
        dp[i][j]=-10**9
for i in range(H):
    print(' '.join(map(str,dp[i])))

Measured memory_bytes: 45916
#include<bits/stdc++.h>
using namespace std;
long long n,x2=1,ans,x1=131,xx=x1,a1[1000001],a2[1000001];
map<unsigned long long,int>t;
string st,s;
inline long long read()
{
   long long sum=0,x=1;
   char ch=getchar();
   while (ch<'0'||ch>'9')
   {
       if (ch=='-')
	     x=-1;
	   ch=getchar();
   }
   while (ch>='0'&&ch<='9')
   {
   	   sum=sum*10+ch-'0';
	   ch=getchar();
   }
   return sum*x;
}
inline void write(long long x)
{
    if (x<0)
	{
        putchar('-');
        x=-x;
    }
    if (x>9)
      write(x/10);
    putchar(x%10+'0');
    return;
}
int main()
{
	n=read();
	for (register int i=1;i<64;++i)
	{
		x2*=xx;
		xx*=xx;
	}
	cin>>st;s=' '+st;
	a2[0]=1;
	for (register int i=1;i<=n;++i)
	{
		a1[i]=a1[i-1];a2[i]=a2[i-1];
		if (s[i]=='+')
		  a1[i]+=a2[i];else
		if (s[i]=='-')
		  a1[i]-=a2[i];else
		if (s[i]=='<')
		  a2[i]*=x2;else
		  a2[i]*=x1;
		++t[a1[i]];
	}
	for (register int i=1;i<=n;++i)
	{
		ans+=t[a1[n]*a2[i-1]+a1[i-1]];
		--t[a1[i]];
	}
	write(ans);
	return 0;
}

Measured memory_bytes: 38740
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;



int main(){
    int X, A;
    cin >> X >> A;
    cout <<  ( X < A ? 0 : 10);
    rn 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
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;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x%mod;
}

int mod_pow(int x, int y, int mood) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%mood;
		x = x * x%mood;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int n, k;
string s;
int cnt;

signed main() {
	cin >> n >> k >> s;
	for (int i = 1; i < (int)s.size(); i++) {
		if (s[i - 1] == s[i])cnt++;
	}
	cout << min(n - 1, cnt + 2 * k) << endl;
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
	public static void main(String[] args) throws java.io.IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String snake;
		bf.readLine();
		while ((snake = bf.readLine()) != null) {
			String ans = isSnakeA(snake) ? "A" : isSnakeB(snake) ? "B" : "NA";
			System.out.println(ans);
		}
	}

	private static boolean isSnakeA(String snake) {
		String sa = "^>'(=+)#\\1~$";
		Pattern pa = Pattern.compile(sa);
		Matcher ma = pa.matcher(snake);
		return ma.matches();
	}

	private static boolean isSnakeB(String snake) {
		String sb = "^>\\^(Q=)+~~$";
		Pattern pb = Pattern.compile(sb);
		Matcher mb = pb.matcher(snake);
		return mb.matches();
	}
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
using namespace std;
long long a, b, x, y, c;
int main() {
    scanf("%lld %lld %lld",&a, &b, &c);
    x = (a/c)*c;
    if (x<a) x+=c;
    y = (b/c)*c;
    printf("%lld\n",(y-x)/c+1);
    return 0;
}

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

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

#ifndef INPUTS_DIR
#define INPUTS_DIR "./"
#endif


vector<ll> bestArray(vector<ll> a) {
    int n = a.size() / 3;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        pq.push(a[i]);
        sum += a[i];
    }
    vector<ll> answer;
    answer.push_back(sum);
    for (int i = n; i < 2 * n; i++) {
        pq.push(a[i]);
        sum += a[i];
        sum -= pq.top();
        pq.pop();
        answer.push_back(sum);
    }
    return answer;
}

void solve(ll N, vector<ll> a) {
    auto front = bestArray(a);
    for (auto &&i : a) i *= -1;
    reverse(a.begin(), a.end());
    auto back = bestArray(a);
    long long ans = -1e18;
    for (int i = 0; i <= N; i++) {
        ans = max(ans, front[i] + back[N - i]);
    }
    cout << ans << endl;
}


void main_(istream &cin) {
    ll N;
    cin >> N;
    vector<ll> a(3 * N - 1 + 1);
    for (int i = 0; i <= 3 * N - 1; i++) {
        cin >> a[i];
    }
    solve(N, a);
}

int main() {
#ifdef INTELLIJ
    ifstream ifs(string(INPUTS_DIR) + "in_1.txt");
    if (ifs.is_open()) {
        main_(ifs);
        ifs.close();
    } else {
        cerr << "Error: no input." << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    main_(cin);
#endif
}





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

int main()
{

  int n ;
  cin >> n ;
  int a[n],b[n],c[n-1] ;
  for(int i=0;i<n;i++) cin >> a[i] ;
  for(int i=0;i<n;i++) cin >> b[i] ;
  for(int i=0;i<n-1;i++) cin >> c[i] ;

  int ans = 0;
  ans+= b[a[0]-1] ;

  for(int i=1;i<n;i++){
      ans+= b[a[i]-1] ;
      if(a[i]==(a[i-1]+1)){
          ans+= c[a[i-1]-1] ;
      }
  }
  
  cout << ans << endl;
    return 0;
}



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

int n;

string ans4[4]={
    "abaa",
    "abcc",
    "ccba",
    "aaba"
};

string ans5[5]={
    "aa.ab",
    "b..ab",
    "baacc",
    "abb.b",
    "a.aab"
};

int main(){
    cin>>n;
    if(n==2){
        cout<<"-1\n";
        return 0;
    }

    if(n==3){
        cout<<"aab\n";
        cout<<"b.b\n";
        cout<<"baa\n";
        return 0;
    }

    if(n==6){
        cout<<"aab...\n";
        cout<<"b.b...\n";
        cout<<"baa...\n";
        cout<<"...aab\n";
        cout<<"...b.b\n";
        cout<<"...baa\n";
        return 0;
    }

    if(n==7){
        cout<<"aa.aa.a\n";
        cout<<".bb..ba\n";
        cout<<"a..aab.\n";
        cout<<"a...b.b\n";
        cout<<"....bab\n";
        cout<<"abb..a.\n";
        cout<<"a.aa.bb\n";
        return 0;
    }

    if(n==11){
        cout<<"aabb.a.....\n";
        cout<<".cc.ca.....\n";
        cout<<"b...cb.....\n";
        cout<<"bc...b.....\n";
        cout<<"ac.cc......\n";
        cout<<"a.bbaa.....\n";
        cout<<"......aa.ab\n";
        cout<<"......b..ab\n";
        cout<<"......baacc\n";
        cout<<"......abb.b\n";
        cout<<"......a.aab\n";
        return 0;
    }

    int num4,num5;
    for(num4=0;;num4++){
        if((n-4*num4)%5==0)break;
    }
    num5=(n-4*num4)/5;

    rep(i,n){
        rep(j,n){
            if(i<4*num4&&j<4*num4&&i/4==j/4)cout<<ans4[i%4][j%4];
            else if(4*num4<=i&&4*num4<=j&&(i-4*num4)/5==(j-4*num4)/5)cout<<ans5[(i-4*num4)%5][(j-4*num4)%5];
            else cout<<'.';
        }
        cout<<endl;
    }
}

Measured memory_bytes: 1280
#include "bits/stdc++.h"
using namespace std;
int s[510][510];
int main(){
	int n,m,q;cin>>n>>m>>q;
	int l,r;
	for (int i=0; i<m; ++i){
		cin>>l>>r;
		for (int j=r; j<501; ++j)++s[l][j];
	}
	int ans;
	for (int i=0; i<q; ++i){
		cin>>l>>r;
		ans=0;
		for (int j=l; j<=r; ++j)
			ans+=s[j][r]-s[j][l-1];
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 1920
using System;

namespace ABC100_A_Happy_Birthday
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			string[] input = Console.ReadLine().Split(' ');
			int a = int.Parse(input[0]);
			int b = int.Parse(input[1]);

			if (a <= 8 && b <= 8)
			{
				Console.WriteLine("Yay!");
			}
			else
			{
				Console.WriteLine(":(");
			}
		}
	}
}


Measured memory_bytes: 11092
a,b,c,d=map(int,input().split())

def calc_div_num(a,b,x):
  return b//x - (a-1)//x

num_c = b//c - (a-1)//c
num_d = b//d - (a-1)//d

import math
lcd = int(c * d / math.gcd(c,d))
num_lcd = b//lcd - (a-1)//lcd

result = b-a+1 - (num_c+num_d-num_lcd)
print(result)

Measured memory_bytes: 9216
#define _LIBCPP_DEBUG 0
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;

    string result = "No";
    if((a==b || a==c || c==b) && !(a==b && b==c)) result = "Yes";
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int Array[100005];
long long Partial[100005];
int Max = 0;
void Read()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        cin >> Array[i];
    }
    sort(Array + 1, Array + N + 1);
    for(int i = 1; i <= N; i++)
    {
        Partial[i] = Partial[i - 1] + Array[i];
        if(Partial[i - 1] * 2 < Array[i])
        {
            Max = i;
        }
    }
    cout << N - Max + 1 << "\n";
}


int main()
{
    Read();
    return 0;
}


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

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

int main()
{
  int n, m;

  while (cin >> n >> m, n + m){
    int s[2000] = {0}, tmp[m + 1], p = 0, cnt = 0;
    REP(i, n) cin >> s[i];
    REP(i, m) cin >> tmp[i];
    REP(i, m){
      if (p <= n - 1){
        cnt++;
      }
      else break;
      p += tmp[i];
      p += s[p];
    }
    cout << cnt << endl;
  }
}

Measured memory_bytes: 1168