akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;

const ll MAXN = 200000;
const ll INF = 1001001001;
const ll MOD = 1000000007;

ll N, ans=1, tmp=0;
vector<char> A;
vector<ll> B;

signed main(){
    cin >> N;
    for(int i=0;i<2*N;i++) {
        char a;
        cin >> a;
        A.push_back(a);
    }
    ll ct=0;
    for(int i=0;i<A.size()-1;i++) {
        if(A[i]==A[i+1]) {
            ct++;
            //cout << ct << endl;
        }
        if(ct%2==1) {
            tmp = i+1-2*B.size();
            B.push_back(tmp);
            if(tmp<=0) {
                cout << 0 << endl;
                return 0;
            }
        }
    }
    if(A[0]=='W'||ct%2==0||B.back()!=1) {
        cout << 0 << endl;
        return 0;
    }
    for(int i=0;i<B.size();i++) {
        ans *= B[i];
        ans %= MOD;
        //cout << B[i] << endl;
    }
    //cout << ans << endl;
    for(int i=1;i<=N;i++) {
        ans *= i;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4468
#include <cstdio>
#include <algorithm>

using namespace std;

using llint = long long;

const int MAXN = 2e5+5;

int n;
int h[MAXN], v[MAXN];
llint sol;

llint data[MAXN];
void update(int x, llint val) {
  for (int i = x; i < MAXN; i += i & -i) data[i] = max(data[i], val);
}
llint get_max(int x) {
  llint ret = 0;
  for (int i = x; i > 0; i -= i & -i) ret = max(ret, data[i]);
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", h+i);
  for (int i = 0; i < n; ++i) scanf("%d", v+i);

  for (int i = 0; i < n; ++i) {
    llint dp_i = get_max(h[i]-1)+v[i];
    update(h[i], dp_i);
    sol = max(sol, dp_i);
  }

  printf("%lld\n", sol);
  return 0;
}


Measured memory_bytes: 3328
#include<algorithm>//sort(all(変数),greater<型名>())　で降順に
#include<bits/stdc++.h>
#include<cmath>//切り上げceil(値)
#include<deque>
#include<iomanip>//setprecision(数字)
#include<iostream>
#include<list>
#include<map>
#include<numeric> //xとyの最大公約数は__gcd(x,y),xとyの最小公倍数は(x*y)/__gcd
#include<queue>//priority_queue<型名> 変数：優先度付きキュー　最大値の探索が早い
#include<set>
#include<stack>
#include<string>
#include<vector>
#define rep0(i,n)  for(ll i=0; i<n; i++)
#define rrep0(i,n) for(ll i=n-1; 0<=i; i--)
#define rep1(i,n)  for(ll i=1; i<=n; i++)
#define rrep1(i,n) for(ll i=n; 1<=i; i--)
#define vll vector<ll>
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define INF 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; }
using ll = long long;
using namespace std;

int main(){
  int n;  cin >> n;
  vi h(n);
  rep0(i,n)cin >> h[i];
  vll dp(n,INF);
  dp[0] = 0;
  rep0(i,n){
    chmin(dp[i],dp[i-1]+abs(h[i-1]-h[i]));
    if(1 <= i) chmin(dp[i],dp[i-2]+abs(h[i-2]-h[i]));
  }
  cout << dp[n-1];
}


Measured memory_bytes: 1408
n,m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
edge.sort()
from heapq import heappop,heapify,heappush
heapify(edge)

heap = [(0, 1)]
dist = [float("inf")]*(n+1)
while heap:
    cost, cur = heappop(heap)
    if dist[cur] <= cost:
        continue
    dist[cur] = cost
    while edge:
        if edge[0][0] <= cur:
            l,r,c = heappop(edge)
            if r < cur:
                continue
            heappush(heap,(cost+c, r))
        else:
            break

if dist[-1] == float("inf"):
    print(-1)
else:
    print(dist[-1])

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  if (a + b > c + d) cout << "Left" << endl;
  else if (a + b == c + d) cout << "Balanced" << endl;
  else if (a + b < c + d) cout << "Right" << endl;
}


Measured memory_bytes: 3640
#include <stdio.h>

int main() {
  int n, m;
  int data[1010][101];
  int result[101] = {};
  int idx;
  int i, j;

  while(scanf("%d %d", &n, &m), n || m) {
    for(i = 0; i < 101; i++) result[i] = 0;
    for(i = 0; i < n; i++) {
      for(j = 0; j < m; j++) {
	scanf("%d", &data[i][j]);
	result[j] += data[i][j];
      }
    }
    for(i = 0; i < m; i++) {
      idx = 0;
      for(j = 0; j < m; j++) {
	if(result[j] > result[idx]) idx = j;
      }
      printf("%d%c", idx+1, " \n"[i==m-1]);
      result[idx] = -1;
    }
  }

  return 0;
}

Measured memory_bytes: 996
n = int(input())
a = list(map(int, input()))
l = [0] * (n - 1)
for i in range(n - 1):
    l[i] = abs(a[i + 1] - a[i])
n -= 1
if 1 in l:
    for i in range(n):
        if l[i] == 2:
            l[i] = 0
ans = 0
for i, x in enumerate(l):
    if not (i ^ (n - 1)) & i:
        ans ^= x
print(ans)


Measured memory_bytes: 20692
#include <bits/stdc++.h>///int * int = int
using namespace std;
int h,w,d,s[300][300],q,a,b;
int x[90001],y[90001];
int dp[90001];
int main()
{
    scanf("%d%d%d",&h,&w,&d);
    for(int i = 0;i < h;i ++)
    {
        for(int j = 0;j < w;j ++)
        {
            scanf("%d",&s[i][j]);
            x[s[i][j]] = i;
            y[s[i][j]] = j;
        }
    }
    for(int i = 1 + d;i <= h * w;i ++)
    {
        dp[i] = dp[i - d] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d]);
    }
    scanf("%d",&q);
    for(int i = 0;i < q;i ++)
    {
        scanf("%d%d",&a,&b);
        printf("%lld\n",abs(dp[a] - dp[b]));
    }
}

