akhauriyash/Code-Regression huggingface dataset:
#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;

ll const MAX = 200005;
ll v[MAX];
vector<ll> G[MAX];
ll n, m;
ll color[MAX];
ll v_a[MAX];
ll v_b[MAX];

int main() {
	cin >> n >> m;
	REP(i, 1, n) {
		char c;
		cin >> c;
		v[i] = (c == 'A');
		color[i] = 1;
		v_a[i] = v_b[i] = 0;
	}
	REP(i, 1, m) {
		ll s, t;
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	stack<ll> st;
	REP(i, 1, n) {
		for (ll j = 0; j < G[i].size(); j++) {
			ll next = G[i][j];
			//cout << i << " " << next <<" " << v[next]  << endl;
			if (v[next] == 1) {
				v_a[i]++;
			}
			else {
				v_b[i]++;
			}
		}
		
			/*
			for (ll j = 0; j < G[i].size(); i++) {
				ll next = G[i][j];
				if (v[i] == 1) {
					v_a[next]--;
				}
				else {
					v_b[next]--;
				}
			}
			*/
		
	}
	REP(i, 1, n) {
		if ((v_a[i] <= 0 || v_b[i] <= 0) && color[i] == 1) {
			color[i] = 0;
			st.push(i);
			//cout << i << endl;
		}
	}
	while (!st.empty()) {
		ll cur = st.top();
		st.pop();
		for (ll i = 0; i < G[cur].size(); i++) {
			ll next = G[cur][i];
			if (color[next] == 0) {
				continue;
			}
			if (v[cur] == 1) {
				v_a[next]--;
			}
			else {
				v_b[next]--;
			}
			if (v_a[next] <= 0 || v_b[next] <= 0) {
				color[next] = 0;
				st.push(next);
				//cout << next << endl;
			}
		}
	}
	/*
	cout << "!" << endl;
	REP(i, 1, n) {
		cout << color[i] << " " << v_a[i] << " " << v_b[i]<< endl;
	}
	*/
	REP(i, 1, n) {
		if (color[i] == 1) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 18688
import numpy as np
n = int(input())
a = [int(i) for i in input().split(" ")]
s = [a[0]]
for i in a[1:]:
    s.append(s[-1]+i)
s = np.array(s)
ar = np.argmin(np.abs(s-s[-1]/2))
if s[ar]==s[-1]/2:
    print(0)
else:
    te=s[ar]-s[-1]/2
    print(int(abs(te)//0.5))

Measured memory_bytes: 34208
from collections import defaultdict


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    S = [0] * (N + 1)  # 累積和
    for i in range(1, N + 1):
        S[i] = S[i - 1] + A[i - 1]
    T = [(s - i) % K for i, s in enumerate(S)]
    counter = defaultdict(int)
    ans = 0
    for j in range(N + 1):
        if j >= K:
            counter[T[j - K]] -= 1
        ans += counter[T[j]]
        counter[T[j]] += 1
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 53900
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    string s;
    cin >> s;
    for (char& c : s)
        if (c == '?') c = 'D';
    cout << s << endl;
}

Measured memory_bytes: 3752
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            bool ans = false;
            string[] s = Console.ReadLine().Split(' ');

            int A = int.Parse(s[0]);
            int B = int.Parse(s[1]);
            int C = int.Parse(s[2]);

            if(A < B)
            {
                if (A < C && C < B)
                    ans = true;
                else
                    ans = false;
            }
            else
            {
                if (B < C && C < A)
                    ans = true;
                else
                    ans = false;

            }

            if(ans)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11092
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    double k = sqrt(8*n+1)/2.0 - 1.0/2.0;
    int z = int(k);
    if (k != int(k)) ++z;

    for (int i=z;i>0;--i) {
        if (n-i<0) {}
        else if (n-i==0) {
            cout << i << endl;
            break;
        }
        else {
            n -= i;
            cout << i << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
long long n, c, a[500], b[500], I[500][500], dp[500][500], mod = 1000000007;
int main() {
	cin >> n >> c; 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; i++) {
		for (int j = a[i]; j <= b[i]; j++) {
			long long P = 1;
			for (int k = 0; k <= c; k++) {
				I[i][k] += P; P *= j; P %= mod; I[i][k] %= mod;
			}
		}
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= c; j++) {
			for (int k = 0; k <= j; k++) { dp[i][j] += dp[i - 1][k] * I[i - 1][j - k]; dp[i][j] %= mod; }
		}
	}
	cout << dp[n][c] << endl;
	return 0;
}

Measured memory_bytes: 3328
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

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

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

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

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

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

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

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

fn gcd(x: i64, y: i64) -> i64 {
  if y == 0 {
    x
  } else {
    gcd(y, x % y)
  }
}

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    a: i64,
    b: i64,
  }
  let g = gcd(a, b);
  let m = a * b / g;
  puts!("{}\n", m);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define N 2001
#define M 1000000007ll
using namespace std;

long long s, ans, dp[N][N];

int main() {
    cin>>s; dp[0][0] = 1;
    
 	for (int i=1; i<=s; i++) {
        for (int j=3; j<=s; j++) {
            dp[i][j] = (dp[i-1][j-3] + dp[i][j-1]) % M;
        }
    }
    
    for (int i=1; i<=s; i++) ans = (ans + dp[i][s]) % M;
    cout<<ans<<endl;
}

Measured memory_bytes: 34688
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	vector<int> P(N);
	int i;
	for(i = 0; i < N; i++) {
		cin >> P[i];
	}
	
	vector<int> p_memo;
	size_t p_size = p_memo.size();
	bool f1 = true, f2 = true, f3 = true;
	int j;
	int count = 0;
	while(f1 && f2 && f3 && N - p_size > 2) {
		for(i = 0; i < N; i++) {
			if(f1 && P[i] <= A) {
				for(j = 0; j < p_size; j++) {
					if(i == p_memo[j]) {
						f1 = false;
						break;
					}
				}
				if(f1) {
					p_memo.push_back(i);
					p_size++;
					f1 = false;
				}
				else f1 = true;
			}
			else if(f3 && P[i] > B) {
				for(j = 0; j < p_size; j++) {
					if(i == p_memo[j]) {
						f3 = false;
						break;
					}
				}
				if(f3) {
					p_memo.push_back(i);
					p_size++;
					f3 = false;
				}
				else f3 = true;
			}	
			else if(f2 && P[i] > A && P[i] <= B) {
				for(j = 0; j < p_size; j++) {
					if(i == p_memo[j]) {
						f2 = false;
						break;
					}
				}
				if(f2) {
					p_memo.push_back(i);
					p_size++;
					f2 = false;
				}
				else f2 = true;
			}	
		}
		if(!f1 && !f2 && !f3) {
			count++;
			f1 = f2 = f3 = true;
		}
	}
	cout << count << endl;
}


Measured memory_bytes: 256
S = input().strip()
N = len(S)
A = [0 for _ in range(N)]
flag = 0
curR = 0
for i in range(N):
    if flag==0 and S[i]=="L":
        curL = i
        nR = i-curR
        flag = 1
    if flag==1 and S[i]=="R":
        curR = i
        nL = i-curL
        flag = 0
        if (nR+nL)%2==0:
            A[curL-1]=(nR+nL)//2
            A[curL] = (nR+nL)//2
        else:
            if nR>nL and (nR-1)%2==0:
                A[curL-1]=(nR+nL+1)//2
                A[curL] = (nR+nL)//2
            elif nR>nL and (nR-1)%2==1:
                A[curL-1]=(nR+nL)//2
                A[curL] = (nR+nL+1)//2
            elif nL>nR and (nL-1)%2==0:
                A[curL-1]=(nR+nL)//2
                A[curL]=(nR+nL+1)//2
            elif nL>nR and (nL-1)%2==1:
                A[curL-1]=(nR+nL+1)//2
                A[curL]=(nR+nL)//2
nL = N-curL
if (nR+nL)%2==0:
    A[curL-1]=(nR+nL)//2
    A[curL] = (nR+nL)//2
else:
    if nR>nL and (nR-1)%2==0:
        A[curL-1]=(nR+nL+1)//2
        A[curL] = (nR+nL)//2
    elif nR>nL and (nR-1)%2==1:
        A[curL-1]=(nR+nL)//2
        A[curL] = (nR+nL+1)//2
    elif nL>nR and (nL-1)%2==0:
        A[curL-1]=(nR+nL)//2
        A[curL]=(nR+nL+1)//2
    elif nL>nR and (nL-1)%2==1:
        A[curL-1]=(nR+nL+1)//2
        A[curL]=(nR+nL)//2
print(*A)

Measured memory_bytes: 83948
k = int(input())

lun_ls = []
def change_to_num(ls):
    ls = list(map(str, ls))
    strnum = ''.join(ls)
    return int(strnum)
def lun(num):
    '''
    渡された数が上限行ってなければlun_lsに追加して、次の数で再帰呼出
    '''
    if num > 3234566667:
        return

    lun_ls.append(num)
    last = num % 10
    for nex in range(last-1, last+2):
        if 0<= nex < 10:
            new_str = str(num) + str(nex)
            new = int(new_str)
            lun(new)
            
for start in range(1,10):
    lun(start)
lun_ls.sort()
print(lun_ls[k-1])

Measured memory_bytes: 13368
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[100010],n;
long long s;
int dfs(int x)
{
    int i;
    s=s+a[x];
    for(i=x+1;i<n;i++)
    {
        if(a[i]>2*s)
            break;
        s=s+a[i];
    }
    return i;
}
int main()
{
    int i,j,sum;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        s=0;
        i=0;
        while(1)
        {
            if(i==n)
                break;
                j=i;
            i=dfs(i);
        }
        sum=n-j;
        printf("%d\n",sum);
    }
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
typedef long long ll;

int main() {
    int N; cin >> N;
    vector<ll> A(N);
    map<ll, ll> MAP;
    rep(i,N){
        cin >> A[i];
        MAP[A[i]]++;
    }
    
    ll sum = 0;
    for(auto it : MAP) sum += it.second*(it.second-1)/2;

    rep(i,N){
        cout << sum - MAP[A[i]] + 1 << endl;
    }
}

Measured memory_bytes: 12160
from collections import deque

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = deque([])
    for i, tmp in enumerate(a):
        if i%2 == 0:
            b.append(tmp)
        else:
            b.appendleft(tmp)
    if n%2 == 1:
        b.reverse()
    print(*b)

if __name__ == "__main__":
    main()


Measured memory_bytes: 25412
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

    ll N;
    cin >> N;
    cout << N*N*N << endl;
}

Measured memory_bytes: 256
/*#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	cout<<max(0,b+c-a)<<endl;
	return 0;
}*/
/*#include<bits/stdc++.h>
using namespace std;
bool check(int p)
{
	if(p>=1&&p<=9||p>=100&&p<=999||p>=10000&&p<=99999) return true;
	return false;
}
int main()
{
	int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++)
	if(check(i)) ans++;
	cout<<ans<<endl;
	return 0;
}*/
/*#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	int f[100010];
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&f[i]);
	for(int i=1;i<n;i++)
	if(f[i]<=f[i+1]) continue;
	else if(f[i]+1==f[i+1]) f[i+1]--;
	else if(f[i]==f[i+1]+1&&f[i]-1>=f[i-1]&&i!=1) f[i]--;
	else
	{
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
	return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int i=0;
	while(i<s.length())
	{
		int odd=0,even=0;
		int lb,rb;
		int l=i,r;
		int tmp=1;
		while(s[i]=='R'&&i<s.length())
		{
			i++;
			tmp++;
		}
		if(tmp%2==0) odd+=tmp/2,even+=tmp/2;
		else odd+=tmp/2+1,even+=tmp/2;
		lb=i-1;
		rb=i;
		tmp=0;
		while(s[i]=='L'&&i<s.length())
		{
			i++;r=i;
			tmp++;
		}
		tmp--;
		if(tmp%2==0) odd+=tmp/2,even+=tmp/2;
		else odd+=tmp/2,even+=tmp/2+1;
		for(int j=l;j<r;j++)
		if(j==lb) cout<<even<<" ";
		else if(j==rb) cout<<odd<<" ";
		else cout<<0<<" ";
	}
	cout<<endl;
}

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


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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
int main(void){
    ll n;
    cin>>n;
    ll a[5];
    ll m=1000000000000000000,t=0;
    cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
    for(int i=0;i<5;i++){
        if(m>a[i]){
            m=a[i];
            t=i;
        }
    }
    ll ans=4+(n+m-1)/m;
    cout<<ans<<endl;
    
    
}


Measured memory_bytes: 3628
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)
#define REPIT(i,x) for(auto i{(x).begin()}; i != (x).end(); i++) 

#define PB push_back
#define MP make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef double dbl;
typedef vector<bool> Vb;
typedef vector<char> Vc;
typedef vector<double> Vd;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<string> Vs;
typedef vector<vector<int>> VVi;
typedef vector<vector<ll>> VVl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }
inline void YES() { cout << "YES" << endl; } inline void Yes() { cout << "Yes" << endl; }
inline void NO() { cout << "NO" << endl; } inline void No() { cout << "No" << endl; }

const int inf = 1 << 30;
const ll linf = 1LL << 60;
const int MOD = 1000000007;

#include <set>

typedef tuple<int, int, int> tup;

int n, q;

auto sortBegin = [](const tup& left, const tup& right) { return get<0>(left) > get<0>(right); };
auto sortEnd = [](const tup& left, const tup& right) { return get<1>(left) > get<1>(right); };

multiset<int> stop;
priority_queue<tup, vector<tup>, decltype(sortBegin)> pending(sortBegin);
priority_queue<tup, vector<tup>, decltype(sortEnd)> active(sortEnd);

vector<pii> query;
Vi ans;

void init()
{
	cin >> n >> q;
	REP(_i, n)
	{
		int s, t, x;
		cin >> s >> t >> x;
		s = max(0, s - x);
		t = max(0, t - x);

		pending.push(tup(s, t, x));
	}
	query.reserve(q);
	ans.resize(q);
	REP(i, q)
	{
		int t; cin >> t;
		query.emplace_back(pii(t, i));
	}
	sort(ALL(query));
}

int main()
{
	init();

	REP(i, q)
	{
		int t = query[i].first;

		while (!pending.empty() && get<0>(pending.top()) <= t)
		{
			stop.insert(get<2>(pending.top()));
			active.push(pending.top());
			pending.pop();
		}

		while (!active.empty() && get<1>(active.top()) <= t)
		{
			stop.erase(stop.find(get<2>(active.top())));
			active.pop();
		}

		if (!stop.empty())
			ans[query[i].second] = *(stop.begin());
		else
			ans[query[i].second] = -1;
	}

	REP(i, q)
		cout << ans[i] << endl;
}


Measured memory_bytes: 18288
#include<iostream>

using namespace std;

int main(){

  int a[13]={0,1,2,1,3,1,3,1,1,3,1,3,1};

  int x,y;
  cin >> x >>y;
  if(a[x] == a[y]){
    cout << "Yes" << endl;
  }
  else{
    cout << "No"<<endl;
  }

}

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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka
const long MOD = 998244353;

long pw(int x) {
    long res = 1;
    long a = 2;
    while (x > 0) {
        if (x & 1) {
            res *= a;
            res %= MOD;
        }
        a *= a;
        a %= MOD;
        x /= 2;
    }
    return res;
}

void add(int &a, int b) {
    a += b;
    a %= MOD;
//    cout << "!!! " << b << "\n";
}

vector<int> f;

void init(int n) {
    f.assign(n + 1, 0);
}

long sum(int r) { // exclusive
    if (r == 0)
        return 0;
    r--;
    long result = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        result += f[r];
    return result;
}

void inc(int i) {
    for (; i < f.size(); i = (i | (i + 1)))
        f[i]++;
}

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

    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;

    int res = 0;
    for (int i = 0; i < n; i++) {
        add(res, pw(n));
        add(res, -pw(i));
        add(res, -pw(n - 1 - i));
        add(res, -pw(i));
        add(res, -pw(n - 1 - i));
    }

    sort(p.begin(), p.end());
    int last = -2000000000;
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (p[i].first != last) {
            last = p[i].first;
            c++;
        }
        p[i].first = c;
    }
    for (int i = 0; i < n; i++) {
        swap(p[i].first, p[i].second);
    }
    for (int q = 0; q < 2; q++) {
        for (int i = 0; i < n; i++) {
            p[i].first = n - 1 - p[i].first;
        }
        sort(p.begin(), p.end());

        init(n + 1);
        for (int i = 0; i < n; i++) {
//            cout << p[i].first << " " << p[i].second << "\n";
            int x = sum(p[i].second);
            int y = i - x;
//            cout << " " << x << " " << y << "\n";
            add(res, pw(x));
            add(res, pw(y));
            inc(p[i].second);
        }
    }

    res -= n;
    while (res < 0) res += MOD;
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 2560
N = int(input())
data_pp = [0]*N
data_pm = [0]*N
data_mp = [0]*N
data_mm = [0]*N
for i in range(N):
    x, y = map(int, input().split())
    data_pp[i] = x+y
    data_pm[i] = x-y
    data_mp[i] = -x + y
    data_mm[i] = -x - y

tmp1 = max(data_pp) + max(data_mm)
tmp2 = max(data_mp) + max(data_pm)
tmp3 = max(data_pm) + max(data_mp)
tmp4 = max(data_mm) + max(data_pp)
print(max(tmp1, tmp2, tmp3, tmp4))
def d(p1, p2):
    xA = p1[0]
    xB = p2[0]

    yA = p1[1]
    yB = p2[1]
    return max(xA + yA - (xB + yB), - (xA - yA) - -1 * (xB - yB), xA - yA - (xB - yB), -1*(xA + yA)- -1 * (xB + yB)) 



Measured memory_bytes: 40424
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(void)
{
     ll a  , b , c ,d;

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

    if(a*b>c*d)
    {
        cout << a*b <<endl;
    }
    else if( c*d > a*b )
    {
        cout << c*d <<endl;
    }
    else
    {
        cout << a*b <<endl;
    }


}


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

int main(){
  char s[100],p[100],c[200];

  scanf("%s",s);
  scanf("%s",p);

  strcpy(c,s);
  strcat(c,s);
  if(strstr(c,p)!=NULL)printf("Yes\n");
  else printf("No\n");

  return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #define int long long
    int n;
    cin >> n;
    vector <int> a(n);
    int s = 0, x = -1e9;
    for(int i = 0; i < n; ++i){cin >> a[i];s += abs(a[i]);}
    for(int i = 0; i < n; ++i){x = max(x, s-2*abs(a[i]));}
    s = 0;
    for(int i = 0; i + 1 < n; ++i){if(a[i] < 0) {a[i] *= -1; a[i+1] *= -1;}}
    for(int i = 0; i < n; ++i){s += (a[i]);}
    x = max(x, s);
    
    cout << x << '\n';
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll n, K;
    cin >> n >> K;

    ll R, S, P;
    cin >> R >> S >> P;

    string T;
    cin >> T;

    ll sum = 0;
    rep(i, n) {
        if (i >= K && T[i] == T[i-K]) {
            T[i] = '_';
            continue;
        }
        if (T[i] == 'r') {
            sum += P;
        }
        else if (T[i] == 's') {
            sum += R;
        }
        else {
            sum += S;
        }
    }

    put(sum);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 3744
// ABC 144-D
// 2019.10.27 bal4u

#include <stdio.h>
#include <math.h>

#define PI 3.1415926535897932384626433832795

int main()
{
	int a, b, x;
	double ans;
	
	scanf("%d%d%d", &a, &b, &x);
	ans = atan2(2.0*x, (double)a*b*b);
	if (b*tan(ans) > a) {
		ans = atan2(a*a*a, 2.0*(a*a*b-x));
	}
	printf("%.12lf\n", 90-ans*180.0/PI);
	return 0;
}


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

#define int long long int
#define ff first
#define ss second
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod = 1e9 + 7;
const int cmod = 998244353;
const int N = 1e3 + 5;
const int inf = 1e16 + 2;

void solve(int Case) {
    int d , l , r;
    cin >> l >> r >> d;
    cout << (r / d - (l - 1) / d) << '\n';
}
/*
 */

int32_t main()
{
    fastio
    int testcase = 1;
    //cin >> testcase;
    int Case = 1;
    while(testcase --) {
        solve(Case ++);
    }
    return 0;
}
 



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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>a(5,0);
	vector<int>P={0,0,0,0,0,0,1,1,1,2};
	vector<int>Q={1,1,1,2,2,3,2,2,3,3};
	vector<int>R={2,3,4,3,4,4,3,4,4,4};
	for(int i=0;i<n;++i){
		string s; cin>>s;
		if(s.front()=='M')++a.at(0);
		else if(s.front()=='A')++a.at(1);
		else if(s.front()=='R')++a.at(2);
		else if(s.front()=='C')++a.at(3);
		else if(s.front()=='H')++a.at(4);
	}
	uint64_t ans=0;
	for(int i=0;i<10;++i){
		ans+=(uint64_t)a.at(P.at(i))*a.at(Q.at(i))*a.at(R.at(i));
	}
	cout<<ans<<"\n"s;
}

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N, M, R = MAP()
A = [a-1 for a in LIST()]
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