Measured memory_bytes: 5124
import itertools
import math

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

N = int(input())
x, y = [], []
for i in range(N):
    xi, yi = map(int, input().split(" "))
    x.append(xi)
    y.append(yi)

ans = 0
for perm in itertools.permutations(range(N)):
    for i in range(0, N - 1):
        ans += math.sqrt((x[perm[i]] - x[perm[i + 1]]) ** 2 + (y[perm[i]] - y[perm[i + 1]]) ** 2)

print(ans / fact(N))

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

int main() {
    int n, ma, mb;
    int a[40], b[40], c[40];
    cin >> n >> ma >> mb;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }

    int dp[401][401];
    for (int i = 0; i < 401 * 401; i++) {
        dp[0][i] = 9999;
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int y = 400 - b[i]; y >= 0; y--) {
            for (int x = 400 - a[i]; x >= 0; x--) {
                if (dp[y][x] == 9999) continue;
                dp[y + b[i]][x + a[i]] = min(dp[y + b[i]][x + a[i]], dp[y][x] + c[i]);
            }
        }
    }

    int min_c = 9999;
    for (int i = 1;; i++) {
        if (i * ma > 400 || i * mb > 400) break;
        min_c = min(min_c, dp[i * mb][i * ma]);
    }
    cout << (min_c == 9999 ? -1 : min_c) << endl;
    return 0;
}


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

int main(){
  string S,T,U;
  int A,B;
  
  cin>>S>>T;
  cin>>A>>B;
  cin>>U;
  
  if(S==U){
    A-=1;
  }else{
    B-=1;
  }
  cout<<A<<" "<<B<<endl;
}

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

using namespace std;

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

	int n;
	cin >> n;
	
	vector<int> d;
	d.resize(n);

	vector<pair<int, int> > e;

	vector<vector<int> > G;
	G.resize(n);

	for(int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		e.emplace_back(a, b);

		G[a].emplace_back(b);
		G[b].emplace_back(a);

		++d[a];
		++d[b];

	}
	
	int ans = 0;
	
	for(int i = 0; i < n; ++i) {
		ans = max(ans, d[i]);
	}

	cout << ans << '\n';

	vector<int> p;
	p.resize(n);

	map<pair<int, int>, int> c;

	function<void(int, int)> dfs = [&] (int u, int f) {
		for(auto v : G[u]) {
			if(v != f) {
				if(c.count(minmax(u, f)) && p[u] == c[minmax(u, f)]) {
					++p[u];
				}
				
				c[minmax(u, v)] = p[u]++;

				dfs(v, u);
			}
		}
	};

	dfs(0, -1);

	for(auto& p : e) {
		cout << c[minmax(p.first, p.second)] + 1 << '\n';
	}

	return 0;
}

Measured memory_bytes: 17276
def main():
    a, b, c, k = (int(x) for x in input().split())
    ans = 0
    if k <= a:
        ans += k
    elif a + b < k and k > a:
        ans += 2 * a + b - k
    elif a + b >= k and k > a:
        ans += a

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9184
//package gfg;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

 class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
////		int t=Integer.parseInt(br.readLine().trim());
//		while(t-->0)
//		{
			String[] s1=br.readLine().split(" ");
			int n=Integer.parseInt(s1[0].trim());	
			int k=Integer.parseInt(s1[1].trim());	
			String[] s=br.readLine().split(" ");
			int[] a=new int[n];
			for(int i=0;i<n;i++)
			{
				a[i]=Integer.parseInt(s[i].trim());
			}
			
			System.out.println(algo(a,k));
		
//		}
	}

	public static int algo(int[] a,int k) {
		Arrays.sort(a);
		int sum=0;
		for(int i=0;i<k;i++) {
			sum+=a[i];
		}
		
		return sum;
		
	}
	
	
	
}



Measured memory_bytes: 33024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin>>n;
  int a=0;
  string s;
  cin>>s;
  for(int i=0; i<n-1; i++){
    if(s[i]!=s[i+1])
      a++;
  }
  cout<<a+1<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    cin >> s;
    int count=0, result=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='A' || s[i]=='T' || s[i]=='G' || s[i]=='C'){
            count++;
            result = max(result, count);
        } else {
            count=0;
        }
    }
    cout << result << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll n, m, x, c[12] = {}, a[12][12] = {}, ans = 1e7;

void dfs(ll cur, vector<ll> u, ll cst) {
	if (cur < n - 1) {
		dfs(cur + 1, u, cst);
		rep(i, m)u[i] += a[cur][i];
		dfs(cur + 1, u, cst + c[cur]);
	}
	else {
		bool ok = true;
		rep(i, m) {
			if (u[i] < x)ok = false;
		}
		if (ok)ans = min(ans, cst);
		rep(i, m)u[i] += a[n - 1][i];
		ok = true;
		rep(i, m) {
			if (u[i] < x)ok = false;
		}
		if (ok)ans = min(ans, cst + c[n - 1]);
	}
}

int main() {
	cin >> n >> m >> x;
	vector<ll> u(m);
	rep(i, n) {
		cin >> c[i];
		rep(j, m)cin >> a[i][j];
	}
	dfs(0, u, 0);
	if (ans < 1e7) {
		cout << ans << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define umii            unordered_map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define rep(i,st,end)   for(int i=st;i<end;i++)
#define w(x)            int x; cin>>x; while(x--)
//mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void s_g_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
	s_g_c();
	int t, d, count = 0;
	cin >> t >> d;
	while (t--)
	{
		int a, b;
		cin >> a >> b;
		int ans = a * a + b * b;
		if (ans <= d * d)
			count++;
	}
	cout << count;
	return 0;
}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
int a, b, sx, sy, ex, ey, color[1050][1050], dis[1000050];
int direx[4] = {1, 0, -1, 0};
int direy[4] = {0, 1, 0, -1};
string str[1050];
void bfs(int x, int y)
{
	queue<int> Q; Q.push(x); Q.push(y);
	while(!Q.empty())
	{
		int tx = Q.front(); Q.pop();
		int ty = Q.front(); Q.pop();
		for(int i=0; i<4; i++)
		{
			int dx = tx + direx[i];
			int dy = ty + direy[i];
			if(dx < 0 || dx >= a || dy < 0 || dy >= b) continue;
			if(str[dx][dy] == '#') continue;
			if(color[dx][dy]) continue;
			color[dx][dy] = color[tx][ty];
			Q.push(dx); Q.push(dy); 
		}
	}
}
vector<int> V[1000050];
void cal(int now)
{
	queue<int> Q;
	Q.push(now);
	while(!Q.empty())
	{
		int top = Q.front(); Q.pop();
		for(int x : V[top])
		{
			if(dis[x] != 2e9) continue;
			dis[x] = dis[top] + 1;
			Q.push(x);
		}
	}
}
int main()
{
	cin >> a >> b >> sx >> sy >> ex >> ey;
	sx --; sy --; ex --; ey --;
	for(int i=0; i<a; i++)
		cin >> str[i];
	int now = 1;
	for(int i=0; i<a; i++)
	{
		for(int j=0; j<b; j++)
		{
			if(color[i][j] || str[i][j] == '#') continue;
			color[i][j] = now ++;
			bfs(i, j);
		}
	}
	// for(int i=0; i<a; i++)
	// {
	// 	for(int j=0; j<b; j++)
	// 		cout << color[i][j] << ' ';
	// 	cout << '\n';
	// }
	for(int i=0; i<a; i ++)
	{
		for(int j=0; j<b; j++)
		{
			if(str[i][j] == '#') continue;
			for(int k=i - 2; k <= i + 2; k ++)
			{
				for(int l=j - 2; l <= j + 2; l ++)
				{
					if(k < 0 || k >= a || l < 0 || l >= b) continue;
					if(str[k][l] == '#') continue;
					if(color[i][j] == color[k][l]) continue;
					V[color[i][j]].push_back(color[k][l]);
				}
			}
		}
	}
	for(int i=1; i<now; i++)
		dis[i] = 2e9;
	dis[color[sx][sy]] = 0;
	cal(color[sx][sy]);
	if(dis[color[ex][ey]] == 2e9) dis[color[ex][ey]] = -1;
	cout << dis[color[ex][ey]] << '\n';
}

Measured memory_bytes: 44720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    if (n == 3) {
        printf("2 5 63\n");
        return 0;
    }
    if (n == 4) {
        printf("2 5 20 63\n");
        return 0;
    }
    if (n == 5) {
        printf("3 5 6 8 38\n");
        return 0;
    }
    vector<ll> ans(n);
    ans[0] = 2;
    ans[1] = 3;
    ll sum = 5, idx = 2;
    reps(i, 4, 30001) {
        if ((i % 2 != 0) && (i % 3 != 0)) continue;
        sum += i;
        ans[idx++] = i;
        if (idx == n) break;
    }
    if (sum % 6 != 0) {
        ll rem = 6 - sum % 6;
        rrep(i, n) {
            if (((ans[i] + rem) % 2 == 0) || ((ans[i] + rem) % 3 == 0)) {
                ans[i] += rem;
                rem = 0;
            }
            else {
                ans[i] += (rem - 1);
                rem = 1;
            }
            if (rem == 0) break;
        }
    }
    rep(i, n) printf("%lld%s", ans[i], (i == (n - 1)) ? "\n" : " ");
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n,m,sum,c[110],d[110];
    string s[110],b;

    while(cin >> n >> m,n!=0&&m!=0){
        for(int i=0;i<n;i++){
            cin >> s[i] >> c[i];
            d[i] = 0;
            if(s[i].rfind("*") != string::npos) d[i] = s[i].rfind("*")+1;
        }
    
        sum = 0;
        for(int i=0;i<m;i++){
            cin >> b;
            for(int j=0;j<n;j++){
                if(b.substr(d[j],8-d[j]) == s[j].substr(d[j],8-d[j])) sum += c[j];
            }
        }
        cout << sum << endl;
    }
    
    return 0;
}



Measured memory_bytes: 3152
#include <set>
#include <cstdio>
#define f first
#define s second
#define mp make_pair

using namespace std;

int main(){
  int n; scanf("%d", &n);
  while(n --> 0){
    pair<int, pair<int, int> > ans = mp(0, mp(0, 0));

    int x = 0;
    int y = 0;
    
    while(true){
      int dx, dy;
      scanf("%d%d", &dx, &dy);

      if(dx == 0 && dy == 0) break;

      x += dx; y += dy;
      int dist = x * x + y * y;

      ans = max(ans, mp(dist, mp(x, y)));
    }

    printf("%d %d\n", ans.s.f, ans.s.s);
  }

  return 0;
}

Measured memory_bytes: 0
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

using ll = long long;

int n, m;
vector<pair<ll, ll>> ab;

ll solve() {
  sort(ab.begin(), ab.end());
  ll h{}, ans{};
  REP(i, n) {
    ll a, b;
    tie(a, b) = ab[i];
    if (m - h <= b) {
      ans += (m - h) * a;
      h += m - h;
    } else {
      ans += a * b;
      h += b;
    }
    if (h == m) {
      // cout << "abc" << endl;
      break;
    }
  }
  return ans;
}

int main() {
  cin >> n >> m;
  REP(i, n) {
    int in_a, in_b;
    cin >> in_a >> in_b;
    ab.emplace_back(in_a, in_b);
  }
  cout << solve() << endl;
}


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

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

const long long MOD = 1000000007;