# 全体グラフの最短距離(ここから必要な頂点間だけ使う)
wf = warshall_floyd(N, G)

ans = INF
for r in range(R):
    # TSP(巡回セールスマン)
    dp = list2d(1<<R, R, INF)
    dp[1<<r][r] = 0
    for bit in range(1, (1<<R)-1):
        for i in range(R):
            if not (bit >> i & 1):
                continue
            for j in range(R):
                if bit >> j & 1:
                    continue
                a, b = A[i], A[j]
                dp[bit|1<<j][j] = min(dp[bit|1<<j][j], dp[bit][i] + wf[a][b])
    ans = min(ans, min(dp[-1]))
print(ans)


Measured memory_bytes: 54236
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
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; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll H, W;
        cin >> H >> W;
        vector<vector<char> > grid(H+2, vector<char>(W+2, '.'));

        rep(i, 1, H+1) rep(j, 1, W+1) cin >> grid[i][j];

        rep(i, 1, H+1) {
                rep(j, 1, W+1) {
                        if (grid[i][j] == '#') {
                                if (grid[i+1][j] == '.' and grid[i-1][j] == '.' and grid[i][j+1] == '.' and grid[i][j-1] == '.') {
                                        cout << "No" << endl;
                                        return 0;
                                }
                        }
                }
        }
        cout << "Yes" << endl;
}

Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){
  char s[200010], t[200010];
  scanf("%s",&s);
  scanf("%s",&t);
  int count = 0;

  for(int i = 0;i < strlen(s);i++){
    if(s[i]!=t[i]){
      count ++;
    }
  }
  printf("%d",count);
  return 0;
}


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

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

	for (int i = 0; i <= 1009; ++i) {
		if ((int)(i * 0.08) == a && (int)(i * 0.1) == b) {
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}

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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long

const int N = 200009, MOD = 998244353;
int n;
struct robot {
    int x, d;
    bool operator<(const robot& other) const {
        return x < other.x;
    }
} r[N];

int ans[N];

int seg[2*N];

void init() {
    for(int i = 0; i < n; ++i) {
        seg[i+n] = i+1;
    }

    for(int i = n-1; i > 0; --i) {
        seg[i] = max(seg[i<<1], seg[i<<1 | 1]);
    }
}

void upd(int i, int val) {
    i += n;
    seg[i] = val;
    for(; i > 1; i >>= 1) {
        seg[i>>1] = max(seg[i], seg[i^1]);
    }
}

int q(int l, int r) {
    int ret = 0;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if(l&1) ret = max(ret, seg[l++]);
        if(r&1) ret = max(ret, seg[--r]);
    }
    return ret;
}

int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> r[i].x >> r[i].d;
    }

    sort(r, r+n);

    init();
    for(int i = n-2; i >= 0; --i) {
        robot search; search.x = r[i].x+r[i].d;
        auto it = lower_bound(r, r+n, search);
        int mx = q(i, it-r);
        upd(i, mx);
    }

    ans[n] = 1;

    for(int i = n-1; i >= 0; --i) {
        ans[i] = (ans[seg[i+n]] + ans[i+1])%MOD;
    }

    cout << ans[0] << '\n';
    
    return 0;
}


Measured memory_bytes: 8064
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<math.h>
using namespace std;
using LL = long long;
const int INF = 1e9;

int N;

vector<int> len(3);
int ans = INF;

vector<pair<int, int>> now(4, pair<int, int>(0,0));
void dfs(int depth, vector<int> &l){
    if(depth < N){
        for(int i = 0;i < 4;i++){
            now[i].first += l[depth];
            now[i].second += 1;
            dfs(depth+1, l);
            now[i].first -= l[depth];
            now[i].second -= 1;
        }
    }
    else{
        int tmp = 0;
        for(int i = 0;i < 3;i++){
            if(now[i].second == 0)return;
            tmp += abs(len[i]-now[i].first)+10*(now[i].second-1);
        }
        ans = min(ans, tmp);
    }
}