int main(){
  int a,b,c,k;
  cin >> a >> b >> c >> k;
  rep(i,k){
    if(a>=b) b*=2;
    else c*=2;
  }
  if(a<b && b<c) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3632
import scala.io.StdIn.readLine

object Main {
  def main(args: Array[String]) {
    def printRectangle: Unit = {
      val Array(a, b) = readLine().split(" ").map(_.toInt)
      if(a != 0 || b != 0) {
        for(i <- 0 until a) {
          println("#" * b)
        }

        println()
        printRectangle
      }
    }

    printRectangle
  }
}

Measured memory_bytes: 45076
#include <bits/stdc++.h>
#define rep(i, n) for (Int i = 0; i < (Int)(n); i++)
typedef int64_t Int;
using namespace std;
 
int main(){
    Int N, P; string S;
    cin >> N >> P >> S;

    reverse(S.begin(), S.end());
    
    Int sum = 0, ansP = 0, pow = 1;
    vector<Int> cnt(10000,0); cnt[0] = 1;
    rep(i, N){
        int c = S[i] - '0';
        if(c % P == 0) ansP += N-i;
        sum = (sum + c*pow) % P;
        cnt[sum]++; pow = (pow*10) % P;
    }

    if(P == 2 || P == 5){
        cout << ansP << endl;
    } else {
        Int ans = 0;
        rep(i, P) ans += cnt[i]*(cnt[i]-1)/2;
        cout << ans << endl;
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<=(b);++(i))
#define rep(i, n)  FOR(i,0,n-1)
#define FFOR(i, a, b) for(int (i)=a;(i)>(b);--(i))
#define rrep(i,n) FFOR(i,0,n)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define lb long double
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define int long long
#define double long double
#define mod 1000000007LL
#define INF 123456789012345
typedef pair<ll, ll> P;
typedef pair<int, P> PP;

const int maxn =1e5 + 10;


signed main(){

	int n;cin>>n;
	int ans = 0;
	rep(i,n)
	{
		int x;cin>>x;
		ans += x;
	}
	cout << ans - n<<endl;
	

}

Measured memory_bytes: 256
import sys

X, Y = map(int, input().split())
mod = int(1e9) + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


# 組み合わせ(1e9+7で割る場合)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


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

# 方針：Xについてすべての動かし方を列挙する。Yに符合すれば組み合わせ計算、それ以外であれば没
kake = 0
ans = 0
while X >= 0:
    temp = X
    if temp*2 + kake*1 == Y:
        ans += cmb(temp + kake, kake, mod)
    kake += 1
    X -= 2
print(ans)


Measured memory_bytes: 167860
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
#define repd(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a) memset(a,0,sizeof(a));
#define il inline
#define sz(a) ((int)o.size())
#define run(x) for(int k=head[x];k;k=e[k].ne)
#define v e[k].t
#define all(a) o.begin(),o.end()
#define mp make_pair
#define pb push_back 
#define w1 first
#define w2 second
#define adm(a,b,c) {a=a+b;if(a>=c)a-=c;else if(a<0)a+=c;}
typedef double db;
typedef long long ll;typedef long double ld;typedef unsigned long long ull;
typedef pair<int,int> pa;
const int N=1e6+5,M=1e7+5,INF=1e9,mod=1e9+7;
const ll linf=1e18;const double eps=1e-8,pi=acos(-1);
il int gmin(int &a,int b){if(a>b)a=b;}il ll gmin(ll &a,ll b){if(a>b)a=b;}il int gmax(int &a,int b){if(a<b)a=b;}il ll gmax(ll &a,ll b){if(a<b)a=b;}
il void read(ll&x){ll f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il ll read(ll&x,ll&y){read(x);read(y);}
il void read(int&x){int f=1,t=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}x=t*f;}il int read(int&x,int&y){read(x);read(y);}
il void read(int&a,int&b,int&c){read(a);read(b);read(c);}il void read(ll&a,ll&b,ll&c){read(a);read(b);read(c);}
il int read(){int x;read(x);return x;}
il ll qpow(ll a,ll b,ll p){ll ret=1;for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;return ret;}il ll qpow(ll a,ll b){ll ret=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod;return ret;}
il ll qmul(ll a,ll b,ll p){ll ret=0;for(;b;b>>=1,a=(a<<1)%p)if(b&1)adm(ret,a,p);return ret;}il ll qmul(ll a,ll b){ll ret=0;for(;b;b>>=1,a=(a<<1)%mod)if(b&1)adm(ret,a,mod);return ret;}
il void judge(){
	freopen("dato.in","r",stdin);
	freopen("dato.out","w",stdout);
}
int n,res=1,a[N],vis[N],d[N],len[N],cnt[N];
ll f[N];
void gao(int n,int m){
	ll f1=1;if(n>1&&n%2==1)f1++;
	f[0]=1;f[1]=f1;
	rep(i,2,m)(f[i]=f1*f[i-1]%mod+f[i-2]*(i-1)%mod*n%mod)%=mod;
	res=res*f[m]%mod;
}
int main(){
	read(n);rep(i,1,n)read(a[i]),d[a[i]]++;
	rep(i,1,n)if(d[i]>2)return puts("0"),0;
	rep(i,1,n)if(!d[i]){
		int x=i,sz=0;
		for(;d[x]<2;x=a[x])vis[x]=1,sz++;
		len[x]=sz;
	}
	rep(i,1,n)if(!vis[i]){
		int x;vector<int>o;
		for(x=i;!vis[x];x=a[x])vis[x]=1,o.pb(x);
		if(x!=i)return puts("0"),0;
		int isc=1;re(j,0,o.size())if(len[o[j]])isc=0;
		if(isc)cnt[o.size()]++;else{
			int tmp=1;
			repd(j,o.size()-1,0)if(!len[o[j]])tmp++;else break;
			re(j,0,o.size())if(len[o[j]]){
				if(len[o[j]]<tmp)res=res*2%mod;
				if(len[o[j]]>tmp)return puts("0"),0;
				tmp=1;
			}else tmp++;
		}
	}rep(i,1,n)if(cnt[i])gao(i,cnt[i]);
	cout<<res<<endl;
}

Measured memory_bytes: 11000
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;
using ll=long long;

#define rep(i, a, n) for (int i = (a); i < (n); i++)
#define repr(i, a, n) for (int i = (n); i >= (a); i--)

void Main(){
  int l,n;
  cin>>n>>l;
  vector<string> s;
  string m;
  rep(i,0,n){cin>>m;s.push_back(m);}
  sort(s.begin(),s.end());
  rep(i,0,n){cout<<s[i];}
  cout<<endl;
}

int main(){
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  Main();
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)


function main()
    n,m=parseMap(split(readline()))
    a=sort(parseMap(split(readline())))
    l,r=1,1<<30
    x=0
    while r-l>1
        i=l+(r-l)>>1
        d=m
        k=0
        for j in 1:n
            num=a[j]
            while i<=num
                num÷=2
                d-=1
            end
            k+=num
        end
        if d>=0
            r=i
            x=k-i÷2*d
        else
            l=i
        end
    end
    if x>0
        println(x)
    else
        println(0)
    end
end
main()

Measured memory_bytes: 169200
s=input()
N=len(s)
ans=0
data=[]
i=0
while N>i:
    if s[i]=='A':
        data.append('X')
        i+=1
    elif s[i]=='B' and i<len(s)-1 and s[i+1]=='C':
        data.append('A')
        i+=2
    else:
        index=[]
        count=0
        for j in range(0,len(data)):
            if data[j]=='A':
                index.append(j)
                count+=1

        for j in range(count):
            ans+=index[j]-j
        data=[]
        i+=1
else:
    if data:
        index=[]
        count=0
        for j in range(0,len(data)):
            if data[j]=='A':
                index.append(j)
                count+=1

        s=0
        for j in range(count):
            s+=index[j]-j

        ans+=s

print(ans)

Measured memory_bytes: 7144
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    l = [x - i for i, x in enumerate(a)]
    from collections import Counter
    c = Counter(l)
    ans = 0
    for i in range(n):
        index = -i * 2 - l[i]
        ans += c[index] if index in c else 0
        c[l[i]] -= 1
    print(ans)


if __name__ == '__main__':
    resolve()


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

#define pb push_back
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(); cin.tie(0); cout.tie(0);
#define debug(x...) cerr << "[" << #x << "]: " << x << "\n";

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pl;

int const N = 2e5 + 7;
int dp[N];
int mod[N][2]; //0: k-1, 1: k+1

int n;
char s[N];

inline int popcount(int n)
{	
	int res = 0;
	while (n)
	{
		res += (n & 1);
		n = (n >> 1);
	}
	return res;
}

inline int modulo(int idx, int k)
{
	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		if (s[i] == '1')
			res = (res + mod[i][idx]) % k;
	}
	return res;
}

int main()
{
	fastio;

	dp[0] = 0;
	for (int i = 1; i < N; ++i)	
		dp[i] = 1 + dp[i % popcount(i)];
	
	cin >> n;
	cin >> s;

	int k = 0;
	for (int i = 0; i < n; ++i)
		k += (s[i] == '1');


	int a; //S mod (k-1)
	int b; //S mod (k+1);

	if (k != 1)
	{
		mod[n-1][0] = 1 % (k-1);
		for (int i = n-2; i >= 0; --i)
			mod[i][0] = (mod[i+1][0] * 2) % (k-1);

		a = modulo(0, k-1);
	}

	if (k != n)
	{
		mod[n-1][1] = 1 % (k+1);
		for (int i = n-2; i >= 0; --i)
			mod[i][1] = (mod[i+1][1] * 2) % (k+1);

		b = modulo(1, k+1);
	}


	for (int i = 0; i < n; ++i)
	{
		if (k == 1 && s[i] == '1')
		{
			cout << 0 << '\n';
		}
		else if (s[i] == '0')
		{
			int res = (b + mod[i][1]) % (k+1);
			cout << dp[res] + 1 << '\n';
		}
		else
		{
			int res = (((a - mod[i][0]) % (k-1)) + k-1) % (k-1);
			cout << dp[res] + 1 << '\n';
		}
	}

	return 0;
}


Measured memory_bytes: 6120
#include<stdio.h>
#include<string.h>
 
#define N 3
#define LIM 32
#define HN 362897
 
struct dep{
    int depth,key;
};
 
int ans[N][N]={
    {1,2,3},
    {4,5,6},
    {7,8,0}};
 
int min = LIM;
struct dep h[HN];
 
int hash1(int k){
    return k % HN;
}
int hash2(int k){
    return 1 + k%(HN-1);
}
int hash(int k, int i){
    return (hash1(k) + i*hash2(k))%HN;
}
 
 
void dfs(int p[N][N], int n){
    int i,j,i0,j0,a=0,b=1;
    int f=0;
    int tmp[N][N];
    //printf("A\n");
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            if(ans[i][j]!=p[i][j])f++;
            if(p[i][j]==0)
            {
                i0=i;
                j0=j;
            }
            a+=p[i][j]*b;
            b*=10;
        }
    }
     
    if(f==0)
    {
        if(min>=n)
        {
            min=n;
        }
        return;
    }
    if(n>min) return;
    i=0;
    while(1)
    {
        b=hash(a, i);
        if(h[b].key == 0)
        {
            h[b].key=a;
            h[b].depth=n;
            break;
        }
        else if(h[b].key == a)
        {
            if(h[b].depth>n)
            {
                h[b].depth=n;
                break;
            }
            else return;
        }
        i++;
    }
     
    if(i0>0 && i0<N)
    {
        memcpy(tmp,p,sizeof(int)*N*N);
        f=tmp[i0][j0];
        tmp[i0][j0]=tmp[i0-1][j0];
        tmp[i0-1][j0]=f;
        dfs(tmp, n+1);
    }
    if(j0>0 && j0<N)
    {
        memcpy(tmp,p,sizeof(int)*N*N);
        f=tmp[i0][j0];
        tmp[i0][j0]=tmp[i0][j0-1];
        tmp[i0][j0-1]=f;
        dfs(tmp, n+1);
    }
     
    if(i0>=0 && i0<N-1)
    {
        memcpy(tmp,p,sizeof(int)*N*N);
        f=tmp[i0][j0];
        tmp[i0][j0]=tmp[i0+1][j0];
        tmp[i0+1][j0]=f;
        dfs(tmp, n+1);
    }
    if(j0>=0 && j0<N-1)
    {
        memcpy(tmp,p,sizeof(int)*N*N);
        f=tmp[i0][j0];
        tmp[i0][j0]=tmp[i0][j0+1];
        tmp[i0][j0+1]=f;
        dfs(tmp, n+1);
    }
     
}
 