int main(){
    cin >> N;
    for(int i = 0;i<3;i++)cin >> len[i];
    vector<int> l(N);
    for(int i = 0;i<N;i++)cin >> l[i];
    dfs(0, l);
    cout << ans;
}



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

int main() {
	// your code goes here
	string s;
	cin>>s;
	if(s=="Sunny")cout<<"Cloudy";
	if(s=="Cloudy")cout<<"Rainy";
	if(s=="Rainy")cout<<"Sunny";
	return 0;
}

Measured memory_bytes: 888
#include<stdio.h>

int main() {
	char S[102];
	long long K, i;
	char ans = '1';
	scanf("%s", S);
	scanf("%lld", &K);
	for (i = 0; i < K; i++) {
		if (S[i] != '1') {
			ans = S[i];
			break;
		}
	}
	printf("%c\n", ans);

	return 0;
}

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

int main(){
  int n, a, b;
  cin >> n >> a >> b;
  int ans = 0;
  rep(i,n+1){
    int k = 0;
    int res = i;
    while(res){
      k += res%10;
      res/=10;
    }
    if(a<=k && k<=b) ans += i;
  }
  cout << ans ;
  return 0;
}

Measured memory_bytes: 256
def main():
    N, X = (int(i) for i in input().split())

    A = [1] * (N+1)
    P = [1] * (N+1)
    for i in range(1, N+1):
        A[i] = 2*A[i-1] + 3
        P[i] = 2*P[i-1] + 1

    def f(N, X):
        if N == 0:
            return 0 if X <= 0 else 1
        elif X == 1:
            return 0
        elif X <= 1 + A[N-1]:
            return f(N-1, X-1)
        elif X == 2 + A[N-1]:
            return P[N-1] + 1
        elif X <= 2 + 2 * A[N-1]:
            return P[N-1] + 1 + f(N-1, X-2-A[N-1])
        elif X == 3 + 2 * A[N-1]:
            return 2 * P[N-1] + 1

    print(f(N, X))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
N,Q = map(int,input().split())
S = input()
s = [0]
cnt = 0
for i in range(N-1):
    if S[i:i+2] == 'AC':
        cnt += 1
    s.append(cnt)
for _ in range(Q):
    l,r = map(int,input().split())
    print(s[r-1]-s[l-1])


Measured memory_bytes: 6100
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
vector<long long> s;
void go(int x){
  if(x==1)
    for(int i=1;i<=9;i++)
      s.push_back(i);
  else if(x==2)
    for(int i=19;i<=99;i+=10)
      s.push_back(i);
  else{
    long long o=9;
    long long oo=10;
    for(int i=0;i<x-3;i++){
      o*=10;
      o+=9;
      oo*=10;
    }
    for(int i=10;i<=99;i++)
      s.push_back(i*oo+o);
  }
}
char ss[20];
pair<long double,long long> snuke[2001];
void choose(){
  for(int i=0;i<s.size();i++){
    sprintf(ss,"%lld",s[i]);
    int sum=0;
    for(int j=0;j<strlen(ss);j++)
      sum+=ss[j]-'0';
    snuke[i].first=(long double)(s[i]*1.0)/(sum*1.0);
    snuke[i].second=i;
  }
}
int main(){
  int k;cin>>k;
  s.clear();
  for(int i=1;i<=15;i++)
    go(i);
  long long o[9]={100999999999999,101999999999999,102999999999999,103999999999999,104999999999999,
  105999999999999,106999999999999,107999999999999,108999999999999};
  bool ok;
  int cnt=0;
  s.insert(s.begin()+1098,o,o+9);
  choose();
  for(int i=0;i<s.size();i++){
    ok=1;
    for(int j=i+1;j<s.size();j++)
      if(snuke[i].first>snuke[j].first)
        {ok=0;
         break;}
    if(ok==1 && cnt<k){
      cout<<s[i]<<endl;
      cnt++;}
  }
  return 0;
}