int main(){
    int i,j;
    int p[N][N];
     
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            scanf("%d",&p[i][j]);
        }
    }
    dfs(p,0);
     
    printf("%d\n",min);
     
    return 0;
}

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

int num[101];//各a_iの個数をカウントする
int main() {
	int N;
	cin >> N;
	int mx = 0, mn = 1000;//a_iの最大値と最小値
	for(int i=0; i<N; i++){
		int a; cin >> a;
		mx = max(mx, a);
		mn = min(mn, a);
		num[a]++;
	}
	bool ok = true;
	//maxが偶数の時
	if (mx % 2 == 0) {
		//minはmaxの半分でなければダメ
		if (mn != mx / 2)ok = false;

		//a_iがminとなるiは1つだけで、それ以上増やせない
		if (num[mn] != 1)ok = false;

		//a_iがmn+1~mxとなるiは少なくとも2つなのでそれを下回っていればImpossible
		for (int i = mn+1; i <= mx; i++){
			if (num[i] < 2) {
				ok = false;
			}
		}
	}
	//maxが奇数の時
	else {
		//minは(max+1)の半分でなければダメ
		if (mn != (mx + 1) / 2)ok = false;

		//a_iがmaxとなるiは2つだけで、それ以上増やせない
		if (num[mn] != 2)ok = false;

		//a_iがmn+1~mxとなるiは少なくとも2つなのでそれを下回っていればImpossible
		for (int i = mn + 1; i <= mx; i++) {
			if (num[i] < 2) {
				ok = false;
				if (ok)cout << "ok" << endl;
			}
		}
	}
	if (ok) {
		cout << "Possible" << endl;
	}
	else {
		cout << "Impossible" << endl;
	}
}