Measured memory_bytes: 384
n,m = map(int,input().split())
a = [int(v) for v in input().split()]
bc = [[int(v) for v in input().split()] for _ in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)


a.sort()

for i,v in enumerate(a):
  if len(bc) == 0:
    break
  c  = bc[0][1]
  bc[0][0] -= 1

  if bc[0][0] == 0:
    bc.pop(0)
    

  if v < c:
    a[i] = c
  else:
    break

print(sum(a))


Measured memory_bytes: 27000
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()

int main() {
   int n,k;
   cin >> n >> k;
   int l[60];
   rep(i,n)
   cin >> l[i];
   sort(l,l+n,greater<int>());
   int ans=0;
   rep(i,k)
   ans+=l[i];
   cout << ans << endl;
}

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

namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string str = Console.ReadLine();
            char moji;
            int code = 0;
            int anscode;
            int length = str.Length;
            char ans;

            for (int i = 0; i < length; i++)
            {
                moji = str[i];
                code = (int)moji;
                code -= 65;
                code += n;
                anscode = code % 26;
                anscode += 65;
                ans = (char)anscode;
                Console.Write(ans);
            }


        }
    }
}


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

int main() {
  int N;
  cin >> N;
  
  map<int,int> S;

  for(int i = 0; i < 10; i++) {
    for(int j = 0; j < 10; j++) {
      S[i * j];
    }
  }

  if (S.count(N)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void solve(){
    string s;
    int d;
    cin>>s;
    if (s=="SUN")
        cout<<7;
        if (s=="MON")
        cout<<6;
        if (s=="TUE")
        cout<<5;
        if (s=="WED")
        cout<<4;
        if (s=="THU")
        cout<<3;
        if (s=="FRI")
        cout<<2;
        if (s=="SAT")
        cout<<1;
}
int main(){
    solve();
    return 0;
}

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

#define FOR(i,n,m) for(int i=n; i<m; i++)

int main () {
    
    int n;
    cin >> n;
    
    int a[n];
    FOR(i,0,n) cin >> a[i];
    
    int MAX = INT_MIN;
    int min = INT_MAX;
    FOR(i,0,n) {
        
        if(a[i] - min > MAX ) MAX = a[i] - min;
        if(a[i] < min) min = a[i];
        
    }
    
    cout << MAX << endl;
    
    return 0;
}


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

using namespace std;
typedef long long ll;

const int P=1e9+7,M=1030;

struct mat{
	int x[3][3];
	mat(bool f=false){
		memset(x,0,sizeof(x));
		if(f)x[0][0]=x[1][1]=x[2][2]=1;
	}
	inline int* operator[](int i){return x[i];} 
	inline mat friend operator*(mat a,mat b){
		mat c;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)
			c[i][j]=((ll)a[i][0]*b[0][j]+(ll)a[i][1]*b[1][j]+(ll)a[i][2]*b[2][j])%P;
		return c;
	}
}A,B,R(true),v0[M],v1[M],v2[M];
int n,m,u,v;

inline mat fpa(int t){return v0[t&1023]*v1[t>>10&1023]*v2[t>>20&1023];}

int main(){
	A[0][0]=2,A[0][1]=2,A[0][2]=1;
	A[1][0]=1,A[1][1]=1,A[1][2]=1;
	A[2][0]=1,A[2][1]=0,A[2][2]=1;
	
	v0[0]=v1[0]=v2[0]=R;
	
	v0[1]=A;
	for(int i=2;i<=1024;i++)v0[i]=v0[1]*v0[i-1];
	v1[1]=v0[1024];
	for(int i=2;i<=1024;i++)v1[i]=v1[1]*v1[i-1];
	v2[1]=v1[1024];
	for(int i=2;i<=1024;i++)v2[i]=v2[1]*v2[i-1];
	
	B[0][0]=1,B[0][1]=2,B[0][2]=1;
	B[1][0]=0,B[1][1]=1,B[1][2]=1;
	B[2][0]=0,B[2][1]=0,B[2][2]=1;
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&v);
		R=R*fpa(v-u-1)*B;
		u=v;
	}
	R=R*fpa(n-u-1);
	
	printf("%d\n",((unsigned)R[0][0]+R[0][1]+R[0][2])%P);
	
	return 0; 
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1e+9;