Measured memory_bytes: 256
import java.util.*;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner stdIn = new Scanner(System.in);
		boolean firstFlag = true;
		while(stdIn.hasNext())
		{
			int count = 0;
			int a = stdIn.nextInt();
			int b = stdIn.nextInt();
			if(a == 0 && b == 0)
			{
				break;
			}
			if(!firstFlag)
			{
				System.out.println("");
			}
			firstFlag = false;
			for(int i = a; i <= b; ++i)
			{
				if(i % 4 == 0)
				{
					if(i % 100 == 0 && i % 400 == 0)
					{
						System.out.println(i);
						++count;
					}
					else if(i % 100 != 0)
					{
						System.out.println(i);
						++count;
					}
				}
			}
			if(count == 0)
			{
				System.out.println("NA");
			}
		}
	}
}

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

int main() {
    int n, k;
    double a=0;
    cin >> n >> k;
    vector<double> vec(n);
    vector<double> kita(n), s(n+1);
    s.at(0)=0;
    cout << fixed << setprecision(7);
    for(int i=0; i<n; i++) {
        cin >> vec.at(i);
        kita.at(i) = vec.at(i) * (vec.at(i)+1)/2/vec.at(i); 
        s.at(i+1) = s.at(i)+kita.at(i);
    }
    for(int i=0; i<=n-k; i++) {
        a=max(a,s.at(i+k)-s.at(i));
    }
    cout << a << endl;
}

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