int main(){
	int n;
	while( cin >> n , n ){
		int d[11][11], v=0, s[11]={0};
		
		for(int i=0 ; i < 11 ; i++ ){
			for(int j=0 ; j < 11 ; j++ ){
				d[i][j] = (i==j)? 0 : INF;
			}
		}
		for(int i=0 ; i < n ; i++ ){
			int a,b,c;
			cin >> a >> b >> c;
			d[a][b] = c;
			d[b][a] = c;
			v = max( max( v , a ) , b );
		}

		for(int k=0 ; k <= v ; k++ ){
			for(int i=0 ; i <= v ; i++ ){
				for(int j=0 ; j <= v ; j++ ){
					d[i][j] = min( d[i][j] , d[i][k]+d[k][j] );
				}
			}
		}

		int ans = INF;
		for(int i=0 ; i <= v ; i++ ){
			int cost = 0;
			for(int j=0 ; j <= v ; j++ ){
				cost += d[i][j];
			}
			s[i] = cost;
			ans = min( ans , cost );
		}
		for(int i=0 ; i <= v ; i++ ){
			if( s[i] == ans ){
				cout << i << " " << ans << endl;
				break;
			}
		}
	}
}



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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
int N, M;
cin >> N >> M; 
print((M * 1900 + 100 * (N - M)) * pow(2,M));
}


Measured memory_bytes: 256
// #include<bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef pair<int ,int> P;

const int INF  = 0x3f3f3f3f;
const int MAXN = 1e6+7;

string s[MAXN];

int main(){
        // freopen("../in.txt","r",stdin);
        // freopen("../out.txt","w",stdout);
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n;
        while(cin>>n) {
                map<string, ll> m;
                for(int i=0;i<n;++i) {
                        cin>>s[i];
                        sort(s[i].begin(),s[i].end());
                        m[s[i]]++;
                }
                ll ans = 0;
                ll cnt = 0;
                for(map<string,ll>::iterator it=m.begin();it!=m.end();++it) {
                        cnt = it->second;
                        ans += (cnt-1)*(cnt)/2;
                }
                cout<<ans<<endl;
        }
        return 0;
}