int main() {
  long n,m,ans=1,mod=1000000007;
  cin >> n >> m;
  vector<long> s(n),t(m),a(m,1);
  for(long i=0;i<n;i++) cin >> s[i];
  for(long i=0;i<m;i++) cin >> t[i];
  
  for(long i=0;i<n;i++) {
    long x=0;
    for(long j=0;j<m;j++) {
      if(s[i]==t[j]) {
        long y=(x+a[j])%mod;
        ans=(ans+a[j])%mod;
        a[j]=(a[j]+x)%mod;
        x=y;
      } else {
        a[j]=(a[j]+x)%mod;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
typedef long long ll;
const long long MOD=1e09+7;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back



ll firstprime(ll n, vector<long long> &data){
  ll answer=0;
  for (ll i=2;i*i<=n;i++){
    if (data.at(i)==1 and n%i==0){
      answer=i;
      break;
    }
  }
  
  return answer;
}







int main(){

    long long n;
    cin>>n;
 long long lastcheck=n;
  
  

    vector<long long> data(1000001,1);

    data.at(0)=0;
    data.at(1)=0;

    int s=int(data.size());

    for (ll i=2;i<s;i++){
        if (data.at(i)==1){
            for (ll j=2*i;j<s;j+=i){
                data.at(j)=0;
            }
        }
    }
  
  
  map<ll,ll> primes;
  
  while (firstprime(n,data)!=0){
    ll tmp=firstprime(n,data);
    if (primes.find(tmp)!=primes.end()){
      primes[tmp]+=1;
    }
    else {
      primes[tmp]=1;
    }
    n/=tmp;
  }
  
  primes[n]++;
  

  ll myanswer=0;
  
  for (auto mypair:primes){
    int cnt=mypair.second;
    int tmp=1;
    int answercount=2;
    
    while (tmp+answercount<=cnt){
      tmp+=answercount;
      answercount++;
    }
    myanswer+=answercount-1;
  }
  
  if (lastcheck==1){
    myanswer=0;
  }
  
  
  cout<<myanswer<<endl;
    
    
    
  






}

Measured memory_bytes: 11152
#![allow(unused_macros, unused_imports, dead_code)]

use std::io;

fn read_line() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s
}

macro_rules! from_line {
    ($($a:ident : $t:ty),+) => {
        $(let $a: $t;)+
        {
            let _line = read_line();
            let mut _it = _line.trim().split_whitespace();
            $($a = _it.next().unwrap().parse().unwrap();)+
            assert!(_it.next().is_none());
        }
    };
}

fn main() {
    from_line!(x: u32);
    let y = x.pow(3);
    println!("{}", y);
}


Measured memory_bytes: 5024
// atcoder/abc149/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  int r, s, p;
  string t;
  while (cin >> n >> k >> r >> s >> p >> t) {
    for (int i = 0; i < t.size(); ++i) {
      t[i] = toupper(t[i]);
    }

    map<char, char> win;
    win['P'] = 'S';
    win['S'] = 'R';
    win['R'] = 'P';

    const int N = 1e5 + 5;
    static bool vis[N];
    fill(vis, vis + N, false);

    vector<string> v;
    for (int i = 0; i < t.size(); ++i) {
      if (vis[i]) break;
      string x;
      for (int j = i; j < t.size(); j += k) {
        x += t[j];
        vis[j] = true;
      }
      v.push_back(x);
    }
    // cout << v << endl;

    const int R = 0;
    const int P = 1;
    const int S = 2;
    const int X = 3;

    map<int, char> rev;
    rev[R] = 'R';
    rev[P] = 'P';
    rev[S] = 'S';

    auto score = [&] (char c) {
      if (c == R) return r;
      if (c == P) return p;
      if (c == S) return s;
      assert(false);
    };

    lli sum = 0;
    each (x, v) {
      const int M = 4;
      static lli dp[N][M];

      for (int i = 0; i < x.size() + 2; ++i) {
        for (int j = 0; j < M; ++j) {
          dp[i][j] = -(1LL << 60);
        }
      }

      dp[0][X] = 0;
      for (int i = 0; i < x.size(); ++i) {
        for (int last = 0; last <= 3; ++last) {
          if (dp[i][last] < 0) continue;
          for (int next = 0; next < 3; ++next) {
            if (last == next) continue;
            assert(rev[next]);
            if (win[x[i]] == rev[next]) {
              setmax(dp[i + 1][next], dp[i][last] + score(next));
            } else {
              setmax(dp[i + 1][next], dp[i][last]);
            }
          }
        }
      }
      lli mx = 0;
      for (int i = 0; i < x.size() + 2; ++i) {
        for (int j = 0; j < M; ++j) {
          setmax(mx, dp[i][j]);
        }
      }
      sum += mx;
    }
    cout << sum << endl;
  }

  return 0;
}


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

int main(){
  int n,m;
  cin>>n>>m;

  long long sum=0;
  for(int i=0; i<m; i++){
	long long k;
    cin>>k;
    sum+=k;
  }
  if(sum>n){
    cout<<"-1";
  }
  else{
    cout<<n - sum;
  }
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <limits>
#include <cfenv>
#include <cmath>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <tuple>
#include <queue>
#include <vector>
#include <cmath>
#include <random>
#include <math.h>
#include <list>
#include <random>
#include <functional>


#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) for(int (i) = (n) - 1; (i) >= 0; --(i))
#define ALL(TheArray) TheArray.begin(), TheArray.end()

using lli = long long int;
using pii = std::pair<int, int>;

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



// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



std::vector<int> In;
std::vector<std::vector<int>> Edge;
std::vector<int> S;

int main(void){
    int n, m; scanf("%d%d", &n, &m);
    Edge.resize(n); In.resize(n, 0);
    REP(i, n + m-1){
        int a, b; scanf("%d%d", &a, &b); a--; b--;
        Edge[b].push_back(a); In[a]++;
    }
    S.resize(n, 0);
    std::queue<int> Q;
    REP(i, n) if(In[i] == 0) Q.push(i);
    while(not Q.empty()){
        int v = Q.front(); Q.pop();
        for(int nv : Edge[v]){
            if((--In[nv]) == 0){
                S[nv] = S[v] + 1;
                Q.push(nv);
            }
        }
    }
    REP(i, n){
        if(Edge[i].size() == 0) puts("0");
        else{
            int pr, d = 2e9;
            for(int v : Edge[i]){
                if(S[v] < d){d = S[v]; pr = v;}
            }
            printf("%d\n", pr+1);
        }
    }



  
    return 0;
}

Measured memory_bytes: 7552
// きさま！ 見ているなッ！

#include<iostream>
#include<queue>
#include<memory>
#include<map>
#include<set>
#include<unordered_map>
#include<array>
#include<vector>
#include<algorithm>
#include<list>
#include<limits>
#include<stdio.h>
#include<math.h>
#include<string>
#include<thread>

using namespace std;
using ll = long long;
using vec = vector<int>;
using mat = vector<vec>;
using lst = list<ll>;

const ll MOD = 1000000007;


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

	cout << (N*(N-1)/2 + M*(M - 1) / 2) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std;
int main(){
int a,b,c,x;
cin>>a>>b>>c>>x;
int ans=0;
for(int i=0;i<=a;i++)
for(int j=0;j<=b;j++)
{
int d=x-i*500-j*100;
if(d%50==0 && d/50<=c && d>=0)
ans++;
d=x;}
cout<<ans;
return 0;
}

Measured memory_bytes: 256
/* ***********************************************
Author        :yang12138
Created Time  :2017年07月07日 星期五 16时08分26秒
File Name     :A.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

const int N=2e5+10;

int ans[N<<1];

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

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

	int l=N,r=N;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(i&1) ans[r++]=x;
		else ans[--l]=x;
	}

	if(n&1) reverse(ans+l,ans+r);

	for(int i=l;i<r;i++){
		printf("%d%c",ans[i],i==r-1?'\n':' ');
	}
    
    return 0;
}


Measured memory_bytes: 3072
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <string>

using namespace std;
typedef long long ll;

int main() {
    string S;
    cin >> S;
    if(S.size()==1){
        cout << S << endl;
        return 0;
    }
    for(int i=1;i<S.size();i++){
        if(S[i]!='9') break;
        if(i==S.size()-1){
            cout << 9*(S.size()-1)+(S[0]-'0') << endl;
            return 0;
        }
    }
    cout << 9*(S.size()-1)+(S[0]-'0')-1 << endl;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;

int main(){

    ll N; cin >> N;
    map<ll, ll > mp;
    for(ll i = 0; i < N; i++){
        ll t; cin >> t;
        mp[t]++;
    }

    ll sum = 0;

    auto begin = mp.begin(), end = mp.end();
    for (auto iter = begin; iter != end; iter++) {
        if(iter->second % 2 != 0){
            sum++;
        }
    }    

    cout << sum << endl;

}

Measured memory_bytes: 6528
/**
 * author:    Ziel
 * created:   27.04.2020 11:22:49
**/

// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	
	int n, m;
	cin >> n >> m;
	
	vector<int> a(n);
	for (int& i: a) cin >> i;
	sort(all(a), greater<int>());
	vector<ii> b(m);
	for (int i = 0; i < m; i++) cin >> b[i].se >> b[i].fi;
	sort(all(b), greater<ii>());
	
	int i = 0, j = 0, cnt = 0;
	ll sum = 0;
	while (true) {
		cnt++;
		if ((i < n && a[i] > b[j].fi) || j >= m) sum += a[i++];
		else if ((j < m && a[i] <= b[j].fi) || i >= n) {
			sum += b[j].fi;
			b[j].se--;
			if (b[j].se <= 0) j++;
		}
		if (cnt >= n) break;
	}
	
	cout << sum;
	return 0;
}

/*
	Raise your standard.
*/

Measured memory_bytes: 1408
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=(c+1,h,w),
print(1--d//K)

Measured memory_bytes: 75356
// ボール: 区別なし, 箱：区別なし, 入れ方: 1 個以上
// 分割数
// P(n, k) = P(n, k - 1) + P(n - k, k)
#include <iostream>
using namespace std;
const int MOD = 1000000007;
const long long MAXN = 1010;
long long P[MAXN][MAXN] = {};

void pertition_init() {
  for(int k = 0; k < MAXN; k++) P[0][k] = 1;
  for(int n = 1; n < MAXN; n++) {
    for(int k = 1; k < MAXN; k++) {
      P[n][k] += P[n][k - 1] + (n - k >= 0 ? P[n - k][k] : 0);
      P[n][k] %= MOD;
    }
  }
}

int main() {
  
  pertition_init();
  int n, k; cin >> n >> k;
  if(n - k < 0) cout << 0 << endl;
  else cout << P[n - k][k] << endl;
  return 0;
}



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

int main(){
  int a, b, c;
  
  cin >> a >> b >> c;
  
  if(a == b && b == c) cout << "No";
  else if(a != b && a != c && b != c) cout << "No";
  else cout << "Yes";
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
using namespace std;
int input(){
  int x;
  cin>>x;
  return x;
}
int abss(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}
int gcd(int x, int y){
	if(x<y){
    return gcd(y,x);
  }
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}



int main() {
  int N,X;
  cin>>N>>X;
  vector<int>x(N);
  for(int i=0;i<N;i++){
    cin>>x.at(i);
  }
  vector<int>zettai(N);
  for(int i=0;i<N;i++){
    zettai.at(i)=abss(X-x.at(i));
  }
  int max=zettai.at(0);
  for(int i=1;i<N;i++){
      max=gcd(zettai.at(i),max);
  }
  cout<<max<<endl;





  
  
  

  


}


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

int main() {
  int n;cin>>n;
  int one=n%10;
  if(one == 3) cout <<"bon"<<endl;
  else if(one == 0 || one == 1 || one == 6 ||one == 8) cout <<"pon"<<endl;
  else cout<<"hon"<<endl;
}


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

using namespace std;

long long n;
string str;

void solve2(){
    int i;
    vector<int> cnt;
    char c = str[0];
    cnt.push_back(1);
    for(i = 1;i < str.length();i++){
        if(str[i] != c){
            cnt.push_back(1);
            c = str[i];
        }
        else{
            cnt[cnt.size()-1] += 1;
        }
    }
    long long ans = 0;
    if(str[0] == str[str.length()-1]){
        ans += cnt[0]/2;
        ans += cnt.back()/2;
        for(i = 1;i < cnt.size()-1;i++) ans += cnt[i]/2*n;
        ans += (cnt[0]+cnt.back())/2*(n-1);
    }
    else{
        for(i = 0;i < cnt.size();i++) ans += cnt[i]/2*n;
    }
    cout << ans << endl;
}

void solve(){
    int i,j;
    cin >> str;
    cin >> n;
    for(i = 1;i < str.length();i++){
        if(str[i] != str[i-1]){
            solve2();
            return;
        }
    }
    cout << str.length()*n/2 << endl;
}

int main(){
    solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int alice = 0;
    int bob = 0;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end(),greater<>());
    for(int i=0; i<n; i++){
        if(i%2==0){
            alice += a[i];
        }else{
            bob += a[i];
        }
    }
    cout << alice - bob << endl;
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;

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

    cout << int(floor(X / 500) * 1000 + floor((X % 500) / 5) * 5) << endl;
}

Measured memory_bytes: 256