Measured memory_bytes: 23680
class UnionFind():
  def __init__(self,n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    
    if x == y :
      return 
    
    if self.parents[x] > self.parents[y]:
      x,y = y,x
  
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
  def size(self,x):
    return -self.parents[self.find(x)]
  

n, m = map(int,input().split())

ab = []
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  
  ab.append((a,b))
  
ans = 0
for i in range(len(ab)):
  uf = UnionFind(n)
  
  for j in range(len(ab)):
    if i == j:
      continue
      
    uf.union(ab[j][0], ab[j][1])
    
  if uf.size(0) != n:
    ans += 1
    
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

bool ac[100001] = {};
int wa[100001] = {};

int main(void) {
	lli n, m, wa_count = 0, ac_count = 0;
	cin >> n >> m;


	for (int i = 0; i < m; i++) {
		lli a;
		string s;
		cin >> a >> s;

		if (!ac[a]) {
			if (s == "AC") {
				ac[a] = true;
				ac_count++;
				wa_count += wa[a];
			}
			else if (s == "WA") {
				wa[a]++;
			}
		}
	}

	cout << ac_count << " " << wa_count << endl;

	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long

const int N=1005;
const int MOD=1e9+7;
 
 
int32_t main()
{
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin>>n;
  string s;
  cin>>s;
  int count=0;
  for(int i=0;i<n;i++)
  {
  	if(s[i]=='R')
  	{
  		count++;
  	}
  }
  int t=n-count;
  if(count>t)
  {
  	cout<<"Yes"<<endl;
  }
  else
  {
  	cout<<"No"<<endl;
  }
  
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
using namespace std;
 
int main(){
    int n,a[5001];
    int ans;
    a[0]=0;
    while(cin>>n&&n){
        ans = INT_MIN;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i] += a[i-1];
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                ans = max(ans,a[j]-a[i-1]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 2992
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;



#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

ll debugFlag = false;
template<typename T> void debug(T&);
template<typename T> void debug(T&, bool);
template<typename T> void debug(vector<T>&);
template<typename T> void debug(vector<T>&, bool);
template<typename T, typename U> void debug(pair<T, U>&);
template<typename T, typename U> void debug(pair<T, U>&, bool);

template<typename T>
void debug(T& obj) {
	debug(obj, true);
}

template<typename T>
void debug(T& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << obj;
	if (lnFlag) cout << endl;
}

template<typename T>
void debug(vector<T>& obj) {
	debug(obj, true);
}

template<typename T>
void debug(vector<T>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "[";
	rep(i, obj.size()) {
		if (i != 0) cout << ",";
		debug(obj[i], false);
	}
	cout << "]";
	if (lnFlag) cout << endl;
}

template<typename T, typename U>
void debug(pair<T, U>& obj) {
	debug(obj, true);
}

template<typename T, typename U>
void debug(pair<T, U>& obj, bool lnFlag) {
	if (!debugFlag) return;
	cout << "(";
	debug(obj.first, false);
	cout << ",";
	debug(obj.second, false);
	cout << ")";
	if (lnFlag) cout << endl;
}

void solve() {

	ll N;
	cin >> N;

	vector<ll> vec(N + 1);

	rep(i, vec.size()) {

		if (i == 0) vec[i] = 2;
		else if (i == 1) vec[i] = 1;
		else vec[i] = vec[i - 1] + vec[i - 2];

	}

	cout << vec[N];

}


int main(int argc, char* argv[]) {
	if (argc == 2 && string(argv[1]) == "debug") debugFlag = true;
	solve();
	cout << endl;
	return 0;
}


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

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

using namespace std;
const int MAXLEN = 50;

char S[2 * MAXLEN + 1];
char T[2 * MAXLEN + 1];

int main() {
	scanf("%s%s", S, T);
	for (int i = strlen(S) - strlen(T); i >= 0; i--) {
		bool ok = true;
		for (int j = 0; j < strlen(T); j++) {
			if (S[i + j] != T[j] && S[i + j] != '?') {
				ok = false;
				break;
			}
		}
		if (ok) {
			for (int j = 0; j < strlen(T); j++) {
				if (S[i + j] == '?') S[i + j] = T[j];
			}
			for (int j = 0; j < strlen(S); j++) {
				if (S[j] == '?') printf("a");
				else printf("%c", S[j]);
			}
			printf("\n");
			return 0;
		}
	}
	printf("UNRESTORABLE\n");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int N,buf;
    int len = 0;
    int d[100];
    bool flag;
    cin >> N;
    for(int i=0;i<N;i++){
        flag = true;
        cin >> buf;
        for(int j=0;j<len;j++){
            if(d[j] == buf){
                flag = false;
                break;
            }
        }
        if(flag){
            d[len] = buf;
            len++;
        }
    }
    cout << len << endl;
    return 0;
}


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

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    cout << "vowel" << endl;
  else cout << "consonant" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	string s;
	cin >> s;
	if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) {
		cout << "Bad" << endl;
	}
	else {
		cout << "Good" << endl;
	}
	return 0;
}

Measured memory_bytes: 256